Introduction

The Prowl Language is a statically-typed stack-based programming language that draws from a wide range of inspirations, mainly functional, logic, and stack-based languages. However, the language is unique with its powerful program combinator system. Prowl exploits a homomorphism between string concatenation and concatenative languages that allows regex to be used as a computational and mental model for control flow. This model provides a rigid framework to solve combinatory and constraint problems (in addition to general purpose programming) yet retains performant translations into DFAs due to the regex base. With stacks for data and regex for control flow, Prowl provides a unique but ergonomic way to think about hard problems.

Prowl has 3 major influences that you should know about:

• The Kitten Language
• The Vinegar Language
• Oniguruma Regex

Prowl mirrors Kitten’s ambition in modernizing the concatenative paradigm with syntactic and semantic ML features. Prowl sheds its concatenative purity and imports key quality of life features such as infix, lexically scoped variable bindings, anonymous functions, destructuring, and pattern matching to elevate the language’s productivity and expressivity. From OCaml, we borrow a lot of syntax, binding operators, ML modules and functors, and even the plan for modular implicits. Indeed, Prowl does not shy away from the deeper developments of other languages – we also borrow some of Haskell’s common abstractions such as monoids, functors, and monads, and plan to use the modular implicits feature to support them and their infix operators. We also take significant inspiration from Joy, importing it's closures, stack combinators, and recursive combinators – the latter modified to better accomodate Prowl's spin.

Prowl also draws inspiration directly from Vinegar and Oniguruma Regex in its unique and powerful descriptions of control flow. It all starts with Vinegar’s key innovation:

• All operators can fail

While typical concatenative languages have functions of (in Haskell notation) Stack -> Stack, Vinegar has functions of Stack -> Maybe Stack. Every function can fail but can be handled with the alternation operator |, so that alternate branches can be tried if one fails. It’s an interesting novelty and variation of the paradigm, and it’s definitely worth checking out in its own right. However, Prowl takes things one step further by innovating that functions should be Stack -> List Stack, where the list is actually lazy in practice. This is to say that all functions produce some number of viable future stacks based off some past stack, and that we are guiding a search down these spaces, adding and pruning stacks as we move along.  We can then use concatenation to compose these functions, alternations to search down one list before the other, and then define quantifiers such as Kleene star in terms of the existing definitions of concatenation and alternation. Kleene stars and n-times quantifiers in regex are like while and for loops in imperative programming, and so it actually forms a nice basis to program in. And it’s efficient – regex control flow can target DFAs where edges are programs rather than characters, enabling some unique optimization opportunities, yet we retain Turing completeness with heap-allocated lists.  

Prowl is an ambitious language with a unique spin but aims to remain fully productive. If this sounds like it interests you, give the tutorial a look, as the parts are described in much greater detail.

Basics

Concatenative Programming

Prowl is a stack-based programming language. If you are not familiar with the paradigm, I would recommend you learn about it first by checking out some of the links in the introduction before moving on.

Comments

Let's begin our tour of the language with the comment syntax.

/* This is a comment */

/* Comments are 
multiline */

/* Comments can be /* nested */*/

Fundamentals

Let's kick things off with some of the most basic operations so you can use Prowl like a calculator.

Expressions

The first thing you should know about is that all files in Prowl are expressions. Most other languages like Python, C, Java, OCaml, and so on have a concept of top-level definitions, or something more complicated, which must house all the expressions you can write. In Prowl, not so - files are simply expressions.

Literals

In stack languages, all "values" are really functions, which operate between stacks. Literals are functions which accept a stack, any stack, and produce a new stack with the value representing the literal on top. Juxtaposing these functions composes them, which is how we can create new programs that do interesting things.

5  /* Places a 5 on the stack */
5 7  /* Places a 5 and then a 7 on the stack */

Prowl has many kinds of literals, here are some of them:

42  /* Integer */
2.3  /* Float */
"Hello!"  /* String */
'x'  /* Char */
<>  /* Unit */

Output

Prowl makes output easy using this one simple rule: the contents of the stack is printed at the end of execution, when the program completes. For the time being, there is no put (print) function - programs are pure - you must write your programs in a way such that the final stack contains your answer. 5 should print:

5

5 7 should print:

5
7

The values on the stack are printed last-final, so that they match the order of execution in a naive program.

Input

You may be wondering now how user input can be retrieved. Prowl makes this simple as well - command line arguments are placed on the stack at the start of execution. However, all command line arguments are placed as strings.

Program: 7 Invocation: prowl path/program.prw -i 5 Output:

5
7

Note again that 5 is a string, but strings are shown without quotes.

Arithmetic

Let's do some math! Prowl is unusual among stack languages in that it supports infix. It looks the same as in most other programming languages. Prowl also implements the operator precedence that you should be familiar with from math.

5 + 6

==> 11

5 - 1 - 2

==> 2

• + is add
• - is subtract
• * is multiply
• / is divide
• ** is power

Additionally, parentheses can be used for grouping.

6 * (1 + 1)

==> 12

Bindings

In order to write more complicated programs, we need to have ways to manipulate the stack. One way to do this is with concatenative combinators - and Prowl has those - but they can sometimes be difficult to reason about, forming "stack chatter". Prowl uses lexically-scoped bindings as a more gentle and flexible means of stack manipulation, while leaving concatenative combinators for terseness where it is a boon.

As Expressions

as expressions pop the top element from the stack at the time of execution and store it in the following name.

5 as x -> x + 1

In this program, 5 is placed on the stack. Then, 5 is popped from the stack and stored in x. Following the right of the arrow, x places it's bound value 5 to the stack, and it is added to 1, producing 6.

x can also be used multiple times:

5 as x -> x * x

==> 25

as can pop and bind multiple values off the stack

3 4 as x y -> x ** 2 + y ** 2

=> 25

In general, the -> arrow symbolizes producing a new scope. You can think of these expressions performing a substiution and producing a new expression, e.g. (5 as x -> x * x) produces the new expression (5 * 5), then simplifies.

Let Expressions

let expressions bind the result of the value on the right-hand side of the assignment to the name on the left-hand side.

let x = 5 -> x * x

==> 25, as before

Let Functions

let expressions support functions in their right-hand side - expressions are able to pop values off of a stack that they can't see yet. This produces a binding that then pops values, which can act as a function.

/* names may use - */
let norm-sqr = as x y -> x ** 2 + y ** 2 ->
3 4 norm-sqr

==> 25

Unlike as expressions, having multiple names following let uses those names as arguments, as sugar for a following as expression.

let norm-sqr x y = x ** 2 + y ** 2 -> 
3 4 norm-sqr

==> 25

Concatenation

In the previous example, we can see that 3 4 norm-sqr produces 25 as norm-sqr pops the two values before it from the stack and then pushes the result. These are always evaluated in left-to-right Reverse Polish Notation (RPN) order. Juxtaposing functions next to each other composes them, and is called concatenation. Concatenation has higher precedence than all infix operators (barring module access and the rare infix regex operators).

Sectioning

Prowl implements Haskell-style sectioning. This turns the arithmetic operations into concatenative RPN ones.

4 5 (+)

==> 9

Wrapping an infix operator in parenthesis makes it behave as it does in many other stack languages: it pops its two args from the stack, performs its operation, and pushes its result to the stack.

Operator precedence no longer exists in this style.

2 1 (+) 2 (-) 4 (*)

==> 4

Operators can also be partially applied with a particular input in an infix-like fashion, just like in Haskell.

5 (- 1)

==> 4

5 (1 -)

==> -4

(a `op`) becomes x as a `op` x
(`op` b) becomes x as x `op` b

We can use this with let as we saw with as

let z = 0 -> 
let s = (+ 1) -> 
z s s s

==> 3

Patterns

