Tarek Chaaban

Tarek Chaaban, M.Sc's official blog. It contains current web project portfolio, posts regarding his Canadian army experience, news, sports articles, and web tutorials on programming and using social networking technologies.

Programmation fonctionnelle : Rapport sur Scheme

Programmation fonctionnelle : Rapport sur Scheme

CONSTRUCTION DE DESSINS AVEC SCHEME

The code source of (Making drawings with Scheme) can be found here : Scheme Programming Home Work

SCHEME

Programmeur : Tarek Ali Chaaban

Introduction

Ce TP consiste à écrire des fonctions… ce qui étais un peu différents des tps qu’on a fait.

On n’a pas eu de problème avec le langage schème, c’est un langage assez facile à utiliser.

Plus d’information sur schème … plus tard dans ce document :)

Les Fonctions :

== (ligne départ arrivée) ==

segm, segm -> segment list

Pour cette première fonction, le Prof nous a donner l’algorithme à faire, il fallait prendre deux vecteurs dans l’espace et faire en sorte de retourner un segment qui contient tous les points de longueur plus petite que 1/10.

L’algorithme :

Soit T la fonction de transformation, D et A les points de départ et d’arrivée, et M le point sur la ligne D-A qui est équidistant de D et A. Si la distance entre T(D) et T(A) est plus petite que 1/10 alors on a un seul segment de T(D) à T(A), sinon on a l’union des segments de (ligne D M) et (ligne M A).

Donc il ne restait qu’a appliqué l’algorithme en utilisant notre langage préféré: Schème.

Mais … il fallait faire une révision de mathématique du secondaire :)

* Formule pour calculer la distance entre deux points.
* Formule pour trouver le milieu d’un segment (x1, y1) (x2, y2)

J’ai été confus au début de l’utilité de cette fonction puisqu’en utilisant la fonction affichée avec deux vecteurs j’obtenais un dessin sur le modèle mais j’ai compris en utilisant la fonction (parcours->dessinateur parcours).

Et avec quelque bug je suis arrivé à faire des animations (o’.'o) …

Aucun autre problème avec cette fonction.

== (parcours->dessinateur parcours) ==

Cette fonction prenais en argument plusieurs vecteurs et retourner un dessinateur des segments résultants.

J’ai fais une erreur sans m’apercevoir … qui n’est apparue que dans la partie ‘loupe’

J’ai oublié d’appliquer la fonction qui découpe un segment en segment plus petit …

Dans cette partie j’ai écris une fonction “appliquer-transf” je pense que c’est la meilleur fonction de tous le TP et la plus importante :) … je l’ai tellement utilise !!

C’était la clé de presque toutes les autres fonctions.

Elle prend une liste en argument et une fonction de transformation et elle au but d’appliquer cette fonction aux éléments de la liste.

C’est cette fonction qui nous permet d’avoir quelque chose qui ressemble a :

(define ell
(lambda (transf)
(list (segm (transf (vect -1/2 -1)) (transf (vect -1/2 1)))
(segm (transf (vect -1/2 -1)) (transf (vect 1/2 -1))))))

de retour a la fonction parcours->dessinateur … c’étais une fonction facile, il fallait simplement faire un append et utiliser la récursivité.

Problème :

J’ai passe de très longues heurs en pensant par exemple qu’il fallait fermer le dessin par exemple dans le cas du carre 5 points au lieu de 4 points … mais en utilisant le modèle je me suis aperçu qu’il n’y a pas de fermeture !! Ça arrive …

== (translation déplacement-x déplacement-y dessinateur) ==
== (réduction facteur-x facteur-y dessinateur) ==
== (rotation thêta dessinateur) ==
== (loupe facteur dessinateur) ==

Ces fonctions sont presque tous pareils, la seule différence c’est la fonction de calculs.

Donc c’est une très bonne façon de faire une même fonction qui va prendre en argument la fonction de calcul … en utilisant les fonctions à ordre supérieur.

Mais ce n’est pas ce qu’on a fait … on a commence le TP avant que le professeur explique les fonctions d’ordre supérieur, et puisque ça marche on ne voulait pas ce casse la tête :

On s’est contenté de quelque chose qui marche  .

Dans les 4 cas les formules ont soit été données dans l’énonce soit qu’elles étaient facile a deviner (translation, réduction …)

Le problème que j’ai eu dans cette partie c’est la loupe, même après avoir testé la formule de la loupe je n’obtenais pas le même résultat que celui du modèle.

