Scheme

Je voulais savoir si il y avait des gens aussi qui bossaient dessus. ça va faire la deuxième année à la fac qu’on apprend ce langage.
En gros a la base il y avait Fortran, ensuite LISP pour faire de l’IA et du lambda calcul. Scheme découle de LISP , en prenant un peu d’objet et d’impératif ! On peut faire des appels systèmes, de la 3D, du web.
Donc on peux faire n’importe quoi avec.
C’est dynamiquement typé et interpreté.

Pour ceux qui voit pas du tout ce que c’est et qui veulent en savoir plus.
Un programme est une liste, donc plein de parenthèse dans tout les sens.
les ; c’est les commentaires.

Par exemple a + b + c va s’écrire (+ a b c) on appelle la fonction + avec les paramètres a, b et c.
Un exemple de fonction

(define (op f a b) (f a b))
la fonction op prend une fonction f et 2 nombres.
Utilisation :

[code](op + 1 4)

5[/code]

le if prend 3 arguments :

  • La condition
  • Ce qui se passe si la condition est vraie.
  • Ce qu’il se passe si elle est fausse.
    C’est pas limpide ??

Et tout est vrai sauf #f (false) (à savoir quand meme)

Introduction au lambda calcul

(op (lambda (a b) (if (< a b) a b)) 1 5) 1
on appelle la fonction op avec 1 et 5 et la fonction f sera la fonction qui renvoi a si a < b et b sinon.
En gros on vient de créer un fonction à la volé sans trop de problème.
Vous me faites ça en C ?? en une ligne ??

Un exemple de CPS (Continuation Passing Style)

[code]Factorielle normale :
(define (fac n) ; calcule f(n!)
(if (= n 0)
1
(* n (fac (- n 1)))))
Gros problème de pile vu que la fonction récursive est enveloppée (* n a chaque fois) c’est super pas bien.

(define (k-fac n f); calcule f(n!)
(if (= n 0)
(f 1)
(k-fac (- n 1) (lambda ® (f (* n r))))))
Plus de problème au fur et a mesure on construit une fonction qui donnera n! quand on l’appellera avec 1

On peut se la faire un iterative aussi la meilleur methode. en definissant une fonction (iter n res) a l’interieur de (fac n)[/code]

On nous a fait faire plein d’algo sur les listes et les arbres. les fonctions font quelques lignes.
On a fait du filtrage sur les strings.
De l’imperatif, en gros on prend un prog C et on le recompie
on utlise alors des set! pour ecraser des variables. Ce qui parait normal dans un language imperatif.
Mais pas en scheme. Mais pour certaine chose on est obligé de passer par là.

Scheme dispose aussi d’un langage de macro assez puissant vu qu’on code en scheme dedans. On peut coder while (qui n’est pas de base) en quelques lignes.
Les fonctions qui font ca permette de dire ce qu’on va faire pour le premier element.
Et on met … et tout est fait.

[code](define-syntax while
(syntax-rules ()
((while t expr …) (letrec ((iter (lambda ()
(if t
(begin expr …
(iter))))))
(iter)))))

let permet de définir des variables par exemple
(let ((a 1)(b 2))
(+ a b))

3
le letrec fait pareil mais on peut lui donner des fonctions récursives.[/code]
Pour ceux qui savent pas les macros vont prendre le code est le modifier selon les regles enoncées.

Ce qui est marrant c’est qu’on fois executé le programme peut se modifier egalement.
(Les premiers virus ont ete fait en LISP…)

J’ai zappé plein de truc, mais c’est juste pour vous faire decouvir une autre facette de la programmation.

Si vous voulez tester, c’est gratuit. Je code sur DrScheme v209 ça tourne sur tout les OS \o/
DrScheme

Pour l’utiliser il y a 2 parties.
Celle d’en haut vous taper le code. Quand on l’execute les resultats s’affiche en bas dans le top-level.
Vous pouvez aussi taper aussi ce que vous voulez dans le top level.

hf…

Ahhh Scheme, que de souvenirs, le bon temps des études où on étudiait plein de langages bizarres et variés.

Mais pour ce que j’en ai retenu… DIE SCHEME, DIE !!
(ben oui, Scheme j’ai pas aimé)

[quote=“Twin, post:2, topic: 25673”]Ahhh Scheme, que de souvenirs, le bon temps des études où on étudiait plein de langages bizarres et variés.

Mais pour ce que j’en ai retenu… DIE SCHEME, DIE !!
(ben oui, Scheme j’ai pas aimé)[/quote]
Mais j’aime bien ce genre de languages… les arbres d’expressions Lambda, ca déchire carrément. Beaucoup de languages modernes devraient s’inspirer un peu plus de ce type d’approches… D’ailleurs C# 3 introduira les lambda expressions, et c’est completement inspiré du Lisp Scheme et autres languages avec pleins de parenthèses (LISP = “Lazy, insipid and stupid parenthesis” chez pas mal d’étudiants :P)