Patterns refer more generally to the names that succeed as and let. Prowl implements both destructuring and pattern matching, as we will see.

Most of the time, patterns are simply an identifier. This binds the expression to the pattern, and keeps it in the context. Patterns concatenate, allowing us to bind multiple values. However, we can also use pattern literals to assert for certain values.

Matching

A pattern such as as 0 -> will assert that the value that as pops is equal to the integer literal 0. If true, it simply carries on the execution past -> without any substitution. If false, the program is rejected, meaning it fails, and the program tells you this.

0 as 0 -> 5

==> 5

1 as 0 -> 5

==> rejected

Eithers

Let's introduce our first nontrivial data type - eithers. Eithers create a union between two types. As there can only be two of them, values are tagged either left or right.

A left value can be constructed with (... ;)

(5;)

A right value can be constructed with (; ...)

(;5)

As before, you can assert that a value is left or right, and extract that value once you've confirmed which kind it is.

(;5) as (;x) -> x

==> 5

These structures are useful when working with a value that can be two different types, e.g. an int or a str, and will appear more motivated once we explore error handling.

Destructuring

Pairs

Pairs can be created using (..., ...). Pairs place two values in a single spot in the stack. (5, 4) would place the pair of 5 and 4 on the stack.

Pairs can be destructured, meaning their value can be extracted. In this way, they are similar to eithers, but the pairs pattern cannot fail on its own in the absense of other patterns or type errors.

(3, 4) as (x, y) -> x ** 2 + y ** 2

==> 25

Captures

Captures are a special and important kind of data. They allow functions, which normally pop and push to the stack, to be literals that are placed on the stack. Captures may be known as quotes in other concatenative languages. However, Prowl captures are opaque - they can only be used for concatenative logic, not for metaprogramming.

Captures are created using { ... }, as in Kitten. They thunk the expression inside of them, meaning they stop execution. The expression {3 4} places, on the stack, the function that pops none and pushes 3 and 4. The expression {+ 1} pushes to the stack the function that pops an integer, adds 1 to it, and pushes the new number.

While there are many ways to call captures, including concatenative combinators and many library functions, one way is to simply use pattern matching.

{7 8} as {f} -> f (*)

==> 56

The previous example pushes the function that places 7 and 8 to the stack. Then, the capture is destructured in as, and the bare function is bound to f. f is then executed, placing 7 and 8 on the stack, and then they are multiplied.

Control Flow

We have previously explored much of the concatenative & stack behaviors of the language, inspired largely by Kitten. It's now time to move onto control flow, inspired largely by Vinegar, and organized syntactically with regex.

Control flow in Prowl is based on regex. The two key events are acceptance and rejection. All functions receive a stack as input. A function that accepts its input returns a stack as an output, or sometimes many stacks in a particular order. A function that rejects it's input returns nothing, and must either be handled, or result in the full program being rejected.

The Vinegar language imagines functions of stacks a lot like parser combinations, where they take the form (in Haskell notation) of Stack -> Maybe Stack. A successful program returns a stack, and one that isn't returns nothing. However, in Prowl, functions look more like Stack -> List Stack, where List is actually lazy. The reason for this is that functions can produce many possible future options for subsequent programs, which the subsequent programs can prune to their likings until they find a particular stack that they accept. This allows a form of search in our control flow - Prowl is powerful, and enables this structured and efficient form of search.

Program Combinators

Let's start off with something familiar:

Concatenation

Concatenation (cat for short) is the simplest form of control flow, representing Kleisli composition over the list monad. Those details aren't important if you are not familiar with them - all that you need to know is that concatenation tries to run a subsequent program after a previous one.

The symbol for concatenation is &, e.g. f & g. You might also recall juxtaposition, f g, being referred to as concatenation. It is that, too. However, f g (space) has a very fast precedence level, faster than all infix, whereas & is the slowest infix operator. This allows & to flatten out, linearize, and deparenthesize code that is composed with the infix operators.

Alternation

