Pour comprendre il faut avoir fait du lambda calcul en fait :P. Ca permet d’avoir une notation universelle pour faire des demonstration en theorie des langages et prouver des equivalences de classe et autre joyeusetes de ce genre de « maths » de l’informatique… par exemple quand on parle de compilateurs (qui n’est rien d’autre qu’un traducteur de langage dans un autre qu’on peut prouver fonctionellement equivalent etc). Scheme est le language qui doit s’approcher le plus de la notation utilisee en lambda calcul mais c’est pas du tout obligatoire de faire du scheme pour faire du lambda calcul (par exemple j’ai eu des cours de lambda calcul mais j’ai jamais fait de scheme). Dans cette notation le concept central c’est « l’expression lambda ».
En anglais mais j’ai la flemme de traduire. C’est pas complique non plus…
[quote]The λ calculus can be called the smallest universal programming language of the
world. The λ calculus consists of a single transformation rule (variable substitution)
and a single function definition scheme. It was introduced in the 1930s by Alonzo
Church as a way of formalizing the concept of effective computability. The λ calculus
is universal in the sense that any computable function can be expressed and evaluated
using this formalism. It is thus equivalent to Turing machines. However, the λ calculus
emphasizes the use of transformation rules and does not care about the actual machine
implementing them. It is an approach more related to software than to hardware.
The central concept in λ calculus is the "expression". A "name", also called a
"variable", is an identifier which, for our purposes, can be any of the letters a, b, c, . . .
An expression is defined recursively as follows:
:= | |
:= λ .
:=
An expression can be surrounded with parenthesis for clarity, that is, if E is an
expression, (E) is the same expression. The only keywords used in the language are λ
and the dot.[/quote]
Scheme assure une recursivité terminale pour les fonction recursive non eveloppées.
[code](define (rec-fac n)
(if (= n 0)
1
(* n (rec-fac ( - n 1)))))
(define (iter-fac n)
(define (iter n r)
(if (= n 0)
r
(iter (- n 1) (* r n))))
(iter n 1))[/code]
Ca faite exactement la meme chose la complexité en temps est O(n)
Mais l’espace sera pas le meme.
rec-fac mettre une multiplication dans la pile or que iter-fac n’as pas de pile.
Le probleme c’est que la fonction est envelopée par “* n” si elle ne l’etait pas
Scheme assure que ca fera pareil qu’une fonction iterative.
[quote=“avavrin, post:22, topic: 25673”]Scheme assure une recursivité terminale pour les fonction recursive non eveloppées.
[code](define (rec-fac n)
(if (= n 0)
1
(* n (rec-fac n))))
(define (iter-fac n)
(define (iter n r)
(if (= n 0)
r
(iter (- n 1) (* r n))))
(iter n 1))[/code]
Ca faite exactement la meme chose la complexité en temps est O(n)
Mais l’espace sera pas le meme.
rec-fac mettre une multiplication dans la pile or que iter-fac n’as pas de pile.
Le probleme c’est que la fonction est envelopée par “* n” si elle ne l’etait pas
Scheme assure que ca fera pareil qu’une fonction iterative.[/quote]
Soit je suis une buse, soit ton rec-fac est foireux : à la denière ligne ce sera pas plutot (* n (rec-fac (- n 1))))) ?
Bah la récursivité, “cémal” (notez les guillemets, hein, parce qu’il faut relativiser quand même), parce que
ca complique le débugage (pas celui a base de “printf”, celui avec gdb)
tu perds FORCEMENT en vitesse: tu empile tout un contexte dans ta pile, alors qu’avec la même méthode dérécursifiée, tu peux n’empiler que ce qu’il te faut.
tu reperds en vitesse : un appel de fonction, c’est pas gratuit. Y a le changement de contexte, mais aussi toutes les merdes qui vont avec l’appel de fonction (style t’as des chances de faire sauter tout ce que t’as dans ton pipeline)
Mais c’est vrai que c’est vraiment HYPER pratique… la pile tu la gère pas, tu laisse faire le compilo. Et pui faut bien se servir de la puissance des machines (j’ai horreur de ce langage, mais ca n’engage que moi)
Sinon, tout algorithme récursif peut être dérécursifié, avec une technique a la con, et en général sans gain pour la complexité.
sinon, le scheme, je me demande si il “dérécursifie” pas, c’est a dire si il a pas sa propre pile qu’il gère comme un grand pour éviter de faire des changemens de contexte a la con (pour l’interprété, hein, parce que pour le compilé, je sais pas si on peut dérécursifier automatiquement)
