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 [email protected]

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


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


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


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


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


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


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'


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


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


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)


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


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


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


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


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)


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


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 ();;


19

Anonyme Funktionen

• Definition:(fun argument -> expression)


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


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]


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;;


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


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


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


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.


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


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?


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


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 [email protected]


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.


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


33

Übung 1

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

Algorithmus vorgegeben


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

Documents

Konzepte der Programmiersprachen SS 2004 Dipl.-Inf. Christoph