Alternation, or alt for short, is represented with |, the second slowest infix, only faster than &. Alternation appends the lists produced by our two functions so that the left one is in front of the right one, and is the alternative monoid over the list functor. More intuitively, f | g tries f, and if f is rejected, tries g, backing up to exactly the same stack f had. This finally provides us a mean of error handling, and of managing the rejections we recieve from programs. The manipulation of rejections is how we achieve control flow in Prowl.

A good place to start with alternation is to emulate the FP feature of pattern matching. We continue to try successive patterns until one fails.

(;5) (
  (as (x;) -> x + 1))
  | (as (;x) -> x - 1)
)

==> 4

The above program attempts to match 5-right against x-left. The as-expression rejects the input, and the alternation moves on to the following case. The second as-expression accepts the input, destructures the right to reveal the 5, then binds to x and substitutes.

You may notice this syntax to be a little awkward - and it is! The | infix does not work so great across lexical scoping, and so we introduce the [ ... ; ...] syntax as sugar. This is regex inspired, but there's no limitations on what may be inside.

(;5) [
  as (x;) -> x + 1;
  as (;x) -> x - 1
]

==> 4

Comparison

Just as patterns in as-expressions emulate pattern matching, comparison operators emulate guards. Comparison operators consume two items and emit nothing; they return the reduced stack when their condition is true, and reject on false. As a result, they can be mixed with patterned as-expressions or any other programs that fail in alt-chains.

let abs n = [
  n < 0 & n neg;  /* `neg` negates a number */
  n
] ->

Intersection

Intersection is && as in regex, except it can appear anywhere. The interesction of two arguments only accepts a stack if both of it's arguments accept the stack. However, only the result from the second argument is kept, the first has its output disposed of. This is useful to assert some quality of the stack without messing with it, as the second argument does not see the effects of the first. We can rewrite the previous example a little more concisely with it.

let abs = [
  (< 0) && neg;
  ()  /* identity */
] ->

The && operator has the 3rd slowest precedence, ahead of |. It represents *> over the list functor, in Haskell.

Quantifiers

Quantifiers are program combinators that create loops - they are useful in all the same places loops are.

N-Times Quantifier

The n-times quantifier repeats a program the specified number of times, analogous to a for loop in imperative programming. It is semantically equivalent to concatenating the program with itself the given number of times, though the quantity can be runtime-determined.

All quantifiers are space-sensitive, and must trail the previous program, touching it. program{n} will repeat program exactly n times, stopping and rejecting if any subprogram does. On n=0, the program becomes identity (), pushing and popping nothing and accepting all stacks. On n<0, the quantifier rejects the program.

let s = (+ 1) -> 
5 s{2}
5 (s{4} s{2}){3}

==>

7
23

As a note, in order for a program to be well-typed, the input program to all quantifiers must always be from a stack to a stack containing data of the same type - all data in the input and output stacks must have the same types in the same arrangement. ( -- ), ( int -- int), and (str int -- str int) are acceptable effects, ( int -- str ) is not.

Optional Quantifier

The "0 or 1 times" optional quantifier ? alternates the argument with identity (). If it fails, it does nothing. We can rewrite our abs function even terser now.

let abs = ((< 0) && neg)? ->

Kleene Star

The star quantifier repeatedly composes a program with itself until the program fails, then returning the last accepted run before failure. It is analogous to the while loop of imperative programming, or tail recursion in functional programming. The Kleene star itself cannot fail, as it eventually reduces itself to identity. It is very easy to write infinite loops using star: ()* is a short one.

Let us use star and some of what we have learned so far to write a simple factorial program.

let fac = 1 (as n a -> n > 0 & n - 1 & a * n)* (as _ a -> a) ->
5 fac

==> 120

Kleene Plus

The plus quantifier is like the star quantifier, except it asserts that the program must succeed at least once. It corresponds to do-while in imperative programming.

Backtracking & Greediness

