Définition de fonctions récursives primitives sur des types de données généraux

Les fonctions récursives primitives sont définies sur les nombres naturels. Cependant, il semble que le concept devrait se généraliser à d'autres types de données, permettant de parler de fonctions récursives primitives qui mappent des listes à des arbres binaires, par exemple. Par analogie, les fonctions récursives partielles sur les nombres naturels se généralisent bien aux fonctions calculables sur n'importe quel type de données, et j'aimerais comprendre comment faire le même type de généralisation pour les fonctions récursives primitives.

Intuitivement, si je devais définir un langage impératif simple qui permettait des opérations de base sur, disons des listes (comme la concaténation, prendre la tête et la queue, la comparaison des éléments) et une forme d'itération qui nécessite de savoir à l'avance combien d'itérations se produiront ( comme itérer sur les éléments d'une liste immuable), alors un tel langage devrait tout au plus être capable de calculer les fonctions récursives primitives sur des listes. Mais comment puis-je comprendre cela formellement, et plus précisément, comment pourrais-je prouver que mon langage calcule toutes les fonctions récursives primitives sur des listes et pas seulement un sous-ensemble d'entre elles?

Pour être clair, je suis intéressé à comprendre les fonctions récursives primitives comme une classe de fonctions bien définies (si elles le sont), plutôt que simplement par le fonctionnement de la récursion primitive elle-même, ce qui semble simple. Je serais intéressé par des pointeurs vers tout ce qui a été écrit sur la récursivité primitive sur des structures de données générales, ou même dans un contexte autre que les nombres naturels.

mise à jour: j'ai peut-être trouvé une réponse, dans un article intitulé Walther Recursion , par McAllester et Arkoudas. (Actes de CADE 1996 ). Il semble contenir une version généralisée de la récursion primitive ainsi que la récursion Walther plus puissante. J'ai l'intention d'écrire une auto-réponse une fois que j'ai digéré cela, mais en attendant, cette note pourrait être utile à d'autres personnes ayant la même question.

computability Nathaniel
la source

Je ne sais pas exactement ce que vous recherchez. Il semble que vous essayiez simplement de trouver des types W , mais ce n'est peut-être pas le cas.

Andrej Bauer

Il est probablement utile de noter que les types de données "ordinaires" (ressemblant à des arbres) peuvent être encodés de manière assez simple en nombres naturels, puis les fonctions PR sur les naturels sont une assez bonne représentation de ce que vous pourriez vouloir. Alternativement, vous pouvez utiliser le système T de Gödel étendu aux types de données de premier ordre strictement positifs avec les récurseurs "habituels".

cody

Vous pouvez restreindre les types de sortie des éliminateurs à des types de base si vous souhaitez éliminer cette "fonctionnalité".

cody

Il me semble toujours qu'une forme de types W restreints est ce que vous recherchez. Quelque chose comme les types W à ramification finie et les récurseurs limités à l'élimination dans d'autres types W restreints.

Andrej Bauer

La conférence CADE 1996 visite ici: dblp.org/db/conf/cade/cade96

John Fisher

Réponses:

En général, dans un langage avec des types de données (comme des listes, des arbres, etc.), il est facile de décrire un langage de fonctions qui se comportent exactement comme nous nous attendons à ce que la récursion primitive se comporte.

Par exemple, si le type de données est et que les constructeurs ont le type $D$ $c_1,\ldots, c_n$

c_{i} : T_{1}^{i} \to T_{2}^{i} \to \dots \to T_{k_{1}}^{i} \to D \to \dots \to D

$c_i : T_1^i\rightarrow T_2^i\rightarrow \ldots\rightarrow T_{k_1}^i\rightarrow D\rightarrow\ldots\rightarrow D$

alors le récursif pour le type de sortie aura le type $\mathrm{rec}_D^O$ $O$

{r e c}_{D}^{O} : (T_{1}^{1} \to \dots T_{k_{1}}^{1} \to D \to \dots \to D \to O \to \dots \to O) \to \dots \to D \to O

$\mathrm{rec}^O_D:(T_1^1\rightarrow\ldots T^1_{k_1}\rightarrow D\rightarrow \ldots\rightarrow D\rightarrow O\rightarrow \ldots\rightarrow O)\rightarrow\ldots\rightarrow D\rightarrow O$

et la sémantique opérationnelle sera:

{r e c}_{D}^{O} f_{1} \dots f_{n} (c_{i} t_{1} \dots t_{k_{i}} d_{1} \dots d_{m}) \to f_{i} t_{1} \dots t_{k_{i}} ({r e c}_{D}^{O} f_{1} \dots f_{n} d_{1}) \dots ({r e c}_{D}^{O} f_{1} \dots f_{n} d_{m})

$\mathrm{rec}^O_D\ f_1\ \ldots\ f_n\ (c_i\ t_1\ldots t_{k_i}\ d_1\ldots d_m)\rightarrow\\ f_i\ t_1\ldots t_{k_i}\ (\mathrm{rec}^O_D\ f_1\ldots\ f_n\ d_1)\ldots (\mathrm{rec}^O_D\ f_1\ldots f_n\ d_m)$

pour chaque . $i$

Quelque chose d'une bouche pleine! Au moins pour les nombres naturels, on obtient en effet

