Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Probeklausur
Hallo,
wie bereits angelegentlich bemerkt, steht der Klausurtermin (zumindest das Datum) mittlerweile in mein campus. Ferner ist jetzt auch die Probeklausur online, siehe Veranstaltungshomepage.
Herzliche Grüße,
Lutz Schröder
5 „Gefällt mir“
Fehler?
Hallo,
kann es sein, dass sich in den definierten Funktionen der Aufgabe 2 der Probeklausur folgender Fehler eingeschlichen hat?:
succ n = λ n f a . f ( n f a ) //Das rote n müsste ergänzt werden
[quote=kawa_blue]kann es sein, dass sich in den definierten Funktionen der Aufgabe 2 der Probeklausur folgender Fehler eingeschlichen hat?:
succ n = λ n f a . f ( n f a ) //Das rote n müsste ergänzt werden[/quote]
Das passt schon so. (Übrigens auch zu finden auf Übungsblatt 2 - Aufgabe 4.)
Deine Notation beschreibt die Funktion [m]succ[/m].
Auf der linken Seite steht aber [m]succ n[/m], was quasi schon die Anwendung der Funktion [m]succ [/m]auf [m]n[/m] ist. Dadurch erhälst du auf der rechten Seite eine freie Variable [m]n[/m] (die halt schon eingesetzt wurde).
Du hast also zwei Möglichkeiten, das zu schreiben:
- succ n = λ f a . f ( n f a )
- succ = λ n . λ f a . f ( n f a ) = λ n f a . f ( n f a )
(siehe auch: Vorlesung 6 ab 1:16:00)
1 „Gefällt mir“
ich denke, dass
succ n=λfa.f(nfa) dasselbe ist wie
succ=λnfa.f(nfa)
was ich aber nicht weiss ist, ob man das in der Klausur dann auch so machen darf (oder gar muss).
(also: einfach succ ersetzen statt succ n)
Weiss es irgendwer von euch sicher?
//edit: zu langsam, aber immerhin richtig gedacht…
danke an ceptoplex 
[quote=sushi]was ich aber nicht weiss ist, ob man das in der Klausur dann auch so machen darf (oder gar muss).
(also: einfach succ ersetzen statt succ n)[/quote]
Wenn in der Klausur dasteht [m]succ succ n[/m] und man das βδ-reduzieren soll, dann gehst du je nach Angabe der Regel ein bisschen anders vor. Um genau zu sein, unterscheidet sich [m]succ [/m]und [m]succ n[/m] ja nur in einer β-Reduktion, die man theoretisch mehr machen müsste. (Hier mal anschaulich mit allen Schritten in applikativer Reihenfolge.)
Für succ n = λ f a . f ( n f a ):
→δ succ succ λ f a . a
→δ succ λ f a . f ( ( λ f a . a ) f a )
→ββ succ λ f a . f a
→δ λ f a . f ( ( λ f a . f a ) f a )
→ββ λ f a . f ( f a )
Für succ = λ n f a . f ( n f a ):
→δ succ succ λ f a . a
→δ succ ( λ n f a . f ( n f a ) ) λ f a . a
→β succ λ f a . f ( ( λ f a . a ) f a )
→ββ succ λ f a . f a
→δ ( λ n f a . f ( n f a ) ) λ f a . f a
→β λ f a . f ( ( λ f a . f a ) f a )
→ββ λ f a . f ( f a )
Dieser eine β-Reduktionsschritt wäre bei [m]succ x[/m]:
succ x →δ ( λ n f a . f ( n f a ) ) x →β λ f a . f ( x f a )
EDIT: Falsche Klammerung, siehe übernächster Post.
1 „Gefällt mir“
Omg thx, hab mich verlesen. Danke 
@cyptoplex:
ok, hab das auch so. Nur die Klammerung deines Ergebnisses ist denke ich nicht richtig, weil Currying:
ffa ≡ (ff)a ≢ f(fa)
Du hast recht.
Ich hab das oben mal nachträglich korrigiert, nicht dass Leute verwirrt sind, wenn sie das lesen.
Ich war da mit meinen Gedanken noch beim λ, wo die Klammer ja bis ans Ende geht. Bei der Applikation ist das ja aber nicht so.
kann mir evtl. mal jemand mit der Aufgabe zur strukturellen Induktion auf die Spruenge helfen?
ich verstehe naemlich schon den Datentyp nicht so recht. Was genau bedeutet
data List a = Nil | Cons aGenauer: Was macht das “Cons a”? Spaeter in der Aufgabe kommt immer nur ein Cons x xs (also mit zwei Parametern) vor, wenn ich das richtig sehe, und da verhaelt es sich dann so, wie x:xs in Haskell. Das kenn ich, das kann ich benutzen.
Aber was bedeutet Cons a?
Wie kann man das denn fuer irgendwas einsetzen?
// ist ein Fehler in der Angabe laut Tutoren grad… muss heissen: data List a = Nil | Cons a (List a)
Das Cons a sieht für mich auch komisch aus, vielleicht kann das ja jemand anderes erklären. Meine Vermutung ist einfach dass das bedeuten soll, dass Cons auf Listen arbeitet die Elemente vom Typ a enthalten.
Cons müsste den Typ (a → List a → List a) haben. Oder einfach ausgedrückt: Nimm eine List von Elementen vom Typ a und hänge vorne ein weiteres Element vom Typ a dran, und gib das Ganze dann wieder als Liste zurück.
Das e dass man da einsetzten muss, muss dann auch vom Typ a sein.
Neue Version
Hallo,
zur Behebung der in der Fragestunde aufgefallenen Unklarheiten findet sich nunmehr eine neue Version der Probeklausur (mit zwei neuen Hinweisen und Korrektur eines Tippfehlers) auf der Homepage.
Herzliche Grüße,
Lutz Schröder
Falls die Klausur noch nicht gedruckt ist: Ich würde mich freuen, wenn Definitionen oder Gleichungen in der Angabe nummeriert sind, sodass man sie bei Beweisen oder Erklärungen einfach referenzieren kann.
1 „Gefällt mir“
wenn ich jetzt bei applikativer Reduktion so etwas wie
a (b c) d
habe, welche Definition setze ich dann zuerst ein - die von c, oder die von d?
Wenn ich das richtig verstanden habe, setzt du die applikative Reduktion von (b c) zuerst ein - also c. Danach die von b, danach die von d, danach die von a
Ich würde Hasenichts zustimmen für das Beispiel und noch was anderes in den Raum werfen:
Wenn wir Folgendes haben:
a b (c d)
Dann ist die Reihenfolge bei applikativer Reduktion der eingesetzten Werte doch b, d, c - richtig?
(Weil wir im Lambda-Kalkül ja bei Funktionen mit mehreren Parametern (Stichwort Currying) ja auch immer von links nach rechts die ß-Reduktionen abgearbeitet haben.)
EDIT: Es heißt ja “leftmost innermost”. Und wenn man mit d anfangen würde wäre es ja “innermost leftmost”. Wenn man mit dem d anfangen würde, ginge das ja nur bei der Klammerung: a ( b ( c d ) ). Aber die Klammerung von oben ist ja implizit: ( a b ) ( c d ). Oder?
EDIT: Ich glaube jetzt hab ich das gesagt, was ich wollte. 
Stimme Hasenichts und ceptoplex zu, aber das ist nur meine Intuition
Les dir meinen Post nochmal durch. Bei Hasenichts wäre ja dann auch ein Fehler drin, wenn es nach der unteren Theorie von mir ginge.
Hab’s alles mal richtig reineditiert, sorry dass ich deine Antwort erst jetzt gesehen hab.
EDIT: Vergesst einfach alles.
Ich werde nichts mehr editieren.
Mein erster Post war doch korrekt.
heh, das wird ein Spaß
passend zum Thema hier mal meine Lösung zur 2.1 der Probeklausur: http://ente.hawo.stw.uni-erlangen.de/~ki08jofa/thprog.jpg
Haltet ihr das für richtig?
Und, bei der applikativen Reduktion, ist da Schritt 4 oder Schritt 4’ der richtige (4’ sieht mult x y = bla als mult = lam x y . bla an, 4 macht dummes Patternmatching).
Außerdem: habe ich die Schrittanzahlen richtig gezählt?
Ich halte 4’ für korrekt, da wir intuitiv betrachtet bei applikativer Reduktion erst versuchen müssen, den ersten Parameterso weit wie möglich auszuwerten (das heißt in diesem Fall: [m]mult [/m]ersetzen), bevor wir mit dem zweiten Parameter weiter machen (also [m]one [/m]ersetzen).
Meine Begründung: Es heißt “leftmost innermost”.
Das mit der Schrittzahl würde mich auch interessieren.
Für mich heißt 4 Beta-Delta-Reduktionsschritte auch (wie in Windfischs Lösung), dass auch Nur-Delta-Schritte da dazuzählen - und nicht nur Schritte, in denen eine Beta-Reduktion stattfindet. Ist aber auch nur meine Meinung.