Est-il possible d'avoir à la fois curry et fonction variadique?

13

Je pense à rendre les fonctions currying et variadic disponibles dans un langage de programmation fonctionnel typé dynamiquement, mais je me demande si c'est possible ou non.

Voici quelques pseudocodes:

sum = if @args.empty then 0 else @args.head + sum @args.tail

qui est censé résumer tous ses arguments. Ensuite, si sumlui-même est traité comme un nombre, le résultat est 0. par exemple,

sum + 1

est égal à 1, en supposant que +cela ne peut fonctionner que sur des nombres. Cependant, même si sum == 0c'est vrai, sumil conservera sa valeur et sa propriété fonctionnelle quel que soit le nombre d'arguments fournis (d'où "partiellement appliqué" et "variadique" en même temps), par exemple, si je déclare

g = sum 1 2 3

gest alors égal à 6, cependant, nous pouvons encore appliquer g. Par exemple, g 4 5 == 15c'est vrai. Dans ce cas, nous ne pouvons pas remplacer l'objetg par un littéral 6, car bien qu'ils produisent la même valeur lorsqu'ils sont traités comme un entier, ils contiennent différents codes à l'intérieur.

Si cette conception est utilisée dans un vrai langage de programmation, cela causera-t-il une confusion ou une ambiguïté?

Michael Tsang
la source
1
À strictement parler, l'utilisation du curry comme fondement d'un langage signifie que toutes les fonctions sont unaires - non seulement il n'y a pas de fonctions variadiques, il n'y en a même pas de binaires! Cependant, les programmes dans ce langage auront toujours l' air d' avoir pris plusieurs arguments, et cela vaut autant pour les fonctions variadiques que pour les fonctions normales.
Kilian Foth
Ensuite, ma question est simplifiée: "un objet peut-il être à la fois une fonction et une valeur de non-fonction?" Dans l'exemple ci-dessus, sumest 0sans argument et s'appelle récursivement avec un argument.
Michael Tsang
n'est-ce pas le travail de reduce?
ratchet freak
1
Jetez un oeil sur les fonctions que vous utilisez sur args: empty, headet tail. Ce sont toutes des fonctions de liste, ce qui suggère que la chose la plus simple et la plus simple à faire serait peut-être d'utiliser une liste où se trouvent les éléments variadiques. (Donc, sum [1, 2, 3]au lieu de sum 1 2 3)
Michael Shaw

Réponses:

6

Comment peut-on implémenter des varargs? Nous avons besoin d'un mécanisme pour signaler la fin de la liste des arguments. Cela peut être soit

  • une valeur de terminaison spéciale, ou
  • la longueur de la liste vararg passée comme paramètre supplémentaire.

Ces deux mécanismes peuvent être utilisés dans le contexte du curry pour implémenter des varargs, mais le typage approprié devient un problème majeur. Supposons que nous ayons affaire à une fonction sum: ...int -> int, sauf que cette fonction utilise le curry (nous avons donc en fait un type plus similaire sum: int -> ... -> int -> int, sauf que nous ne connaissons pas le nombre d'arguments).

Cas: valeur du terminateur: Soit endle terminateur spécial et Tle type de sum. Nous savons maintenant que appliqué à endla fonction retourne: sum: end -> intet celle appliquée à un entier nous obtenons une autre somme comme fonction: sum: int -> T. Par conséquent , Test l'union de ces types: T = (end -> int) | (int -> T). En substituant T, nous obtenons différents types possibles tels que end -> int, int -> end -> int, int -> int -> end -> int, etc. Cependant, la plupart des systèmes de type ne peuvent pas accueillir de tels types.

Cas: longueur explicite: le premier argument d'une fonction vararg est le nombre de varargs. Alors sum 0 : int, sum 1 : int -> int, sum 3 : int -> int -> int -> intetc. Ceci est pris en charge dans certains systèmes de type et est un exemple de frappe dépendante . En fait, le nombre d'arguments serait un paramètre de type et non un paramètre régulier - il ne serait pas logique pour l'arité de la fonction à dépendre d'une valeur d'exécution, s = ((sum (floor (rand 3))) 1) 2est évidemment mal tapé: ce Equivaut à deux s = ((sum 0) 1) 2 = (0 1) 2, s = ((sum 1) 1) 2 = 1 2ou s = ((sum 2) 1) 2 = 3.

En pratique, aucune de ces techniques ne doit être utilisée car elles sont sujettes aux erreurs et n'ont pas de type (significatif) dans les systèmes de type commun. Au lieu de cela, il suffit de passer une liste de valeurs comme l' un paramter: sum: [int] -> int.

Oui, il est possible qu'un objet apparaisse à la fois comme fonction et comme valeur, par exemple dans un système de type avec coercitions. Soit suma SumObj, qui a deux contraintes:

  • coerce: SumObj -> int -> SumObjpermet sumd'être utilisé en fonction, et
  • coerce: SumObj -> int nous permet d'extraire le résultat.

Techniquement, il s'agit d'une variante du cas de valeur de terminateur ci-dessus, avec T = SumObjet coerceétant un décapsuleur pour le type. Dans de nombreux langages orientés objet, cela est trivialement implémentable avec une surcharge d'opérateur, par exemple C ++:

#include <iostream>
using namespace std;

class sum {
  int value;
public:
  explicit sum() : sum(0) {}
  explicit sum(int x) : value(x) {}
  sum operator()(int x) const { return sum(value + x); }  // function call overload
  operator int() const { return value; } // integer cast overload
};

int main() {
  int zero = sum();
  cout << "zero sum as int: " << zero << '\n';
  int someSum = sum(1)(2)(4);
  cout << "some sum as int: " << someSum << '\n';
}
amon
la source
Réponse géniale! L'inconvénient de placer des varargs dans une liste est que vous perdez l'application partielle du curry. Je jouais avec une version Python de votre approche de terminateur, en utilisant un argument de mot-clé ..., force=False)pour forcer l'application de la fonction initiale.
ThomasH
Vous pouvez créer votre propre fonction d'ordre supérieur qui applique partiellement une fonction qui prend une liste, comme curryList : ([a] -> b) -> [a] -> [a] -> b, curryList f xs ys = f (xs ++ ys).
Jack
2

Vous voudrez peut-être regarder cette implémentation de printf dans Haskell , avec cette description de son fonctionnement . Il y a un lien sur la dernière page vers le document d'Oleg Kiselyov sur ce genre de chose, qui vaut également la peine d'être lu. En fait, si vous concevez un langage fonctionnel, le site Web d'Oleg devrait probablement être une lecture obligatoire.

À mon avis, ces approches sont un peu un hack, mais elles montrent que c'est possible. Si votre langue propose une saisie entièrement dépendante, cependant, c'est beaucoup plus simple. Une fonction variadique pour additionner ses arguments entiers pourrait alors ressembler à ceci:

type SumType = (t : union{Int,Null}) -> {SumType, if t is Int|
                                         Int,     if t is Null}
sum :: SumType
sum (v : Int) = v + sum
sum (v : Null) = 0

Une abstraction pour définir le type récursif sans avoir besoin de lui donner un nom explicite pourrait faciliter l'écriture de telles fonctions.

Edit: bien sûr, je viens de relire la question et vous avez dit un langage typé dynamiquement , à quel point évidemment la mécanique de type n'est pas vraiment pertinente, et donc la réponse de @ amon contient probablement tout ce dont vous avez besoin. Eh bien, je vais laisser cela ici au cas où quelqu'un viendrait à travers cela tout en se demandant comment le faire dans un langage statique ...

Jules
la source
0

Voici une version pour le curry des fonctions variadiques en Python3 qui utilise l'approche "terminator" de @amon, en tirant parti des arguments optionnels de Python:

def curry_vargs(g):
    actual_args = []
    def f(a, force=False):
        nonlocal actual_args
        actual_args.append(a)
        if force:
            res = g(*actual_args)
            actual_args = []
            return res
        else:
            return f
    return f

def g(*args): return sum(args)
f = curry_vargs(g)
f(1)(2)(3)(4,True) # => 10

La fonction retournée f collecte les arguments qui lui sont passés dans des appels successifs dans un tableau lié dans la portée externe. Ce n'est que lorsque l' forceargument est vrai que la fonction d'origine est appelée avec tous les arguments collectés jusqu'à présent.

Les mises en garde de cette implémentation sont que vous devez toujours passer un premier argument à f que vous ne puissiez pas créer un "thunk", une fonction où tous les arguments sont liés et ne peuvent être appelés qu'avec la liste d'arguments vide (mais je pense que cela est conforme à la mise en œuvre typique du curry).

Une autre mise en garde est qu'une fois que vous avez passé un mauvais argument (par exemple du mauvais type), vous devez recréer la fonction d'origine. Il n'y a pas d'autre moyen de réinitialiser le tableau interne, cela n'est fait qu'après une exécution réussie de la fonction curry.

Je ne sais pas si votre question simplifiée, "un objet peut-il être une fonction et une valeur de non-fonction en même temps?", Peut être implémentée en Python, comme référence à une fonction sans parenthèses évaluée à l'objet fonction interne . Je ne sais pas si cela peut être plié pour renvoyer une valeur arbitraire.

Ce serait probablement facile en Lisp, car les symboles Lisp peuvent avoir une valeur et une valeur de fonction en même temps; la valeur de la fonction est simplement sélectionnée lorsque le symbole apparaît en position de fonction (en tant que premier élément d'une liste).

ThomasH
la source