Algorithmen und Programmierung I Funktionale ... - Informatik · Einführung ALP I: M. Esponda, 1. Vorlesung 1958 schrieb McCarthy ein Paper mit einem einfachen Lisp- Interpreter,

WS 2012/2013

Prof. Dr. Margarita Esponda

1

Algorithmen und Programmierung IFunktionale Programmierung

ALP I: M. Esponda, 1. Vorlesung


Inhalt

Inhalt

2

1. Einführung in die Funktionale Programmierung

(Haskell):

2. Grundlagen der Berechenbarkeit:

3. Das Beweisen von Programmeigenschaften:

4. Implementierung und Programmiertechnik:


Inhalt

1. Einführung in die Funktionale Programmierung

3

• Ausdrücke und Primitive Datentypen

• Funktionsdefinitionen

• Listen, Tupel, Zeichenketten

• Rekursion vs. Iteration

• Such- und Sortieralgorithmen

• Funktionen höherer Ordnung

• Polymorphie

• Typsystem, -herleitung und -überprüfung

• Algebraische und abstrakte Datentypen


Inhalt

2. Grundlagen der Berechenbarkeit

4

• Lambda-Kalkül

• Kombinatoren

• Turing-Maschine

• Registermaschine

• Primitive Rekursion

• µ-Rekursion


Inhalt

3. Das Beweisen von Programmeigenschaften

5

• Termersetzung

• Strukturelle Induktion

• Terminierung, Implementierung und Programmiertechnik


Inhalt

4. Implementierung und Programmiertechnik

• Auswertungsstrategien für funktionale Programme

• Modularer Programmentwurf

6


Literatur

7

✴ The Craft of Functional ProgrammingThird Edition. 2011. Addison-Wesley. Pearson.Simon Thompson.

✴ Real World HaskellO'Reilly. 2009.Bryan O'Sullivan, Don Stewart, and John Goerzen.

✴ Programming in HaskellCambridge University Press, 2007. Graham Hutton.

Literatur


Vorlesung & Übungen

Vorlesungen & Übungen

8

1. Regelmäßige und aktive Teilnahme in der Vorlesung

Fragen stellen!

2. Regelmäßige und aktive Teilnahme an den Übungen

Selbständige Lösung der Übungsblätter!

Grundlegende Regeln zum Erfolg sind:


Mitschriften

Warum ist Mitschreiben wichtig?

Das Mitschreiben hat folgende Vorteile:

✴ Es erhöht die Aufmerksamkeit und fördert die Konzentration

✴ Es regt dazu an, sich aktiv zu beteiligen

✴ Es individualisiert den Lernstoff und bildet eine gute Grundlage für die Klausurvorbereitung

Fragen zuerst aufzuschreiben hat viele Vorteile.

9


Vorlesung & Übungen

10

Tutoren

Lucas Jacob

Simon Tippenhauer

Nicolas Lehmann

Oliver Wiese

Terese Haimberger

?

?

?

?

?


Kriterien des Leistungsnachweises

Kriterien für die Bestätigung der aktiven Teilnahme:

11

1. Eine regelmäßige Teilnahme an den Laborterminen ist unerlässlich.

2. Die Abgabe der Übungsblätter erfolgt montags um 10:10 Uhr. Nach diesem

Termin abgegebene Übungsblätter werden nicht berücksichtigt.

3. Jeder Student muss an mindestens n-2 Übungsterminen anwesend sein.

4. Jeder Student muss n-2 Übungsblätter bestehen. Ein Übungsblatt gilt als

bestanden, wenn man mind. 40% der zu erreichenden Punkte erreicht hat.

5. Jeder Student muss 60% der maximal erreichbaren Punktzahl aus allen

Übungsblättern erreichen.

6. Jeder Student muss mindestens zwei Mal seine Lösungen vorrechnen. Wer

jeweils vorrechnen muss, wird per Zufall am Anfang des jeweiligen Tutoriums

