01
Informatik 1
13 – Programme als Daten und
der λ-Kalkül
Winter 2020/21
Torsten Grust
Universität Tübingen, Germany
02
1 ┆ Neue Sprachebene: DMdA — fortgeschritten
Wir schalten auf die nächste Sprachebene Die Macht der
Abstraktion — fortgeschritten um. Änderungen bzw. neu: 1. Neues Ausgabeformat für Listen (⋯) in der REPL:
> (list “1 “2 … “ₙ) (“1 “2 … “ₙ)
> empty
()
>█
2. Polymorpher Gleichheitstest equal? für beliebige Werte: (: equal? (%a %b -> boolean))
3. Sei ‘ ein beliebiger Ausdruck. Dann liefert (()*+, ‘) die Repräsentation von ‘ — ‘ wird nicht ausgewertet:
(quote 42)
(quote “Leia”)
(quote #t)
(quote (+ 40 2)) (quote (lambda (x) x))
⇝ 42 ⎫ Literale
⇝ “Leia” ⎬ repräsentieren ⇝ #t ⎭ sich selbst
⇝ (+ 40 2) ⎱ Repräsentiert ⇝ (lambda (x) x) ⎰ als Liste
03
Quoting: Programme sind Daten
Syntaktischer Zucker: ⍘’ ≡ (quote ‘).
⇒ Kompakte Notation literaler Listen (Literale 7i):
‘(7172…7ₙ) ⇝ (list7172…7ₙ) ‘() ⇝ empty
Symbole: Repräsentation von Identifiern/Namen
04
Was genau ist (first ‘(* 1 2))? Was sind 9:;<=:, x, + in
'(9:;<=: (x) (+ x 1))?
Neue Signatur symbol zur Repräsentation von Identifiern (Namen) in Programmen:
effiziente interne Darstellung (keine Duplikate),
effizient vergleichbar (mittels equal?),
kein Zugriff auf die einzelnen Zeichen des Symbols.
Operationen auf Symbolen:
(: symbol? (%a -> boolean)) (symbol? ‘*) ⇝ #t (: symbol->string (symbol -> string)) ⎱ inverse
(: string->symbol (string -> symbol)) ⎰ Funktionen
2 ┆ Der λ-Kalkül
05
Der λ-Kalkül ist eine Notation, die beliebige (für einen Computer überhaupt) berechenbare Funktionen darstellen kann.
Entwickelt in den 1930er Jahren von Alonzo Church (*1903, †1995) als neues Fundament der Mathematik (aber die Mathematiker bevorzugten die axiomatische Mengenlehre…). Seither im Einsatz als theoretischer Unterbau von Programmiersprachen.
Alonzo Church
“There may, indeed, be other applications of the system [the λ-calculus] than its use as a logic.”
Die Syntax des λ-Kalküls
06
Die Menge der Ausdrücke > (expressions) des λ-Kalküls ist rekursiv definiert (@: unendliche Menge von Variablennamen):
• ∀ B ∊ @: B ∊ >
• ∀ ‘1 ∊ >, ‘2 ∊ >: (‘1 ‘2) ∊ > KK
Funktion Argument
• ∀ B ∊ @, ‘1 ∊ >: (λB.’1) ∊ > KK
Parameter Rumpf
[D:EF:<9,G]
[HII9FJ:+F*G]
[H
(λN.N) ∊ > Identitätsfunktion
(λN.O) ∊ > Funktion ignoriert Argument N, liefert z ((P “) N) ∊ > Anwendung von P auf ” und N (Currying) (λP.(P “)) ∊ > Anwendung von Arg P auf ” (H.O.F, Typ i)
┌──┐
(λP.(P “))
KK
Variablen sind entweder U,<)G=,G/VE,F
Verabredete Abkürzung im λ-Kalkül (Currying):
('1 '2 '3 ... 'ₙ) ≡ (⋯(('1 '2) '3) ... 'ₙ) (P " N) ≡ ((P ") N)
Im Ausdruck X1 ≡ ((λ".(P " N)) O) ...
... markiert das λ" die Variable " als Parameter. Damit ist Variable " (an das Argument O) gebunden (bound), aber die Variablen P, N und O sind frei (free).
08
3 ┆ Freie und Gebundene Variablen
Berechne die Menge der freien / gebundenen Variablen in einem λ-Ausdruck:
PY''(B)
PY''(('1 '2))
PY''((λB.'1))
^_`ab(B)
^_`ab(('1 '2))
^_`ab((λB.'1))
={B} = PY''('1) ∪ PY''('2) = PY''('1) \ {B}
=∅ = ^_`ab('1) ∪ ^_`ab('2) = ^_`ab('1) ∪ {B}
λB bindet B
λB bindet B
Beispiel: Freie Variablen in X1 ≡ ((λ".(P " N)) O):
PY''(((λ".((P ") N)) O))
= PY''((λ".((P ") N))) ∪ PY''(O)
= (PY''(((P ") N)) \ {"}) ∪ {O}
= ((PY''((P ")) ∪ PY''(N)) \ {x}) ∪ {O}
= (((PY''(P) ∪ PY''(x)) ∪ {N}) \ {"}) ∪ {O}
= ((({P} ∪ {"}) ∪ {N}) \ {"}) ∪ {O}
= ({P,",N} \ {"}) ∪ {O}
= {P,N,O}.
Bindung/Freiheit muss für jedes Vorkommen einer Variablen separat entschieden werden. Beispiel:
X2 ≡ ("̅(λ".")̲): PY''(X2) = {"̅}, ^_`ab(X2) = {"}̲ KK
frei gebunden
∪∪
\∪
09
Freie und Gebundene Variablen (Beispiele)
4 ┆ Auswertung im λ-Kalkül: β-Reduktion
10
Die Applikation einer Funktion (= λ-Abstraktion) auf ein Argument wird durch β-Reduktion ⇝β beschrieben:
Die Applikation ((λB.'1) '2) wird durchgeführt, in dem 1. eine Kopie des Rumpfes '1 hergestellt wird und
2. alle freien Vorkommen von $ in der Kopie des Rumpfes
%1 durch '2 ersetzt werden.
((λ".P__) ^XY) konstante Funktion ⇝β P__. ╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌ ((λ".((λN.(* N ")) X)) ^) Currying
⇝β ((λN.(* N ^)) X) ⇝β (* X ^).
Auswertung im λ-Kalkül: β-Reduktion
11
Mehr Beispiele für β-Reduktion:
gebunden frei
┌────┐ h
((λ".((* ((λ".(+ " X)) ^)) ")) 7) ersetze VE,F, "
i───────────────j──────k im Rumpf durch 7 freiRumpf
h
⇝β ((* ((λ".(+ " X)) ^)) 7) ersetze VE,F, "
i──j──k im Rumpf durch ^
Rumpf
⇝β ((* (+ ^ X)) 7).
NB: Ohne eine Regel wie apply_prim endet die Reduktion aus der Sicht des λ-Kalküls hier.
Auswertung im λ-Kalkül: β-Reduktion und Variable Capture
Noch mehr Beispiele für β-Reduktion:
Typ i
l───m───n
((λP.(P 7)) (λ".(+ " X))) Programmieren mit H.O.F ⇝β ((λ".(+ " X)) 7)
⇝β (+ 7 X). ╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌ ignoriere 2. Arg, liefere 1. Arg
l───m────n
((((λ".(λN.")) (λO.N)) ↯) X)
12
└┈ i─j──k
ignoriere Arg, liefere N
┌─────┐captured
⇝β (((λN.(λO.N)) ↯) X) D:EF:<9, ⇝β ((λO.↯) X) freies N
müsste insgesamt N liefern...
⇝β ↯.
und wird
z:I+)E, : “wandert” unter λN damit gebunden
Auswertung im λ-Kalkül: Wie funktioniert β-Reduktion genau? '{"→X}: “In ", ersetze freie Vorkommen von # durch $”. Damit
13
gilt dann ((λ".') X) ⇝β '{"→X}:
"{"→X} = X
B{"→X} = B
('1 '2){"→X} = ('1{"→X} '2{"→X})
(λ".'1){"→X} = (λ".'1)
⎧ (λB.'1{"→X})
(λB.'1){"→X} = ⎨⎩ (λB’.'1{B→B’}){"→X} sonst
[→1]
[→2]
[→3]
[→4]
[→5] [→6]
※ Wenn B nicht frei in X ist, kann B nicht gecaptured
werden. Name B’ ist neu (wir brauchen einen Pool von Namen).
B nicht frei in X ※
Auswertung im λ-Kalkül: β-Reduktion im Beispiel
14
Drei β-Reduktionen werten ((((λ".(λN.")) (λO.N)) ↯) X) aus:1
((((λ".(λN.")) (λO.N)) ↯) X)
⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺
⇝β (((λN."){"→(λO.N)} ↯) X)
→6 (((λN’."{N→N’}){"→(λO.N)} ↯) X)
→2 (((λN’."){"→(λO.N)} ↯) X)
→5 (((λN’."{"→(λO.N)}) ↯) X)
→1 (((λN’.(λO.N)) ↯) X)
⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺
⇝β ((λO.N){N’→↯} X) →5 ((λO.N{N’→↯}) X) →2 ((λO.N) X)
⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺
⇝β N{O→X} →2 N.
erwartetes Ergebnis: N
N frei in (λO.N) N’: neuer Name N’ nicht frei in (λO.N)
O nicht frei in ↯
1 ____ markiert den zu reduzierenden Ausdruck (%&'ucible &(pression, redex).
Auswertung eines Ausdrucks ' im λ-Kalkül: Iteriere β- Reduktion, bis ' in seine Normalform überführt wurde:
'istinÜ*E;:9V*E; ⇔ ∄'’∊>:’⇝β’’ i───────j───────k
Beispiele:
”
(λ”.”)
((λ”.”) O)
((λ”.(” “)) (λ”.(” “)))
ist in NF
ist in NF
ist nicht in NF
ist nicht in NF
(und besitzt auch keine)
‘ kann nicht weiter reduziert werden
15
5 ┆ Auswertung im λ-Kalkül: Normalform
Ist es OK, von der (eindeutigen) Normalform zu sprechen?
Beispiel: Reduziere die beiden Redexe in Reihenfolge 12 und 21. Unterscheidet sich das Endergebnis der Reduktion?
⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽1
((λO.(O X)) ((λ”.(λN.”)) ^))
2åβ ((λO.(O X)) (λN.^)) ⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺
⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺2
1hβ (((λ”.(λN.”)) ^) X)
⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺
hβ
((λN.^) X)
⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺
hβ
^ in NF
Zufall? Nein! Satz von Church-Rosser.
åβ
16
Auswertung im λ-Kalkül: Die Normalform ist eindeutig
Auswertung im λ-Kalkül: Satz von Church-Rosser
17
Satz von Church-Rosser: Wenn Ausdruck ‘ sich (in mehreren) Schritten (⇝β∗) zu ‘1 und ‘2 reduzieren lässt, dann gibt es einen Ausdruck ‘’, in den sich ‘1 und ‘2 reduzieren lassen:
β∗ ‘1
‘ è êβ∗’’ Church-Rosser “Diamant” ♢ ê èβ∗
β∗ ‘2
[ohne Beweis]
Konsequenz: Sollten ‘1 und ‘2 in Normalform sein, dann gilt ‘1 = ‘’ = ‘2 (‘i ⇝β∗ ‘’ führt null β-Reduktionen aus). Also ist ‘1 = ‘’ = ‘2 die Normalform von ‘.
6 ┆ Reduktionsstrategie (Redex-Auswahl) Applicative Order
Applicative Order wertet λ-Ausdruck ‘ durch wiederholte β- Reduktion aus. ⟦’⟧k mit maximalem ï ist der nächste Redex:
18
⟦B⟧k ≝ B
⟦(λB.’1)⟧k ≝ (λB.⟦’1⟧k)
⟦(‘1 ‘2)⟧k ≝ Sei P ≡ ⟦’1⟧k+1, dann: ⁎
⎧ ⟦'{B→⟦’2⟧k+2}k+1⟧k ⎨⎩ (P ⟦’2⟧k+1)
P = (λB.’)
sonst
[:*▁ò:E]
[:*▁ô]
[:*▁û]
[:*▁:II9ü]
Applicative Order wertet zuerst den innersten Redex aus (siehe Regel :*▁û, ∗). Damit wird Argument ‘2 ausgewertet, bevor die Funktionsanwendung stattfindet.
19
Reduktionsstrategie Applicative Order kann scheitern Für manche Ausdrücke ‘ findet Applicative Order die
Normalform des Ausdrucks nicht. Beispiel: Reduktion von ((λ”.N) Ω):2
1. Reduktion via Applicative Order:
⟦((λ”.N) Ω)⟧0 = ⋯ = ⟦N{“→⟦Ω⟧2}1⟧0
↻ £ endlose Reduktion,
da ⟦Ω⟧k = ⟦Ω⟧k
2. Reduziere Funktionsanwendung zuerst (Normal Order): ((λ”.N) Ω) ⇝β N.
⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺
2 Ω ≝ ((λ”.(” “)) (λ”.(” “))).
7 ┆ Programmieren im λ-Kalkül: Booleans
Q: Literale und Operationen darauf stehen im λ-Kalkül nicht
zur Verfügung. Kann man damit jemals programmieren? !
A: Ja! Definiere λ-Ausdrücke, die bei Interaktion die erwarteten algebraischen Eigenschaften zeigen. Beispiel:
20
§•¶> ≝ (λ”.(λN.”)) © ̈TM ́> ≝ (λ”.(λN.N)) ≠ا ≝ Übung
®©->TM ́> ≝ (λ”.”)
̈≠Æ ≝ (λX.(λ^.((^ X) ^))) Ø• ≝ Übung
Diese λ-Ausdrücke verhalten sich wie die Booleans:
⟦(((®©->TM ́> §•¶>) N’∞) a_)⟧0 = N’∞
⟦(((®©->TM ́> © ̈TM ́>) N’∞) a_)⟧0 = a_
⟦(( ̈≠Æ © ̈TM ́>) “)⟧0 = © ̈TM ́>
⟦(( ̈≠Æ §•¶>) “)⟧0 = ”
21
8 ┆ Programmieren im λ-Kalkül: Paare, Selektoren und Listen
Repräsentation von Paaren ⟨”,N⟩ im λ-Kalkül:
≥ ̈®• ≝ (λ”.(λN.(λ∞.((∞ “) N))))
́≠Æ ≝ (λ¥.(¥ (λ”.(λN.N))))
© ́§ ≝ (λ¥.(¥ (λ”.(λN.”))))
i────j────k
§•¶> ¥
Repräsentation von Listen (make-pair ” “∞) und empty:
⟨© ̈TM ́>,⟨”,”∞⟩⟩
l─────────────m────────────n
μ ̈∂>-≥ ̈®• ≝ (λ”.(λ”∞.((≥ ̈®• © ̈TM ́>) ((≥ ̈®• “) “∞))))
⟨”,N⟩
( ́≠Æ ⟨”,N⟩) ⇝ N (© ́§ ⟨”,N⟩) ⇝ ”
i─j─k
©®• ́§
•> ́§
>μ≥§∑?
>μ≥§∑
≝ (λ”∞.(© ́§ ( ́≠Æ “∞)))
≝ (λ”∞.( ́≠Æ ( ́≠Æ “∞)))
≝ © ́§
≝ ® (>μ≥§∑? >μ≥§∑) ⇝ (® §•¶>) ⇝ §•¶>
9 ┆ Programmieren im λ-Kalkül: Church Numerals
Existiert eine Repräsentation der natürlichen Zahlen {0,1,2,
…} im λ-Kalkül, die arithmetische Operationen erlaubt?
Definition: ã ist das Church Numeral für a ∊ N:
ã ≝ (λP.(λ”.(Pn “)))
= (λP.(λ”.(P ⋯ (P (P “))⋯)))
i────────j───────k
a-fache Applikation von P
Beispiele:
0̃̃ ≡ (λP.(λ”.”))
1̃ ≡ (λP.(λ”.(P “)))
2 ≡ (λP.(λ”.(P (P “))))
⋮
22
” ist Fixpunkt von Funktion P, falls P(“) = ” gilt. Beispiele (reelle Funktionen):
23
10 ┆ Rekursion im λ-Kalkül: Fixpunkt von Funktionen
P(“) = “2
P(“) = ” + 1
P(“) = ”
zwei Fixpunkte: ” = 0, ” = 1
kein Fixpunkt
unendliche viele Fixpunkte
Im λ-Kalkül hat jede Funktion ‘ einen Fixpunkt: (∑ ©).
Sei ∑ ≝ (λP.((λ”.(P (” “))) (λ”.(P (” “))))). Dann gilt:
(© (∑ ©)) = (∑ ©) (∑ ©) ist Fixpunkt von ©
24
Rekursion im λ-Kalkül: Der (-Kombinator
=
(∑ ©) ⎺
((λP.((λ”.(P (” “))) (λ”.(P (” “))))) ©)
⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺
(Y F) = (F (Y F))
(Y F) = (F (Y F))
(Y F) = (F (Y F))
(Y F) = (F (Y F))
(Y F) = (F (Y F))
MIT Scheme
= (© (∑ ©)).
Zu ⇜β: Es gilt: ‘ = ((λP.'{©→P}) ©) (β-Abstraktion).
∑ ist Haskell B. Curry’s (-Kombinator, den wir einsetzen können, um Rekursion im λ-Kalkül auszudrücken.
⇝β ((λ”.(© (” “))) (λ”.(© (” “)))) ⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺
⇝β (© ((λ”.(© (” “))) (λ”.(© (” “))))) ⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺
⇜β (© ((λP.((λ”.(P (” “))) (λ”.(P (” “))))) ©)) ⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺
Rekursion im λ-Kalkül: Beispiel Fakultätsfunktion )!
25
λ-Ausdruck (© ̈Ω a) berechnet die Fakultät )! rekursiv:
© ̈Ω ≝ (λa.(((®©->TM ́> (® ́æ>•Ø? a)) Rekursion ø̃) ¿
((μ¶TM§ a) (© ̈Ω (≥•>Æ a)))))
┊
⇜β ((λP.(λa.(((®©->TM ́> (® ́æ>•Ø? a))┊ ø̃) ┊
((μ¶TM§ a) ( P (≥•>Æ a)))))) © ̈Ω)
i─────────────────────j──────────────────────k
≡©
Es gilt also © ̈Ω = (© © ̈Ω) ⇒ © ̈Ω ist Fixpunkt von ©. Definiere die Fakultätsfunktion als © ̈Ω ≝ (∑ ©).
Rekursives P. © ≡ β-Abstraktion von P. P ≝ (∑ ©).
Rekursion im λ-Kalkül: Eine Reduktionsstrategie für (
26
Applicative Order führt für (∑ ©) zu endloser Reduktion: ((∑ ©) a͠0) ⇝ ((© (∑ ©)) a͠0) ⇝ ((© (© (∑ ©))) a͠0) ⇝ ⋯ ∞
⎺⎺⎺⎺⎺ ⎺⎺⎺⎺⎺ ⎺⎺⎺⎺⎺
Benötigt: eine Reduktionsstrategie, die Funktionsanwendung vor Funktionsargumenten reduziert. Etwa Normal Order:3
‘1[((∑ ©) a͠1)] ⇝ ⋯ ͠ ͠ è ⎺⎺⎺⎺⎺
((∑ ©) a0) ⇝ ((© (∑ ©)) a0) ⇝ © entscheidet
⎺⎺⎺⎺⎺ ⎺⎺⎺⎺⎺⎺⎺⎺⎺ ê ⎺⎺⎺⎺⎺⎺
‘2[a͠0]. Rekursionsabbruch 3 ‘1[‘] bezeichnet einen Ausdruck ‘1, in dem ‘ als Teilausdruck vorkommt.
⚠
11 ┆ Reduktionsstrategie Normal Order4
⟦B⟧k ≝ B
⟦(λB.’1)⟧k ≝ (λB.⟦’1⟧k)
⟦(‘1 ‘2)⟧k ≝ Sei P ≡ ⟬’1⟭k+1, dann:
⁎
⎰ ⟦'{B→’2}k+1⟧k
⎱ (⟦P⟧k+1 ⟦’2⟧k+1)
P = (λB.’)
sonst
[G*▁ò:E]
[G*▁ô]
[G*▁û]
[G*▁:II9ü]
27
Intern nutzt Regel G*▁û die Call by Name Reduktion ⟬⟭k:
⟬B⟭k ≝ B
⟬(λB.’1)⟭k ≝ (λB.’1)
⟬(‘1 ‘2)⟭k ≝ Sei P ≡ ⟬’1⟭k+1, dann:
⁎
⎰ ⟬'{B→’2}k+1⟭k
⎱ (P ‘2)
4 Verfügbar als Funktion no im File definitions-13.rkt.
P = (λB.’)
sonst
[