Лямбда-исчисление в 397 байтах

Лямбда-исчисление — это язык программирования с единственным ключевым словом. Это асфальтовая топь Тьюринга, обнаруженная научным руководителем Тьюринга. В этом посте я расскажу о совершенно новой 397-байтной реализации двоичного лямбда-исчисления в виде Linux ELF для x86-64. Также в нём представлены удобно портируемый код на C и собранные двоичные файлы APE для других платформ.

SectorLambda реализует виртуальную машину Чёрча-Кривина-Тромпа с монадным вводом-выводом. В 397 байтах нам удалось реализовать сборку мусора, «ленивые» списки и хвостовую рекурсию. Интерпретатор извлекает самый младший бит из каждого байта stdin. Вывод состоит из байтов 0 и 1. Он 64-битный, однако смещение ограничено [0,255], поэтому программы не могут быть слишком большими. Поэтому это интересный инструмент для обучения, однако имеется 520-байтная версия для приложений более промышленного масштаба, обходящая многие подобные ограничения; впрочем, в ней нужно писать код ещё большей сложности.

-rwxr-xr-x 1 jart jart 397 Feb 27 12:15 blc
-rw-r--r-- 1 jart jart 17K Feb 27 12:15 blc.S

Виртуальную машину можно скомпилировать в Linux для Linux x64 следующим образом:

cc -c -o blc.o blc.S
ld.bfd -o blc blc.o -T flat.lds

Программа считывается из stdin, за которым следует его ввод. Вот простой туториал по использованию функции тождественности (λ 0), в двоичном лямбда-исчислении кодируемой как (00 10):

$ { printf 0010; printf 0101; } | ./blc; echo 0101

Если вы пользуетесь Mac, Windows, FreeBSD, NetBSD или OpenBSD, то можете вместо этого сделать следующее:

$ curl https://justine.lol/lambda/lambda.com >lambda.com $ chmod +x lambda.com $ { printf 0010; printf 0101; } | ./lambda.com; echo 0101

Почему это важно

Программы, написанные на двоичном лямбда-исчислении, невероятно малы. Например, метациклический интерпретатор занимает всего 232 бита. Если работать с 8-битной версией интерпретатора (Blc с заглавной буквы), использующей истинный binary wire format, то мы можем получить представление о том, насколько малы могут быть программы, целевой платформой которых является виртуальная машина.

$ curl https://justine.lol/lambda/uni.Blc >uni.Blc $ curl https://justine.lol/lambda/Blc >Blc $ chmod +x Blc $ { cat uni.Blc; printf ' '; printf 'hello world'; } | ./Blc; echo hello world $ ls -hal uni.Blc -rw-r--r-- 1 jart jart 43 Feb 17 21:24 uni.Blc

Это означает, что наша 521-байтная виртуальная машина достаточно выразительна, чтобы реализовать себя всего в 43 байтах, то есть в меньше чем одной десятой от своего размера! Также в качестве виртуальной машины она имеет возможности, которых не хватает JVM, хотя и меньше неё на шесть порядков величин. Что-то подобное может иметь практическое применение в форматах сжатия, которым нужен маленький busy beaver, способный создавать большие объёмы данных. Кроме того, это просто круто.

Например, если вы собрали инструмент для сжатия, с его помощью можно закодировать файл как генерирующее его лямбда-выражение. Так как сложно внедрять новый формат сжатия, который не установлен у большинства людей, можно создать префикс сжатого файла с этим 397-байтным интерпретатором, получив автономный самораспаковывающийся архив, которым может пользоваться каждый. Кроме того, двоичное лямбда-исчисление будет более логичным в качестве встроенного микропроцессора, чем LISP.

Компиляция

Программы кодируются в следующем формате:

 00      means abstraction   (pops in the Krivine machine) 01      means application   (push argument continuations) 1...0   means variable      (with varint de Bruijn index)

Можно использовать шелл-скрипты sed в качестве компилятора байт-кода. Ему достаточно делать s/λ/00/g, s/\[/01/g, s/[^01]//g и т. д.

 #!/bin/sh</span> tr \\n n |   sed '       s/;.*//       s/#.*//       s/1/⊤/g       s/0/⊥/g       s/λ/00/g       s/\[/01/g       s/9/11111111110/g       s/8/1111111110/g       s/7/111111110/g       s/6/11111110/g       s/5/1111110/g       s/4/111110/g       s/3/11110/g       s/2/1110/g       s/⊤/110/g       s/⊥/10/g       s/[^01]//g     '

Теперь мы можем писать более красивые программы:

{ printf %s "(λ 0)" | ./compile.sh   printf 00010101 } | ./blc

Программирование

Эта программа означает exit(0), потому что она возвращает $nil или []:

 λ λλ0

Эта программа возвращает [⊥,⊤] поэтому выводит 10.

λ [[$pair $false] [[$pair $true] $nil]]

Эта программа означает if (1 - 1 == 0) putc('1') else putc('0'):

λ [[[$if [$iszero [[$sub $one] $one]]]       [[$pair $false] $nil]]    [[$pair $true] $nil]]

Эта программа делает то же самое, что и программа ident, но написана более обстоятельно. Среда выполнения передаёт два аргумента, gro и put (или λ [[0 wr0] wr1]). Индекс 110 — это внешний параметр, а 10 — внутренний. То есть эта программа эквивалентна for (;;) putc(getc())

λλ [1 0] ││ │└binds `put` or `(λ 0 wr0 wr1)` [cited as 0] └binds `gro` or `⋯` [cited as 1]

Эта программа инвертирует поток битов при помощи Y-комбинатора. Её скорость обработки составляет аж целых 16 кБ/с.

# a.k.a. Y(λfi.i(λbjn.❬¬b,fj❭)⊥) [$Y λλ [[[$if 0] λλλ [[$pair [$not 2]] [4 1]]] $nil]]     ││           │││     ││           ││└consumes $nil terminator [uncited]     ││           │└binds ? input bit [cited as 1]     ││           └binds (λ 0 ? ⋯) [cited as 2]     │└binds gro (λ 0 ? ⋯) [cited by first 0]     └binds recursive function [cited as 4]

Если вам нужно объяснение происходящего, то вы можете воспользоваться интерпретатором lambda.com с флагом -r. Например, вот вышеприведённый код с пустым вводом. Вы можете наблюдать, как происходят разные действия, например, применение Y-комбинатора. Затем он считывает некий ввод, а затем использует бит ввода как предикат в условном операторе if. В отличие от LISP, лямбда-исчисление выполняет головную редукцию, поэтому можно считать, что блок вычислений лениво потребляет поток продолжений. Именно из-за всей этой парадигмы в языках наподобие Haskell не нужно так много скобок.

$ nil="λλ 0" $ true="λλ 1" $ false="λλ 0" $ pair="λλλ [[0 2] 1]" $ not="λ [[0 $false] $true]" $ Y="λ [λ [1 [0 0]] λ [1 [0 0]]]" $ printf %s "[$Y λλ [[0 λλλ [[$pair [$not 2]] [4 1]]] $nil]]" | ./compile.sh | ./lambda.com -r [Y λλ [[0 λλλ [[pair [¬ 2]] [4 1]]] ⊥]] λ [0 put] [[Y λλ [[0 λλλ [[pair [¬ 2]] [4 1]]] ⊥]] ⋯] 0 put Y λλ [[0 λλλ [[pair [¬ 2]] [4 1]]] ⊥] ⋯ put λ [1 [0 0]] λ [1 [0 0]] ⋯ put 1 [0 0] ⋯ put λλ [[0 λλλ [[pair [¬ 2]] [4 1]]] ⊥] [0 0] ⋯ put λ [[0 λλλ [[pair [¬ 2]] [4 1]]] ⊥] ⋯ put 0 λλλ [[pair [¬ 2]] [4 1]] ⊥ put ⋯ λλλ [[pair [¬ 2]] [4 1]] ⊥ put ⊥ λλλ [[pair [¬ 2]] [4 1]] ⊥ put λ 0 ⊥ put 0 put ⊥ put λ 0

Эта программа означает for x in reversed(stdin): put(x)

# a.k.a. λa.a(ω(λbcde.d(bb)(λf.fce)))⊥ λ [[0 [λ [0 0] λλλλ [[1 [3 3]] λ [[0 3] 1]]]] $nil]

Эта программа означает ['1'] * 4**3. Если вам нужно возвести в степень бОльшие числа, например, 9**3 (по стандартам ФП это big data), тогда вам потребуется изменить параметр STACK в blc.S так, чтобы попросить у операционной системы чего-то большего, чем предоставляется по умолчанию.

λ [[$Y λλ [[[$if [$iszero 0]]                 $nil]              [[$pair $false]               [1 [$dec 0]]]]]    [[$pow $four] $three]]

Вот написанный на BLC интерпретатор BLC размером 232 бита.

[[λ [0 0]   λλλ [[[0 λλλλ [2 λ [[4 [2 λ [[1 [2 λλ [2 λ [[0 1] 2]]]]                                [3 λ [3 λ [[2 0] [1 0]]]]]]]                       [[0 [1 λ [0 1]]]                        λ [[3 λ [3 λ [1 [0 3]]]] 4]]]]]         [2 2]] 1]]  λ [0 [λ [0 0] λ [0 0]]]]

Вот генератор кривой Пеано гильбертова пространства с использованием 8-битной версии:

$ curl https://justine.lol/lambda/hilbert.Blc >hilbert.Blc $ curl https://justine.lol/lambda/Blc >Blc $ chmod +x Blc $ { cat hilbert.Blc; printf 123; } | ./Blc  _   _   _   _ | |_| | | |_| | |_   _| |_   _|  _| |_____| |_ |  ___   ___  | |_|  _| |_  |_|  _  |_   _|  _ | |___| |___| |

Определения

Вот некоторые важные значения:

nil="λλ0" false="λλ0" true="λλ1"

Вот некоторые важные абстракции:

if="λ 0" omega="λ [0 0]" pair="λλλ [[0 2] 1]" car="λ [0 $true]" cdr="λ [0 $false]" or="λλ [[0 0] 1]" and="λλ [[0 1] 0]" not="λλλ [[2 0] 1]" xor="λλ [[1 λλ [[2 0] 1]] 0]" bitxor="λλ [[1 0] λλ [[2 0] 1]]" iszero="λλλ [[2 λ 1] 1]" Y="λ [λ [0 0] λ [1 [0 0]]]"

Вот целочисленные значения:

zero="λλ 0" one="λλ [1 0]" two="λλ [1 [1 0]]" three="λλ [1 [1 [1 0]]]" four="λλ [1 [1 [1 [1 0]]]]" five="λλ [1 [1 [1 [1 [1 0]]]]]" six="λλ [1 [1 [1 [1 [1 [1 0]]]]]]" seven="λλ [1 [1 [1 [1 [1 [1 [1 0]]]]]]]" eight="λλ [1 [1 [1 [1 [1 [1 [1 [1 0]]]]]]]]" nine="λλ [1 [1 [1 [1 [1 [1 [1 [1 [1 0]]]]]]]]]"

Вот арифметика:

pow="λλ [0 1]" mul="λλλ [2 [1 0]]" dec="λλλ [[[2 λλ [0 [1 3]]] λ 1] λ 0]" sub="λλ [[0 $dec] 1]" inc="λλλ [1 [[2 1] 0]]" add="λλλλ [[3 1] [[2 1] 0]]" fac="λλ [[[1 λλ [0 [1 λλ [[2 1] [1 0]]]]] λ1] λ0]" min="λλλλ [[[3 λλ [0 1]] λ1] [[2 λλ [3 [0 1]]] λ1]]" div="λλλλ [[[3 λλ [0 1]] λ 1] [[3 λ [[[3 λλ [0 1]] λ [3 [0 1]]] λ0]] 0]]" mod="λλλλ [[[3 $cdr] [[3 λ [[[3 λλλ [[0 [2 [5 1]]] 1]] λ1] 1]] λ1]] λλ0]"

Вот предикаты:

eq="λλ [[[[1 λ [[0 λ0] λ0]] [[0 λλλ [1 2]] λλ0]] λλλ0] λλ1]" le="λλ [[[1 λλ [0 1]] λλλ1] [[0 λλ [0 1]] λλλ0]]" lt="λλ [[[0 λλ [0 1]] λλλ0] [[1 λλ [0 1]] λλλ1]]" odd="λ [λ [0 0] λλ [[0 λλ 1] λ [[0 λλ 0] [2 2]]]]" divides="λλ [[[1 $cdr] [$omega λ[[[1 λλλ [[0 [2 λλ0]] 1]] λ[1 1]] λλ1]]] λλ0]"

Инструментарий

Вот как используется утилита blcdump:

$ printf 0010 | blcdump.com -l 2>/dev/null λa.a  # convert to traditional notation $ blcdump.com -l <invert.blc 2>/dev/null ω(λab.b(λcdef.f(c⊥⊤)(aad))⊥)  # convert to de Bruijn notation $ blcdump.com <invert.blc 2>/dev/null [ω λλ [[0 λλλλ [[0 [[3 ⊥] ⊤]] [[5 5] 2]]] ⊥]]  # convert Blc to blc $ blcdump.com -bB <uni.Blc 2>/dev/null 00011001010001101000000001010101100000000000010...  # create portable lambda expression $ blcdump.com -lnNS <invert.blc 2>/dev/null (\a.a a) (\a.(\b.(b (\c.(\d.(\e.(\f.(f(c (\g.(\h.h)) (\g.(\h.g)))(a a d)))))) (\c.(\d.d)))))

Вот как используется утилита lam2bin:

$ { printf 'λa.a' | lam2bin.com; printf 1010; } | blc 1010 $ { printf '\\a.a' | lam2bin.com; printf 1010; } | blc 1010 $ { printf 'ω(λab.b(λcdef.f(c⊥⊤)(aad))⊥)' | lam2bin.com; printf 1010; } | blc 0101

Вот как используется утилита asc2bin:

$ { printf 'λa.a' | lam2bin.com | asc2bin.com; echo hello; } | Blc hello

Среда выполнения

ВМ разворачивает программу при запуске следующим образом:

? ⟶ [λ [0 λ [[0 wr0] wr1]] [? ⋯]]

Условное обозначение ленивого списка редуцируется следующим образом:

⋯ ⟹ $nil                     ;; if eof / error ⋯ ⟹ λ [[0 $false] ⋯]         ;; if ~getc() & 1 ⋯ ⟹ λ [[0 $true] ⋯]          ;; if  getc() & 1

Условные обозначения wr0 и wr1 редуцируются следующим образом:

wr0 ⟹ λ [0 λ [[0 wr0] wr1]]  ;; w/ putc(0) side-effect wr1 ⟹ λ [0 λ [[0 wr0] wr1]]  ;; w/ putc(1) side-effect

8-битная среда выполнения (Blc с заглавной) разворачивается при помощи списков big-endian. Например, пробел (0b00100000) будет выглядеть так:

λ [[0 λ [[0 ⊤] λ [[0 ⊥] λ [[0 ⊥] λ [[0 ⊤] λ [[0 ⊥] λ [[0 ⊤] λ [[0 ⊤] λ [[0 ⊤] ⊥]]]]]]]]] ⋯]

Двоичные файлы

-rwxr-xr-x 1 jart jart 397 Feb 27 12:15 blc (только linux x86-64)
-rwxr-xr-x 1 jart jart 521 Feb 27 12:15 Blc (только linux x86-64)
-rwxr-xr-x 1 jart jart 20K Feb 28 12:11 tromp.com (ioccc 2012)
-rwxr-xr-x 1 jart jart 48K Feb 28 12:11 lambda.com (дружественный)
-rwxr-xr-x 1 jart jart 36K Feb 28 12:11 blcdump.com
-rwxr-xr-x 1 jart jart 40K Feb 28 12:11 bru2bin.com
-rwxr-xr-x 1 jart jart 40K Feb 28 12:11 lam2bin.com
-rwxr-xr-x 1 jart jart 20K Feb 28 12:11 asc2bin.com

Программы

-rw-r--r-- 1 jart jart 84 Feb 27 12:54 invert.blc
-rw-r--r-- 1 jart jart 167 Feb 27 12:52 primes.blc
-rw-r--r-- 1 jart jart 232 Feb 27 12:52 uni.blc
-rw-r--r-- 1 jart jart 43 Feb 27 12:52 uni.Blc
-rw-r--r-- 1 jart jart 67 Feb 27 12:52 reverse.blc
-rw-r--r-- 1 jart jart 9 Feb 27 12:52 reverse.Blc
-rw-r--r-- 1 jart jart 186 Feb 27 12:52 symbolic.Blc
-rw-r--r-- 1 jart jart 143 Feb 27 12:52 hilbert.Blc
-rw-r--r-- 1 jart jart 141 Feb 27 12:52 parse.Blc
-rw-r--r-- 1 jart jart 112 Feb 27 12:52 bf.Blc
-rw-r--r-- 1 jart jart 112 Feb 27 12:55 hw.bf

Скрипты

-rwxr-xr-x 1 jart jart 343 Feb 27 12:06 compile.sh
-rwxr-xr-x 1 jart jart 224 Feb 27 12:06 trace.sh
-rwxr-xr-x 1 jart jart 661 Feb 27 12:06 lam2sh.sh
-rwxr-xr-x 1 jart jart 573 Feb 27 12:06 lam2sqr.sh
-rwxr-xr-x 1 jart jart 565 Feb 27 12:06 sqr2lam.sh

Исходники

-rw-r--r-- 1 jart jart 17K Feb 27 12:15 blc.S
-rw-r--r-- 1 jart jart 12K Feb 24 17:25 Blc.S
-rw-r--r-- 1 jart jart 3.1K Feb 27 12:18 Makefile
-rw-r--r-- 1 jart jart 1023 Feb 27 12:03 tromp.c
-rw-r--r-- 1 jart jart 7.9K Feb 27 12:04 lambda.c
-rw-r--r-- 1 jart jart 3.1K Feb 27 12:05 asc2bin.c
-rw-r--r-- 1 jart jart 7.9K Feb 27 12:05 lam2bin.c
-rw-r--r-- 1 jart jart 8.3K Feb 27 12:05 bru2bin.c
-rw-r--r-- 1 jart jart 4.7K Feb 27 12:08 blcdump.c
-rw-r--r-- 1 jart jart 1.3K Feb 27 12:05 blc.h
-rw-r--r-- 1 jart jart 4.5K Feb 27 12:09 debug.c
-rw-r--r-- 1 jart jart 2.2K Feb 27 12:09 error.c
-rw-r--r-- 1 jart jart 2.4K Feb 27 12:09 getbit.c
-rw-r--r-- 1 jart jart 7.9K Feb 27 12:04 lambda.c
-rw-r--r-- 1 jart jart 1.8K Feb 27 12:10 needbit.c
-rw-r--r-- 1 jart jart 2.5K Feb 27 12:08 parse.c
-rw-r--r-- 1 jart jart 35K Feb 27 12:08 print.c
-rw-r--r-- 1 jart jart 1023 Feb 27 12:03 tromp.c
-rw-r--r-- 1 jart jart 2.5K Feb 27 12:10 vars.c
-rw-r--r-- 1 jart jart 2.1K Mar 1 09:11 flat.lds
-rw-r--r-- 1 jart jart 3.5K Mar 1 09:11 unflat.lds

Прозрачность DWARF

-rwxr-xr-x 1 jart jart 419K Feb 27 12:11 tromp.com.dbg
-rwxr-xr-x 1 jart jart 822K Feb 27 12:11 lambda.com.dbg
-rwxr-xr-x 1 jart jart 736K Feb 27 12:11 blcdump.com.dbg
-rwxr-xr-x 1 jart jart 663K Feb 27 12:11 bru2bin.com.dbg
-rwxr-xr-x 1 jart jart 677K Feb 27 12:11 lam2bin.com.dbg

Демо Blinkenlights

Вот скринкаст работающей SectorLambda в Blinkenlights. Программа вводится в консоль как функция тождества 0010, или (λ 0), или λ?.?. После ввода программы все дальнейшие нажатия клавиш будут выводиться echo на основании младшего бита.

В правом нижнем углу видны распределения кучи в стеке, увеличивающемся в процессе сборки его списка. В правом верхнем углу видно увеличивающееся по мере считывания ввода количество неизменяемых членов. Эти члены записываются непосредственно после исполняемого образа.

Схемы процедур

division

λabcd.a(λef.fe)(λe.d)(a(λe.b(λfg.gf)(λf.c(fe))(λf.f))d)

λλλλ [[[3 λλ [0 1]] λ 1] [[3 λ [[[3 λλ [0 1]] λ [3 [0 1]]] λ 0]] 0]]

0000000001010111110000001101100011001011111000010101111100000011 01100001111100110110001010

modulus

λabcd.a(λe.e(λfg.f))(a(λe.b(λfgh.h(f(cg))g)(λf.e)d)(λe.d))(λef.f)

λλλλ [[[3 λ [0 λλ 1]] [[3 λ [[[3 λλλ [[0 [2 [5 1]]] 1]] λ 1] 1]] λ 1]] λλ 0]

0000000001010111110000110000011001011111000010101111100000000101 100111100111111101101100011011000110000010

divides predicate

λab.a(λc.c(λde.d))((λc.cc)(λc.b(λdef.f(d(λgh.h))e)(λd.cc)(λde.d)))(λcd.d)

0000010101110000110000011001000110100001010111000000001011001111 000001011000011101100000110000010

binary lambda calculus interpreter

(λa.aa)(λabc.c(λdefg.e(λh.d(f(λi.h(g(λjk.i(λl.lkj)))(f(λj.g(λk.ik(jk))))))(h(g(λi.ih))(λi.f(λj.g(λk.j(kh)))e))))(aa)b)(λa.a((λb.bb)(λb.bb)))

0101000110100000000101011000000000011110000101111110011110000101 1100111100000011110000101101101110011111000011111000010111101001 1101001011001110000110110000101111100001111100001110011011110111 1100111101110110000110010001101000011010

binary lambda calculus interpreter w/ byte i/o

λa.a((λb.bb)(λb.(λcde.e(λfgh.g(λijk.(λl.f(c(λm.i(l(λno.m(λp.pon)))(c(λn.l(λo.mo(no)))))j)(i(l(λm.mi)j)(c(λm.l(λn.m(ni)))g)))d)(λi.i(λj.cd(λk.kfj))))(λf.f(cd)))(bb))(λbc.b((λd.dd)(λd.dd))))

0001100101000110100001000000010110000000010111000000001000101111 1111001011111111111000010111111001110000001111000010110110111001 1111111111100001111000010111101001110101110010111110010110000110 1111101110010111111111110000111000011100110111111011111101111111 1000011000010111111111011111110000101101111110110000110011111011 10011010000001110010001101000011010

Goldbach

(λa.a((λb.bb)(λbcd.(λef.ae(f(bbe)))(λe.eed(λf.fc)e))(λbcde.e)))((λa.aa)(λabc.c(λde.e)((λd.aad((λe.ee)(λe.d(ee))))(λd.(λe.e(e(bd)))(λefgh.hf(ge)))))(λabcd.d(λef.e)(ca)))

0100011001010001101000000001000001011111110110011001011111101111 1011000010101011010110000110111101000000000100101000110100000000 1011000001001000101011111011110100100011010000111001101000010001 1001100111110110000000000101101110011101111000000000010110000011 00111011110

Goodstein

λa.a(λbcd.b(λe.c(λfg.e(λhij.jh(if))(λh.g)(λhi.i)))(λef.de(d(λg.e(λhij.g(cdi(λkl.j(λm.mkl))(λkl.j(λm.kml))h)ij))f)))(λb.b)(λb.b(λcd.c)(λc.c))(λb.b(λcde.c))(λb.b)(λbc.b(λde.cd(de)))(λbc.b(λde.cd(d(de)))c)(λb.b)

0001010101010101011000000001011110000111100000010101111000000001 0110111001110111110001100000100000010111101100101111000011110000 0000101011111001010101011111111101111111011000000111100001011011 1011000000111100001011110101101110110101000100001011000001100010 0001100000001110001000000111000000101111011001110100000010111000 0001011110110011100111010100010

primes

λa.(λb.(λc.b(b((λd.dd)(λdef.f(λgh.h)((λg.ddg((λh.hh)(λh.g(hh))))(λghij.jh(i(eg)))))(λdef.b(fd))))((λde.d(d(de)))(ccc)(λdefg.ge(fd))(λdefg.g)))(λcd.c(cd)))(λbc.c(λde.d)b)

0001000100010111001110010100011010000000010110000010010001010111 1101111010010001101000011100110100000000001011011100111001111111 0111100000000111111001101110010101000001110011100111010010110101 0000000000101101110011101111000000000100000011100111010000001011 00000110110

sort

λa.(λb.bb)(λb.(λcde.e(λfg.(λh.hh)(λhi.i(λjkl.hhk(λm.j(λnopqrs.sm(n(λu.uoq)q)(nr(λu.uor)))(λnop.p(λqr.mq(λs.sqr))no)))(λj.(λk.jkkk)(λkl.l)))e(λhijk.(λl.h(d(λmn.n))(c(l(λmn.m))i(c(l(λmn.n))jk)))(λlm.d(λn.nlm)))))(bb))(λb.b)a(λbc.c)

0001010101000110100001000000011000000101010001101000000101100000 0001010111111011111011000010111110000000000000010101101111111001 0111111100001011011111101111011100101111111011000010110111111011 1000000001010110000001011111110110000101101110110111011000010001 0101110101010000010111000000000010001011111100111111111100000100 1010111111111110011000001101111001010111111111110011000001011101 1000000111111111110000101101110110011010001010000010

compliant brainf#*k interpreter

λa.(λb.a((λc.cc)(λc.(λd.(λe.(λf.(λg.(λh.g(f(h(f(h(f(h(h(e(b(λijk.ikj)))))(f(f(e(λijklm.m(λn.inkl)))(e(b(λi.i))))(g(e(λijklmn.nj(ijklm)))))))(h(h(f(g(e(λijkl.l(λm.im(λn.njk)))))(g(e(λijkl.ki(λm.mjl)))))))))(g(h(h(f(h(h(λij.jd(λk.e((λl.ll)(λlmn.n((λo.oo)(λopq.p(q(oo))(λr.k(llr))))mn))k))))(g(h(λijk.k(λl.l)j)))))))))(f(e(λh.h))))(λg.fg(e(λh.h))))(λfgh.h(λi.ifg)))(λefg.gd(λhij.j(λk.e(hk))i)))(cc)))(λc.(λd.dd)(λde.e((λf.f(f(f(λgh.h(λij.i)g))))(λfg.f(fg))(λfg.g))(dd))(c(λdefghi.i))c))(λbcd.c((λe.ee)(λefg.f(λhij.eei(λkl.g(λm.m(lh)k)(bhl(λm.m))))(gf(λhij.hji)))d(λef.e)))

0001000101110010001101000010001000100010001000111001011110011001 0111100110010111100110011001111100111111110000000010111101011001 0111100101111001111100000000000011000010101111111010111101110011 1110011111111000100111001111100000000000000101101111100101010111 1111011111011110111011001100110010111100111001111100000000001100 0010111111010000101101111101111001110011111000000000010111011110 0001011011110110011100110011001011110011001100000010110111111100 0010111111110010001101000000001010110010001101000000001011100110 0111101110000111111111001011111111011111110101101010011100110000 0000101100010110011100111100010000101110100111100010000000011000 0101101111011100000000101101111000000001011000011111111001111101 0110011010000101010001101000000101100101000110011001100000010110 0000110110000001110011101000001001110110011000000000000010100000 0001110010101000110100000000101110000000010101111111011111101100 0000101111111000010110011101111110111001010111111111111011111010 00100101101100000000101111010110100000110

Как это работает

#define IOP 0  // code for gro, wr0, wr1, put #define VAR 1  // code for variable lookup #define APP 2  // code for applications #define ABS 3  // code for abstractions #define REF(c) (++(c)->refs, c)  struct Parse {   int n;   int i; };  struct Closure {   struct Closure *next;   struct Closure *envp;   int refs;   int term; };  static const char kRom[] = {     APP, 0,  //  0 (λ 0 λ 0 (λ 0 wr0 wr1) put) (main gro)     ABS,     //  2 λ 0 λ 0 (λ 0 wr0 wr1) put     APP, 0,  //  3     VAR, 0,  //  5     ABS,     //  7     APP,     //  8     ABS,     //  9 λ 0 λ 0 wr0 wr1     APP, 2,  // 10     VAR,     // 12     IOP,     // 13     ABS,     // 14 λ 0 wr0 wr1     APP, 4,  // 15     APP, 1,  // 17     VAR,     // 19     IOP,     // 20 wr0     IOP, 0,  // 21 wr1 };  long ip;                // instruction pointer long end;               // end of code pointer int mem[TERMS];         // bss memory for terms struct Closure *frep;   // freed closures list struct Closure *contp;  // continuations stack struct Closure root = {.refs = 1}; struct Closure *envp = &root;  void Gc(struct Closure *p) {   for (; p && p != &root; p = p->envp) {     if (--p->refs) break;     Gc(p->next);     p->next = frep;     frep = p;   } }  void Var(void) {   int i, x;   struct Closure *t, *e;   e = t = envp;   x = mem[ip + 1];   for (i = 0; i < x && e != &root; ++i) e = e->next;   if (e == &root) Error(10 + x, "UNDEFINED VARIABLE %d", x);   ip = e->term;   envp = REF(e->envp);   Gc(t); }  void Gro(void) {   int c;   if ((c = fgetc(stdin)) != -1) {     mem[end++] = ABS;     mem[end++] = APP;     mem[end++] = 8;     mem[end++] = APP;     mem[end++] = 2;     mem[end++] = VAR;     mem[end++] = 0;     mem[end++] = ABS;     mem[end++] = ABS;     mem[end++] = VAR;     mem[end++] = ~c & 1;   } else {     mem[end++] = ABS;     mem[end++] = ABS;     mem[end++] = VAR;     mem[end++] = 0;   } }  void Put(void) {   fputc('0' + (ip & 1), stdout);   ip = 2; }  void Bye(void) {   int rc = mem[ip + 2];  // (λ 0) [exitcode]   if (rc) Error(rc, "CONTINUATIONS EXHAUSTED");   if (postdump && !rc) Dump(0, end, stderr);   exit(0); }  // pops continuation and pushes it to environment void Abs(void) {   if (!contp) Bye();   struct Closure *t = contp;   contp = t->next;   t->next = envp;   envp = t;   ++ip; }  struct Closure *Alloc(void) {   struct Closure *t;   if (!(t = frep)) {     if (!(t = calloc(1, sizeof(struct Closure)))) {       Error(6, "OUT OF HEAP");     }   }   frep = t->next;   t->refs = 1;   ++heap;   return t; }  // pushes continuation for argument void App(void) {   int x = mem[ip + 1];   struct Closure *t = Alloc();   t->term = ip + 2 + x;   t->envp = t->term > 21 && t->term != end ? REF(envp) : &root;   t->next = contp;   contp = t;   ip += 2; }  void Iop(void) {   if (ip == end) {     Gro();   } else {     Put();  // ip ∈ {6,13,20,21}   }   Gc(envp);   envp = &root; }  static void Rex(void) {   switch (mem[ip]) {     case VAR:       Var();       break;     case APP:       App();       break;     case ABS:       Abs();       break;     case IOP:       Iop();       break;     default:       Error(7, "CORRUPT TERM");   } }  char GetBit(FILE* f) {   int c;   if ((c = fgetc(f)) != -1) c &= 1;   return c; }  char NeedBit(FILE* f) {   char b = GetBit(f);   if (b == -1) Error(9, "UNEXPECTED EOF");   return b; }  struct Parse Parse(int ignored, FILE* f) {   int t, start;   char bit, need;   struct Parse p;   for (need = 0, start = end;;) {     if (end + 2 > TERMS) Error(5, "OUT OF TERMS");     if ((bit = GetBit(f)) == -1) {       if (!need) break;       Error(9, "UNFINISHED EXPRESSION");     } else if (bit) {       for (t = 0; NeedBit(f);) ++t;       mem[end++] = VAR;       mem[end++] = t;       break;     } else if (NeedBit(f)) {       t = end;       end += 2;       mem[t] = APP;       p = Parse(0, f);       mem[t + 1] = p.n;       need = 1;     } else {       mem[end++] = ABS;     }   }   p.i = start;   p.n = end - start;   return p; }  void LoadRom(void) {   long i;   for (; end < sizeof(kRom) / sizeof(*kRom); ++end) {     mem[end] = kRom[end];   }   mem[4] = 9;   mem[1] = end - 2; }  void Krivine(void) {   int main;   long gotoget;   LoadRom();   mem[end++] = APP;   gotoget = end++;   main = end;   mem[gotoget] = Parse(1, stdin).n;   for (;;) Rex(); }

Ассемблерный код

GAS LISTING o/blc.i page 1

GNU assembler version 2.34 (x86_64-alpine-linux-musl)  using BFD version (GNU Binutils) 2.34.  options passed: -aghlms=o/blc.lst  input file    : o/blc.i  output file   : o/blc.o  target        : x86_64-alpine-linux-musl  time stamp    : 2022-02-28T10:37:17.000-0800

GAS LISTING o/blc.i page 2

   1              /*-*- mode:unix-assembly; indent-tabs-mode:t; tab-width:8; coding:utf-8     -*-│    2              │vi: set et ft=asm ts=8 tw=8 fenc=utf-8                                     :vi│    3              ╞══════════════════════════════════════════════════════════════════════════════╡    4              │ Copyright 2022 Justine Alexandra Roberts Tunney                              │    5              │                                                                              │    6              │ Permission to use, copy, modify, and/or distribute this software for         │    7              │ any purpose with or without fee is hereby granted, provided that the         │    8              │ above copyright notice and this permission notice appear in all copies.      │    9              │                                                                              │   10              │ THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL                │   11              │ WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED                │   12              │ WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE             │   13              │ AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL         │   14              │ DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR        │   15              │ PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER               │   16              │ TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR             │   17              │ PERFORMANCE OF THIS SOFTWARE.                                                │   18              ╚─────────────────────────────────────────────────────────────────────────────*/   19                 20              #define TRACE   0// enable ./trace.sh support   21              #define FASTR   0// favor perf over tininess   22              #define TERMS5000000// number of words of bss   23              #define STACK0// bytes of stack to get   24                 25              #define IOP0// code for read, write0, write1, flush   26              #define VAR1// code for variable name lookup   27              #define APP2// code for applications   28              #define ABS3// code for abstractions   29                 30              #define NEXT0*8   31              #define ENVP1*8   32              #define REFS2*8+0   33              #define TERM2*8+4   34                 35              #define mem%rbx   36              #define memd%ebx   37              #define envp%rbp   38              #define contp%r9   39              #define frep%r8   40              #define eof%r13   41              #define eofb%r13b   42              #define eofd%r13d   43              #define idx%r15   44              #define idxb%r15b   45              #define idxd%r15d   46                 47              .macropushpop constexpr:req register:req   48              .byte0x6a,\constexpr   49              pop%r\register   50              .endm   51                 52              .macromxchg register:req memory:req   53              #if FASTR

GAS LISTING o/blc.i page 3

  54              mov\register,%rax   55              mov\memory,\register   56              mov%rax,\memory   57              #else   58              xchg\register,\memory   59              #endif   60              .endm   61                 62              .bss   63 0000 00000000 .zeroTERMS   63      00000000   63      00000000   63      00000000   63      00000000   64              .previous   65                 66 0000 7F454C46 ehdr:.ascii"\177ELF"   67                 68              ////////////////////////////////////////////////////////////////////////////////   69              //TWELVE BYTE OVERLAP#   70              //.byte2# EI_CLASS is ELFCLASS64   71              //.byte1# EI_DATA is ELFDATA2LSB   72              //.byte1# EI_VERSION is 1   73              //.byte3# EI_OSABI is ELFOSABI_LINUX   74              //.quad0#   75 0004 03       kRom1:.byteABS#  0       (λ ((0 (λ (λ ?))) ⋯))   76 0005 02       .byte  APP#  1       8   77 0006 08       .byte  8#──2──┐    -   78 0007 02       .byte    APP#  3  │    (0 (λ (λ ?)))   79 0008 02       .byte    2#──4────┐  (read (λ (λ ?)))   80 0009 01       .byte      VAR#  5  │ │  0   81 000a 00       .byte      0#  6  │ │  read   82 000b 03       .byte    ABS#──7────┘  (λ (λ ?))   83 000c 03       .byte      ABS#  8  │    (λ ?)   84 000d 01       .byte        VAR#  9  ┴    ?   85 000e 00       .byte0# exit(0) %al   86 000f 00       .byte0# elf padding                     [mark]   87              ////////////////////////////////////////////////////////////////////////////////   88                 89 0010 0200     ehdr2:.word2# e_type is ET_EXEC           [precious]   90 0012 3E00     .word62# e_machine is EM_X86_64      [precious]   91                 92              ////////////////////////////////////////////////////////////////////////////////   93              //FOUR BYTE OVERLAP#   94              //.long1# e_version is 1                  [mark]   95 0014 58       Bye2:pop%rax# __NR_exit   96 0015 0F05     syscall#   97 0017 00       .byte0# elf padding   98              ////////////////////////////////////////////////////////////////////////////////   99                100 0018 00000000 ehdr3:.quad_start# e_entry                     [precious]  100      00000000  101 0020 38000000 .quadphdrs - ehdr# e_phoff is 56               [precious]  101      00000000  102                103              ////////////////////////////////////////////////////////////////////////////////  104              //FOURTEEN BYTE OVERLAP#

GAS LISTING o/blc.i page 4

 105              //.quad0xc681c031# e_shoff  [should be 0]          [mark]  106              //.long0xfce2abac# e_flags  [should be 0]          [mark]  107              //.word0xc3# e_ehsize [should be 64]         [mark]  108 0028 57       Get:push%rdi#  109 0029 31C0     xor%eax,%eax# __NR_read  110 002b 31FF     xor%edi,%edi# stdin  111 002d 8D73FF   lea-1(mem),%esi# buf  112 0030 0F05     syscall#  113 0032 EB1C     jmpGet2#  114 0034 00       .byte0# elf padding  115 0035 00       .byte0# elf padding  116              ////////////////////////////////////////////////////////////////////////////////  117                118 0036 3800     .word56# e_phentsize                 [precious]  119                120              ////////////////////////////////////////////////////////////////////////////////  121              //EIGHT BYTE OVERLAP#  122              //.word1# e_phnum              [correct overlap]  123              //.word0# e_shentsize          [correct overlap]  124              //.word1|2|4# e_shnum              [p_flags clobber]  125              //.word0# e_shstrndx           [correct overlap]  126 0038 01000000 phdrs:.long1# p_type is PT_LOAD  127 003c 07000000 .long1|2|4# p_flags is PF_X|PF_W|PF_R  128              ////////////////////////////////////////////////////////////////////////////////  129                130 0040 00000000 .quad0# p_offset                    [precious]  130      00000000  131 0048 00000000 .quadehdr# p_vaddr                     [precious]  131      00000000  132                133              ////////////////////////////////////////////////////////////////////////////////  134              //EIGHT BYTE OVERLAP#  135              //.quadehdr# p_paddr                         [mark]  136 0050 2016     Get2:and%dl,(%rsi)# 1. al= 1 (si)='0' → ZF=1 CF=1 EAX=0  137 0052 2816     sub%dl,(%rsi)# 2. al= 1 (si)='1' → ZF=1 CF=0 EAX=0  138 0054 FFC8     dec%eax# 3. al= 0 (si)=??? → ZF=0 CF=? EAX<0  139 0056 5F       pop%rdi# 4. al=-1 (si)=??? → ZF=0 CF=? EAX<0  140 0057 C3       .Lret:ret#  141              ////////////////////////////////////////////////////////////////////////////////  142                143 0058 00000000 phdrs2:.quadfilesz# p_filesz         [insurmountable gulf]  143      00000000  144 0060 00000000 .quadmemsz# p_memsz          [insurmountable gulf]  144      00000000  145              //.quad4096# p_align  146                147 0068 97       Bye:xchg%edi,%eax  148 0069 C1EF10   shr$16,%edi  149 006c 6A3C     push$60# __NR_exit  150 006e EBA4     jmpBye2  151                152 0070 FF4810   Gc:declREFS(%rax)# unref memory (order matters)  153 0073 75E2     jnz.Lret# 1. free parents via recursion  154 0075 50       push%rax# 2. free self  155 0076 488B00   movNEXT(%rax),%rax# 3. free siblings via iteration  156 0079 E8F2FFFF callGc  156      FF

GAS LISTING o/blc.i page 5

 157 007e 58       pop%rax  158 007f 4C8900   movfrep,NEXT(%rax)  159 0082 4989C0   mov%rax,frep  160 0085 488B4008 movENVP(%rax),%rax  161 0089 EBE5     jmpGc  162                163 008b 57       Parse:push%rdi# save 1  164 008c B0       0:.byte0xB0# lda §movsb,%al (nop next byte)  165 008d A4       1:movsb# 00 is abstraction  166 008e 41FFD6   call*%r14# Get  167 0091 7314     jnc2f  168 0093 41FFD6   call*%r14# Get  169 0096 72F5     jc1b  170 0098 B002     1:mov$APP,%al# 01 is application  171 009a AA       stosb  172 009b 57       push%rdi# save 2  173 009c AE       scasb  174 009d E8E9FFFF callParse  174      FF  175 00a2 5E       pop%rsi# rest 2  176 00a3 8806     mov%al,(%rsi)  177 00a5 EBE5     jmp0b  178 00a7 B001     2:mov$VAR,%al# 1⋯ is variable  179 00a9 AA       stosb# 0-based de Bruijn indices  180 00aa F6D8     neg%al  181 00ac FEC0     3:inc%al  182 00ae 50       push%rax  183 00af 41FFD6   call*%r14# Get  184 00b2 58       pop%rax  185 00b3 73F7     jnc3b  186 00b5 AA       stosb  187 00b6 5E       pop%rsi# rest 1  188 00b7 89F8     mov%edi,%eax  189 00b9 29F0     sub%esi,%eax  190 00bb C3       ret  191                192 00bc 55       Var:pushenvp  193 00bd 3D       .byte0x3D# cmp §0x6D8B48,%eax (nop 4x)  194 00be 488B6D00 1:movNEXT(envp),envp  195 00c2 FFC9     dec%ecx  196 00c4 79F8     jns1b  197 00c6 448B7D14 2:movTERM(envp),idxd  198 00ca 488B6D08 movENVP(envp),envp  199 00ce FF4510   inclREFS(envp)  200 00d1 58       pop%rax  201 00d2 E899FFFF callGc  201      FF  202 00d7 EB41     jmpRex  203                204 00d9 4D85C9   Abs:testcontp,contp  205 00dc 748A     jzBye  206              mxchgenvp,NEXT(contp)  206              >  206              >  206              >  206              >  206              >

GAS LISTING o/blc.i page 6

 206 00de 498729   >  xchg %rbp,0*8(%r9)  206              >  207 00e1 4987E9   xchgenvp,contp  208 00e4 EB34     jmpRex  209                210 00e6 41FFD6   Gro:call*%r14# Get  211              pushpop10,cx  211 00e9 6A0A     >  .byte 0x6a,10  211 00eb 59       >  pop %rcx  212 00ec BE000000 mov$kRom1,%esi  212      00  213 00f1 7403      jz2f  214 00f3 83C607   add$7,%esi  215 00f6 B000     2:mov$0,%al  216 00f8 1400     adc$0,%al  217 00fa F3A4     rep movsb  218 00fc AA       stosb  219 00fd EB1B     jmpRex  220                221              _start:  222              #if STACK  223              mov$STACK,%rsi  224              mov$9,%al# __NR_mmap  225              mov$3,%dl# PROT_READ|PROT_WRITE  226              mov$0x0122,%r10w# MAP_PRIVATE|MAP_ANONYMOUS|MAP_GROWSDOWN  227              syscall  228              lea-24(%rax,%rsi),%rsp  229              mov$0,%dl  230              #endif  231 00ff BB000000 mov$kRom,memd# romz  231      00  232 0104 41BE0000 mov$Get,%r14d# saves two bytes  232      0000  233 010a 4889E5   mov%rsp,envp# prevent segfaults clobber argv[0]  234 010d FEC2     inc%dl# dx=1 for read() and write()  235 010f 8D7B16   .byte0x8d,0x7b,kEnd-kRom+1# lea kEnd-kRom+1(mem),%edi  236 0112 E874FFFF callParse# parse expr (xxx: tight displacement)  236      FF  237 0117 884315   .byte136,67,kEnd-kRom# mov %al,kEnd-kRom(mem)  238              //jmpRex# sets main() apply length  239                240 011a 428B043B Rex:mov(mem,idx),%eax# head normal form reduction  241 011e 0FB6CC   movzbl%ah,%ecx# %al should be ∈ {0,1,2,3}  242 0121 41FFC7   incidxd  243 0124 3C02     cmp$APP,%al  244 0126 77B1     jaAbs  245 0128 7423     jeApp  246 012a 84C0     test%al,%al  247 012c 758E     jnzVar  248              //jmpIop  249                250 012e 41FFCF   Iop:decidxd# lazy lists like haskell  251 0131 4183FF15 cmp$21,idxd# length of rom  252 0135 77AF     jaGro  253              //jmpPut  254                255 0137 89DE     Put:movmemd,%esi

GAS LISTING o/blc.i page 7

 256 0139 4183C71E add$30,idxd# 18,19 += 48,49 or '0','1'  257 013d 44883E   movidxb,(%rsi)  258 0140 41B707   mov$7,idxb# λ 0 λ 0 wr0 wr1  259 0143 57         push%rdi  260 0144 89D7     mov%edx,%edi# stdout  261 0146 89D0     mov%edx,%eax# __NR_write  262 0148 0F05     syscall  263 014a 5F       pop%rdi  264 014b EBCD     jmpRex  265                266 014d 4D85C0   App:testfrep,frep  267 0150 7508     jnz1f  268 0152 31C0     xor%eax,%eax  269 0154 50       push%rax# calloc() on stack lool  270 0155 50       push%rax  271 0156 50       push%rax  272 0157 4989E0   mov%rsp,frep  273 015a 41FFC7   1:incidxd  274              mxchgcontp,NEXT(frep)# get closure from free list  274              >  274              >  274              >  274              >  274              >  274 015d 4D8708   >  xchg %r9,0*8(%r8)  274              >  275 0160 4D87C8   xchgcontp,frep  276 0163 41FF4110 inclREFS(contp)# save machine state  277 0167 FF4510   inclREFS(envp)  278 016a 49896908 movenvp,ENVP(contp)  279 016e 4401F9   addidxd,%ecx  280 0171 41894914 mov%ecx,TERM(contp)  281 0175 EBA3     jmpRex  282                283 0177 00       buf:.byte0  284 0178 02       kRom:.byteAPP#  0         [λ [0 λ [[0 wr0] wr1]] [main ⋯]]  285 0179 12       .byte.Lloop-1f#──1─┐  286 017a 03       1:.byte  ABS#  2 │       λ [0 λ [[0 wr0] wr1]]  287 017b 02       .byte    APP#  3 │       [0 λ [[0 wr0] wr1]]  288 017c 07       .byte    .Lw01-1f#──4───┐  289 017d 0100     1:.byte      VAR,0#  5 │ │     0  290 017f 03       .L0w01:.byte    ABS#──7─┴─┘     λ [[0 wr0] wr1]  291 0180 02       .byte      APP#  8 │       [[0 wr0] wr1]  292 0181 04       .byte      4#─ 9───┐  293 0182 02       .byte        APP# 10 │ │     [0 wr0]  294 0183 01       .byte        1#─11─────┐   1  295 0184 01       .byte        VAR# 12 │ │ │   0  296 0185 00       .Lwr:.byte      IOP#─13─────┘   wr0  297 0186 00       .byte  IOP#─14───┘     wr1  298 0187 02       .Lloop:.byteAPP#─15─┘       [main ⋯]  299              kEnd:  300              

GAS LISTING o/blc.i page 8

 300              .globlehdr  301              .globl_start  302              .typekRom,@object  303              .typekRom1,@object  304              .typeehdr,@object  305              .typeehdr2,@object  306              .typeehdr3,@object  307              .typephdrs,@object  308              .typephdrs2,@object  309              .typebuf,@object  310              .weakfilesz  311              .weakmemsz

GAS LISTING o/blc.i page 9

DEFINED SYMBOLS                blc.S:66     .text:0000000000000000 ehdr                blc.S:75     .text:0000000000000004 kRom1                blc.S:89     .text:0000000000000010 ehdr2                blc.S:95     .text:0000000000000014 Bye2                blc.S:100    .text:0000000000000018 ehdr3                blc.S:221    .text:00000000000000ff _start                blc.S:126    .text:0000000000000038 phdrs                blc.S:108    .text:0000000000000028 Get                blc.S:136    .text:0000000000000050 Get2                blc.S:143    .text:0000000000000058 phdrs2                blc.S:147    .text:0000000000000068 Bye                blc.S:152    .text:0000000000000070 Gc                blc.S:163    .text:000000000000008b Parse                blc.S:192    .text:00000000000000bc Var                blc.S:240    .text:000000000000011a Rex                blc.S:204    .text:00000000000000d9 Abs                blc.S:210    .text:00000000000000e6 Gro                blc.S:284    .text:0000000000000178 kRom                blc.S:304    .text:000000000000018d kEnd                blc.S:266    .text:000000000000014d App                blc.S:250    .text:000000000000012e Iop                blc.S:255    .text:0000000000000137 Put                blc.S:283    .text:0000000000000177 buf  UNDEFINED SYMBOLS filesz memsz

Авторство

SectorLambda написан Жюстин Танни на основании криптограмм и обфусцированного кода, выпущенного Джоном Тромпом. Питер Ферье из Amazon внёс оптимизации размера.

Дополнительная информация

1. https://tromp.github.io/cl/Binary_lambda_calculus.html
2. https://www.ioccc.org/2012/tromp/hint.html
3. https://github.com/tromp/AIT