2008-01-07 / 23:57 /

Today an announcement of JoyJ crossed reddit, so I decided to check out the language. Joy is “Forth’s functional cousin”. If you recall, Forth is a low-level stack-based language, almost a stack-based VM assembly language. In contrast Joy is a higher-level language. For example, whereas Forth uses [ and ] to do tricks switching between compiled and immediate mode, Joy uses hard brackets to to delimit lists and code. Note that it’s lists and code. Like Lisp, code is data and can be used as arguments for combinators.

Code & data

I installed the reference interpreter linked to from the homepage: joy.tar.gz. It compiled fine in cygwin. They also provide just the C code if you want to use your own compiler & linker (doesn’t that sound like fun). Once it’s built, you just invoke joy.exe and start playing around. If you want help with any of the functions, check the online manual.

Let’s take a constant (5), square it and add 1 (Italics are input):

5 dup * 1 + .
26

To translate:

  1. put 5 on the stack
  2. duplicate the 5 (now there are two 5’s on the stack)
  3. multiply the two fives and put 25 on the stack
  4. put a 1 on the stack
  5. add 25 and 1
  6. end the program and pop the stack

If we wanted to reuse the “square and add 1” logic, we can make that code by wrapping it in hard brackets. Then we can play around with it like any other list (dup duplicates the top of the stack, I use it to so we can play with a copy of the [dup * 1 +] list while leaving the original intact):

[dup * 1 +]
dup size .
4
dup first .
dup
dup rest .
[* 1 +]

Or we can use the i combinator to apply it:

dup 5 swap i .
26

This code duplicates our [dup * 1 +] list, adds 5 to the stack, swaps them and then uses i to interpret the list [dup * 1 +] as code. And–ta-da!–26.

We can get fancier:

dup [[1 +] [id] ifinteger] map 5 swap i .
27

We duplicate our original [dup * 1 +] code, run it through map and then run it as before. map is a combinator that takes a list, runs a function on each element, and returns the result. In this case the list is [dup * 1 +]. The function is [[1 +] [id] ifinteger] which adds 1 to each integer and returns other values unchanged, i.e. map changes our initial code so instead of adding 1 we add 2.

We can also assign a name to our [dup * 1 +] code (note that the . in the DEFINE statement terminates the definition, it doesn’t pop the stack)

DEFINE sqrplus1 == dup * 1 + .
5 sqrplus1 .
26

Now we can use sqrplus1 like a built-in. Unfortunately I don’t know a way to go backwards: I can’t start from a defined word and get the list. This isn’t to say it’s impossible, just that I don’t know how to do it.

sqrplus1 [[1 +] [id] ifinteger] map .
run time error: one parameter needed for dup
[sqrplus1] [[1 +] [id] ifinteger] map .
[sqrplus1]

Combinators

Combinators, if you didn’t take the time to check the earlier wikipedia link, are just functions that take functions (I think there’s also a fancy combinatorial logic behind them, but I’m ignoring that). We already used three: i, ifinteger and map. Joy’s also got other standards like fold and filter.

ifinteger and it’s branching siblings are interesting. Instead of a standard “if…then…else”, Joy uses combinators that read the boolean to check and the different code branches from the stack. The combinator checks the condition and then executes whichever branch is appropriate. This reminds me of Smalltalk‘s (and I think Ruby’s) “conditionals are messages to booleans”:

result := a > b
    ifTrue:[ 'greater' ]
    ifFalse:[ 'less' ]

Fancy recursion

Although you can do regular recursion with DEFINEd functions, the coolest combinators are for allowing anonymous recursion. From the tutorial:

A high proportion of recursively defined functions exhibit a very simple pattern: There is some test, the if-part, which determines whether the ground case obtains. If it does, then the non-recursive then-part is executed. Otherwise the recursive else-part has to be executed. In the else-part there is only one recursive call, and there can be something before the recursive call and something after the recursive call. It helps to think of the else-part to have two components, the else1-part before the recursive call, and the else2-part after the recursive call. This pattern is called linear recursion, and it occurs very frequently.

