Konzepte der Programmiersprachen SS 2004 Dipl.-Inf. Christoph

Konzepte der Programmiersprachen SS 2004http://www.st.informatik.tu-darmstadt.de/static/pages/lectures/pl/ss04/assignments/index.html

Dipl.-Inf. Christoph Bockischbockisch@informatik.tu-darmstadt.de

Darmstadt University of Technology

Übung

Einführung in Objective Caml

PL SS04 Übung Christoph Bockisch

2

Übersicht

• ML: Meta-Language– Funktionale Programmiersprache– Automatische Speicherverwaltung– Statische Typsicherheit– (Fast) keine Seiteneffekte– Pattern-Matching– …

• Caml: Categorical Abstract Machine Language– Gehört zur Sprachfamilie ML– Basiert auf der Categorical Abstract Machine

(CAM)– Entwickelt seit 1987 am INRIA Institut, Frankreich

• Objective Caml (O‘Caml) seit 1996– Objekt-orientierte Features

PL SS04 Übung Christoph Bockisch

3

Programmieren in O‘Caml

• O‘Caml System– Zum Ausprobieren– Read-Evaluate-Print– Toplevel mit „ocaml“ aus Kommandozeile

starten– Oder O‘Caml Windows– „Mysteriöse Fehler“ bei Copy & Paste

wegen falscher Zeilenumbrüche

• O‘Caml Compiler– Programm mit Editor schreiben– Endung .ml– Compiler „ocamlc“ aufrufen– Programm „camlprog“ ausführen

PL SS04 Übung Christoph Bockisch

4

O‘Caml Programmiersprache

• Kommentare eingeschlossen von (* und *)– Kommentare können verschachtelt sein

• Bezeichner bestehen aus Zahlen, Buchstaben und _– Beginnen mit einem Kleinbuchstaben– O‘Caml ist case-sensitiv

• Mit let können Konstanten definiert werden

• Funktionen sind Werte!• Ein Ausdruck wird mit ;; beendet

PL SS04 Übung Christoph Bockisch

5

Erste Gehversuche(O‘Caml System)

# 1 + 1 ;;- : int = 2

Eingabe

Name

Typ

Wert

# let five = 5 ;;val five : int = 5 Ein benannter

Wert

# let succ n = n + 1 ;;val succ : int -> int = <fun>

# succ five ;;- : int = 6

Funktionstyp

Funktion als Wert

PL SS04 Übung Christoph Bockisch

6

Erste Gehversuche(O‘Caml Compiler)

• Programm in Datei mit Endung .ml• Nur Definitionen sichtbar, die weiter oben

stehen• Sequenz von Ausrücken:expr1; … ; exprn

– Wertet alle Ausdrücke der Reihenfolge nach aus

– Hat den Wert des letzten Ausdrucks– expr1 bis exprn-1 sollten Typ unit haben

– ; nur zwischen zwei Ausdrücken (nicht danach)

• ;; beendet Ausdruck– Nur benötigt, wenn von Compiler nicht

feststellbar

PL SS04 Übung Christoph Bockisch

7

Erste Gehversuche(O‘Caml Compiler)

let succ n = n + 1

let rec add (a, b) = if a = 0 then b else succ (add (a - 1, b));;

print_string "5 + 6 = ";print_int (add (5, 6)) Sequenz

Compiler erkennt neuen Ausdruck

wegen let

Compiler erkennt neuen Ausdruck

nicht selbst

Compiler erkennt neuen Ausdruck wegen

Dateiende

PL SS04 Übung Christoph Bockisch

8

Primitive Typen

• int0, 5, 42, -17, 0x00FF– Negative ints müssen (oft) eingeklammert

werden: (-1)• float0.0, -5.3, 1.7e14, 1e-10– Dürfen nicht mit . anfangen

• booltrue, false

• string"", "One\nTwo\nThree"

• char'a', '\n'

PL SS04 Übung Christoph Bockisch

9

Operatoren

• Arithmetische operatoren für ints:+ - * /

• Arithmetische operatoren für floats:+. -. *. /.

• Es gibt keine implizite Typkonvertierung– float_of_int– int_of_char– int_of_string (konvertiert "10" zu 10)– …

• Vergleichoperatoren für Primitive:< <= = <> >= >

• Boole’sche Operatoren (shortcut Evaluierung):&& || not

PL SS04 Übung Christoph Bockisch

10

Operationen für string / char

• Konkatenation:^

• Das Modul String enthält weitere Funktionen zur Behandlung von strings– String.length s– String.index s c– String.sub s p n– String.uppercase s– String.capitalize s

PL SS04 Übung Christoph Bockisch

11

Listentypen

• In [ ] eingeschlossen• Einzelne Elemente durch ; getrennt• Alle Elemente müssen denselben Typ

haben• Leere Liste:[]

• Beispiele:– int list– float list– 'a list (wenn der Elementtyp unbekannt

ist)

PL SS04 Übung Christoph Bockisch

12

Operationen für Listen

• Element vorne an Liste anfügen:::

• Zwei Listen verbinden:@

• Das Modul List enthält weiter Funktionen– List.hd l– List.tl l– List.length l– List.nth l n

PL SS04 Übung Christoph Bockisch

13

Tupeltypen

• Durch ( ) eingeschlossen• Die Elemente durch , getrennt• Elemente können verschiedene Typen

haben• Anzahl der Elemente fest• Beispiele:

– (int * int)– (string * float * int list)

• Spezialfall Paare (pair)– Funktionen fst und snd zum Zugriff auf erstes /

zweites Element

• Weitere Funktionen durch Pattern-Matching• Leeres Tupel: () oder unit

PL SS04 Übung Christoph Bockisch

14

Recordtypen

• Definition:type {name1:typ1;…;namen:typn}

• Erzeugung von Records:let const={name1=val1;…;namen=valn}

• Zugriff auf Records:const.name1

• Allgemein:expression.name

PL SS04 Übung Christoph Bockisch

15

Parametrisierte Typen

• Definition:type ('a1 … 'an) name = typedef

• Beliebige Anzahl von Typvariablen als Tupel• Typvariablen fangen mit ' an• Ansonsten wie andere Bezeichner• Typvariablen können in Typdefinition

verwendet werden• Beipiele:

– type 'param paired_with_int=int*'param;;– 'a list

PL SS04 Übung Christoph Bockisch

16

if … then … else Ausdruck

• Schreibweise:if boolean-expression then expression1 else expression2

• Else-Teil wird benötigt, damit der Ausdruck immer einen Wert hat

• Then- und Else-Teil müssen denselben Typ haben

• Then-Teil wird nur ausgewertet, wenn die Bedingung true ist (umgekehrt für Else-Teil)

PL SS04 Übung Christoph Bockisch

17

Definition von Funktionen

• Übernehmen ein Argument• Geben einen Wert zurück• Argument und Rückgabewert

– Können Tupel sein (mehrere Werte)– Können unit sein (kein Wert)

• Mit let rec werden rekursive Funktionen definiert

• and verknüpft let Definitionen– Können sich gegenseitig sehen

• Auswerten einer Funktion:function_name argument

PL SS04 Übung Christoph Bockisch

18

let / let rec / and

let factorial n = if n = 0 then 1 else n*(factorial n–1);;

let rec factorial n = if n = 0 then 1 else n*(factorial n–1)

let ping n = if n > 0 then pong n–1; else ()

let pong n = if n > 0 then ping n–1; else ();;

let rec ping n = if n > 0 then pong (n - 1) else ()and pong n = if n > 0 then ping (n - 1) else ();;

PL SS04 Übung Christoph Bockisch

19

Anonyme Funktionen

• Definition:(fun argument -> expression)

PL SS04 Übung Christoph Bockisch

20

match

• match Ausdruck:match expr with pattern1 -> expr1

| …| patternn -> exprn

• Die Ausdrücke expr1 bis exprn müssen denselben Typ haben

• Die Patterns sollten alle möglichen Fälle abdecken– Sonst Warung vom Compiler

• Die Patterns werden in angegebener Reihenfolge getestet

PL SS04 Übung Christoph Bockisch

21

Generalized Assignment

# let (a, b, c) = (8, 3, 6);;

val a : int = 8

val b : int = 3

val c : int = 6

# let (x::xs) = [1;2;3;4];;

(* Non-exhaustive match warning deleted *)

val x : int = 1

val xs : int list = [2; 3; 4]

PL SS04 Übung Christoph Bockisch

22

Pattern-Matching

• Generalized Assignment auch in Patterns

• Das Pattern (x :: xs) entspricht einer nicht leeren Liste

# let rec listSize the_list =

match the_list with

[] -> 0

| (x::xs) -> 1 + listSize xs;;

PL SS04 Übung Christoph Bockisch

23

Higher-Order Funktionen

• Eine First-Order Funktion ist eine Funktion, deren Argument und Wert “Daten” sind

• Bei einer Second-Order Funktion ist Argument oder Wert eine First-Order Funktion

• Eine Higher-Order Funktion hat beliebige Funktionen als Argument oder Wert

• O’Caml unterstützt Higher-Order Funktionen

PL SS04 Übung Christoph Bockisch

24

Typinferenz

• Der O‘Caml Compiler kann an Funktionsdefinitionen erkennen, welchen Typ Argument und Ergebnis haben

