I thought I would share some of the reading I am doing lately with regards to intermediate and assembly languages:
I’ve just posted the latest draft of my perpetual paper, Cat: A Typed Functional Stack Based Language.
It is still in a rough draft form, but any comments would be very welcome!
Most of a stack program involves the manipulation of the order of elements on the stack, so it can make programs pretty involved. For example if we were to emulate the effect:
abc -> abac
It would require a sequence of operators such as:
[[dup] dip swap] dip]
Looking at the code snippet, it is not clear what is happening without some kind of comment. This can make stack-based programs exhausting to read.
One solution is to use a set of functions with a particular naming convention that represents what happens. For example the code snippet above would be defined as:
def abac { [[dup] dip swap] dip }
Notice that the name represents what the operation to a stack containing the elements a, b, and c, on top. Interestingly consider:
def aba { [dup] dip swap }
Which would alternatively allow the definition:
def abac { [aba] dip }
That being said, this naming convention is only unambiguous when the operation are assumed to either shuffle and/or duplicate stack items.
Here is a list of operations and their definitions for rearranging two or three stack items (*warning* these haven’t been tested yet)
def aa { dup }
def ab { [id] dip }
def bb { pop dup }
def ba { swap }def aaa { pop dup dup }
def aab { [dup] dip }
def aba { [dup] dip swap }
def baa { swap dup }
def bba { swap [dup] dip }
def bab { dup rot3up }
def abb { ab dup }
def bbb { [pop] dip dup dup }def abc { [[id] dip] dip }
def acb { abc swap }
def bca { rot3down }
def bac { [swap] dip }
def cab { rot3up }
def cba { swap rot3down }def aabc { [aab] dip }
def aacb { acb aabc }
def bbac { bac aabc }
def bbca { bca aabc }
def ccab { cab aabc }
def ccba { cba aabc }def abac { [aba] dip }
def acab { acb abac }
def babc { bac abac }
def bcba { bca abac }
def cacb { cab abac }
def cbca { cba abac }def abcc { abc dup }
def acbb { acb dup}
def bcaa { bca dup }
def bacc { bac dup }
def cabb { cab dup }
def cbaa { cba dup }def abca { [[dup] dip] dip] rot4down }
def cabc { cab abca }
def bacb { bac abca }
def cbac { cba abca }
def bcab { bca abca }
def acba { acb abca}def abbc { [dup] dip }
def bcca { bca abbc }
def cbba { cba abbc }
def caab { cab abbc }
def accb { acb abbc }
def baac { bac abbc }
Of course, many of these have more efficient implementations, but optimizing stack shuffling operations is probably a job best left to a compiler.
Tail recursive functions are recursive functions that perform the recursive call as the last step in the procedure. They are interesting because they can be trivially converted to while loops.
There is a problem though, tail recursive functions tend to be inelegant. This defeats one of the principle advantages of using recursion over iteration. Consider the following excerpt from a post by Frank A Christoph
In functional programs, we need looping behavior, but we don’t want to ntroduce a while loop construct just for this purpose when we have recursive functions instead. Many kinds of looping programs are expressed more clearly and elegantly using recursion than while-, for-… constructs.
Intuitively, a function is iterative if it has no work left over to do after it returns from a recursive call. Consider the following definition.
(define (factorial n)
(if (= n 0)
1
(* n (factorial (- n 1)))))The factorial function is obviously iterative, but that fact is not readily gleaned from the definition above. When factorial returns from its recursive call with a value x, it still has a calculation left to do, namely to compute (* n x) and then return the result of that to the caller.
However, we can rewrite factorial so that it is obviously iterative, by
adding
an argument that functions as an accumulator, and then wrapping the new
function with another that provides an initial value:(define (factorial-helper n m)
(if (= n 0)
m
(factorial-helper (- n 1) (* n m))))(define (factorial n) (factorial-helper n 1))
Of course what Frank has shown us is how to eliminate the elegance of recursive processes! This is a problem with most functional languages. However Cat offers a very elegant solution.
Cat does not currently support recursive definitions but it does support recursive processes through the use of the lin_rec combinator :
def fac1 { [id] [1 ==] [*] [dec] lin_rec }
The lin_rec combinator requires four functions on the top of the stack, from top down they are: the argument relation, the result relation, the termination condition, and the termination function.
This has the same problem identified before for regular linear recursion, but is easily solved by using the tail_rec combinator instead.
def fac2 { 1 [1 ==] [*] [dec] tail_rec }
The only differences between tail_rec is that terminating function is replaced with a value, and that the result relation must be associative.
The subtle difference between fac1 and fac2 is that
5 fac1 == 5 * 4 * 3 * 2 * 1
whereas
5 fac2 == 1 * 5 * 4 * 3 * 2
To be fair though it would be relatively trivial to implement the tail_rec combinator in most functional languages, but being built into the Cat language makes compilation into efficient assembly much easier.
Powered by WordPress