Een Python-interpreter maken in 1024 bytes

def buzz():
    for n in range(101):
        if n % 15 == 0:
            print("FizzBuzz")
        else:
            if n % 3 == 0:
                print("Fizz")
            else:
                if n % 5 == 0:
                    print("Buzz")
                else:
                    print(n)
buzz()

Ik kan waarschijnlijk niet de volledige Python-taal in een interpreter passen die slechts 1024 bytes groot is. Dus wat kan ik er wel in passen dat eruitziet als Python?

Dit FizzBuzz-programma ziet er typisch Pythoniaans uit. Het heeft de def, de dubbele punten, de inspringingen en geen haakjes bij de if-statements. Voor mij ziet dit eruit als Python! Natuurlijk zal ik ook enkele beperkingen moeten toevoegen die verder gaan dan alleen een subset van de syntax.

Eerste poging: 512 bytes is niet genoeg!

Ik heb al veel recursive descent parsers geschreven, dus hoe anders kan dit zijn? Een subset van Python zou vergelijkbaar moeten zijn met andere talen die ik heb geïmplementeerd (zoals mijn Teeny Tiny compiler).

Ik begon met de meest basiscode die ik kon bedenken: 1 + 2. Daarna maakte ik het complexer: x = 1 + 2 * 3. En vervolgens voegde ik zelfs statements toe: if x > y: z = 3.

Geweldig, ik had een rekenmachine gemaakt... maar dat was niet wat ik met deze uitdaging bedoelde! Bovendien was ik al over de limiet heen. Op dat moment zoomde ik uit en maakte ik een lijst met elementen die "Pythony" ogen, terwijl ik me realiseerde dat mijn code golf-vaardigheden niet voldoende waren om het in 512 bytes te passen.

Misschien lukt het wel in 1024 bytes? Eerst zorgen dat het werkt, en daarna het klein maken.

De parser

De eigenlijke CPython-implementatie tokeniseert de Python-broncode, parseert deze naar een abstract syntax tree (AST), voert analyses en optimalisaties uit, genereert bytecode en interpreteert vervolgens die bytecode.

Deze versie doet dat allemaal niet. De status wordt bijgehouden in een handvol globale variabelen. Er wordt gebruikgemaakt van een array met vaste lengte (voor nu 999) waarin de ruwe Python-code wordt opgeslagen. De variabelen en functienamen passen allemaal in één array.

char src[999];       /* Gehele programma zonder de meeste spaties. */
int  vars[256];      /* Symboeltabel.                       */
int  pos;            /* Volgende karakter in src.              */
int  ch;             /* Huidig karakter in src.           */
int  line_start;     /* Waar de huidige regel begint.      */

Expressies worden behandeld zoals in elke andere recursive descent parser en worden direct tijdens het parsen uitgevoerd. Bijvoorbeeld:

int parse_sum(void) {
    int value = parse_term();
    while (ch == '+' || ch == '-') {
        if (ch == '+')
            value = value + parse_term();
        else
            value = value - parse_term();
    }
    return value;
}

Tot nu toe is het vrij eenvoudig. Er is geen enkele vorm van foutafhandeling! Er wordt sterk uitgegaan van de correctheid van de code. Er wordt bijvoorbeeld aangenomen dat keywords correct zijn getypt:

