Trace of Joy program evaluation
+-----------------+-------+-------+
| Program | Stack | Value |
+=================+=======+=======+
| `3 sq`{.joy} | {} | |
| `3 dup *`{.joy} | {} | |
| `dup *`{.joy} | {3} | |
| `*`{.joy} | {3 3} | |
| | {3*3} | |
| | {9} | |
| | {} | 9 |
+-----------------+-------+-------+

Now with closures:
[code="Joy"]
Program Stack Value
3 sq {} ()
3 dup * {} ()
dup * {(3)} ()
* {(3) (3)} ()
{((3) * (3))} () -- Done, evaluate the result
{} ((3) * (3))
{} (3 * 3) -- (3) is memoised; both eval at once
{} (9)
{} 9
[/code]
They're both about the same, although the closure-based one goes
through more 'unwrapping' steps.
Now the second example on a value-based stack:
[code="Joy"]
Program Stack Value
5 fermats_last_theorem prove zap {}
fermats_last_theorem prove zap {5}
prove zap {5 fermats_last_theorem}
zap {5 proof_of_flt}
{5}
{} 5
[/code]
Uh oh, we ended up proving Fermat's last theorem. That probably took a
while! How about with closures?
[code="Joy"]
Program Stack Value
5 fermats_last_theorem prove zap {}
fermats_last_theorem prove zap {(5)}
prove zap {(5) (fermats_last_theorem)}
zap {(5) (prove (fermats_last_theorem))}
{(5)}
{} (5)
{} 5
[/code]
Much better, we just throw away the closure without running it!
**Quotation**
The final part of the calculus underlying Joy is that it features
quotation, similar to LISP's. Quotes are written [in square brackets].
We know that symbols like "a", "b" and "c" are functions from stacks
to stacks, and we know that a concatenation of symbols "a b c" is a
function from stacks to stacks (the composition of a, b and c). A
quotation "[a b c]" is a function from stacks to stacks, which pushes
a function on to the stack; in this case the stack would be topped
with the "a b c" function.
With quotation in our arsenal, Brent Kerby has shown that we only need
two other functions in order to be Universal. There are a few
(countably many) combinations to choose from, but a nice pair are what
Kerby calls "k" (since it's similar to Schoenfinkel's applicative K
combinator) and "cake" (pairs elements into a pair of head-recursive
and tail-recursive quotations). Here's what they do:
[code="Joy"]
-- k :: [A b [a]] -> [A a]
-- k pops a quotation and another element, and pushes the contents of
-- the quotation (in other words, unquoting it). For example:
5 7 11 [dup * +] k
-- Let's look at the types, concatenating up to the whole thing:
-- 5 pushes a 5
-- 5 :: [A] -> [A {5}]
-- 7 pushes a 7
-- 7 :: [A] -> [A {7}]
-- 5 7 pushes a 5 then a 7
-- 5 7 :: [A] -> [A {5} {7}]
-- 11 pushes an 11
-- 11 :: [A] -> [A {11}]
-- 5 7 11 pushes a 5 then a 7 then an 11
-- 5 7 11 :: [A] -> [A {5} {7} {11}]
-- dup pushes a copy of whatever's on the top of the stack
-- dup :: [A a] -> [A a a]
-- * pops two Nums and pushes their product
-- * :: [A Num Num] -> [A Num]
-- dup * pops a number and pushes its square (copies then multiply)
-- dup * :: [A Num] -> [A Num]
-- + pops two numbers and pushes their sum
-- + :: [A Num Num] -> [A Num]
-- dup * + pops two numbers and pushes the second plus the square of
-- the first
-- dup * + :: [A Num Num] -> [A Num]
-- [dup * +] pushes the "dup * +" function
-- [dup * +] :: [A] -> [A ([A Num Num] -> [A Num])]
-- 5 7 11 [dup * +] :: [A] -> [A {5} {7} {11} ([A Num Num] -> [A Num])]
-- 5 7 11 [dup * +] pushes those three numbers and that function
-- k :: [A b [a]] -> [A a]
-- k pops a quotation, pops another element, then applies the quoted
-- function to the rest of the stack
5 7 11 [dup * +] k :: [A] -> [A Num]
-- 5 7 11 [dup * +] k pushes some numbers and a function, then pops
-- the function and the number 11, and applies the function to the
-- stack containing 5 and 7. Let's see how it unfolds, showing the
-- temporary values that are used by the functions too:
Program Stack Temporary
5 7 11 [dup * +] k {}
7 11 [dup * +] k {5}
11 [dup * +] k {5 7}
[dup * +] k {5 7 11}
k {5 7 11 [dup * +]}
{5 7 11} [dup * +]
{5 7} [dup * +]
dup * + {5 7}
* + {5 7} 7
* + {5 7 7}
+ {5 7} 7
+ {5} 7 7
+ {5} 49
+ {5 49}
{5} 49
{} 49 5
{} 54
{54}
[/code]
What about cake?
[code="Joy"]
-- cake :: [A b [a]] -> [A [b a] [a b]]
-- cakes pops a quotation and another item and pushes two quotations;
-- both pairings of the second item and the contents of the first.
-- For example:
Program Stack Temporary
5 7 11 [dup * +] cake {}
7 11 [dup * +] cake {5}
11 [dup * +] cake {5 7}
[dup * +] cake {5 7 11}
cake {5 7 11 [dup * +]}
{5 7 11} [dup * +]
{5 7} [dup * +] 11
{5 7} [dup * + 11] [11 dup * +]
{5 7 [11 dup * +] [dup * + 11]}
[/code]
With k, cake and quotation we get a Universal language. Similarly to
Lambda Calculus, we get no datatypes other than functions, but we can
encode data as functions (in a similar way to Church encoding and the
like in Lambda Calculus) to get as much richness as we need.
What's interesting is the way types and stack effects work in
concatenative languages, but I'll leave that for another post.
I've thrown together a quick interpreter for the not-quite-Joy I've
been using in this blog post (Joy features hard-coded datatypes for
numbers, characters, etc. which I don't want to deal with), but due to
gitorious troubles (damn you cookies!) I've not put it online yet.