01 Introduction Flashcards
rekursjon
prosedyrer som kaller på seg selv
prosedyrer som førsteordens objekter
prosedyrer er datatyper på lik linje med tall, symboler, strenger, lister, etc.
høyere-ordens prosedyrer
prosedyrer som kan
1) ta prosedyrer som argumenter og
2) returnere prosedyrer
objektorientering via prosedyrer
innkapsulering av data i prosedyrer for å skjule tilstandsvariabler
strømmer og utsatt evaluering
definering av uendelige sekvenser og realisering av de enkelt elementene i disse ved utsatt evaluering etter behov
funksjonell vs imperativ programmering
Funksjonell programmering:
- Ingen tilstandsendringer
- En prosedyres returverdi vil alltid være den samme hvis argumentene er de samme
- Beregninger utføres som funksjonelle transformasjoner av data (kontra sekvensielle endringer av tilstandsvariabler ved imperativ programmering)
viktige egenskaper ved funksjonell programmering
Funksjoner danner byggeklossene.
Prosedyrene er uavhengige av ekstern tilstand, og påvirker ikke ekstern tilstand.
Dette gir enklere, sikrere, mer testbar og paralleliserbar kode.
Prosedyrer er data. Og disse kan representeres ved lister. Program = data.
Scheme
minimalistisk dialekt av Lisp
REPL
Read-Eval-Print Loop
primitive uttrykk i Scheme evaluerer til ___
seg selv
Hva evaluerer til true i Scheme?
Alt bortsett fra #f
notasjon i Scheme
parantesbasert prefixnotasjon
(Scheme)
Det første elementet i en liste er ___. Resten av lista består av ____.
operatoren, operandene (argumentene)
introdusere en leksikal variabel
(define foo 42)
define er en “special form”
Schemes evalueringsregel
1) Evaluér enkeltuttrykkene i sammensetningen
a) Atomære uttrykk evalueres til seg selv
b) Leksikale variabler og prosedyrer evalueres til verdiene de refererer til
c) Sammensatte uttrykk: anvend 1) igjen
2) Anvend operatoren på verdiene til de andre uttrykkene
Unntak: special forms
Evalueringsregelen er altså rekursivt definert
LISP står for…
List Processing
generell form for lambda-uttrykk
(define navn
(lambda (argumenter)
kropp))
kortform for lambda-uttrykk
(define (navn argumenter)
kropp)
predikater
prosedyrer eller uttrykk som returnerer #t eller #f
Innebygget i Scheme: even? zero? not >
‘and’ returnerer…
det logiske konnektivet ‘and’ returnerer #f eller verdien til det siste uttrykket
‘or’ returnerer…
det logiske konnektivet ‘or’ returnerer #f eller verdien til det første sanne uttrykket
Hva skiller de logiske konnektivene fra andre prosedyrer?
Evalueringen avbrytes så snart problemstillingen kan besvares. De logiske konnektivene følger altså ikke Schemes evalueringsregel.
syntaks for kondisjonale uttrykk
(if
)
(cond ( )
( )
( )
(else ))
applicative-order evaluation
1) Evaluer argumentene
2) Kall prosedyre på verdi
Dette er standard i Scheme.
(kontra normal-order evaluation)
Hvilke variable er bundne og frie i denne prosedyren:
define (avslag p pris
(* (/ pris 100) p))
Frie: *, /
Bundne: p, pris
Skopet for bindingen er kroppen til prosedyren.
en blokk
Når man definerer en prosedyre internt og lokalt i definisjonen til en annen prosedyre
Scheme er svakt/sterkt og dynamisk/statisk typet
Scheme er svakt og dynamisk typet
funksjon vs prosedyre vs prosess
En prosedyre er en implementasjon av en (matematisk) funksjon.
En prosess er beregningene en prosedyre gir opphav til.
halerekursjon
Det rekursive kallet står i “haleposisjon” (det er det siste prosedyren utfører). Dermen slipper man ventende prosedyrer og stack overflow.
(eng: tail call elimination)
halerekursiv prosedyre
En prosedyre er halerekursiv (eng: tail recursive) hvis dens returverdi er lik returverdien til det siste rekursive kallet.
ulike typer rekursjon
rekursjon
halerekursjon (iterativ prosess)
trerekursjon
par
> (cons 1 2)
(1 . 2)
> (car (cons 1 2))
1
> (cdr (cons 1 2))
2
den tomme listen
’()
liste
Lister er rekursiv definert
- ’() er en liste
- et par der cdr på paret er en liste, er en liste
> (cons 1 (cons 2 (cons 3 ‘())))
(1 2 3)
> (list 1 2 3)
(1 2 3)
(null? ‘())
t
en special form som gjør at uttrykket som følger ikke evalueres
quote
‘foo
quote foo
absoluttverdi
abs
anvende prosedyre på alle elementene i en liste
(map proc list)
NB: Endrer (selvsagt) ikke den opprinnelige listen, men returnerer en ny
(reduce proc init ‘(1 2 3))
(proc 1 (proc 2 (proc 3 init)))
(define stuff (list + “zoo” 42 ‘towel))
> stuff
(# “zoo” 42 towel)
let-uttrykk med n variable er ekvivalent med…
et lamda-uttrykk med n parametre
let-uttrykk der bindingene kan referere til hverandre
(let* …)
let-uttrykk
(let ((var1 exp1)
(var2 exp2))
body)
message passing
en prosedyre kaller en prosedyre med en gitt verdi (beskjed)
define (car proc
(proc 0))
par implementert som prosedyre
(define (cons x y)
(lambda (query)
(cond ((= query 0) x)
((= query 1) y))))
(clojure!)
