Reversing a List in 3 Instructions
Cat is my functional stack-based language based on Joy. One of the interesting characteristics Cat shares with Joy is an incredible succinctness, which rivals that of array-oriented languages such as K or Q. A demonstration of this is how list reversal can be achieved with just three instructions:
nil [cons]Â foldÂ
You would use it like this:
>>Â [1 2 3 4] list nil [cons] foldÂ
stack: (4Â 3 2 1)
One of the advantages of stack-based languages is that they are executed left to right. This means we can enter each instruction on separate lines which is useful for pedgogical purposes because we can see the stack after each instruction.
The first thing that happens is that we push a function literal (called a quotation) on to the stack:
>> [1 2 3 4]
stack: [1 2 3 4]
This pushes a function on the stack that if executed would push the values 1,2,3 and 4. Next we call the “list” instruction
>> list
stack: (1 2 3 4)
This converts a quotation into a list. We can convert any function into a list as long as it doesn’t pop any values off of the stack. The resulting list contains the values that would be generated if we executed the function on any empty stack.
The next thing we do is push an empty list on the stack using the “nil” instruction.
>>Â nil
stack: (1 2 3 4) ()
Now we push another quotation containing the “cons” instruction on the stack.
>> [cons]
stack: (1 2 3 4) () [cons]
The “cons” instruction is similar to the Lisp/Scheme instruction that appends a value to a list. For example “[1 2 3] list 4 cons” is the same as “[1 2 3 4] list”. You may notice then that the front of a list is the rightmost value. This is in keeping with the postfix notation of Cat.
The final instruction is the “fold” instruction.
>> fold
stack: (4 3 2 1)
The Cat “fold” instruction, which is similar to the “foldl” function in Haskell, takes a binary function off of the stack, an initial accumulator value, and a list. The binary function is applied successively to each element in the list and the accumulated value. On each iteration the accumulated value is updated with the result of applying the function. Another example of using the fold function is when summing the values in a list (e.g. “[1 2 3 4] list 0 [+] fold”).
In future posts I will go into more detail about the Cat “fold” function, how it is constructed, and how it differs from the Haskell “foldl” function. For now I hope you will download the interpreter.