Lambda Calculus to Brainfuck

The goal of this page is to compile Lambda Calculus into Brainfuck.

Functions

Procedures

You think Brainfuck is not functional? Not at all. You can make prodedures(functions without parameters and return values) with it.

Here, I made a procedure(permanently named procedure UN0, or NOT 0):

Choose the procedure to call(Here calls UN0)
+
Here is the procedure checker(UN0 prints "Hello world")
[>+[-->-[>>+>-----<<]<--<---]>-.>>>+.>>..+++[.>]<<<<.+++.------.<<-.>>>>+.[>]]

See? You can also define procedure 0:

Choose the procedure to call(Here calls P0)
Here is the prodedure checker(P1 prints "Hello world")
not the cell:
[>+<[-]]+>[<->-][>+[-->-[>>+>-----<<]<--<---]>-.>>>+.>>..+++[.>]<<<<.+++.------.<<-.>>>>+.[>]]

Procedures with return values

That's easy. Simply set a cell into a value as return value.

We will define procedure 2(print spaces forever)here:

++>++<
Checker:
[->-<]+>[<->[-]]<[++++++++.[-]>++>++<[->-<]+>[<->[-]]<]

Look! We just made a recursion program!(Recursion requires procedures with return values)

Last but not least:functions

We will make a procedure with parameters value here(which is a function).

Just for simplicity, we will swap 2 values.(We name is procedure UN0)

[>>[->+<]<[->+<]>>[-<<+>>]]

See...2 cells represent the return values(usually functions can only return 1 value)

Anonymous functions

We have to name the function, or it will be impossible to call it.

This is how we implement anonymous functions.

Calling Functions

We just called functions in the function checker.

example

Implement this:

(λx.(λy.(λz.(λx.z x) (λy.z y)) x) y)

Think x, y, z as 3 cells on Brainfuck.

Implementation of the steps(for clearer logic. I am possibly wrong; please correct that if so):

(λx.(λy.(λz.(λx.z) (λy.z)) x) y)
(λx.(λy.(λz.z z) x) y)
(λx.(λy.(λz.z) x) y)
(λx.(λy.z x) y)
(λx.z y)
z

In every lambda expression

(λx.z y)

x is the parameter, z is the return value, y is the parameter value.

Right, we can use the functions defined above.(We have to name it)

Let us first check out a function:

((λx.z) y)

Name it procedure UN0 ant try to implement it:

[[<]>>>]

(P.S.:we permanently put cells 1-3 from x to y, and leave cell 0 blank)

However, we cannot implement Nested functions.

Try Again

Check out this program below:

(λx.(λy.y x) y)

An example of nested functions.

Name the outside function 2, and the inner function 1.

Step 1, predefine

>>+>++<<<

The predefine step. Define z as 1, a as 2. (function1, function2)

Step 2, calling 1

Just note that b is the calling byte.

>>>>+[-<->]+<[>-<[-]][<<<<----]++++

I predefined x as 4, y as 2.

Step 3, calling 2

[>]>[-]++[-<<->>]+<<[>>-<<[-]][<<<--]++

Successfully returned y.

The execution in Lambda Calculus

(λx.(λy.y x) y)
(λx.x y)
y

Comment: the sequence used in the program

xyzab0000000000000000000000000000...