Après les ateliers Cod'Art, Compression, Brainfuck et Calculatrice(s) auxquels vous êtes encore et toujours invités à participer si vous en avez envie et quelque chose à apporter, voici l'atelier P'tit Langage.

Le but est encore une fois de permettre à chacun de participer, dans le but de s'exercer, découvrir des langages amusants, de nouvelles façons de faire les choses, etc.

Si vous avez un problème de compréhension, n'hésitez pas à poser des questions. On est aussi là pour aider les gens. Si vous pensez que cela donnera lieu à une discussion longue, par exemple s'il faut débugguer un long programme qui ne marche pas et donner des explications, vous pouvez créer un topic à côté.

Présentation

Comment créer un langage de programmation ? La question revient souvent sur les forums du site du zéro. Malheureusement, ce n'est pas la bonne question. Ce qu'il faut se demander en premier, c'est : comment comparer des langages de programmation ?

En effet, ça ne sert à rien d'essayer de faire quelque chose de nouveau si on ne connaît pas ce qui existe déjà. Ce serait comme quelqu'un qui veut inventer une recette de cuisine, mais qui n'a jamais mangé que des pâtes et du riz, sans accompagnement. Il n'arrivera en général à rien de bon, il lui manque les connaissances de base que l'on acquiert en goûtant des plats et des ingrédients variés.

Pour les langages de programmation, c'est pareil : il faut goûter et étudier les ingrédients. La notion de variables, par exemple, revient dans quasiment tous les langages de programmation. Les concepts de procédure ou de fonctions aussi. Les boucles sont des concepts très présents, mais il existe des langages qui ne proposent pas de boucles dès le départ. Pourquoi ?
Pour s'habituer à ces questions, une bonne idée est d'expérimenter un peu soi-même sur un petit langage jouet, qui ne serait pas du tout original ou nouveau, mais permet de faire différents essais et de bien comprendre le fonctionnement de ces concepts.

Le sujet de cet atelier est donc l'implémentation d'un petit langage de programmation. Vous devrez écrire un programme (dans le langage de votre choix) qui joue le rôle d'interpréteur : il lit de petits 'programmes' (écrits dans le P'tit Langage) qu'on lui donne, il les évalue et donne le résultat.

Voici un exemple de programme du P'tit Langage : "(+ 2 2)". Son résultat est 4.

Pour évaluer un programme, il faut commencer par reconnaître sa structure : là, c'est une déclaration de variable, là un appel de fonction, etc. Ça a l'air tout bête, mais ce n'est pas si facile quand la syntaxe (les règles de grammaire) du langage est un peu compliquée. Mais ici on s'intéresse aux concepts, et pas à la syntaxe; pour éviter que vous perdiez trop de temps avec ça, on a choisi une syntaxe pour vous. Elle est très simple (sans doute la plus simple possible) et mettra tout le monde sur un pied d'égalité.

De plus, vous pourrez réutiliser pour l'analyse syntaxique les connaissances et le code accumulés par l'atelier Calculatrice(s), donc ça ne devrait pas être un problème. Ne vous focalisez pas sur l'emballage, c'est le goût qui nous intéresse !

Différentes fonctionnalités

La syntaxe de votre P'tit Langage est (globalement) fixée, mais les concepts sont plus libres. On vous propose une série de concepts différents, par ordre de difficulté, et vous choisissez lesquels vous allez accepter dans votre P'tit Langage.

Opérations arithmétiques

Ce premier concept du langage est très proche du langage mathématique "à la lisp" de l'atelier Calculatrice(s). Vous avez :

• des nombres (entiers positifs) : 1 2 33 ...
• des opérateurs mathématiques : + - * /
• une syntaxe pour appliquer un opérateur à des valeurs (op a b), où op est un opérateur et a, b des expressions du langage (des nombres ou des opérations mathématiques entre parenthèses).

Exemple de programme :

(+ 2 (* 3 4))

Déclaration de variables

Pour faire de votre P'tit Langage un langage qui se respecte, il faut se donner la possibilité de déclarer des variables.

• un opérateur define
• une syntaxe (define var val), où var est un nom de variable et val une expression.

Un programme avec des déclarations est tout simplement une suite de déclarations, suivie par une valeur (qui est le résultat du programme).

Exemple de programme :

(define six (+ 3 3))
(* six six)

Conditions booléennes

• des opérateurs de comparaison entre entiers : < <= > >= = <>
• des opérateurs booléens : and, or, not
• un opérateur de test if et sa syntaxe (if cond a b) où cond est une expression booléenne et a, b deux expressions de votre P'tit Langage.

Exemple de programme :

(if (not (> 3 (+ 4 2))) (* 3 6) 5)

On peut écrire des expressions sur plusieurs lignes, par exemple en indentant la partie "then" et la partie "else" :

(if (not (> 3 (+ 4 2)))
    (* 3 6)
    5)

Fonctionnalités impératives

Si vous choisissez d'ajouter ce concept, il vous sera enfin possible de modifier la valeur de vos variables !

• un opérateur d'assignement set!
• un operateur de boucle : (while cond expr)
• un opérateur de sequence : (begin expr expr expr ...) évalue les différentes expressions les unes à la suite des autres (un peu comme expr; expr; expr en C)

Exemple de programme :

(define i 0)
(define sum 0)
(while (< i 10)
    (begin
        (set! sum (+ sum i))
        (set! i (+ i 1))))
sum

Déclarations locales de valeur

Ce concept permet de déclarer des valeurs seulement pour un petit bout de code qui les utilise, et pas pour tout le reste du programme, grâce à l'opérateur let. La syntaxe est un peu compliquée parce qu'elle permet de déclarer plusieurs valeurs en même temps : (let ((var val) (var val) ...) expr)

