Lambda til kaffen (del 4: rekursjon)

lørdag 21. september 2013 Polyglot CoffeeScript Lambda Rekursjon

I min demonstrasjon av lambda calculus har vi nå kommet til utfordringen knyttet til hvordan man itererer – gjør noe mange ganger. I løpet av denne posten vil jeg vise hvordan man kan støtte rekursjon i et funksjonelt språk som i utgangspunktet ikke har denne muligheten "innebygd".

Og hvis du havnet på denne siden uten å ha lest begynnelsen så finner du del 1 her.

Vanlig rekursjon

I del 3 definerte jeg funksjonen MOD ved hjelp av et vanlig rekursivt kall, noe som ikke er tillat i lambda calculus. Definisjonen så ut som dette:

MOD = (m) -> (n) ->
  IF(IS_LESS_OR_EQUAL(n)(m))(
    (x) -> MOD(SUBTRACT(m)(n))(n)(x)
  )(
    m
  )

I programmeringsspråk du er vandt med har du ulike former for løkker (for, while, until) som brukes til å iterere. Disse er implementert med GOTO-statements. I det teoretiske språket lambda calculus har man kun funksjoner, og i likhet med rekursjon kan vi ikke benytte oss av noen goto heller. Det vi trenger er et lurt triks...

Z combinator

Og trikset vi skal bruke kalles Z-kombinatoren (også referert til som call-by-value Y combinator). Den er veldig vanskelig å forstå, og derfor ekstremt vakker :)

La oss definere den først:

Z = (f) -> ((x) -> f((y) -> x(x)(y)))((x) -> f((y) -> x(x)(y)))

Ok. Hva i alle dager er det som skjer her?

Jo, Z er en funksjon som har en annen funksjon f som parameter. f-funksjonen er den som trenger rekursjon, og hemmeligheten er at gjennom noen funksjonelle krumspring så får den seg selv inn som parameter. Dermed kan jeg for eksempel gjøre følgende for å eksekvere en uendelig rekursjon:

r = Z((x) –> () –> x())
r()

Kjører jeg denne får jeg raskt feilmeldingen "Maximum call stack size exceeded". Men jeg kan jo gjøre noe litt mere fornuftig, for eksempel summere alle tall fra 0 til 10:

sumRange = Z((f) ->
  (i) -> (sum) ->
    show "i=#{i} sum=#{sum}"
    if i == 0
      sum
    else
      f(i-1)(sum+i))

show "Result = " + sumRange(10)(0)

Her bruker jeg altså flere ting fra CoffeeScript - dette er ikke lambda calculus, kun en liten test - men jeg holder meg likevel til funksjoner med kun én parameter. Koden gir følgende output som viser at Z virker:

i=10 sum=0
i=9 sum=10
i=8 sum=19
i=7 sum=27
i=6 sum=34
i=5 sum=40
i=4 sum=45
i=3 sum=49
i=2 sum=52
i=1 sum=54
i=0 sum=55
Result = 55

Hvordan Z virker..

Å forklare hvordan Z- eller Y-kombinatoren virker er desverre utenfor scope for denne blogposten. Jeg håper du ikke blir alt for skuffet. Det finnes flere andre som har forsøkt, og jeg kan anbefale denne lenken for dem som er interessert. Kanskje forsøker jeg meg på en forklaring selv i en fremtidig post, men det holder ikke med en enkelt kaffepause :)

Modulo vha. Z

Det jeg derimot skal gjøre er å implementere en ny versjon av MOD som ikke bryter med reglene i lambda calculus. Og når jeg nå har definert Z så går det ganske greit:

MOD = Z((f) ->
  (m) -> (n) ->
    IF(IS_LESS_OR_EQUAL(n)(m))(
      (x) -> f(SUBTRACT(m)(n))(n)(x)
    )(
      m
    ))

Her har jeg tatt definisjonen jeg hadde og pakket den inn i en funksjon som jeg sender som et argument til Z. Dette er ganske likt som sumRange-funksjonen jeg nettopp laget, men nå bruker jeg kun lambda calculus-funksjonene og verdiene mine.

Og det var det!

Neste gang..

I neste del av Lambda til kaffen vil vi se på noe litt enklere, og som jeg har vært borti flere ganger før, nemlig lister. Jeg vil også definere en RANGE-funksjon som kan gi meg en liste av alle tall mellom to verdier, og da vil vi igjen ta i bruk Z-kombinatoren.