Höhere Programmiersprachen Wintersemester 2004/2005 fileProf. Dr. Gerhard Goos, Dr. Sabine Glesner Höhere Programmiersprachen WS 2004/2005: Teil 1 Grundlagen 2 Übung Höhere Programmiersprachen

Prof. Dr. Gerhard Goos, Dr. Sabine Glesner Höhere Programmiersprachen WS 2004/2005: Teil 1 Grundlagen 1

Höhere ProgrammiersprachenWintersemester 2004/2005

Dr. Sabine GlesnerUniversität Karlsruhe

Institut für Programmstrukturen und Datenorganisation

Ort: -102 (Info)Zeit: Montag, 14:00 - 15:30

Vorlesungsunterlagen: http://www.info.uni-karlsruhe.de/...Email: [email protected]


Übung Höhere ProgrammiersprachenWintersemester 2004/2005

Dipl.-Inform. Jan Olaf BlechUniversität Karlsruhe

Institut für Programmstrukturen und Datenorganisation

Ort: SR -118 (Info)Zeit: Montag, 15:45 – 17:15 (14-tägig)

Übungsunterlagen: http://www.info.uni-karlsruhe.de/...Email: [email protected]


Lernziele

Sprachübergreifende Konzepte– lernen und verstehen– wiederfinden in einzelnen konkreten Sprachen

Überblick über höhere Programmiersprachen– Vorteile und Nachteile– Wann welche Sprache sinnvoll einsetzbar

Übersicht über Methoden zur formalen Semantik(operationale, denotationelle, axiomatische Semantik)

Vorgestellte Programmiersprachen

– Programme lesen und verstehen können– Sprache leicht lernen können

Kein Programmierkurs

Inhaltsübersicht HPS WS 2004/05

- Grundlagen (1,2)- Konzepte imperativer Programmiersprachen (2,3)- Deklarative Programmiersprachen (4)- Objektorientierte Programmiersprachen (5,6)- Programmierung von Smart Cards: Java Card (7)- Wissenschaftliches Rechnen: Fortran (8)- Wirtschaftsanwendungen: Cobol (8, 9)

- Formale Semantik - Operationale Semantik mit ASMs (10) - Operationale Semantik mit natürlicher Semantik und SOS (11) - Denotationelle Semantik (12, 13) - Axiomatische Semantik (14)


1. Grundlagen

Geschichte von Programmiersprachen

Paradigmen

Syntax, Semantik, Pragmatik

Statische und dynamische Eigenschaften

λ - Kalkül, Bindungen,

Lebensdauer, Gültigkeitsbereich

Abstrakter Datentyp


2. Konzepte imperativer Sprachen

Typen

Ausdrücke

Ablaufsteuerung

Prozeduren, Module, Klassen

Generizität und Polymorphie


3. Standardparadigmen

Funktionales Programmieren (LISP)

Logisches Programmieren (Prolog, Datalog)

Wissenschaftliches Rechnen (Fortran)

Objektorientiertes Programmieren (Java, Small Talk, Cecil, Sather, Eiffel, CLOS und C++ im Vergleich)(Programmieren von Smart Cards: Java Card)


4. Weitere Programmiersprachen

Wirtschaftsanwendungen (COBOL)


Formale Semantik

Operationale Semantik

– mit abstrakten Zustandsmaschinen (ASMs),

– mit natürlicher Semantik und

– mit strukturell operationaler Semantik (SOS)

Denotationelle Semantik

Axiomatische Semantik

Inhaltsübersicht HPS WS 2004/05

- Grundlagen (1,2)- Konzepte imperativer Programmiersprachen (2,3)- Deklarative Programmiersprachen (4)- Objektorientierte Programmiersprachen (5,6)- Programmierung von Smart Cards: Java Card (7)- Wissenschaftliches Rechnen: Fortran (8)- Wirtschaftsanwendungen: Cobol (8, 9)

- Formale Semantik - Operationale Semantik mit ASMs (10) - Operationale Semantik mit natürlicher Semantik und SOS (11) - Denotationelle Semantik (12, 13) - Axiomatische Semantik (14)

LiteraturGoos, Zimmermann: Programmiersprachen. In Rechenberg, Pomberger (Hrsg.):Handbuch der

Informatik, Kap. D2. Hanser, 1997.Robert W. Sebesta: Concepts of Programming Languages, Addison Wesley, 2004.T. Pratt, M. Zelkowitz: Programming Languages - Design and Implementation. Prentice Hall, 2001.H. Riis Nielson, F. Nielson: Semantics with Applications: A Formal Introduction. Published by John

Wiley & Sons 1992, überarbeitete Version von 1999 unter www.daimi.au.dk/~hrn.S. Glesner: ASMs versus Natural Semantics: A Comparison with New Insights. In Proc. of 9th