Exemple de programme :

(+
    (let ((x 3) (y 2))
         (* x y))
    (/ 9 4))

Déclaration de fonctions

Ce concept est le plus difficile à implémenter.

On utilisera pour déclarer des fonctions une syntaxe proche de la déclaration de variable (define variable valeur) : on remplacera uniquement le nom de la variable par le nom de la fonction et de ses arguments (en nombre quelconque), le tout évidemment entre parenthèses : (define (f x y) valeur), où valeur sera le corps de la fonction.

Pour appeler une fonction, on fera comme pour les opérateurs : (f x y).

Exemple de programme :

(define (valeur_absolue x) (if (> x 0) x (- 0 x)))
(valeur_absolue (- 0 2))

(define (fact n)
    (if (= n 0) 1
        (* n (fact (- n 1)))))

(fact 8)

Valeurs composées : n-uplets

Il s'agit de pouvoir créer des structures de données plus complexes, des valeurs qui peuvent contenir plusieurs valeurs.

• un opérateur de création de couple ou n-uplet , : (, a b) pour le couple contenant les valeurs a et b
• un opérateur d'accès à un des champs (numérotés) d'une valeur composée, nth

Exemple de programme :

(define list (, 1 (, 2 3)))
(nth 0 (nth 1 list))

Liberté et responsabilité

Une fois que vous aurez implémenté ces ingrédients de base, vous pourrez choisir d'épicer un peu votre P'tit Langage avec des concepts plus avancés. Le but de cet atelier n'est pas que tout le monde fasse exactement la même chose, et si vous voyez des choses intéressantes à ajouter, vous pouvez faire des expérimentations.

Je vous encourage cependant à commencer par vous assurer que votre implémentation des bases est bien solide et propre. Il y a beaucoup de détails que je n'ai pas mentionnés en présentant ces concepts, de questions que vous devrez vous poser. Que fait par exemple le code suivant ?

(define x 2)
(+ x (let ((x 3)) x))

Même pour ces concepts de base, vous aurez donc des choix à faire. Quand vous en rencontrez un, n'hésitez pas à le signaler et à expliquer la décision que vous avez prise.

Il y a deux manières d'enrichir votre langage :

• ajouter de nouveaux concepts (pas si facile parce que mine de rien, on a quand même couvert le principal); vous pourriez par exemple vous demander comment introduire du typage (donner des types aux valeurs), des pointeurs/références, le filtrage de motifs, etc. Il faut aussi savoir ne pas avoir les yeux plus gros que le ventre : ce serait une mauvaise idée à mon avis de se lancer dans un système de Programmation Orientée Objet pour votre P'tit Langage.
• enrichir et étendre les concepts existants. Par exemple, on a montré comment transformer les define en déclaration de fonction, il est aussi facile d'étendre les let de la même manière. Le langage Scheme, qui nous a servi de base pour la syntaxe de notre langage, propose aussi deux opérateurs let* et letrec qui pourraient être intéressant. D'autres formes de boucles ou de conditions pourraient être intéressantes, des valeurs composées supplémentaires (chaînes de caractères, tableaux ?), etc.

Mais il faut aussi faire attention : vous être responsable de votre langage. Si vous y ajoutez n'importe quoi, il risque de devenir gras, informe et écoeurant. Si les ajouts ne sont pas assez réfléchis, ils peuvent casser la cohérence du langage. Le P'tit Langage de base est très simple, quelques paragraphes ont suffi pour le décrire en entier, mais il permet d'écrire des programmes sophistiqués; si vous ajoutez une tripotée de cas particuliers, vous ne gagnerez pas grand chose et votre langage sera beaucoup plus compliqué, donc moins élégant.

Citation : Saint-Exupéry

Il semble que la perfection soit atteinte non quand il n'y a plus rien à ajouter, mais quand il n'y a plus rien à retrancher.

N'hésitez pas à discuter avec les autres participants des idées que vous avez. Si cela mérite une discussion à part, créez un topic à part.

Règles

On veut un topic amical et créatif, ce n'est pas un concours et il n'y a pas de règles rigides. Tant que vous faites des efforts pour être courtois, respectueux et intéressant, ça devrait aller. Je me permets tout de même de recopier les indications données pour les derniers ateliers :

Citation : Conseils

On veut le code, on veut tripoter

Publiez toujours la source de votre programme (normalement vous n'avez besoin de donner rien d'autre); il faudrait, dans la mesure du possible, que chacun puisse l'essayer chez soi (donc évitez les langages propriétaires, les machins pas portables du tout, etc.).

Essayez de présenter votre source de la manière la plus lisible et la plus claire possible (pas de "oh j'ai pas eu le temps de mettre des vrais noms de variables"); sinon, vous vous exposez aux commentaires du public, et ça peut vous poursuivre pendant longtemps (hein delroth ?).

Les autres participants peuvent reprendre la source, la modifier, l'améliorer, etc. On n'impose pas de licence ou quoi (et si vous précisez une licence libre elle sera respectée, enfin j'espère), mais si vous n'êtes pas prêts à vous faire tripoter, ne postez rien.

Éviter les répétitions

Si vous avez fait un programme dans votre langage préféré, mais qu'il existe déjà une proposition pour ce langage (ou un langage quasiment identique) et que le votre n'apporte visiblement rien, vous pouvez vous retenir de poster. Cherchez plutôt un aspect intéressant à explorer (une optimisation, etc.).

Le but c'est surtout d'avoir un certain nombre de versions intéressantes à comparer, et de pouvoir voir par exemple les forces ou les faiblesses de certains langages ou styles de programmation. Pas de montrer à tout le monde qu'on est le meilleur programmeur de la planète (même si c'est cool aussi).

