The Unlambda Programming Languagebody { font-family: Univers, Verdana, Helvetica, Arial, sans-serif; font-size: 1em; background: white; color: black}h1, h2, h3, h4, .subtitle { text-align: center; font-family: Baskerville, "New Century Schoolbook", serif}The Unlambda Programming LanguageUnlambda: Your Functional ProgrammingLanguage Nightmares Come TrueTable of contentsWhat's New in Unlambda World?IntroductionWhat is Unlambda?What does Unlambda look like?What are the principles of Unlambda?Links and meta-links to other obfuscatedprogramming languagesTutorialFunctions and applicationCombinatorsAbstraction eliminationMaking abstraction elimination moreefficientMore Unlambda builtinsv.xdcHOWTO: various programming techniquesHow do I write a loop in Unlambda?How can I represent numbers inUnlambda?How can I represent lists (and related datastructures) in Unlambda?How do I write tests and booleans inUnlambda?A note about the Unlambda Quine ContestImplementing UnlambdaFirst-class functionsFirst-class continuationsGarbage collectionPromisesCan Unlambda be compiled?Unlambda referenceUnlambda distribution (download Unlambdahere)Comprehensive Unlambda Archive NetworkWhat's New in Unlambda World?(If you don't know what Unlambda is, skip this section and movedirectly to the introduction below.)[2001/08] This page is being revised in preparation of theUnlambda 3 distribution.Introduction“It's disgusting — it's revolting — we loveit.”CyberTabloid“Unlambda, the language in which every program is anIOUCC.”Encyclopædia Internetica“The worst thing to befall us since Intercal.”Computer Languages Today“The effect of reading an Unlambda program is like habingyour brains smashed out by a Lisp sexp wrapped around an ENIAC. Youwon't find anything like it west of Alpha Centauri.”The Hitch-Hacker's Guide to ProgrammingWhat is Unlambda?Unlambda is a programming language. Nothing remarkable there. Theoriginality of Unlambda is that it stands as the unexpectedintersection of two marginal families of languages:Obfuscated programming languages, of which the canonicalrepresentative is Intercal. This meansthat the language was deliberately built to make programming painfuland difficult (i.e. fun and challenging).Functional programming languages, of which the canonicalrepresentative is Scheme (a Lispdialect). This means that the basic object manipulated by thelanguage (and indeed the only one as far as Unlambda isconcerned) is the function.Obfuscated programming languages (see below for links) are typically made nasty byeither strongly restricting the set of allowed operations in thelanguage, or making them very different from what programmers are usedto, or both. (Of course, the goal is to do that while still beingTuring-complete.) Unlambda does this (note, however, that theoperations permitted were not chosen at random: they have theirtheoretical importance). But whereas most obfuscated programminglanguages try to somehow model the Turing Machine paradigm, Unlambdadoes not use a tape, array or stack. Nor is it binary-oriented; as amatter of fact, it does not manipulate integers in any way. Otherremarkable (un)features of Unlambda are the fact that it does not haveany variables, data structures or code constructs (such as loops,conditionals and such like).Rather, Unlambda uses a functional approach to programming: theonly form of objects it manipulates are functions. Each functiontakes a function as argument and returns a function. Apart from abinary “apply” operation, Unlambda provides several builtinfunctions (the most important ones being the K and S combinators).User-defined functions can be created, but not saved or named, becauseUnlambda does not have any variables.Despite all these apparently unsurmountable limitations, Unlambdais fully Turing-equivalent.Mathematically, the core of the language can be described as animplementation of the lambda-calculus without the lambda operation,relying entirely on the K and S combinators. Hence the name“Unlambda”. It uses head (“eager”, “byvalue”, “strict”) evaluation. I cannot claimoriginality there. However, as far as I know, I am the first to havetaken this theoretical concept and made it into an actual(deliberately obfuscated) programming language. I added a couple offunctions (chosen for their obscurity) to the language so as to makeoutput (and, in version 2, input) possible, or just to make thingseven more obscure (delay and call/cc are such).A note on terminology: The phrase “purelyfunctional programming language” is usually applied tolanguages, like Haskell orClean, which are lazy anddemand explicit sequencing of side effects. I dislike thisterminology: for one thing, a “functional” programminglanguage is one in which functions have first-class citizenship, so a“purely functional” one should be one where, as inUnlambda, only functions have first-class citizenship. Andwhat are usually called “purely functional programminglanguages” should be called, exactly as I just did, lazilyevaluating programming languages with explicitly sequenced sideeffects. All these points are orthogonal: it is quite possible toconceive a lazy programming language which is not functional, or aneager (i.e. non-lazy) functional programming language which stilldemands explicit sequencing of side effects. In any case, this is tosay that I might, on occasion, speak of Unlambda as a “purelyfunctional” programming language, although, with the usualterminology, it is not.What does Unlambda look like?Well, let's discuss an example: the following Unlambda programcalculates and prints the Fibonacci numbers (as lines ofasterisks)```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(All whitespace is optional and arbitrary. Some former versions ofthis page gave a uselessly complicated and inefficient program.)You're right: it's not very readable. Writing Unlambda programsisn't really as hard as it might seem; however, readingUnlambda programs is practically impossible. We'll be explaining what all this means later on, but let'sjust stick to basic observations for the moment.As you can see, the most common character (essentially, it makes uphalf of any Unlambda program) is the backquote (ASCII number 96=0x60).The backquote represents Unlambda's apply operation. Afterthat come the S and K combinators (and I, but I can be done away withentirely). Some other characters can occur in Unlambda programs butthey are not nearly so common. Besides the backquote and the letterss, k and i, the above programhas r and .* as its only other buildingblocks: these are the Unlambda printing functions (rprints a newline and .* prints an asterisk). The moresophisticated Unlambda functions (v, d,c, e and the input functions) are not usedhere at all.What are the principles of Unlambda?The number one principle of the Unlambda language is thateverything is a function: this is true in the sense thatUnlambda is a profile of the pure untyped lambda calculus. (Well, tobe honest, the d builtin isn't precisely a function, butwe will consider it as such anyway.)Despite Unlambda being a form of the lambda calculus, it does nothave a lambda (abstraction) operation. Rather, this operation must bereplaced by the use of the S, K and I combinators — this can bedone mechanically using abstractionelimination. Because there is no abstraction, functions are notnamed in Unlambda (except the builtin ones): there are no variables orsuch thing. This doesn't mean you can't build up your own functions.Nor does the fact that there are only functions in Unlambda preventyou from coming up with data structures and the like, but you justhave to represent them with ad hoc functions. Infact, you can so well build your own structures and such that Unlambdais (and, to work, must be) garbage-collected like any decenthigh-level language.So, everything is a function. To start with, you have the builtinfunctions (i, k, s and thelike), and you can do one thing: apply a function F to afunction G, the result being denoted`FG. It is from this basic ideathat Unlambda is built.Links and meta-links to other obfuscatedprogramming languagesTheRandom Programming Languages List, by Ben Olmstead(also the inventor of Malbolge,probably the most devilish language in existence), is a quitecomprehensive list of evil programming languages. It mentionsUnlambda.TheTuring Tarpit, by BrianConnors (named after an entryin the Jargon File), isa similar list of Bad Languages and other cyberlinguistic horrors. Italso mentions Unlambda.Ryan Kusnery'slist of WeirdProgramming Languages is also quite good, despite its notmentioning Unlambda.Prfnoff's ObfuscatedLanguages list mentions two languages he wrote (not usuallyincluded in similar lists): Fromage and BAK.Eric S. Raymond's famousRetrocomputing Museumlists a few thinks that cause a feeling “between nostalgia andnausea”.Intercal remainsthe archetype of the Obfuscated Programming Language.Cats-Eye Technologies(used to be http://www.cats-eye.com/ and has moved tohttp://www.catseye.mb.ca/: thanks to Rafael Kaufmann forpointing this out) hosts a lot of items of related interest, includingthe famous BrainF*** language,whose name quite appropriately describes the point of all theselanguages. They also have a page on fortune's lesser-knownprogramming languages.The “Institute of AppliedIconoclasm” maintains an Esoteric LanguagesDatabase, which lists Unlambda.They also seem to have a very high opinion of it, and ofmyself ;-)TheEsoteric Programming Languages Ring of which this site is part:[Previous 5 Sites|Previous|Next|Next 5 Sites|Random Site|List Sites]TutorialAlthough the very idea of a tutorial for such an obfuscatedlanguage as Unlambda is patently absurd, I shall try to give a briefintroduction to the concepts before dwelling in the details of thereference section (which is also very short considering how smallUnlambda is as a whole).Functions and applicationAs has been mentioned in the introduction, theonly objects that the Unlambda programming language manipulates arefunctions. Every function takes exactly one argument (thatis also a function) and returns one value (that is also afunction).The basic building blocks for Unlambda programs are the primitivefunctions and the application operation. There areseven primitive functions in Unlambda version 1: k,s, i, v, d,c and .x (where x isan arbitrary characters — so actually that makes 6+256 primitivefunctions, but we shall consider .x as asingle function; the r function is but a commoditysynonym for .x where x is thenewline character). Unlambda version 2 adds the following newprimitive functions: e, @,?x (where x is a character) and|.Function application is designated with the backquote (ASCII number96=0x60) character. The notation is prefix, in other words,`FG means F applied toG.We'll be explaining in detail what application means exactly, butfor the moment, we'll just say that it means that F will dosomething with the value of G, including applying otherfunctions to it, or applying it to other functions. (That's about theonly thing it can do, as a matter of fact.) Just how Fdoes this will become clear later on (or it should). We have to note,of course, that both F and G may themselves beobtained by applying various functions to each other.The fact that every Unlambda function is unary (takes exactly oneargument) means that the backquote notation is unambiguous, and we donot need parentheses (or, if you prefer, the backquote plays the roleof the open parenthesis of Lisp, but the closed parenthesis isunnecessary). For example,``FGH means(F applied to G) applied to H whereas`F`GH means Fapplied to (G applied to H). To check whetheran expression is a valid Unlambda expression, there is a simplecriterion: start at the left with a counter equal to the number 1, andmove from left to right: for every backquote encountered, incrementthe counter, and for every primitive function encountered, decrementit; the counter must always remain positive except at the very endwhen it must reach zero.Since all Unlambda functions take exactly oneargument, when we wish to handle a function of several arguments, itis necessary to “curry” that function. That is, read thearguments one after another. For example, if F is afunction that should take three variables, it will be applied thus:```FG1G2G3.The idea being that F will do nothing but read the firstargument and return (without side effects) a function that reads thesecond argument and returns a function that reads the third argumentand finally do whatever calculation it is F was supposed toperform. Thus, both``FG1G2and `FG1 are legal, butthey don't do much except wait for more arguments to come.The previous discussion is not so theoretical. Of course, when theuser is defining his own functions, he may use whatever mechanism heseems fit for reading the functions' arguments (but such acurrying is certainly the best because pairs and lists are sohorribly difficult to define in Unlambda). But the builtink and s functions take respectively 2 and 3arguments, and the several arguments are passed in the manner which wehave just described. (As a side note, Iremark that it is, if not impossible, at least inconvenient, toconstruct functions that take zero arguments because preventingevaluation until all arguments have been read is good but when thereare no arguments to be read, the situation is not pleasant; in thepure lambda calculus there is no problem because evaluation order isunspecified and irrelevant, but in Unlambda we have a bigger problem.Here the d function might help.)A note about evaluation order: when Unlambda is evaluating anexpression `FG, it evaluatesF first, and then G (the exception being whenF evaluates to d), and then appliesF to G. Evaluation is idempotent: that is,evaluating an already evaluated expression in Unlambda does not haveany effect (there is no level-of-quotation concept as in m4 or SIMPLE).(Perhaps it would be clearer to describe things by distinguishingexpressions and functions, where the latter areobtained by evaluating the former. This is what the Java version ofthe Unlambda interpreter does, for example (whereas the Scheme versiondoes not). It is merely a matter of choice. True, the distinctionmight help in understanding the d builtin, since it keepsan expression in its unevaluated form.)We now turn to the description of the Unlambda builtins.CombinatorsThe k and s builtins are the core of thelanguage. Just these two suffice to make Unlambda Turing complete(although .x is also necessary if you want toprint anything). The k builtin is easy enough todescribe: it takes two arguments (in curried fashion, as explained above) and returns the first. Thus,``kXY evaluates toX (evaluated). Note that Y isstill evaluated in the process. The s builtin isslightly more delicate. It takes three arguments, X,Y and Z, and evaluates as does``XZ`YZ.So, let's get things straight: k doesn't do much untilit is applied to two arguments, in which case it throws the second oneaway and returns the first. As for s, it doesn't do muchuntil it is applied to three arguments, at which point it applies thefirst to the third, and the second to the third, and the result of theformer application to the result of the latter.To take an example, consider ```skss: here sis applied to three arguments, k, s ands, so it performs the evaluation of ``ks`ss.But here we see that the first k is applied to two arguments(s and `ss), so that it returns the first(namely s), and the final result is s.We also mention immediately the i function: it is simplythe identity function In other words, it takes an argument and returnsit intact. The i function is not strictly necessary butit is practical. It could be replaced by ``skk.(Indeed, ```skkX evaluates as``kX`kX because of thes, which in turn evaluates as Xbecause of the k.)To summarize, the k builtin is a “constantfunction constructor”. That is, for all X,`kX is the constant function with valueX. The s builtin corresponds to“substituted application”: that is,``sXY is a function that, insteadof applying X to Y directly, will apply each ofthem to Z (the argument) first, and then one to the other.Finally, i is the identity function.Abstraction eliminationWe will now try to describe the central process of abstractionelimination. This is not necessary to understand how Unlambda works,but it is necessary to understand how you can do anything with it.The central feature which appears to be missing fromUnlambda is that of variables. This is precisely what abstractionelimination enables us to recover. The problem is, given anexpression F that contains, apart from ordinary Unlambdasymbols, one “variable” symbol which we will write$x, to build a function that, when applied tosome X, will return the value of F withX substituted in place of $x. Inother words, we want to build a function (which we will write^xF) which takes a valueX for $x and does some operation(specified by F) on it. This is the lambda (orabstraction) operation of the lambda calculus (our notation^ is supposed to stand for a lambda). Unfortunately,Unlambda, as its name indicates, does not have this lambda operation,and our problem is to eliminate it, in a systematic way, fromexpressions (hence the name abstraction elimination). Forexample, ^x$x (the function of $x whichsimply returns $x) is supposed to give i (orsomething equivalent) when abstraction elimination is performed.So, we take an expression F involving$x, and we want to eliminate the startinglambda in ^xF. We do this byinduction on the complexity of F; there are three caseswhich must be taken into account: either F is builtin (orsome variable other than $x, if we permitthis), or F is $x, or Fis an application, say, `GH, withG and H simpler expressions (which, byinduction, we know how to reduce). So we consider these three casesseparately:In the first case, we want to eliminatethe lambda from ^xF, whereF does not depend on $x. So it isthe constant function with value F. But, as we know, thisis `kF. So we know how to eliminateabstraction in this case.In the second case, we want to eliminate the lambda from^x$x. But this is precisely theidentity function, so it reduces as i.In the third case, we want to eliminate the lambda from^x`GH, assuming we knowhow to eliminate the lambda from^xG and from^xH. But the function we areconsidering takes an X and applies it to^xG, then to^xH, and finally applies the resultof one to the result of the other. This is precisely the role of thes builtin. So^x`GH is no other than``s^xG^xH(and by eliminating the lambda from the inner expressions we get whatwe wanted).Finally, abstraction elimination is described mechanically asfollows: consider the expression F and we want to eliminatethe lambda from ^xF. Scan theF expression from left to right: for every `(backquote) encountered, write ``s (by virtue of thethird case above); for every $x encountered,write i (by virtue of the second case); and for anybuiltin or any variable other than $x, write`k followed by the thing in question.As an example, the function ^x`$xk, which takes afunction and applies that function to the function k,transforms as ``si`kk.If several lambdas need to be eliminated from one expression, thetrick is to start with the innermost ones, and to eliminate theoutermost lambdas last. As an example, ^x^y`$y$x becomesfirst ^x``si`k$x (upon eliminating the innermorst lambda)and then ``s``s`ks`ki``s`kki (upon eliminating theoutermost).If several lambdas are present, i.e. if several abstractioneliminations are performed as explained in the previous paragraph, thelength of the resulting expression grows exponentially (with factor 3for each lambda). A single ` becomes ``safter one abstraction elimination, then ``s``s`ks after asecond, ``s``s`ks``s``s`ks``s`kk`ks after a third,``s``s`ks``s``s`ks``s`kk`ks``s``s`ks``s``s`ks``s`kk`ks``s``s`ks``s`kk`kk``s`kk`ksafter a fourth. Similar giveaway sequences appear before anybuiltin.Making abstraction elimination moreefficientIt is sometimes desirable to obtain a shorter result whenperforming lambda elimination. Shortcuts can be used, but they demandsome care.Consider the first case we described above.We explained that when F is a builtin or a variable otherthan $x then we can eliminate the lambda from^xF by simply rewriting it as`kF. This is quite correct. However, thisrule applies a bit more widely than we have suggested: this is true aslong as F does not involve x, because it isthen a constant, and creating constants is precisely what the Kbuiltin is good at. So if F is a lengthy expression notinvolving $x, instead of going through thetedious process of eliminating in F, we can shortcut thewhole thing and rewrite it as `kF.There is a danger, however, in so doing. While all this workswithout glitch in the blessed realm of the pure untyped lambdacalculus, i.e. in the absence of side effects (the functions wehave seen so far do not create any side effects) and as long as wedon't express excessive worries about nontermination, there is aslight difficulty involved when evaluating F causes a sideeffect or might not terminate. Indeed, when we write^xF, we probably expect the sideeffect (or nontermination) in question to be delayed until thefunction is applied (i.e. until $xreceives a value, even if that value is ignored); this is indeed thecase if we perform abstraction elimination through the canonical(long) way. If, however, we short-cut and rewrite this as`kF, then F is evaluatedas soon as this expression is encountered, even if the function is notapplied to anything. This might not be what you wanted.So the shortcut is really this: you can rewrite^xF as `kFprovided (a) F does not involve$x. amd (b) you can prove that evaluatingF terminates and performs no side effect. One easy way ofmaking sure of (b) is to check that the only applications found inF are of the form: the K builtin applied to oneargument, or the S builtin applied to one or twoarguments, or the D builtin applied to any expression whatsoever (seebelow about this).If F does not involve x but doesinvolve evaluations which might (or do) cause side effects ornontermination, there is still a way to perform abstractionelimination from `kF without peering in theentrails of F. Namely, to use the D builtin described below, and write `d`kF. Atrue purist, however, does not rely on the D to make his programwork.Another shortcut in abstraction elimination is to spot expressionssuch as ^x`F$x and torewrite them as simply F — provided ofcourse the variable $x does not appear inF. This is pretty benign if F is just a builtinother than D, or a variable other than$x. But if F can produce sideeffects, this presents the same risks as the other shortcut we justdescribed (and you can also get around them by writing`dF).Note also that the V builtin can always beabstracted to itself. (That is, `kv is functionallyidentical to v.)More Unlambda builtinsvThe v function is a kind of “black hole”.It takes an argument, ignores it and returns v. It canbe used to swallow any number of arguments.The v function can be implemented using s,k and i (and hence, using s andk only). Indeed, it can be written using the lambdaexpression `^h^x`$h$h^h^x`$h$h (which evaluates to^x of the same thing), and abstraction elimination shows that this is` ``s``s`kskk ``s``s`kskk (here is an example when someincorrect shortcuts in an abstractionelimination can be disastrous, for example if ` ``s`kk``sii``s`kk``sii were used instead, as obtained by attempting toreduce ^h^x`$h$h as^h`k`$h$h)..xThe .x function is the only way to performoutput in Unlambda (note that in Unlambda version 1 there is no way toperform input). This function takes an argument and, like theidentity function, returns it unchanged. Only contrary to theidentity function it has a side effect, namely to print the characterx on the standard output (this writing takes place when.x is applied). Note that while this functionis written with two characters, it is still one function; onno account should .x be thought of assomething applied to x (and, just to insist, there isno such function as . (dot), only.x (dot x)). The rfunction is just one instance of the .xfunction, namely when x is the newline character. Thus,the `ri program has the effect of printing a newline (sowould `rv or `rr or`r(anything), but r alone doesn'tdo it, because here the r function isn't applied: here mynote about the impossibility of currying functions of zero arguments should becomeclearer).dThe d function is an exception to the normal rules ofevaluation (hence it should be called a special form ratherthan a function). When Unlambda is evaluating`FG and F evaluates tod (for example when F isd) then G is not evaluated. The result`dG is a promise to evaluateG: that is, G is kept unevaluated until thepromise is itself applied to an expression H. When thathappens, G is finally evaluated (afterH is), and it is applied to H. This is calledforcing the promise.For example, `d`ri does nothing (and remainsunevaluated), and ``d`rii prints a blank line (because weare forcing the promise). Another point to note is that``dd`ri prints a blank line: indeed, `dd isfirst evaluated, and since it is not the d function(instead, it is a promise to evaluate d), it does notprevent the `ri expression from being evaluated (toi, with the side effect of printing a newline), so thatwhen finally d is applied, it is already too late toprevent the newline from being printed; to summarize, thed function can delay the d function itself.On the other hand, ``id`ri does not print a blank line(because `id does evaluate to d).Similarly, ```s`kdri is first transformed to```kdi`ri, in which ``kdi is evaluated tod, which then prevents `ri from beingevaluated so no newline gets printed.Writing `d`kF is another form of promise(perhaps more customary but at the same time less transparent): whenit is applied to an arbitrary argument Y, then Yis ignored and F is evaluated and returned. Thispossibility has already been mentioned in the discussion on shortcuts during abstraction elimination.cThe c (“call with current continuation”)function is probably the most difficult to explain (if you arefamiliar with the corresponding function in Scheme, it will help alot). I suggest you try reading the call/ccpage at this point. c called with an argumentF will apply F to the currentcontinuation. The current continuation is a special functionwhich, when it is applied to X, has the effect of makingc return immediately the value X. In otherwords, c can return in two ways: if F appliedto the continuation evaluates normally, then its return value is thatof c; but if F calls the continuation at somepoint, c will immediately return the value passed to thecontinuation.Note that the continuation can even escape from the ccall, in which case calling it will have the effect of going “back intime” to that c call and making it return whatever valuewas passed to the continuation. For a more detailed discussion, seeany book on Scheme or the call/ccpage mentioned.Examples of c include ``cir: here,`ci evaluates to the continuation of the cwhich we shall write <cont>, and we have`<cont>r: here, the continuation is applied, so itmakes the c call return r, and we are leftwith `rr which prints a newline. Another interestingexample is `c``s`kr``si`ki: in this expression, theargument ``s`kr``si`ki (which does not evaluate anyfurther) is applied to the continuation of the c, giving```s`kr``si`ki<cont> (where we have written<cont> for the continuation in question); thisgives ` ``kr<cont> ```si`ki<cont> whichevaluates to `r``i<cont>``ki<cont>, hence to`r`<cont>i (this was where we wanted to get), andin this expression, the continuation is applied, so that thec in the initial expression immediately returnsi, and the remaining calculations are lost (inparticular, the r is lost and no newline getsprinted).Expressions including c function calls tend to behopelessly difficult to track down. This was, of course, the reasonfor including it in the language in the first place.As an exercice in using c, you might try constructingan expression that when applied to v returnsi, and when applied to i returnsv (this is not possible in the absence ofc). Answer is in the HOWTO sectionon booleans.HOWTO: various programming techniquesHow do I write a loop in Unlambda?We'll explain this with a simple example: how to write a loop thatprints “Hello, world!” over and over, followed by acertain number of asterisks, each line having one more asterisk thanthe previous.The first step is to write the loop using tail-recursion. We wantto write a function <loop>: it will takeas its argument a function $f that prints a certainnumber of asterisks, it will print “Hello, world!”,followed by the asterisks, and a newline, and then it will call itselfwith a new function that prints one more asterisk.To get things straight, we assume that<msg> is a function that acts like theidentity with the side-effect of printing “Hello, world!”,and we assume that similarly, $f acts like the identitywith the side effect of printing the asterisks. Moreover, we willwrite a function <inc> that takes suchan $f and returns a new one that prints one moreasterisk.Our first attempt at writing <loop>is the following:^f``r`$f`<msg><loop>`<inc>$f.The main ideas are: first, to “increase” $f,we simply call the same function again with`<inc>$f as argument (this is thestandard use of tail-recursion to avoid imperative constructions likevariable change). Second, to make sure we have the side effects ofwriting the message, the asterisks and the newline, we apply them tothe operator (we could have equally well applied them to the operand),which works since they act like the identity.Only one thing is wrong with our attempt:<loop> cannot be part of its ownexpansion. Here is how we get around this: we add one more parameter,$h, to <loop>, and wedecide that <loop> will be called withthis parameter equal to <loop> itself.Now there is no difficulty in writing the loop: it is^h^f```r`$f`<msg>$h$h`<inc>$f.Eliminating abstraction, we find<loop> equal to``s``s`ks``s``s`ks``s`k`s`kr``s`k`si``s`kd``s`kk<msg>k`k<inc>and it remains to write the <msg> and<inc> functions. We obtain them byeliminating abstraction respectively from^x`````````````.H.e.l.l.o.,. .w.o.r.l.d.!$x and^f^x`$f`.*$x.Finally, to start our program, we apply to<loop> the function^h``$h$hi (i.e. ``s``sii`ki), and ourfinal program is```s``sii`ki ``s``s`ks ``s``s`ks``s`k`s`kr ``s`k`si``s`k`s`k `d````````````.H.e.l.l.o.,. .w.o.r.l.d.! k k `k``s``s`ksk`k.*(Concerning indentation: the idea is that, if we insert a linebreak between an expression F and an expressionG to which F is applied, then we startG on the same column as F; furthermore, we thenalways insert a line break after G.)How can I represent numbers inUnlambda?There are many ways to do that. In the previous example, we have (implicitly)represented the integer n by the function that acts likethe identity but with the side effect of printing nasterisks. Such a representation is fine for adding integers (justcompose the functions, i.e. the addition function is^m^n^x`$m`$n$x), but you won't be able to multiply themfor example.Generalizing a little we can arive at a representation of integerswhich is quite standard and which allows any kind of manipulation(i.e. any recursive function on the integers can be representedin the pure lambda calculus using this representation), the so-called“Church integers” (named after Alonzo Church, the inventorof the lambda calculus). Our previous representation representedn as the n-th iterate of the function.*: this is not good because we can't do much with.*. Rather to try to find a function which is generalenough to permit arbitrary manipulations (it can be found but it is abit long), we represent n as the n-th iterate ofa parameter function $f. So wewrite<0> is ^f^x$x(i.e. `ki).<1> is ^f^x`$f$x(i.e. i).<2> is ^f^x`$f`$f$x(i.e. ``s``s`kski).<3> is ^f^x`$f`$f`$f$x(i.e. ``s``s`ksk``s``s`kski).and so on…Using this representation, the various operations are quite simpleto perform on numbers:The function <print> which prints a Churchinteger as a line of asterisks is ^n`r``$n.*i,i.e. ``s`kr``s``si`k.*`ki.The function <inc> which increments a Churchinteger is ^n^f^x`$f``$n$f$x,i.e. `s``s`ksk (this is a very highly optimized abstraction elimination).The function <add> which adds two Churchintegers is ^m`$m<inc>,i.e. ``si`k`s``s`ksk.The function <mul> which multiplies two Churchintegers (by applying them consecutively to the same function) is^m^n^f`$m`$n$f, i.e. ``s`ksk.The function <pow> which raises its secondargument to the power of its first, by applying the first argument tothe second (thus multiplying it with itself as many times as given bythe first) is ^m^n`$m$n, i.e. i(impressive, isn't it?).As an example of the use of Church integers, we construct anUnlambda program that prints a line of 1729 stars. To do this, we usethe fact that 1729 is the sum of 103 and 93(Srinivasa Ramanujan in memoriam), so we write theprogram as`<print>`^n``<add>`<3>$n`<3>`<inc>$n`<2><3>,(we have used the fact that 9 is 32 and 10 is itssuccessor), so`<print>```s``s`k<add><3>``s`k<3><inc>`<2><3>and after replacement our program is finally```s`kr``s``si`k.*`ki ```s``s`k``si`k`s``s`ksk``s``s`ksk``s``s`kski ``s`k``s``s`ksk``s``s`kski`s``s`ksk ```s``s`kski``s``s`ksk``s``s`kskiHow about comparing the Church integers? Sure enough,that can be done. I suggest the following — however, keep inmind that their performance (both in size and time) is far worse thanthe previous functions, and they are on the whole far less“polished”.The function <test> which returnsi if its argument is nonzero, and votherwise, is ^n``$n`kiv,i.e. ``s``si`k`kiv. A faster (but longer) versionof the same uses call/cc to return immediately when the argument hasbeen discovered to be non-zero: ^n`c^q`v``$n$qi,i.e. ``s`kc``s`k`sv``ss`k`ki.The function <leq> which returns iif its first argument is less or equal to its second, andv othwerise, is^m^n```$m<A>^ti``$n<A>^tv where<A> is ^f^g`$g$f (I suggest workingthis out to understand the modus operandi); so<leq> is``s``s`ks``s`kk``s``si`k``s`k`sik`k`ki`k``s``si`k``s`k`sikv.To decrement (and hence to substract) Church integers is by nomeans impossible. I don't know if it can be done with even moderateefficiency, however. The following scheme will work, but it ishopeless algorithmically:Consider ``$ni`ki: it evaluates to `kifor any Church integer $n, and, if $n is`k`kk, then it evaluates to k.Consequently, ^n````$ni`ki`ki`<inc>$n returns`<inc>$n if applied to an argument $nwhich is a Church integer, and `ki (i.e. the Churchinteger <0>) if applied to `k`kk.Call this function <_inc>. It is``s``s``s``si`ki`k`ki`k`ki`s``s`ksk.Consequently, the function <dec>, whichdecrements a Church integer, can be written as^n``$n<_inc>`k`kk, i.e.``s``si`k``s``s``s``si`ki`k`ki`k`ki`s``s`ksk`k`k`kk.Note that this function takes <0>(i.e. `ki) to `k`kk) — so youshould only use it on Church integers which were<test>ed as non zero.The substraction function can be built from the<dec> function. I won't even write it because it'stoo ugly.Note that the Church integers are by no means the only way torepresent integers in Unlambda. Essentially, there are two paths: youcan either use a representation which is particular to your problem athand (as we did above) and which is notcompletely general, or you can use a universal representation,i.e. one which can be transformed into the Church integers and vice versa (and which differs only by questions ofconvenience). An example of a non-universal representation is:representing n by a function that prints nasterisks. An example of a universal representation is: representingn by a list of lengthn, or representing n by a function whichevaluates its argument applied to i ntimes.How can I represent lists (and related datastructures) in Unlambda?We discuss how to create two types: products (i.e. pairs) andunions.To create products we represent the pair of $u and$v as a function which is capable, on demand, ofproducing one or the other variable:The <cons> function (creates a pair from itstwo arguments) is ^u^v^f``$f$u$v,i.e. ``s``s`ks``s`kk``s`ks``s`k`sik`kk.The <car> function (returns the pair's firstelement) is ^p`$pk, i.e. ``si`kk.The <cdr> function (returns the pair's secondelement) is ^p`$p`ki,i.e. ``si`k`ki.A union type is one which is capable of retaining one of two cases,with one datum in each case, and distinguish the two cases. It isdual to a product type:The <q1> function (creates a union in the firstcase) is ^u^f^g`$f$u,i.e. ``s`k`s`kk``s`k`sik.The <q2> function (creates a union in thesecond case) is ^v^f^g`$g$v,i.e. ``s`kk``s`k`sik.The <switch> function (takes a union and twofunctions and applies the first one to the union's data in the firstcase, the second one in the second case) is^q^f^g``$q$f$g, i.e. i.What you can do with these types is up to your imagination. A listmight be created as a chain of pairs, for example. There is a littledifficulty at the end of the list (to represent the empty list, thatis). The obvious way around it is to represent a list by a uniontype, where the first case represents the empty list and the secondcase represents a pair of the first element and the rest of the list.This works but it is long. Another solution is use v forthe empty list: this is more practical for some operations(essentially, because it is shorter), and less for others (essentiallybecause v is a bit tricky to detect, and requires call/ccfor that).How do I write tests and booleans inUnlambda?A pair of boolean values is a pair of Unlambda functionsused (arbitrarily) to represent “true” and“false”. The essential thing is that they be universal,i.e. there should exist an <ifthenelse>function which takes three arguments: if the first is the boolean<true> then it returns the second, if the first isthe boolean <false> then it returns the third.Many pairs of functions can be used to represent booleans. Hereare a few suggestions:i and v: this choice is the “standard”(or “internal”) Unlambda choice of booleans (because it is used bythe input functions, and because the functions are already part of thelanguage). They have some advantages, for example then<and> function is very easy to write (it is^p^q`$p$q, hence i). They are frequentlyuseful in the case where $f is a function which performssome side effects (when passed an argument $x, say): ifyou want to make the side effects happen according to the value of aboolean $b, just replace `$f$x by``$b$f$x. However, because v is difficultto test, the <ifthenelse> function is a bitcomplex: it is ^b`c^q``k`ki``$b$qk,i.e. ``s`kc``s`k`s`k`k`ki``ss`k`kkk and `ki: this choice is also verystandard. The advantage is that the<ifthenelse> function is extremely simple: it is^b^x^y``$b$x$y, i.e. i (notice howi plays many roles in Unlambda?). The perspicaciousreader will observe that, because of this, we build the<ifthenelse> of the other boolean pairs byconverting them to this pair.^x^y`$x$y (i.e. i) and^y^x`$y$x (i.e. ``s`k`sik). Then the<ifthenelse> is ^b``$b`kk`k`ki,i.e. ``s``si`k`kk`k`k`ki.i and `ki: these are the two firstChurch integers. The <ifthenelse> function is then^b``$b`kk`ki,i.e. ``s``si`k`kk`k`ki.A note about the Unlambda Quine ContestRecall that a quineis a program that prints its own listing. By the fixedpoint theorems in logic, such a program exists in anyTuring-complete language in which printing an arbitrary string ispossible (by a computable program of the string — a technicalcriterion which is satisfied in all programming languages inexistence). Although the fixed point theorem is constructive (andthus actually algorithmically produces a quine), actually writing downthe program can be difficult. See my quinepage and my personalcollection of quines for examples of quines in (ordinary, nonobfuscated) programming languages.From 1999/10/27 to 1999/11/03, I opened the Unlambda Quine Contest:I had written aquine in Unlambda myself, and I invited anyone else to do so.During that week, the quines were kept secret (only their md5fingerprint was revealed so that it could be later checked), in orderthat their independence be guaranteed. I offered a copy of the WizardBook to the first person to produce a quine (retrospecively I findthat I should have offered it to the best quine, or to the shortestone, or some such thing, but no matter).The contest is now over. Olivier Wittenberg (olivier.wittenberg@ens.fr)won the prize with his onemegabyte quine that he sent me within a few hours of the contest'sopening. Subsequent quines were written by Panu Kalliokoski (Panu.Kalliokoski@nokia.com),Jean Marot(jean.marot@ens.fr),Denis Auroux(denis.auroux@ens.fr) andJacob Mandelson (jlm@ghs.com).All these quines are truly gems (and, once again, I congratulateall the authors). The shortestone is only 491 bytes long, and was written by Jean Marot. The mostefficient one (in terms of data/code size ratio) was written byDenis Auroux. JacobMandelson's quine is also very remarkable in that it minimizes thenumber of dots (dots are printing functions in Unlambda) to only60.The full list of quines can be found in the quine/directory on the FTPrepository of the Comprehensive Unlambda ArchiveNetwork.I don't have any special remarks to make about how quines can bewritten in Unlambda. My general quinepage already contains everything I have to say about quines; asfor the particular case of Unlambda, well, for my part, I used a list representation of the data, but many moresubtle and compact representations were found later.Implementing UnlambdaWriting programs in Unlambda is a good exercice in patience, orderand method. It is not fundamentally difficult, being mainly aquestion of applying abstractionelimination to expressions of the untyped lambda calculus (ofcourse, obtaining these expressions in the first place is notnecessarily evident); if you're messy it will turn into a nightmare.Debugging or reading Unlambda programs is just about impossible.Another problem is to write implementations of theUnlambda language (i.e. interpreters, that is, a program thattakes an Unlambda program as input, and executes it). This is a taskthat demands less caution (an Unlambda interpreter is far easier todebug, or to read if someone else wrote it, than an Unlambda program)but more smartness, especially if the targeted language (the languagein which the interpreter is written) is a low-level language like C.For the Unlambda programming language combines the difficulties of itstwo families: of functional languages as far as writing an interpretergoes and of obfuscated languages as far as writing programs goes. Atany rate, Unlambda certainly has some nasty features that make it hardto write an interpreter for; and we now discuss some of these nastyfeatures and how to get around them.Writing an Unlambda interpreter is certainly pedagogicallyinteresting. I think it can be a good introduction to some importantconcepts in theoretical computer science, because it presents themajor difficulties (the “nasty features” as I called them a minuteago) of high-level language interpreters without some of the technicalburden of typing or variable bindings (these are interesting also, butit may be good to postpone learning about them to a later lesson).For my part, I certainly learned a good deal by writing variousUnlambda interpreters. Unfortunately, I have neither the place northe knowledge to go in the details of all the important theoreticalconcepts, but you will learn a lot by trying to write an Unlambdainterpreter yourself.The first interpreter written was the one in Scheme, which formsthe Unlambda 1.0.0 distribution. This interpreter is not reallyinteresting, for one thing because Scheme has so many features itmakes it almost trivial to interpret Unlambda in. The Unlambda 2.0.0distribution, however, includes interpreters in several otherlanguages. I suggest beginners to start with the one in Java. It isonly of pedagogical interest (being very inefficient), and Ihave taken care to put a lot of comments in it, and to writeit very cleanly (despite the comments themselves' claim to thecontrary).One question which is yet open, however, is how difficult it is towrite an Unlambda interpreter in Unlambda. That more or less combinesthe two classes of difficulty (writing Unlambda programs and writingUnlambda interpreters). I still think that the first class (thedifficulty of writing Unlambda programs) would be the dominant one;for one thing, Unlambda (as Scheme) already has all the necessarybells and whistles (such as a call/ccfunction) making interpreting Unlambda (relatively) easy.Basically, any functional language interpreter is centered, asexplained in the WizardBook, on the so-called eval/apply cycle, with twofunctions, eval and apply, calling each otherrecursively. Eval takes an expression of the language andevaluates it (i.e. executes it), whereas apply takes afunction (already evaluated) and some arguments, and applies theformer to the latter. Eval calls on apply to evaluateapplications (what in Unlambda we write`FG), and apply calls oneval to evaluate the body of a function (in Unlambda, we canargue that functions don't have bodies, but still, when applyis told, for example, to apply s to three argumentsX, Y and Z, it calls eval on``XZ`YZ).So, the basic Unlambda interpreter (forgetting about dfor the moment), written in a sufficently high-level language is verysimple: eval evaluates all the builtins to themselves and callsapply to evaluate applications; in turn, apply makes``kXY into X and```sXYZ into``XZ`YZ(which is again fed to eval). Certain features of Unlambda, orunfeatures of the meta language, will complicate the evaluator.First-class functionsUnlambda has first-class functions. In my sketchy description above,I've simply omitted the important fact that an Unlambda function canbe something like `sX (a “partially applied”s).If the underlying language (the language in which the interpreter iswritten, aka the “meta” language) has first-class functions, thenthe obvious thing is to represent Unlambda functions by functions ofthe underlying language, in which case the apply function ofthe interpreter becomes particularly trivial (it is just theapply function of the underlying language). Actually, this isnot what has been done in the interpreters that accompany the Unlambdadistribution (for one thing, because it was more tempting to make theeval function trivial than the apply function), even inlanguages where this would have been possible (see the SML/NJ versionof the interpreter for a good example of this). But it is somethingworth thinking on (an Unlambda interpreter in Unlambda would probablyuse this system).Rather than using first-class functions of the underlying languageto represent first-class functions in Unlambda, we can represent themusing data structures: represent `kX as afunction k1 with a hidden parameter X:applying k yields k1, and applyingk1 yields the hidden parameter. These hidden parametersare what would correspond, if we were interpreting a real high-level(functional) language, to closures (i.e. function environments).It should be noted that these closures can become arbitrarily complex(indeed, they are the only kind of data structures we have inUnlambda), and that they will require some kind of memory management(see below).Furthermore, if the underlying language (say, CAML) has first-classfunctions and is tail-recursive, then, even if it does not havefirst-class continuations, the difficulties we have with implementingthe continuations of Unlambda are greatlyalleviated. Indeed, we can then rewrite the interpreter in ContinuationPassing Style (see below) and representthe (passed) continuations as functions of the underlying language,which get called in a tail-recursive manner.If the underlying language does not have first-class functions,then they must be emulated by means of data structures (indeed, theonly “variable” part in a first-class function is its closure, andthat can be represented by a data structure, since the code is alwaysthe same). This is more or less clear in the Java version of theUnlambda interpreter (Java does not have first-class functions, so weuse classes and methods instead, as we are supposed to).First-class continuationsContinuations are the major pain for implementing Unlambda when theunderlying language does not have them. I refer to my call/ccpage (hoping for it to be finished some day) for a more detaileddiscussion on first-class continuations.Essentially, the canonical method is to rewrite the interpreter inContinuationPassing Style. Then eval and apply take one moreargument: a continuation, and instead of returning their result, theythrow that result to the continuation they were given (thecontinuation represents the “future of computation” at this point,and it is the continuation which will call the further eval andapply functions as needed).If the underlying language has first-class continuations, ofcourse, then we do not need CPS, because we can represent thecontinuations of Unlambda by continuations in the meta language (thisis what has been done in the Scheme and SML/NJ versions of theinterpreter). If it does not, but at least it has first-classfunctions and is properly tail-recursive, then we can very easilyrewrite the interpreter in CPS, by representing continuations ofUnlambda by functions in the meta language (this is what has been donein the Caml version of the interpreter, since Caml has first-classfunctions but not first-class continuations; it may be instructive tocompare the Caml version with the SML/NJ version). In this case, theeval and apply functions each terminate by calling theircontinuation in tail-recursive manner, so tail-recursion is heavilyused.If the underlying language (or, more precisely, its implementation)is not properly tail-recursive, then we cannot use CPS directly,because CPS calls are tail-recursive, they never terminate (except atthe very end of the program), so in a non properly tail-recursivelanguage, this will give a stack overflow (consider, for example, theRCS revision 1.5 of the Unlambda interpreter in Java that is includedin the distribution). There are various ways to work around this. Idon't know what is “standard”, if anything. One way which I findelegant is to introduce “tasks”: rather than having apply andeval never terminate and finish by calling their continuation,have them return a “task”, which is something like a continuationplus a value about to be thrown to the continuation, and when the taskis run, it proceeds with the computation. For details, consider thechanges between RCS revisions 1.5 and 1.6 of the interpreter inJava.[All this discussion does not specifically concern Unlambda. Itshould be moved to my call/ccpage when I find the time.]If the underlying language has neither first-classcontinuations nor first-class functions nor propertail-recursion, as is the case of C, then things are even more messy.All the missing abstraction layers have to be built up from scratch.First-class functions, as noted earlier, haveto be replaced by the appropriate data structures, both in thehandling of the Unlambda functions themselves, and in the handling ofthe Unlambda continuations. Yuck.Garbage collectionAs in any language having first-class (higher-order) functions,and, therefore, escaping closures, the lifetime of the variousstructures is not statically determined in Unlambda, and some kind ofautomatic memory management (aka “garbage collection”) is necessary.If the underlying language has first-class functions and Unlambdafunctions are represented by functions of the meta language, then thegarbage collection system for the meta language is used in Unlambda aswell, and all is transparent. If it does not, data structures must beused to replace the missing functionalities, and these data structureshave to be garbage collected. If the underlying language has garbagecollection (e.g. Java), then all is for the better, because, thereagain, we can rest on the existing structures. But if it doesn't,some kind of memory management has to be added to the interpreter.The simplest solution is to use an external garbage collector (forexample, the Hans Boehmconservative C/C++ garbage collector, which I used in the Cversion of the interpreter).But, as Jacob Mandelson (jlm@ghs.com) pointed out to me (andas he demonstrated in hisUnlambda interpreter, full garbage collection is not necessary inUnlambda. Indeed, since the language is without side-effects, and inparticular without the possibility of modifying pointers (in theclosures) once they are created, new objects can only point to olderobjects, and cycles cannot be created. Under those circumstances, asimpler memory mangement system will suffice: reference counting(i.e. keeping a count of the number of references to each object,and freeing a pointer when the reference count becomes 0). Theinterpreter present in the c-refcnt/ directory of theUnlambda distribution uses this reference counting method (and isotherwise identical to the garbage-collected interpreter in thec/ directory).PromisesPromises (i.e. the use of the d function) makeUnlambda a bit more of a mess. Without them, the eval functionwould be completely straightforward: call eval on the operator,call eval on the operand, and then call apply of theformer on the latter. But in fact, the result of the firsteval must be checked: if it happens to be d, thenthe further steps are not performed, the operand is bundled(unevaluated) in a promise, and that promise is returned(e.g. thrown to the continuation) as the result of the computation.Promises are forced in the apply function: when applyreceives a promise as operator, it must call eval toforce the promise, and to evaluate the part that was leftunevaluated, and finally apply it to the operand.It may, therefore, seem that the apply function will neverreceive d as operator (it is held back at the level ofthe eval function). Indeed, if you consider the SML/NJ or Camlversions of the interpreter, that part of the pattern matching iscommented out. But there are subtleties: what about something like`cd: the Unlambda specificationsclearly state that this evaluate `d<cont>, with<cont> being the appropriate continuation. Butinstead of constructing the `d<cont> expression andcalling eval on it, we may prefer to directly call applyon d and the appropriate continuation, in which caseapply will, indeed, receive d as operator. (Seethe note in the invoke method of theDelContinuation class in the interpreter written inJava.)Can Unlambda be compiled?An interesting question, and one whose answer I do not really know,for one thing because I'm not entirely certain as to what“compiling” should mean.On the one hand, we can certainly write a program (technically,using the snm theorem) that takes an Unlambda program, possibly parsesit, and bundles it with an Unlambda interpreter, and call that the“compiled” version. I don't think that qualifies as a compiler: acompiler should turn Unlambda code into code of the targetlanguage, not data that will be interpreted by some genericcode. Unfortunately, the boundaries between code and data are not asclear as I would like them to be (see also my quinepage for more thoughts on the subject). Unlambda can certainly becompiled in Unlambda at least, by the identity function. JacobMandelson (jlm@ghs.com)observed that it is more reasonable to try “decompiling” Unlambdathan “compiling” it.If we restrict ourselves to the S, K and I combinators (as well asprinting functions), removing the troublesome C and D functions, thenUnlambda can be compiled, at least in a high-level functional language(which can then be compiled in low-level imperative languages usingstandard methods): for example, ```sii``sii (an endlessloop) would be trivially compiled, using a lisp-like notation, in(((S I) I) ((S I) I)), where S andI are part of the “Unlambda run-time library”. Thismay seem like a void assertion, but note the important differencebetween this and producing (interpret '(((S I) I) ((S I)I))), where only interpret is defined: the formeris a true (albeit trivial) compilation, and the latter is merelybundling the program as data with an interpreter to read the data.The c (call/cc) function would not cause considerabletrouble either, if the underlying language (the target language forcompilation) has first-class continuations, and even if it doesn't, wecan emulate them for example by producing CPS code.Promises are a much bigger problem: I don't think it is possible tocompile Unlambda, with the d special form, in areasonable programming language. Indeed, whereas we could convert“apparent” promises, such as `dX, intopromises from the target language, it is not possible to knowbeforehand whether a piece of code will really be interpreted ormerely made into a promise.On the other hand, promises aren't anything like aneval function (something that canonically can't becompiled — or at any rate, to compile it you need to bundle theprogram with an entire interpreter or compiler). So maybe it ispossible after all, but I'm very uncertain as to the way it shouldwork. I wish I could express myself more clearly.Unlambda referenceFirst we must specify that whitespace is ignored in an Unlambdaprogram (wherever it may be, except, naturally, between the period andthe character in the .x function name).Comments are also ignored, a comment being anything starting from the# character to the end of the line.If F and G are two Unlambda expressions, thenthe expression `FG is also anexpression (called the application of F toG). It is evaluated as follows: first,F is evaluated (and its value is a function, since there isno other kind of values in Unlambda); if the value of F isnot d, then, G is evaluated, andfinally the value of F is applied to the value ofG.To complete the description of Unlambda, we need therefore onlyspecify what happens when F is applied to G, andto do that we consider each possible value of F.k (“constant generator”)The kfunction takes an argument X and returns the function`kX (see below).`kX (“constant function”)The`kX function (which is not primitive butobtained by applying the primitive function k to somefunction X) takes an argument, ignores it and returnsX.s (“substitution”)The sfunction takes an argument X and returns the function`sX (see below).`sX (“substitution firstpartial”)The `sX function (which isnot primitive but obtained by applying the primitive functions to some function X) takes an argumentY and returns the function``sXY (see below).``sXY (“substitutedapplication”)The ``sXYfunction (which is not primitive but obtained by applying theprimitive function s to two functions X andY successively) takes an argument Z and returnsthe evaluation of``XZ`YZ.i (“identity”)The i functiontakes an argument and returns that argument.v (“void”)The v functiontakes an argument X and returns v itself.c (“call with current continuation”)Thec function takes an argument X and returnseither the evaluation of `X<cont> where<cont> is c's current continuation(see below), or else the value passed to <cont> ifthe latter was applied (with the effect of making creturn immediately).<cont> (a continuation)Continuationstake an argument and non-locally jump to the point in history when theevaluator was waiting for the corresponding c to return,making that c return that argument.d (“delay”)The d function isnever truly applied (it is a special form). It only occurs in theform `dF where F is an Unlambdaexpression (see below).`dF (“promise”)The`dF function takes an argument Yand evaluates F, giving a function X, andreturns the evaluation of `XY..x (“print”) and r(“carriage return”)The .x functionis written using two characters. The first character is aperiod and the second is any character. Nevertheless,.x is a single function in Unlambda, andx in this expression is merely a character (read duringparsing), not a parameter to the function. The rfunction is exactly equivalent to .(newline).The .x function behaves like thei (identity) function, with the side effect that itprints the character x (to the standard output) when it isapplied. The r function also behaves like the identityand prints a newline character.e (“exit”) only in Unlambda version 2 andgreaterThe e function takes an argumentX. It exits immediately, pretending (if the interpretercares) that the result of the evaluation of the program isX.@ (“read”) only in Unlambda version 2 andgreaterThe @ function takes an argumentX. It reads one character from the standard input, makingit the “current character” and returns the evaluation of`Xi or of `Xvaccording as one character has been read successfully or not (forexample on EOF).?x (“compare character read”)only in Unlambda version 2 and greaterThe?x function (where x is acharacter, as in the .x function) takes anargument X. It returns the evaluation of`Xi or of `Xvaccording as the current character (the one read by the lastapplication of @) is x or not (if@ has not been applied or if it has encountered an EOF,there is no current character, and x is deemed not to beequal to the current character).| (“reprint character read”) only inUnlambda version 2 and greaterThe |function takes an argument X. It returns the evaluation of`X.x, where x is thecurrent character (the one read by the last application of@) or of `Xv if there is nocurrent character (i.e. if @ has not yet beenapplied or if it has encountered an EOF).Unlambda distributionUnlambda 2.0.0 is now available. You can download it using FTPor using HTTP,but using FTP is preferred if you have the choice. If you want olderversions, they are available in this FTPdirectory.Unlambda is distributed under the terms of the GNU General PublicLicense, either version 2 of this license, or, at your option, anylater version. Since Unlambda is Free Software, it comes withabsolutely no warranty: see the GNU General PublicLicense for more details.(Note that this concerns the distribution. There is nocopyright on the language itself: you do not need to ask formy permission to write an Unlambda interpreter, and you are permitted(though by no means encouraged) to write a non-free interpreter. As amatter of fact, there exists at least one non-free Unlambdainterpreter, theone written by Jacob Mandelson (jlm@ghs.com), which is farmore efficient than the interpreters in the Unlambdadistribution.)This document is included in the Unlambda distribution. You canalso find it on the World Wide Web at http://www.eleves.ens.fr:8080/home/madore/programs/unlambda/.Please send comments and suggestions about Unlambda and itsinterpreters to david.madore@ens.fr.Happy hacking!Comprehensive Unlambda Archive NetworkThe goal of the Comprehensive Unlambda Archive Network is to gatherall the Unlambda programs that are written (provided their authorsagree, of course). Since there are very few programs in Unlambdaaltogether, it is convenient to centralize everything in one place, itwill not take too much disk space, and a copy of the archive isincluded in the Unlambda distribution.You can find the archive in the directory /pub/madore/unlambda/CUAN/on the “Quatramaran” FTPsite. See theMANIFEST file for a list of the programs in the CUAN.Please drop me a note if youhave a program you want to add to the archive.This site is part of theEsoteric Programming Languages Ring:[Previous 5 Sites|Previous|Next|Next 5 Sites|Random Site|List Sites]David MadoreLast modified: $Date: 2003/08/10 22:24:48 $ |
|