entschieden.



Regelung für die Notenvergabe

12

Die Prüfungsnote ergibt sich aus dem Wert folgenden Ausdrucks

Dabei sind:

z - die Anzahl der erreichten Punkte in der Zwischenklausur (Stoff der ersten Semesterhälfte) k - die Anzahl der erreichten Punkte in der Endklausur (Stoff des ganzen Semesters)

n - die Anzahl der erreichten Punkte in der Nachklausur (Stoff des ganzen Semesters)

Zum Bestehen der Prüfung muss dieser Wert mindestens 50 Punkte betragen. Jede Klausur hat dabei eine maximale Punktzahl von 100.

max z + k2,k, z + n

2,n⎛

⎝⎜⎞⎠⎟



• Zusätzlich ist es den Teilnehmern möglich durch besonders

aktive mündliche Teilnahme an den Tutorien die Gesamtnote

um maximal 0,7 zu verbessern. Diese Bewertung wird von

den Tutoren individuell vorgenommen.

• Durch diese Verbesserung kann ein Bestehen der Klausur

nicht erreicht werden.

• Die beste zu erreichende Note ist 1,0.

13

Verbesserungsmöglichkeiten


Fragen

14

Fragen

Inhaltliche Fragen sind immer willkommen

– während und nach jeder Vorlesung

– in der Sprechstunde (Freitags 8 -11)


Keine Laptops

15

NO LAPTOPS

NO iPADS

NO HANDYS

NO MUSIK-

Geräte


Homepage

http://www.inf.fu-berlin.de/lehre/WS12/ALP1/

Vorlesungsfolien

Literaturliste

Übungen

Zusätzliches Material

wichtige Nachrichten

[email protected]

16

Sprechstunde: Fr. 8:00 - 11:00 Uhr

Raum 161

Homepage


Homepage

17

Warum Funktionales Programmieren?

Warum Haskell?

Wie so nicht F#?

Warum nicht Dart oder Ceylon oder Rust?


Wie viele Programmiersprachen?

18

Es gibt mehr als 2000 Programmiersprachen, die im kommerziellen

Bereich bekannt sind oder gewesen sind.

✴ mehr als 200 davon haben sich im Laufe der Geschichte stärker

verbreitet

✴ (einige) Firmen entwickeln eigene private Sprachen

✴ es gibt viele akademische Programmiersprachen

✴ und es kommen immer mehr Programmiersprachen hinzu

Einführung


Kurz über die Geschichte der Programmiersprachen

Sammet, J. Programming Languages. History and Fundamentals. Prentice Hall, 1969.

19


30er Jahre

20

Alonzo Church1903-1995

Stephen C. Kleene1909-1994

Lambda-Kalkül ✴universelle abstrakte Programmiersprache

✴nur die Hardware fehlte

Erste Programmiersprache

λ − Kalkül

Lisp 1958

Funktionale Programmiersprachen

Miranda HaskellFP

ALP I: M. Esponda, 1. Vorlesung 21

30er Jahre

Alan Turing (1912-1954)

“On computable numbers, with an

application to the Entscheidungsproblem”.

1936

Turing-Maschine

Ein Modell, um die Klasse der intuitiv berechenbaren Funktionen zu bilden.

Einführung


Erste Programmgesteuerte Maschine

Jacquard Looms

1801

"Programm

Lochkarten-Steuerung der Jacquard-Maschine

22


Einführung

Programmgesteuerter Rechner

1941 Konrad Zuse

Maschinensprache

Programm

23

Einführung


Programmierung

eigentlich kein Programm

24

Steinzeit der elektronischen Computer

Einführung


40er JahreDas Wort Software existierte noch nicht.

✴ die ENIAC hatte keine Software

✴ am Anfang stand "Layette" bei der UNIVAC Corporation

für die Programme

✴ Wurde später es durch das Wort "Software" ersetzt

25