if (ch == 'w' || ch == 'i' || ch == 'f') {
    int keyword = ch;
    int loop_var = 0;
    if (keyword == 'f') {        /* "for K in range(N):" */
        pos += 2;                /* Sla "or" over.           */
        loop_var = next();
        pos += 8;                /* Sla "inrange(".     */
        vars[loop_var] = 0;
    } else if (keyword == 'w')
        pos += 4;                /* Sla "hile" over.         */
    else
        pos += 1;                /* Sla "f" van "if" over.    */

Ook wordt ervan uitgegaan dat de token-grenzen correct zijn en wordt het grootste deel van de witruimte verwijderd. Inspringingen en spaties in string-literalen blijven behouden. De interpreter is beperkt tot variabelen van één enkele kleine letter, waardoor we symboeltabel-opzoekacties direct kunnen uitvoeren:

if (ch > 96) {
    value = vars[ch];
    next();
}

Control flow magie

De functie voor het uitvoeren van codeblokken gaat door totdat de inspringing afneemt. Op dat moment keert de functie terug, waarna het aan de aanroeper is om de volgende regel af te handelen. Er wordt dus gebruikgemaakt van de call stack van het C-programma om de recursie te beheren.

void run_block(int min_indent) {
    for (;;) {
        int indent = read_indent();
        if (ch == '\n')
            continue;
        if (indent < min_indent || ch == 0) {
            pos = line_start;
            return;
        }

Maar hoe zit het met loops? Omdat er niets wordt gecompileerd, werken loops door terug te springen en de broncode bij elke iteratie opnieuw te parsen. Zowel while- als for-loops houden de positie van de conditie-expressie bij. Nadat het blok is uitgevoerd, springt de parser terug naar die positie en gaat hij verder met parsen.

Functies werken op dezelfde manier. Bij het parsen van de definitie onthoudt de symboeltabel de positie van de functie in de broncode. Wanneer een functie wordt aangeroepen, wordt de locatie van de aanroeper opgeslagen, springt de parser naar het functieblok, voert dit uit, en herstelt de locatie van de aanroeper zodra het einde is bereikt.

Het is vrij mooi wat we kunnen doen, zelfs zonder een intermediate representation. De interpreter houdt bovendien zeer weinig status bij.

Minificeren!

Ik heb niet veel ervaring met code golf. Het inkorten van variabelenamen en het verwijderen van witruimte is voor de hand liggend, maar hoe bespaar ik de echt grote hoeveelheden bytes?

Er bestaat een oude, vergeten website genaamd Stack Overflow waar de codemagiërs van weleer hun kennis deelden. Ik heb veel ideeën opgedaan uit "Tips for golfing in C".

Omdat regels alleen in je verbeelding bestaan, moest ik creatief worden. Sommige van die tips vertrouwen op specifieke "features" van GNU C89. Dit is geen onzin, maar conventioneel knutselwerk. Dit is wat ik heb gedaan om bytes te besparen ten opzichte van de leesbare versie:

  • Gebruik van variabelen en functienamen van één letter.
  • Ervan uitgaan dat de compiler libc linkt.
  • Gebruik van globale variabelen voor tijdelijke variabelen.
  • Globale variabelen zijn standaard op nul geïnitialiseerd.
  • C89 staat toe dat variabelen impliciet int zijn en functies worden verondersteld int terug te geven.
  • Functieparameters gebruiken als tijdelijke variabelen die bewaard blijven op de call stack.
  • ASCII-waarden gebruiken in plaats van karakter-literalen.
  • Gebruik van de ternaire operator en de komma-operator.
  • Bitwise-operaties gebruiken in plaats van logische operaties.

Zo is de eerder getoonde functie parse_sum(void) ingekort tot e(){for(z=t();c-43u<3;)y=44-c,z+=y*t();return z;}. Er worden ASCII-waarden gebruikt om een paar bytes te besparen.

Een ander voorbeeld is een helperfunctie die springt naar het einde van een regel:

void skip_to_eol(void) {
    if (ch != 0 && ch != '\n') {
        next();
        skip_to_eol();
    }
}

Deze heb ik teruggebracht naar: Y(){c&&c-10&&Y(G());}. Er wordt getest op 0, er wordt 10 afgetrokken om te controleren op een nieuwe regel, en er wordt && gebruikt in plaats van een if. Daarnaast wordt een byte bespaard door Y(G()); te doen in plaats van G();Y();. Slim! Opnieuw dank aan dat Stack Overflow-bericht.

Uiteindelijk is de golfed versie precies 1024 bytes! De definitieve leesbare versie is echter ruim 4800 bytes. Oorspronkelijk had ik meer functies, maar ik heb er continu dingen uitgesneden om in de limiet te passen. Vergelijkings-expressies waren de volgende die eraf moesten, omdat die veel bytes kosten en truthiness nog steeds werkt zonder hen: if n%15:.

Als het me alleen ging om het werkend krijgen van FizzBuzz, denk ik dat ik onder de 800 bytes zou kunnen komen. Er zijn waarschijnlijk nog andere golfing trucs.

Hier is de golfed broncode in al zijn glorie:

char s[999];v[256],p,c,x,y,z,w,u;G(){return c=s[p++];}I(){for(u=p;G()==32;);return p-u;}Y(){c&&c-10&&Y(G());}f(){x=0;if(G()>96)x=v[c],G();for(;c-48u<10;G())x=x*10+c-48;return x;}t(g,h){for(g=f();c==42|c==37;)h=c,g=h-42?g%f():g*f();return g;}e(){for(z=t();c-43u<3;)y=44-c,z+=y*t();return z;}E(a,q){a=e();if(c-60u>2)return a;w=c-61;q=G()==61;p-=!q;x=e();return w?(a-x)*w>-q:a==x;}S(i){for(;I()>i|c==10;)Y();p=u;}Q(){for(G();G()-34;)putchar(c);G();}B(i,q,j,k,a,m,n){for(;;){j=I();if(c==10)continue;if(j<i|!c){p=u;return;}if(c==119|c==105|c==102){k=c;k-102?p+=k/4-25:(p+=2,m=G(),p+=8,v[m]=0);q=p;for(;;){a=k-102?E():v[m]<E();p+=k==102;G();if(!a){S(j);break;}B(j+1);if(k==105)break;k-102||v[m]++;p=q;}I()-j|c-101?p=u:(p+=4,G(),a?S(j):B(j+1));}else if(c==100){p+=2;k=G();Y();v[k]=p;S(j);}else{if(c>96){k=c;while(G()>96);c==40?k-112?(G(),n=p,p=v[k],B(2),p=n,G()):(s[p]-34?printf("%d",E()):Q(),puts(""),G()):(v[k]=E());}Y();}}}main(q,m,h){for(h=m=q=0;~(c=getchar());){c=c-9?c:32;h^=c==34;s[q]=c;q+=c-32?1:!m|h;m=c>32|m&&c-10;}B(0);}

Uiteindelijk ben ik erin geslaagd om de volgende functies te implementeren:

  • Integer variabelen (één letter) en literals
  • Toewijzing van variabelen
  • Rekenkunde met +, -, *, % met prioriteitsregels (unaire + - werkt alleen aan het begin van een expressie)
  • Vergelijkingen met <, >, <=, >=, == (maximaal één per expressie)
  • Integer truthiness
  • if en else
  • while loops, inclusief else blokken
  • for x in range(y) loops, inclusief else blokken
  • Functiedefinities zonder argumenten
  • Functie-aanroepen, inclusief recursie
  • Op inspringing gebaseerde blokken (zonder scope)
  • print met één string-literal of integer-expressie
  • Commentaren

Ik denk niet dat ik binnenkort opnieuw aan code golf uitdagingen zal doen. Het proces was behoorlijk tedious; ik moest constant heen en weer schakelen tussen de versie in wording en de originele versie om te begrijpen wat ik twee minuten geleden precies had aangepast. Beide versies staan op GitHub.

Nu is het jullie beurt. Hoe ziet jullie Python-interpreter van 1024 bytes eruit?