C'est marrant, je suis justement en train d'écrire un Lisp pour m'amuser, cependant il ne respecte pas tout à fait les consignes indiquées (au niveau du nom des fonctions par exemple, etc.) et il n'a pas les mêmes contraintes (un des trucs que je m'imposais était de pouvoir facilement coupler mon Lisp avec de l'OCaml, par exemple). Je le poste ici après ou c'est pas intéressant ?

Ah, et aussi :

(define i 0)
(define (f x) (+ i 1))
(define i 1)
(f 3) ;; Doit valoir 3 ou 4 ?

(define (g x) (let (machin y) (+ x y) machin) ;; On gère les closures ou pas ?

Ppjet6 > j'ai fixé la syntaxe du langage, pas la sémantique. C'est pour que les gens se débrouillent et décident de ce qu'il font. Fais tes choix en fonction de ce que tu voudrais gérer, et de ce que ton implémentation te permet de gérer.


Je me permets d'insister sur un point : P'tit Langage n'est pas un Lisp. J'ai repris la syntaxe parce qu'elle est simple, mais le but n'est pas que tout le monde essaie de faire un Lisp le plus authentique possible. Faites le langage que vous voulez, si vous voulez essayer d'écrire du C ou Haskell ou Io avec cette syntaxe (en abandonnant certains trucs et en changeant d'autres), ça me va.

C'est comme si quelqu'un disait "il y a des accolades { }, donc c'est du C, donc il faut implémenter l'arithmétique des pointeurs". Avec ce genre de raisonnement on serait pas allé bien loin

Salut !

Gloups, ya plein d'ateliers en ce moment Faudrait que je ressorte, nettoie et commente un code que j'ai déjà fait auparavant qui implémente un petit interpréteur de type array programming (les scalaires sont envisagés comme des cas particuliers de tableaux). Est-ce que c'est de la triche (on se comprend, je sais que ce n'est pas un concours et tout et tout) si c'est déjà fait et en lex/yacc ?

Cordialement,
Cacophrène

J'ai codé ça cette nuit, le code est pas exemplaire et il y a des gros hacks pour faire passer les fonctions OCaml en Lisp, mais ça fonctionne plutôt bien .

open Printf

(* Type of a value, Abstr is there for abstract types which can be
 * returned by any OCaml function *)
type abstr
type value =
|   Abstr of abstr
|   Unit
|   Int of int
|   Float of float
|   String of string
|   Symbol of string
|   Func of (context -> int -> value list -> value)
(* A context is where values will be searched with a name *)
and context = (string, value) Hashtbl.t

(* The AST definition. S stands for S-expression. *)
type ast =
|   S of (int * ast) list
|   Name of string
|   DirectValue of value

(* The return type of an OCaml function wrapped in Lisp *)
type retttype = [`Abstr | `Unit | `Int | `Float | `String | `Func]

(* Internal exception raised when an error is found. It is caught by
 * the exec function which will display an error message in the logs *)
exception Eval_error of string

(* As Eval_error, but raised when a parse error is found *)
exception Parse_error of string

(* The global context contains every global function of the lisp *)
let global_context = Hashtbl.create 42

(* Returns a Lisp function (type "value list -> value") from an OCaml
 * function, provided its number of arguments and return type. However
 * it's not type-safe for the arguments, and providing a bad argument
 * type will lead to segfaults ! *)
