Acid, le lisp-like de la communauté !

J'aurais tendance à rejoindre @nohar concernant la syntaxe. Partir sur un lisp-like me semble être un choix plus simple et pratique. Par exemple, partir sur une base de Scheme.

Concernant la syntaxe proposée, quelques remarques/propositions:

1. Typages

L'utilisation de -> en infixe ne me semble pas cohérent avec une syntaxe à la lisp, comme cela a déjà été relevé. Du coup, pourquoi ne pas reprendre ce que fait Common Lisp avec declare (c.f la spec) en adaptant un peu:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

(declare (type int x))
(define x 10)

(let ((x 0) (y 1.0))
  (declare (type int x)
           (type float y))
  (+ x y))

(declare (type (function int int int) add))
(define (add x y) (+ x y))

(declare (type (function (int 0 *) (int 0 *) (int 0 *)) uadd))
(define (uadd x y) (+ x y))

L'avantage, c'est que ça laisse la possibilité d'utiliser la forme declarepour préciser autre chose qu'une signature (e.g inline).

Types algébriques

1
2
3
4
5

(deftype Bool #t #f)

(deftype (List a)
  Nil
  (Cons a (List a)))

3. Autres

• Ca serait bien d'avoir des records ou structures:

1
2
3
4
5
6

(declare (type (struct int int) point))
(defstruct point x y)

(defstruct point
  (x :type float)
  (y :type float))

• Un système de macros, vu que ça parle d'un lisp-like. Les macros c'est cool parce que ça permet de construire le reste du langage et plus (e.g rajouter un système OO). A voir la compatibilité avec le typage statique par contre.

Voilà, c'était mes 2 cents

• Pour définir la valeur d'un tuple, pourquoi imposer le mot tuple ? Est ce qu'une suite d'expression ne peut pas représenter un tuple directement ? En gros pourquoi devoir écrire (tuple 1 2 3) plutôt que (1 2 3) ?

Dans ton système, comment distinguerais-tu un appel de fonction d’un tuple contenant la valeur renvoyée par ta fonction ? Pire encore, si on adopte la notation des types de lambdas sans flèche suggérée par nohar, comment distingues-tu (Char Char Char) qui est le type d’une lambda de (Char Char Char) qui est le type d’un tuple ?

Je suis pas sûr de comprendre le problème (ps : j'ai pas lu toute la spec, bien trop de notions que je ne saisis absolument pas ^^). Une lambda est définie par les types de ses arguments, suivi de son type de retour ? Par exemple une fonction d'addition : (lambda (Int Int Int)) (pas sûr de la syntaxe mais je suis sûr que vous me suivez). Du coup en fait, le type d'une lambda c'est un tuple, en sachant que le dernier élément a une signification différente, non ?

Le seul problème que je vois c'est le passage en paramètres. Si on passe un tuple à notre lambda, quel est la structure du tuple ? En reprenant mon exemple précédent, est-ce qu'on passe un tuple (Int Int) ou un tuple (Int Int Int) et la dernière variable sera notre retour ?

Merci pour vos futurs éclaircissement

Je trouve que Lisp à son élégance, il serait dommage de perdre ces aspects.

J'apprécie les propositions de Dominus mais je pense que l'on pourrait les revoir pour s'adapter à une philosophie plus proche de Lisp (sans la respecter à la lettre).

Faisons d'Acid quelques chose de simple mais élégant.

Il existe une fonction, qui s’appelle généralement map, et qui permet d’appliquer une fonction à tous les éléments d’une liste chaînée. Par exemple, on va appliquer une fonction uppercase à une liste de caractères, pour mettre toute la liste en majuscules.

Bon. la fonction uppercase est une lambda dans notre terminologie. Et son type est Char -> Char, puisqu’elle prend un Char et en renvoie un autre Char. Un tuple (Char Char), ce serait ('a' 'b'), par exemple.

Et faire map (uppercase) [a b c d e], ça a du sens, alors que faire map ('a' 'b') [a b c d e], cela n’en a aucun. Seulement, si on suit la représentation de Kje et celle de nohar, l’un et l’autre auraient pour type (Char Char). Impossible de les distinguer.

Voilà le problème.

Il suffit de décrire la fonction pour ce qu'elle est :

(function Char Char)

Et voilà, plus d'ambiguïté :

1
2
3
4

(declare 
  (type (function (function 'a 'b) (List 'a) (List 'b))) 
  map
)

Donc j'avais bien identifié le problème

Il me paraît plus simple de changer la déclaration de fonctions :

1
2
3
4
5

// Lambda (a peu de chose près)
(lambda (Char Char) -> Char) // 2 char en paramètre, 1 char en sortie

// Tuple
(Char Char)

Comme ça il y a une vraie différence et on peut passer un tuple en paramètre d'une fonction

Et pour mieux respecter Lisp :

1

(lambda (-> (Char Char) Char) Code)

Mais je crois que le problème n'est pas là, sa peut toujours aider pour la nouvelle spec

À la rigueur oui, utilisez la flèche à la place du mot-clé function de mon exemple, et ça revient exactement à corriger le problème, c'est-à-dire transformer une syntaxe infixe qui fait tâche en une forme qui soit uniforme avec le reste et tout aussi expressive. Le type de map donnerait :

(-> (-> 'a 'b) (List 'a) (List 'b))

À la fois lisible, non-ambigu et trivial à parser.

Et pour montrer ce que ça donne avec des tuples, le type de zip qui prend deux listes en argument et retourne une liste de tuples :

(-> (List 'a) (List 'b) (List ('a 'b)))

@Ricocotam: pour les tuples niveau valeur ta syntaxe reste ambiguë.

D'ailleurs même au nieau des types ça pourra devenir ambiguë plus tard, si on décide d'implémenter des higher-kinded types, ce qui est en fait déjà le cas de List.

Dans ton exemple nohar, (List 'a) pourrait alors désigner un tuple désignant une paire de liste abstraite (il s'agit d'un type inhabité mais c'est totalement valide quand même) et de type libre 'a.

Edit: Au passage j'ai réussi à implémenter les fonctions variadiques mais c'est dégueulasse donc je suis pas super satisfait. Je suis en train de penser à une autre façon de les coder.

Edit 2: Euh en fait nan, le tuple de types (Maybe, Int) n'est pas valide en Haskell. Mais si on élève le système de Hindley—Milner aux kinds, alors ça ne pose aucun souci théoriquement.

Edit 3: Ah si j'ai trouvé une autre façon de coder les fonctions variadiques, j'ai poussé sur le dépôt.

Dans ton exemple nohar, (List 'a) pourrait alors désigner un tuple désignant une paire de liste abstraite (il s'agit d'un type inhabité mais c'est totalement valide quand même) et de type libre 'a

List tout court devrait être interdit. Pour moi List est un type paramétrique, tu es obligé de lui spécifier un type en paramètre. Tu l'as dit toi-même : un type inhabité n'a aucun intérêt, alors pourquoi les autoriser ? Au mieux tu peux spécifier List 'a pour un type de liste abstrait.

Si on considère les fonctions comme des valeurs ordinaires, pourquoi de pas considérer les types paramétriques (qui sont juste des fonctions de types) comme des types ? A mon sens c'est logique, mais en effet il faudrait déjà avoir un système de type solide avant de penser à ça.

Mais par exemple si on veut implémenter en Acid la monade Free, qui s'écrit en Haskell

1
2
3
4
5

data Free f a
    = Pure a
    | Free (f (Free f a))

-- Free :: (* -> *) -> * -> *

… on a besoin de passer un foncteur en première argument de Free, donc un higher-kinded type.

PS: Comment ça se traduit higher-kinded types en français ?

Au pire quand ça se présentera (si ça se présente), tu pourras le noter (List) explicitement.

… Ou alors il faut noter les tuples eux-mêmes de façon explicite avec (tuple ...).

Oui mais on perd en cohérence

Dans l'idéal il faudrait la même syntaxe au niveau des types qu'au niveau des valeurs.

Au niveau des valeurs on aura donc (fonction) pour appeler fonction sans argument, mais au niveau des types on aura (List) pour justement ne pas appeler le type List ?

Et si on reprend les tuples, on aura (1, 'z', False) (je mets des virgules parce que la sinon on peut pas différencier certains cas d'un appel de fonction, mais proposez autre chose si vous avez une idée), et (Int Char Bool) ?

Une bonne grammaire est une grammaire cohérente.

… Ou alors il faut noter les tuples eux-mêmes de façon explicite avec (tuple …).

Pourquoi pas les virgules ? C'est pas super difficile à parser et ça a le mérite d'être clair. Ou sinon on garde ta syntaxe et on fait (, 1 'z' False) comme ça on garde la syntaxe LISP sans que ça soit trop verbeux.

Ce qui nous ramène au final à ce qui est spécifié une page plus haut. Je pense vraiment que c’est plus simple de marquer les tuples explicitement, quitte à ce que ce soit avec le mot-clé ', et laisser la forme (Char Char Char) pour les fonctions.

Ah non moi je parle de tout nommer explicitement. Les fonctions ET les tuples.

Pourquoi pas.

Sinon, concernant la syntaxe (+ 1 2 3 4 5) de Lisp, qui renvoie en réalité (+ 1 (+ 2 (+ 3 (+ 4 5)))) : en réalité, il serait possible de le faire ainsi avec la syntaxe proposée par nohar.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

(hastype ((lambda a b a) a (List b) a) foldl)

(define foldl (lambda (f acc xs) (
    match xs (
        (Nil acc)
        ((Cons x next) (foldl f (f acc x) next))
    )
)))

// C’est ici que ça se passe.
(foldl + 0 [1 2 3 4 5])

À mon sens, c’est plus propre que d’introduire un comportement qui n’existe que pour certaines fonctions particulières, et qui n’est pas signalé explicitement.

@Dominus Carnufex: Pour la plupart des cas foldl suffit, mais c'est pas super naturel d'écrire une liste à chaque fois que tu veux sommer plus de deux termes. Dans mon système de fonctions variadiques, on peut toujours appliquer partiellement les fonctions donc c'est pas un souci, on peut toujours utiliser foldl et leur donner un nombre indéterminé d'arguments.

De toute façon on aura besoin des fonctions variadiques pour les tuples et les flèches, donc j'ai pas implémenté ça pour rien

Bonsoir les enfants !

Concernant les problèmes liés aux fonctions et tuples, je pense personnellement qu'on peut considérer les fonctions et les tuples comme des types algébriques du point de vue syntaxique et donc noter explicitement les types Function et Tuple comme l'a proposé nohar. On réduit ainsi le nombre de constructions possibles (type primitifs, types algébriques et possiblement structures).

Ensuite, toujours syntaxiquement, on peut introduire les variadiques au moyen d'un sigil & devant le type du dernier argument de la fonction :

1
2
3
4
5
6
7

(hastype (Function &Int Int) add)
(define add (lambda (args)
  (match args
    ((Nil 0)
    ((Cons x xs) (+ x (add xs))))))

(add 1 2 3 4 5 6 7 8 9)

Enfin, pour une notation des tuples sans mot-clef genre (1 2 3), je suis contre, y a la macro quote pour ça et c'est pas pour rien.

Salut,

Je suis en train de re-regarder la spec de Carnufex pour compléter mon parser, et j'ai vu qu'il y avait encore des trucs un peu chelou genre ça:

1
2
3
4

(define List (type a (
    Nil
    (Cons a (List a))
)))

Pourquoi restreindre à un paramètre ?

Ensuite si on veut faire un alias de type on pourra pas distinguer la définition d'un type avec la définition d'une valeur.

Du coup moi je propose quelque chose comme ça:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

(deftype String [Char])

(deftype Bool (data
    True
    False
))

(deftype List (lambda (a)
    (data
        Nil
        (Cons a (List a))
    )
))

L'avantage de cette syntaxe c'est qu'on garde une cohérence avec notre syntaxe de déclaration des valeurs.

Edit: Je viens de voir que dans la spec, une lambda à un seul paramètre s'écrit (lambda x ...), sans parenthèses autour du x, donc ça restreint pas à un paramètre en fait

Pourquoi restreindre à un paramètre ?

Tu t’es répondu à toi-même, il n’y a en effet aucune restriction.

Ensuite si on veut faire un alias de type on pourra pas distinguer la définition d'un type avec la définition d'une valeur.

Si.

(34) Les identifiants de module, de type et de constructeur doivent commencer par une majuscule. Les autres identifiants doivent commencer par une minuscule.

1
2
3

(define String (List Char)) // Alias de type.

(define string "abc") // Définition d’une valeur.

Sauf si j’ai mal compris ce que tu veux dire.

Ah oui d'accord, j'avais zappé cette règle désolé