17
CSI3525: Concepts des Langages de Programmation Notes # 5: Langages de Programmation Fonctionelle I: Introduction au Scheme

CSI3525: Concepts des Langages de Programmation Notes # 5: Langages de Programmation Fonctionelle I: Introduction au Scheme

Embed Size (px)

Citation preview

Page 1: CSI3525: Concepts des Langages de Programmation Notes # 5: Langages de Programmation Fonctionelle I: Introduction au Scheme

CSI3525:Concepts des Langages de

ProgrammationNotes # 5:

Langages de Programmation Fonctionelle I:

Introduction au Scheme

Page 2: CSI3525: Concepts des Langages de Programmation Notes # 5: Langages de Programmation Fonctionelle I: Introduction au Scheme

Introduction I

Le paradigme de programmation fonctionelle est base sur les fonctions mathematiques.

Une fonction mathematique est une application qui va de l’ensemble de depart a l’ensemble d’arrivee. Elle prend un element de l’ensemble de depart et le transforme en un element de l’ensemble d’arrivee.

Les fonctions sont controllees par des appels recursifs et des instructions conditionnelles plutot que par des sequences d’instructions et des repetitions iteratives.

De meme, une fonction calcule toujours le meme resultat etant donne les memes arguments d’entrée.

Page 3: CSI3525: Concepts des Langages de Programmation Notes # 5: Langages de Programmation Fonctionelle I: Introduction au Scheme

Introduction II

Les fonctions peuvent etre combinees de maniere elegante et pratique.

En particulier, on peut creer des fonctions d’ordre plus eleve--aussi appellees formes fonctionelles--qui, ou bien prennent comme argument une autre fonction, ou bien retournent comme resultat une fonction.

Examples de formes fonctionelles: les compositions, les constructions et les applications generalisees.

Page 4: CSI3525: Concepts des Langages de Programmation Notes # 5: Langages de Programmation Fonctionelle I: Introduction au Scheme

Fondation des Langages de Programmation I L’objectif de la programmation fonctionnelle est d’imiter

le plus possible les fonctions mathematiques. Ces langages sont donc tres differents des langages imperatifs.

En particulier, un langage fonctionel pur n’utilise ni variables ni instruction d’affectement. Il utilise la recursion pour obtenir de la repetition.

Les programmes sont des definitions de fonctions et des specifications d’applications de fonctions.

Les executions sont des evaluations d’applications de fonctions.

Page 5: CSI3525: Concepts des Langages de Programmation Notes # 5: Langages de Programmation Fonctionelle I: Introduction au Scheme

Fondation des Langages de Programmation II Un langage fonctionel doit avoir:

– Un ensemble de fonctions primitives,– Un ensemble de formes fonctionnelles qui permettent de

construire des fonctions complexes a partir de ces fonctions primitives,

– Une operation d’application de fonction,– Et, finallement, une ou plusieures structures de donnees

Bien que les langages fonctionnels soient souvent implementes avec des interpreteurs, ils peuvent aussi etre compiles.

Page 6: CSI3525: Concepts des Langages de Programmation Notes # 5: Langages de Programmation Fonctionelle I: Introduction au Scheme

Quelques examples en Scheme….

Page 7: CSI3525: Concepts des Langages de Programmation Notes # 5: Langages de Programmation Fonctionelle I: Introduction au Scheme

Lisp en General

Scheme (1975) represente l’un des nombreux dialectes du Lisp (originellement: Lisp 1.5 (1975); plus recemment: Common Lisp (1985)).

Le Lisp 1.5 n’avait que deux types* de donnees: des atomes et des listes. Les atomes sont les symboles du Lisp. On peut avoir des listes de listes et une liste peut melanger les atomes et sous-listes de different degree sans probleme.

Example: (A (B C) D (E (F G))) est parfaitement valide. * On parle d’un type different des types en langages imperatifs.

Page 8: CSI3525: Concepts des Langages de Programmation Notes # 5: Langages de Programmation Fonctionelle I: Introduction au Scheme

Syntaxe du Lisp et de ses descendants Les programmes et les donnees sont exprimes dans la

meme syntaxe:– Applications de fonctions et structures conditionnelles

sont ecrites sous la forme de listes, en parentheses en utilisant la forme prefix.

– Programmes et donnees peuvent etre distingues par leurs contexte.

Cette uniformite d’expression donne aux langages fonctionnels leur flexibilite et leur puissance d’expression: les programmes peuvent etre manipules comme s’ils etaient des donnees!!

Page 9: CSI3525: Concepts des Langages de Programmation Notes # 5: Langages de Programmation Fonctionelle I: Introduction au Scheme

Les 5 fonctions primitives du Lisp Pur + 2 autres operations essentielles

Primitives: cons --- pour construire une liste car --- pour trouver le premier element d’une liste. cdr --- pour trouver la queue d’une liste. eq -- pour verifier si deux atomes sont egaux. atom -- pour verifier si une entite est un atome.Operations Supplementaires Essentielles: Evaluation d’une expression Application d’une fonction a des arguments (deja

evalues)[Le Lisp 1.5 a aussi un certains nombre d’operations

auxilliaires pour gerer les listes d’arguments et les evaluations conditionnelles].

