Weekends are for hacking up crazy ideas (and so are evenings). This weekend was no different; amongst other things I got around to implement an Unlambda interpreter in C#. A what? Let’s talk about that first.

Warning: Reading this post can cause permanent brain damage. It definitely helps to have some understanding of lambda calculus, SKI combinators, continuations, and more.

# What’s Unlambda?

Unlambda is an esoteric programming language designed by David Madore. It’s based on functional programming ideas, very minimalistic (in terms of the number of operations) and very obscure (because of its minimalistic nature and the syntax). What’s it good for? Fun, nothing more. Or maybe some understanding of combinators. Let me cite the Unlambda website to summarize the above:

This means that the language was deliberately built to make programming painful and difficult (i.e. fun and challenging).

I guess I should start believing what some colleagues attribute to me: I like pain. A while back I added the creation of an Unlambda interpreter to my list of planned Crazy Sundays projects. (Unfortunately the list always grows and never shrinks…)

So, what’s in a name? Unlambda is based on functional programming, which finds its foundations in lambda calculus. We all know by now what lambda calculus embodies, don’t we? Essentially, it’s “just” a way to declare functions and manipulate them. The lambda notation of functions comes in two parts: the arguments and the body. This is shown below with a couple of samples:

Here I have declared three functions. The first is the identity function: given x, it simply returns x. The second one takes two arguments and drops the second one, just to return the first one. The last function is more subtle. Remember that all we manipulate in lambda calculus are functions: the arguments of the last function are named x, y and z and are all functions. Functions can be applied to other functions: this is simply written by juxtaposition (putting symbols next to one another). For example xy stands for apply x to y. This happens in a left-associate manner: xyz means (xy)z, so the function resulting from evaluating the application of x to y is next applied to argument z. The last function I’ve shown above does use parentheses to change the evaluation order: x is applied to z and that result is applied to the result of applying y to z (still follow?).

But those functions are not just samples: they’re actually the basic building blocks of combinatory logic. In essence this means you can get rid of all lambdas, replacing them by combinations of those essential building blocks:

I is known as the identity function. It’s actually redundant, as SKK is equal to I (to try that, evaluate SKKx = Kx(Kx) = x, therefore SKKx = Ix and thus SKK = I through extensionality).

K is the constant function: it produces a constant output (given by its first argument) no matter what it’s applied to next: Kx(whatever) always produces x. It’s a simple as that.

S is the substitution function. Instead of applying x to y directly, it first applies z to both functions (producing xz and yz) and then applies those two to one another. So the third argument, z, gets “substituted” in both x and y through application.

Having just S and K makes a language Turing-complete. All good things boil down to two: binary, duality, S and K. So, all we need to write all sorts of programs is a machine with two instructions: S and K. (Question for the reader: Can we do with less?) Needless to say this leads to obscure code, but that’s what unlambda stands for. And now you see why the language is called Unlambda: there’s no lambda operation (abstraction) left, everything goes through the combinators.

Oh, and by the way, if you’re given a program based on lambdas, you can “compile” those away by applying a technique called “abstraction elimination”, resulting in S, K, I and parentheses:

Ignore this curiosity for now; just keep in mind it’s a “handy” way to write programs using plain old lambda calculus and make it fit in S, K and I combinators.

# The syntax

There’s no reason for me to duplicate the Unlambda Reference here. The main operators are ` (backtick, for application), s, k and i. A few others are provided to make the language more usable (., r and @ for input and output, as well as ? and | to deal with input state). And as Unlambda is meant to be a pain in the neck, David added some interesting complications such as Call/CC (call with current continuation, known from Scheme) and promises (a way to delay evaluation).

With this in place, we can start writing applications (note it’s normal for your head to explode):

```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

This one prints the Fibonacci numbers by means of asterisks (*, *, **, ***, *****, etc) separated by newlines. Try to spot the output in the see of combinators: .* prints the asterisks and r prints the newlines.