International Workshop on Abstract State Machines ASM 2003, Springer LNCS 2003. ASM Homepage: www.eecs.umich.edu/gasm.R. Bird, P. Wadler: Einführung in die funktionale Programmierung. Hanser, 1992.P. H. Schmitt: Theorie der logischen Programmierung. Springer, 1992.L. Sterling, E. Shapiro: The Art of Prolog. MIT Press, 1994.J. W. Lloyd: Foundations of Logic Programming. Springer, 1984.G. Goos: Vorl. über Informatik, Band 1. Dritte Aufl., Springer, 2000.G. Goos: Vorl. über Informatik, Band 2. Dritte Aufl., Springer, 2001.B. Meyer: Object-oriented Software Construction. Prentice Hall, 1988.E. Horowitz (Hrsg.): Programming Languages. A Grand Tour. Springer-Verlag, 1983.J. Loeckx, K. Mehlhorn und R. Wilhelm: Grundlagen der Programmiersprachen. B.G. Teubner, 1986.R. Sethi: Programming Languages - Concepts and Constructs. Addison-Wesley,1996.Th. J. Bergin, R. G. Gibson: History of Programming Languages. Addison-Wesley 1996.R. L. Wexelblat: History of Programming Languages. Academic Press, 1981.J. E. Sammet: Programming Languages: History and Fundamentals. Prentice-Hall, 1969.

Sprachbeschreibungen und Standards siehe Hinweise im Lauf der Vorlesung


Teil 1

Grundlagen


Programmiersprachen

Programmiersprache:

– Notation, um Berechnungen in maschinen- undmenschenlesbarer Form zu beschreiben

Abstraktion von Maschineneigenschaften

Programmiersprachen sind Spezifikationssprachen

Programm:

– Algorithmus: Funktion Eingangsdaten → Ausgangsdaten

– Reaktives System:Strom von Eingabedaten → Strom von Ausgabedaten


Geschichte

1944: Zuse's Plankalkül (erst um 1970 bekannt geworden)40er: Maschinensprache (sedezimal)50er: Maschinensprache (symbolisch, symbolisch adressiert)1954-: Fortran: Formeln, Parameterübergabe1958/60: Algol 60: Ablaufstruktur, Blockstruktur, Kellerverwaltung, Namensaufruf, 1959: Lisp: Listenorganisation, Speicherbereinigung, ,,Programm ist Liste``1959/60: Cobol: Verbunde, Fallunterscheidung, Trennung der E/A1962/65: APL: interaktive Sprache~1964: Snobol: Textverarbeitung, Muster auf Texte anwenden, Suchbäume1967: Algol-W: Halde, Verweise, benutzerdeklarierte Typen1967: Simula 67: Objektorientierung1971: Pascal: Vereinfachung von Algol1972ff: Prolog: Unifikation, Termersetzung1974ff: Smalltalk: alles sind Objekte1975: Modula, CLU: Modulbegriff1976ff: Scheme, ML: funktionales Programmieren1980ff: SQL: ,,Sprachen der vierten Generation``

Geschichte II1955

1960

1965

1970

1975

1980

1985

1990

1995

2000

Fortran I (1954)

Algol 60

Algol 68Pascal

Modula 2

Ada 83

Oberon

Ada 95

Simula 67

Smalltalk 74

Smalltalk 80

Lisp

Prolog

ML

Haskell

C

BCPL

CPL

C++

Java

Scheme

Common Lisp

Gofer

Cobol

PL/1

ABAP4

CLOS

SML

Eiffel

Sather

Fortan IV

Fortran 77

Fortran 90

HPF


Sprachtypen

Imperativ (prozedural, operational)

– Zustände

– Zustandsübergänge (Zuweisung)

Funktional

– geschachtelte Funktionsauswertung

– Funktionen als Werte (Funktionale)

– applikativ: Kopplung imperativ+funktional

Logisch

– Hornklauseln (Resolution, Unifikation)


Was ist ein Programm?

Algorithmus: Funktion: Eingangsdaten → Ausgangsdaten Reaktives System: Strom v. Eingangsdaten → Strom v. Ausgangsdaten

Programmiersprache legt fest, – Syntax : Was ist ein wohlgeformtes Programm?– Semantik: Welche abstrakte Bedeutung hat ein wohlgeformtes

Programm?– Pragmatik: Welche konkrete Bedeutung hat ein wohlgeformtes

Programm?

Unterscheide– Semantik: Bedeutung im formalen System (Selbstbezug)– Pragmatik: Bedeutung in der Umwelt (und auf dem Rechner)


Gemeinsame Eigenschaften

Gliederung in Syntax, Semantik, Pragmatik

Typen

Bindungen von Namen

– an Deklarationen (von Typ, Funktion und Variablen)

– an Typen und Werte

Ablaufsteuerung

Beispiel: λ - Kalkül


Syntax

Lexik:

– Bedeutungstragende Sprachelemente

– Beschrieben durch reguläre Ausdrücke

Syntax*:

– Obermenge der gültigen Programme

– Beschrieben durch kontextfreie Grammatik

Statische Semantik*:

– Definiert gültige Programme

