Дзен миниатюризации27.02.2025 09:15

Отобрал для вас несколько удивительных проектов, способных расширить границы воображения программиста, сильно загаженного современными жирными фреймворками и кривыми решениями.

78a3c9c9a7dfaf31d0dba9094b6c98e0.png

Сегодня рассказ пойдет о компиляторах — тех самых «страшных штуках», которые используют программисты для своей сложной работы.

Как и большинство нынешнего ПО, современные компиляторы — жирные, страшные, кривые и косые чудовища, вынужденная работа (за деньги) с которыми давно уже не дает никаких положительных эмоций.

Поэтому проекты ниже — настоящий глоток свежего воздуха и бальзам на душу моим несчастным коллегам, убивающим отстатки мозга об какой-нибудь MSVC и его замечательные ошибки и ключи линковки.

Этой статьей я хочу показать, что бывает и по-другому:

все еще существуют компиляторы, которые не занимают на диске по паре гигабайт и не напоминают своим поведением 16-летнюю девушку.

Тестовое окружение

В этот раз решил использовать не стандартную (для автора) *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

формирует ассемлерный код:

587da59d0a88890e008e9a685c378fea.png

Дальше этот код с помощью все того же clang собирается в запускаемый бинарник: 

clang -static -nostartfiles -nodefaultlibs -masm=intel output.S runtime.S -o LISPC

Это и есть готовый к использованию компилятор Lisp:

34cc87b28c9812f4732e5830cd3adbf3.png

В качестве проверки, можно собрать 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:

e34357ac4a5f2a25fa2a52046f9fdc27.png

Вот так выглядит тестовый код, запущенный выше: 

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 го IOCCC за 2019й год.

Читабельная версия (с комментариями и форматированием) компилятора на С занимает 427 строк, а код оригинала-победителя IOCCC привожу целиком: 

#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_^#d6B!tb-on27d%i_OS5(W5eV-=M14kYO);Fe7k!N41LW%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.*D2%;[0B+#8UANT1.tSd/^@Lamp;a6^g@jYNMC7OWCKOk&#[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(/\\IkjPam;F-A,(tVN+bG@\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 
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<

Можете использовать в качестве заклинания для призыва темных сил, благо такой код будет отлично смотреться на страницах из выделанной кожи, будучи написанным чьей‑нибудь кровью.

Сборка и запуск работают до сих пор: 

curl https://www.ioccc.org/2019/2019.tar.bz2 | tar xj
cd 2019/lynn
make

Вот так выглядят тесты:

9fd72d30a8689cfc82754583c376a904.png

MinimalCC

https://github.com/been-jamming/MinimalCC

Одна из множества реализаций «минимального компилятора С», которых на свете очень много, поскольку задача создания такого компилятора является учебной и часто дается на профильных курсах, посвященных CS и компиляторам.

Но конкретно в этом есть нюанс:

Minimal C subset compiler. Currently compiles to MIPS assembly which runs on MARS and SPIM.

Ну как пройти мимо такой прелести?

Исходного кода достаточно много (целых 10 файлов), вот так выглядит вся цепочка — от сборки до запуска тестового приложения:

9bf464c4751f1d71c4d9c771ec4c4a06.png

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, который отвечает и за сборку и за тесты, вот так это выглядит в работе:

c850bc1c5deb548e788b0fe648b589df.png

Я немного поправил скрипт сборки, добавив ключ: 

-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)

Вот так это выглядит в работе:

0036629c5edf918979f8e9ec48646289.png

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/

Но все до сих пор отлично работает, цепочка от сборки до запуска выглядит так:

f78bcf8836afda62ba767e1baf7f5686.png

Да, если вы еще не заметили, этот компилятор написан целиком на ассемблере!

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 строчек кода с комментариями, а вот так выглядит вся цепочка от сборки до запуска:

b91eba0d8f978c1451fd57dfd038ad9f.png

Одной строкой

Интересных проектов на тему миниатюризации очень и очень много, посмотреть и тем более описать их все — не хватит никаких сил и времени.

Поэтому ниже буквально одной строкой по каждому найденному интересному проекту, просто чтобы вы о них тоже узнали.

mini-js

https://github.com/maierfelix/mini-js

Компилятор для Javascript, реализованный на самом Javascript:

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.

P.S.

Это цензурированная версия статьи, куда более фривольный оригинал как обычно доступен в нашем блоге.

0×08 Software

Мы небольшая команда ветеранов ИТ‑индустрии, создаем и дорабатываем самое разнообразное программное обеспечение, наш софт автоматизирует бизнес‑процессы на трех континентах, в самых разных отраслях и условиях.

Оживляем давно умершее,  чиним никогда не работавшее и создаем невозможное — затем рассказываем об этом в своих статьях.

© Habrahabr.ru