Discussion :

[SpiceGuid]

Voici le type de mes lambda-expressions et de mes lambda-valeurs:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
type lambda_expr =
  | Cst of int
  | Var of int
  | Abs of lambda_expr
  | App of lambda_expr * lambda_expr
  | Let of lambda_expr * lambda_expr
  | Letrec of lambda_expr * lambda_expr
and  lambda_val =
  | Val of int
  | Fun of (lambda_val -> lambda_val)
;;

Et mon évaluateur:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
let rec eval expr env =
  match expr with
  | Cst n    -> Val n
  | Var n    -> List.nth env n
  | Abs body     -> Fun (fun x -> eval body (x::env))
  | App (f,arg)  ->
      ( match eval f env with
      | Fun f -> f (eval arg env)
      | _ -> invalid_arg "Can't apply, not a function")
  | Let (e1,body) -> eval body (eval e1 env::env)
  | Letrec (e1,body) ->
      let rec env1 = (eval e1 env1)::env
      in eval body env1
;;

Tout marche très bien... jusqu'au Letrec.

[gorgonite]

env1 n'est pas censé être une liste... parce que sa définition me fait penser à une fonction

ça ne pose pas des problèmes de typage ?


par ailleurs, pourquoi les types sont mutuellement récursifs alors qu'ils ne s'utilisent pas l'un l'autre ?



EDIT en plus ça compile pas...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
| Letrec (e1,body) ->
(*      let rec env1 = (eval e1 env1)::env in  *)
      let env1 = (eval e1 env)::env in  
      eval body env1

[gorgonite]

une question... quelles opérations peux-tu espérer effectuer avec un tel langage
il n'y a aucune opération sur les constantes, aucune structures de données complexes, etc

c'est assez déconcertant... perso, je pense qu'il faudrait ajouter :
+ opérations arithmétiques de base
+ type "tuple"
+ système de continuations
+ évaluation paresseuse ?



par ailleurs, essaies de faire une machine virtuelle, c'est beaucoup plus marrant qu'un interprète

[SpiceGuid]

Pourquoi env1 une fonction? Une fonction aurait la forme suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

let rec env1 () = ...

Non ça ne pose pas de problème de typage, le message d'erreur n'est pas une erreur de typage.

Oui env1 est une liste, non ça ne compile pas, d'ailleurs si ça compilait ça marcherait puisque ma définition est bonne, je veux dire que la nouvelle valeur définie vaut bien eval e1 env1 et le nouvel environnement d'évaluation est bien env augmenté de cette nouvelle valeur.