Page 10: CSI3525: Concepts des Langages de Programmation Notes # 5: Langages de Programmation Fonctionelle I: Introduction au Scheme

L’Usage du Lisp et de ses Descendants IComme Prolog et SmallTalk, Lisp est utilise

interactivement: Il n’y a pas de programme principal La boucle du niveau superieur evalue une expression

(elle peut aussi faire du I/O). Cette expression, en revanche, peut invoqier une fonction qui implemente un algorithme long et complique

Un programme de Lisp consiste en une collection de fonctions qui peuvent etre appelees (directement ou indirectement) a partir de la boucle du niveau superieur.

Page 11: CSI3525: Concepts des Langages de Programmation Notes # 5: Langages de Programmation Fonctionelle I: Introduction au Scheme

L’Usage du Lisp et de ses Descendants II Les expressions sont, normallement,

evaluees. Afin d’eviter l’evaluation, il faut le demander specifiquemen au Lisp en utilisant l’expression “quote” ou “ ‘ ”.

Les atomes sont traites literallement: ils sont ce qu’ils sont et rien de plus: il se peut que l’atome ait une signification dans le domaine d’application, mais le Lisp ne le sait pas.

Page 12: CSI3525: Concepts des Langages de Programmation Notes # 5: Langages de Programmation Fonctionelle I: Introduction au Scheme

Revenons au Scheme… Voici ses caracteristiques Le Scheme est un langage de tres petite taille avec une

syntaxe et semantique simple. Il utilise l’evaluation a portee locale (ou statique). Cela

signifie que la portee (ou visibilite) d’une variable peut-etre determinee avant l’execution du programme. => La portee d’une variable est plus simple a determiner que si elle doit etre determinee dynamiquement (comme en Lisp 1.5).

Il traite les fonctions comme entites de premiere classe, ce qui veut dire que les fonctions peuvent- etre manipulees comme des donnees.

Les structures de donnees sont simples, uniformes et versatiles et s’appellent S-expressions (comme en Lisp)

Page 13: CSI3525: Concepts des Langages de Programmation Notes # 5: Langages de Programmation Fonctionelle I: Introduction au Scheme

Les Structures de Donnees

Nombres: entiers ou reels Variables:

– un nom attache a un objet (define pi 3.14159) – Le type d’une variable est implicite et depend de sa

valeur.– Une variable peut recevoir une nouvelle valeur: (set! pi

3.141592) (set! pi ‘alpha) Symboles: un nom et rien qu’un nom: pas de valeur! Listes: (E1 E2…En) ou Ei est une S-expression

Page 14: CSI3525: Concepts des Langages de Programmation Notes # 5: Langages de Programmation Fonctionelle I: Introduction au Scheme

Les Fonctions Primitives I

+, -, *, et / => Notation Prefixe -- Ex: (+ 3 7) EVAL est une fonction utilitaire appellee automatiquement

a chaque etape de la boucle lecture-evaluation-ecriture de l’interpreteur. Elle evalue, tout d’abord, les parametres de la fonction, et ensuite, evalue la fonction appliquee a ces parametres.

quote ou ‘ est la fonction qui evite l’evaluation d’expressions.

car, cdr, cons, list (et aussi caaar, cddr, cadaddadr, etc.)

Page 15: CSI3525: Concepts des Langages de Programmation Notes # 5: Langages de Programmation Fonctionelle I: Introduction au Scheme

Les Fonctions Primitives II

eq?, null?, list? =, <>, >, <, >=, <=, even?, odd?, zero?, eqv? display, newline define

– (define (square x) (* x x)) ou– (define squre (lambda (x) (* x x)))

cond, if

(cond ((equal? x 0) #f) (if (equal? x 0) ((> x 5) 5) <> #f (else #t)) #t)

Page 16: CSI3525: Concepts des Langages de Programmation Notes # 5: Langages de Programmation Fonctionelle I: Introduction au Scheme

Fonctions de haut niveau I (fonctions qui peuvent etre des arguments) Example: map map(f (E1 E2…En))=((f E1) (f E2)…(f En))( define ( map f l ) ( if ( null? l ) l ( cons ( f ( car l ) ) ( map f ( cdr l) ) ) ) )E.g.: (map (lambda (x) (+ x 1)) ‘(1 2 3) )

--> (2 3 4)

Page 17: CSI3525: Concepts des Langages de Programmation Notes # 5: Langages de Programmation Fonctionelle I: Introduction au Scheme

Fonctions de haut niveau II (fonctions qui peuvent etre des arguments)

Les reducteurs: Etant donne une fonction binaire f et une constante f0, on

veut definire la fonction de haut niveau telle que: (reduit f (E1 E2 … En)) -->

(f E1 (f E2 (f … (f En f0) …)))Examples: (E1 E2 … En) --> E1 + E2 + … + En +0 (E1 E2 … En) --> E1 * E2 * … * En * 1 ( define (reduce f f0 1) ( if (null? l ) f0 (f (car l) (reduce f f0 (cdr l))) ) ) E.g.: (reduce + 0 ‘( 1 2 3 4) ) --> 10 (reduce * 1 ‘( 1 2 3 4) ) --> 24