Alles getestet.
Auch kalibriert.
Ich begrüße Sie zur Vorlesung Informatik 1.
Ich möchte an der Stelle, da sollten Sie vielleicht aufpassen, ein
paar Sachen, die vielleicht nicht ganz unwichtig sind.
Das Erste ist die Klausuranmeldung.
Der Herr Scholderer hat Ihnen ja wohl letzten Mittwoch gesagt, dass
heute die Zettel ausgeteilt werden oder zur Verfügung stehen.
Das machen wir am Mittwoch in der Zentralübung.
Und da können Sie sich eben dann zur Klausur anmelden.
Das Zweite ist, vom Herrn Polik soll ich ausrichten, das ist der
Lehrer, der hier die Schüler betreut, dass die Schüler bitte nach Ende
dieser Veranstaltung noch sich hier sammeln sollen, weil er Ihnen was
zu sagen hat.
Vielleicht sollte ich dazu auch noch einen Punkt sagen, dass wir hier
schon seit längerem mit den Schulen im Umkreis erfolgreich
zusammenarbeiten, nämlich es sind ca.
30 Schüler, sind hier beteiligt in der Informatik 1-Vorlesung und
haben die Möglichkeit, auch an der Klausur teilzunehmen, auch als
Schüler schon mal in den Vorlesungsbetrieb reinzuriechen.
Und das ist ein ganz erfolgreiches Projekt, was wir in den letzten
Jahren schon durchgeführt haben.
Und ich wünsche den Schülern und Schülerinnen alles Erfolgreiche und
Gute, genauso wie Ihnen für die Klausur, dass Sie das hier also
bestehen.
Gut, kommen wir nochmal zum... jetzt vielleicht die dritte Anmerkung.
Das ist eine inhaltliche Anmerkung, die ich gerne machen würde, zu dem
Stoff, den wir zurzeit bearbeiten.
Ich habe das noch nicht... können Sie ein bisschen ruhiger sein,
bitte.
Ich habe das nicht explizit gesagt, aber Sie haben das sicherlich über
das Lernsystem schon mitbekommen.
Wir haben ja jetzt von dem Großbuch, sind wir übergewechselt in den
Bräuteil.
Also vielleicht hat sich der ein oder andere von Ihnen auch schon mal
das Buch angeschaut oder sogar besorgt.
Ich möchte an der Stelle mal ganz deutlich machen, in welcher Art und
welche Qualität von Einführungsstoff es sich hier handelt.
Der Herr Goos und auch der Herr Bräu, die gehören nicht nur
deutschlandweit, sondern europa- und weltweit zu führenden
Informatikexperten in dem Einführungsbereich.
Das sind absolute Standardbücher, die wir hier durcharbeiten.
Etablierte und auch fundierte Arbeiten, die Sie hier finden.
Der Herr Bräu als Beispiel ist der renommierteste Informatikprofessor,
den wir deutschlandweit haben.
Er ist Leibnizpreisträger.
Das ist vergleichbar fast für Informatiker mit dem Nobelpreis.
Er ist aus dem Bereich Software Engineering.
Er arbeitet und lehrt an der TU München, wo ich auch mein Studium
gemacht habe.
Das hat damit nichts zu tun.
Ich habe den Herrn Bräu nicht mehr kennengelernt so richtig.
Auf jeden Fall nicht als Student.
Ich wollte Ihnen nur sagen, dass wenn Sie gewisse Zweifel haben an dem
Stoff, dass das gegebenenfalls mit einer falschen Erwartungshaltung
Ihrer Seite zu tun hat.
Diese Einführungsveranstaltung ist ganz bewusst nicht als
Programmierkurs zu verstehen.
Sie werden genügend programmieren.
Sie haben ja auch in der Übung schon erste Programmiererfahrungen
gesammelt.
Da ist der Spektrum beliebig weit.
Das kann ich Ihnen nur an der Stelle sagen.
Es gibt sehr viele Leute, die gerne erstmal hingeführt werden zur
Programmierung.
Auch hingeführt werden wollen sie den Programmierkonzepten.
Es gibt natürlich andere von Ihnen, das ist klar, die jetzt sozusagen
einen ausgereiften Java-Kurs sich erwartet hätten.
Versuchen Sie Ihre Erwartungshaltung, was das angeht, was
Programmierung angeht, was aus Ihrer Sicht Praxis bedeutet.
Versuchen Sie das zumindest ein wenig mit dem Stoff, den wir hier
bearbeiten, in Einklang zu bringen.
Versuchen Sie sich dem anzunähern.
Weil die Dinge, die Sie hier hören und die ich hier versuche Ihnen zu
vermitteln, sind relevante Grundlagen, die Sie wirklich brauchen für
Ihr Informatikstudium.
Und wie gesagt, da kommt Programmierung genug vor, da kommen
praktische Industrieprojekte dazu.
Sie brauchen aber diese fundierten Grundlagen, die wir hier im Rahmen
dieser Einführungsveranstaltung bearbeiten.
Und nochmals gesagt, das ist nicht auf meinen Mist gewachsen, was wir
hier bearbeiten, sondern das ist fundiert von den wichtigsten Leuten,
die wir in dem Bereich überhaupt haben.
Und ich habe es auch schon von anderer Seite mal gehört, das wäre
altmodischer Kram oder sowas.
Das ist neueste Literatur, das sind neueste Konzepte, die Sie sich
hier wiederfinden.
Und das ist der Stand, den wir heute als Grundlagen, wenn wir
Informatik als Wissenschaft verstehen, was wir jedem als Stand
vermitteln können, als Grundlagen in die Informatik einführen, in die
Informatik.
Soviel als nochmal vorbereitende Bemerkung.
Um das auch nochmal deutlich zu machen, wir sind sozusagen jetzt von
dem Lambda-Kalkül, wie wir eine konkrete Programmiersprache, eine
funktionale Programmiersprache, zu einer Abstraktionsebene jetzt
gelangt, wo wir sozusagen die Sprachkonzepte von funktionalen
Programmiersprachen, von funktionalen Sprachen verstehen wollen.
Und wir gehen nach einem ganz einheitlichen Schema hier vor.
Wir schauen uns erstmal das gesamte Programm an.
Sie erinnern sich an Folie 3 von diesem Abschnitt, wo wir die ganze
Sprache, also erstmal sozusagen die oberste Ebene der Grammatik
kennengelernt haben, in Form von dieser Bacchus-Lauer-Form, und
arbeiten jetzt sozusagen die einzelnen Sprachelemente ab und
interessieren uns an der Stelle immer für einmal syntaktische
Fragestellungen, also wie schreibt man so ein Sprachelement hin, und
dann noch viel wichtiger die Frage, was bedeutet, was wollen wir mit
diesem Sprachkonzept ausdrücken, also die Semantik dieses
Sprachkonzeptes.
Und wir sind jetzt eben angekommen bei der Funktionsapplikation, die
sollte Ihnen aus dem Lambda-Kalkül heraus, aus der Sprache Woffe
heraus, schon bekannt sein.
Und wir wollen uns eben jetzt hier anschauen, wie wir die Semantik
vernünftig beschreiben können und wie wir die hinschreiben können.
Und Semantik heißt eben nichts anderes, als dass wir eine Abbildung,
eine Interpretationsabbildung von diesem syntaktischen Konstrukt auf
mathematische Objekte, auf formale Objekte erreichen.
Und wir haben hier an der Stelle, das habe ich auch schon beim letzten
Mal angedeutet oder Ihnen gesagt, wir haben hier jetzt dieses kleine f
eingeführt, das eben sozusagen die Interpretation von unserer Funktion
Groß f unter der Belegung Beta darstellt.
Und das ist letztendlich diese Abbildung, die wir hier auf eigentlich
alle Elemente anwenden, die wir in der Funktionsapplikation haben und
eben dieses kleine f, das die Interpretation von diesem
Funktionssymbol Groß f wiedergibt.
So, jetzt kommt ein ganz wichtiger Aspekt, wie die Auswertung des
Funktionsaufrufs erfolgen kann oder erfolgen soll.
Und hier haben wir jetzt zwei grundsätzlich verschiedene Aufrufe, die
da heißen Call-by-Value und Call-by-Name.
Und das Call-by-Value bedeutet folgendes.
Call-by-Value drückt aus, dass wir einen Funktionsaufruf mit dem Wert,
daher kommt das Value, der Parameter.
Und es geht um Funktionsaufrufe und die Frage, wie wir letztendlich
mit den Parametern, wie wir uns da verhalten.
Und dieser Wert der Parameter drückt letztendlich aus, dahinter
steckt, dass alle Argumente, Ausdrücke sind sozusagen vor Aufruf
Ausführung auszuwerten.
Statt Aufruf Auswertung könnte man auch Rumpf Ausführung sagen.
Das heißt, wir müssen erstmal alle Werte bestimmen von diesen
Parametern.
Und da steckt auch nochmal ein wichtiger Aspekt drin, das können ganze
Ausdrücke sein.
Das kann sogar so weit gehen, dass Sie darin wieder Funktionsaufrufe
erstmal haben, Sie damit also relativ intensiv beschäftigt sind, bis
Sie diesen Wert überhaupt ermittelt haben.
Und erst dann kann ich sozusagen diese Funktion, also die Ausführung
des Aufrufes durchführen, beziehungsweise in den Rumpf reingehen und
den Rumpf bearbeiten.
Das ist also die eine Möglichkeit, nennen wir Call by Value.
Zuerst werden in beliebiger Reihenfolge, das ist auch nochmal hier
wichtig, Sie müssen also nicht von links nach rechts vorgehen, sondern
kann sich der Compiler dann auch überlegen, wie er da die Reihenfolge
auswertet.
Aber die müssen zuerst ausgewertet werden, bevor Sie sich an die
eigentlichen Funktionen machen können.
So und Call by Name drückt jetzt genau das Gegenteil aus, nämlich dass
Sie da nicht so eine harte Randbedingung an diesen Funktionsaufruf
stellen, sondern Sie fangen einfach mal mit der Auswertung des
Funktionsaufrufes an und werten die Parameter sozusagen on demand aus.
Das heißt, Sie werten sie erst dann aus, wenn sie wirklich gebraucht
werden.
Und das bedeutet, können wir hier vielleicht einfach dazufügen,
Parameter werden bei Bedarf ausgewertet.
Und bei Bedarf ist klar, das heißt nichts anderes als dann, wenn sie
gebraucht werden in dem Rumpf, wenn sie angesprochen werden, dann
braucht man die Werte und dann muss man sich um die Auswertung der
Parameterausdrücke kümmern.
Das haben wir schon kennengelernt.
Wenn Sie also als Beispiel hier dieses if-then-else nochmal sich
anschauen und hier diese nichtstrickte Auswertung, dann haben Sie da
genau dieses Beispiel.
Da sagen Sie nämlich, da haben Sie ja die Bedingungen und ein e1 und
ein e2, das sind ja diese drei Parameter.
Da sagen Sie nämlich genau, erst brauche ich die Bedingung, die kommt
ja hier nach dem if vor.
Ich gehe einfach mal in das if-then-else rein, fange also mit dem
Rumpf an und dann kommt als erstes die Bedingung, mit der muss ich
mich rumschlagen, die muss ich auf jeden Fall bearbeiten, sonst kann
ich nie weitermachen.
Und dann wird ja in Abhängigkeit, wie die Bedingung aussieht, gehe ich
entweder nur in den sen-Zweig oder in den else-Zweig.
Das heißt, ich lasse einen von den Parametern auf jeden Fall, außer,
schaue ich mir nicht an und da ist eben kein Bedarf und der wird eben
da nicht ausgewertet.
Das sind die beiden unterschiedlichen Aufrufeformen, call-by-value,
call -by-name.
Wenn Sie also in allen höheren Programmiersprachen, werden Sie diese
beiden Arten grundsätzlich finden.
Es gibt noch ein weiteres, das ist das call-by-reference, aber da
gehen wir zusammen mit zuweisungsorientierter Programmierung ein.
Das hat was mit Variablen zu tun und Pointern auf Variablen zu tun.
Schauen wir uns die Identifikatoren in Funktionen an.
Also jetzt nicht nur allgemein Identifikatoren, die haben wir ja schon
betrachtet, sondern solche, die in Funktionen auftreten.
Das ist ja die Normalität in funktionalen Programmiersprachen.
Und die Identifikatoren, die haben ja immer die Funktion eines
Platzhalters.
Das ist also in Funktionen genauso gegeben.
Und Platzhalter bedeutet nichts anderes als, dass sie für einen Wert
stehen, den ich an einer bestimmten Stelle deklariere oder angebe und
den kann ich dann eben später einsetzen, wenn dieser Identifikator in
einem Ausdruck vorkommt.
Und da haben wir also den Vergleich mit der Mathematik.
Da werden genau solche Identifikatoren oder Platzhalter immer wieder
eingeführt.
Wenn wir sowas haben, sei x ein Element der Menge m mit dem Wert.
Und das ist genau das Beispiel, also ist eine mathematische
Vorgehensweise, die hier eben in diesen Identifikatoren in Funktionen
bindet.
Und jetzt interessiert uns eben hier die Frage, wie das jetzt im
Zusammenhang mit Funktionen aussieht, diese Identifikatoren.
Und da soll dieses einfache Beispiel Ihnen einfach in diese Richtung
lenken.
Wir haben hier eine Funktion, die natürliche Zahlen aufeinander
abbildet.
Und dann haben wir hier eine Gleichung, das ist sozusagen der Rumpf
dieser Funktion.
In dem Beispiel x mal x plus 1, x ist dann aus den natürlichen Zahlen.
Und das führt dann letztendlich unmittelbar zu den
Funktionsdeklarationen.
Ich brauche also hier die Identifikatoren, um so eine
Funktionsdeklaration durchzuführen.
Und die Funktionsdeklaration, die besteht aus zwei Dingen.
Zum einen aus der Typangabe von Definitions- und Wertebereich.
Das ist die Funktionalität.
Und das zweite, und da kommen jetzt genau die Identifikatoren ins
Spiel, beziehungsweise sie sind hier schon oben in dem Kopf angegeben.
Das sind eine die Funktion, eine die Funktion definierende Gleichung.
Das heißt, das funktioniert alles nur auf Basis der Einführung von
Identifikatoren.
Sonst kann ich sozusagen gar keine Funktion deklarieren, kann ich
keinen Funktionsrumpf bilden.
Also Identifikatoren sind hier sozusagen die Grundlage, um überhaupt
eine Funktionsdeklaration durchzuführen.
Also Typangabe von Definitions- und Wertebereich.
Das ist jetzt genau diese Stelle hier, das ist 1.
Und an der Stelle haben wir jetzt den 2, die definierende Gleichung.
Kennen Sie alles schon von der Lambda-Kalkül von Gopher?
Wir wollen wie gesagt jetzt hier dieses Sprachelement nochmal auf
einer Programmiersprachenebene einführen und beleuchten.
Und insofern ist klar, dass wir jetzt hier mit diesen Mechanismen oder
Konzepten, die wir vom Lambda-Kalkül erkennen, die treten hier
selbstverständlich wieder auf.
Aber eben auf einer allgemeinen Programmiersprachenebene.
Wir haben also auch hier die Frage der Gebundenheit und der Freiheit
von Identifikatoren zu behandeln.
Und das können wir also sehr schnell abhaken, hier diese Erkenntnis,
dass wir durch diese Funktionsdeklaration, jetzt kommt nochmal eine
notationelle Repräsentation, die wir noch einführen können, wir können
also auf den Funktionsnamen verzichten.
Das ist genau hier passiert.
Sie finden hier an der Stelle kein F oder irgendwie eine andere
Bezeichnung.
An der Stelle, ohne eine Funktionsbezeichnung einzuführen, können Sie
so ein Konstrukt hinschreiben.
Und hier, im Zusammenhang mit diesem Konstrukt, binden wir diesen
Identifikator X, das ist genau dieses Prinzip, wie Sie es beim Lambda
-Ausdrücken vorsehen, im Gegensatz zur Freiheit.
Das heißt, wenn Sie ein Beispiel hätten, dass das X gieße X plus Y und
der Kopf bleibt der gleiche, hätten Sie sozusagen nur das X dort
gebunden und das Y wäre frei.
Das heißt, dieses wäre dann ein freies Vorkommen eines Identifikators,
weil Sie das nicht im Kopf, in der Funktionalität hier im ersten Teil
angeben, in der Funktionsbeschreibung.
X ist syntaktisch durch die Kennzeichnung NatX als Platzhalter
ausgezeichnet.
Also ein Platzhalter, den ich hier einführe, den ich dann besetze.
Und die Belegung dieses Wertes erfolgt dann durch die
Funktionsapplikation.
Das ist also eine spezielle Art, wie ich diesen Identifikator mit
einem Wert belege.
Diese konsistente Ersetzung, das ist genau diese Alpha-Konversion, die
wir hier schon kennengelernt haben.
Wir können also solche gebundenen Identifikatoren konsistent ersetzen.
Also diese Gebundenheit ist wichtig, sonst können Sie die Ersetzung
nicht durchführen.
Und Sie müssen immer beachten, dass Sie mit freien Auftritten von
Identifikatoren in dem Ausdruck, den Sie betrachten, dass Sie da nicht
in Konflikt kommen.
Das heißt, Sie können durchaus, wenn Sie von diesem Beispiel hier oben
ausgehen, dann können Sie das X gegen Y konsistent ersetzen.
Währenddessen, wenn Sie von diesem Beispiel hier ausgehen, von diesem
zweiten, das ich Ihnen hier hingeschrieben habe, dann müssen Sie das
Y, müssen Sie das freie Auftritten von dem Y beachten.
Dann können Sie eben hier keine Ersetzung von dem X in der Form
durchführen.
Und Sie müssten erstmal dieses Y entsprechend umbenennen.
Das heißt, Sie müssten sozusagen dieses X mal X plus Y, da müssen Sie
sozusagen mit einer Alpha-Konversion erstmal X mal X plus Y
durchführen.
Und dann können Sie hier dieses Y ersetzen.
Oder Sie müssen sich sozusagen eine andere Bezeichnung für diese
Ersetzung vorstellen.
Das heißt, dass Sie das X gegen Z oder Y Strich ersetzen oder Y2
ersetzen oder dergleichen.
Das sind also genau die gleichen Mechanismen, genau die gleichen
Vorgehensweisen, Regeln, die wir kennengelernt haben, die Sie eben an
dieser Stelle für die funktionale Programmiersprache anwenden können.
Sozusagen nur diese Übertragung von dem Lambda-Ausdruck in ein solches
Programmiersprachlöskonstrukt.
Das ist allerdings, kommt hier noch ein Aspekt dazu, das werden wir
auf einer letzten Folie in dem Abschnitt auch behandeln, das ist nicht
typfrei.
Das sind ja Tüten und die kommen hier zu dem Lambda-Kalkül eben noch
hinzu.
Ansonsten ist das aber vollkommen identisch.
Die Funktionsabstraktion, das ist das, was ich Ihnen schon gerade
gesagt habe, dass Sie also hier so eine Schreibweise einführen können,
die auf eine Funktionsbezeichnung verzichtet.
Und jetzt können wir hier an der Stelle nochmal dieses Sprachelement
der Funktionsabstraktion.
Ich schreibe es nochmal hier hin.
Wir behandeln die ganzen Konzepte hier als Sprachelemente einer
funktionalen Programmiersprache.
Sie sehen, das ist auch Teil dieser BNF-Notation, da kommt eben
Function Abstraction, dieses Non-Terminal.
Das wird jetzt eben hier nochmal enger, tiefer beleuchtet.
Sie können entsprechend diese Komponenten dieses Sprachelementes
analysieren.
Sie müssen an der Stelle wegen der Typgebundenheit beachten, dass das
E eben ein Ausdruck der Sorte S ist.
Das heißt, dieses S ist ja nichts anderes als die Ergebnissorte.
Und Sie müssen beachten, dass das Ergebnis, also das, was sozusagen
bei dem Wimpf, bei dem E herauskommt, zum Ausdruck dieser
Ergebnissorte entspricht.
Und wir reden dann eben, E ist Ausdruck einer bestimmten Sorte.
Von einer Sorte ist ein äquivalenter Begriff dazu der Typ.
Die x1 bis xn sind die formalen Parameter dieser Funktionsabstraktion.
Und jetzt kommen wir genau zu diesen Begriffen, die ich schon genannt
habe.
Nämlich, Sie reden hier von einer Kopfzeile, das ist der Kopf.
Und Sie reden bei dem E von einem Rumpf.
Das sind also die beiden Begriffe, die wir hier einführen.
Entsprechend die englischen Begriffe Kopf übersetzt als Head und Rumpf
übersetzt als Body.
Das sind also die zwei Bestandteile, aus denen diese
Funktionsabstraktion sich zusammensetzt.
Hier ist nochmal dieser Begriff des Rumpfes und des Kopfes oder der
Kopfzeile genannt.
Die Syntax an der Stelle ist auch nicht viel zu sagen.
Sie können hier also beliebig viele Identifier anfügen.
Wichtig ist hier nochmal, um zu verstehen, welche Bedeutung hier diese
geschwungenen Klammern haben.
Gegebenenfalls auch kein Parameter ist hier möglich.
Das wird also durch diese geschwungenen Klammern angegeben.
Hier sollten Sie eben entsprechend noch die Bacchus-Nauer-Form wieder
parat haben.
Das ist also eine Sache, die Sie auch für die Klausur unbedingt kennen
müssen, damit Sie sowas formal hinschreiben können.
Also diese Bacchus-Nauer-Form, die ja überall, fast an vielen Stellen
in der Vorlesung auftritt, die haben wir in einer der ersten Kapitel
behandelt.
Die habe ich dann nochmal vertieft in Kapitel 4.
Und hier wird das ja ständig eingesetzt, Bacchus-Nauer-Form, um die
Syntax zu beschreiben.
Jetzt kommen wir zur Semantik.
Und da werden wir eben diese beiden Arten von Semantik hier
betrachten.
Erstmal die funktionale Semantik.
Und dann werden wir uns mit der operationalen Semantik auch noch
beschäftigen.
Und da kommen wir wieder zu dem Call-By-Value und Call-By-Name.
Zu diesen beiden Arten der Parameter-Auswertung.
Die Funktionsabstraktion und die Funktionsapplikation hängen also eng
miteinander zusammen.
Man führt eine Funktionsabstraktion letztendlich ein, damit man diese
Funktion auch anwenden kann.
Eine Funktionsabstraktion alleine macht wenig Sinn.
Und die Applikation, die ist jetzt eben hier, haben Sie ja genau die
Funktionsabstraktion letztendlich angegeben an der Stelle.
Und hier haben Sie jetzt die aktuellen Parameter.
Aktuelle Parameter.
Und das führt ja genau zu der Applikation.
Das ist ja genau die Art der Funktionsanwendung, dass ich also in die
formalen Parameter aktuelle Parameter einsetze.
So wie Funktionsaufruf könnte man das eben auch als Funktionsaufruf
bezeichnen.
So und die Interpretation führt jetzt zu folgendem Ergebnis.
Und zwar stellen wir fest, dass hier diese Interpretationsfunktion auf
das f, also auf die Funktion, die entnehmen wir sozusagen der
Belegung.
Das heißt in der Belegung tritt auf, mit welchem Funktionswert dieses
f belegt ist.
Das ist aber nicht das Ergebnis eines Funktionsaufrufs, sondern das
ist wie ein Identifikator.
Das f ist ja ein Funktionsidentifikator, das wir eben aus der Belegung
herausbekommen, um welche Art von Funktion es sich handelt.
Also beispielsweise ist das eine Addition oder ist das eine andere
bühlsche Operation, die hier dahinter steckt.
Das gibt sozusagen hier die Interpretation von diesem f wieder.
Das heißt hier steht, es ist Teil der Belegung.
Teil der Belegung und die haben wir ja Beta genannt.
Jetzt schauen wir uns die Interpretation der Funktionsabstraktion an.
Und wir stellen fest, dass wir hier noch mal eine andere Belegung
einführen müssen, dieses Beta 1.
Um das zu verstehen, müssen wir das noch nachreichen, was das Beta 1
eigentlich bedeutet.
Das Beta 1 von einem Y ist folgendermaßen hier definiert.
Beta 1, das ist a, i, falls y und xi gleiche Identifikatoren sind,
gleiche Identifikatoren sind für ein i, wobei 1 kleiner gleich i,
kleiner gleich n ist.
Und wir übernehmen die normale Belegung Beta y sonst.
Dieses a, i, das ist ja genau der aktuelle Parameter.
Das schreiben wir vielleicht nochmal mit einer anderen Farbe hier hin.
Das ist ja genau der aktuelle Parameter, also der Aufrufparameter.
Und diese xi, das waren ja genau die formalen Parameter.
Und jetzt können wir auch an der Stelle sozusagen verstehen, was also
diese Interpretation bedeutet.
Also a, i, falls y und xi gleiche Identifikatoren sind für ein i, 1
kleiner gleich i, kleiner gleich n.
Heißt also nichts anderes als, dass hinter dem y verbirgt sich einer
der formalen Parameter, das bedeutet das.
Das könnte man hier auch nochmal ergänzen.
y bezeichnet einen der formalen Parameter xi.
Das ist das, was hier angegeben ist.
Solche Art von formalen Darstellungen oder Ausdrucksweisen sollten Sie
sich für die Klausur zurechtlegen.
Solche Art von Aussagen sollten Sie treffen können.
Und zwar eben eher von der blauen Bauart als von der roten Bauart.
Solche Art von Spezifikationen, das ist nämlich nichts anderes als
eine Spezifikation, sollten Sie in der Lage sein, selbstständig
durchzuführen.
Jetzt sehen wir auch, was das nämlich hier bedeutet.
Wir wollen erstmal hier sicherstellen, dass die a, i nicht bottom
sind, also nicht undefiniert.
Bottom-Element nochmal, das haben wir ja eingeführt, um sozusagen
nochmal diesen undefinierten Zustand, um da einen definierten Wert
anzugeben.
Also es ist nach wie vor undefiniert, aber es ist durch das Bottom
-Element dann zumindest auf der syntaktischen Ebene definiert.
Und entsprechend wird jetzt hier sozusagen dieses Beta-1 eingeführt,
indem wir nämlich letztendlich jetzt hier die Belegung, es geht hier
um den Rumpf E, und an jeder Stelle, wo wir diese Übereinstimmung von
vormalem und aktuellen Parameter haben, das ist ja genau was Beta-1
angibt, wird das in der Belegung geändert.
Deswegen haben wir hier an der Stelle eben das Beta-1.
Beta-1 kann man auch noch kurzschreiben.
Wir können unsere Kurzschreibweise hier auch verwenden, Beta-1 ist
gleich Beta...
und jetzt können wir diese punktweise Änderung a1x1 bis anxn, können
wir jetzt durch diese eckigen Klammer angehen.
Schauen Sie auf einer der vorhergehenden Folien mal nach, wie wir
diese Notation hier eingeführt haben.
Aber bedeutet Beta-1 stimmt mit Beta überein, nur für diese x1 bis xn
werden die a1 bis an substituiert.
Und ansonsten ist das eben hier undefiniert.
An der Stelle sehen Sie, dass wir hier Stricktheit voraussetzen.
Nämlich wir wollen dafür sorgen, wenn einer der aktuellen Parameter
undefiniert ist, dass dann auch das Gesamtergebnis undefiniert ist.
Das ist genau das, was wir eben mit der Stricktheit definiert haben.
Jetzt kommen wir wieder zurück zu dem, was wir auf der ersten Folie
heute behandelt haben.
Nämlich jetzt schauen wir uns die operationale Semantik an.
Operationale Semantik.
Und da haben wir auch gesagt, schon auf einer vorhergehenden Folie,
operationale Semantik hat etwas mit Thermersetzungssystemen zu tun.
Das ist sozusagen unsere Maschine, die diese Funktionsapplikationen
auswertet.
Und jetzt müssen wir uns überlegen, was sind die
Thermersetzungsregeln, die dieses Sprachelement ausreichend
beschreiben oder vollständig beschreiben.
Und hier müssen wir jetzt diese beiden Formen vorsehen, was wir eben
mit Call-by-Name und Call-by-Value eingeführt haben.
Nämlich wir müssen uns überlegen, ob wir irgendwelche Anforderungen,
ob wir irgendwelche Bedingungen stellen oder nicht.
Und die erste Thermersetzungsregel stellt eben eine Bedingung
dergestalt, dass wir fordern, dass die AI, die wir hier jetzt
sozusagen als aktuelle Parameter einsetzen, und da müssen wir
bedenken, das sind Ausdrücke, das müssen wir immer wieder in
Allgemeinfall betrachten, das sind Ausdrücke, das sind jetzt nicht
einzelne Parameterwerte, das können ganze Ausdrücke sein, dass wir
sagen, dass diese AI-Terminal für Einsteiner gleich i, Kleiner gleich
n sind, also dass alle AI-Terminal sind und das ist nichts anderes,
als dass wir eben Normalform fordern.
Wir können auch ausdrücken, dass wir nur primitive Operationen hier
erlauben, das heißt wir können also keine weiteren Auswertungen mehr
durchführen, wir können keine Funktionsapplikationen mehr durchführen.
Und das heißt nichts anderes, als dass wir vollständig ausgewertete
Ausdrücke auf der Argumentposition fordern.
Wir müssen sogar noch weitergehen, dass diese primitiven Operationen
auch ausgeführt sind.
Also vollständige Auswertung, bis wir an den Punkt gekommen sind, wo
wir sagen, das gehört zu unserer algorithmischen Basis, da können wir
nicht weiter auswerten.
Und das ist genau die Call-by-Value-Auffassung, vollständige
Auswertung, bevor man sich an den Rumpf heranwagt, bevor man hier
dieses E weiter betrachtet und erfüllt dann entsprechend die
Strickheitsregel, weil Sie nämlich genau zu der Erkenntnis kommen,
wenn Sie in ein Undefiniert geraten, da haben Sie jetzt ein bisschen
ein Problem, nämlich das bedeutet, Sie kommen zu einer Nicht
-Terminierung, dann geht es eben nicht weiter.
Dann kann es nicht sein, dass einer dieser Ausdrücke dorthin ist oder
undefiniert ist, aber das Gesamtergebnis ist nicht undefiniert.
Das Unangenehme an der operationalen Semantik ist hier, wenn Sie sich
eben im Bereich der Thermasetzungssysteme aufhalten, also auf so einer
Maschinenebene, dass undefiniert nichts anderes heißt, als dass einer
dieser Ausdrücke nicht terminiert, also undefiniert entspricht hier
Nicht -Terminierung.
Im formalen Sinne können wir dann dieser unglücklichen Situation,
Nicht -Terminierung des Bottom-Elements zuweisen.
Hier merken Sie es einfach daran, dass Sie endlos lange
Thermasetzungsregeln bekommen und gegebenenfalls können Sie auch diese
Nicht -Terminierung dann beweisen, manchmal aber auch nicht.
Unbedingte Thermasetzung lässt jetzt diese Bedingung weg, das heißt,
Sie haben ohne irgendeine Bedingung, wie sie da oben aufgetreten ist,
die Auswertung erfolgt durch Einsätze noch nicht auf Normalform
gebrachten aktuellen Parameter.
Das heißt also, hier werten Sie noch nicht die Parameter vorher aus,
sondern Sie beginnen mit der Auswertung und werten dann die
Parameterwerte bei Bedarf eben aus, wenn Sie diesen Wert tatsächlich
brauchen.
Und das ist genau die Call-by-Name-Auffassung, die Sie hier haben und
die erfüllt selbstverständlich nicht die Strickheitsregel, weil
nämlich Sie gegebenenfalls zu einem definierten Wert kommen, auch wenn
einer der Parameter undefiniert ist, weil Sie den an der Stelle
gegebenenfalls nicht gebraucht haben.
Jetzt wollen wir uns nochmal ein paar Gedanken machen zu dem Call-by
-Name.
An der Stelle, was sind denn da Vor- und Nachteile?
Schauen wir uns das Call-by-Name an.
Da ist sicherlich der Vorteil,
keine Berechnung,
wenn ein XI, also ein formaler Parameter, nicht gebraucht wird.
Da entsteht für Sie überhaupt kein Aufwand, weil Sie das ja nur an die
Hand machen.
Die Nachteile, hier kann man zwei finden, zwei Nachteile.
Der erste Nachteil, was wir gesagt haben, dass wir als Ergebnis nicht
-strickte Funktionen erhalten, ist das ein Nachteil.
Wir werden also sehen, dass wir mit nicht-strickten Funktionen sehr
viel schwieriger, auch in der Praxis, die Semantik und die
Wirkungsweise eines Programmes nachvollziehen können.
Das ist jetzt nicht ganz so schlimm wie nicht-determinismen, aber es
läuft eigentlich schon fast in diese Richtung.
Wenn man da Aussagen, Korrektheitsaussagen über Programme durchführen
möchte, da hat man bei nicht-strickten Funktionen sehr große Probleme.
Beziehungsweise Sie können gewisse Korrektheitsbeweise, die auf nicht
-strickten Funktionen anwendbar sind, die versagen bei nicht-strickten
Funktionen.
Das ist also ein ganz praktischer Nachteil.
Wenn Sie nicht sagen können, ist das Programm korrekt oder nicht, dann
ist das ein relevanter Nachteil.
Und das Zweite, das geht jetzt auf die Effizienz.
Das Ganze ist aufwendig bei mehrfach Auftreten.
Wenn Sie sich nämlich so eine Strategie wählen, ich werte das immer on
demand aus und solche Systeme machen das dann tatsächlich auch so.
Die merken sich nicht, ob sie es schon mal ausgewertet haben und dann
setzen sie den Wert ein, den sie vorher schon mal ausgeführt haben.
Das ist also ein mechanisches Vorgehen, ein nicht-intelligentes
Vorgehen, was hier zugrunde liegt bei diesen Thermasetzungssystemen.
Ob das bedingte oder nicht-bedingte Thermasetzungssysteme sind, ist
egal.
Und hier haben Sie tatsächlich das Problem, wenn Sie mehrfach
Auftreten haben, dass Sie auch immer wieder die gleiche Auswertung
durchführen.
Diese beiden Dinge, die ich jetzt hier Ihnen genannt habe,
insbesondere hier dieses Zweite, das ist also Fragen der Effizienz,
die Sie sich jetzt hier stellen.
Effizient ist das sicherlich der Vorteil von Call-By-Name.
Kein Auftreten bedeutet keine Auswertung, mehrfach Auftreten ist ein
Effizienznachteil.
Sie müssen eben auch mehrfach ausführen.
Aber dieser Punkt hier, diese nicht-strikte Funktion, das ist noch
viel gewichtiger als die Effizienzfrage, weil Sie damit tatsächlich
ein ganz unterschiedliches Semantikverhalten bearbeiten.
Die letzte Folie hier zu diesem Abschnitt, die schlägt nochmal einen
Bogen zurück zu den Lambda-Kalkülen und Funktionsabstraktionen als
Lambda -Abstraktionen.
Und Sie haben hier an der Stelle letztendlich, kommen Sie zu der
Lambda -Abstraktion, dadurch, dass Sie ein Verzicht auf Typen oder
Sorten, können Sie sagen, hier vornehmen.
Und wenn Sie mal diese beiden Ausdrücke nebeneinander setzen, dann
entspricht so ein Lambda X, Punkt E, genau der Funktionsabstraktion
S1X, hier brauchen Sie dann ein S und Groß E.
Und das ist genau, was Sie sozusagen hier jetzt einführen, nämlich
diese Sorten, die Sie hier haben, die kommen eben dazu.
Deswegen redet man an der Stelle eben von Typbehaftet.
Und das ist Typfrei.
Das sind also die beiden grundsätzlich unterschiedlichen Klassen von
Programmiersprachen.
Und heutige Programmiersprachen, höhere Programmiersprachen sind
eigentlich immer Typbehaftet.
Sie haben immer solche Sorten oder Typen, die Sie eben einführen, um
die Objekte, mit denen Sie arbeiten, vernünftig zu klassifizieren.
Ansonsten können Sie diese Alpha-Reduktion, diese konsistente
Umbenennung, haben wir ja gesehen, können Sie also aus dem Lambda
-Kalkül 1 zu 1 auf diese Sprachkonzepte, Sprachelemente anwenden, die
wir hier im Rahmen dieser Sprache eingeführt haben.
Sie müssen diese Konsistenzeigenschaften auch berücksichtigen, Sie
eben dafür sorgen, dass Sie freie Identifikatoren nicht
unzulässigerweise binden.
Und entsprechend können Sie diese ganzen Konstrukte des Lambda-Kalküls
hier auch übernehmen.
Auch diese Substitution von Identifikatoren funktioniert.
An der Stelle können Sie 1 zu 1 übernehmen, das wird also hier nochmal
angedeutet.
Und an der Stelle nochmal diese zwei Bedingungen, die Sie hier
berücksichtigen müssen.
Die erste Bedingung, die besagt nichts anderes als, dass vorhandene
Bindungen bleiben bestehen.
Die dürfen Sie also auch nicht auflösen, d.h.
das was gebunden ist, muss gebunden bleiben.
Und keine neuen, wie wir sagen, unzulässigen Bindungen.
Und da verweist man einfach auf die Substitutionsregeln, die wir im
Zusammenhang mit dem Lambda-Kalkül eingeführt haben.
Die lassen sich also hier 1 zu 1 darauf anwenden.
Sie haben neben diesen Substitutionsregeln auch immer noch diese
syntaktischen Nebenbedingungen, die sich eben auf die Typen, auf die
Sorten beziehen.
Die kommen eben dazu, weil wir hier von einer typbehafteten Sprache
ausgehen.
Das wäre also jetzt soweit zum Abschnitt 4.3.
Jetzt mache ich eine kurze Pause und komme dann zum Abschnitt 4.4.
Soll ich nicht gerne weitermachen?
Beschäftigen wir uns jetzt mit den Deklarationen in applikativen
Sprachen.
Auch wieder Sprachelemente, die wir hier einführen.
Und insbesondere, wenn wir uns mit Gültigkeitsbereichen, Lebensdauern
von Identifikatoren auseinandersetzen.
Fangen wir mal an, wozu wir Deklarationen benötigen.
Wir müssen erstmal bei so einem Identifikator immer unterscheiden,
steckt dahinter ein Element oder steckt dahinter eine Funktion.
Das sind die beiden Arten von Identifikatoren.
Und mit einer Deklaration deklarieren wir oder vereinbaren wir ein
Element oder eine Funktion.
Man könnte an der Stelle auch durchaus so mit einer Deklaration
assoziieren, dass man sozusagen so etwas wie eine Abkürzung einführt
für einen Ausdruck.
Für ein Element oder auch für eine Funktion.
Abkürzung.
So und wir müssen uns überlegen, und da kommen jetzt wieder
Sprachelemente rein, bzw.
Sprachfragmente.
Wo ist diese Abkürzung gültig?
Wo kann ich diesen Identifikator als Abkürzung benutzen?
Und dieser Identifikator bezeichnet dann genau das, was ich hier in
der Deklaration vereinbart habe.
Das ist die Frage.
Und das führt uns genau zu den sogenannten Abschnitten.
Das ist nichts anderes als eine Begrenzung der durch eine Deklaration
erzeugten Bindung.
Also eigentlich eine Begrenzung, wo diese Deklaration gültig ist, wo
diese Bindung, die ich hier in der Vereinbarung festgelegt habe,
genutzt werden kann.
Und der englische Begriff für Abschnitt ist eben Section.
Und wir führen jetzt hier dieses syntaktische Element ein.
Sie wissen, Sie müssen nochmal schauen, ich habe es Ihnen auch schon
gesagt, an der entsprechenden Stelle auf dieser Folie 3 in der letzten
Abschnitt, da kam schon diese Section drin vor in dieser gesamten
Sprachbeschreibung.
Und das wird jetzt weiter vertieft.
Und wir haben hier ein Inne, das steht sozusagen für einen inneren
Abschnitt.
Das ist also ein weiteres Non-Terminal, was wir hier im Rahmen dieser
Bacchus -Mauer-Form einführen.
Das wird dann entsprechend hier weiter vertieft.
Und wir haben als Section ein If-Then-Else-Konstrukt, das auch wieder
im Wesentlichen aus diesen inneren Abschnitten sich zusammensetzt.
Jetzt ist es interessant, wie ein innerer Abschnitt aussieht.
Und hier haben wir verschiedene Declarations und Expressions, die wir
hier angeben.
Hier dieses Expression, das ist ja sozusagen die Wurzel, das Haupt-Non
-Terminal unserer Sprache.
Und das ist eben auch im Abschnitt 4.3 behandelt.
Abschnitt 4.3.
In der Folie 3, da ist genau angegeben, was sich hinter einem
Expression verbirgt.
Da kommt dann wieder die Section vor, insofern haben Sie hier
sozusagen indirekt die Möglichkeit, mehrere Deklarationen
hintereinander zu schreiben.
Über diese Expression hinweg geht das, das sollten Sie sich vielleicht
mal anschauen.
Ich schreibe es nochmal als Hinweis.
Enthält wieder die Section als eine Alternative.
Enthält ist vielleicht, ich wollte nur einen Anführungsstrich setzen,
lässt sich überführen in eine Section.
Dadurch kommen Sie eben dazu, dass Sie mehrere Deklarationen
hintereinander aufschreiben können.
Und ich möchte an zwei Stellen hier nochmal eine Referenz setzen, die
Sort -Declaration.
Erstmal die Sort-Declaration, mit der fangen wir mal an.
Sort-Declaration, das ist eigentlich eine Anbindung von Sorten
-Deklarationen.
Und das ist genau unser Kapitel 6.
Da werden wir also die Sprache eben um Sorten-Deklarationen erweitern.
Und ich glaube hier können wir diesen Bindestrich wegmachen.
Und wenn Sie sich nochmal anschauen, das war jetzt die Sort
-Declaration, die Procedural-Inne, dieses hier.
Das werden wir erst im Zusammenhang mit Procedural-Inne weiter
vertiefen in diesem Kapitel.
Das sind zuweisungsorientierte Sprachelemente.
Zuweisungsorientierte Sprachelemente.
Und das werden Sie also nicht in diesem Kapitel hier sehen, sondern
das ist eben in Kapitel 5, wenn wir das aufgreifen.
Das heißt, wir haben uns jetzt hier sozusagen nochmal einen Haken
gesetzt, dass wir sowohl die Inhalte von Kapitel 5 als auch von
Kapitel 6 hier einbeziehen können in unsere Syntax.
Insofern geht das systematisch, wird diese Sprache erweitert um
zuweisungsorientierte bzw.
um Sorten-Deklarationen.
Das ist also hier nochmal ein Hinweis an dieser Stelle.
Und womit wir uns eben jetzt beschäftigen, das ist genau diese beiden
Deklarationen, nämlich die Element-Declaration und Function
-Declaration.
Das sind funktionale Sprachelemente.
Deswegen werden sie hier in diesem Kapitel auch vertieft.
Element-Deklaration, also Element-Declaration.
Sie ist von dieser Form, Sx gleich E.
Wir haben hier wieder die Sorten, die wir berücksichtigen müssen.
Und was letztendlich gemacht wird, ist eine Bindung von diesem
Identifikator x an den Wert des Ausdrucks e.
Das wird hier durchgeführt.
Und jetzt haben wir der Bindungsbereich, den müssen wir uns jetzt eben
anschauen, der ist durch einen Abschnitt begrenzt.
Und was wir letztendlich an der Stelle jetzt brauchen, um diese
Abschnitte zu bezeichnen, ist nichts anderes als wieder ein
Beschreibungsmittel.
Und dieses Beschreibungsmittel führt uns genau zu diesen eckigen
Klammern hier.
Das sind taktische Beschreibungsmittel, um einen Abschnitt
festzulegen.
Das ist sozusagen Teil der Syntax, Teil der Sprache.
Und an der Stelle soll jetzt hier die Deklaration sein, E0, irgendein
Ausdruck.
Und die nennen wir hier jetzt entsprechend Abschnittsklammern.
Und dadurch wird der sogenannte Gültigkeitsbereich der Deklaration
angegeben und eben beschränkt.
Das heißt außerhalb dieser Abschnittsklammern gilt diese Deklaration
nicht.
Entsprechend können wir hier nochmal die Syntax angeben, das ist also
nichts Neues weiterhin.
Also sozusagen übernommen dieses Beispiel dann in eine allgemeine Form
gegossen.
Und die syntaktischen Nebenbedingungen, die betreffen wieder die
Sorten, also dass wir eben hier eine Typgebundenheit haben.
Also da müssen wir nicht weiter tiefer drauf eingehen, das ist soweit
klar.
Jetzt müssen wir uns nochmal Beispiele für Elementdeklarationen
anschauen.
Doch eine Stelle ist schon wichtig hier.
Das ist diese Typgebundenheit, das ist klar.
Bloß das hier ist nochmal interessant, x tritt in e nicht frei auf.
Das ist eine interessante Nebenbedingung, die aber klar sein wird,
wenn wir uns das Beispiel anschauen.
Das heißt, dass wir hier keine rekursiven Elementdeklarationen
zulassen, was für die Funktionsdeklarationen dann nicht gilt.
Also hier können wir nicht irgendwie was konstruieren in der Form, ich
gebe mal ein Beispiel an, was eben nicht zulässig ist.
Nat x gleich 3 plus x, das ist also nicht zulässig.
Das ist klar, weil wir sozusagen hier das x ja erstmal festlegen
wollen mit dieser Angabe.
Und wenn wir auf der rechten Seite das x verwenden, dann wissen wir
nicht, was das eigentlich bedeuten soll.
Und insofern ist das nicht zugelassen.
Andere Deklarationen, die jetzt hier zulässig sind, ist zum Beispiel
nat x gleich 3 plus 4.
Und dann können wir das x eben an dieser Stelle verwenden.
Und das ist genau hier diese eckigen Klammern, das ist das, was wir
eben als Gültigkeitsbereich verstehen oder eingeführt haben.
Was Sie auch sehen in der Sprache, die wir jetzt hier einführen, ist,
dass jeder dieser Abschnitt ein Ergebnis produziert.
Sozusagen wird ein Ergebnis weitergeliefert.
Das kann man hier auch nochmal an dem zweiten Beispiel recht schön
sehen.
Diese innere Abschnitt liefert ein Ergebnis, das ist dieses x.
Und entsprechend liefert auch dieser äußere Abschnitt ein Ergebnis, in
dem eben diesem Ergebnis des inneren Abschnitts noch ein x addiert
wird.
Das ist also an der Stelle noch eine Spezialität, dass also jede
Section auch ein Ergebnis liefert, wie eine Funktion, wenn man so
will.
Das hängt also mit diesem Aspekt der Funktionsabstraktion auch direkt
zusammen.
Jetzt schauen wir uns hier mal dieses zweite Beispiel an, das ist
etwas interessanter insofern, als dass wir hier eben eine Verschattung
feststellen.
Derart, dass Sie hier im inneren Abschnitt ein x einsetzen und auch im
äußeren Abschnitt ein x einsetzen.
Und in diesem Bereich, in dem hier angegebenen Bereich, wird sozusagen
dieses x des äußeren Abschnitts verschattet.
Und es gilt, an der Stelle hat dieses x den Wert 2 und nicht den Wert
1.
Und hier hat es eben den Wert x gleich 1.
Sie können erstens mal diese Sections verschachten.
Das finden Sie da, das ist ein Beispiel, das sollten Sie sich mal klar
machen, auch anhand von den BNF-Regeln, dass das syntaktisch möglich
ist.
Und das bedeutet eben, dass Sie hier gegebenenfalls bei identischen
Bezeichnungen solche Verschattungen einführen.
Sie können also sich das auch nochmal dadurch klar machen, dass Sie
hier eine konsistente Unbedehnung durchführen.
Das ist eben genau diese Alpha-Konversion oder konsistente
Ungenennung, die Sie hier entsprechend durchführen können.
Und das gibt es eben in allen möglichen Programmiersprachen.
Sie sind diese entsprechenden eckigen Klammern oder Winkelklammern
durch entsprechende andere Sprachelemente, Begin, End oder geschweifte
Klammern oder sonstige Konstrukte eben hier auch wiederzufinden.
Diese Verschattung führt dann eben auch dazu, dass wir uns neben dem
Begriff des Gültigkeitsbereichs eben auch noch mit der Lebensdauer
beschäftigen müssen.
Oder dass der Gültigkeitsbereich nicht der Lebensdauer entspricht.
Die Lebensdauer, das ist der gesamte Bereich zwischen den
Winkelklammern, der ist syntaktisch festgelegt.
Eben genau durch die Winkelklammern, die ich hier setze an der Stelle.
Der Gültigkeitsbereich hingegen, und hier reden wir auch von einem
sogenannten Bindungsbereich.
Das wird auch als Bindungsbereich bezeichnet.
Und der Gültigkeitsbereich, das ist eben die Lebensdauer, wir gehen
also hier von der Lebensdauer aus abzüglich der inneren Abschnitte mit
neuen Bindungen.
Und diese inneren Abschnitte mit neuen Bindungen, das nennt man auch
den Verschattungsbereich.
Das ist genau das, was wir gerade im Zusammenhang mit dem Beispiel
auch kennengelernt haben.
Das war also jetzt hier durch innere Abschnitte, wo die gleichen
Identifikatoren deklariert werden, dass wir die äußeren
Identifikatoren verschatten.
Jetzt können wir hier die Semantik dieser Elementdeklaration, also
Elementdeklaration, uns auch nochmal anschauen.
Das ist hier eine Elementdeklaration, das wird man nochmal deutlich
machen, von G.
Und das ist nichts anderes als eigentlich eine Punktweise, die wir
hier nochmal ergänzen.
Das ist eine punktweise Änderung einer Belegung.
Und somit eine Abbildung zwischen zwei Belegungen.
Also ich überführe sozusagen die bestehende Belegung in eine neue
Belegung über, indem ich hier eine punktweise Änderung durchführe.
Und das drückt genau hier dieses Konstrukt aus, dieses Environment,
das können wir ja nochmal angeben, das war ja nichts anderes als die
Menge aller Belegungen.
Wobei diese Belegung eben die ID, diese Identifikatoren in diese Menge
der semantischen Objekte überführt hat, eben dieses H, das wir
eingeführt haben.
Also Beta ist eine Abbildung von ID, von den Identifikatoren in die
Menge H der semantischen Objekte.
Und diese Abbildung zwischen Belegungen, das wird auch hier nochmal
deutlich, sie starten eben mit der eigentlichen Belegung Beta, die
gilt.
Und sie ändern jetzt genau, das ist hier wieder dieses Beta und diese
eckigen Klammern, die sie an der Stelle haben.
Sie ersetzen hier das X gegen I-Beta von E1, das ist genau die
Deklaration, die sie hier eben durchgeführt haben.
Sie haben also Sx gleich E1 gesetzt, das ist genau dieses Beispiel,
was wir hier nochmal zugrunde legen.
Die Deklaration sieht also so aus, dass sie Sx gleich E1 hier zugrunde
legen.
Das ist also hier für diese Festlegung der Interpretationsfunktion
gilt.
Und entsprechend legen sie hier fest, dass es sich um einen nicht
undefinierten Wert handelt, diese Interpretation, die hier rauskommt.
Ansonsten, falls sie hier undefiniert angeben, setzen sie dieses Omega
an der Stelle fest.
Das ist die Belegung, die jedem Identifikator den undefinierten Wert
zuordnet.
Die haben wir also auch schon eingeführt.
Dieses Zurückführen der Deklaration auf die Funktionsapplikation hat
folgenden Hintergrund, um das zu verstehen, was wir jetzt hier als
Zwischenschritt noch einführen.
Wir stellen fest, dass eine Deklaration nicht unmittelbar durch
Termersetzungsregeln durch Termersetzungsregeln ausgewertet werden
kann.
So.
Und was man dann aber macht ist, und was einem da jetzt weiterhilft,
und das sehen wir dann sehr schnell, wie das funktioniert.
Es lässt sich eine Regel für die Auswertung angeben,
die eine Abstützung auf die Funktionsapplikation vornimmt.
Das ist das, was hier auf der Folie steht, diese Regel.
Und dann können sie sozusagen alles, was sie für die
Funktionsapplikation ausgesagt haben, und was sie hier erarbeitet
haben, das können sie dann unmittelbar auf die Deklaration
zurückführen.
Das sind also hier die zwei Deklaration zurückführen auf die
Funktionsapplikation.
Lass uns nochmal kurz das fertig schreiben, und dann schauen wir uns
das auf der Folie an.
Und das ist genau was wir eben suchen, diese Regel, wie wir das eben
aufeinander abbilden.
Und jetzt schauen sie sich diese Deklaration an der Stelle an, diesen
Abschnitt mit der Deklaration und dem Ausdruck E2.
Da haben wir eben E1, der Ausdruck der Sorte S, E2, Ausdruck der Sorte
R.
Und jetzt können wir diesen Abschnitt, den wir hier angegeben haben,
ohne Probleme auf diese Funktionsapplikation zurückführen.
Und das ist jetzt nicht irgendwie ein Umsortieren, sondern das ist
eine Thermersetzungsregel.
Das können sie also sozusagen operationell in ein
Thermersetzungssystem überführen.
Und dann können sie sozusagen diese linke Seite hier, wenn man es so
darstellt, das können sie ersetzen gegen diese rechte Seite.
Und entsprechend ersetzen sie jetzt hier eine Elementdeklaration,
dadurch dass sie hier eine Funktionsapplikation durchführen.
Das können sie sich also sehr schnell vorstellen, dass das eben eine
korrekte Regel ist, eine Semantik erhaltene Regel.
Das ist eben wichtig, Semantik erhaltend.
Also sie drücken damit genau das gleiche aus wie eben mit der
Deklaration.
Und das führt dazu, dass sie solche Begriffe wie Bindung, Gültigkeit,
Lebensdauer, gebunden sein, Freiheit, also frei sein, dass sie das an
der Stelle genauso übernehmen können, wie das eben für die
Funktionsapplikation festgelegt ist.
Sie können das auch noch auf die Logik, auf den Existenzquantum
überführen, da müssen wir an der Stelle aber nicht weiter eingehen.
Das ist also nur nochmal eine zusätzliche Vertiefung.
Ich schreibe es hier hin, keine Vertiefung.
Das heißt hier ist also nicht Gegenstand, das wird nicht Gegenstand
von irgendeinem Klausurstoff sein.
Müsste man ein bisschen mehr noch sagen, wie man sozusagen die Logik
damit verknüpft, werden wir hier aber an der Stelle nicht machen.
Funktionsdeklaration, wir haben also jetzt die Elementdeklaration
behandelt, jetzt kommen wir zur Funktionsdeklaration und da kommen
sehr interessante Aspekte mit rein, insbesondere im Zusammenhang mit
rekursiven Funktionen.
Also schon mal hier angedeutet, rekursive Deklarationen werden uns
hier beschäftigen, insbesondere dann im nächsten Abschnitt.
Das andere, das geht eigentlich, das nichtrekursive
Funktionsdeklaration können wir eigentlich mit uns schon behandeln,
wie wir sie kennen.
Es geht also hier jetzt um diesen Aspekt, nicht mehr um Elemente,
sondern wir stellen fest, solche Identifikatoren und solche
Deklarationen von Identifikationen können Funktionen bezeichnen, das
ist das Entscheidende.
Und die Deklaration einer Funktion sieht so aus, dass wir hier jetzt
mit so einem Kopf und einem Rumpf arbeiten, das haben wir schon so
weit kennengelernt und das können wir auch als Beispiel nochmal
vertiefen, das ist sozusagen jetzt hier dieses F, das finden Sie hier,
das ist an dem Beispiel der Absolutbetrag, ABS.
Dann können Sie jetzt hier diesen Head wieder, wollen wir mal das S
noch dazunehmen, das finden Sie also jetzt an der Stelle wieder und
entsprechend dieses E, das ist jetzt hier dieser Rumpf, also so weit
als Beispiel nochmal zur Auffrischung, finden also genau diese
Elemente, Sie haben die Bezeichnung, Sie haben den Kopf und Sie haben
den Rumpf als Elemente und das sehen Sie jetzt in dem Beispiel auch
als konkrete Ausprägung wieder.
Die Syntax ist weiter auch nicht viel zu sagen, die Deklaration wird
also auf die Abstraktion letztendlich zurückgeführt.
Die Abstraktion war ja ohne die Bezeichnung, war eine
Funktionseinführung ohne Bezeichnung und das ist sozusagen noch die
Bezeichnung, die Sie hier mit angeben.
Also Sie haben sozusagen eine Deklaration, Bezeichnung und die
zugehörige Funktionsabstraktion sind hier die Elemente.
Ja, rekursive Funktionsdeklaration und Semantik.
Erstmal, was heißt rekursiv an der Stelle?
Sie kriegen auf der rechten Seite wieder die Funktion, die Sie
eigentlich deklarieren wollen und hier ist jetzt wichtig zu sagen, das
ist möglich im Gegensatz zur Elementdeklaration, da wollten wir auf
der rechten Seite mit dem Element, was wir deklarieren, nichts
anfangen, aber an der Stelle ist das also bei der Funktionsdeklaration
erlaubt.
Und hier müssen wir jetzt sauber unterscheiden oder uns auseinander
dividieren, die rekursive Festlegung der Semantik und die
nichtrekursive, den nichtrekursiven Fall.
Der nichtrekursiven Fall führt also zu keinem großen Problem, geht
nämlich in der Form, dass wir hier eine Funktion f' einführen und f'
ist also jetzt hier, um das nochmal so explizit hinzuschreiben, das
ist also gar eine Definition, i unter der Belegung eta von f, sowas
haben wir eigentlich schon am Anfang der letzten Vorlesungsstunde
behandelt und das ist auch vollkommen ausreichend, weil wir eben
sozusagen bei dem f' sicherstellen, dass wir also an der Stelle nicht
nochmal das f auftreten.
Also das ist ja eigentlich jetzt hier dieses Groß f, Groß f ist an der
Stelle der Rumpf von unserer Funktion f, Klein f und wir nutzen hier
aus, dass in dem Rumpf dieses Klein f nicht nochmal auftritt.
Das ist ja genau der nichtrekursive Fall und dann kommen wir ohne
Schwierigkeiten mit diesem f' hier zur Rande und können hier
entsprechend das f' gegen das f' substituieren.
Das ist also an der Stelle nur deswegen möglich, weil wir eben keine
nichtrekursive Funktion haben.
Diese Operationalsemantik basiert dann auf der Substitution.
Wir ersetzen an der Stelle das Groß f für das f einsetzende E.
Das Groß f ist also der Rumpf der Funktion.
Wir suchen also sozusagen in diesem Ausdruck E alle kleinen f's raus,
das sind genau unsere Aufrufe von unserer Funktion und ersetzen diese
Aufrufe Klein f gegen den Rumpf Groß f.
Das ist in dem Ausdruck E nichts anderes, als was hier eben
entsprechend steht.
f darf eben nicht mehr im Rumpf von f vorkommen.
Das ist ganz entscheidend, sonst funktioniert die ganze Geschichte
nicht.
Und dass wir noch aufpassen müssen, das ist jetzt der letzte Punkt,
den ich noch hier behandeln möchte.
Wir können Namenskonflikte an der Stelle hier auftreten und das können
wir lösen, indem wir uns nochmal hier mit Bindungsbereichen
beschäftigen.
Also es kommen genau diese Bindungsbereiche und Gültigkeitsbereiche
mit ins Spiel.
Aber wir stellen eben fest, dass wir, und das werden wir an dem
Beispiel gleich auch noch sehen, dass wir also uns hier entscheiden
müssen.
Wir haben also Möglichkeiten, diese ganze Geschichte eher statisch zu
betrachten oder dynamisch zu betrachten.
Bedeutet also, welche Elementdeklaration wählen wir denn hier aus?
Also es geht um Identifikatoren, die in e und f auftreten, in diesem
Beispiel hier, was wir angegeben haben.
Also im Rumpf und in dem nachfolgenden Ausdruck nach diesem Rumpf.
Und diese Identifikatoren bezeichnen ja gewisse Ausdrücke oder gewisse
Werte und das wird eben genau durch den Bindungsbereich festgelegt.
Und jetzt schauen wir uns mal an, dass ich jetzt eigentlich darunter
verstehe, warum das einmal statisch und dynamisch betrachtet werden
kann.
Das wird also durch folgendes Beispiel jetzt deutlich.
Also versuchen wir das Beispiel nochmal auf den allgemeinen Fall, den
ich gerade eingeführt habe, zurückzuführen.
Also hier in dem Beispiel ist das unser f, also unser Rumpf, unsere
rechte Seite von der Funktion.
Und dieser Teil hier nach dem großen f, das ist unser e.
Wir können das also mit der vorhergehenden Folie nochmal verknüpfen
und feststellen, dass das tatsächlich ein Beispiel zu dem allgemeinen
Fall ist, den wir auf der vorhergehenden Folie skizziert haben.
Und die Problematik ist, nochmal konkretisiert, wir haben gerade von
Namenskonflikt geredet, konkreter ist das in e, bestehen lokal
vereinbarte Identifikatoren, die in f frei vorkommen.
Das ist unser Problem.
Und das Beispiel gibt genau dieses Problem wieder.
Nämlich in der Form, dass wir diesen lokal vereinbarten Identifikator,
also diese Angabe hier bezieht sich genau auf dieses nat x gleich 2.
Das ist unser lokal vereinbarter Identifikator x in e.
Und wir haben jetzt das Problem, dass dieses x hier frei in f
auftritt.
Und die Frage, die sich hier stellt, ist, welche Deklaration gilt
jetzt für dieses x hier?
Ich versuche jetzt nochmal eine andere Farbe zu wählen für dieses x.
Welche Deklaration gilt hier an der Stelle?
Jetzt versuche ich nochmal, bevor Sie mit zu diesem Beispiel auch
nochmal vernünftig mitverfolgen können, gebe ich mal an, was
eigentlich statisch ist.
Ja, das gefällt mir auch nicht.
Das statisch heißt, wähle nächstäußere Deklaration.
Und jetzt kommt die Frage bezüglich was?
Wir müssen immer sagen, von welcher Stelle aus betrachtet.
Und hier ist genau bezüglich der Funktionsdefinition.
Das ist statisch.
Und dynamisch bedeutet, wähle nächstäußere Deklaration bezüglich der
Funktionsapplikation.
Das machen wir jetzt an dem Beispiel, wo ich das jetzt eben
durchexerziere.
Aber das werde ich jetzt nicht mehr heute machen, weil ich da ein
bisschen länger für brauche.
Nein, nein, das ist ganz gut so.
Weil Sie nämlich an der Stelle jetzt mal für das nächste Mal sich
überlegen, wo sozusagen die Definition und wo die Applikation ist.
Und dann auch nochmal sich überlegen, warum das hier dynamisch ist.
Nämlich da brauchen Sie den Laufzeitkeller für.
Hier, das können Sie aus der Syntax, aus der Aufschreibung
rausbekommen.
Bis Mittwoch, danke.