Même après avoir teste et découper la formule pour être sure qu’on n’a pas fais d’erreur de calcul … mais je n’arrivais pas à voir l’erreur.

Après avoir consulté M. Feeley il m’a dit qu’il se peut que j’ai fais une erreur dans la partie (parcours->dessinateur) ce que je n’aurai jamais deviné…

Puisque les autres formules fonctionnaient pour la loupe ne fonctionnerait pas ! … mais il avait raison (comme d’habitude) j’ai oublie d’appliquer la fonction de transformation sur la liste de segments générées par ma fonction (parcours->dessinateur).

== (superposition dessinateur1 dessinateur2) ==
== (pile prop dessinateur1 dessinateur2) ==
== (cote-a-cote prop dessinateur1 dessinateur2) ==

Ces trois fonctions peuvent être découpe en deux parties, la superposition et (pile, cote-a-cote)

La fonction superposition est une fonction facile a réaliser, il suffit de faire un append des deux dessins et les mettre dans un seul, aucun problème dans cette partie.

Les deux autres fonctions, il fallait un peu de mathématique et jouer avec les proportions la première avec les x la deuxième avec les y (5 lignes de code simple font l’affaire)

Il fallait bien sure utiliser les fonctions que j’ai déjà fait (superposition, réduction, translation) .

== entier -> dessinateur ==

Partie importante qui n’est pas très difficile a faire , J’ai fais une lecture du fichier tp1-def et j’ai constater qu’il y a une utilisation des vecteurs pour faire les dessiner des entier de 0 a 9 , après quelque recherche sur google j’ai trouve une fonction prédéfinie (vecteur-ref n) ou n est un entier , ça renvoie les valeurs du vecteur a la position n , ce qui est dans notre cas la liste des segments de 0 a 9 .

Après avoir trouvé comment faire l’extraction des listes de segments, la première étape étais de faire l’affichage d’un nombre simple entre 0 et 9, étape réussi.

Maintenant il fallait pouvoir afficher un nombre > 10, donc il fallait transformer l’entier reçu en une liste.

J’ai écrit une fonction number->list, qui prend un entier en paramètre et qui renvoie une liste (ex : 123 -> ‘(1 2 3))

En utilisant le modulo, le quotient et la récursivité, j’obtiens une liste à l’ envers … donc avec un reverse sur cette liste j’obtiens la bonne réponse.

J’ai écrit une autre fonction list->number, qui elle prend une liste en argument et renvoie un nombre, cette fonction sera utile dans la fonction principale … même si elle m’a causé beaucoup de trouble.

Et a la fin, l’utilisation bien sur les fonctions précédente, (cote-a-cote ) qui clairement prennent leur place dans cette partie et pour la proportion ça sera la taille de la liste.

- Problème –

Un problème majeur a eu lieu dans cette partie, ce sont les zéros :) … au début je ne me suis pas aperçu de l’erreur car je faisais des tests sur des nombres au hasard, mais le problème se trouvait dans l’appelle de ma fonction list->number, lorsque cette fonction reçoit des 0, elle retourne un zéro

Ex: 009 -> 9,

Le problème dans ce cas c’est que si j’envoie (1009), le 1 va s’afficher correctement mais l’appelle récursif sur 009 renvoie 9 donc l’affichage va être 19.

Ce problème a été Contourne grâce a notre démonstrateurs  qui m’a suggérer d’envoyer la liste au lieu d’envoyer l’entier, donc j’ai fais quelque modifications sur ma fonction pour qu’elle accepte une liste au lieu d’un nombre et ca marche ! Merci a Notre Démonstrateur encore une fois  .

== ARBRE -> Dessinateur ==

C’est la fonction qui a pris le plus de temps non pas parce qu’elle est difficile a faire mais c’est que je n’avais aucune idée comment la faire.

Je ne savais pas comment étais fais le structure de l’arbre et le rapport avec la liste.

Mais après à peu près une centaine de test … oui … et plus d’explication de M. Feeley j’ai compris le principe !

J’ai commencé à faire une fonction qui calcule la longueur de l’arbre en profondeur length-arbre, c’est une fonction récursive assez simple.

(define length-arbre (lambda (arbre)
(if (pair? arbre)
(+ 1 (max (length-arbre (car arbre)) (length-arbre (cdr arbre))))
0)))