let wrap_ml_function name f nb_args ret =
    let val_to_ml line = function
    |   Abstr a -> Obj.magic a
    |   Unit -> Obj.magic ()
    |   Int i -> Obj.magic i
    |   Float f -> Obj.magic f
    |   String s -> Obj.magic s
    |   _ -> raise (Eval_error (
            sprintf ("unable to pass symbol or functions to OCaml " 
                     "functions at line %d") line
            ))
    in
    let wrapper _ line val_list =
        let len = List.length val_list in
        if len <> nb_args then (
            raise (Eval_error
                (sprintf ("bad argument number for function %s : " 
                          "got %d but %d expected") name len nb_args)
        )) ;
        let retval = List.fold_left (fun f arg ->
            ((Obj.magic f) : 'a -> 'b) (val_to_ml line arg)) f val_list in
        match ret with
        |   `Abstr -> Abstr (Obj.magic retval)
        |   `Unit -> Unit
        |   `Int -> Int (Obj.magic retval)
        |   `Float -> Float (Obj.magic retval)
        |   `String -> String (Obj.magic retval)
    in
    wrapper

(* A new context is a copy of the global context *)
let new_context () =
    Hashtbl.copy global_context

(* Register values or OCaml functions into a context *)
let register_value = Hashtbl.add
let register_ml_function ctx f name nb_args rettype =
    register_value ctx name (Func (wrap_ml_function name f nb_args rettype))

(* Merge two or more contexts into the first context *)
let merge_contexts = function
|   [] -> new_context ()
|   first :: others -> List.iter (Hashtbl.iter
(Hashtbl.add first)) others ; first

(* Ensures that a value is a function and return the ML func *)
let func_of_value line = function
|   Func f -> f
|   _ -> raise (Eval_error (sprintf ("this value is not a function, " 
                                     "it cannot be aplied at line %d") line))

(* Evaluate an AST *)
let rec eval_ast ctx (line, ast) = match ast with
|   S ((l2, Name n) :: args) when args <> [] ->
        let v = eval_ast ctx (l2, Name n) in
        let f = func_of_value l2 v in
        f ctx line (List.map (eval_ast ctx) args)
|   S _ ->
        raise (Eval_error (
            sprintf ("empty or one-element S-expression are not " 
                     "allowed at line %d") line
        ))
|   Name n -> (
        try
            Hashtbl.find ctx n
        with Not_found ->
            raise (Eval_error (
                sprintf "Unable to resolve symbol %s at line %d" n line
            )))
|   DirectValue v ->
        v

(* All valid ident chars *)
let ident_chars = "abcdefghijklmnopqrstuvwxyz" ^
                  "ABCDEFGHIJKLMNOPQRSTUVWXYZ" ^
                  "0123456789-_+=*/<>"

(* Is a character c in a string s ? *)
let char_in c s =
    try (
        ignore (String.index s c) ;
        true
    ) with Not_found ->
        false

(* Parse an ident in string s with length l beginning at index l *)
let parse_ident s n l =
    let rec parse_ident n acc =
        if n = l then
            n, acc
        else if char_in s.[n] ident_chars then
            parse_ident (n + 1) (acc ^ (String.make 1 s.[n]))
        else
            n, acc
    in
    parse_ident n ""

(* Parse a number, see parse_ident *)
let parse_number line s n l =
    let rec parse_number n acc =
        if n = l then
            n, acc
        else if char_in s.[n] "0123456789." then
            parse_number (n + 1) (acc ^ (String.make 1 s.[n]))
        else
            n, acc
    in
    let next, s = parse_number n "" in
    try
        next, Int (int_of_string s)
    with Failure _ ->
        try
            next, Float (float_of_string s)
        with Failure _ ->
            raise (Parse_error (sprintf "cannot parse number at line %d"
                                line))

(* Parse Lisp code into an AST *)
let parse s =
    let len = String.length s in
    let rec parse n l acc = if n = len then acc, n, l else match s.[n] with
    |   '\n' -> parse (n + 1) (l + 1) acc
    |   '(' when (n + 1 < l && s.[n + 1] = ')') ->
            parse (n + 2) l (acc @ [l, DirectValue Unit])
    |   '(' ->
            let parsed, next, nextline = parse (n + 1) l [] in
            parse next nextline (acc @ [l, S parsed])
    |   ')' ->
            acc, (n + 1), l
    |   '\'' ->
            let next, id = parse_ident s (n + 1) len in
            parse next l (acc @ [l, DirectValue (Symbol id)])
    |   c when (char_in c "0123456789.") ->
            let next, num = parse_number l s n len in
            parse next l (acc @ [l, DirectValue num])
    |   c when (char_in c ident_chars) ->
            let next, id = parse_ident s n len in
            parse next l (acc @ [l, Name id])
    |   _ ->
            parse (n + 1) l acc
    in
    parse 0 1 []

(* Execute a Lisp statement and catches eventual errors *)
let exec ?(fname = "<unknown-file>") ctx s =
    let ast = try
        let a, _, _ = parse s in a
    with Parse_error s -> (
        print_endline (sprintf "Parse error in %s : %s" fname s) ;
        []
    ) in
    let rec eval_all = function
    |   [] -> ()
    |   hd :: tl ->
            try (
                ignore (eval_ast ctx hd) ;
                eval_all tl
            ) with Eval_error s ->
                print_endline (sprintf "Eval error in %s : %s" fname s)
    in
    eval_all ast

Exemple d'utilisation :

let ctx = new_context ();;

let () = register_ml_function ctx (+) "+" 2 `Int;;
let () = register_ml_function ctx print_int "print-int" 1 `Unit;;

let () = exec ctx "(print-int (+ (+ 1 2) 3))";;

Pour la gestion des variables et fonctions, il faudrait rajouter d'autres fonctions qui elles manipulent l'environnement, via register_value. C'est faisable facilement et c'est laissé en exercice au lecteur.

Moi aussi j’ai codé un petit truc. Comme d’habitude, j’aime faire compliqué quand on peut faire simple et donc le code est plutôt long. J’ai d’abord essayé de faire un parser qui garde trace de la localisation des S-exp dans le code afin d’avoir des messages d’erreurs plus précis. Tout ça rend le code du parser pas forcément très joli (en plus je me trimballe les locs dans le code de l’évaluateur :-°).

Bref tout ça pour arriver à quelque chose de plus intéressant. J’ai eu un problème similaire à Ppjet6, à savoir comment « injecter » une fonction caml en lisp sans avoir à modifier la question (par exemple j’ai mon (+) qui renvoie la somme d’une liste d’entier non vide, int list -> int en caml et je veux la passer « directement » en lisp — en spécifiant juste son type).

La solution que j’ai choisi utilise les foncteurs (et en Haskell, avec les typeclasses, on aurait inférence automatique, plus classe :-°).

Pour attribuer un type à une fonction je lui associe un « pattern », (l’idée est de matcher un appel à une fonction contre le pattern associé à la fonction). Pour l’instant il y a 5 patterns différents :

• un seul élément ;
• une liste d’éléments ;
• un couple d’élements ;
• un choix (« either ») entre deux patterns ;
• un tuple, c'est-à-dire un élément, plus un autre pattern (pour faire
  une liste chaînée — différente de la première liste car on peut
  imposer un nombre fini d'arguments en faisant des tuples de tuples, ou
  bien des listes non vides en faisant Tuple(Element)(List(Element))).

Ensuite il faut typer chacun des éléments. J’ai pour l’instant implémenté ces « types » :

• entier, booléen ;
• identificateur ;
• expression évaluée (pour les (define x (+ 3   4)) par exemple) ;
• expression non évaluée (pour les (define (f x) x) par exemple) ;
• mot-clé, ça matche un identificateur précis

Ainsi il suffit de spécifier pour chacun de ces types / patterns comment le construire depuis une expression et comment construire une expression à partir d’une valeur caml. Ça nous mène aux signatures suivantes :

module type Value = sig
  type t
  val deserialize : Env.t -> evalfun -> sexp -> t * Env.t
  val serialize : t -> sexp_type
end
module type Pattern = sig
  type t
  val deserialize : loc -> Env.t -> evalfun -> sexp list -> t * Env.t
  val serialize : loc -> t -> sexp
end

Il ne reste plus qu’à coder tous les Value et les Pattern dont on a besoin. Par exemple, le type de « define » est le suivant :

(Either (Couple(Ident)(Sexp))
   (Couple
     (VTuple(Ident)(List(Ident)))
     (NESexp))
)
(Single(Ident))

En effet define prend soit deux arguments du type (identificateur valeur) (traduit par Couple(Ident)(Sexp)) (valeur doit être évaluée) soit une liste composée d’un identificateur suivi d’une liste de variable, liste suivie d’une expression à ne pas évaluer. Et define renvoie le nom de la variable définie.

Ensuite il ne reste qu’à définir une fonction du type ((string *sexp), ((string * string list) * sexp)) either -> string
Le code est pas mal long, j’ai uploadé les fichiers ici. Les fichiers intéressants :

• patterns.ml ;
• eval.ml

Bon, en vrai il faut que je rajoute deux trucs à mon langage pour qu'il soit complet : des polymorphes et des quotations (ce que j'appelle les quotations c'est en gros un bout d'AST évalué plus tard que le reste, comme un block en Ruby par exemple ou les NESexp d'asmanur). Comme ça j'pourrais faire par exemple (def 'nom-de-la-fonction 'arg-1 'arg-2 '(+ arg-1 arg-2)) et ça serait cohérent et pas magique.

À priori je peux pas définir de fonctions sans les quotations, d'ailleurs.

EDIT:

open Printf

(* Type of a value, Abstr is there for abstract types which can be
 * returned by any OCaml function *)
type abstr
type value =
|   Abstr of abstr
|   Unit
|   Int of int
|   Float of float
|   String of string
|   Symbol of string
|   Func of (context -> int -> value list -> value)
|   Quotation of (int * ast) list
(* A context is where values will be searched with a name *)
and context = (string, value) Hashtbl.t
(* The AST definition. S stands for S-expression. *)
and ast =
|   S of (int * ast) list
|   Name of string
|   DirectValue of value

(* The return type of an OCaml function wrapped in Lisp *)
type retttype = [`Abstr | `Unit | `Int | `Float | `String | `Func]

(* Internal exception raised when an error is found. It is caught by
 * the exec function which will display an error message in the logs *)
exception Eval_error of string

(* As Eval_error, but raised when a parse error is found *)
exception Parse_error of string

(* The global context contains every global function of the lisp *)
let global_context = Hashtbl.create 42

(* Returns a Lisp function (type "value list -> value") from an OCaml
 * function, provided its number of arguments and return type. However
 * it's not type-safe for the arguments, and providing a bad argument
 * type will lead to segfaults ! *)
let wrap_ml_function name f nb_args ret =
    let val_to_ml line = function
    |   Abstr a -> Obj.magic a
    |   Unit -> Obj.magic ()
    |   Int i -> Obj.magic i
    |   Float f -> Obj.magic f
    |   String s -> Obj.magic s
    |   _ -> raise (Eval_error (
            sprintf ("unable to pass symbol or functions to OCaml " 
                     "functions at line %d") line
            ))
    in
    let wrapper _ line val_list =
        let len = List.length val_list in
        if len <> nb_args then (
            raise (Eval_error
                (sprintf ("bad argument number for function %s : " 
                          "got %d but %d expected") name len nb_args)
        )) ;
        let retval = List.fold_left (fun f arg ->
            ((Obj.magic f) : 'a -> 'b) (val_to_ml line arg)) f val_list in
        match ret with
        |   `Abstr -> Abstr (Obj.magic retval)
        |   `Unit -> Unit
        |   `Int -> Int (Obj.magic retval)
        |   `Float -> Float (Obj.magic retval)
        |   `String -> String (Obj.magic retval)
    in
    wrapper

