Re: logiciel de mail ?
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
Reply to: