Upload
abelard-poulet
View
108
Download
0
Embed Size (px)
Citation preview
CSI3525:Concepts des Langages de
ProgrammationNotes # 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.
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.
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.
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.
Quelques examples en 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.
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!!
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].
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.
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.
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)
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
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.)
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)
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)
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