(* A new context is a copy of the global context *)
let new_context () =
    Hashtbl.copy global_context

(* Register values or OCaml functions into a context *)
let register_value = Hashtbl.add
let register_ml_function ctx f name nb_args rettype =
    register_value ctx name (Func (wrap_ml_function name f nb_args rettype))

(* Merge two or more contexts into the first context *)
let merge_contexts = function
|   [] -> new_context ()
|   first :: others -> List.iter (Hashtbl.iter
(Hashtbl.add first)) others ; first

(* Ensures that a value is a function and return the ML func *)
let func_of_value line = function
|   Func f -> f
|   _ -> raise (Eval_error (sprintf ("this value is not a function, " 
                                     "it cannot be aplied at line %d") line))

(* Evaluate an AST *)
let rec eval_ast ctx (line, ast) = match ast with
|   S ((l2, Name n) :: args) when args <> [] ->
        let v = eval_ast ctx (l2, Name n) in
        let f = func_of_value l2 v in
        f ctx line (List.map (eval_ast ctx) args)
|   S _ ->
        raise (Eval_error (
            sprintf ("empty or one-element S-expression are not " 
                     "allowed at line %d") line
        ))
|   Name n -> (
        try
            Hashtbl.find ctx n
        with Not_found ->
            raise (Eval_error (
                sprintf "Unable to resolve symbol %s at line %d" n line
            )))
