Embedding Higher-order Stack Languages in Racket

It is well-known that stack-based languages can be embedded into functional languages. This has even been done in the typed setting by Chris Okasaki in his article Techniques for Embedding Postfix Languages in Haskell. Though Okasaki’s paper does not mention row-polymorphism, his typed embedding is essentially a way to sneak row-polymorphism into Haskell using nested tuples. We even get a taste of how existing type systems can handle higher-order functions over a stack in Sami Hangaslammi’s article Concatenative, Row-polymorphic Programming in Haskell.

One of the key insights in the beginning of Okasaki’s paper is that the functions used to model stack operations end up being partial continuations. Since I was tasked with trying to embed some basic higher-order stack combinators in Racket, one of my first thoughts was ‘How else might stack languages be embedded into a functional language?’ Okasaki’s embedding has the advantage of clarity and typability, but I’ll present another embedding that is made possible by Racket’s multiple-return values feature.

The multiple-values feature of Racket is only briefly discussed in the documentation, but it should be clear enough to get a good intuition of how it can be used. We will also need Racket’s support for variadic functions. The end result will be an encoding of a subset of Brent Kerby’s calculus from the Theory of Concatenative Combinators, extended with some basic integer arithmetic. I’ve also built another version which isolates the semantics in one place, but the resulting embedded language is not as pretty to read.

To make things easy, we first encode the simple arithmetic language. We’ll only handle addition and subtraction, but adding other operations follows a similar template. We don’t want to make a separate combinator for each distinct constant, so we’ll make a generic push function as well.

(define (push c f)
  (lambda xs (call-with-values (lambda () (apply values c xs)) f)))
(define (add f)
  (lambda (a b . xs)
    (call-with-values (lambda () (apply values (+ a b) xs)) f)))

We can’t test it just yet, because each of these combinators takes an argument which represents the rest of the computation. So we need a special word to mark the end of an expression, which just returns the values it receives as its input:

(define end (lambda xs (apply values xs)))

With this we can program in a very basic RPN-like notation that just has a few more parentheses:

(require rackunit)
;; equivalent to
;; 4 1 2 3 add add == 4 6
(check-equal?
 (call-with-values (push 4 (push 1 (push 2 (push 3 (add (add end)))))) list)
 (list 6 4))

Note that we must specify the result stack in reverse order, since Racket lists are generated from left to right, and the left-most element of a list corresponds to our ‘top of the stack’. This is all well and good, but its very simplistic and using continuations for this purpose is completely overkill. Let’s add a few generic stack manipulation combinators:

(define (dup f)
  (lambda (a . xs)
    (call-with-values (lambda () (apply values a a xs)) f)))
(define (zap f)
  (lambda (a . xs)
    (call-with-values (lambda () (apply values xs)) f)))
(define (swap f)
  (lambda (a b . xs)
    (call-with-values (lambda () (apply values b a xs)) f)))

The names for each of these are fairly intuitive: dup duplicates the element on top of the stack, zap is a synonym for ‘pop’ which deletes the top element of the stack, and swap pulls the second element over the top element.

By themselves, these combinators don’t really add much power to the language. We could probably move numbers and math operators around to the point where we could transform any expression containing the above three into an equivalent expression without them. They will be necessary for a complete system by the time we are done, however. Next up, let’s increase the power of our language by adding anonymous functions:

(define (quot f n)
  (lambda xs
    (call-with-values (lambda ()
      (apply values
             (lambda ys (apply f ys))
             xs)) n)))

The quot function takes two parameters: the first is the expression that represents the body of the function, and the second is the expression rest of the program. The name quot is short for quotation, which is what anonymous functions are often called in the concatenative language community. A quotation wraps a list of combinators up in a box and puts that box on the stack, to be duplicated, zapped, or executed at a later time. But this means that we have a function on top of the stack with no way to call it! In applicative languages, a function knows that it is supposed to execute based on its position in the expression. In the lambda calculus and functional languages based on it, this is the left-most part of the expression. In concatenative systems, we need to be more explicit, so we include a way to call a function that is on top of the stack:

(define (call n)
  (lambda (f . xs)
    (call-with-values (lambda () (apply f xs)) n)))

The call combinator is just a slightly clearer name for Kerby’s i combinator. It unwraps the quotation currently on top of the stack and executes the expression inside it. We can also add another combinator, dip, which call the quotation on top of the stack so that it ignores the stack item just below it. It may not seem like a useful idea at first glance, but dip, or a way to construct it, is actually a key part of what separates a complete concatenative system from an applicative one.

(define (dip n)
  (lambda (f x . xs)
    (call-with-values
     (lambda ()
       (apply values x
              (list (call-with-values (lambda () (apply values xs)) f))))
     n)))

We can make, store, and call functions now, but we’re not done quite yet. Two more combinators will give us enough of a basic system to construct all other possible combinators. The first, unit, wraps the item on top of the stack in a quotation (it takes the top element and creates a constant function that pushes that element onto the stack when called). The second, cons, can be thought of as a partial application combinator, sort of like currying.

(define (unit n)
  (lambda (f . xs)
    (call-with-values
     (lambda ()
       (apply values (lambda ys (apply values f ys)) xs)) n)))
(define (cons n)
  (lambda (f b . xs)
    (call-with-values
      (lambda ()
        (apply values
          (lambda ys (call-with-values (lambda () (apply values b ys)) f))
          xs))
      n)))

Factoid: only four of the combinators discussed, plus quot, are necessary to have a complete system! It’s a fun exercise to try and determine what they are. Hint: try to construct the remaining three from an arbitrary set of four.

And with that, we have a tiny but complete higher-order stack language embedded in Racket! Adding other combinators from Brent Kerby’s page should follow a similar pattern. There’s plenty of place to go from here, but whether it is useful or efficient is perhaps the more prescient question. Regardless, happy stacking!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s