*: eigentlich Syntax = kontextfreie Syntax + statische Semantik


Semantik und Pragmatik

Semantik:

– dynamische Semantik

– Ordnet syntaktischen Sprachelementen Bedeutung zu

– Definiert die Ausführung des Programms

Pragmatik:

– setzt Sprachelemente zu Konzepten außerhalb der Sprache in Beziehung

– Beispiel: Arithmetik der Zielmaschine


λ-Kalkül

einfachste algorithmische Sprache entwickelt von ALONZO CHURCH

Eigenschaften:– einfache Termalgebra mit Variablen– Programm ist Folge von Termen– Daten sind Terme– einfache Syntax– nur drei semantische Regeln– keine E/A

Grundlage von– LISP– Beschreibung von Programmiersprachen


λ -Kalkül

(Variable) v

(λ-Abstraktion) λv.t

(Anwendung) ( t t´ )

Termalgebra Λ:

gegeben abzählbare Variablenmenge V:

– v єV ist ein Term

– λv.t ist ein Term für v є V, t є Λ

– ( t t´ ) ist ein Term für t, t´ є Λ


Programm im λ -Kalkül

Funktionsdefinitionen:Folge von Definitionen ( v=t ) mit v ∈ V und t ∈ Λ

Funktionsanwendung:( t t´ ), Terme t, t´ ∈ Λ

( f = ( λ v . v ) ) ( f t )


Syntax des λ-Kalküls

Grundsymbole:

– Bezeichner (Namen) für Variable, . , λ, ( , ) , =

Syntax:

– siehe vorangehenden Folien

Statische Semantik:

– (noch) keine Einschränkungen


Substitutionen im λ -Kalkül

Freie Variable:

Zulässige Substitution:

t [ t´/ v ] zulässig: freie Variable in t` dürfen durch die Ersetzung nicht gebunden werden: ¬∃ v: v ∈ frei (t`) ∧ v ∉frei (t[t'/v])

frei (v) = vfrei (λv.t) = frei (t) \ vfrei (t t´) = frei (t) ∪ frei (t´)


Programmlauf im λ -Kalkül

Programmlauf durch drei Konversionen definiert:

(α) λv.t → λv´.t[v´/ v], falls zulässig(β) ((λv.t) t´ ) → t[t´/ v], falls zulässig(η) (λv.(t v)) → t, falls v ∉ frei(t)


Beispiel: Programmlauf

1. ( f = ( λ v . v ) )( f t )

3. (( λv . v ) t )

4. (( λ v´. v[v´/ v]) t ) = (( λv´. v´ ) t ) (α), falls erforderlich

5. ( v' [ t / v' ] ) = t (β)


Semantik des λ-Kalküls

Bindung

– von Variablen in Termen (Bindung der Bedeutung)

– von Funktionsnamen an Terme (Bindung des Werts)

Ausführung: Folge von Transformationen

Pragmatik

– (noch) keine Beziehung zu anderen Konzepten


Endlose Auswertung

Ω = (λx. x x)(λx. x x)

= ( λx. x x) ( λx. x x) = ( λx. x x) ( λx. x x) ...

(λx. λy. y) Ω = (λx. λy. y) ((λx. x x)(λx. x x))

= (λx. λy. y) ((λx. x x)(λx. x x)) = ...

= (λ y. y)


Auswertestrategie

Links zuerst:

– Vollständig

– Namensaufruf

– Faule Auswertung

Rechts zuerst:

– Unvollständig

– Wertaufruf

– Strikte Auswertung

t

λx.t

(t t)

y

λy.t

Ω


Konfluenz

λ-Kalkül ist konfluent (Church-Rosser Eigenschaft)d.h. Regelanwendung in beliebiger Reihenfolge erlaubt

Terme ohne weitere Reduktion: Normalform

Normalform bis auf -Konversionen eindeutig

Aber: nicht alle Terme besitzen Normalform

Konfluenz:

´´´: *2

*12

*1

* ttttttttt →∧→∃⇒→∧→

t

t1 t

2

t´

* *

* *


Fixpunkt: Beispiel

F beliebige Formel

Y = λ F.((λt.(F (t t)) λt. (F (t t))))

w = λt.(F (t t)) (Abkürzung)

Y F = (w w) = (λt.(F (t t)) w) = (F (w w)) =

= (F(Y F))

YF ist Fixpunkt von F


Bedingte Anweisung

λ x y ... z . t =def λ x . ( λ y . ( ... (λ z . t) ...))

wahr = λ x y . x

falsch = λ x y . y

if-then-else = λ b t t´. ( b t t´)

b Funktion mit Ergebnis wahr oder falsch


Eigenschaften von Termen

Im Beispiel:

– Kontext if-then-else erfordert: b muß wahr oder falsch liefern

Allgemein:

– Kontext erzwingt Einschränkung potentiell an einen Namen gebundener Terme

Typisierung der Terme:

– Partitionierung der Terme bezüglich anwendbarer FunktionenÜbung: Die natürlichen Zahlen sind Funktionale

0 = (λ x. λ f . x)succ(n) = (λ x . λ f . (f x)),

definiere damit Addition, Multiplikation, ...


Typ eines Terms

Typ T verhält sich wie eine Menge von Termen

Induktiv definiert über

– Konstruktoren

– Operationen

– Axiome

Beispiel:Abstrakte Datentypen (ADTs) ADT INT:

Konstruktoren:..., -2, -1, 0, 1, 2, ... : INT

Operatoren:+, × , div, mod : INT INT INT==, < , > : INT INT wahr, falsch

Axiome:+ 0 t = t ... ×1 t = t ...


Rekursive Programme

Beispiel: Größter gemeinsamer Teiler ggT

ggT a b = ( if-then-else (== a b) a

( if-then-else (< a b) ( ggT b a) ( ggT b (+ a (× (-1) b)))

))

if-then-else und Rekursion zusammen erlauben Formulierung beliebiger sequentieller Abläufe.


Zusammenfassung λ-Kalkül

Einfache Sprache über Termen

nur drei Regeln definieren die Semantik

Ausführungsreihenfolge beliebig: Church-Rosser-Eigenschaft

Turing-mächtig: nicht abbrechende Berechnungen, Fixpunkte

Programme sind Daten, Daten sind Programmstücke(Grundlage der Metaprogrammierung)Grundlage von LISP

Grundlage vieler formaler Sprachbeschreibungen


Bindung

Zwei Formen der Bindung: Bedeutung: Zuordnung (freie) Variable (Bezeichner) zu

Definition (λ, Quantor, Vereinbarung, ...) Wert: Zuordnung: (gebundene) Variable (Name) zu Wert

Im λ-Kalkül: Zuordnung Bezeichner - Term– entspricht Bedeutungszuordnung

Name: Bezeichner, oft auch komplizierterer Zugriffspfad

Grundregel: In einem korrekten Programm sind alle Bezeichner gebunden(durch Vordefinition, explizit, oder implizit).– potentielle Fehler: nicht vereinbarter Bezeichner, polymorpher Aufruf

einer nicht-existenten Methode (z.B. in Smalltalk)


Gültigkeitsbereiche

Unterscheide

Definition (defining occurrence) eines Namens

Anwendung (applied occurrence) eines Namens

Bindung ordnet der Anwendung eine sichtbare Definition zu.

Gültigkeitsbereich einer Definition: Teil des Programms, in dem die Definition sichtbar ist.

Gültigkeitsbereiche statisch definiert durch:

– Blockschachtelung (entspricht α-Regel im λ-Kalkül/LISP)

– lokale Sichtbarkeit in Moduln/Klassen/Verbundtypen

alternativ: Gültigkeit dynamisch definiert: LISP, APL, polymorphe Sprachen


Bindezeitpunkte

Bedeutungsbindung:– statisch: fest zur Übersetzungszeit– beim Programmstart– dynamisch: abhängig von Aufrufhierarchie

Wertbindung:– statisch: fest zur Übersetzungszeit– polymorph: abhängig von Operandentypen– beim Programmbinden– beim Programmstart– bei Vereinbarung des Namens (dynamische Konstante)– dynamisch: Zuweisung


Statische Bindung

Bedeutungsbindung:

Gültigkeitsbereich statisch definiert

eventuell zusätzlich: bezeichnetes Objekt statisch definiert

– alle Objekte in COBOL, FORTRAN, ...

– Modulattribute in Modula, Ada, ...

– „static“ Variable/Konstante in C, C++, Java

– „shared“ oder Klassen-Attribute in oo Sprachen

Wertbindung:

Name bezeichnet stets den gleichen Term (statische Konstante)


Dynamisches Binden

Bedeutungsbindung: Sichtbarkeitsregeln dynamisch:

– Auswertungsfolge, nicht Programmstruktur (Syntax) definiert Zuordnung Anwendung - Definition:

Zuletzt ausgeführte Definition ist sichtbar. Verwendung in interpretiertem LISP, APL Für den Programmierer schwierig zu überprüfen

Wertbindung: Zur Laufzeit: unterschiedliche Terme an gleichen Bezeichner gebunden Zu jedem Zeitpunkt: nur ein Term

Kopplung Wert-Bedeutung bei Polymorphie (siehe später)

Achtung: interpretiertes/übersetztes LISP verhalten sich unterschiedlich!


Beispiele: statischer vs. dynamischer Gültigkeitsbereich

mit Pascal-Syntax:...var a: INT;

procedure q; begin writeln(a) end;procedure p; var a: INT; begin a := 1; q end;begin (* Hauptprogramm*) a := 2; pend;

Ergebnis 2 bei statischer Bindung, 1 bei dynamischer Bindung

im λ-Kalkül (mit Funktional):(a = 2)(f = (λ b. a))(g = λ a. (f a))(g 1)

dynamisch: (g 1) = ((λ a. (f a)) 1) = (f 1) = = ((λ b. 1) 1) = 1statisch: (g 1) = ((λ a. (f a)) 1) = (f 1) = = ((λ b. 2) 1) = 2Ergebnis 2 bei statischer Bindung, 1 bei dynamischer Bindung


Binden beim Programmbinden

Einzelne (getrennt übersetzte) Module definieren Namensräume.

Binder bindet Anwendung und Definition von Namen aus verschiedenen Moduln.

Beispiele:

Zuordnung externer Funktionen,

Überlagerung von COMMON-Zonen in Fortran


Binden beim Programmstart

Bedeutungsbindung: Bindung dynamischer Bibliotheken

Wertbindung COBOL bindet logische Dateinamen

aus der Umgebungssektion an physikalische Dateien Initialisierung statischer Variabler

Unterschied Wertbindung beim Startzu statischer Bindung/Bindung beim Programmbinden:

Speicherbereiche werden bei jedem Programmstart neu initialisiert.

– Daher kein Neuladen initialisierter Variablenbereiche erforderlich (eintrittsinvarianter Code, reentrant code)


Binden zur Ausführungszeit

Bedeutungsbindung:

Dynamisches Nachladen von Moduln

Java Klassen werden zur Laufzeit geladen, wenn sie benötigt werden.

Wertbindung:

Bindung konstanter Werte bei Vereinbarung des Namens (dynamische Konstante)

Zuweisung


Typen in Programmiersprachen

Typ: Klassifikation möglicher Werte nach zulässigen Operationen 0-stellige Operation ≡Konstante gegeben durch Termalgebra Typ bestimmt Semantik der Operationen und Speicherzuweisung

Abstrakter Datentyp: Spezifikation einer Termalgebra durch Signatur, Konstruktoren, Axiome

Typbindungen: typfrei: nur Speicherumfang bekannt,

Semantik der Operationen selbstidentifizierend (Maschinensprachen, niedrige Programmiersprachen)

uniform: nur Werte eines Typs (λ-Kalkül, elementares LISP, Prolog) typisiert mit mehreren Typen: alle anderen Sprachen


Typisierte Sprachen

schwache Typbindung: Mischung mit Eigenschaften typloser Sprachen (C, Fortran, ...), Typen nicht disjunkt

starke Typbindung: Typen disjunkt, alle Variable/Objekte/Werte haben eindeutigen Typ– statisch typisiert: Typisierung zur Übersetzungszeit bestimmbar.

– polymorph: Zur Übersetzungszeit Bestimmung von Typmengen (Obertyp), zur Laufzeit Auswahl des endgültigen Typs.

– dynamisch typisiert: Typ wird zur Laufzeit bestimmt (Smalltalk). Nur wenige Sprachen wirklich stark typgebunden: funktionale Sprachen,

Ada, Sather, Java– Gegenbeispiel Pascal, Modula-2: Typbindung verletzt beim Umgang mit

Verbunden mit Varianten (Variantenzeiger wird nicht geprüft). Problem starker Typisierung: Sprache nicht für explizites

Speichermanagement geeignet (Typwechsel von Speicherzellen notwendig) starke und dynamische Typisierung sind kein Widerspruch!

(Übersetzerentscheidung, Kriterien: Speicheraufwand, Laufzeit)


Typen von Namen

Was ist der Typ von a oder b ?

Typ bestimmt aus Vereinbarungen (hier nicht vorhanden)

Typinferenz bestimmt Obertyp (Menge möglicher Typen): alle vorkommenden Operationen (hier: ==, <, +, ×, -) und Konstante müssen zulässig sein.

Vorsicht bei Typinferenz: semantische Bedeutung von ==, <, usw. bleibt offen!

ggT a b = ( if-then-else (== a b) a

( if-then-else (< a b) ( ggT b a) ( ggT b (+ a (× (-1) b)))

))


Warum Typen?

Korrektheit der Programme zusichern

– Sind alle Operationen definiert sind auf Termen, Werten/Objekten

– Haben ausgeführte Operationen eine Pragmatik (Nie Äpfel mit Birnen addieren)

Verbessern Laufzeitfehlerinformation ("Operation nicht definiert“ statt "Segmentation Fault“)

Wähle korrekte Operation aus (Polymorphie)

Bestimmen Speicherabbildung

– Kein Implementierungsdetail!

– Entscheidend bei mehreren Übersetzungseinheiten und heterogenen Komponentensystemen


Historische Sicht auf Typen

Typen gekennzeichnet durch ihre Speicherausrichtung (alignment) und durch ihre Länge

Werte sind Bitsequenzen

Operationen bestimmen die Interpretation ihrer Operanden,z.B. bei Addition Wort versus Doppelwort, Festpunkt vs. Gleitpunkt

Alternative Typkennung der Operanden: Beispiel: Burroughs B6700 hat nur einen Additionsbefehl, Auswahl der Operation dynamisch nach Typkennung und Wert, dabei Unterscheidung der Operandenlängen und Festpunkt- oder Gleitpunktzahlen


Klassifikation

typisierte vs. typfreie Sprachen

– Werden Typen von Termen und Werten/Objekten unterschieden?

starke vs. schwache Typisierung

– Kann ein und dasselbe Objekt nur einem konkreten Type angehören?

statische vs. dynamische Typisierung

– Werden zur Übersetzungszeit Typen von Termen bestimmt, um die Typen der Werte/Objekte, die zur Laufzeit daran gebunden werden, abzuschätzen und Konsistenzprüfungen zu unterziehen?

inferierte vs. deklarierte Typisierung

– Werden statische Typen bestimmt durch den Nutzer (per Deklaration) oder durch den Übersetzer (aus Kontext und Literaltypen)?

Die meisten realen Programmiersprachen bieten Mischformen.


Untertypen

Ein Untertyp t' von Typ t ist ein Typ so, dass alle Werte und Operationen des Typs t' anstelle von Werten bzw. Operationen des Typs t benutzt werden können.

gewöhnlich sind die Operationen von t', t identisch,Ausnahme oo Sprachen

Beispiele und Gegenbeispiele: Untertyp t' definiert durch (konforme) Vererbung des Obertyps t in oo

Sprachen Strukturäquivalente und strukturkonforme Records Nicht Ausschnitte [a..b] von integer in Pascal, Modula-2 (bedenke b+1) Nicht array[a..b] of S von offenen Reihungen array[ ] of S in Pascal, Modula-2 in der Mathematik: Z ⊆ Q ⊆ R ⊆ C, Quadrate ⊆ Rechtecke

In der Informatik gelten diese Inklusionen nicht!


Statische Typen

Statischer Typ TS(n) eines Terms n (Namen im Lambda Kalkül) ist mindestens die Vereinigung der statische Typen TS(t) der potentiell zur Laufzeit an n gebundenen Werte/Objekte t (Terme im Lambda Kalkül).

Wenn t an n gebunden, gilt TS (t) ⊆ TS (n)

Statische Typisierung wird definiert durch

– explizite Vereinbarung

– Typinferenz


Dynamische Typen

Annahme:

– Werte/Objekte sind stark typisiert

– Grundterme (Compiler definierte Konstanten) sind stark typisiert Grundterme: Literale (nichtsymbolische Konstanten) und Ausdrücke mit Grundtermen als Operanden

Dynamischer Typ TD(n) eines Terms n (Namen im Lambda Kalkül) zu einem Zeitpunkt zur Laufzeit ist der Typ des Werts/Objekts (Grundterms im λ-Kalkül), der zu diesem Zeitpunkt an n gebunden ist (undefiniert, wenn nicht vorhanden)

– TD(n) ist Untertyp des statischen Typs TS(t) des Terms t der momentan an n gebunden ist.

Statischer Typ TS(n) eines Terms n (Namen im Lambda Kalkül) ?


Typvereinbarungen

Definition der speziellen Typen von Namen und Funktionen

Ableiten der Typen von Ausdrücken

Konsistenztest im Ausdrucks- und Zuweisungskontext

In vielen imperativen und funktionalen Sprachen


Typverband

Gegeben: Menge T aller disjunkten Typen. Werte (Grundterme in Termalgebren) sind immer eindeutig typisiert. Menge aller Werte ist partitioniert: jeder Wert w hat eindeutigen Typ t ∈T.

Potenzmenge von T ΡT bildet Verband mit ⊆ als Ordnung. top = T größtes Elementbot = Ø kleinstes Element

Variable und Funktionen (Prozeduren, Methoden) haben– monomorphen Typ t ∈T, oder– polymorphen Typ t ∈ ΡT, t Vereinigung monomorpher Typen

Beispiele:– funktionale Sprachen: alle Bezeichner (log. Variable, Funktionen) polymorph– C++, Java: polymorphe Variable definierbar, virtuelle Methoden polymorph– Sather: polymorphe Variable definierbar, alle Methoden polymorph– Smalltalk: alle Variablen und Methoden polymorph


Typinferenz

Gegeben: Variable v vom Typ t ∈ΡT, eventuell t = T, und Aufruf f(v).

In funktionalen Sprachen: Schränke Typ t ein unter Kenntnis der Aufrufe f(v).– Schränke mögliche Def. von f und mögliche Ergebnistypen von f(v) mit Kenntnis

des Typs von v ein.– alles zur Übersetzungszeit.

In oo Sprachen: Zur Laufzeit wähle aufgrund des Typs des Werts von v unter mehreren Definitionen f1, f2, ..., fn von f aus (dynamic dispatch).– muß zur Übersetzungszeit geschehen, wenn f nicht polymorph, sondern

überladen.

– kann zur Übersetzungszeit geschehen, wenn durch Datenflußanalyse die Typen der Werte von v bereits genauer bekannt sind (Optimierungsmaßnahme).

Analog für Funktionen / Methoden mit mehreren Parametern Typinferenz auch zur Konsistenzprüfung einsetzbar.


Kopplung Wert-Bedeutung bei Polymorphie

zugeordnete Definition einer Prozedur (oder Operation) kann vom Typ des Werts der Operanden abhängen– wird prinzipiell zur Laufzeit berechnet– bei polymorphem Aufruf in oo Sprachen zählt nur der erste Operand (das

Objekt der Methode), – Ausnahmen multiple dispatch in CLOS, Cecil– bei Überladen zählen immer alle Operanden– statischer Typ der Operanden ist Obermenge aller zur Laufzeit möglichen

Typen unterscheide:

– Überladen von Operationen/Prozeduren: Typen zur Übersetzungszeit bekannt– generische Polymorphie: Operandentyp von Typparametern des Moduls (Klasse,

Funktion) abhängig - statische/dynamische Auflösung implementierungs-abhängig (Ada, C++, Eiffel, Sather, Pizza,..., alle funktionalen Sprachen)

– Vererbungspolymorphie: nur dynamisch auflösbar (alle oo Sprachen), statisch berechenbare Auswahlfunktion


Parametrisierte oder generische Typen

Beispiel: Behältertyp liste(v) ∈ΡT von Elementen eines Typs v ∈ΡT.– Jede Spezialisierung v = t ∈T der Typvariablen v liefert konkreten Typ

liste(t) ∈T.– liste(v) heißt generischer Typ mit Typparameter v.

Vorsicht: Alle Operationen des Typs t, die zur Implementierung der Operationen von liste(v) erforderlich sind, müssen auch tatsächlich (mit der gewünschten Semantik) verfügbar sein!

Daher in oo Sprachen: liste(v < t') mit Typschranke t': Nur Typen t, die alle Operationen des Typs t' aufweisen, dürfen für v eingesetzt werden.

Anwendung:– alle funktionale Sprachen– C++ (templates), Eiffel, Sather, Pizza (Java-Erweiterung), generic Java

(mit Einschränkungen, zukünftiges Java?), Ada (aber leicht anders)


Wie definiere ich Typen?

Basis bilden vordefinierte Typen der Sprache

Klassische Typkonstruktoren:

– Verbund

– Vereinigung

– Funktion

– Reihung (Feld)

– Referenz

Programmiererdefinierte abstrakte Datentypen (Module, Klassen)


Typkonstruktoren

Verbund: T1 × T2 × ... × Tn

Vereinigung: T1 ∪ T2 ∪ ... ∪ Tn

Funktion: T1 → T2 → ... → Tn

Reihung (Feld): I1 × I2 × ... × In → T'

Referenz: ↑T'

Spezialfall Ausschnittstyp: Teilmenge der Werte eines vorgegebenen skaleren oder Reihungstyp


Verbund

T = T1 × T2 × ... × Tn definiert ADT– die Elemente der Tupel heißen Felder, bezeichnet durch Feldbezeichner

Feldbezeichner und/oder (sprachabhängig) Reihenfolge der Felder Bestandteil des Typs

Konstruktoren: K1 × K2 × ... × Kn , Ki: beliebiger Konstruktor für Ti

Projektionen (Zugriff auf Felder):f1 : T → T1

f2 : T → T2

...

fn : T → Tn

Zuweisung (auch an einzelne Felder) ändert Gesamtverbund!


Vereinigung

T = T1 ∪ T2 ∪ ... ∪ Tn definiert ADT

Konstruktoren: K1 ∪ K2 ∪ ... ∪ Kn, Ki: Konstruktor für Ti

Operationen:O1 ∪ O2 ∪ ... ∪ On mit Oi: Menge der Operationen von Ti

∪ bezeichnet disjunkte Vereinigung: Ti bezeichnet Typ mit Nummer i,für i ≠ j ist Ti per definitionem verschieden von Ti.

Alternative:– normale Vereinigung T = T1 ∪ T2 ∪ ... ∪ Tn, alle Ti verschieden (nicht typsicher)– Verbund mit Varianten/Oberklasse mit Unterklassen,

Variante eines Verbunds kann selbst ein Verbundtyp seinVariantenzeiger in Pascal/Modula explizit, in oo Sprachen implizit


Funktion

T = T1 → T2 → ... → Tn definiert ADT

Konstruktoren:– Funktions- oder Prozedurdefinition mit Argumenten

T1, T2, ... und Resultat Tn

– Ausdruck mit Blättern T1, T2, ... und Resultat Tn

Operationen:bind T = T1 → (T2 → ... → Tn) (curryen)eval T1 → T2 → ... → Tn

bind proc (T,T') (T) liefert proc(T'): in oo Sprachen: a+b = a.plus(b): 1. binde a, 2. einstellige Addition +b.

Haskell Curry: amerikanisch/niederländischer Logiker (kombinatorische Logik)


Reihung

T = I1 × I2 × ... × In → TE definiert ADT– Indexmengen Ii endlich: Ausschnitt aus ganzen Zahlen oder

Aufzählungstyp,– Elementtyp: TE

Konstruktoren:KE | I1 | × |I2 | × ... × | InI , wobei |Ii| Kardinalität der Indexmenge Ii

Operationen: Zugriff auf Elemente:get : T × I1 × I2 × ... ×In → TE

set : T × I1 × I2 × ... × In × TE → T

Zuweisung an Elemente bedeutet Zuweisung an Gesamtreihung! Unterscheide:

– statische Reihung: Indexmengen statisch fest.– dynamische Reihung: Indexmengen bei Konstruktion fest.– flexible Reihung: Indexmengen durch Zuweisung änderbar

Theoretisch gehören Indexmengen Ii zum Typ, statische Reihungen Praktisch zählt nur die Anzahl n der Stufen zum Typ.


Referenz

T = ↑ TE definiert ADT Konstruktoren:

new KE, wobei KE Konstruktor von TE void (nil)

Operationen: Zugriff auf Inhalt (dereferenzieren)

<> : T → TE

Adreßarithmetik + - : T × INT → T

- : T × T → INT

Unterscheide left hand value (Referenz), right hand value (Inhalt) Dereferenzieren in einigen Sprachen explizit, in oo Sprachen implizit

Statt ↑TE schreibt man oft ,,ref TE''


Gleichheit von Typen

In Sprachen mit Typvereinbarungen heißen zwei Typen s, t gleich, entweder wenn sie namensgleich sind (Bezeichner s, t identisch, gleiche Vereinbarung) oder wenn sie strukturell gleich sind

– verlangt ist Gleichheit der legalen Zugriffe auf Objekte von s, t, d.h., die Annahme s=t führt nicht zum Widerspruch: bei Verbunden/Klassen: alle Felder gleich (Bezeichner und Typ) bei Reihungen: Anzahl der Stufen und Elementtyp ...

Beispiel in Pascal-Syntax:– T1 = record a: INT; b: ↑ T1 end

– T2 = record x: INT; y: ↑ T1 end

– T3 = record a: INT; b: ↑ record a: INT; b: ↑ T1 end end

– T1 ,T3 strukturgleich, T2 nicht Namensgleichheit ist die Regel. Aber:

– Auch verschieden benannte Reihungstypen mit gleichem Elementtyp sollen gleich sein:– sonst Schwierigkeiten bei Operationen aus Paket 1

angewandt auf Reihungen aus Paket 2.


Strukturelle Konformität

Ordnung auf Typen T1 < T2: Alle Operationen von T2 auch in T1 zulässig: T1 heißt strukturell konform zu T2.

Wichtig bei parametrisierten Typen T(T') und Unterklassen T" von T:Unabhängig davon, welcher Typ T" für T' eingesetzt wird, müssen die in den Operationen von T verlangten operativen Eigenschaften von T" gewährleistet werden.

Beispiel: Operation von T setzt Ordnung der Elemente von T' voraus: Dann muß T" auch tatsächlich die Ordnung a < b für seine Elemente definieren.

Vorsicht: Die Programmiersprache überprüft bei struktureller Konformität nur die Signatur, nicht die semantische Bedeutung!

procedure p(x: R): R' in T1 definiertprocedure p(x: S): S' in T2 definiertT1 < T2 wennkontravariant: Parametertypen S strukturell konform zu Rkovariant: Ergebnistyp R' strukturell konform zu S'


ADT: Spezifikation vs.Implementierung

Ziel bei ADTs: Geheimnisprinzip, Freiheit bei der Implementierung

Unterscheidung zwischen der Spezifikation und der Implementierung eines abstrakten Datentyps (ADT):

Methode 1: keine Unterscheidungklassischer OO-Ansatz

Methode 2: abstrakte Klasse als Spezifikation, Unterklassen als Implementierungexistiert z.B. in ADA und Modula mit Paketen und Moduln, Paket, d.h. Spezifikation, und Paketrumpf sind getrenntNachteil: nur eine Implementierung

Methode 3: Ansatz von DelegationKlasse enthält lokales Attribut, das lokale Repräsentation darstellt, alle Operationen werden darauf ausgeführt, vergleiche Delegationsmuster


Repräsentationswechsel bei Polymorphie

Wann ist ein Repräsentationswechsel bei polymorphen Aufrufen erlaubt?

Beispiel: ADT Keller, implementiert durch Listen und doppelt verkettete Listen

ADT Keller dargestellt als abstrakte Oberklasse, beide Implementierungen als Unterklassen

Unterscheidung zwischen Kernmethoden und abgeleiteten Methoden

abstrakte Klasse muß geeignete Methoden definieren, die ohne Kenntnis der beiden Implementierungen von einer Repräsentation zur anderen wechseln können, z.B. beim Kopieren

Siehe Konzepte objektorientierter Sprachen

Documents

Höhere Programmiersprachen Wintersemester 2004/2005 fileProf. Dr. Gerhard Goos, Dr. Sabine Glesner Höhere Programmiersprachen WS 2004/2005: Teil 1 Grundlagen 2 Übung Höhere Programmiersprachen