CS Challenge 12, The X Calculus

Turing-maskinen blev udviklet i 1936 af Alan Turing som et (negativt) svar på Hilberts berømte Entscheidungsproblem fra år 1900. Dette skete længe før man byggede faktiske, fysiske computere, men de basale ideer i Turing-maskinen (hukommelse, instruktioner, sekventiel udførelse, tilstandsændringer) er stadig arkitekturen for alle moderne computere.

Bemærkelsesværdigt blev problemet også i 1936 løst helt uafhængigt af Alonzo Chruch, med en på mange måder mere elegant model for beregninger. I denne Challenge ser vi på en meget abstrakt formulering af dette af Haskell Curry fra ca. 1952.

Et program er et binært træ med symbolet X i alle blade. Det vil sige, at programmet faktisk kun er repræsenteret som faconen af træet. Det beregningsmæssige indhold er defineret ved, at der på runtime laves omskrivninger (kaldet reduktioner) i træet. På runtime kan der yderligere optræde symbolerne S, K og I som blade, efter disse regler: Der er altid tale om binære træer, så fx a K S K skal læses som ((a K) S) K.

Man kan se, at X-symbolerne hurtigt forsdvinder, og at resultatet altid er et SKI-træ. Til gemgæld kan SKI-træer præsenteres som X-tr%aelig;er, da der gælder disse ligninger:

Generelt har vi såldes SKIX-træer, kan nøjes med SKI-træer, og bruger ehentlig kun X-træer for at imponere - et rent binært træ er en meget abstrakt formulering af et program!
Lige nu kan vi kun stirre undrende på vores sprog og vores runtime: hvordan kan denne maskine benyttes til at foretage fornuftige beregninger? Men situationen er egentlig ikke anderledes, end hvis nogen gav os en ukendt computer uden software: vi kan skrive et langt bitmønster i hukommelsen, og på runtime ændrer dette sig til et andet bitmønster.

I begge tilfælde skal vi repræsentere vores information på en så sneedig måde, at den transformeres som beregninger.

Toolet X.java implementerer denne maskine. Jommandoen: 
java X run
læser et SKIX-træ fra stdin, foretager alle reduktioner og udskriver resultatet på stdout. Dem næste reduktion, der vælges, er altid den højest oppe i træet og læmgst til venstre. Dette vslg gør SKIX til et lazy sprog (hvorfor?). Varianten: 
java X trace
udskriver også mellemresultatet efter hver reduktiion.

Spørgsmål A

Forklar, at man i metoden reduceS kan se, at implementationen faktisk tillader delte undertræer. Giv et uformelt argument for, at dette ikke æmdrer resultatet og nogle gange er hurtigere. Hint: SKIX er et pure sprog.
Ikke-negative heltal kan udtrykkes på følgende må, gcor [E] generelt angiver indkodningen af et udtryk E: hvor vi benytter forkortelserne: Det snedige ved denne indkodning er, at: Det vil sige, et tal faktisk indkodes som en for-løkke med dette antal iterationer.
Toolet understøtter også kommandoen: 
java X translate
der oversætter et SKIX-udtryk (fra stdin) med brug af numeraler og forskellige andre konstanter til et rent X-udtryk (på stdout). Endeligt vil kommandoen; 
java X constant
tage et AKIX-udtryk (fra stdin) og udskrive det tilsvarende numeral (på stdout), hvis udtrykket faktisk er indkodningen af et sådant.

Med tilstrækkelig snedighed kan man også finde udtrk for andre aritmetiske operationer, som:

der også understøttes af translate kommandoen (afprøv dem!).

Spørgsmål B

Udfør et antal eksperimenter af formen: 
echo "n m" | java X translate > foo
java X run < foo > bar
java X constant  < bar
for forskellige (små) heltal n og m. Find på en hypotese om, hvad [n][m] generelt beregner.
Toolet bruger ofte meget stakplads i Java, men denne kan forøges til fx 4MB ved at bruge option -Xss4m til java kommandoen.
Booleans indkodes med disse udtryk: De indkoder direkte en if-sætning, da: Mu kan vi også finde en iszero funktion på numeraler. Den udnytter at n er en for-løkke til n gange at anvende den konstante funktion false på argumentet true, og ser ud som følger: Hvordan programmerer man den slags, når SKI-operationerne virker som ekstremt lavniveau maskinkode? Det kan faktisk gøres helt systematisk.

Antag, at et SKIX-udtryk E har fået lov til at bruge et antal parametre x1,...,xk. De kan elimineres i en induktiv proces, hvor E omskrives til [x1],...,[xk]E efter reglerne:

Denne algoritme viser designet bag SKI-systemet: S fordeler en parameter til to undertræer, K smider en uønsket parameter væk, og I aflæser en ønsket parameter.

Med denne teknik kan vi fx programmere not, der med en parameter let kan skrives som:

Med algoritmen kan vi eliminere a og få: Kommandoerne translate og constant understøtter også booleans.

Spørgsmål C

Udvid X.java med funktionen or på booleans. Den skal skrives med SKI-koder og derefter skal Java-koden udvides et par steder.
Vi kan nu bygge mere og mere ovenpå, til vi ril sidst har et komplet programmeringssprog. Fx kan minus skrives son (hvorfor?):

Spørgsmål D

Vis, hvordan man tilsvarende kan skrive funktionerne lt (less-than) og le (less-than-or-equal).
Det eneste vi nu mangler for at have samme udtrykskraft som alle andre programmeringssprog er rekursion, men også det kan lade sig gøre.

Udganhspunktet er en forunderlig operator:

med egenskaben: Med denne kan vi i hvert fald lave en uendelig løkke som fx fix(I) (prøv den!).

Spørgsmål E (frivillig)

Udnyt alt ovenfor til at programmere et SKIX-udtryk, der beregner fakultetsfunktionen.

Dette spørgsmål er rigtig vanskeligt, så man får også denne Challenge godkendt uden at svare på det. Men det er jo sidste lejlighed til at imponere på CS Challenge 2016!

BlueJ version: XBlueJ.zip.
Du deltager i vores Challenge ved senest den 11. december at sende en e-mail til mis@cs.au.dk med subject Challenge 12 og svarene på spørgsmål A, B, C, D og og (eventuelt) E (i plain text) og koden til spørgsmål C i form af et attachment med en ny udgave af programmet X.java.