Prof. Dr. Manfred Schmidt-Schauß Fachbereich Informatik (20) Künstliche Intelligenz/Softwaretechnologie Johann Wolfgang Goethe-Universität Frankfurt am Main

Funktionales Programmieren II: Semantik, statische Analyse, Verifikation und abstrakte Interpretation

Wintersemester 1996/97

Übungsblatt Nr. 11

Vielleicht sollte das Parkinsonsche Gesetz um einen Zusatz ergänzt werden, der etwa lauten könnte:”Jede Handlung erfordert eine gleich starke entgegengesetzte Unterlassung, um herauszufinden, ob sie notwendig ist oder nicht.” Ich meine hier nicht triviale Aktivitäten wie das Nichtbegleichen der Telefonrechnung bis zur Androhung der Anschlußsperrung , sondern eine komplexere Art des Nichtstuns.

aus Nigel Williams: 2 \frac{1}{2} Männer im Boot

Aufgabe 1

Zeigen Sie: botelem ist Bot-closed.

Aufgabe 2

Zeigen Sie: Die Menge M mit Nil ∈ M und t ∈ W T und s ∈ M → (t: s) ∈ M ist in γ(F in), aber nicht in γ(Inf).

Aufgabe 3

Schreiben Sie folgende Evaluatorfunktionen für Bäume:

a) Eine Funktion, die Bäume komplett auswertet.

b) Eine Funktion, die die Baumstruktur komplett auswertet.

c) Eine Funktion, die den linkesten Ast komplett auswertet.

d) Eine Funktion, die den linkesten Ast in seiner Struktur auswertet.

e) Eine Funktion, die die HNF auswertet.

Aufgabe 4

Können Sie einen Evaluator für folgenden Listenkontext angeben?

⟨Cons ⊥ ⊥⟩