Todays tasty treat: a variable-free nearly-pure functional programming language: Unlambda.
\nUnlambda 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:
\n1. S = λ x y z . x z (y z)
\n2. K = λ x y . x
\n3. I = λ x . x
\nGiven 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”.
\nYou can do recursion in SKI; the Y combinator of lambda calculus is:
\nY = S S K (S (K (S S (S (S S K)))) K)
\nUnlambda 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.
\n(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)”.)
\nThere are eight basic instructions in Unlambda:
\n1. ““”` : 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!
\n2. “`k`” : the K combinator.
\n3. “`s`” : the S combinator.
\n4. “`i`” : the I combinator.
\n5. “`v`” : a “drop” combinator: takes a parameter, discards it, and returns “`v`”
\n6. “`d`” : the “delay” operator; a way of doing *lazy evaluation* in Unlambda. Unlambda normally evaluates the argument before it
\napplies a function. `’dA` is the same thing as `A`, except that `A` isn’t evaluated until “`’dA`” is applied to something else.
\n7. “`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.
\n8. “`.`” : The “.” operator is actually a meta-operator. “`.x`” is a function which returns its parameter, *and* prints the character “x”.
\n9. “`r`” is a shorthand for “`.CR`”, where CR is the carriage return character.
\nAnd that is it. The entire language.
\nNote that there are no numbers! We need to build numbers using church numerals.
\n* The church numeral “0” is “λ f. (λ x . x)”. In Unlambda, that’s “`’ki`”.
\n* The church numeral “1” is “λ f . (λ x . f x)”; in unlambda, that’s “`i`”.
\n* The church numeral “2” is “λ f . (λ x. f f x)”; or “`”s”s’kski`”.
\n* The church numeral “3” is “λ f . (λ x . f f f x)”; or “`”s”s’ksk”s”s’kski`”.
\n* And so on.. Just keep appending “`”s”skski`” for each successive number.
\nSo… On to a couple of programs!
\nHello world in Unlambda is:
\n`r“““““`.H.e.l.l.o. .w.o.r.l.di
\nIt’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.
\nNext, a counter: starts with “N=1”; print “N” asterisks, add one, and then repeat.
\n“r`ci“s`k`c“s“s`ksk`kr.*
\nIf 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”.
\nOne 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”:
\n“`s“s“sii`ki
\n`k.*“s“s`ks
\n“s`k`s`ks“s“s`ks“s`k`s`kr“s`k`sikk
\n`k“s`ksk
\nI’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]).
\n[callcc]: http:\/\/community.schemewiki.org\/?call-with-current-continuation
\n[ski]: http:\/\/goodmath.blogspot.com\/2006\/05\/from-lambda-calculus-to-combinator.html
\n[curry]: http:\/\/goodmath.blogspot.com\/2006\/05\/my-favorite-calculus-lambda-part-1.html
\n[iota]: http:\/\/ling.ucsd.edu\/~barker\/Iota\/
\n[lazyk]: http:\/\/homepages.cwi.nl\/~tromp\/cl\/lazy-k.html
\n[jot]: http:\/\/ling.ucsd.edu\/~barker\/Iota\/#Goedel<\/p>\n","protected":false},"excerpt":{"rendered":"
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. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[92],"tags":[],"class_list":["post-111","post","type-post","status-publish","format-standard","hentry","category-pathological-programming"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-1N","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/111","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=111"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/111\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=111"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=111"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=111"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}