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.