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