Lambdir
| Paradigm(s) | functional |
|---|---|
| Designed by | Ian Graham Martinez |
| Appeared in | 2026 |
| Computational class | Turing Complete |
| Reference implementation | Lambdir |
| Influenced by | Combinatory Logic |
| File extension(s) | N/A |
Lambdir is a language which inputs a program given in the form of a directory structure without any files (or variables). Lambdir is an extension of combinatory logic (using the SK basis) supporting Church Numerals (including addition, through a built-in + operator), the Y combinator, tuple/array constructors, and I/O (via $ & ! builtins). All execution is performed on the given directory itself, so that (almost) no memory allocations are performed at runtime. A more in-depth description of the language is available here.
Structure
Each folder is a combinator, either named as a primitive such as S, K, Y, +, or N5, or named as an integer (indicating argument position, in reverse order). As an example, S + (K 2) 2 would be encoded as:
├───0
│ └───N2
├───1
│ ├───0
│ │ └───N2
│ └───1
│ └───K
├───2
│ └───+
└───3
└───S
Note that these are names of directories, not files. The program's directory should contain no files at all.
Tuples/Arrays
There is a builtin T constructor which inputs the length of the tuple n, then n elements, and lastly an n-ary function to act on those elements. In short, T behaves as follows:
T 0 f = f T 1 a f = f a T 2 a b f = f a b T 3 a b c f = f a b c
I/O
Lambdir takes a monadic approach to I/O by providing the $ primitive for input, and the ! primitive for output, which behave as follows (where ~> means "reduces to"):
$ f ~> f n [where `n` is the next byte read from stdin] ! n f ~> f [which outputs byte `n` to stdout as a side effect]
This helps sequence reads & writes, so that, for example, the following two programs have the same behavior, despite appearing "backwards":
$ (S ! K) ! ($ I) K
Note that this does not make execution order totally unambigious. For example, ! '0' (! '1' K) has two redexes, and depending on which is reduced first, the output will either be 01 or 10. Because of this, for Lambdir to have well defined semantics, we must use a reduction strategy consistent with that of the reference implementation (which uses normal-order reduction, or leftmost-outermost reduction).
Example
A program to print the nth Fibonacci number (and reduce to K) is given below, though not as a directory, and using variables for readability. This can be easily converted to a directory, for example using this function from the reference implementation repository. Also, since Lambdir does not support explicit recursion, we can always expand out variables as needed.
I = S K K -- I x = x
B = S (K S) K -- B f g x = f (g x)
V = B (S I) K -- V x f = f x
-- [a, b] -> [b, a+b]
step = S -- "Distributes" [a,b] over the arguments
(B (T 2) (V (K I))) -- [a, b] -> T 2 b
(S (B + (V K)) (V (K I))) -- [a, b] -> a + b
-- n -> fib n
fib = S
(V step) -- n -> n step
(K (T 2 0 1)) -- n -> [0,1]
! ($ fib) K -- Read input & pass it to fib