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]

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.

[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