|   DirectValue v ->
        v

(* All valid ident chars *)
let ident_chars = "abcdefghijklmnopqrstuvwxyz" ^
                  "ABCDEFGHIJKLMNOPQRSTUVWXYZ" ^
                  "0123456789-_+=*/<>"

(* Is a character c in a string s ? *)
let char_in c s =
    try (
        ignore (String.index s c) ;
        true
    ) with Not_found ->
        false

(* Parse an ident in string s with length l beginning at index l *)
let parse_ident s n l =
    let rec parse_ident n acc =
        if n = l then
            n, acc
        else if char_in s.[n] ident_chars then
            parse_ident (n + 1) (acc ^ (String.make 1 s.[n]))
        else
            n, acc
    in
    parse_ident n ""

(* Parse a number, see parse_ident *)
let parse_number line s n l =
    let rec parse_number n acc =
        if n = l then
            n, acc
        else if char_in s.[n] "0123456789." then
            parse_number (n + 1) (acc ^ (String.make 1 s.[n]))
        else
            n, acc
    in
    let next, s = parse_number n "" in
    try
        next, Int (int_of_string s)
    with Failure _ ->
        try
            next, Float (float_of_string s)
        with Failure _ ->
            raise (Parse_error (sprintf "cannot parse number at line %d"
                                line))

(* Parse Lisp code into an AST *)
let parse s =
    let len = String.length s in
    let rec parse n l acc = if n = len then acc, n, l else match s.[n] with
    |   '\n' -> parse (n + 1) (l + 1) acc
    |   '(' when (n + 1 < len && s.[n + 1] = ')') ->
            parse (n + 2) l (acc @ [l, DirectValue Unit])
    |   '(' ->
            let parsed, next, nextline = parse (n + 1) l [] in
            parse next nextline (acc @ [l, S parsed])
    |   ')' ->
            acc, (n + 1), l
    |   '\'' when (n + 1 < len && s.[n + 1] = '(') ->
            let parsed, next, nextline = parse (n + 2) l [] in
            parse next nextline (acc @ [l, DirectValue (Quotation parsed)])
    |   '\'' ->
            let next, id = parse_ident s (n + 1) len in
            parse next l (acc @ [l, DirectValue (Symbol id)])
    |   c when (char_in c "0123456789.") ->
            let next, num = parse_number l s n len in
            parse next l (acc @ [l, DirectValue num])
    |   c when (char_in c ident_chars) ->
            let next, id = parse_ident s n len in
            parse next l (acc @ [l, Name id])
    |   _ ->
            parse (n + 1) l acc
    in
    parse 0 1 []

(* Execute a Lisp statement and catches eventual errors *)
let exec ?(fname = "<unknown-file>") ctx s =
    let ast = try
        let a, _, _ = parse s in a
    with Parse_error s -> (
        print_endline (sprintf "Parse error in %s : %s" fname s) ;
        []
    ) in
    let rec eval_all = function
    |   [] -> ()
    |   hd :: tl ->
            try (
                ignore (eval_ast ctx hd) ;
                eval_all tl
            ) with Eval_error s ->
                print_endline (sprintf "Eval error in %s : %s" fname s)
    in
    eval_all ast

Ce code gère maintenant les quotations. Le problème c'est les polymorphes, ça m'obligerait à en gros typer tout mon code Lisp pour avoir un truc satisfaisant. Or je veux pas un truc typé et en plus j'ai du late-binding. Donc j'ai une solution plus simple : register_ml_function (fun x -> x) "int" 1 `Int. En gros, je peux faire des fonctions qui forcent le type de mes polymorphes (de type `Abstr) en me basant sur id. C'est gore mais ça fonctionne bien, je cherche pas à être un exemple (sur ce point, le code d'asmanur est suffisant ).

Si vous postez du code un peu long, mettez le en [secret] et/ou sur un site à part (attention aux pastes à durée limitée cependant, dans le doute je préfère le [secret] personellement).

Par ailleurs, vous faites ce que vous voulez mais si les autres (y compris des gens qui connaissent pas très bien votre langage ou le domaine sur lequel on travaille) peuvent comprendre, c'est encore mieux. Pour ma part je compte commencer par faire des choses plutôt simples, et attendre un peu pour partir en délire profond, mais visiblement ce n'est pas l'avis de tout le monde


Enfin, Ppjet6 tu devrais séparer un peu les trucs dans ton code (en différent modules, ou au moins pas toutes les fonctions mélangées au hasard). De manière générale, si vous pouvez séparer clairement la phase de parsing et la phase d'évaluation, ce n'en sera que plus lisible et agréable pour tout le monde.

Citation : Cacophrene

Gloups, ya plein d'ateliers en ce moment Faudrait que je ressorte, nettoie et commente un code que j'ai déjà fait auparavant qui implémente un petit interpréteur de type array programming (les scalaires sont envisagés comme des cas particuliers de tableaux). Est-ce que c'est de la triche (on se comprend, je sais que ce n'est pas un concours et tout et tout) si c'est déjà fait et en lex/yacc ?

Le problème des choses "déjà faites" c'est que ça colle pas forcément au sujet, et qui se tout le monde se met à balancer le fond de son $HOME dès que ça ressemble de près ou de loin à un interpréteur, on ne va pas s'en sortir. Si, par contre, tu l'as bien nettoyé et que c'est un truc cohérent avec ce qui nous concerne ici, il n'y a pas de problème. Et pour lex/yacc, aucun soucis, le but de cet atelier est d'évaluer, pas de parser, donc utiliser un parser tout fait est tout à fait normal.

Petite question:

Les lignes de ce type

(+ 2 (* 3 4))

doivent-elles afficher le résultat dans la console ? J'imagine que oui, mais ce n'est pas forcément évident pour les gens ne pratiquant pas ce genre de langages.

Citation : Nanoc

Petite question:

Les lignes de ce type

(+ 2 (* 3 4))

doivent-elles afficher le résultat dans la console ? J'imagine que oui, mais ce n'est pas forcément évident pour les gens ne pratiquant pas ce genre de langages.

Si tu es en utilisation interactive (« toplevel ») oui. Si tu évalues un fichier, la réponse est moins tranchée. À mon avis oui, sinon tu vas pas avoir d'output du tout (à moins d'introdure des foncions pour faire des i/o)

C'est ce que je pensais également pour l'intérêt de l'exercice. L'autre solution possible étant de créer la seule et unique fonction de la bilbiothèque standard du P'tit Language.

Je laisse les implémenteurs décider de ce genre de chose.


Voici une implémentation de démonstration. Le but est d'être le plus simple et le plus court possible, tout en couvrant une grande partie du sujet. Elle est en OCaml, comme les deux précédentes, mais nettement plus compréhensible.

Déclaration de l'AST, Arbre de Syntaxe Abstraite (la structure sur laquelle mon évaluateur travaille) :


Parseur (on passe de l'entrée à l'AST) :


Évaluation (AST -> résultat) :


