Global Utilities

by Manfred von Thun

This short paper contains the design of a Joy interpreter written in Joy itself.

Let L1 and L2 be two languages. An interpreter for language L1 , written in language L2 is a program P which takes as a parameter any program written in L1 and executes it in the same way as a processor for L1 would have. If the two languages are the same language L , such an interpreter is called metacircular. Languages in which program = data make it particularly easy to write an interpreter in its own language. The best known example is the Lisp interpreter eval. A metacircular interpreter for Joy can also be written.

The remainder of this paper assumes some familiarity with Joy.

A Joy interpreter written in Joy

A Joy interpreter in Joy is a program which expects a quoted program on top of the stack and executes it. The following is the design of Joy interpreter joy written in Joy itself. The first version of the interpreter is merely a reminder that Joy already has a combinator, the i combinator, which removes a program from the top of the stack and executes it.

joy  ==  i

The next version makes explicit the fact that Joy programs are sequences which are executed by stepping through the members of the sequence. For each member in the sequence an appropriate action is taken. The step combinator will indiscriminately leave literals, operators and combinators on top of the stack. But any operators and combinators on top of the stack cannot actually be executed. However, their unitlist can be executed by the i combinator. So this is the next version of the interpreter:

joy  ==
        [ unitlist
          i ]
        step

The last interpreter does not actually specify what is to be done what a particular element of the sequence has appeared on top of the stack. A better one should say things like this for the operators:

If the top element is "+"
    then pop off the "+" and add the two numbers below
If the top element is "rest"
    then pop off the "rest" and take the rest of the aggregate below
For the literals it is even simpler:
If the top element is any number
    then leave it there and do not do anything
If the top number is any list
    then leave it there and do not do anything
Essentially we need a way of examining what is on top of the stack and executing the appropriate action. So in the previous version of the interpreter we must replace the unitlist by something more specific. It has to consist of several cases, for the various literals, operators and combinators. The opcase operator is suitable for just that. It expects any kind of item on top of the stack, and above that a list of cases. Each case is a list consisting of a test item and a (possibly) empty rest. The effect of the opcase operator is to remove the top item and the list of cases, and to leave behind the rest of case for which the item matched the test item. The last case in the list is the default, it does not have a test item. The default is returned if there was no match. For the present design step the default does nothing. The following is what has to replace the unitlist in the interpreter:
      [ [ 0 ]                           (* sample number *)
        [ [] ]                          (* sample list *)
        [ + pop + ]                     (* addition operator *)
        [ rest pop rest ]               (* rest operator *)
        [ ] ]                           (* default, do nothing *)
      opcase