Puis c’étais claire du dessin que je devais utiliser plusieurs fonctions que j’ai déjà fait :

• cote-a-cote pour les feuilles
• pile pour la longueur en profondeur
• un arbre simple avec 2 branches (droite & gauche)
• récursivité

Je pensais que c’était la fonction qui sera la plus longue … mais en réalité après avoir fais quelque test, ça ma prit 10 min pour écrire la fonction arbre->dessinateur.

J’ai été surpris que ça marche ! Une fonction qui a l’aire très difficile et qui fait beaucoup de chose soit faite en quelque ligne de code.

On peut voir très clairement la force de schème dans ce TP, qui permet de faire plusieurs choses en quelque ligne de code.

Java vs Schème

== Forces et faiblesses du langage Schème ==

Dans ce TP je n`ai vue que des forces du langage schème, c`est un langage dote d`une très grande puissance.

Ces forces sont dans la rapidité d`exécution, dans notre TP, un segment pouvait être découpés en plusieurs centaines de segment de longueur plus petite que 1/10 et schème n`a jamais planter ou lance une erreur de mémoire, dans java même si ca fait 2 ans que je n`ai touche a ce langage  je sais qu`il y a la gestion de mémoire automatique c`est le cas aussi dans schème. Mais je pense que l`implémentation est un peu différente.

Une force qui nous a été plus qu`utile dans ce TP c`est de pouvoir envoyer une fonction en résultat, ca n`existe pas en java (d`après mon expérience …)

Cette force nous a permis de faire plus de 80 % du TP ou même plus !!

La plus part des fonctions devaient retourner une fonction qu`on devait utiliser dans d`autre fonctions.

Une faiblesse (peut être) c`est le fait que tous les fonctions soient relier ensemble (la façon que je l`ai fait) donc si il y avait une erreur dans la fonction numéro 1 et que j`utilise cette fonction dans la fonction 10, il est très difficile de trouver l`erreur parce que pour le programmeur le fonction numéro 1 est correcte … ca ressemble un peu au principe des compilateurs qui donnent de compilateur … après quelque version si on s`aperçoit d`une erreur … soit il faut retourner a la version qui marche soit avoir des 100 , 000 de lignes de code a déboguer

Une autre petite faiblesse c`est le type des variables, même si schème n`est pas stricte comme HASKELL, on a eu quelque problèmes avec les types, des fois on avait une fonction qui attend une liste en paramètre mais le fais de faire un car retourner un entier au lieu d`une liste nous a causer quelque problème mais on a réussi à contourner ce genre de problème.

Mais je crois que ce genre de problème est arrivé à cause de la manière de notre programmation

Notre seul but étais de faire quelque chose qui marche sans faire d`optimisation sur notre programme … ce n`étais pas le but.

Une autre force, même si on ne sait pas comment elle est faite … c`est l`interaction avec d`autre programme d`une façon très dynamique par exemple dans notre TP il y avait une interaction avec le TCL/TK, dans java l`applet est déjà intégré ce qui rend le programme un peu plus lourds, dans notre cas schème s`occupe seulement des résultats et c`est a TCL/TK de gérer les dessins.

== Quelles difficultés avez-vous rencontrées avec l’utilisation du langage Schème? ==

Son API est compose de 50 pages je pense, donc il est très facile a apprendre.

La Seule difficulté qu`un programmeur peut avoir en utilisant schème c`est de penser en terme de « programmation fonctionnel »

Des qu`on commence à penser en terme de programmation fonctionnel la programmation devient plus facile, mais un programmeur normalement est habituer à faire de la programmation impérative ce qui lui causera un problème au début mais avec l`expérience ce problème sera fixe.

Dans mon cas Schème n`est pas nouveau, je connais déjà la syntaxe et j`ai déjà fait un projet (serveur web) en utilisant schème comme langage.

Un autre point important c`est la compréhension du code, en schème c`est beaucoup plus difficile de comprendre un code qu`en java, même si on revient a notre propre code après certains temps … ca sera difficile de le comprendre.

== Qu’est-ce qui a été facilite par l’utilisation de Schème? ==

Ce qui a rendu ce TP facile c`est bien sur l`utilisation de schème comme langage de programmation, je ne sais même pas comment faire ce TP en utilisant java comme langage, j`ai déjà essayé de faire un programme (PAINT) et j`ai vu la lenteur de l`exécution d`un applet java.

Comme je l`ai mentionné un peu plus haut, le fait que dans schème il y a une possibilité d`envoyer une fonction en résultat qui elle va attendre un argument a été notre sauveur dans ce TP, de cette manière on pouvait découper notre programme en plus petite morceau (diviser pour régner)

== Recherche Java vs Schème ==

Reference: http://w3.umh.ac.be/genlog/cours/principesLangages-cours.html

Voici une petite recherche qu`on a fait pour trouver l`expérience d`autre personnes plus expérimentés dans schème.

• Les variables locales :

En Schème : les variables définies dans une expression sont locales a cette expression.

En java : les variables définies dans une méthode sont locale à cette méthode.

• La portée statique :

La portée d’une variable est déterminée statiquement, c.-à-d., avant que le programme est exécuté, Si des sous programmes peuvent être emboîtes, nous pouvons avoir une portée statique emboîtée.

Exemples :
1. define emboîte en Schème
2. Instructions composées (et Inner class) en Java

• La portée dynamique :

La portée d’une variable est déterminée pendant l’exécution du programme

Exemples :

(define f
(lambda (a b) (+ a b c)) )
(define g
(lambda (c) (f 1 2)) )

L’évaluation (g 3) renvoi 6 en LISP
- Dans l’environnement ou f est évaluée, la valeur de c est 3
Error en Schème

- Au point ou f est définie, l’environnement ne contient pas la valeur de c.

La portée Dynamique interagit avec d’autres mécanismes dans un langage O .O

- Les appels super ont une portée statique
- Les appels this (Java) ont une portée dynamique
- Les variables qui ne sont pas trouvées dans la classe sont statiquement recherchées dans la chaîne de superclasses.
- Les restrictions de visibilité (en Java) affectent les règles de portée
Public, private, protected

• Les concepts « first class »

Les fonctions en Schème Vs les objets en Java
Des fonctions peuvent être assignées aux variables
(define f (lambda (x) (+ x x)))
# Des fonctions peuvent être passées comme arguments
(define (apply x y)(x y))
(apply f 5) => 25
Des fonctions peuvent être retournées comme résultat

(define (composition f g)(lambda (x) (f (g x))))
(composition (lambda (x) (* x x)) (lambda (x) (+ 5 x)))
#

• Les objets en Java sont « first class »

- Ils peuvent être assignées aux variables
- Ils peuvent être passées comme arguments d’une méthode
- Ils peuvent être retournées comme résultats d’une méthode.

Les méthodes en Java ne sont pas « first class »
Les classes en Java ne sont pas « first class »
On peu passer un objet comme argument, mais pas une classe.

• Le passage des paramètres (Par Valeur, Par Référence et Par Nom)

Passage par valeur : même chose entre Java et Schème pour toutes les valeurs primitives.

Passage par référence :
- en Java les objets sont passes par référence
- en Schème, les paires sont passées par référence

• Les structures de données primitives :

Les Listes Les Tableaux Les Classes Autres
Schème Oui Oui, les vecteurs Oui Les paires
Java Oui java.util Oui, les arrays Oui

Reference: http://w3.umh.ac.be/genlog/cours/principesLangages-cours.html

== Avantages et inconvénients de la représentation fonctionnelle pour dessins normalises ==

Ce que je comprends de cette question est : Montrer la différence entre la programmation fonctionnelle et la programmation impérative (par exemple)

Bien sure si ces fonction qu`on avait à faire étais à faire en utilisant le type de programmation impérative (java ou c) ou même la programmation logique (prolog) … ca sera faisable.

Mais chaque langage a ces forces et faiblesse, dans notre cas je pense que la meilleur façon étais d`utiliser le type fonctionnelle car presque toutes les fonctions sont baser sur les autres on a vu comment dessiner un arbre binaire en moins de 10 lignes de code … ce qui peut être dans java ou c peu prendre des centaines de lignes.

L`avantage principale c’est l`extension des fonctions et la réutilisation.

Tandis que dans une programmation impérative ou même dans schème en utilisant les Set! Peu être il y avait d`autre moyens de garder les listes dans un tableau et de les passer sans avoir des problèmes de types.

Un autre petit inconvénient c’est que toutes les fonctions sont lies

Ligne -> parcours-dessinateur -> rotation – translation … ->superposition -> arbre.

C`est très difficile de savoir d’ou vient l’erreur exactement.

Leave a Response

Please note: comment moderation is enabled and may delay your comment. There is no need to resubmit your comment.