• Wenn der Typ nicht bestimmbar ist, wird Typvariable eingesetzt– Die Funktion heißt dann „polymorph“– Nicht zu verwechseln mit Polymorphie bei

OO Sprachen

PL SS04 Übung Christoph Bockisch

25

Typinferenz

# let add (a, b) = a + b;;val add : int * int -> int = <fun>

Integeraddition: Operanden und Ergebnis müssen ints

sein

# let rec reverse the_list = match the_list with [] -> [] | h :: t -> reverse t @ [h];;val reverse : 'a list -> 'a list = <fun>

Listenoperationen: Operanden und Ergebnis müssen Listen

sein

Elementtypen sind gleich

PL SS04 Übung Christoph Bockisch

26

Ein- / Ausgabe

• Funktionen, die auf die Konsole schreiben– print_int arg– print_string arg– …– print_newline ()

• Funktionen, die von Tastatur lesen– read_line

Hat einen string als Rückgabewert

• Modul Printf

# print_newline () ;;

- : unit = ()

Erwartet Wert von Typ unit. Nur unit

selbst hat den Wert.

PL SS04 Übung Christoph Bockisch

27

Referenzen

• Objective Caml Homepage: http://www.ocaml.org/

• Komplette Dokumentation und Referenz: „Developing Applications with Objective Caml“, E. Chailloux, P. Manoury, B. Pagano, O’Reilly:http://caml.inria.fr/oreilly-book/html/

• Kurze Einführung und Zusammenfassung: „A Concise Introduction to Objective Caml“, D. Matuszek: http://www.csc.vill.edu/~dmatusze/resources/ocaml/ocaml.html

• Tutorial: „A C++/Java Programmer’s introduction to Objective Caml“, S. Houben: http://caml.inria.fr/FAQ/stephan.html

• Geschichte von Caml: http://www.pps.jussieu.fr/~cousinea/Caml/caml_history.html

PL SS04 Übung Christoph Bockisch

28

Übung 1

• Aufgabe 1 (Bearbeitung bis 30.4.):– O‘Caml Dokumentation lesen– Übungsaufgaben daraus bearbeiten– Können Sie Muster formulieren, wie

bestimmte Problemstellungen gelöst werden?

– Oder Coding-Styles?

PL SS04 Übung Christoph Bockisch

29

Übung 1

• Aufgabe 2 (Bearbeitung bis 30.4.):– O‘Caml wertet Ausdrücke „eager“ aus:

– Das Gegenteil ist eine „lazy“ Auswertung:

– Beweisen Sie dass O‘Caml eager auswertet– Verwenden Sie nach Möglichkeit keine

Seiteneffekte

let mult (x, y) = x * y;;mult (1 + 2, 3 + 4) mult (3, 3 + 4) mult (3, 7) 3 * 7 21

mult (1 + 2, 3 + 4) (1 + 2) * (3 + 4) 3 * (3 + 4) 3 * 7 21

PL SS04 Übung Christoph Bockisch

30

Übung 1

• Aufgabe 2.a)– Wie kann „lazy“ Auswertung dennoch

erzwungen werden?– Benutzen Sie nicht das Schlüsselwort lazy

und Modul Lazy– Funktion und Argument dürfen angepasst

werden– Bonusaufgabe: Ein Bonus-Prozentpunkt

für• Korrekte Bearbeitung• Kurze (5 – 10 Min.) Präsentation• Eingereicht bis 29.4.• An bockisch@informatik.tu-darmstadt.de

PL SS04 Übung Christoph Bockisch

31

Übung 1

• Aufgabe 3 (Bearbeitung bis 30.4.):– Gegeben sind Funktionsdefinitionen– Bestimmen Sie den Typ der Funktionen– Bestimmen Sie, welche Funktionen partiell

sind– Geben Sie für partielle Funktionen ein

Beispiel an, das nicht akzeptiert wird.

PL SS04 Übung Christoph Bockisch

32

Übung 1

• Aufgabe 4 (Bearbeitung bis 7.5.):– Programmieren Sie ein Mancala Spiel

S1F0

S1F1

S1F2

S1F3

S1F4

S1F5

S1G

S2G

S2F5

S2F4

S2F3

S2F2

S2F1

S2F0

PL SS04 Übung Christoph Bockisch

33

Übung 1

• Aufgabe 4, Zusatzaufgabe:– Intelligenter Computerspieler– Implementierung des Negamax-

Algorithmus vorgegeben

PL SS04 Übung Christoph Bockisch

34

Übung 1

• Das Übungsblatt mit weiteren Quellen und weitere Materialien können heruntergeladen werden:

http://www.st.informatik.tu-darmstadt.de/static/pages/lectures/pl/ss04/assignments/

index.html