Can I explain the program above? I could try, but am not going to: “all” there is to it is executing it blindlessly using the rules for S, K and I. The backticks are applications and make it possible to drop all parentheses from the syntax (they are not allowed in fact, making it very easy to parse Unlambda programs btw). How was this program written (by the way, I didn’t write it – it’s taken from the Unlambda homepage)? One necessary ingredient when working with numbers is Church numerals (which represents numbers and operations on those, as we need things like addition). Below are a few representations of numbers 0, 1 and 2 in Church numerals, translated to SKI:

Next, we also need some operators. On such operator is increment (+ 1):

It’s trivial to see that applying inc to 1 (represented as I), yields 2. I’ll leave it to the reader to verify that applying inc to 0 results in 1. Also calculate 3 from 2 using the inc function.

One more operator while we’re at it: plus. This one is defined in terms of inc as follows (why?):

Exercise: Apply plus to 1 and 2 and check it corresponds to the result of inc 2 (previous exercise).

# Implementing Unlambda in C#

Now to the real topic of this post. How to implement Unlambda in its entirety (including “c” Call/CC and “d” promises)? Before we get there, we need to think about parsing input first. But let’s start with the Main method:

## Main

Main is trivial. It validates arguments, parses the input file, and feeds the resulting expression tree to an Execute method. And, hacky as this is, we do some ugly not-so-much recommended exception handling as well:

```static void Main(string[] args)
{
if (args.Length != 1 || string.IsNullOrEmpty(args[0]))
{
Console.WriteLine("Usage: {0} <inputfile>", Assembly.GetEntryAssembly().GetName().Name);
return;
}

string file = args[0];
if (!File.Exists(file))
{
return;
}

try
{
Execute(Parse(file));
}
catch (Exception ex)
{
Console.WriteLine("Error: " + ex.Message);
}
}```

## Parse

Parse isn’t hard either. The entry-point to the parser simply opens the file and gets a StreamReader:

```static Expression Parse(string file)
{
return Parse(sr);
}```

Next, the real parser. Simply a mapping from characters onto expressions:

```static Expression Parse(StreamReader sr)
{
char ch;
do
{
if (ch == '#')
{
ch = '\n';
}
} while (char.IsWhiteSpace(ch));

switch (ch)
{
case '`':
return new ApplyExpression(Parse(sr), Parse(sr));
case 'S':
case 's':
return new FunctionExpression(S);
case 'K':
case 'k':
return new FunctionExpression(K);
case 'I':
case 'i':
return new FunctionExpression(I);
case 'V':
case 'v':
return new FunctionExpression(V);
case 'D':
case 'd':
return new DelayedFunctionExpression(D);
case 'C':
case 'c':
return new FunctionExpression(CallCC);
case 'E':
case 'e':
return new FunctionExpression(Exit);
case 'R':
case 'r':
return new FunctionExpression(Print('\r'));
case '@':
case '.':
case '|':
return new FunctionExpression(Reprint);
case '?':
default:
throw new Exception("Unrecognized input symbol: " + ch);
}
}

{
if (c == -1)
throw new Exception("Unexpected end of file.");
return (char)c;
}```

But this deserves a bit of explanation. First, the comment-and-whitespace ignoring loop: this simply scans input for whitespace and if an # is encountered, drops the rest of the line.

The big switch statement recognizes all valid input symbols, case-insensitively. There are three sorts of expressions being built:

• Function expressions correspond to built-in functions. The arguments to the constructor will be explained next.
• The delayed function expression for “d” promises. Essentially the same as a regular function expression but a different type to recognize during evaluation.
• The apply expression that takes two expressions and applies the first one to the second one. This corresponds to the ` operator: `AB means applying whatever A is to whatever B is.

The ReadNextChar helper tries to read one character and throws if the end of the file is reached. This is fine, it will only be called when we really expect a character in the input stream. Notice how functions like . and ? read one character ahead to get their corresponding character (to print it, ., or compare it, ?, respectively).

## The expression objects

So, the output of the parser is an Expression object, and we know there are three subtypes. How do those look?

```abstract class Expression
{
}

class ApplyExpression : Expression
{
internal ApplyExpression(Expression f, Expression arg)
{
Operator = f;
Operand = arg;
}

public Expression Operator { get; private set; }
public Expression Operand { get; private set; }

{        …
}
}

class FunctionExpression : Expression
{
internal FunctionExpression(Function f)
{
Function = f;
}

public Function Function { get; private set; }

{        …
}
}

class DelayedFunctionExpression : FunctionExpression
{
internal DelayedFunctionExpression(Function f) : base(f) { }
}```

Simple, isn’t it? As you can see, each expression can be evaluated through an Eval method. We’ll talk about that next, in addition to the Function and Continuation types.

## Continuation-passing style

In order to allow Call/CC (call with current continuation), we need to use Continuation Passing Style (CPS). The idea of this weird-sounding animal is simple: a function takes in a “continuation function” that will get the result of the function’s execution. So, every such function can be void-returning:

void Add(int a, int b, Action<int> continueWith)
{
continueWith(a + b);
}

This results in a tail-recursive setting. How this enables (and what is) Call/CC is something I won’t elaborate on this time. You’ll see it implemented in just a minute. The sample above could be called like:

{ Console.WriteLine(sum2); }));

We’ll call the continuation function (Action<int> above) a Continuation:

`delegate Task Continuation(Function f);`

This delegate takes in a Function (the result of every computation in Unlambda is a function, remember there’s nothing but functions) and returns a Task. Where does that come from?

Well, there’s one problem with our CPS-based solution: it exhausts the call-stack. Yes, the CLR a tail call instruction, but no it’s not exposed through C#. We need something else here, which we’ll call tasks. This idea is that a task can be applied to yield the subsequent task. Sounds weird? Stay with me for a moment and have a look at the Execute method:

```static void Execute(Expression ex)
{
Continuation exit = f => { Environment.Exit(0); return null; };
;
}```

Say we have an expression that computes some function: we call it by means of the Eval method. Eval wants a continuation, essentially saying what to do next after Eval completes. We begin by saying the thing to do after the top-level expression (i.e. representing the whole program) completes, is to exit the interpreter. The “return null” statement will never be reached. An alternative implementation would be to break from the loop in a null-task and make exit simply return null.

Conceptually, Eval should be called recursively: to do an application of A to B, we need to evaluate A first, then B and finally call the result of evaluating A with the result of evaluating B. But this would be one source of stack exhaustion. So instead of causing recursive calls, we make Eval return a Task object. Our main loop then gets that task, and calls it. The result of such a call is the next task to carry out:

`delegate Task Task();`

So, how does ApplyExpression do its eval?

```class ApplyExpression : Expression
{
internal ApplyExpression(Expression f, Expression arg)
{
Operator = f;
Operand = arg;
}

public Expression Operator { get; private set; }
public Expression Operand { get; private set; }

{
return () => Operator.Eval(f => () => Operator is DelayedFunctionExpression ? c(Program.D1(Operand)) : Operand.Eval(arg => () => f(arg, c)));
}
}```

Ah, we’re getting somewhere: basically the evaluation of an applications hands back to the caller a task (notice the () => … lambda to new up a Task) that will “recursively” call the Operator’s Eval method to get the function to be applied (e.g. ` (SKK) (KSK) will first evaluate the operator (SKK), to I that is, and then evaluate the operand (KSK), to S that is).

How the inner Operator.Eval works is irrelevant for now. The idea is that Operator.Eval will return a Task and the thing we return from the ApplyExpression’s Eval method needs to be a Task too. So, you see that the result of calling Eval on the application is a new task with the first thing it will do being the evaluation of the operator. This allows the main loop to continue calling through the resulting task objects, and you see the call stack never grows deeper than a single eval.

So, we know how a Task works and how a Continuation works. Recapitulate:

```delegate Task Task();

A continuation is something that can execute a function and return a task to continue executing. A task is something that can execute, producing its successor task. We still need to know how a Function works. Well, everything is a function in Unlambda so not unsurprisingly the argument to a Function is, well, a Function. And as we’re using CPS, the next argument needs to be a Continuation object:

`delegate Task Function(Function arg, Continuation c);`

Wow, three mutually recursively defined delegate types. A note on functions only taking in one argument, this can be achieved by currying: every function of multiple arguments can be rewritten as a function that eats one argument at a time:

K x y = x
K x = y –> x
K = x –> y –> x

S x y z = x z (y z)
S x y = z –> x z (y z)
S x = y –> z –> x z (y z)
S = x –> y –> z –> x z (y z)

## A look at the SKI combinators

Let’s make this whole thing concrete by looking at how the functions S, K and I are defined. First I, as that’s the simplest one:

`static Function I = (x, c) => c(x);`

Remember a function takes in a function as its argument (here x) and a continuation (here c). All I does is taking its argument and passing it to its continuation as-is. This should be simple to understand: we just continue the computation with I’s argument, as the effect of applying I is nothing but returning its argument (identity function behavior).

K is a bit more complicated, but not too hard either:

`static Function K = (x, c) => c((y, c1) => c1(x));`

Here we curry K, a function that takes in two argument x and y, to eat one argument at a time. Every argument comes with the continuation for that application. That explains the (x, c) and (y, c1) input pairs. Recall what K does: given two arguments, it simply returns the first one (x). So, once we have the two arguments (one at a time, through currying), we apply the first argument (x) to the continuation we have at hand. That’s what c1(x) does.

Notice how the first continuation is called, passing in the curried function:

(y, c1) => c1(x)

This is nothing but the curried version of K. The y parameter is irrelevant as K doesn’t look at it. So in essence: calling K with the first argument returns a Task that results from calling the supplied Continuation with a new (curried K) Function that on its turn evaluates its continuation to x, the surviving argument from K.

Now the beauty of all: S. Here we need to curry twice:

```static Function S = (x, c) => c((y, c1) => c1((z, c2) =>
{
Expression arg = new FunctionExpression(z);
return () => new ApplyExpression(
new ApplyExpression(
new FunctionExpression(x),
arg),
new ApplyExpression(
new FunctionExpression(y),
arg)
).Eval(c2);
}));```

First x is supplied with its continuation c, then y with c1 and finally z with c2. Once we’re there we can evaluate what S is supposed to do:

S x y z = x z (y z)

This consists of three applications: first x to z, then y to z and finally the results of the first application (x z) to the result of the second one (y z). But we already have the ability to apply functions by means of our expression tree model, so we just new up an expression tree that represents the computation (x z (y z)). Then we call Eval on it, passing in the current continuation at hand, so it will eval the whole thing and pass its result (a Function, as everything in Unlambda is such a thing) to the continuation c2.

I bet this will be overwhelming, but that’s what esoteric languages are all about: an impractical nature :-).

## Void

“Ignore whatever is passed to me”, is what void does. It simply says: give me something and I’ll do my own thing going forward. To accomplish this, it passes itself to the continuation:

`static Function V = (x, c) => c(V);`

Quiz: Why does the above work? We’re declaring V and using it on the right-hand side. Would the following work? Why (not)>

void DoSomething()
{
Function V = (x, c) => c(V);
}

## Some other, simple functions

To regain breath, let’s look at a few input/output functions which are fairly trivial. To make those work, we have the concept of an input stream (simply Console.In) and a character that was last read:

```static TextReader In = Console.In;
static char? lastChar = null;```

Three functions deal with this piece of global state: Read (@), Reprint (|) and Compare (?). Those are shown below:

```static Function Read = (x, c) =>
{
lastChar = ch == -1 ? null : (char?)ch;
return () => x(lastChar != null ? I : V, c);
};
static Function Reprint = (x, c) => () => x(lastChar != null ? Print(lastChar.Value) : V, c);
static FC<char> Compare = ch => (x, c) => () => x(lastChar == ch ? I : V, c);```

Read takes input from the input stream, sees whether we reached the end or not, and sets the lastChar – a nullable char – accordingly. Next, it returns a task that will call the function following the Read (@) call, i.e. x. The argument to that function becomes either the identity function (causing execution to continue in essence) or void (something bad happened), depending on the input that was read. And obviously it passes on the continuation.

Reprint is very similar and defined in terms of a yet-to-be-defined built-in Print function. But again, it either passes on the Print function or void (in case no character is available yet, or anymore).

Compare is a function that takes an argument in the program code (e.g. ?b to compare the last read character to b), so we create an FC or function constructor that can be called by the Parser:

```case '?':

So, the next character in the program text becomes the character to compare to, the the “real” Compare function is parameterized in this:

static FC<char> Compare = ch => (x, c) => () => x(lastChar == ch ? I : V, c);

with

`delegate Function FC<T>(T t);`

yields the following given ‘b’:

Function compB = (x, c) => () => x(lastChar == ‘b’ ? I : V, c);

which again follows the same pattern as the Read function: if equal, I is returned, otherwise V is returned. This allows for some control flow constructs.

Finally, there’s the Print function, again parameterized by source text (e.g. .* prints a ‘*’):

`static FC<char> Print = ch => (x, c) => { Console.Write(ch); return c(x); };`

Prints to the console as a side-effect and continues execution by calling the continuation. Notice ‘r’ is implemented in terms of Print, simply by printing ‘\n’ to write a new line:

case 'R':
case 'r':
return new FunctionExpression(Print('\n'));

## Call/CC and delay/promises

The most esoteric parts of Unlambda are maybe the Call/CC and delay functions (c and d):

`static Function CallCC = (x, c) => () => x((f, c2) => c(f), c);`

This is Call/CC: a function that returns a new task (() => …) that calls the given function (x) with the current continuation (c), but also causes the function’s argument to become a function that ignores its own continuation (c2) and instead uses the current one. That’s the crux at the heart of Call/CC: it ignores that passed-in continuation, and substitutes it by the current one. David has a good overview of Call/CC if that seems exotic to you.

Another one we should mention here is “d”, maybe even more mind-boggling. It essentially delays the evaluation of its argument: `FG where F evaluates to the delay function (d) does not evaluate G straight away. Instead it returns a function that, when applied, will evaluate G. E.g. if ``FGH is evaluated, and F is ‘d’, G doesn’t get evaluated till H is applied to the delayed `dG function. Therefore, this is an exception to the regular rules of evaluation in Unlambda, and not surprisingly it is a bit involved to write down:

`static Function D = (f, c) => c(D1(new FunctionExpression(f)));`

This is the easy part. I’ve factored out D1, the curried form, as it needs to be reused somewhere else – see further. I just wished I could explain how D1 works in a crystal-clear fashion. Let me try…

`internal static FC<Expression> D1 = ex => (f1, c1) => () => ex.Eval(f => () => f(f1, c1));`

In essence, D1 is again a function constructor, this time based on a FunctionExpression. Our function expression here is based on “f”, the thing to be delayed. In here, we create a new Function that given an argument f1 and a continuation c1 will produce a task (() => …) that will evaluate the delayed expression (ex), passing in a continuation. This is the most complex aspect of D1, at least to understand it (because, again it’s quite simple in its implementation). The way FunctionExpression.Eval works is shown below:

```class FunctionExpression : Expression
{
internal FunctionExpression(Function f)
{
Function = f;
}

public Function Function { get; private set; }

{
return cont(Function);
}
}```

It simply calls the continuation with the supplied function. Put this together with how D defers evaluation of its argument f by new’ing up a FunctionExpression (ex) that subsequently gets called in D1 through ex.Eval, and we come to the conclusion that the argument of that continuation is no other than the deferred f:

static Function D = (f, c) => c(D1(new FunctionExpression(f)));

internal static FC<Expression> D1 = ex => (f1, c1) => () => ex.Eval(f => () => f(f1, c1));

So the task returned by the Eval’s continuation simply calls the deferred function f and passes in f1 as its argument, also asking to be continued with D1’s continuation.

## ApplyExpression revisited

The final thing to look at is ApplyExpression’s Eval method (again):

