Memoisering

memoisering.clj

;; Ok. Jeg husker ikke Scheme/Racket helt, så jeg tar det i Clojure.
;; Jeg satser på at syntaxen er lik nok til at du skjønner poenget.
;; Først skal jeg bare forklare et par konsepter som kan være ulikt scheme.

;; atom
;; Alt i Clojure er i utgangspunktet immutable(ikke-muterbart).
;; Funksjoner som set-car! og set-cdr! finnes ikke.
;; For å kunne mutere state, kan en pakke inn en verdi i et atom.
;;
;; (def muterbar (atom '()) <-- definerer en muterbar liste som heter 'muterbar'
;; @muterbar <-- henter ut verdien i 'muterbar', som jo er '()
;;
;; For å oppdatere atomet, bruker vi funksjonen swap! som tar imot atomet og en
;; funksjon som oppdaterer state.
;;
;; (swap! muterbar cons 1) <-- kaller (cons @muterbar 1) og lagrer resultatet i 'muterbar'
;; @muterbar <-- skal nå være '(1)
;;
;; I Scheme vil du sannsynligvis bare bruke set-car! eller tilsvarende.

;; Maps
;; I Clojure kan du skrive {} for å få en hashmap/dictionary.
;;
;; (def navn->kjønn {"Ola" "mann"
;;                   "Kari" "kvinne"})
;; (get navn->kjønn "Ola") <-- Gir "mann"
;;
;; I Scheme bruker en vel association lists(?).
;;
;; Så eksempelet over blir vel noe som:
;;
;; (define navn->kjønn '(("ola" . "mann")
;;                       ("Kari" . "kvinne"))
;; Også finnes det vel funksjoner som henter ut riktig verdi basert på
;; hva 'car' er.

;; & args og apply
;; Funksjoner som tar imot '& <navn>' tar imot argumenter som en liste
;; (def ex (fn [& args]
;;           args)
;; (ex 1 2 3) <-- 'args' er '(1 2 3)
;;
;; apply lar oss kalle en funksjon med en liste som om hvert element
;; i listen var et direkte argument.
;; (apply fn '(1 2 3)) er det samme som (fn 1 2 3)

;; Hvordan koden fungerer
;;
;; Memoize tar imot en funksjon, og returnerer en funksjon
;; Den returnerte funksjonen har tilgang på en muterbar cache,
;; som inneholder en hashmap/assosiasjonsliste som mapper
;; input fra tidligere kall, til ferdig kalkulerte resulater.
;; Dersom du argumentene du kaller funksjonen med finnes i cache,
;; så leser vi bare ut verdien. Hvis ikke kaller vi den opprinnelige
;; funksjonen med argumentene vi er gitt, og lagrer argumenter og
;; resultatet i cache.
;;
;; HVA!? Muterbarhet i funksjonell kode!? Jada. Det går fint så lenge
;; vi ikke bryter "renheten" i det. Så lenge du får ut samme resultat
;; gitt samme input, så bryr vi oss ikke så veldig mye om hvordan det
;; skjer.
;;
;; Greit å ha i bakhodet at memoizering er noe en bør være forsiktig med.
;; Verdier blir værende i cachen uendelig, som betyr at minnebruken øker
;; hver gang funksjonen kalles med forskjellige argumenter, og den minnebruken
;; reduseres aldri. Dette er kjent som en space-leak, som er en avart av
;; en minnelekasje.

(defn memoize [to-memoize] ;; to-memoize er funksjonen du vil memoisere
  (let [cache (atom {})] ;; oppretter en muterbar hashmap kalt cache
    '(
       (fn [& args] ;; funksjonen som returneres. Bruker '& args' for å kunne memoisere alle slags funksjoner
      (let [in-cache (get @cache args)] ;; sjekker om denne funksjonen er kalt med 'args' før.
        (if in-cache
          in-cache ;; hvis vi finner en verdi i cache, returner denne
          (let [res (apply to-memoize args)] ;; hvis ikke, kall funksjonen med gitte argumenter
            (swap! cache assoc arg res) ;; oppdater cache
            res)))))
        (fn []
          (reset! cache {})
    ) ;; returner '(memoized unmemoize)

;; Gitt et tall, gir deg neste tall i fibanacci sekvensen (helt sikkert feil)
(defn fib [n]
  (if (<= n 0)
    1
    (+ (fib (- n 1)) (fib (- n 2)))))

;; memoiser fib funksjonen
(def memoize-res (memoize fib))
(def memoized-fib (first memoize-res))
(def unmemoize-fib (second memoize-res))

;; dobbel sjekk at fib og memoized-fib gir samme resultat
(assert (= (fib 5) (memoized-fib 5)))
(unmemoize-fib)