argh, parler d’un truc comme ça alors que j’ai partiel de CAML à la rentrée… Bande de salauds :stuck_out_tongue:

Plus sérieusement y’a des trucs pas mal en fonctionnel, c’est clairement surpuissant pour tout ce qui est analyse syntaxique d’expressions et récursivité.
Après j’avoue que je suis assez dubitatif sur le fait que ca va écraser le C++ et que si les SSII n’utilisent pas ça, c’est pour le plaisir de passer plus de temps à coder et à maintenir (véridique de la bouche de mon prof… Oui c’est un universitaire qui n’aime pas l’industrie, ca se voit tant que ça ?).

Oui c’est vrai qu’en une ligne on peut faire énormément de choses. Dans d’autres langages aussi, et c’est ici aussi clairement à l’encontre de la lisibilité du code.

(merci pour relire ce genre de trucs, rares mais ca arrive quand même : (ok y’a un peu de mauvaise foi, c’est la déclaration d’une lambda expression)
let fib = Appl(z, Abs(« f », Abs(« n », Cond(Appl(Appl(Var « egal », Var « n »), Const 0), Const 0, Cond(Appl(Appl(Var « egal », Var « n »), Const 1) ,Const 1, Appl(Appl(Var « plus », Appl(Var « f », Appl(Appl(Var « moins », Var"n"),Const 1))), Appl(Var « f », Appl(Appl(Var « moins », Var"n"),Const 2))))))));; :stuck_out_tongue:

Hahaha :stuck_out_tongue: Ils sont marrants certains dans les FACs… serieux quoi…

oué, c’est un cas ce prof

le problème c’est qu’on est pas en fac nous, on va avoir l’air malin avec une mention caml sur nos CV :stuck_out_tongue:

Ce mode de programmation a l’air, ma foi, marrant comme tout.

J’ai fait quelques recherches sur l’ami « gOOgle » et j’ai comme d’habitude trouve de tout et de rien sur le sujet.

Est ce que vous connaissez des bons sites (ou cours) en disant un peu plus sur le sujet, prennant un peu le novice par la main pour lui glisser delicatement le doigt dans l’engrenage, tout en expliquant a quoi ca peut servir, comment en tirer partie dans la vie de tous les jours (si tant est que programmer serve dans la vie de tous les jours …) ?

Rien de plus terrible quand meme que de tomber sur des sites mal faits qui te degoutent un peu du sujet … :stuck_out_tongue:

Je peux te conseiller le site de ma 2eme année de licence (truc pas officiel avec les corrections et tout)

http://lmi2.free.fr / Scheme.

Sinon dans l’aide de PLT DrScheme il y a un gros tutorial.

[quote=“lucasbfr, post:6, topic: 25673”]oué, c’est un cas ce prof

le problème c’est qu’on est pas en fac nous, on va avoir l’air malin avec une mention caml sur nos CV :P[/quote]
Sur les CVs c’est tres bien. J’ai fait du Caml aussi et tu apprends plein de choses en faisant de la programmation fonctionelle qui auraient plus de mal a rentrer autrement. Mais bon, ca a un but pedagogique quoi, y a une bonne raison pour laquelle c’est pas utilise dans l’industrie…

Coucou,

Si je m’en souviens bien, on utilise la récurrence à fond avec ce language …
Hors, j’ai appris depuis , que la récurrence était à éviter , paradoxe ?
Autre point que j’aimerais éclaircir, j’ai aussi entendu dire , que les appels de fonctions étaient à limiter surtout quand celles-ci ont beaucoup de paramètres , est-ce le cas avec scheme ?

Arg comme j’en ai un mauvais souvenir moi de ces trucs.

Franchement, ok il y a des trucs sympas dedans, mais bonjour la lisibilité du truc et la gymnastique d’esprit à choper pour coder cet engin. Ceci dit, il ne faut pas tout critiquer, Emacs est codé en Lisp et il est quand même pas mal puissant et ses macros du coup, sont assez fortes. D’ailleurs j’étais assez étonné de voir que C# 3 implémentait les lambda, même si c’est justifié par Linq.

Enfin c’est clair que j’ai passé mon temps à la fac a essayé d’expliquer à mon prof les principes de coûts et de temps de développement :stuck_out_tongue: (bah oui j’avais repris la fac après 2ans de « vrai » taf, donc ça m’a fait tout chose).

EDIT: le nombre de fois que je dis truc dans mon message :stuck_out_tongue: C’est mon ancien prof de français qui serait content.

Tiens ca m’intéresse, pour quelle raison ? Parce que la récurrence risque de bouffer plus de mémoire (fatalement) que la forme “normale” ?

(PS ; de toutes facon je hais caml, c’est tout : je viens de chier l’exam (comme une buse) donc prout le chameau)

Moi on m’a au contraire dit qu’une baisse éventuelle de performances en programmant récursivement avec un langage non fonctionnel n’était qu’une légende. Par conséquent, on pouvait bien faire comme ça nous arrangeait le plus, tant qu’on ne s’amusait pas à ajouter de la complexité en implémantant comme des porcs les algorithmes.

La récurrence bouffe de la mémoire car elle fait beaucoup d’appel de fonctions (elle même), ce qui nécessite pas mal d’allocations sur la pile d’éxecution.
Il faut dire que j’ai bossé avec des accros du temps réel , donc c’est surtout dans ce cadre que j’ai eu ces recommandations. J’étais un peu décu , car je trouve la programmation récursive très élégante :stuck_out_tongue:

Ouai enfin faut pas s’emballer, faut pas eviter la recursivite quand on programme avec des contraintes « normales ». Si tu vas vraiment trop en profondeur, tu peux exploser la stack, mais c’est en general un signe que ta structure de donnees est mal organisee plus qu’un probleme avec la recursivite (genre il faut balancer ton arbre mieux…). Dans certains cas extreme avec enormement de donnees on peut avoir des soucis et devoir reprogrammer en iteratif, mais pour faire des trucs aussi debile que « afficher le contenu d’un arbre binaire balancé dans l’ordre », c’est a s’arracher les cheveux. Enfin encore une fois comme toujours ca depend de ton scenatio, c’est juste un outil: oui il y a des cas ou c’est pas adapte et il vaut mieux un meilleurs outil, mais dans la plein de cas c’est tres bien la recursivite. On peut certainement pas faire de regle du genre « c’est mal » en tout cas :stuck_out_tongue:

Je me rappelle d’un cours dont hélas je n’ai plus les notes, ou le prof, en prenant un algo de parcour de graph récursif, et en le recodant en itératif, nous avait montré en calculant la complexité qu’en fait, la version itérative était bien plus puissante (genre passer du quadratique au linéaire).

Bien sûr, un exemple ne fait pas une règle général, mais il me semble que justement lui disait que c’était applicable dans la plupart des cas.

[quote=“BodySplash, post:16, topic: 25673”]Je me rappelle d’un cours dont hélas je n’ai plus les notes, ou le prof, en prenant un algo de parcour de graph récursif, et en le recodant en itératif, nous avait montré en calculant la complexité qu’en fait, la version itérative était bien plus puissante (genre passer du quadratique au linéaire).

Bien sûr, un exemple ne fait pas une règle général, mais il me semble que justement lui disait que c’était applicable dans la plupart des cas.[/quote]

La programmation récurssive est pour moi bien plus intuitive que la programmation iterative, de plus , le code est souvent bien plus concis. Si je ne me trompe pas tout algo récurssif à une version itérative , mais je souhaite bien du plaisir à certain de trouver la version itérative de certains algo récurssifs.
d’ailleur, je sais pas si ca existe des systèmes experts permettant de trouver automatiquement la version itérative d’un algo récurssif ? Scheme ne serait-il pas basé sur ce principe ?

Dans les algo a base de backtracking il va falloir maintenir sa stack a la main en iteratif et ouai… bonne chance quoi. C’est d’ailleurs une question d’entretien pour un collegue, de recoder un truc evident en recursif en iteratif. Faut voir les mecs se vautrer… Je suis pas trop l’argument de complexite sinon. Je vois pas trop en quoi on peut generaliser qu’un algo O(n^2) pourrait passer en O(n) juste en changeant/adaptant le meme algo en iteratif ou recursif. Y a des scenarios plus ou moins adaptes et tu peux faire du code en bois ou tres mlain dans un cas qui sera pas forcement applicable dans l’autre mais je vois pas le rapport avec la technique elle meme.

Ouaip désolé Glop, comme ça ça parait pas évident, même pour moi ^^ Et je peux me planter complètement, mais il me semble bien me rappeler que la complexité était moindre. Alors peut-être qu’il a triché sur les bords, et que l’adaptation en itératif était pas vraiment le même algo, et c’était surement pas passé du quadratic au linéaire :stuck_out_tongue:

C’est vrai aussi que la version itérative avait une sale gueule par rapport à l’itérative :stuck_out_tongue:

Pour la technique, comme je l’ai dit je ne pense pas que c’en était vraiment une, mais plus un exemple pour nous montrer que le récursif, il fallait savoir s’en passer suivant les cas, et ne pas se jeter dessus les yeux fermés juste parce que c’est « elégant ».

P.S: vache en fait on oublie vite ce qu’on apprend pendant les études. Je serais bien incapable de calculer une complexité maintenant :stuck_out_tongue:

erm… c’est quoi une expression lambda? :stuck_out_tongue: