true = λab.a false = λab.b and = λxy.(x y false) in (and true false)

Run Debug parsing

What is this?

Untyped lambda calculus evaluation tool, and thus Turing complete programming language. All of computation can be built on top of pure lambda functions, and this is a kind of sandbox where you first define what is a number before you can do anything useful. Like nand-game but with functions.

Umm, what?

This is a lambda function definition

λab.a

It takes two parameters a and b, and returns the first parameter a. The a and b are also called symbols.

Function evaluation is written with parenthesis wrapping both function and its arguments:

(λab.a argument1 argument2)

So instead of the common function call notation f(a, b), it is (f a b). In the example above the function λab.a returns the first parameter a, evaluating to argument1.

Here the argument1 and argument2 are some expressions. An expression is either function definition, function evaluation, or symbol. It can be a deeply nested structure.

The program consists of the assignments, a keyword in, and one expression. For example, this is a valid program you can insert to the left

argument1 = λc.c
argument2 = λd.d
in
(λab.a argument1 argument2)

It evaluates to

λc.c

Ok, and?

That's it! There is nothing more! No numbers, no if-statements, no loops. Only pure lambda functions. The task is to build the programming language primitives from pure lambda functions. These primitives can be then used to build more intuitive programs. This goes extreme on the paradigm of functional programming: "Building your own programming language first"

You have full liberty to decide what is true. For example, boolean calculation "false and true" can be encoded like so:

true = λab.a
false = λab.b
and = λxy.(x y false)
in
(and true false)

Try copy-pasting it to the left, it evaluates to

λa.λb.b

Wait, why λa.λb.b instead of λab.b?

Because that is just internal representation in lambda calculus, which does not have multiparameter functions. A two parameter function λab is just a syntax sugar to a single parameter function λa that returns a single parameter function λb. This behaves as a two parameter function.

But why?

All of computation can be formulated on top of functions! How cool is that! See this video, it's awesome.

Can I hide the pony below?

No, she's integral part of the interpreter.

Standard library

Copy paste whatever fragments you need from here. Or all.

true = λab.a
false = λab.b
and = λxy.(x y false)
or = λxy.(x true y)

# Numbers encoded as recursive function calls
0 = λfx.x
1 = λfx.(f x)
2 = λfx.(f (f x))
3 = λfx.(f (f (f x)))
4 = λfx.(f (f (f (f x))))
5 = λfx.(f (f (f (f (f x)))))
+1 = λnfx.(f (n f x))
-1 = λnfx.(n λgh.(h (g f)) (λu.x) (λu.u))

# Arithmetic
+ = λnmfx.((n f) (m f x))
* = λnmf.(m (n f))
- = λmn.(n -1 m)
^ = λnm.(m n)
↑↑ = λmn.((-1 n) (^ m) m)

# Pairs: x=first, y= second, h=head, t=tail
pair = λxyf.(f x y)
nil = false
fst = λl.(l λhtd.h nil)
snd = λl.(l λhtd.t nil)
is_nill = λl.(l λhtd.false true)

# Recursion with Y-combinator
u = λxy.(y (x x y))
Y = (u u)

# Factorial
if_0 = λn.((n λa.false) true)
! = (Y λfn.(if_0 n 1 (* n (f (-1 n)))))

# List processing
rfold = λfa.(Y (λrl.(l λhtd.(f (r t) h) a)))
map = λf.(rfold (λah.(pair (f h) a)) nil)
[1,2,3] = (pair 1 (pair 2 (pair 3 nil)))

See also wikipedia page

Examples

Using the definitions in the "standard library", following expression can be calculated. Note, copy-paste only one expression after in statement at a time.

# 1 + 1 = 2
(+ 1 1)

# 2 * 4 = 8
(* 2 4)

# 2^2^2 = 16
(↑↑ 2 3)

# 3! = 3 * 2 * 1 = 6
(! 3)

# 1^2 + 2^2 + 3^2 = 14
(rfold + 0 (map (^ 2) [1,2,3]))

You may notice that there is no real need for numbers larger than 4, as your computer is throttling anyways. Many operations, especially the -1, are extremely inefficient requiring ridiculous amount of β-reduction cycles. Any meaningful programs are thus infeasible with this tool.