Einführung


Konzepte imperativer Programmierung

Die eigentliche Geschichte der imperative Programmiersprachen

begann mit:

• dem Konzept der von Neumann-Maschine, die 1945 die

Notwendigkeit eines gespeicherten Programms postulierte.

• und mit dem Konzept des "conditional control transfer"

• If-then-Anweisung

• looped-Anweisungen

• Subroutines (Funktionen)

Einführung


Was ist ein Programm?

✴ Ein Programm ist eine Folge von Anweisungen, die auf einer

Maschine ausgeführt werden können.

✴ Ein Programm ist die Formulierung eines Algorithmus in einer

konkreten Programmiersprache.

✴ Ein OO-Programm ist ein System kooperierender Objekte.

27

Imperative Programmiersprachen



28

LOAD #1 C

LOAD #2 B

MULT #1 #2 #3

LOAD #4 A

ADD #3 #4 #1

STORE #1 C

Maschinensprache

0101000101101011

0101001011110101

0111000100100011

0101010001010110

0010001101000001

0000000101101011

....

Assembler-

Programmiersprache

Höhere

Programmiersprachen

C = A + B*C

50er Jahre



29

CPU

Programmsteuerungs-Einheit

ALU

Anweisungen

Daten

Programme

DatenRegister

Arithemitc and Logic Unit (Rechenwerk)

Speicher

LOAD #1 5

ADD #1 #2 #3STORE #3 7

JUMP 100

Einführung


Imperatives Programmieren

• Ältestes und populärstes Programmierparadigma

– Fortran, Cobol, Algol, C, Basic, Pascal, Modula,

Java, usw.

• Widerspiegelt die dahinter stehende Hardware-

Architektur

– von Neumann Maschine

– gespeichertes Programm + Daten

Einführung


Höhere Programmiersprachen

CobolCOmmon Business Oriented LanguageFORmula TRANslator

John Backus

Grace Hopper

31

1955

1959

Einführung



LISt Processor

Lisp

John McCarthy

32

1958

Einführung


1958 schrieb McCarthy ein Paper mit einem einfachen Lisp- Interpreter, der

wiederum in Lisp geschrieben war.

Lambda-Kalkül ist die grundlegende Basis für seine minimalen Lisp-Funktionen.

Es gibt keinen grundsätzlichen Unterschied zwischen Daten und

Programmanweisungen.

Dies ermöglicht unter anderem, Programme zur Laufzeit beliebig zu manipulieren

Ein Lisp-Programm ist eine Liste, die einen abstrakten Syntaxbaum darstellt.

( + (+ a (* b c) d ))

33

Lisp


Geschichtliche Einführung

34

Deklarative Sprachen Imperative Sprachen

ObjektorientierteProgrammiersprachen

Was? Wie?


Funktionale Sprachen

Logische Sprachen

Prozedurale

AspektorientierteProgrammiersprachen

in ALP IIin ALP I



deklarativ vs. imperativ

-Sprachen basieren auf einem

mathematischen Formalismus

-Wissen über ein Problem rein

deklarativ darstellbar

- Intelligentes System, das Fragen

an das Programm beantworten

kann

-Sprachen sind von der

dahinterstehenden Hardware

geprägt

-Befehlssequenz (Zustände)

- zeitlicher Ablauf im Programm

sichtbar

kompakter

robuster

einfacher

effizienter

35

Einführung


Was ist ein Programm?

✴ Ein Funktionales Programm ist eine Menge von

Funktionsdefinitionen.

✴ Eine Funktion bindet eine Variable an einen Wert.

✴ Die Ausführung des Programms wird mit der Auswertung

eines Ausdrucks gestartet, die mit Hilfe der Funktionsmenge

erfolgt.

36

Funktionale Programmiersprachen



Deklarative Programmiersprachen

Mutter( luise, maria ).Mutter( anne, maria ).Mutter( maria, andrea ).