Joy has a useful device, the linrec combinator, which allows computation of anonymous functions that might have been defined recursively using a linear recursive pattern. Whereas the ifte combinator requires three quoted parameters, the linrec combinator requires four: an if-part, a then-part, an else1-part and an else2-part. For example, the factorial function could be computed by

        [null]  [succ]  [dup pred]  [*]  linrec

There is no need for a definition, the above program can be used directly.

Very frequently the if-part of a linear recursion tests for a simple base condition which depends on the type of the parameter. For numbers that condition tends to be being zero, for sets, strings and lists that condition tends to be being empty. The else1-part frequently makes the parameter smaller in some way. For numbers it decrements them, for sets, strings and lists it takes the rest.

Joy has another useful combinator which has the appropriate if-part and else1-part built in. This is the primrec combinator, which only has to be supplied with two quotation parameters, the (modified) then-part and the else2-part of linear recursion. For the factorial function the two quotation parameters are very simple:

        [1]  [*]  primrec

computes the factorial function. So, if one wanted to compute the list of factorial of a given list of numbers this can be done by either of the following:

        [ [null]  [succ]  [dup pred]  [*]  linrec ]   map
        [ [1]  [*]  primrec ]   map

The factorial of a number is the product of successive natural numbers up to the actual parameter. The following compute instead their sums and the sum of their squares:

        [0]  [+]  primrec
        [0]  [dup * +]  primrec

There are also combinators for tail recursion, binary recursion (quicksort), tree recursion (tree walking) as well as a few others. I’d love to be able to comment about how this compares with fixed point combinators, but reading that makes my head explode.

For comparison, let’s look at factorial across some languages:

Python:

def fact(n):
    if n <= 1: return 1
    return n * fact(n-1)
>>> fact(5)
120

Haskell:

fact :: Integer -> Integer
fact 0 = 1
fact n | n > 0 = n * fact(n-1)
Main> fac 5
120

Joy:

5 [1] [*] primrec .
120

Interacting with the outside world

Joy’s got get and put for simple IO, though get didn’t work inside my interpreter, but that could be a strange cygwin interaction. It can also open files, read command line args (via argc, argv), check your environmental variables, and call other processes.

I don’t really know when I would use it, but it’s kind of cute to be able to easily do this:

"pwd" system .
/home/dgingrich/src/joy1
"wc -l *.c *.h" system .
  3130 interp.c
   262 main.c
   198 scan.c
   344 utils.c
   185 globals.h
  4119 total

And yeah, that’s all the C code. There’s also Joy code that comes with the installation.

Wrapping up

Joy = Lisp + Forth. Or something like that. I don’t think I’m going to look at it any further, though I’m more inclined to than with Forth. Forth seemed fun but low-level. Joy seems fun and high-level, but with some quriks. In particular:

  • The stack makes parameters implicit. You have to read the code to see how many arguments will be popped (or use comment conventions like in Forth)
  • You spend a lot of time juggling variables on the stack.
  • Everything reads backwards
  • Non-google friendly name (half joking)

Looking back at the ifinteger, Joy and Smalltalk have a similar idea for branching, but the way it reads is much different. The Smalltalk says “here’s a condition, if true, else” vs. Joy’s “if true, else, condition.”

In the recursive examples, the Haskell looks the best to me. Python, while simple, has if plumbing inside. Joy’s claim to fame is that it’s short and can recurse even though anonymous. That’s nice, but the Haskell looks almost identical to the mathematical notation. Pretty handy for readability.

Just for kicks

DEFINE pi == [0] [swap dup 2 pow 1 swap / swap -1 swap 1 - pow * +] primrec 12 * sqrt .
500 pi .
gc - 132 nodes inspected, 122 nodes copied, clock: 1
3.14159
10000 pi .
gc - 5029 nodes inspected, 5020 nodes copied, clock: 1
gc - 8986 nodes inspected, 8977 nodes copied, clock: 1
gc - 10008 nodes inspected, 9999 nodes copied, clock: 1
     32 [main] joy 1568 _cygtls::handle_exceptions: Error while dumping state (probably corrupted stack)
Segmentation fault (core dumped)

On an unrelated note

It looks like Forth is being used in the OLPC XO-1. Neat.