blob: 330bc9faa8e1327e1f48a6370cfdba4f338018ad (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
# Compilation
Bruijn can be compiled to John Tromp's binary lambda calculus (BLC).
BLC uses the following encoding:
| term | lambda | bruijn | BLC |
|:-------------|:-------|:--------|:-----------------|
| abstraction | λM | `[M]` | 00M |
| application | (MN) | `(M N)` | 01MN |
| bruijn index | i | `i` | 1<sup>i+1</sup>0 |
There are two modes of compilation:
- **Bitwise** compiles to BLC and encodes every bit as 1 bit and pads
the last remaining byte: `bruijn -b path`
- **ASCII** compiles to BLC and encodes every bit as 1 ASCII character
(`'0'`/`'1'`): `bruijn -B path`
## Compilation overhead
Typical compilation to BLC results in much redundant code, since every
used function gets substituted and translated separately. In
`((+3) + (+4) + (+3))`{.bruijn}, for example, `add`{.bruijn} gets
compiled to BLC two times, resulting in a redundant overhead of around
3500 bits.
This is because BLC was never intended for compilation of normal
programs, but mainly as an academic encoding model. This also means that
it's quite good for writing very expressive and minimal programs
(i.e. obfuscated code golfing, see [John Tromp's
IOCCC](https://ioccc.org/2012/tromp/hint.html)).
Most programs, however, won't be golfed and can result in rather large
compiled programs. While there's not really any practical need for
compilation aside from golfing, you could still use the
[BLoC](https://github.com/marvinborner/bloc) project to optimize
redundant terms.
Typical workflow:
``` bash
$ bruijn -B program.bruijn | bloc --from-blc -i - -o out.bloc
$ cat input | bruijn -E <(bloc --from-bloc -i out.bloc)
```
|