Vater( luise, peter ).Vater( maria, joachim ).

Oma( X, Y ) :- Mutter( X, Z ), Mutter( Z, Y ).Oma( X, Y ) :- Vater( X, Z ), Mutter( Z, Y ).

Geschwister( X, Y ) :- Mutter( X, Z ), Mutter( Y, Z ).Geschwister( X, Y ) :- Vater( X, Z ), Vater( Y, Z ).

?Oma( anne, andrea ).

Programm in Prolog

37


Normalisierte Ergebnisse aus der Popularität in:

- Open-Source-Projekte

- Powell`s Books

- Job-Angebot

- Popularität in der Software-Industrie

- Google Code Search

- usw.

Quelle: http://langpop.com/ (DedaSys. Open Source Consulting) 2011

In der realen Welt verwendete Sprachen

38


TIOBE Programming Community Index

(Oktober 2012)

Beliebteste Programmiersprachen

Einführung


Deklarative Programmiersprachen

1950 1960 1970 1980 1990 2000 2010

LISP COMMON LISP COMMON LISP ANSI

FP

PROLOG PARLOG

Clean

Erlang

SCHEME

SASL

HOPE

ML

FL

Haskell Curry1900-1982

Caml

MIRANDA HASKELL

OCaml

40

Einführung


Software-Krise

• John Bakus

• 1977

• Lecture for the ACM Turing award session

"Can Programming be liberated from the von Neumann Style? A

Functional Style and its Algebra of Programs“

• FP (Funktionale Programmiersprache)

41

Einführung


Warum Haskell?✴ sehr einfach

✴ Programme sind klein, übersichtlich und einfacher zu warten

✴ sehr nützlich als Spezifikationssprache

✴ Programmeigenschaften sind einfacher zu beweisen

✴ Algorithmen können auf einem höheren Niveau formuliert und analysiert

werden

✴ Moderne Programmiersprache

✴ mit ständiger Verbreitung im kommerziellen Bereich

42

Einführung


Warum Haskell?

43

✴ Haskell ist geeignet an Stellen, wo Sicherheit und fehlerfreie Software

vor Geschwindigkeit steht.

In Haskell implementierte Software:

• Xmonad windows manager für Linux

• Cryptol Language (www.cryptol.net)

• Facebook (Projekte und Tools)

• usw.

Programmiersprachen, die das Funktionale Paradigma unterstützen

sind im Trend.

Beispiel: F#, Erlang und Scale.

The International Obfuscated C Code Contest /*

+ + + + [ >i>n[t */ #include<stdio.h> /*2w0,1m2,]_<n+a m+o>r>i>=>(['0n1'0)1; */int/**/main(int/**/n,char**m){FILE*p,*q;int A,k,a,r,i/* #uinndcelfu_dset<rsitcdti_oa.nhs>i/_*/;char*d="P%" "d\n%d\40%d"/**/ "\n%d\n\00wb+",b[1024],y[]="yuriyurarararayuruyuri*daijiken**akkari~n**" "/y*u*k/riin<ty(uyr)g,aur,arr[a1r2a82*y2*/u*r{uyu}riOcyurhiyua**rrar+*arayra*=" "yuruyurwiyuriyurara'rariayuruyuriyuriyu>rarararayuruy9uriyu3riyurar_aBrMaPrOaWy^?" "*]/f]`;hvroai<dp/f*i*s/<ii(f)a{tpguat<cahfaurh(+uf)a;f}vivn+tf/g*`*w/jmaa+i`ni("/** */"i+k[>+b+i>++b++>l[rb";int/**/u;for(i=0;i<101;i++)y[i*2]^="~hktrvg~dmG*eoa+%squ#l2" ":(wn\"1l))v?wM353{/Y;lgcGp`vedllwudvOK`cct~[|ju {stkjalor(stwvne\"gt\"yogYURUYURI"[ i]^y[i*2+1]^4;/*!*/p=(n>1&&(m[1][0]-'-'||m[1][1] !='\0'))?fopen(m[1],y+298):stdin; /*y/riynrt~(^w^)],]c+h+a+r+*+*[n>)+{>f+o<r<(-m] =<2<5<64;}-]-(m+;yry[rm*])/[* */q=(n<3||!(m[2][0]-'-'||m[2][1]))?stdout /*]{ }[*/:fopen(m[2],d+14);if(!p||/* "]<<*-]>y++>u>>+r >+u+++y>--u---r>++i+++" <)< ;[>-m-.>a-.-i.++n.>[(w)*/!q/**/) return+printf("Can " "not\x20open\40%s\40" "" "for\40%sing\n",m[!p?1:2],!p?/* o=82]5<<+(+3+1+&.(+ m +-+1.)<)<|<|.6>4>-+(> m- &-1.9-2-)-|-|.28>-w-?-m.:>([28+ */"read":"writ");for ( a=k=u= 0;y[u]; u=2 +u){y[k++ ]=y[u];}if((a=fread(b,1,1024/*,mY/R*Y"R*/,p/*U*/)/* R*/ )>/*U{ */ 2&& b/*Y*/[0]/*U*/=='P' &&4==/*"y*r/y)r\}*/sscanf(b,d,&k,& A,& i, &r)&& ! (k-6&&k -5)&&r==255){u=A;if(n>3){/*]&<1<6<?<m.-+1>3> +:+ .1>3+++ . -m-) -;.u+=++.1<0< <; f<o<r<(.;<([m(=)/8*/u++;i++;}fprintf (q, d,k, u >>1,i>>1,r);u = k-5?8:4;k=3;}else /*]>*/{(u)=/*{ p> >u >t>-]s >++(.yryr*/+( n+14>17)?8/4:8*5/ 4;}for(r=i=0 ; ;){u*=6;u+= (n>3?1:0);if (y[u]&01)fputc(/* <g-e<t.c>h.a r -(-).)8+<1. >;+i.(<)< <)+{+i.f>([180*/1* (r),q);if(y[u ]&16)k=A;if (y[u]&2)k--;if(i/* ("^w^NAMORI; { I*/==a/*" )*/){/**/i=a=(u)*11 &255;if(1&&0>= (a= fread(b,1,1024,p))&& ")]i>(w)-;} { /i-f-(-m--M1-0.)<{" [ 8]==59/* */ )break;i=0;}r=b[i++] ;u+=(/**>> *..</<<<)<[[;]**/+8&* (y+u))?(10- r?4:2):(y[u] &4)?(k?2:4):2;u=y[u/* 49;7i\(w)/;} y}ru\=*ri[ ,mc]o;n}trientuu ren ( */]-(int)'`';} fclose( p);k= +fclose( q); /*] <*.na/m*o{ri{ d;^w^;} }^_^}} " */ return k- -1+ /*\' '-`*/ ( -/*}/ */0x01 ); {;{ }} ; /*^w^*/ ;}


Funktionale Programmierung

Quelle: http://www.ioccc.org

Wichtig


Funktionale Programmierung

- Anmeldung ins KVV ⇒ Anmeldung zu den Übungsterminen

- Anmeldung im Campus Management ⇒ Anmeldung zur Klausur

- Anmeldung in das Betriebspraktikum-Modul

- Das 0. Übungsblatt muss nicht abgegeben werden

Haskell-Plattform

"Welcome to FU!"

main = putStrLn "Welcome to FU!"

Haskell-Interpreter

GHCI

Haskell-Compiler

GHC


Ich freue mich auf eine gute Zusammenarbeit und auf ein erfolgreiches Lernen!

Documents

Algorithmen und Programmierung I Funktionale ... - Informatik · Einführung ALP I: M. Esponda, 1. Vorlesung 1958 schrieb McCarthy ein Paper mit einem einfachen Lisp- Interpreter,