IN2040 · UiO

Studieguide for IN2040 Funksjonell programmering

Komplett pensumoversikt for funksjonell programmering ved UiO — med forklaringer, sentrale begreper, eksamenstips og vanlige fallgruver. Eksamensoptimalisert basert på tidligere eksamener.

Introduksjon

IN2040 Funksjonell programmering (tidligere INF2810) er Ifi-kurset som lærer deg å tenke i funksjoner, rekursjon og abstraksjon — med Scheme som verktøy. Eksamen er en 4-timers skriftlig digital eksamen uten hjelpemidler, og oppgavesettet summerer til 100 poeng.

Denne guiden er bygget rundt det som faktisk testes: vi har analysert autentiske eksamenssett fra forgjengeremnet INF2810 (vår 2014 og vår 2015, begge med offisielle løsningsforslag, samt prøveeksamenen). Mønsteret er påfallende stabilt: boks-og-peker-diagrammer med set-car!/set-cdr!, omgivelsesdiagrammer, «skriv samme prosedyre i flere paradigmer»-oppgaven (halerekursiv, rekursiv, høyereordens, destruktiv og strømbasert), telling av cons-operasjoner, innkapsling med lokal tilstand, og evalueringsstrategier (eager vs. lazy). Behersker du disse gjengangerne, har du dekket brorparten av poengene.

Et praktisk råd fra eksamensinstruksen selv: står du fast på Scheme-syntaks, skriv pseudokode med kommentarer — det gir langt mer uttelling enn et blankt felt.

Funksjonell programmering

Eksamensrelevant

Det funksjonelle paradigmet: uttrykk og verdier, rene prosedyrer uten sideeffekter, let som forkledd lambda, og forskjellen på funksjonell og destruktiv kode — kjernen i eksamens store «skriv flere varianter»-oppgave.

Uttrykk, verdier og rene prosedyrer

I funksjonell programmering er alt bygget av uttrykk som evalueres til verdier. En rent funksjonell prosedyre beregner returverdien sin utelukkende fra argumentene: samme input gir alltid samme output, og ingenting utenfor prosedyren endres. Dette kalles referansegjennomsiktighet — et kall kan alltid byttes ut med verdien sin uten at programmet endrer oppførsel. Motsatsen er prosedyrer med sideeffekter: set!, set-car!, set-cdr! og display endrer tilstand eller omverden, og da betyr plutselig rekkefølgen på evalueringen noe.

Eksamen spør ofte direkte: «Forklar med et par setninger hva som skiller en rent funksjonell prosedyre fra en ikke-funksjonell.» Svaret sensor ser etter: ingen sideeffekter, returverdien avhenger bare av argumentene, og kallet kan erstattes med verdien sin.

let er bare lambda i forkledning

En klassisk eksamensoppgave er å skrive om et let-uttrykk til ekvivalent lambda-form. Nøkkelen: let lager bindinger ved å kalle en anonym prosedyre:

(let ((a 5) (b 10))     ((lambda (a b)
  (+ a b))          ≡      (+ a b))
                          5 10)

Eksempel: omskriving med skygging

(let ((x (list 1 2)))
  (display x)                 ; skriver (1 2)
  (let ((x (cons 0 (cdr x)))) ; NY binding som skygger den ytre
    (display x)))             ; skriver (0 2)

Som lambda: ((lambda (x) (display x) ((lambda (x) (display x)) (cons 0 (cdr x)))) (list 1 2)). Merk to ting sensor ser etter: (1) bindingene i ett og samme let evalueres i den ytre omgivelsen (de ser ikke hverandre — det er let* som binder sekvensielt), og (2) et indre let skygger det ytre uten å endre det.

Funksjonell vs. destruktiv — paradigme-oppgaven

Eksamens største enkeltoppgave ber deg typisk skrive samme transformasjon i flere stiler. En funksjonell versjon bygger en ny liste med cons; en destruktiv versjon (navnekonvensjon: utropstegn, f.eks. dobbel-alle!) endrer den eksisterende strukturen med set-car!:

Eksempel: funksjonell og destruktiv dobling

;; Funksjonell — ny liste, originalen urørt (n cons-operasjoner)
(define (dobbel-alle seq)
  (if (null? seq)
      '()
      (cons (* 2 (car seq))
            (dobbel-alle (cdr seq)))))

;; Destruktiv — muterer argumentet (0 cons-operasjoner)
(define (dobbel-alle! seq)
  (if (null? seq)
      'ferdig
      (begin (set-car! seq (* 2 (car seq)))
             (dobbel-alle! (cdr seq)))))

Etter (define tall (list 1 2 3)) gir (dobbel-alle tall) en ny liste (2 4 6) mens tall fortsatt er (1 2 3); (dobbel-alle! tall) gjør at tall selv blir (2 4 6). Eksamen følger gjerne opp med: «hvor mange cons-operasjoner utløser hver variant?» — tell én per cons i koden ganger antall elementer; destruktive varianter bruker null.

begin og hvorfor funksjonell kode ikke trenger den

(begin e1 e2 ... en) evaluerer uttrykkene i rekkefølge og returnerer verdien av det siste. Et kjent eksamensspørsmål: «Så lenge vi holder oss til ren funksjonell kode har vi ingen bruk for begin — stemmer det?» Ja, i all hovedsak: uten sideeffekter er verdiene av e1 ... e(n-1) bare kastet bort, så bare det siste uttrykket betyr noe. begin har kun mening når de første uttrykkene gjør noe (skriver ut, muterer).

Nøkkelformler

•(let ((v1 e1) (v2 e2)) kropp) ≡ ((lambda (v1 v2) kropp) e1 e2)
•Rent funksjonell = samme argumenter → samme verdi, ingen sideeffekter (referansegjennomsiktighet)
•Navnekonvensjon: utropstegn (dobbel-alle!) signaliserer destruktiv prosedyre
•(begin e1 ... en) → verdien av en; bare nyttig når e1..e(n-1) har sideeffekter
•cons-telling: én per cons i koden × antall ganger den kjøres; destruktive varianter = 0

Vanlige feil

⚠️Tro at let binder sekvensielt — bindinger i samme let evalueres i den ytre omgivelsen; det er let* som binder én og én.
⚠️Skrive «funksjonell» kode som likevel kaller set!/set-car! — én mutasjon er nok til at prosedyren ikke er ren.
⚠️Glemme at append kopierer den første listen — det koster cons-operasjoner, mens cdr aldri kopierer.
⚠️Returnere display-verdien — display er en sideeffekt; returverdien er udefinert og skal ikke brukes videre.

Eksamenstips

💡I «skriv om let til lambda»-oppgaver: oppgi også returverdi/effekt av uttrykket — det står eksplisitt i oppgaven og gir egne poeng.
💡Når du blir bedt om en rent funksjonell variant: sjekk at koden din verken bruker set!, set-car!, set-cdr! eller display.
💡Øv på cons-tellingen på egne løsninger — spørsmålet «hvor mange cons?» kommer igjen og igjen og er raske poeng.

Laster...

Laster…