Types and Programming Languages:

Einführung TypenSWT Seminar WS 05/06

Linda SchmuhlManuel Aldana

Dozenten: Florian Kammüller, Matthias Vösgen

Gliederung

1. Typisierung arithmetische Ausdrücke

2. Einfach getypter lambda-Kalkül

3. Typlöschung

4. Zusammenfassung/Fragen

Typisierung arithmetische Ausdrücke

Vorteile der Typisierung

• Fehlererkennung– Flüchtigkeitsfehler (vergessener Cast)– Konzeptuelle Fehler (komplexe Fallunterscheidungen)

• Wartung– Änderungen in den Datenstrukturen führen zu

„erwünschten“ Inkonsistenzen• Dokumentation

– insbesondere in verwendeten Interfaces• Effizienz

– weniger Checks zur Laufzeit notwendig

Syntax untypisierter arithmetischer Ausdrücke

Evaluation t -> t ’

if true then t2 else t3 -> t2 E-IF-TRUEif false then t2 else t3 -> t3 E-IF-FALSE

t1 -> t1’ E-IFif t1 then t2 else t3-> if t1’ then t2 else t3

t1 -> t1’ E-SUCCsucc t1 -> succ t1’

pred 0 -> 0 E-PRED-ZEROpred (succ nv1) -> nv1 E-PRED-SUCC

t1 -> t1’ E-PREDpred t1 -> pred t1’

iszero 0 -> true E-ISZERO-ZEROiszero (succ nv1) -> false E-ISZERO-SUCC

t1 -> t1’ E-ISZEROiszero t1 -> iszero t1’

Syntax

t ::= Terme

true Konstante truefalse Konstante falseif t then t else t Konditional0 Konstante Nullsucc t Nachfolgerpred t Vorgängeriszero t Null-Test

v ::= Wertetrue true-Wertfalse false-Wertnv numerischer Wert

nv ::= numerische Werte0 Wert 0succ nv Nachfolger-Wert

Probleme untypisierter Terme

• iszero (if true then 0 else succ 0)

• succ if iszero (succ 0) then false else true

These:

Evaluierung eines Terms führt immer zu einem Wert.

Stuck State:

Term ist in Normalform,

aber noch kein Wert erreicht

Idee der Typisierungzugeordnet,

= Typen

KlassenTermen werdendie ihr Evaluierungsergebnis charakterisieren

= Typisierungsrelation

t : T „t ist vom Typ T“

Bedeutung: Es ist ohne Notwendigkeit einer Evaluierung ersichtlich, dass der Term zu einem Ergebnis dieses Typs führt.

Erweiterung der Syntax arithmetischer Ausdrücke

Syntaxt ::= Terme

true Konstante truefalse Konstante falseif t then t else t Konditional0 Konstante Nullsucc t Nachfolgerpred t Vorgängeriszero t Null-Test

T ::= TypenBool Typ der booleschen Ausdrücke

Nat Typ der natürlichen Zahlen

v ::= Wertetrue true-Wertfalse false-Wertnv numerischer Wert

nv ::= …

Erweiterung der Syntax arithmetischer Ausdrücke II

Evaluationsregeln t -> t ’

if true then t2 else t3 -> t2 E-IF-TRUEif false then t2 else t3 -> t3 E-IF-FALSE…

Typisierungsregeln

true : Bool T-TRUEfalse : Bool T-FALSE

t1 : Bool t2 : T t3 : T T-IFif t1 then t2 else t3 : T

0 : Nat T-ZERO

t1 : Nat T-SUCCsucc t1 : Nat

t1 : Nat T-PREDpred t1 : Nat

t1 : Nat T-ISZEROiszero t1 : Bool

Wohlgeformter Term

• Definition:

Ein Term t ist typisierbar oder wohlgeformt (well-typed), wenn es unter Berücksichtigung der Typisierungsregeln einen Typen T gibt, sodass gilt: t : T

• Konsequenz: Für jeden Term kann vor der Evaluierung, also zur Compile-Zeit, entschieden werden, ob er wohlgeformt ist und wenn ja, welchem Typen er zugeordnet werden kann.