Pour tester, réunir les trois fichiers en un seul (j'ai fait ça vite, il n'y a pas de modules bien séparés et tout, mais c'est évident à rajouter), et compiler :
ocamlfind ocamlc -pp camlp4of -package camlp4.lib -linkpkg -o ptit ptit.ml

Salut !

Citation : bluestorm

Le problème des choses "déjà faites" c'est que ça colle pas forcément au sujet, et qui se tout le monde se met à balancer le fond de son $HOME dès que ça ressemble de près ou de loin à un interpréteur, on ne va pas s'en sortir. Si, par contre, tu l'as bien nettoyé et que c'est un truc cohérent avec ce qui nous concerne ici, il n'y a pas de problème. Et pour lex/yacc, aucun soucis, le but de cet atelier est d'évaluer, pas de parser, donc utiliser un parser tout fait est tout à fait normal.

Bien entendu. Je ne compte pas me servir de cet atelier comme d'un débarras. En tout cas merci pour ces précisions. Je vais extraire ce qui colle au sujet, faire un grand nettoyage et le poster ici sous peu.

Cordialement,
Cacophrène

Yo %
Alors voilà, j'ai planché sur une implémentation en Perl, et j'ai implémenté une bonne partie du langage : maths, déclarations de variables, conditions, fonctionnalités impératives (j'ai un set sans ! au bout, 'tention). Il me reste les déclarations locales et de fonctions, ainsi que les tuples, mais je suis pas sûr d'avoir le temps de le faire donc je préfère poster.
Je vous laisse admirer le super "parsing" fait maison. Pour chaque toplevel sexp, j'écris le résultat de l'opération (un nombre, une assignation).

A priori tout fonctionne, mais je n'ai pas forcément tout testé.

Dans set, tu appelles define (si je comprends bien), mais define fait un test et échoue si la variable est déjà définie, ça ne pose pas de problème ?

Par ailleurs, je n'aime pas beaucoup l'hétérogénéité entre "shift" et l'extraction à la main. Le "shift" sent le type qui essaie d'être trop malin, et qui a peur de l'ordre d'évaluation. C'est pas terrible parce que tu espères que les opérations seront commutatives, ce qui n'est pas forcément le cas : "and" et "or" ne sont pas commutatives (si on respecte la convention d'évaluation paresseuse de gauche à droite), et "+" et "*" pas forcément non plus dès qu'on passe à des nombres flottants.

Pourquoi $funcs{begin} mais$funcs{'while'} ?

La méthode de parsing est astucieuse, mais je ne suis pas sûr qu'elle scale très bien aux extensions du langage (par exemple les déclarations locales utilise ((foo bar) (baz foobar)), donc tu vas avoir un tableau de trop) et elle est assez sensible aux espacements (à vue de nez "( + 1 2)" va avoir du mal à passer).

Bonjour.
Voici mon premier jet :
http://quentin.cormier.free.fr/ocaml/lisp/1
C'est un début du langage qui a été implémenté, jusqu'aux conditions et variables globales.
C'est encore un peu...brouillon et expérimental, mais ça marche !
Je compte bien le continuer, bravo encore une fois pour cet atelier !

Je planche sur une version C dès ce soir...

Citation : tc

Je planche sur une version C dès ce soir...

*respect*

Voici une nouvelle version qui gère maintenant le typage :
http://quentin.cormier.free.fr/ocaml/lisp/2
Exemple :

# (define a (+ 5 3))
# (define b (* 4 4))
# (print b)
Bad types with function print : print have type String but it here use with type Num
# (print (string b 12))
Bad types with function string : string have type Num but it here use with type Num -> Num
# (print (string b))
16.#

Par contre, je sais pas encore comment faire pour gérer les lignes et la postion des lexemes dans ocamlyacc :o.

Citation : bluestorm

Dans set, tu appelles define (si je comprends bien), mais define fait un test et échoue si la variable est déjà définie, ça ne pose pas de problème ?

Par ailleurs, je n'aime pas beaucoup l'hétérogénéité entre "shift" et l'extraction à la main. Le "shift" sent le type qui essaie d'être trop malin, et qui a peur de l'ordre d'évaluation. C'est pas terrible parce que tu espères que les opérations seront commutatives, ce qui n'est pas forcément le cas : "and" et "or" ne sont pas commutatives (si on respecte la convention d'évaluation paresseuse de gauche à droite), et "+" et "*" pas forcément non plus dès qu'on passe à des nombres flottants.

Pourquoi $funcs{begin} mais$funcs{'while'} ?

La méthode de parsing est astucieuse, mais je ne suis pas sûr qu'elle scale très bien aux extensions du langage (par exemple les déclarations locales utilise ((foo bar) (baz foobar)), donc tu vas avoir un tableau de trop) et elle est assez sensible aux espacements (à vue de nez "( + 1 2)" va avoir du mal à passer).

(Merci d'avoir commenté )

Oui en effet l'appel de define pose problème dans set, je l'avais appelé pour avoir le check gratuit du nom correct de la variable mais ça va pas. Mais bon ça se corrige rapidement.

Pour shift vs. @_, je trouve pas ça trop moche, mais c'est vrai qu'il vaut mieux respecter une norme. Ça ira de toute façon normalement mieux dans la version Perl 6 que je vais essayer d'écrire.
(Par contre je comprends pas, comment + ou * pourraient ne pas être commutatives avec les flottants ?)

while est un mot-clé du langage, pas define, et j'avais peut que Perl n'autoquote pas tout seul. Après deux-trois tests il le fait apparemment, donc un truc de plus à corriger .

Effectivement ma méthode de parsing fonctionne mal si on espace pas correctement, et je vois difficilement comment régler ça. Par contre pour les extensions, du moment que ça reste une syntaxe parenthésée, ça marche : pour le let par exemple, je vais récupérer quelque chose genre ["let", [["foo", "bar"], ["baz, "foobaz"]], code] . Mon interpréteur va voir un let, lancer la fonction correspondant qui est censée gérer ça bien. Non le vrai problème pour le let c'est la manière dont je gère les variables.

Salut !

Citation : robocop

Par contre, je sais pas encore comment faire pour gérer les lignes et la postion des lexemes dans ocamlyacc :o.

Deux étapes :

(1) Dans le lexer, mettre à jour les numéros de ligne à chaque \n rencontré. Pour OCaml 3.11 il y a une fonction dédiée (Lexing.new_line ). Pour les versions antérieures il faut la coder soi-même.

(2) Dans le parser, il faut utiliser les fonctions du module Parsing . Tu as ainsi accès à la localisation précise de l'erreur.

Cordialement,
Cacophrène

Merci Cacophrene, ça marche bien pour toutes les erreurs dans le parseur.
Mais si je veux traiter les erreurs lors de l'execution ou du typage par exemple, y-a-t-il un moyen de savoir directement la ligne de l'erreur en utilisant cet outil, ou faut-il à chaque fois stocker la ligne et la position dans l'arbre binaire, pour reporter l'erreur ?

Salut !

Citation : robocop

Mais si je veux traiter les erreurs lors de l'execution ou du typage par exemple, y-a-t-il un moyen de savoir directement la ligne de l'erreur en utilisant cet outil, ou faut-il à chaque fois stocker la ligne et la position dans l'arbre binaire, pour reporter l'erreur ?

Tout dépend du moment où sont détectées les erreurs de typage. Si c'est au moment du parsing, ça ne devrait a priori pas poser de problème. Si tu fais ça lors d'une seconde passe (directement sur l'AST), alors il faudra peut-être songer à garder des points de repère...

Cordialement,
Cacophrène

Citation : bluestorm

"+" et "*" pas forcément non plus dès qu'on passe à des nombres flottants.

Je conteste : ils ne sont peut-être pas associatifs mais ils sont bien commutatifs.

C'est pas une question de représentation mémoire des flottants ?

Il n'y a aucune raison que ce soit non commutatif, quelle que soit la représentation mémoire. Je viens de tester avec un langage qui est à priori compliant au standard de l'IEEE là dessus, et même avec des cas louches à base de NaN, d'infinis et de 0 négatifs j'ai toujours la commutativité respectée.

Salut !

Citation : Ppjet6

Il n'y a aucune raison que ce soit non commutatif

+1 dans la mesure où les nombres à virgule flottante forment grosso modo un sous-ensemble de l'ensemble R des nombres réels où les lois de composition interne + et * sont commutatives. Je ne vois que deux façons de casser la commutativité : (1) la surcharge (mais on sort des flottants) et (2) des problèmes d'implémentation (quoique...).

Remarque : En fait les flottants ne sont pas tout à fait un sous-ensemble de R, car l'infini (quel que soit son signe) n'en fait pas partie !

Cordialement,
Cacophrène

Gné, l'infini ne fait pas partie de <math>\(\mathbb R\)</math> ? C'est pour ça qu'on ouvre l'intervalle non ? (Je parle de <math>\(] -\infty, +\infty [\)</math>).

C'est justement ce qu'il dit. Les flottants ne sont pas un sous-ensemble de <math>\(\mathbb{R}\)</math> car <math>\(+\infty\)</math> est dans l'ensemble des flottants mais pas dans <math>\(\mathbb{R}\)</math>.

Re !

@zulon : comme te l'indique Ppjet6, c'est ce que j'ai écrit dans mon message, peut-être après ta lecture (je l'ai édité). En fait si on veut les nombres réels et l'infini, on a ce que l'on appelle la droite numérique achevée. Cependant beaucoup de codes utilisent des flottants sans jamais utiliser inf, -inf et NaN si bien que l'approximation n'est pas nécessairement mauvaise (même si, comme je l'ai dit, elle est indubitablement fausse).

Cordialement,
Cacophrène