```class ApplyExpression : Expression
{
internal ApplyExpression(Expression f, Expression arg)
{
Operator = f;
Operand = arg;
}

public Expression Operator { get; private set; }
public Expression Operand { get; private set; }

{
return () => Operator.Eval(f => () => Operator is DelayedFunctionExpression ? c(Program.D1(Operand)) : Operand.Eval(arg => () => f(arg, c)));
}
}```

Application is the thing that gets influenced by delayed functions, as created by the “d” operator. In essence, if the operator passed to an ApplyExpression is delayed, we should not evaluate the argument either. Rather we should create a promise – as represented by D – for it:

Operator is DelayedFunctionExpression ? c(Program.D1(Operand)) : …

Only when D1 gets called, as explained in the previous paragraph, evaluation of the operand will be forced (as promised).

If the operator passed to an ApplyExpression was not delayed, we just proceed regularly:

Operator.Eval(f => () => Operator is DelayedFunctionExpression ? … : Operand.Eval(arg => () => f(arg, c)));

That is, we evaluate the operand by passing in a continuation that subsequently will call the function f with the evaluated argument, passing in the continuation. If you read the whole (eager) evaluation from left to right you can see we first evaluated the operator, then the operand, and finally called the function. So, there are three nested tasks here (look for () => …).

Note: In theory it would be possible to eliminate the Expression types too, turning them in lambdas as well (representing their Eval method, hence of type Continuation –> Task). There’s one direct implementation worry though: the type-check for an Operator against “a delayed expression type”. Delegates have no tweakable type hierarchy, and there’s no way to add properties (like IsDelayed) to them (yes, you could keep a dictionary to maintain that property for each expression). You could hack it up in IL if you want, but let’s keep that as a challenge to the reader. Essentially you want to replace Expression by something like this:

`delegate Task Expr(Continuation c) {    public bool IsDelayed { get; set; } // Hypothetical syntax};`
```static Func<Function, Expr> FuncExpr = f => c => c(f);
static Func<Expr, Expr, Expr> ApplExpr = (Operator, Operand) => c => () => Operator(f => () => Operator.IsDelayed ? c(Program.D1b(Operand)) : Operand(arg => () => f(arg, c)));```

# Testing it

Phew, never though I’d make it this far. We’ve just written a humble 186 lines of dense C# code (no comments). Let’s see it works, with our Fibonacci sample:

Sweet – looks right, doesn’t it? 1, 1, 2, 3, 5, 8, 13, 21, etc.

I tried the interpreter code on all the samples that come with the Unlambda distribution, and it seems to pass fine:

This said, it’s always possible I made some mistake somewhere, so don’t make your next space shuttle project depend on this code :-).

Gentle as I am, I’ve made the code available over here. Enjoy <g>!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Filed under:

#### #re: Unlambda .NET – With a Big Dose of C# 3.0 Lambdas

Monday, April 27, 2009 3:52 AM by Aaron Powell

I'm really glad I'm a few beers in, this is making a lot more sense to me now :P

Mr De Smet, you are truely insane!

#### #Dew Drop - April 27, 2009 | Alvin Ashcraft's Morning Dew

Pingback from  Dew Drop - April 27, 2009 | Alvin Ashcraft's Morning Dew

#### #re: Unlambda .NET – With a Big Dose of C# 3.0 Lambdas

Monday, April 27, 2009 9:22 PM by Subodh

Hi, Your blog is so inspiring. The innovations are thought-provoking and the explanations you have provided in this blog entry has helped me lot as far as functional programming is concerned. One word - Awesome!! Please keep inspiring... Subodh

#### #Reflective Perspective - Chris Alcock &raquo; The Morning Brew #336

Pingback from  Reflective Perspective - Chris Alcock  &raquo; The Morning Brew #336

#### #The Essence of LINQ – MinLINQ

Friday, January 01, 2010 5:47 AM by B# .NET Blog

Introduction Before reaching the catharsis in the “More LINQ with System.Interactive” series over here

#### #Top 9 Posts from 2009

Sunday, January 03, 2010 1:15 AM by B# .NET Blog

select top 9 [Subject] from dbo . cs_Posts where postlevel = 1 and usertime &lt; &#39;01/01/2010&#39;