On Mon, Aug 04, 2003 at 11:47:04AM +0100, Yves Rutschle wrote: > On Mon, Aug 04, 2003 at 11:21:30AM +0200, Sven Luther wrote: > > Les langages fonctionnels (lisp, scheme, sml, caml, ocaml, haskell, > > erlang, clean, ...) sont base sur la theorie du lambda calcul, qui a ete > > develope par Alonzo Church vers la fin des annees 30 afin de modeliser > > les fonctions mathematiques (vous savez, les f : N -> N x|-> 3x+1). Plus > > tard, on s'est rendu compte que cette theorie logique s'appliquait > > parfaitement a l'informatique, et qu'il etait possible de programmer > > tout ce qui etait programmable avec cette theorie somme toute assez > > simple : on a des variables, l'abstraction fonctionnelle (equivalant a > > dire f(x) = 3x+1) et l'application (f(5) qui represente 3x5+1 soit 16). > > On a bien sur rajouter d'autres theories par la suite, comme le lambda > > calcul type, langage de module et foncteurs, extension oriente objet, > > programmation par continuation, monades, ...). > > Il n'y a rien dans cette description qui permette de dire > que C n'est pas un langage fonctionnel... À part BASIC (et > encore) tous les langages ont des fonctions qui permettent > de faire f(x)=3x+1.
Err, je decrivait le lambda calcul. Une expression du lambda calcul, note E ici est obtenu grace a : o des variables: x, y, z, ... o l'abstraction fonctionnelle, traditionnellement note par un lambda, mais j'utiliserait \ ici : \x.E o l'application, traditionellement note par un espace. f 5 correspond a l'application de la fonction f a l'argument 5, ou f(5) si tu prefere. Avec uniquement cela, et la beta-reduction comme regle de calcul : \x.A B => A[x<=B] (A ou tous les x ont ete remplace par B). Tu peut exprimer tout les programmes exprimable. Ou si tu prefere une notation en en ocaml : type lambda = Var of string | Lambda of string * lambda | App of lambda * lambda exception Nomal_Form let rec remplace x A = function | Var y -> if x = y then A else Var y | Lambda (y, l) -> if x = y then Lambda (y, l) else Lambda (y, remplace x A l) | App (a, b) -> App (remplace x A a, remplace x A b) let beta = function | App (Lambda (x, l), b) -> remplace x b l | _ -> raise Normal_Form Il faut ensuite avoir une strategie d'evaluation pour resoudre tous les beta-redex dans le terme, et il y a bien sur de nombreuse autre maniere de faire cela. Si cela t'interesse, je te renvoie notament a : http://pauillac.inria.fr/caml/lettre_de_caml/lettre6.pdf La difference entre ceci et la machine de turing, est que dans la machinede turing, si je ne me trompe pas, tu a une bande contenant des instructions, et qui est lu, et la lecture de la bande fait changer l'etat de la machine a etat, et ainsi de suite. La puissance d'expression des deux formalisme est exactement le meme, c'est a dire qu'il est prouve que tu peut exprimer exactement la meme classe de programmes dans les deux formalismes. > > > > Ceci dit, dans quel famille de langage classes-tu le C ? > > > > > > Procédural. Le C est pratiquement équivalent à Pascal. > > > > Ou qu'au C++, ou qu'a l'assembleur, au basic, ... > > Le BASIC que je connais n'avais pas de fonctions, et reste > nettement en dessous de C ou Pascal... Mais apparement > 'BASIC' ne veut pas dire grand chose :-) C'est bien la cle du malentendu. Tous ces langages sont des langages proceduraux, et le fait que certain inclus des fonctions et d'autre non ne change rien a ce fait. On parle auss ide langage applicatifs lorsque l'on parle de langage focntionnels. > Dans quelle catégorie places-tu Forth? C'est un langage procedural je crois, je suis pas un expert de Forth cependant. Une autre maniere de voire la difference entre les deux types de langages, c'est que dans un langage fonctionnel on s'interesse a decrire ce que les expressions et fonctions sont, alors qu'un langage imperatif s'interesse a comment elle seront execute. Amicalement, Sven Luther