Дзен миниатюризации
Отобрал для вас несколько удивительных проектов, способных расширить границы воображения программиста, сильно загаженного современными жирными фреймворками и кривыми решениями.
Сегодня рассказ пойдет о компиляторах — тех самых «страшных штуках», которые используют программисты для создания программ.
Как и все в современном ИТ-мире, современные компиляторы — жирные, страшные, кривые и косые у#бища, вынужденная работа (за деньги) с которыми давно уже не дает никаких положительных эмоций.
Поэтому проекты ниже — глоток свежего воздуха и бальзам на душу программистам, убивающим отстатки мозга об какой-нибудь Visual Studio и его замечательные ключи линковки.
Тестовое окружение
В этот раз я решил использовать не *BSD, а более обыденный Linux — в качестве тестового окружения использовалась Mageia Linux 9, gcc, clang и все стандартные утилиты для разработки: bison, yacc, binutils и так далее.
Minimal LISP Compiler
https://github.com/OpenProgger/LISP
Вся цепочка — от сборки до запуска этого проекта показана на заглавной картинке к статье:
This compiler translates a minimal set of LISP primitives to x86_64 assembly code. It requires a assembler/compiler that accepts intel syntax to create a executable.
Bootstrap-часть на Си в 290 строк:
clang compiler.c -o bootstrap
с помощью которой собирается основная часть на Lisp в 204 строки:
cat compiler.lisp | ./bootstrap > output.S
Дальше этот код с помощью все того же clang собирается в запускаемый бинарник:
clang -static -nostartfiles -nodefaultlibs -masm=intel output.S runtime.S -o LISPC
Это и есть готовый к использованию компилятор Lisp:
В качестве проверки, можно собрать Lisp-часть компилятора с помощью его самого:
cat compiler.lisp | ./LISPC > output.S clang -static -nostartfiles -nodefaultlibs -masm=intel output.S runtime.S -o LISPC
Два исходных файла, три команды сборки и у вас свой собственный компилятор Lisp!
lust: Lua in Rust
https://github.com/eatonphil/lust/tree/main
Парсер, компилятор и рантайм (виртуальная машина) для Lua:
This project implements a parser, compiler, and virtual machine evaluator for a minimal subset of Lua. It is written from scratch in Rust.
Четыре исходных файла на Rust, общим объемом меньше 1Кб собираются одной командой:
cargo build --release
Готовый компилятор будет находиться в каталоге target/release:
Вот так выглядит тестовый код, запущенный выше:
function fib(n)
if n < 2 then
return n;
end
local n1 = fib(n-1);
local n2 = fib(n-2);
return n1 + n2;
end
print(fib(30));Игрушка разумеется, но интересная и при желании превращаемая в полноценный проект.
A compiler for a subset of Haskell to Combinatory Logic
https://github.com/siraben/mini-haskell
This is an elaboration and annotation of Ben Lynn's Haskell compiler and C VM.
но я бы использовал термин abomination, как более отражающий суть.
Еще в описании забыли упомянуть, что оба проекта выше — от одного и того же поехавшего автора, а оригинальный компилятор от дядюшки Бена — победитель 26го IOCC за 2019й год.
Читабельная версия (с комментариями и форматированием) компилятора на Си занимает 427 строк, а код оригинала-победителя я приведу целиком:
#define x 0/**/
char*v,*y="33Yb59@&iBFApt;[[h3V19\\3<:4cJ!U 2eT18pC,Qqik4J:sh?HUXMrR(-l0R\"!eKZcI!@E(@B,C/*!aogn5LbK/e=2CmReb+6,]kD!iOC9DEOC9Dc1EV6976c?&s)Be;P;E^tl2eUYkg*#Yf:6^d[Mg_P;VGCr823^L_<X+j2,%nD20Ls lmpi&I(*hV=+p aTO`r.b1<i[/R\\t1,KBt)\\%;\\@27H>^#d6B!tb-on27d%i_OS5(W5eV-=M14kYO);Fe7k!N41<iX*T,kHW,&)_l&L)'0:Jj%j7^h+JU /9pZn&Td:&T%'TE<7>LW%m/R\\rON3-=G]^akjT778YCJ7B8e-5E#RX R=Ig8#/pDdAI;=a[ ISbp't+ZLJ;lUO71C)b5[Y)qTWmFJ)G1ehmS<.`n3RnE IG+G_A`CE=?hZU)bScgt7R3GNs+V(HQLL_R)n4;]#cUR.p>5!^4T3pQg^o//WLATCE18mSUme[Q<53e:')Q_%<L$1lKOnFD(R3%*jj85VW+#8Wt*Ud,1D7AKcdh<9r%igC$2</HD7X$K_0Rr/>L.*D2%;[0B+#8UANT1.tSd/^@Lamp;a6^g@jYNMC7O<rPWO5AfA;C'9WnLn9E:0d:R\\hAZ^m=/09d.R$Jd%:Gp hB-g4&N!VO)$;iED1:F`^`UrnWCSZ!L$Tdma!_hn7H0F$^MT(-Ln9F_Ljfp9*h8Er!<.g.h_7@b0l03?a+]`=dIoY>WCKOk&#[9FCQ#WFoga(tK<[PG6@5k2KY\\ oW':M;e//kd\"[l,_V?UlZ,m(Hh?O81mhM!G18 ]7m?X7e^[7EZYj[;kR,YXD\\X,!k6.HF8Z(V^^nBYea^NIL:]lG0(/\\Ik<m`>jPam;F-A,(tVN+bG@<L'J 1D8dE*hN87:TsccSKVE7KP+k8^5qZIkJG_fH_$MS--5(!*St/1:b+g8(/*",*T,*n=" $6I7H#v Jw\t{\v}\f;\t \v }\f }\f \f \f \v }\f \v\t } }\t ;\f }\f \f\t {\f\v } \f\t }\f ;\t \f\f \t\t {\f {\v\v \t \v\v\v \f }\v\v } }\v\v \f\v\v \f\v\v ;\v\v \v ;\v\v \t\v\v }\v\v \v\t ;\v\v \t\v\v }\v\v }\v\v ;\f }\t }\t }\v\v ;\f }\t \f\f \v\t \f\f \t\v\v }\v\v ;\v\v \t\v\v }\v\v {\t \f\f \f\v\v \t\v\v }\t ;\f }\f }\v\v \t\v\v ; \f\f ;\f }\f \t\f }\f ;\v\v \f\v\v {\t }\f \f\v\v \v {\f\v }\v\v ;\v\v }\f {\f\v ;\t {\f\v \f\v\v ;\t {\f\v \f\t }\f \v ;\v\v ;\v\v ;\t\v {\v\v {\f\v }\f\v }\v\v \t\f\v ;\v\v \t\v\v ;\v\v {\f\v \t\v\v } \f\v\v \f\f\v {\v} \f\v\v }\v\v \v\v} }\f \f\f {\t\v ;\f \f\f \v {\t \f\f \t\f ;\f } {\t \t\f } }\f \v\f} }\t \f \f \f\f ;\v} ;\t \f\t }\f }\t }\t\v \f\v} }\f} }\f \v\f} \f\t }\t {\f} :!#$%&*+./<=>?@\\^|-~\t\t\t \v\v\v \f\t \n\t\v\f} {\v\v {\v\v \f\f }\f --\t\t\t \f\t ;\f} ;\f \v\t ;\f }\f \v\t }\f \f\t \v\f\v ;\v\v {\f\v {\f\v \v\f\v } }\v\v \f\v\v }\f {\f\v \v\f} \t\v\v ;\v\v \t\t }\v\t \t\v\v \v\v\v \\'\"\t\t\f} {\f\v ;\f \t\t }\v{\f \v\v\v }\t} }\v\v \v\v\v \t\f} ;\v\f \v\f} }\f} \f\f\v \f\v\f }\f} }\f :\t\f\v} \v\t \v\v\v }\f }\t }\f \v\v\t \f\v\t }\f\v \v\f\v {\f\t \f\t{\f \v\f\v ;\f\f \v\v\t \f\v\f \t\v\t of\t\v\v\v ;\t\v \f\t\v } \f\f {\t\v }\t\v }\t\v \f\f \f\t }\f\v \f\v} {\f\v \t\v\f \f\f }\f \f\v\v ;\t\v \t\v\v \v\t {\f\t {\f\t }\f }\t ;\v} \t\v} {\v} ;\f }\f \f\f }\t\f \t\v\f }\v} \f\v} \f\v\f \f\f \v\v\v ;\t }\f} \t\v\v \t\f\v {\t ->\t\v\v\v \f\t{\f \t\t{\f \t\v\f \v\f\v \v\t\v ;\t \f\v} ;\t \f\f} }\f} \f\v; \t\f} \v\f\v \t\f\f }\t \f\f} }\f} \v\t \t\v} \t\t {\f} \t\f\v \v\f\f \f\f} \v\v; }\f\f \t\v} }\f} }\f} }\f} {\f\v }\v} \f\v} \f\v} ;\f\v \f\v} \v\f\v {\f\v }\v} ;\t\v ;\t\v {\f} ;\f\v ;\t\v \f\f} ;\f\f \f\f} }\v; {\t} {\f \t ;\f ; \v\t\v \t\v} \f\f\v }\f} }\f} }\f} }\f} ;\f} \f\f} \f\v; }\f\f {\t\f {\v} ;\f let\t;\f in\t\t\f }\f ;\f} \f\f} \v\v; }\f\f } {\v} ;\f case\t;\f }\v\v \t\f \v\f} \v\t ;\f} \f\f} }\t {\f} {\v\v \v\f} {\t ;\f} \f\f} \f\v; {\t\f {\v} {\t\v }\v\t {\t \f\f ;\t }\f} }\f} \f\f} }\f\v \t\t \t\f} ;\f} \f\f} ;\f} \f\f} }\f\f }\f\f \t\t} \f\f\f \t\t \v\t \t\v; \f\v; \t\v; \t \v } {\f; {\f; {\f; } \t } } \f\v; } }\f\f \v \f\v; } \v {\f ;\v\v {\f; } } \v\f; {\f; }\f; } }\f; \v }\f; \v \f\f }\f; \f\f \v\f; }\v; ;\v; \f\f }\f; ;\f \t ;\t }\f; } }\f ;\f} \f\v\v : <= * + - /\t}\f; {\f\v }\f \t\f} {\v} \v\t} \v\f; }\f\f \f\t\v {\t} \t\f} ;\f\v }\t data\t\v\f\f \v\t \v\t} \v\v; }\f; ;\t} {\v\v {\f; \v\t\f {\t\f \v\t\f }\f\f \v\v; ;\v; \f\t\v }\t} \v\t} }\f; \v\v\v \v\t} ;\f } ;\f} {\t} {\t} }\v\v \v\t }\f\v \v\t ;\v\v ;\t{\f \v\t} } {\t \v }\t} \v\t} {\f; \t\f ;\f} }\t} \v\t} {\t\f {\t\v \f\v\v \t\f \t\v\f ;\f; #define x \\";
#include <stdio.h>
typedef unsigned P;
enum{ L=1<<26} ;
P I,C,K=24,M,E
,j[L]={ x},*D=j+L/2,*i=j+L-3;
P w(P _){ return j[_[i]+1]; }
#define X(f,b,y,d) void f(){ D=j+b[i]; *D=y; *++D=d; i+=b; }
X(A,1,w(1),i[1])X(a,2,w(2),w(1))P l(P _,P E){ j[K++]=_; K++[j]=E; return K-2; }
int S;
X(t,1,9,(S=getchar())<0?8:l(l(17,l(1,S)),l(7,0)))P U(P _){ return j[w(_)+1]; }
X(_,2,9,U(1)>U(2)?l(8,9):8)X(b,2,w(2),i[1])P G(P _,P S){ return l(w(_),w(S)); }
#define B(f,o) X(f,2,1,U(1)o U(2))
B(p,*)X(c,3,w(1),G(2,3))X(u,3,G(1,3),w(2))P N(P l,P L,P _){
I=0;
while(*T-I[v])I++;
T++;
return I/6?l:N(l+I/_*L,L*6/_,3-_);
}
X(s,3,G(2,3),w(1))X(m,4,G(4,1),w(2))B(o,-)X(f,3,G(1,3),G(2,3))P Z(){
P _=*T++;
return _-9?l(l(17,l(1,_)),Z()):8;
}
X(d,2,w(1),w(2))X(R,2,l(w(2),printf(E?"%c":"%u,",U(1))),l(23,9))P W(P _){
if(S--); else{ M=0; C=5; while(C--)M=85*M+*y++-32; S=31; }
I=_*2+!!(M&1<<S);
for(_=0; (C=_[n]-9)&&C-I-23; _++);
return C?_?--_<2?C=N(0,1,1),_?l(_,C):C?C<8?C+15:7[D-C]:Z():_:(_=W(0),l(_,W(0))):W(I);
}
B(g,/)B(r,+)X(e,2,9,w(1))X(O,2,w(2),l(w(1),M-8))int main(){
v=12+n;
if(E=*j,E){
D=j+2;
K=E;
} else{
T=v+7;
while((*D=W(0)))D++;
puts(T);
}
*i=l(l(l(*--D,l(7,0)),0),l(23,9));
while(M=*i,M)M<24?(void(*[])()){
O,b,f,u,s,c,a,t,e,d,_,p,r,o,g,R,A,m
} [M*(M<18)](),7:(*--i=M[j]); return E||puts(y); }Можете использовать в качестве заклинания, для призыва темных сил.
Сборка и запуск работают до сих пор:
curl https://www.ioccc.org/2019/2019.tar.bz2 | tar xj cd 2019/lynn make
MinimalCC
https://github.com/been-jamming/MinimalCC
Сие есть одна из множества реализаций минимального компилятора С, которых на свете много.
Minimal C subset compiler. Currently compiles to MIPS assembly which runs on MARS and SPIM.
Ну как пройти мимо такой прелести?
Исходного кода достаточно много (целых 10 файлов), вот так выглядит вся цепочка — от сборки до запуска тестового приложения:
spim это очень старый и известный симулятор MIPS, можно взять отсюда.
Приседания с cat нужны для приделывания стандартного заголовка, обеспечивающего запуск.
minigo
https://github.com/d0iasm/minigo
Следующий шедевр миниатюризации — игрушечный компилятор Golang!
Minimum Go compiler that aims to do self-hosting. Its grammar is based on the official specification (https://golang.org/ref/spec), but it only supports parts of them.
Шесть исходных файлов на Go и компилятор ваш, но разумеется реализована далеко не вся спецификация а лишь небольшая часть.
Calculate a fibonacci funcion (88baba9, 08/27/2019)
до окончательной победы еще далеко.
В корне проекта лежит скрипт test.sh, который отвечает и за сборку и за тесты, вот так это выглядит в работе:
Я немного поправил скрипт сборки, добавив ключ:
-z noexecstack
в вызов gcc при линковке, чтобы консоль не засиралась ненужными предупреждениями.
minischeme
https://github.com/catseye/minischeme
Следующий интересный проект на тему миниатюрных радостей программиста:
This is Cat's Eye Technologies' fork of the original Mini-Scheme implementation, miniscm, by Atsushi Moriwaki. The original README can be found below, following the first line of equals signs in this file.
Самый настоящий компилятор языка Scheme, умещенный в ~2400 строк кода на Си.
У проекта нех#евая такая борода, уходящая корнями в далекое прошлое:
Version 0.85k4 (17 May 1994) Version 0.85k3 (30 Nov 1989) Version 0.85k2 (28 Nov 1989) Version 0.85k1 (14 Nov 1989)
Вот так это выглядит в работе:
jonesforth
https://github.com/nornagon/jonesforth/tree/master
Следующий исторический проект на тему «угара миниатюризации», тоже с большой бородой:
A few years ago I wrote a literate FORTH compiler and tutorial called JONESFORTH. It’s a good way, I think, to understand the power and limitations of FORTH, and a good way to learn a completely different and mind-blowing programming language.
If you’ve not heard of FORTH before, cogitate on this: It is possible to write a FORTH program in 2,000 lines. A program which will boot and provide an entire development environment (inc. editor, compiler etc) on bare hardware.
К сожалению ссылки на оригинальную статью устарели, копии найти не удалось а сайт автора лежит.
Репозиторий на Github это копия:
This is a mirror of Richard WM Jones's excellent literate x86 assembly implementation of Forth, more on which here: http://rwmj.wordpress.com/2010/08/07/jonesforth-git-repository/
Но все до сих пор отлично работает, вся цепочка выглядит вот так:
Да, если вы еще не заметили, этот компилятор написан целиком на ассемблере!
Minimal Lambda Calculus Compiler
https://github.com/OpenProgger/LC
Компилятор лямбда-выражений, от того же автора что создал MiniLisp.
Supports only single char symbols, except 'l' which stands for a lambda function. '+' is used as unchirchifier function to make some simple calculations.
Выражения выглядят примерно так:
((((l (f) (f (l (f) (l (z) (f (f (f (f (f z)))))))))
(((l (y) (l (F) (F (l (x) (((y y) F) x)))))
(l (y) (l (F) (F (l (x) (((y y) F) x))))))
(l (f)
(l (n)
((((((l (n)
((n (l (_) (l (t) (l (f) (f (l (v) v))))))
(l (t) (l (f) (t (l (v) v))))))
(((l (n)
(l (m)
((m
(l (n)
(l (f)
(l (z)
(((n (l (g) (l (h) (h (g f)))))
(l (u) z))
(l (u) u))))))
n)))
n)
(l (f) (l (z) z))))
(l (_)
((l (n)
((n (l (_) (l (t) (l (f) (f (l (v) v))))))
(l (t) (l (f) (t (l (v) v))))))
(((l (n)
(l (m)
((m
(l (n)
(l (f)
(l (z)
(((n (l (g) (l (h) (h (g f)))))
(l (u) z))
(l (u) u))))))
n)))
(l (f) (l (z) z)))
n))))
(l (_) (l (t) (l (f) (f (l (v) v))))))
(l (_) (l (f) (l (z) (f z)))))
(l (_)
(((l (n) (l (m) (l (f) (l (z) ((m (n f)) z))))) n)
(f
(((l (n)
(l (m)
((m
(l (n)
(l (f)
(l (z)
(((n (l (g) (l (h) (h (g f)))))
(l (u) z))
(l (u) u))))))
n)))
n)
(l (f) (l (z) (f z)))))))))))) (l (n) (+ n))) 0)Написан на С и чистом ассемблере, меньше 500 строчек кода с комментариями, вот так выглядит вся цепочка от сборки до запуска:
Одной строкой
Таких проектов очень и очень много, посмотреть их все не хватит никаких сил и времени.
Поэтому буквально одной строкой по каждому найденному интересному проекту.
mini-js
https://github.com/maierfelix/mini-js
Компилятор для Javascript, реализованный на самом Javascript(то что называется self-hosted):
Minimal self-hosted JavaScript compiler in 1k lines of code
Собирается с помощью.. node.js (!)
PICKLE
https://github.com/howerj/pickle/
Очень интересный проект, реализующий интерпретатор языка TCL в ~4Kb кода на Си.
A Small and Embeddable TCL like interpreter and library
Tiny TCL
https://github.com/rcornwell/TinyTcl
Более продвинутая версия интепретатора TCL, реализованная на Go:
Tiny Tcl is a Go version of TCL based on picilo, however this version has been expanded to include many standard TCl operators. This is a pure interpreter, and supports only integer math. It is designed so that it can be embedded into an application. It can also easily be expanded to include new features. There is a sample of how an interpreter could be setup in main.go.
tiny-tiny-pascal
https://github.com/andvarfolomeev/tiny-tiny-pascal
Мини-компилятор для старого доброго Паскаля, написанный на старом добром C++ ... студентом (!)
Разработчик: студент ДВФУ группы Б9120-09.03.03пикд Варфоломеев Андрей
Minimal Java Compiler
https://github.com/kkmanos/minimal-java-compiler
Замечательный и интересный проект, который у меня к сожалению так и не заработал:
A full-blown compiler implementation for a subset of the Java language.