Definieren primitiver rekursiver Funktionen über allgemeine Datentypen

Die primitiven rekursiven Funktionen werden über die natürlichen Zahlen definiert. Es scheint jedoch, als ob das Konzept auf andere Datentypen verallgemeinert werden sollte, sodass man über primitive rekursive Funktionen sprechen kann, die Listen beispielsweise Binärbäumen zuordnen. Analog dazu lassen sich partielle rekursive Funktionen über die natürlichen Zahlen gut auf berechenbare Funktionen für jeden Datentyp verallgemeinern, und ich möchte verstehen, wie die gleiche Art der Verallgemeinerung für primitive rekursive Funktionen vorgenommen werden kann.

Wenn ich intuitiv eine einfache imperative Sprache definieren würde, die grundlegende Operationen ermöglicht, z. B. Listen (wie Verkettung, Kopf und Schwanz, Vergleich von Elementen) und eine Form der Iteration, bei der im Voraus bekannt sein muss, wie viele Iterationen auftreten werden ( B. über die Elemente in einer unveränderlichen Liste iterieren), sollte eine solche Sprache höchstens in der Lage sein, die primitiven rekursiven Funktionen über Listen zu berechnen. Aber wie kann ich das formal verstehen und genauer gesagt, wie würde ich beweisen, dass meine Sprache alle primitiven rekursiven Funktionen über Listen und nicht nur eine Teilmenge davon berechnet?

Um es klar auszudrücken, ich bin daran interessiert, primitive rekursive Funktionen als eine genau definierte Klasse von Funktionen zu verstehen (falls dies tatsächlich der Fall ist), und nicht nur an der Operation der primitiven Rekursion selbst, die unkompliziert erscheint. Ich würde mich für Hinweise auf alles interessieren, was über primitive Rekursion über allgemeine Datenstrukturen oder in einem anderen Kontext als den natürlichen Zahlen geschrieben wurde.

Update: Ich habe möglicherweise eine Antwort in einem Artikel namens Walther Recursion von McAllester und Arkoudas gefunden. (Proceedings of CADE 1996. ) Dies scheint eine verallgemeinerte Version der primitiven Rekursion sowie die stärkere Walther-Rekursion zu enthalten. Ich habe vor, eine Selbstantwort zu schreiben, sobald ich diese verdaut habe, aber in der Zwischenzeit könnte diese Notiz für andere mit derselben Frage hilfreich sein.

computability Nathaniel
quelle

Mir ist nicht klar, wonach Sie genau suchen. Es scheint, als würden Sie nur versuchen, W-Typen zu finden , aber das ist es vielleicht nicht.

Andrej Bauer

Es ist wahrscheinlich nützlich zu bemerken, dass "gewöhnliche" (baumartige) Datentypen auf ziemlich einfache Weise in natürliche Zahlen codiert werden können, und dann sind die PR-Funktionen über den Naturtönen eine ziemlich gute Darstellung dessen, was Sie vielleicht wollen. Alternativ können Sie Gödels System T verwenden , das mit den "üblichen" Rekursoren auf die streng positiven Datentypen erster Ordnung erweitert wurde.

Cody

Sie können die Ausgabetypen der Eliminatoren auf Basistypen beschränken, wenn Sie diese "Funktion" entfernen möchten.

Cody

Es scheint mir immer noch, dass eine Form von eingeschränkten W-Typen das ist, wonach Sie suchen. So etwas wie W-Typen mit endlicher Verzweigung und die Rekursoren beschränken sich darauf, in andere eingeschränkte W-Typen zu eliminieren.

Andrej Bauer

Die CADE-Konferenz 1996 besuchen Sie hier: dblp.org/db/conf/cade/cade96

John Fisher

Antworten:

Im Allgemeinen ist es in einer Sprache mit Datentypen (wie Listen, Bäumen usw.) einfach, eine Sprache von Funktionen zu beschreiben, die sich genau so verhalten, wie wir es von einer primitiven Rekursion erwarten.

Wenn der Datentyp beispielsweise ist und die Konstruktoren den Typ haben $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$

dann hat der Rekorder für den Ausgabetyp den Typ $\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 Ö

$\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$

und die operative Semantik wird sein:

{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)$

für jedes . $i$

So etwas wie ein Mund voll! Zumindest für natürliche Zahlen erhalten wir tatsächlich

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

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

und

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

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

{r e c}_{N.}^{Ö} f_{0} f_{1} (S. n) \to f_{0} n ({r e c}_{N.}^{Ö} 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)$

wie erhofft (beachten Sie, dass der Nullkonstruktor keine Argumente hat!).

Wenn wir jetzt für konstante Funktionen und Projektionen ermöglichen und erlauben beliebige Anwendungen von für nicht-Funktionstypen , dann haben Sie genau primitive Rekursion. $\mathrm{rec}^O_D$ $O$

Wenn alle s ebenfalls nicht funktionsfähig sind, ergibt die übliche Gödel-Codierung des Datentyps beruhigend dieselben primitiven rekursiven Funktionen. $T^j_i$

Es wäre jedoch schön, eine elegantere Beschreibung dieses Prozesses zu haben. Hier kommt Carlos 'Antwort ins Spiel: Diese Datentypen können in der Kategorietheorie eleganter als die anfänglichen Algebren bestimmter Funktoren beschrieben werden, die oft als Polynomfunktoren bezeichnet werden . Der Rekursor ist dann nur (eine Variante) des anfänglichen Morphismus dieser Algebra, der manchmal von Menschen, die versuchen, Dinge zu verwirren , als Katamorphismus bezeichnet wird. Dieser Morphismus existiert durch Konstruktion der Anfangsalgebra.

Ein Paramorphismus ist nur die spezielle Variante, die ich oben beschrieben habe.

Cody
quelle

{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}

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

Ich habe keine elementaren Referenzen auf Anhieb, obwohl ich denke, dass diese Folien eine nette, weiche Einführung geben, und Kapitel 3 von Ralph Mattes ' These geht auf große technische Details ein, obwohl es nicht induktive Typen erster Ordnung zulässt.

Cody

Ich habe kürzlich genau diese Frage gestellt und mehrere Artikel von Interesse gefunden:

Endgültig induktiv präsentierte Logik : (a) definiert eine Logik, die einen allgemeinen Begriff der primitiven Rekursion über jeden Datentyp liefert, der bestimmte Anforderungen erfüllt. (B) beweist, dass diese Logik eine konservative Erweiterung der primitiven rekursiven Arithmetik ist.

Die Komplexität von Schleifenprogrammen : beweist, dass ihre Vorstellung von Schleifenprogrammen den primitiven rekursiven Funktionen entspricht.

Logikprogramme für primitive rekursive Mengen : beweist, dass ihre Klasse von Logikprogrammen primitiven rekursiven Funktionen entspricht.

Eine beweistheoretische Charakterisierung der primitiven rekursiven Mengenfunktionen : beweist, dass alle primitiven rekursiven Funktionen über eine gegebene Menge nur diejenigen sind, die in einer sehr schwachen Mengenlehre definiert werden können.

Stephen Skeirik
quelle

Vielleicht denken Sie an das Konzept eines Paramorphismus ?

Aus der funktionalen Programmierung mit Bananen, Linsen, Umschlägen und Stacheldraht :

$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}$

$b = 1$ $n \oplus m = (n + 1) \times m$

$h$

\begin{aligned} h Null & = b \\ h (Nachteile ein b) & = ein \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
quelle