Todays tasty treat: a variable-free nearly-pure functional programming language: Unlambda.
Unlambda is based on the SKI combinator calculus. The [SKI calculus][ski] is a way of writing lambda calculus without variables, and without lambda. It’s based on three combinators: S, K, and I:
1. S = λ x y z . x z (y z)
2. K = λ x y . x
3. I = λ x . x
Given only S and K, you can actually write *any* lambda calculus expression – and therefore, you can write any computable function using nothing but S and K. I is often added for convenience; it’s just a shorthand for “SKK”.
You can do recursion in SKI; the Y combinator of lambda calculus is:
Y = S S K (S (K (S S (S (S S K)))) K)
Unlambda is based on SKI; but it extends it with a few additional kinds of sugar to make things easier to write. (Nothing makes Unlambda easier to *read*!) The basic idea is that *everything* in unlambda is a function; and in particular, everything is a function that takes a *single* variable: you don’t need more than one parameter, because you can always using [currying][curry] to express any multiparameter function as a series of single-parameter functions.
(As a refresher, if you have a two-parameter function in lambda calculus, like “λ x y . x + y”; *currying* is translating it into a one parameter function that returns a one parameter function: “λ x .(λ y. x + y)”.)
There are eight basic instructions in Unlambda:
1. ““”` : the application operator. “`’AB`” applies the function `A` to the parameter `B`. You can think of this as being something like the “(” in Lisp; there is no close paren because since every function takes only one parameter, there is no *need* for a close paren. And hey, adding a syntactically unnecessary close paren would only make the code easier to read, and we can’t have that!
2. “`k`” : the K combinator.
3. “`s`” : the S combinator.
4. “`i`” : the I combinator.
5. “`v`” : a “drop” combinator: takes a parameter, discards it, and returns “`v`”
6. “`d`” : the “delay” operator; a way of doing *lazy evaluation* in Unlambda. Unlambda normally evaluates the argument before it
applies a function. `’dA` is the same thing as `A`, except that `A` isn’t evaluated until “`’dA`” is applied to something else.
7. “`c`” : the “call-with-current-continuation” combinator. This is equivalent to [“call/cc”][callcc] in Scheme. What it does is call some function with the current state of the computation captured as a function as its parameter. What this means is that “`’cAB`” calls “`A`”. “`A`” receives the value “`cAB`” as a parameter; during A, it can return a value, *or* it can call the continuation, which will evaluate “`cAB`” again. So this is the function-based equivalent of a loop. “c” turns the “loop body” into a function; so at the end of the loop, you re-invoke the continuation with a new parameter to run the next iteration.
8. “`.`” : The “.” operator is actually a meta-operator. “`.x`” is a function which returns its parameter, *and* prints the character “x”.
9. “`r`” is a shorthand for “`.CR`”, where CR is the carriage return character.
And that is it. The entire language.
Note that there are no numbers! We need to build numbers using church numerals.
* The church numeral “0” is “λ f. (λ x . x)”. In Unlambda, that’s “`’ki`”.
* The church numeral “1” is “λ f . (λ x . f x)”; in unlambda, that’s “`i`”.
* The church numeral “2” is “λ f . (λ x. f f x)”; or “`”s”s’kski`”.
* The church numeral “3” is “λ f . (λ x . f f f x)”; or “`”s”s’ksk”s”s’kski`”.
* And so on.. Just keep appending “`”s”skski`” for each successive number.
So… On to a couple of programs!
Hello world in Unlambda is:
`r“““““`.H.e.l.l.o. .w.o.r.l.di
It’s pretty straightforward. It’s actually sort of easier to understand if you look from right to left. The “`.H.e.l.l.o…`” is basically a series of “`i`” combinators, which print out the characters of hello world. The trailing “`i`” is there because “`.d`” needs a parameter in order to do anything. And the list of “`’`”s at the beginning are there to make the “.” functions be applied. Finally, apply “`’r`” to the whole thing – which prints a newline at the end.
Next, a counter: starts with “N=1”; print “N” asterisks, add one, and then repeat.
“r`ci“s`k`c“s“s`ksk`kr.*
If you look at it, you can see the number pattern in there; “`”s”s’ksk`”. That fragment is an SKI function to add one. You capture a continuation for the main iteration; run “`i”s’k’cN`”; that’s a fragment that adds “1” to N, and then prints N. Since you’ve captured the continuation, you can re-invoke it on 1+n; the rest captures *another* continuation which is the inner loop for printing “*”s; it does that, and then it invokes the out continuation to go back and do it for “N+1”.
One last, which I’ll leave for you to trace through yourself: this one generates the fibonacci sequence; and for each element of it, it prints out the numbers using a line of asterisks containing “N” asterisks for the number “N”:
“`s“s“sii`ki
`k.*“s“s`ks
“s`k`s`ks“s“s`ks“s`k`s`kr“s`k`sikk
`k“s`ksk
I’ll also point out that there are a ton of variants on Unlambda, ranging from the really interesting ([LazyK][lazyk]) to the bizzarely minimal ([Iota][iota]) to the downright goofy ([Jot][jot]).
[callcc]: http://community.schemewiki.org/?call-with-current-continuation
[ski]: http://goodmath.blogspot.com/2006/05/from-lambda-calculus-to-combinator.html
[curry]: http://goodmath.blogspot.com/2006/05/my-favorite-calculus-lambda-part-1.html
[iota]: http://ling.ucsd.edu/~barker/Iota/
[lazyk]: http://homepages.cwi.nl/~tromp/cl/lazy-k.html
[jot]: http://ling.ucsd.edu/~barker/Iota/#Goedel
Good Math/Bad Math
The beauty of math; the humor of stupidity.
Is Unlambda as good as a Turing machine (i.e. it can compute anything computable)?
If so, would it be correct to say that Turning’s long roll of toilet paper is represented by the Unlambda evaluation stack?
Also, for the regular lambda calculus this would be its infinite variables?
Is the impurity due to the “.” output operator side effect?
Can you provide an example where one would need (or want) to use “v” (the drop combinator)?
601:
Unlambda *is* lambda calculus. SKI is just an alternate form of the lambda calculus; every SKI expression is exactly equivalent to a lambda calculus expression (just expand each of the references to SKI to the lambda forms that I showed when I defined them), and every lambda term can be translated into a beta-eta equivalent SKI form.
One tricky thing about lambda calculus in general, and things like unlambda in particular: there is no evaluation stack. A lambda calculus or SKI expression can be evaluated completely by string rewrites using beta reductions and alpha-renamings. Both the program and data are represented by lambda expressions. The infinite state comes from the fact that the lambda/SKI expression for the program+data can grow arbitrarily during evaluation.
Yes, the impurity comes from the output operator.
The “v” operator necessary for things like building data structures. If you’ve got a “pair” data structure, you have a function to compose two values into a pair; and a function to decompose a pair into two values. If you decompose a pair into two values, and you only want to second one, you dump the first one using “v”.
It’s easiest to demonstrate using a *rational* lambda-calc based language. Haskell is a very nice lambda-based language that uses an SKI base evaluation strategy. Here’s haskell code for a pair:
data Pair a = Cons a a
first :: Pair a -> a
first Cons frst _ = frst
second :: Pair a -> a
second Cons _ sec = sec
When I’m getting the first or second value from the pair, I don’t care about the other one; so I drop it. The “_” pattern in haskell says to drop that value; it’s basically the equivalent of “v”.
Wow, this is really trippy! I’ve been reading the Yet Another Haskell Tutorial to learn about functional programming, but I’ve not been very successful (focusing more on mastering Ruby, hehe). Functional programming really is beautiful, though, especially things like currying and continutatioins, etc, etc, etc. Also, I’ve not been through a Calculus course, so I’ve been reading up on my Calculus, with particular interest to Lamda Calculus. Very cool stuff.
Thanks for the interesting post that I more or less could follow!
M.T.
You realize that what is commonly taught as “Calculus” is related to “Lambda Calculus” only in the most distant manner, right?
If you really want to learn more about the Lambda Calculus, I suggest you try tackling that directly. It’s sufficiently popular now that there are many introductions that don’t assume you first have a grounding in mathematical logic, or indeed any math beyond high school algebra. (Though I would strongly encourage you to get enough mathematics under your belt to be thoroughly comfortable with proofs by mathematical induction)
I haven’t read it myself, but I’ve heard wonderful things about “The Little Schemer” – that includes a nice discussion of the Y combinator, and once you grasp that completely, you should be able to understand most lambda calculus material you come across. This book has the advantage of not teaching you lambda calculus in a vacuum, but in front of a machine – working through some of these tough concepts is much, much easier when you have a programming language you can type expressions at and see the results. (And if you’re looking for a scheme implementation, I’d recommend PLT Scheme)
Oh, and I was glad to see this post about UnLambda, and am looking forward to the follow-up post on LazyK.
Except for the continuation support in Unlambda, I’ve always preferred Iota. It consists of a prefix composition operator 1 (like Unlambda’s backtick) and a single universal combinator
0 = λx.x (λxyz.xz(yz)) (λxy.x)
You can use the syntax for any universal combinator, so you could change the definition of 0 to one that includes stuff for monadic I/O or continuations.
D’oh! I missed the last line of your essay where you mention it–sorry. But in an attempt to redeem myself, here’s a universal combinator that includes all the features of Unlambda:
Let P=λxyz.zxy, the pair combinator. For readability, I’ll denote PAB as [A,B]. Then we can define a universal combinator by sticking in `kk, `ki, and s into a tree and using the rest of the room for whatever else we want:
0 = [`kk, [`ki, [s, [[[v, d], [r, c]], .]]]]
where . is really another tree full of .x combinators, presumably Huffman coded for optimality 😉
Now,
10100 = k
1101000 = `ki
and you can use each of those to pull out the left or right branch of the binary tree:
111 0 1101000 1101000 10100 = s
111111 0 1101000 1101000 1101000 10100 10100 10100 = v
111111 0 1101000 1101000 1101000 10100 10100 1101000 = d
111111 0 1101000 1101000 1101000 10100 1101000 1101000 = c
111111 0 1101000 1101000 1101000 10100 1101000 10100 = r
1111 0 1101000 1101000 1101000 1101000 = .
Not exactly the most efficient encoding, but this way it’s easy to construct combinators with all the features you want .
Oops! That should be
[‘kk, [[`ki, [s, [all the other stuff from Unlambda], k]]
and
10100 = k
11 100 10100 10100 = `ki
Or
u = [`k`k`k0, [all the other stuff from Unlambda]]
where 0 is Iota’s unversal combinator.
I have to say, my most vivid memory upon discovering Unlambda many years ago was the annoying clicking noise my brain was generating from all the backticks…