lambda 8cc
1.0.0
Lambda-8cc est un compilateur X86 C écrit comme un terme de calcul Lambda fermé monolithique fermé.
Lorsqu'il est imprimé sur du papier de la taille d'une lettre, il devient 18 506 pages de long sur un PDF de 22 Mo sans chiffres. Le PDF peut être vu sur mes pages GitHub ici. La source de latex est de 448 Mo et le fichier journal de compilation LaTeX main.log est de 284 Mo. Je ne pouvais pas croire que le latex a pu faire ça.
Ce gigantesque terme de calcul Lambda est un compilateur C. Voici ROT13.c, un programme qui compile sur GCC sans erreur. Le même programme peut être compilé à l'aide de lambda-8cc produisant l'exécutable x86 ROT13.BIN, Runnable sur x86 / x86-64 Linux:
$ echo ' Hello, world! ' | ./rot13.bin
Uryyb, jbeyq !
$ echo ' Uryyb, jbeyq! ' | ./rot13.bin
Hello, world !Malgré sa taille massive, la compilation de ROT13.c se termine en 8 minutes sur ma machine à l'aide d'un interprète de calcul lambda. Vous pouvez l'essayer sur votre propre PC en clonant ce dépôt. Les statistiques d'heure d'exécution sont résumées dans la section des temps de fonctionnement et de la mémoire. Notez que bien que la compilation prenne du temps, le binaire compilé fonctionne instantanément.
En tant que caractéristique supplémentaire, non seulement LAMBDA-8CC peut compiler C à x86, mais il peut également compiler C aux termes de calcul lambda, produisant quelque chose comme ROT13.lam. Les termes Lambda compilés fonctionnent sur le même interprète de calcul Lambda utilisé pour exécuter Lambda-8cc lui-même.
À l'aide de ses options de compilation, LAMBDA-8CC peut compiler C à 5 formats différents. Voici une liste complète de ses fonctionnalités:
Parmi la liste figure Lazy K, un langage purement fonctionnel minimal avec seulement 4 opérateurs intégrés, similaires au langage impératif minimal BF qui n'a que 8 instructions. J'en ai également couvert un peu dans mon article de blog.
Lambda-8cc est basé sur les 3 projets suivants: Le premier est Lambdavm écrit par l'auteur de ce repo Hikaru Ikuta, un processeur virtuel programmable écrit comme un terme de calcul Lambda non typlé. Ceci est combiné avec 8cc de Rui Ueyama et une version modifiée d'ELVM de Shinichiro Hamaji.
La première page du PDF ressemble à ceci. Remarquez le nombre de pages en haut à gauche:
Sa grande finale est une salve d'applaudissements d'une page pleine de bonnes parenthèses:
Lambda-8cc est écrit comme un terme de calcul Lambda non typlé fermé
Ici, même les cordes sont codées sous forme de termes lambda. Les caractères et les octets sont codés comme une liste de bits avec
Par conséquent, tout dans le processus de calcul, même y compris les entiers, est fermé dans le monde des termes de lambda purs, sans avoir besoin d'introduire un objet de type non Lambda. Il n'utilise aucun type primitif autre que les lambdas. Lambda-8cc fait de la réduction bêta la seule exigence pour compiler C à x86. Notez que le processus ne dépend pas également du choix des noms de variables. Au lieu d'encodage du caractère A en tant que variable avec le nom A est codé comme une liste de bits de son codage ASCII 01000001 .
Le processus d'encodage est un peu lourd à dire au moins à faire à la main. Cela peut être résolu en utilisant un interprète de calcul lambda. Divers interprètes de calcul Lambda gèrent automatiquement ce format d'E / S afin qu'il s'exécute sur le terminal - l'entrée standard est codée en termes lambda, et le terme Lambda de sortie est décodé et illustré sur le terminal. En utilisant ces interprètes, LAMBDA-8CC peut être exécuté sur le terminal pour compiler les programmes C, tout comme GCC.
Pour plus de détails sur la façon dont les E / S sont gérées et la façon dont les programmes sont écrits dans le calcul de Lambda, veuillez consulter les détails de mise en œuvre de mon autre projet LambdAlp, un interprète LISP écrit comme un terme de calcul Lambda non typé.
En plus de x86, Lambda-8cc peut également compiler C avec le calcul de lambda. Le programme de sortie s'exécute sur le même interprète de calcul lambda utilisé pour exécuter Lambda-8cc lui-même. Les termes Lambda compilés fonctionnent également sur des interprètes minimaux tels que l'interprète de calcul Lambda de 521 octets écrit Secteurlambda écrit par Justine Tunney, et l'interprète IOCCC 2012 "le plus fonctionnel" écrit par John Tromp (sa source est sous la forme d'un λ). Cela rend Lambda-8cc autonome dans le royaume du calcul de lambda.
Il est connu depuis longtemps en informatique que le calcul de lambda est Turing-Complete. Lambda-8cc le démontre de manière assez simple en montrant que les programmes C peuvent être directement compilés en termes de calcul lambda.
La bonne chose à propos du calcul de lambda est que les spécifications de langue sont extrêmement simples. Avec Lambda-8cc, nous préservons les connaissances sur la façon de compiler C dans une méthode intemporelle. Même si l'humanité perd des connaissances sur l'ensemble d'instructions x86, tant que nous nous souvenons des règles pour le calcul de lambda et que nous avons le terme lambda pour lambda-8cc, nous pouvons toujours utiliser la langue C entière via lambda-8cc et reconstituer tout dessus.
Voici un programme ROT13.c qui code / décode l'entrée standard vers / depuis le chiffre ROT13. Il compile sans erreurs en utilisant GCC:
// rot13.c: Encodes/decodes standard input to/from the ROT13 cipher
#define EOF -1
int putchar ( int c );
char getchar ( void );
char c ;
int offset ;
int main ( void ) {
for (;;) {
c = getchar ();
if ( c == EOF ) {
break ;
}
offset = 0 ;
if (( 'a' <= c && c < 'n' ) || ( 'A' <= c && c < 'N' )) {
offset = 13 ;
} else if (( 'n' <= c && c <= 'z' ) || ( 'N' <= c && c <= 'Z' )) {
offset = -13 ;
}
putchar ( c + offset );
}
return 0 ;
}Le même programme peut être compilé par Lambda-8cc de la boîte comme suit.
Construisez d'abord les outils et préparez Lambda-8cc:
$ make tools # Build the interpreter uni++ and the tools lam2bin, asc2bin
$ unzip bin/lambda-8cc.lam.zip
$ cat lambda-8cc.lam | bin/lam2bin | bin/asc2bin > lambda-8cc.Blc # Prepare format for uni++Les exigences sont:
clang++ pour construire uni++gcc ou cc pour construire lam2bin et asc2binLes outils construits ici sont:
uni++ : un interprète de calcul Lambda très rapide écrit par Melvin Zhang.lam2bin : Un utilitaire écrit par Justine Tunney (disponible sur https://justine.lol/lambda/), qui convertit la notation de calcul lambda en texte clair tel que xx en notation de calcul lambda binaire, le format accepté par Uni ++.asc2bin : Un utilitaire qui emballe le 0/1 ASCII BitsTtream en octets.Les outils sont construits via le kit de développement de calcul Lambda.
La conversion de lambda-8c.lam à lambda-8cc.blc est simplement une transformation de la notation pour un format accepté par l'interprète Uni ++. Les détails sont décrits en détail.
Ensuite, ROT13.C peut être compilé comme:
$ cat lambda-8cc.Blc examples/rot13.c | bin/uni++ -o > a.out
$ chmod 755 a.out
$ echo ' Hello, world! ' | ./a.out
Uryyb, jbeyq !
$ echo ' Uryyb, jbeyq! ' | ./a.out
Hello, world ! Cela dure environ 8 minutes sur ma machine. Mais soyez prudent - il faut 145 Go de mémoire pour l'exécuter! Si vous disposez d'un espace de stockage gratuit ou d'un lecteur USB, vous pouvez utiliser un fichier de swap avec mkswap et swapon pour étendre le swap sans configurer les paramètres de partition. De plus, en compilant séparément l'assemblage et x86, vous pouvez faire de deux deux fois l'utilisation de la RAM à 65 Go, comme indiqué dans la section d'utilisation détaillée. De petits programmes tels que putchar.c ne prennent qu'environ 40 Go de mémoire. Je soupçonne que l'utilisation de la RAM peut être diminuée en introduisant un GC Mark-and-Sweep à l'interprète, bien que je ne l'ai pas encore confirmé.
Plus de statistiques d'heure d'exécution sont disponibles dans la section des temps de fonctionnement et de la mémoire. Plus d'exemples C de programmes compilables par Lambda-8cc se trouvent sous. / Examples.
D'autres options de compilation sont décrites dans la section d'utilisation détaillée.
Écrit dans le calcul de lambda, naturellement, les options de compilation de Lambda-8cc sont également exprimées en termes de calcul lambda. Ces options peuvent être utilisées pour déverrouiller les fonctionnalités complètes de Lambda-8cc.
Les options de compilation sont utilisées en appliquant un terme facultatif AS (lambda-8cc option) à l'avance de l'entrée. Cela modifie le comportement du terme lambda lambda-8cc afin qu'il accepte / produit un format d'entrée / sortie différent.
Voici toutes les options de compilation de Lambda-8CC:
| Saisir | Sortir | Option de compilation |
|---|---|---|
| C | x86 Exécutable | |
| C | Terme de calcul Lambda en texte en clair | |
| C | Notation de calcul Lambda binaire (programme BLC) | |
| C | Calculus de combinateur de ski (programme Lazy K) | |
| C | Assemblage ELVM | |
| Assemblage ELVM | x86 Exécutable | |
| Assemblage ELVM | Terme de calcul Lambda en texte en clair | |
| Assemblage ELVM | Notation de calcul Lambda binaire (programme BLC) | |
| Assemblage ELVM | Calculus de combinateur de ski (programme Lazy K) |
Chaque option est dans le format d'un 3-Tuple
Les options de compilation indiquées précédemment peuvent être utilisées dans le terminal comme suit.
Pour compiler C à une liste d'assemblage ELVM as :
( ( cat lambda-8cc.lam ; printf ' (\f.(f (\x.\y.x) (\x.\y.\z.\a.\b.b) (\x.x))) ' )
| bin/lam2bin | bin/asc2bin ; cat input.c ) | bin/uni++ -o > a.s Pour compiler une liste d'assemblage ELVM as à x86 exécutable a.out :
( ( cat lambda-8cc.lam ; printf ' (\f.(f (\x.\y.y) (\x.\y.\z.\a.\b.x) (\x.x))) ' )
| bin/lam2bin | bin/asc2bin ; cat a.s ) | bin/uni++ -o > a.out
chmod 755 a.out Comme décrit précédemment, en compilant séparément as et a.out en utilisant ces commandes, l'utilisation maximale de RAM peut être coupée en deux car la mémoire est libérée lorsque chaque processus se termine.
En exécutant LAMBDA-8CC sans aucune entrée ou option, vous pouvez voir un message d'utilisation affichant l'ensemble complet d'options:
$ cat lambda-8cc.lam | bin/lam2bin | bin/asc2bin | bin/uni++ -o
lambda-8cc v1.0.0
Usage:
apply lambda-8cc.lam [input-file]
apply lambda-8cc.lam [option] [input-file]
Options:
(f.(f [input] [output] (x.x)))
(f.(f (x.y.x) (x.y.z.a.b.x) (x.x))) : C to x86 (defualt)
(f.(f (x.y.x) (x.y.z.a.b.y) (x.x))) : C to *.lam (plaintext lambda calculus program)
(f.(f (x.y.x) (x.y.z.a.b.z) (x.x))) : C to *.blc (binary lambda calculus program)
(f.(f (x.y.x) (x.y.z.a.b.a) (x.x))) : C to *.lazy (SKI combinator calculus, as a Lazy K program)
(f.(f (x.y.x) (x.y.z.a.b.b) (x.x))) : C to ELVM assembly
(f.(f (x.y.y) (x.y.z.a.b.x) (x.x))) : ELVM assembly to x86
(f.(f (x.y.y) (x.y.z.a.b.y) (x.x))) : ELVM assembly to *.lam
(f.(f (x.y.y) (x.y.z.a.b.z) (x.x))) : ELVM assembly to *.blc
(f.(f (x.y.y) (x.y.z.a.b.a) (x.x))) : ELVM assembly to *.lazy
lambda-8cc includes the following projects. All of the following projects
are released under the MIT license. See the LICENSE in each location for details.
8cc: By Rui Ueyama - https://github.com/rui314/8cc
ELVM: By Shinichiro Hamaji - https://github.com/shinh/elvm
LambdaVM: By Hikaru Ikuta - https://github.com/woodrush/lambdavm
lambda-8cc: By Hikaru Ikuta - https://github.com/woodrush/lambda-8cc
Le tableau suivant montre le temps de compilation et l'utilisation de la mémoire sur l'interprète de calcul Lambda de Melvin Zhang.
| Programme | Temps de compilation | Max. Utilisation de la RAM au moment de la compilation | x86 Taille binaire | Description |
|---|---|---|---|---|
| putchar.c | 1,8 min | 31 Go | 342 octets | Imprime A |
| bonjour.c | 2,4 min | 42 Go | 802 octets | Imprime Hello, world! |
| echo.c | 2,5 min | 46 Go | 663 octets | Echoes Entrée standard |
| rot13.c | 7,7 min | 84 Go | 2 118 octets | Code / décode stdin vers / depuis rot13 |
| Fizzbuzz.c | 49,7 min | 240 Go | 5 512 octets | Imprime la séquence FizzBuzz jusqu'à 30 |
| pmimes.c | 53,0 min | 241 Go | 5 500 octets | Imprime les plames jusqu'à 100 |
Maintenant, c'est beaucoup de mémoire! Pour compiler des programmes qui nécessitent un énorme RAM, vous pouvez étendre votre région de swap sans modifier les paramètres de partition en utilisant un fichier de swap. Si vous exécutez Linux et que vous avez un stockage gratuit ou un lecteur USB, vous pouvez utiliser ce stockage pour étendre facilement et dynamiquement votre région de swap à l'aide de mkswap et swapon . Les statistiques de ce tableau sont exécutées avec une région d'échange étendue de cette façon. Les instructions sont expliquées dans ce fil Askubuntu. Je soupçonne que l'utilisation de la RAM peut être diminuée en introduisant un GC Mark-and-Sweep à l'interprète, bien que je ne l'ai pas encore confirmé.
Notez que ce sont les temps de compilation - les temps de fonctionnement du binaire x86 compilé sont instantanés. Cela tient même lors de la compilation des termes de calcul Lambda. Les termes Lambda compilés s'exécutent également instantanément et n'utilisent que quelques gigaoctets de mémoire lorsqu'ils sont exécutés sur un interprète de calcul Lambda.
Les compilations de ces statistiques ont été exécutées sur une machine Ubuntu 22.04.1 avec 48 Go de RAM, un swap SSD de 16 Go (partition par défaut) et un swap du disque dur 274 Go (256GIB) (ajouté dynamiquement avec mkswap et swapon ). Le temps d'exécution indiqué ici est le temps de fonctionnement de l'horloge murale, y compris les opérations de mémoire. Pour les programmes lourds d'échange, le temps d'exécution pourrait être diminué en utilisant un appareil avec une vitesse d'E / S plus rapide.
Les statistiques ont été mesurées en fonctionnant
cp examples/[program].c ./input.c
make qui compile as et a.out pour input.c séparément pour enregistrer l'utilisation totale de la mémoire. Un tableau de statistiques plus détaillé pour chaque passe est indiqué en détail.
Veuillez consulter les détails.md.
Pour plus de détails sur la construction de Source, veuillez consulter les détails.md.
Lambda-8cc est une combinaison de 3 projets, Lambdavm, ELVM et 8cc. Lambdavm a été écrit par Hikaru Ikuta, l'auteur de ce référentiel (Lambda-8cc). L'architecture ELVM a été écrite par Shinichiro Hamaji. 8cc a été écrit par Rui Ueyama. La version de 8cc utilisée dans Lambda-8cc est une version modifiée de 8cc incluse dans le cadre de l'ELVM, modifié par Shinichiro Hamaji et autres. Lambda-8cc comprend également ELC, une partie de l'ELVM écrite par Shinichiro Hamaji, modifiée par Hikaru Ikuta afin qu'il puisse compiler l'assemblage ELVM avec le calcul de lambda. Le backend de calcul Lambda pour ELVM a été écrit par Hikaru Ikuta, en intégrant Lambdavm dans ELVM. Les statistiques de temps d'exécution et d'utilisation de la mémoire ont été mesurées à l'aide d'un interprète de calcul Lambda écrit par Melvin Zhang. Lam2bin a été écrit par Justine Tunney.