All of the operators we have seen so far are called greedy operators in regex. They all have a property that allows them to backtrack, that is important to understand as they could hide bugs.

If the program following an alternation, e.g. h in (f | g) h fails, the program will back up to the alternation and try successive cases until the entire subsequent program succeeds. Take the following example:

3 [
  (- 5); 
  (- 1)
] as n -> 0 (+ 1){n}

==> 2

The program puts 3 on the stack. Initially, -2 is chosen as n for the n-times quntifier. However, the quantifier rejects the stack as its argument is negative. The program then backtracks and binds n to 2. 2 is positive, so the quantifier accepts the input, and 0 is succeeded twice to 2.

Alt, star, and plus are all greedy quantifiers by default. Star starts with its longest concatenation chain and works backwards with rejections until identity is reach; plus does the same but stops at 1 composition. If all alternations are exausted, then the entire program encapulated by all those alternations fail, though they can still be handled by alternations farther out. If all alternations in a program fail, the program is rejected -- after all, a full program is simply a function Stack -> List Stack like any subprogram.

However, while the greedy behavior is interesting and powerful for constraint problems, it can hide errors and make programs unnecessary difficult to reason about when those capabilities are not needed. Therefore, we introduce possessive quantifiers which don't backtrack when subsequent programs fail.

Possessive Quantifiers

Adding the posssessive quality is the same as the cut-rule in logic programming, so we use the -cut suffix as a short way of referring to them.

• |+ alt-cut
  • ;+ inside []
• ++ plus-cut
• *+ star-cut

3 [
  (- 5);+ 
  (- 1)
] as n -> 0 (+ 1){n}

==> rejected

Reluctant Quantifiers

Reluctant modifiers start with their most reduced form and then backtrack to attempt their more processed forms, E.g. star *? tries identity, and if a subsequent program fails, tries concatenating its supplied program on each rejection until the supplied program fails.

Combinators

Concatenative Combinators

Concatenative combinators provide an alternate means of stack manipulation from using as, which is analogous to the lambda in FP. Concatenative combinators excel in writing point-free code, and are useful as a terse means for gluing together functions, particularly higher-order ones. All concatenative combinators are RPN, by definition.

While languages like Joy implement and give names to many of these operators (See Theory of concatenative Combinators), we use a streamlined, terse, reduced set for these operations.

There are 4 main categories of concatenative combinators, which form a sufficiently expressive basis:

• ^ (Dup), placing a copy of the top value on top of the stack.
• _ (Zap), destroying the top value of the stack.
• % (Swap), swapping the first and second values on the stack.
• $ (Call), running the top value of the stack, unwrapping quotations { ... }.

In addition to these 4, we have generalized forms for each of them. The numbers that follow the operators must be an actual sequence of digits. The top of the stack is element 1, the second is element 2, and so on.

• ^N Copy the Nth element of the stack, and put it on top.
• _N Delete the Nth element of the stack.
• %3 Rotate, putting the 3rd element on top.
• $N Call the Nth element of the stack.

Recursive Combinators

Prowl imports ideas from Joy, including more complex combinators to express complicated ideas shortly and succintly.

None of these are implemented at this time - this section will be written after they are.

Modules

Modules, inspired from OCaml, provide a way to organize and manage large code bases. They enable the creation of interfaces between separate parts of the code base, and can reduce noise by reconciling different instances of operators with implicits.

Creation

Modules are created with mod .. end. Definitions are like let-expressions, but bind to the module instead of a scope. Modules are expressions, like any other.

mod
  def z = 0
  def s x = x + 1
end

==> (A module)

Let's us a let expression to bind the module to a name.

let m = mod
  def z = 0
  def s x = x + 1
end -> 

Access

Modules can have their fields accessed using . (dot). Dot has faster precedence than concatenation. Let's use the same m from before.

m.z m.s m.s

==> 2

Open

Instead of using access, we can open a module, putting its contents in scope, by matching it against open.

m as open -> 
z s{5}

==> 5

More to come!