BLoCade

BLoC is a file format for shared binary lambda calculus (BLC).

BLoCade, the BLoC-aid, turns BLoC files back into executable files (targets). This is useful for bruijn (see wiki), benchmarking, or general term optimization.

Targets

• BLC (sharing by abstraction): Terms having BLoC entry indices get abstracted and applied to the respective term. The indices get converted to De Bruijn indices. The dependency graph is resolved by a topological sort. Flag bblc (bits) and blc (ASCII 0/1).
• BLC (unshared): Every BLoC entry gets reinserted into the original term. Do not use this if you want efficiency or small files. Flag unbblc (bits) and unblc (ASCII 0/1).
• Planned: “normal” programming languages

Benchmarks

Some deliberately unoptimized test cases from test/, evaluated using ./run and measured in bits (using bloc -m 10 ...):

| file | bloc | unbblc/orig | bblc | |:--------------|:-----|:------------|:------| | echo | 56 | 4 | 4 | | reverse | 248 | 172 | 172 | | churchadd1 | 296 | 390 | 159 | | churchadd2 | 368 | 433 | 207 | | churcharith | 560 | 1897 | 339 | | uni | 576 | 459 | 448 | | ternaryvarmod | 1248 | 2330 | 1824 | | collatz | 1904 | 2884 | 1986 | | ternaryadd | 2240 | 19422 | 2708 | | ternaryfac | 2792 | 9599 | 3091 | | aoc | 7480 | 50062 | 10861 |

Huge and convoluted programs like @woodrush’s lambda-8cc will not get smaller by compiling them to shared BLC. The many sharable terms get abstracted to so many levels that the (unary) BLC indices (in case of 8cc) can literally be 50 kilobit long. One solution would obviously be a BLC variant with binary indices, or just storing and interpreting such files in the BLoC format directly (which also uses binary reference indices). A better algorithm than standard topological sort for resolving the dependencies would also help.

8cc, measured in megabit:

| file | bloc | unbblc/orig | bblc | |:-----------|:-----|:------------|:--------| | lambda-8cc | 5.13 | 40.72 | 3267.88 |

Optimization

You can use BLoC’s minimum tree size deduplication parameter --min-size/-m to generate even smaller files. The optimize bash script tries to find the optimal parameter for your target file using a binary search.

For example, 8cc’s optimal parameter for the bblc target is -m 4587, only marginally reducing the original size:

| file | bloc | unbblc/orig | bblc | |:-----------|:-----|:------------|:------| | lambda-8cc | 5.8 | 40.72 | 40.65 |