Je formule ma question (ce que j'avais oublié de faire, désolé): comment dois-je implémenter l'évaluation du Letrec? (j'ai pas dis la compilation car c'est un autre problème qui ne me concerne pas ici ou en tout cas pas encore)

[gorgonite]

Non ça ne pose pas de problème de typage, le message d'erreur n'est pas une erreur de typage.

juste une erreur de let rec défini à droite d'un -> ; ce qui n'est pas autorisé

Oui env1 est une liste, non ça ne compile pas, d'ailleurs si ça compilait ça marcherait puisque ma définition est bonne, je veux dire que la nouvelle valeur définie vaut bien eval e1 env1 et le nouvel environnement d'évaluation est bien env augmenté de cette nouvelle valeur.

même si ça compilait, rien ne t'assure que ça marcherait... et j'ai du mal à cerner la logique de ton Letrec
avec une meilleure description de ce qu'est censé contenir chacun des deux éléments du doublet Letrec(e1, body), on aurait une chance de t'aider...

ton letrec est bien censé correspondre à une fonction récursive, donc il faudrait son identifiant pour pouvoir l'appeler dans son corps (body je suppose )
dans ce cas qu'est e1 ? les arguments ?


ps: la compilation est un problème... car même un programme conceptuellement juste, mais ne compilant pas, ne vaut "rien" ; sinon c'est qu'on est resté dans le domaine de l'algorithmie, et qu'il serait plus clair d'écrire en "pseudo-code"

[InOCamlWeTrust]

Voici le type de mes lambda-expressions et de mes lambda-valeurs:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
      let rec env1 = (eval e1 env1)::env

Ca compile (je ne peux pas essayer d'où je suis) ? Car si env1 est une liste, alors ce genre de construction récursive est interdite dixit le Fucking Manual, section 7.3...

http://caml.inria.fr/pub/docs/manual...manual021.html

[InOCamlWeTrust]

juste une erreur de let rec défini à droite d'un -> ; ce qui n'est pas autorisé

Non, c'est autorisé, le problème n'est pas là : le fait est que le let rec pour des valeurs non fonctionnelles possède certaines restrictions qui sont listées dans le Fucking Manual.

[InOCamlWeTrust]

ps: la compilation est un problème... car même un programme conceptuellement juste, mais ne compilant pas, ne vaut "rien" ; sinon c'est qu'on est resté dans le domaine de l'algorithmie, et qu'il serait plus clair d'écrire en "pseudo-code"

C'est vrai : un programme ne compilant pas vaut autant que ****mettre ce que l'on veut ici****.

Mais je ne sais pas si SpiceGuid ne se réferrait finalement pas à la partie compilatoire de son application, car il y a peut-être un langage derrière tout ça ?

P.S. : si tu as besoin d'un petit lambda-langage et que ça ne constitue pas le coeur de ton application, ne te fait pas chier et essaye de reprendre celui de Daniel de Rauglaudre présent dans le tutoriel de CamlP4 : il est pas mal.

[SpiceGuid]

Il est minable.

Le letrec que je veux implémenter est le letrec du lambda-calcul enrichi tel que défini par Peyton Jones à l'aide de l'exemple suivant (donné en lambda-calcul mais que j'ai traduit en "ocaml" pour la lisibilité):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
letrec fact = fun n -> if n = 0 then 1 else n * fact (n - 1)
in fact 4

Dans cet exemple fact est une variable, pas une fonction, car seule une variable peut avoir un nom (une fonction du lambda-calcul est toujours anonyme).

Ce letrec est indispensable pour introduire la récursivité, sans lui une fonction du lambda-calcul ne peut pas être récursive puisqu'elle n'a pas de nom.

Mon problème c'est que ce letrec du lambda-calcul enrichi est précisément celui que OCaml interdit.

Il semble que la solution soit d'implémenter le super-combinateur Y, c'est-à-dire qu'il faut implémenter le let et le rec séparément, les deux ensemble ça n'est possible que dans le lambda-calcul enrichi.
J'ai déjà implémenté le let, il ne reste plus qu'à implémenter le rec comme la littérature le propose, c'est-à-dire avec la propriété rec F = F (rec F):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
type lambda_expr =
  | Cst of int
  | Var of int
  | Abs of lambda_expr
  | App of lambda_expr * lambda_expr
  | Let of lambda_expr * lambda_expr
  | Rec of lambda_expr;;
 
type  lambda_val =
  | Val of int
  | Fun of (lambda_val -> lambda_val)
;;
 
let rec eval expr env =
  match expr with
  | Cst n    -> Val n
  | Var n    -> List.nth env n
  | Abs body     -> Fun (fun x -> eval body (x::env))
  | App (f,arg)  ->
      ( match eval f env with
      | Fun f -> f (eval arg env)
      | _ -> invalid_arg "Can't apply, not a function")
  | Let (e,body) -> eval body (eval e env::env)
  | Rec f -> eval (App(f,Rec f)) env
;;

Voilà on a éliminé le letrec et ça compile.
Je cocherai résolu dès que je serai certain d'avoir ce faisant également implémenté le letrec multiple du lambda-calcul enrichi, c'est-à-dire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
letrec var1 = e1
and var2 = e2
...
and varn = en
in body

Pour l'instant c'est pas encore très clair pour moi et la littérature est pas trop abordable c'est le moins que l'on puisse dire. Si vous voulez bien éclairer ma lanterne à ce sujet c'est pas de refus.

[InOCamlWeTrust]

Il est minable.

Ah oui ? Tu as bien compris les 4 ou 5 pages à son sujet ?

Le letrec que je veux implémenter est le letrec du lambda-calcul enrichi tel que défini par Peyton Jones à l'aide de l'exemple suivant (donné en lambda-calcul mais que j'ai traduit en "ocaml" pour la lisibilité):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
letrec fact = fun n -> if n = 0 then 1 else n * fact (n - 1)
in fact 4

Cet exemple marche parfaitement tel quel depuis au moins OCaml 3.06 : je viens d'essayer sous Solaris 9 sur UltraSparc IIIi.

More precisely, consider the expression:
let rec name1 = expr1 and … and namen = exprn in expr

It will be accepted if each one of expr1 … exprn is statically constructive with respect to name1 … namen and not immediately linked to any of name1 … namen

An expression e is said to be statically constructive with respect to the variables name1 … namen if at least one of the following conditions is true:

* ...
* e has the form fun … -> …
* ...

[SpiceGuid]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
let rec fact = fun n -> if n = 0 then 1 else n * fact (n - 1)
in fact 4;;

Je viens d'essayer et cet exemple marchait déjà en Caml Light 0.74, donc je ne pense pas que ce soit vraiment une nouveauté.

Personnellement je n'utilise ni Camlp4 ni CamlYacc/CamlLex et autres extensions du langage, juste OCaml c'est bien suffisant si on sait écrire les fonctions qui remplacent ces utilitaires, je veux programmer, je ne veux pas lire des manuels d'utilisation qui ne serviront qu'à grossir mon environnement de développement tout en me rendant dépendant de ceci/cela.

Pour en revenir à mon problème on ne peut pas s'en sortir par une pirouette théorique comme je l'ai cru assez naïvement. Le combinateur Y c'est puissant et séduisant mais c'est du lambda-calcul pur c'est-à-dire qu'il faut l'évaluation paresseuse, avec l'évaluation stricte son évaluation ne termine pas. Bien sûr ça se voyait dans la propriété rec F = F (rec F), belle récursion en effet, mais à force de lire des gens intelligents qui disent que c'est magique j'ai fini par croire que ça pouvait s'appliquer à mon cas.

Donc il faut en revenir au let rec traditionnel, l'important c'est de comprendre qu'on ne peut pas mettre n'importe quel e dans let rec v = e in body. En cernant mieux ce que peut être e on doit pouvoir utiliser le let rec ocaml pour implémenter le let rec recherché.

Dès que j'ai une implémentation avec un exemple pour la valider je la dépose ici.

[InOCamlWeTrust]

Personnellement je n'utilise ni Camlp4 ni CamlYacc/CamlLex et autres extensions du langage, juste OCaml c'est bien suffisant si on sait écrire les fonctions qui remplacent ces utilitaires, je veux programmer, je ne veux pas lire des manuels d'utilisation qui ne serviront qu'à grossir mon environnement de développement tout en me rendant dépendant de ceci/cela.

CamlP4 je peux comprendre, mais remplacer ocamllex/ocamlyacc par autre chose, c'est comme se tirer une balle dans le pied, étant donné que ces deux outils (et c'en sont vraiment) sont très très simples à utiliser si on les compare aux versions C lex/yacc. Mais chacun fait ce qu'il veut, et c'est juste un commentaire de la part de quelqu'un qui les a beaucoup utilisés et qui n'aime pas non plus devoir apprendre tout un tas de trucs nouveaux.

[gorgonite]

remplacer ocamllex/ocamlyacc par autre chose, c'est comme se tirer une balle dans le pied, étant donné que ces deux outils (et c'en sont vraiment) sont très très simples à utiliser si on les compare aux versions C lex/yacc.

franchement, en C si tu utilises flex/bison, ce sera aussi simple que ocamllex/ocamlyacc

[InOCamlWeTrust]

Non, tout de même moins, notament à cause du fonctionnement de ces outils en C, privilégiant les effets de bord et de leur complexité inhérente (mais c'est ce qui fait aussi leur richesse).

[gorgonite]

Non, tout de même moins, notament à cause du fonctionnement de ces outils en C, privilégiant les effets de bord et de leur complexité inhérente (mais c'est ce qui fait aussi leur richesse).

franchement pour avoir fait du flex/bison avec un compilateur écrit en C++, je peux t'assurer que mes fichiers de parsage étaient aussi concis qu'en ocamllex/ocamlyacc ; mais faut avouer qu'il y a avait pas mal de code ailleurs pour autoriser de si belles "interfaces"

[SpiceGuid]

Voilà qui est fait, le let rec multiple est implémenté avec le minimum de contraintes possible sur la forme des définitions. J'ai également ajouté un minimum d'opérateurs pour tester tout ça.

La source, un interpréteur de lambda-calcul enrichi, à évaluation stricte, avec let, let rec et let rec multiple, dans cette source Lectrec1 est une récursion simple, Letrecm est une récursion multiple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
type lambda_expr =
  | Var of int
  | Abs of lambda_expr
  | App of lambda_expr * lambda_expr
  | Let of lambda_expr * lambda_expr
  | Letrec1 of lambda_expr * lambda_expr
  | Letrecm of (lambda_expr list) * lambda_expr
  (* more lambda_expr *)
  | Cst of int
  | True_cst | False_cst
  | Nul of lambda_expr
  | Pre of lambda_expr
  | Les of lambda_expr * lambda_expr
  | Add of lambda_expr * lambda_expr
  | Mul of lambda_expr * lambda_expr
  | Cnd of lambda_expr * lambda_expr * lambda_expr
;;
 
type lambda_val =
  | True_val | False_val
  | Val of int
  | Fun of lambda_expr * (lambda_val list ref);;
 
let rec eval expr env =
  let unary f a =
      ( match eval a env with
      | Val n -> f n
      | _ -> invalid_arg "Integer expected"
      )
  and binary f a b =
      ( match eval a env, eval b env with
      | Val n, Val m -> f n m
      | _ -> invalid_arg "Integer expected"
      )
  and set_env envn = 
      ( function
      | Fun (body,envr) -> envr := envn
      | _ -> ())
  in match expr with
  | Var n    -> List.nth env n
  | Abs body     -> Fun (body,ref env)
  | App (f,arg)  ->
      ( match eval f env with
      | Fun (body,env0) -> (fun x -> eval body (x::!env0)) (eval arg env)
      | _ -> invalid_arg "Can't apply, not a function")
  | Let (e,body) -> eval body (eval e env::env)
  | Letrec1 (e1,body) ->
      let env1 = (eval e1 env)::env in
      let () = (set_env env1) (List.hd env1)
      in  eval body env1
  | Letrecm (expr_list,body) ->
      let bindings = List.map (fun e -> eval e env) expr_list in 
      let envn =  bindings @ env in
      let () = List.iter (set_env envn) bindings;
      in  eval body envn
  (* more lambda_expr *)
  | Cst n     -> Val n
  | True_cst  -> True_val
  | False_cst -> False_val
  | Nul a -> unary (fun n -> if n = 0 then True_val else False_val) a
  | Pre a -> unary (fun n -> Val (n-1)) a
  | Les (a,b) -> binary (fun n m -> if n < m then True_val else False_val) a b 
  | Add (a,b) -> binary (fun n m -> Val (n + m)) a b 
  | Mul (a,b) -> binary (fun n m -> Val (n * m)) a b 
  | Cnd (e1,e2,e3)->
      ( match eval e1 env with
      | True_val  -> eval e2 env
      | False_val -> eval e3 env
      | _ -> invalid_arg "Boolean expected"
      )
;;

Les examples de test (en source ocaml):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
(fun n -> n - 1) 2;;
 
let rec fact = fun n -> if n=0 then 1 else n * fact (n-1)
in fact 4;;
 
let rec fibo = fun n -> if n < 2 then n else fibo (n - 1) + fibo (n - 2)
in fibo 7;;
 
let rec even = fun n -> if n = 0 then true  else odd  (n - 1)
and      odd = fun n -> if n = 0 then false else even (n - 1)
in even 7;;

Les évaluateurs correspondants à ces expressions (après une hypothétique analyse syntaxique):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
eval (App((Abs(Pre (Var 0))),Cst 2)) [];;
 
let fact4 = Letrec1 (
  (Abs (Cnd (Nul (Var 0), Cst 1, (Mul (Var 0, App (Var 1,Pre (Var 0))))))),
  (App (Var 0,Cst 4))
)
in eval fact4 [];;
 
let fibo7 = Letrec1 (
  (Abs
    (Cnd
       (Les (Var 0,Cst 2),
       (Var 0),
       (Add (App (Var 1,Pre (Var 0)), App (Var 1,Pre (Pre (Var 0)))))))),
  (App (Var 0,Cst 7)))
in eval fibo7 [];;
 
let even7 = Letrecm (
  [
  (Abs (Cnd (Nul (Var 0), True_cst, (App (Var 1,Pre (Var 0))))));
  (Abs (Cnd (Nul (Var 0), False_cst,(App (Var 2,Pre (Var 0))))))
  ],
  (App (Var 1,Cst 7))
)
in eval even7 [];;

Le résultat de l'évaluation des exemples de test (ça va sans dire mais ça va encore mieux en le disant):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
Val 1
Val 24
Val 13
False_val

Restrospectivement, et à la vue des changements dans ma source, il était idiot de dire que "si ça compilait ça marcherait" ou de sous entendre que le let rec du lambda-calcul est plus puissant que celui de ocaml. Ne croyez pas que vos commentaires n'ont pas aidé, bien au contraire sans eux j'aurais persisté dans une voie qui m'éloignait de la solution.

Pour l'analyse lexicale/syntaxique il faudra que je m'y remette, mais je vous assure j'ai des fonction perso qui rendent Yacc/Lex complètement inutiles voire même plutôt désagréables comparé à tout faire en OCaml. On en reparlera quand j'aurai mis tout cela au propre, vous pourrez comparer avec ce que vous faites et choisir la meilleure façon à votre idée. Quand tout ça sera plus mûr je ferai un tutoriel pour l'écriture de compilateur/interpréteur/translateur en ocaml sans outil ni extension, juste avec un simple module qui contient les fonctions lexicales, syntaxiques et leur traitement d'erreur (automatique).


PS: j'ai jeté un coup d'oeil très rapide au tutoriel camlp4, on y défini bien une syntaxe abstraite pour les lambda-termes mais sans définir aucune fonction d'évaluation, et d'ailleurs ça n'est pas l'objet du tutoriel donc c'est bien compréhensible.

[gasche]

Pour l'analyse lexicale/syntaxique il faudra que je m'y remette, mais je vous assure j'ai des fonction perso qui rendent Yacc/Lex complètement inutiles voire même plutôt désagréables comparé à tout faire en OCaml.

Avec des monades ?
(* intéressé *)

[SpiceGuid]

Avec des parsers combinators pour l'analyse syntaxique.

Pour l'analyse lexicale j'utilise une approche qui automatise l'avancement de la lecture et le traitement d'erreur: au lieu de demander quel est le prochain lexème je demande si ce prochain lexème est ceci, puis celà, et à la fin je force la dernière option possible.

Par exemple au lieu d'écrire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
let parse_statement scan =
  if scan.is_word () && (scan.word = "if") then
    (scan.read(); ...)
  else if scan.is_word () && scan.word = "let") then
    (scan.read(); ...)
  else if scan.is_word () && scan.word = "match") then
    (scan.read(); ...)
  else if scan.is_word () && scan.word = "begin") then
    (scan.read(); ...)
  else if scan.is_word () && scan.word = "for") then
    (scan.read(); ...)
  else if scan.is_word () && scan.word = "while") then
    (scan.read(); ...)
  else begin
    message "syntax error, a word is expected, \"while\" would be correct here"
  end;;

J'écris:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
let parse_statement scan =
  if scan#is_word "if" then
    ()
  else if scan#is_word "let" then
    ()
  else if scan#is_word "match" then
    ()
  else if scan#is_word "begin" then
    ()
  else if scan#is_word "for" then
    ()
  else begin scan#force_word "while";
    ()
  end;;

Et ce code ne contient plus aucune opération de lecture ni de traitement d'erreur, il ne contient plus que la syntaxe, il fournit la séparation de code d'un Lex tout en conservant l'expressivité d'un OCaml.

[InOCamlWeTrust]

Tu es normalien ?

[Garulfo]

Tu es normalien ?

On dit « es tu normal ? » plutôt ...