Definiowanie prymitywnych funkcji rekurencyjnych w stosunku do ogólnych typów danych

Pierwotne funkcje rekurencyjne są zdefiniowane ponad liczbami naturalnymi. Wydaje się jednak, że koncepcja powinna uogólnić na inne typy danych, pozwalając mówić o prymitywnych funkcjach rekurencyjnych, które mapują listy na przykład na drzewa binarne. Przez analogię częściowe funkcje rekurencyjne nad liczbami naturalnymi ładnie uogólniają się na funkcje obliczeniowe na dowolnym typie danych i chciałbym zrozumieć, jak zrobić ten sam rodzaj uogólnienia dla pierwotnych funkcji rekurencyjnych.

Intuicyjnie, gdybym miał zdefiniować prosty imperatywny język, który pozwalałby na podstawowe operacje, powiedzmy listy (takie jak konkatenacja, wzięcie głowy i ogona, porównanie elementów) oraz formę iteracji, która wymaga wcześniejszej wiedzy o liczbie iteracji ( takich jak iteracja elementów na niezmiennej liście), wówczas taki język powinien co najwyżej być w stanie obliczyć pierwotne funkcje rekurencyjne na listach. Ale w jaki sposób mogę to zrozumieć formalnie, a dokładniej, jak miałbym udowadniać, że mój język oblicza wszystkie prymitywne funkcje rekurencyjne na listach, a nie tylko ich podzbiór?

Dla jasności interesuje mnie raczej rozumienie pierwotnych funkcji rekurencyjnych jako dobrze zdefiniowanej klasy funkcji (jeśli rzeczywiście są), a nie tylko działanie samej pierwotnej funkcji rekurencyjnej, co wydaje się proste. Byłbym zainteresowany wskazówkami do wszystkiego, co napisano o prymitywnej rekurencji w stosunku do ogólnych struktur danych, a nawet w jakimkolwiek kontekście innym niż liczby naturalne.

aktualizacja: Być może znalazłem odpowiedź w artykule zatytułowanym Walther Recursion autorstwa McAllestera i Arkoudasa. (Postępowanie z CADE 1996. ) Wydaje się, że zawiera uogólnioną wersję prymitywnej rekurencji, a także silniejszą rekurencję Walthera. Zamierzam napisać odpowiedź na pytanie, kiedy to przeczytam, ale w międzyczasie ta notka może być pomocna dla innych z tym samym pytaniem.

computability Nataniel
źródło

Nie jest dla mnie jasne, czego dokładnie szukasz. Wygląda na to, że próbujesz po prostu znaleźć typy W , ale to nie koniec.

Andrej Bauer,

Prawdopodobnie warto zauważyć, że „zwykłe” (drzewiaste) typy danych mogą być dość prosto zakodowane w liczbach naturalnych, a następnie funkcje PR na naturach są całkiem dobrą reprezentacją tego, czego możesz chcieć. Alternatywnie można użyć rozszerzonego systemu T firmy Gödel o ściśle dodatnie typy danych pierwszego rzędu z „zwykłymi” rekursorami.

cody

Możesz ograniczyć typy wyjściowe eliminatorów do typów podstawowych, jeśli chcesz wyeliminować tę „funkcję”.

cody

Nadal wydaje mi się, że szukasz formy ograniczonego typu W. Coś podobnego do typu W ze skończonym rozgałęzieniem i rekursorów ogranicza się do eliminacji do innych ograniczonych typów W.

Andrej Bauer,

Konferencja CADE 1996 odwiedź tutaj: dblp.org/db/conf/cade/cade96

John Fisher

Odpowiedzi:

Zasadniczo w języku z typami danych (takimi jak listy, drzewa itp.) Łatwo jest opisać język funkcji, które zachowują się dokładnie tak, jak oczekujemy pierwotnej rekurencji.

Na przykład, jeśli typem danych jest $D$ i konstruktorów $c_1,\ldots, c_n$ mieć typ

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$

następnie rekursor $\mathrm{rec}_D^O$ dla typu wyjściowego $O$ będzie miał typ

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

a semantyka operacyjna będzie:

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

dla każdego $i$ .

Coś pełnego ust! Przynajmniej otrzymujemy liczby naturalne

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

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

zgodnie z oczekiwaniami (zauważ, że konstruktor zerowy ma zero argumentów!).

Jeśli teraz pozwolimy na stałe funkcje i prognozy, i pozwolimy na dowolne użycie $\mathrm{rec}^O_D$ dla typów niefunkcyjnych $O$ , to masz dokładnie prymitywną rekurencję.

Krzepiące, jeśli wszystkie $T^j_i$ s są również niefunkcjonalne, wówczas zwykłe kodowanie typu danych według Gödla daje te same prymitywne funkcje rekurencyjne.

Byłoby miło mieć bardziej elegancki opis tego procesu. Oto odpowiedź Carlosa: te typy danych można bardziej elegancko opisać w teorii kategorii jako początkowe algebry niektórych funktorów, często nazywane funktorami wielomianowymi . Rekursor jest wtedy (wariantem) początkowym morfizmem tej algebry, czasem nazywanym katamorfizmem przez ludzi próbujących coś pomylić. Ten morfizm istnieje dzięki konstrukcji początkowej algebry.

Paramorphism to tylko szczególny wariant opisałem powyżej.

cody
źródło

Obawiam się, że to trochę poza mną. Dlaczego mieliśmy nadzieję

{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$ jako podpis typu? Czy to automatycznie oznacza, że reprezentuje pierwotną rekurencyjność? (Trudno mi wyobrazić sobie, jak można to odczytać tylko z rodzaju funkcji.) Znam teorię typów do tego stopnia, że mogę programować w Haskell, ale nie znam formalizmu, który ty. ponownie używam tutaj. Gdzie mogę przeczytać wystarczającą ilość tła, aby zrozumieć, co napisałeś?

Nathaniel,

Typ

{r e c}_{N}

$\mathrm{rec}_{\mathbb{N}}$ wynika z bardziej ogólnego schematu powyżej. Reprezentuje pierwotną rekurencyjność, ponieważ semantyka operacyjna reprezentuje operację rekurencyjną z definicji funkcji PR. Nie wyjaśniłem jednak semantyki operacyjnej, więc rozwinę swój komentarz.

cody

Nie mam pod ręką żadnych elementarnych odniesień, choć wydaje mi się, że te slajdy dają przyjemne miękkie wprowadzenie, a rozdział 3 tezy Ralpha Mattesa zawiera bardzo szczegółowe szczegóły techniczne, chociaż dopuszcza typy indukcyjne nie „pierwszego rzędu”.

cody

Niedawno zadałem to pytanie i znalazłem kilka interesujących artykułów:

Finitary Indukcyjnie przedstawiona logika : (a) definiuje logikę, która zapewnia ogólne pojęcie prymitywnej rekurencji na dowolnym typie danych spełniającym określone wymagania (b) dowodzi, że logika ta jest konserwatywnym rozszerzeniem prymitywnej arytmetyki rekurencyjnej.

Złożoność programów pętli : dowodzi, że ich pojęcie programu pętli jest równoważne prymitywnym funkcjom rekurencyjnym.

Programy logiczne dla pierwotnych zestawów rekurencyjnych : dowodzi, że ich klasa programów logicznych jest równoważna z pierwotnymi funkcjami rekurencyjnymi.

Teoretyczna charakterystyka pierwotnych funkcji zbioru rekurencyjnego : dowodzi, że wszystkie pierwotne funkcje rekurencyjne w danym zbiorze są tylko tymi, które można zdefiniować w bardzo słabej teorii zbiorów.

Stephen Skeirik
źródło

Być może myślisz o koncepcji paramorfizmu ?

Z programowania funkcjonalnego z bananami, soczewkami, kopertami i drutem kolczastym :

Dla liczb naturalnych paramorfizm jest funkcją $h = (b, \oplus)$ formularza

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

Na przykład funkcja silnia ma $b = 1$ i $n \oplus m = (n + 1) \times m$ .

W przypadku list funkcją byłby paramorfizm $h$ formularza

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

użytkownik76284
źródło