Ableitungsbäume

• aus den Typinformationen seiner Subterme kann eindeutig auf den Typen des Terms selbst geschlossen werden

• genau ein Ableitungsbaum pro wohlgeformtem Term

Typcheck: Positives Beispiel

iszero (if true then 0 else succ 0)

(Ableitungsbaum siehe Tafel)

Typcheck: Negatives Beispiel

succ if iszero (succ 0) then false else true

(Ableitungsbaum siehe Tafel)

Sicherheit von Typsystemen

• Garantie, dass wohlgeformte Terme während ihrer Evaluation niemals in einen Stuck State führen

• Eigenschaft der Wohlgeformtheit reicht als Aussage, dass dieser Term zur Laufzeit keinen Typ-Fehler erzeugen wird

Sicherheit = Progress + Preservation

Progress

• Ein wohlgeformter Term ist niemals in einem Stuck State.

Term t

Wert t -> t‘

Preservation

• Ein wohlgeformter Term bleibt auch nach Anwendung einer Evaluierungsregel wohlgeformt.

t : T und t → t′, so gilt t′ : T

Einfach getypter Lambda-Kalkül

Motivation

• Typen für arithmetische Ausdrücke kennengelernt• Ziel: Typcheck verhindert Stuck State zur Laufzeit• Stuck-State: Term=Normalform + Wert• Gleiches soll für den lambda Kalkül eingeführt werden

Vorgehensweise

• Einführung Typcheck für lambda-Kalkulus • Vorgehensweise wie bei arithm. Ausdrücken:

Term Syntax Typ-Regeln

Term Typcheck

Abstrakte Ebene

Konkrete Ebene

verwendetbefolgt

checkt

Wiederholung (kurz)

• Lambda Kalkül stellen Funktionen dar, die Eingänge als Variablen enthalten und miteinander komponiert werden können

• Drei einfache Konstrukte:

1. Variablen 2. Abstraktion 3. Applikation

Syntax Erweiterung: Funktions-Typ

• Lambda-Ausdrücke repräsentieren Funktionen• Idee Einführung einfacher Funktions-Typ:

• Funktions-Typ der Beispiel-Terme:

• Einfacher Funktions-Typ nicht mächtig genug…

Funktions-Typ• Typ-Definition (wie wird Typ zusammengestzt):

• Typ-Relation (wie wird einem Term ein Typ zugeordnet):

• Typ-Urteil (wie werden gebundenen Variablen Typen zugeordnet):

Menge Typ-Urteil auf Term

Erweiterung Typ-Urteil

Typ-Regeln

• Typchecker verwendet Typ-Regeln• Pro lambda-Konstrukt eine Typ-Regel

1) Variablen Typ-Regel:

2) Abstraktion Typ-Regel:

3) Applikation Typ-Regel:

Typcheck Beispiel• Beispiele eines Typchecks auf lambda-Ausdrücke

Typdefinition Typ-Regeln

Typcheck Ergebnis

ist wohlgeformt

ist nicht wohlgeformt

Beispiele (Ableitungsbaum siehe Tafel):

1)

2)

Typlöschung

Löschen von Typinformationen

• Typ-Informationen sind für Evaluierung irrelevant• Typ-Informationen stellen Overhead dar und können gelöscht

werden

• Typ-Information über Typ-Rekonstruktion wieder herstellbar

Zusammenfassung

• Vorgestellt wurde statische Typisierung von arithmetischen und lambda-Ausdrücken

• Term-Typisierung realisiert über Typ-Syntax• Term-Typcheck realisiert über Typ-Regeln• Typisierung + Typcheck verhindert Fehlerklasse „Stuck-

State“• Typsicherheit-Beweis über Eigenschaften Progress und

Preservation

Fragen an Euch :)

• Kann ein Term typsicher sein?• Warum sollten Normalformen aus Werten bestehen?• Positive/Negative Erfahrung mit nicht-statischer

Typisierung (meist Skriptsprachen)?