Programming Languages

Hausaufgabe 1

Geben Sie diese Hausaufgabe bis 30. April 2015 ab. Entweder bis 16:00 per Email an Tillmann Rendel
Alumni
Tillmann Rendel
(schreiben Sie “pl2” in den Betreff!) oder zu Beginn der Vorlesung auf Papier.

Gruppen

Sie können in Gruppen von bis zu 3 Personen arbeiten. Schreiben Sie in jedem Fall die Namen und Matrikelnummern aller Gruppenmitglieder mit auf die Hausaufgabe / in die Email. Wenn Sie in einer Gruppe arbeiten, achten Sie darauf, daß alle Mitglieder der Gruppe den Stoff verstehen. Nur dann sind die Hausaufgaben eine gute Vorbereitung auf die Prüfung.

Punkte

Sie können für die Aufgaben dieser Woche jeweils zwischen 0 und 3 Punkten bekommen. Insgesamt also zwischen 0 und 6 Punkten. Sie bekommen für die Aufgaben jeweils:

  • 1 Punkt, wenn Ihre Abgabe zeigt, daß Sie sich mit der Aufgabe ernsthaft beschäftigt haben.

  • 2 Punkte, wenn Sie die Aufgabe weitgehend korrekt gelöst haben.

  • 3 Punkte, wenn Sie die Aufgabe vollständig korrekt gelöst und Ihre Lösung gut verständlich dargestellt haben.

Die Punktevergabe für die weiteren Hausaufgaben im Semester wird ähnlich sein.

Aufgabe 1

In der Vorlesung haben wir eine Sequenz von Mengen Si wie folgt definiert:

S0 = ∅
Si + 1 = { true, false } ∪ { if t1 then t2 else t3 ∣ t1, t2, t3 ∈ Si }

Beweisen Sie: Si ⊆ Si + 1 für alle i.

Aufgabe 2

Hier ist die Syntax einer kleinen Sprache:

t ::= true ∣ false ∣ t ∧ t

Die Semantik dieser Sprache können wir durch eine Relation → zwischen Termen beschreiben:

true ∧ t → t

false ∧ t → false

t1 → t1

t1 ∧ t2 → t′1 ∧ t2

Welche dieser Regeln sind Computation-Regeln, welche sind Congruence-Regeln?

Schreiben Sie zusätzliche Regeln, um folgende Ideen zu beschreiben:

  • t ∧ false bedeutet false, egal was t bedeutet.
  • t ∧ t bedeutet dasselbe wie t.
  • Man kann auch das rechte Argument von ∧ zuerst auswerten.

Welche der neuen Regeln sind Computation-Regeln, welche sind Congruence-Regeln?