It is an easy matter to add the other cases for literals. They have to be treated just like numbers and list:
        [ 'A ]                          (* sample character *)
        [ true ]                        (* sample truth value *)
        [ "" ]                          (* sample string *)
        [ {} ]                          (* sample set *)
Similarly, other operators have to be added such as
        [ swap pop swap ]               (* swap operator *)
        [ cons pop cons ]               (* cons operator *)

For the combinators it is tempting to treat them just like operators:

        [ dip pop dip ]                 (* dip combinator - WRONG *)
        [ map pop map ]                 (* map combinator - WRONG *)
This will work correctly, but it just uses the Joy system inside the quoted program that is being called by i or map. Instead it should use the Joy-in-Joy interpreter that we are writing. To achieve that effect, the program parameter [P] for the combinator has to be replaced by [[P] joy]. For i, dip and map and other unary combinators this is quite easy: after the pop execute [joy] cons. This gives cases like the following:
        [ i    pop [joy] cons  i   ]    (* i combinator *)
        [ dip  pop [joy] cons  dip ]    (* dip combinator *)
        [ map  pop [joy] cons  map ]    (* map combinator *)
The case for the i combinator is unnecessarily inefficient, it could be optimised to
        [ i    pop             joy ]    (* i combinator *)
However, for uniformity this optimisation will not be used here.

So that we do not lose track, here is the interpreter as designed so far:

joy  ==                                 (* literals *)
    [ [ [ 0    ]
        [ []   ]
        [ true ]
        [ 'A   ]
        [ ""   ]
        [ {}   ]
                                        (* operators *)
        [ +             pop     +    ]
        [ rest          pop     rest ]
        [ dup           pop     dup  ]
        [ swap          pop     swap ]
        [ pop           pop     pop  ]
        [ -             pop     -    ]
        [ and           pop     and  ]
        [ cons          pop     cons ]
                                        (* unary combinators *)
        [ i             pop [joy] cons    i      ]
        [ dip           pop [joy] cons    dip    ]
        [ map           pop [joy] cons    map    ]
        [ filter        pop [joy] cons    filter ]
        [ ] ]                           (* provisional default *)
      opcase
      i ]
    step

The interpreter is getting close to its final shape now, but several things need to be fixed. Obviously the binary combinators have to be treated in a way that is similar to the unary ones: The two program parameters [P] and [Q] have to be replaced by [[P] joy] and [[Q] joy]. This is best done by using the app2 combinator as follows:

        [[joy] cons]  app2
So for the binary combinators the cases look like this:
                                        (* binary combinators *)
        [ branch        pop [[joy] cons] app2   branch ]
        [ cleave        pop [[joy] cons] app2   cleave ]
For the ternary combinators and quaternary combinators the pattern is much the same, there are now three or four program parameters that need to be modified. This is easily done using the app3 and app4 combinators to effect the modification.
                                        (* ternary combinators *)
        [ ifte          pop [[joy] cons] app3   ifte ]
                                        (* quaternary combinators *)
        [ linrec        pop [[joy] cons] app4   linrec ]
        [ binrec        pop [[joy] cons] app4   binrec ]

There are still two major amendments needed for the interpreter. The first concerns user defined symbols as they might occur in the standard library, the personal library or in the preamble to a particular run. All Joy symbols have an internal tag, and the tags differ individually only for the operators and combinators. However, all numbers have the same internal tag, all characters have the same tag, all lists have the same tag and so on. Similarly all defined symbols have the same tag. The opcase operator looks at these tags, so all that is needed is one new case for user defined symbols. Just as any number will do as the prototype for numbers, so any user defined symbol will do as the prototype for defined symbols. We might as well choose "joy". When a defined symbol has been encountered, it is necessary to find its definition, which is the program that constitutes the body of that definition. The body operator will find that, it expects a user defined symbol on top of the stack and returns the defining program in quoted form. The Joy interpreter now has to execute this. But it is essential that the Joy interpreter should execute inside that quotation. So it will not do to use the i combinator, but the joy interpreter itself has to be used. Hence the case for user defined symbols is just

        [ joy           body joy ]
The single most common case will be the call of a defined atom rather than an inbuilt one. To improve efficiency this case (with joy) is placed to the front of the caselist.

It always possible that the interpreter is used for programs which contain operators or combinators that are part of the language (not used defined) but have not been given cases in the interpreter itself, either intentionally or through neglect. The joy interpreter should be able to perform reasonably for those operators and combinators. So this is where the default clause for the opcase operator comes in handy. When none of the listed case apply, treat the symbol as we did in the second version of the interpreter: take the unitlist and use the i combinator to execute that. Instead of using unitlist it is better to use its definition [] cons. So the default clause looks like this:

        [               [] cons i ]     (* default *)

This completes the working design of the interpreter. The following is its structure with the last two additions written out fully:

joy  ==
    [ [ [ joy           body joy ]      (* user defined *)
        ...                             (* literals *)
        ...                             (* operators *)
        ...                             (* unary combinators *)
        ...                             (* binary combinators *)
        ...                             (* ternary combinators *)
        ...                             (* quaternary combinators *)
        [               [] cons i ] ]   (* default *)
      opcase
      i ]
    step

Before we write out a more complete version of the interpreter, it is useful to make a number of changes to the design.

Firstly, the cases for the combinators of various arities contain common code which is repeated again and again. The interpreter becomes more readable if such instances are factored out and defined separately. There are cases for unary, binary, ternary and quaternary combinators, and for each of these the common code will be called cr1, cr2, cr3 and cr4. For uniformity the code for cr1 is assimilated to that of the others, using app1. Since they are not likely to be wanted anywhere else, their definitions are given inside a HIDE declaration.

Secondly, it could be useful if the default case does its job not silently but traces out each symbol that it hands over to the Joy system. Such symbols are duplicated and then written out by put. This now makes the default case

        [               dup put [] cons i ]

The interpreter joy now looks like this:

HIDE
  cr1  ==  pop [[joy] cons] app1;
  cr2  ==  pop [[joy] cons] app2;
  cr3  ==  pop [[joy] cons] app3;
  cr4  ==  pop [[joy] cons] app4
IN
  joy  ==
    [ [ [ joy           body    joy       ]
        [ []                              ]
        [ 0                               ]
        ...
        [ dup           pop     dup       ]
        [ +             pop     +         ]
        [ cons          pop     cons      ]
        [ put           pop     put       ]
        ...
        [ i             cr1     i         ]
        [ dip           cr1     dip       ]
        [ map           cr1     map       ]
        [ filter        cr1     filter    ]
        [ app1          cr1     app1      ]
        [ app2          cr1     app2      ]
        ...
        [ ifte          cr3     ifte      ]
        [ linrec        cr4     linrec    ]
        [ binrec        cr4     binrec    ]
        ...
        [               dup put [] cons i ] ]
      opcase
      i ]
    step
END

The interpreter has appropriate cases for all literals and for quite a few operators and combinators. Most operators and combinators are still missing and will therefore be handled by the default clause. However, it is straightforward to make the interpreter more comprehensive and even complete.

It is of some interest to write an interpreter that is just adequate to interpret itself and leaves everything else to the default clause. The following is the minimal Joy interpreter joy0; for variety it uses the optimisation for the i combinator mentioned earlier.

joy0  ==
    [ [ [ joy0          body            joy0     ]
        [ []                                     ]
        [ pop           pop             pop      ]
        [ cons          pop             cons     ]
        [ opcase        pop             opcase   ]
        [ body          pop             body     ]
        [ i             pop             joy0     ]
        [ step          pop [joy0] cons step     ]
        [               [] cons         i        ] ]
      opcase
      i ]
    step

The two versions joy and joy0 are in the file Joy in Joy .

Back to Synopsis of the programming language Joy