{r e c}_{N}^{O} : (N \to O \to O) \to O \to N \to O

$\mathrm{rec}_{\mathbb{N}}^O:(\mathbb{N}\rightarrow O\rightarrow O)\rightarrow O\rightarrow\mathbb{N}\rightarrow O$

{r e c}_{N}^{O} f_{0} f_{1} 0 \to f_{1} 0

$\mathrm{rec}^O_{\mathbb{N}}\ f_0\ f_1\ 0 \rightarrow f_1\ 0$ et

{r e c}_{N}^{O} f_{0} f_{1} (S n) \to f_{0} n ({r e c}_{N}^{O} f_{0} f_{1} n)

$\mathrm{rec}^O_{\mathbb{N}}\ f_0\ f_1\ (S\ n)\rightarrow f_0\ n\ (\mathrm{rec}^O_{\mathbb{N}}\ f_0\ f_1\ n)$

comme espéré (notez que le constructeur zéro n'a aucun argument!).

Si maintenant nous fonctions et des projections constantes, et des utilisations arbitraires de pour les types non fonctionnels , alors vous avez exactement une récursion primitive. $\mathrm{rec}^O_D$ $O$

De manière rassurante, si tous les sont également non fonctionnels, le codage Gödel habituel du type de données donne les mêmes fonctions récursives primitives. $T^j_i$

Ce serait bien d'avoir une description plus élégante de ce processus. C'est là que la réponse de Carlos intervient: ces types de données peuvent être décrits plus élégamment dans la théorie des catégories comme les algèbres initiales de certains foncteurs, souvent appelés foncteurs polynomiaux . Le récurseur est alors juste (une variante de) le morphisme initial de cette algèbre, parfois appelé catamorphisme par les gens essayant de confondre les choses. Ce morphisme existe par construction de l'algèbre initiale.

Un paramorphisme n'est que la variante particulière que j'ai décrite ci-dessus.

cody
la source

Je crains que cela ne me dépasse un peu. Pourquoi espérions-nous obtenir comme saisir la signature? Cela signifie-t-il automatiquement qu'il représente une récursivité primitive? (J'ai du mal à imaginer comment cela pourrait être lu uniquement à partir du type d'une fonction.) Je connais la théorie des types dans la mesure où je peux programmer en Haskell, mais je ne connais pas le formalisme que vous '' réutiliser ici. Où puis-je aller pour lire suffisamment d'informations pour comprendre ce que vous avez écrit?

{r e c}_{N}^{O} : (N \to O \to O) \to O \to N \to O

$\mathrm{rec}_{\mathbb{N}}^O:(\mathbb{N}\rightarrow O\rightarrow O)\rightarrow O\rightarrow\mathbb{N}\rightarrow O$

Nathaniel

Le type de découle du schéma plus général ci-dessus. Il représente la récursivité primitive parce que la sémantique opérationnelle représente l'opération de récursivité à partir de la définition des fonctions PR. Je n'ai pas expliqué la sémantique opérationnelle cependant, je vais donc développer mon commentaire.

{r e c}_{N}

$\mathrm{rec}_{\mathbb{N}}$

cody

Je n'ai pas de références élémentaires, bien que je suppose que ces diapositives donnent une belle introduction douce, et le chapitre 3 de la thèse de Ralph Mattes va dans d'énormes détails techniques, bien qu'il autorise les types inductifs non "de premier ordre".

cody

Je posais récemment cette question et j'ai trouvé plusieurs articles intéressants:

Logiques finales présentées par induction : (a) définit une logique qui fournit une notion générique de récursion primitive sur tout type de données satisfaisant certaines exigences (b) prouve que cette logique est une extension conservatrice de l'arithmétique récursive primitive.

La complexité des programmes en boucle : prouve que leur notion de programme en boucle est équivalente aux fonctions récursives primitives.

Programmes logiques pour les ensembles récursifs primitifs : prouve que leur classe de programmes logiques est équivalente aux fonctions récursives primitives.

Une caractérisation théorique des preuves des fonctions d'ensemble récursives primitives : prouve que toutes les fonctions récursives primitives sur un ensemble donné ne sont que celles définissables dans une théorie des ensembles très faible.

Stephen Skeirik
la source

Vous pensez peut-être au concept d'un paramorphisme ?

De la programmation fonctionnelle avec des bananes, des lentilles, des enveloppes et des barbelés :

Pour les nombres naturels, un paramorphisme est une fonction de la forme $h = (b, \oplus)$

\begin{aligned} h 0 & = b \\ h (n + 1) & = n \oplus (h n) \end{aligned}

$\begin{align} h\; 0 &= b \\ h\; (n + 1) &= n \oplus (h\; n) \end{align}$

Par exemple, la fonction factorielle a et . $b = 1$ $n \oplus m = (n + 1) \times m$

Pour les listes, un paramorphisme serait une fonction de la forme $h$

\begin{aligned} h nil & = b \\ h (cons a b) & = a \oplus (b, h b) \end{aligned}

$\begin{align} h\; \textsf{nil} &= b \\ h\; (\textsf{cons}\; a\; b) &= a \oplus (b, h\; b) \end{align}$

user76284
la source