torsdag 19. september 2013 Polyglot CoffeeScript Lambda
I denne posten skal vi definere tall i lambda calculus. Du bør lese del 1 først, om du ikke har gjort det allerede.
Som med bolske verdier må også tallene være funksjoner – funksjoner er tross alt det vi har å jobbe med. Forslaget er da som følger:
Vi lar alle tall være funksjoner som har 2 parametre (igjen skal vi egentlig bare ha funksjoner med ett parameter, men det løser vi med funksjoner som returnerer funksjoner). Vi bestemmer videre at funksjonen representerer tallet 0 om den, når den blir kalt, returnerer sitt andre argument. Vi kan definere dette slik:
ZERO = (f) -> (x) -> x
For tallet 1 derimot bestemmer vi at resultatet skal være lik resultatet av et kall til det første argumentet med det andre argumentet som parameter. Sagt mye enklere slik:
ONE = (f) -> (x) -> f(x)
Foreløpig er dette ganske vilkårlig, men det gir mening snart..
For tallet 2 gjør vi det samme som for 1, men vi vil kalle det første argumentet enda en gang på resultatet av det første kallet. Altså slik:
TWO = (f) -> (x) -> f(f(x))
Hver gang vi plusser på 1 ønsker vi et ekstra kall til f. Det spiller ingen rolle hva f og x er, poenget er at et tall i vår bruk av lambda calculus er en funksjon som kommer til å kalle f så mange ganger som tallet representerer.
Det kan være greit å lage seg en liten hjelpefunksjon nå, slik at vi enkelt kan oversette et lambda-tall til et "vanlig" tall. Jeg håper du ser hvordan den fungerer:
toNumber = (n) -> n((i) -> i+1)(0)
Hvis n er en funksjon som representerer tallet 0 så skal den returnere sitt andre argument. I toNumber-funksjonen er det nettopp tallet 0.
Hvis n representerer 1 vil den kalle inkrementeringsfunksjonen (i) –> i+1 med 0 som argument. 0+1 er som kjent lik 1.
Og hvis n representerer et tall større enn 1 vil inkrementeringsfunksjonen kalles flere ganger...
show toNumber(ZERO) show toNumber(ONE) show toNumber(TWO)
Denne testen skriver derfor ut 0, 1 og 2.
For å løse oppgaven jeg har tenkt å løse (summen av alle multipler av 3 eller 5 under 1000) trenger jeg å kunne teste om et tall er 0. La oss lage en lambda-funksjon for det:
IS_ZERO = (n) -> n((x) -> FALSE)(TRUE)
Den er ganske link toNumber egentlig. Hvis n er 0 vil den returnere FALSE (lambda-representasjonen av false). Hvis n er større enn 0 vil funksjon i første argument bli brukt (en eller flere ganger), og den returnerer alltid FALSE.
show toBool(IS_ZERO(ZERO)) show toBool(IS_ZERO(ONE))
Dette skriver ut henholdsvis "true" og "false".
PS: Som du så brukte jeg TRUE og FALSE i min definisjon av IS_ZERO. Dette er egentlig ikke tillat i lambda calculus, men en forenkling for at det skal være mulig å forstå for oss dødelige mennesker. Den faktiske implementasjonen av IS_ZERO burde se slik ut:
IS_ZERO = (n)->n((x)->(x)->(y)->y)((x)->(y)->x)
Dette er alt for vanskelig å forholde seg til, så vi fortsetter på den måten vi har gjort det til nå.
Det siste jeg vil vise er hvordan vi kan lage nye tall ved å inkrementere tall vi allerede har.
INCREMENT = (n) -> (f) -> (x) -> f(n(f)(x))
Ved å kalle INCREMENT med et argument n (som representerer et tall), vil vi få ut en ny funksjon som tar parametrene f og x, og returnerer resultatet av n-tallet med et ekstra kall til f (antall kall til f bestemmer jo hvor stort tallet er).
THREE = INCREMENT(TWO) FOUR = INCREMENT(INCREMENT(TWO)) show toNumber(THREE) show toNumber(FOUR)
Dette skriver ut "3" og "4".
I neste kaffepause vil jeg vise deg hvordan vi laget flere numeriske operasjoner som pluss, minus og gange i lambda calculus, og vi vil implementere modulo, som jeg også trenger for å finne ut om et tall er et multippel av 3 eller 5.