Mendefinisikan fungsi rekursif primitif atas tipe data umum

Fungsi rekursif primitif didefinisikan lebih dari bilangan asli. Namun, sepertinya konsep tersebut harus digeneralisasi ke tipe data lain, memungkinkan seseorang untuk berbicara tentang fungsi rekursif primitif yang memetakan daftar ke pohon biner, misalnya. Dengan analogi, fungsi rekursif parsial dari bilangan asli menggeneralisasi dengan baik ke fungsi yang dapat dihitung pada tipe data apa pun, dan saya ingin memahami cara membuat generalisasi yang sama untuk fungsi rekursif primitif.

Secara intuitif, jika saya harus mendefinisikan bahasa imperatif sederhana yang memungkinkan operasi dasar, katakan daftar (seperti penggabungan, mengambil kepala dan ekor, perbandingan elemen) dan bentuk iterasi yang membutuhkan mengetahui sebelumnya berapa banyak iterasi akan terjadi ( seperti iterasi atas elemen-elemen dalam daftar tidak berubah), maka bahasa seperti itu paling banyak harus dapat menghitung fungsi rekursif primitif atas daftar. Tetapi bagaimana saya bisa memahami ini secara formal, dan lebih khusus lagi, bagaimana saya bisa membuktikan bahwa bahasa saya menghitung semua fungsi rekursif primitif dari daftar dan bukan hanya sebagian dari mereka?

Untuk lebih jelasnya, saya tertarik untuk memahami fungsi rekursif primitif sebagai kelas fungsi yang terdefinisi dengan baik (jika memang benar), daripada hanya dalam operasi rekursi primitif itu sendiri, yang tampaknya mudah. Saya akan tertarik pada petunjuk apa pun yang telah ditulis tentang rekursi primitif atas struktur data umum, atau memang dalam konteks apa pun selain bilangan asli.

Pembaruan: Saya mungkin telah menemukan jawaban, dalam makalah yang disebut Walther Recursion , oleh McAllester dan Arkoudas. (Prosiding CADE 1996 ). Ini sepertinya berisi versi umum dari rekursi primitif serta rekursi Walther yang lebih kuat. Saya berniat untuk menulis jawaban sendiri setelah saya mencerna ini, tetapi sementara itu catatan ini mungkin bisa membantu orang lain dengan pertanyaan yang sama.

computability Nathaniel
sumber

Bagi saya tidak jelas apa yang sebenarnya Anda cari. Sepertinya Anda hanya berusaha menemukan tipe-W , tetapi mungkin bukan itu.

Andrej Bauer

Mungkin berguna untuk mencatat bahwa tipe data "biasa" (seperti pohon) dapat dikodekan dengan cara yang sangat mudah menjadi bilangan asli, dan kemudian fungsi PR di atas natural adalah representasi yang cukup bagus dari apa yang mungkin Anda inginkan. Sebagai alternatif, Anda dapat menggunakan System T dari Gödel yang diperluas ke tipe data orde pertama yang benar-benar positif dengan receptor "biasa".

cody

Anda dapat membatasi jenis output dari eliminator menjadi tipe dasar jika Anda ingin menghilangkan "fitur" ini.

cody

Menurut saya, bentuk tipe-W terbatas adalah yang Anda cari. Sesuatu seperti tipe-W dengan percabangan terbatas dan reseptor terbatas untuk menghilangkan tipe-tipe W terbatas lainnya.

Andrej Bauer

Konferensi CADE 1996 mengunjungi di sini: dblp.org/db/conf/cade/cade96

John Fisher

Jawaban:

Secara umum, dalam bahasa dengan tipe data (seperti daftar, pohon, dll.) Mudah untuk menggambarkan bahasa fungsi yang berperilaku persis seperti yang kita harapkan terjadi perulangan primitif.

Sebagai contoh jika datatype adalah , dan konstruktor memiliki jenis $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$

maka recursor untuk tipe output akan memiliki tipe $\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$

dan semantik operasionalnya adalah:

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

untuk setiap . $i$

Sesuatu yang penuh mulut! Setidaknya untuk bilangan asli, kita memang mendapatkan

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

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

dan

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

seperti yang diharapkan (perhatikan bahwa konstruktor nol tidak memiliki argumen!).

$\mathrm{rec}^O_D$ $O$

$T^j_i$

Akan menyenangkan untuk memiliki deskripsi yang lebih elegan dari proses ini. Itulah jawaban Carlos yang masuk: tipe data ini dapat digambarkan secara lebih elegan dalam teori kategori sebagai aljabar awal fungsi -fungsi tertentu, sering disebut fungsi-fungsi polinomial . Kemudian, kursor hanyalah (varian dari) morfisme awal aljabar ini, kadang-kadang disebut catamorfisme oleh orang-orang yang mencoba membingungkan berbagai hal. Morfisme ini ada melalui konstruksi aljabar awal.

Sebuah paramorphism hanyalah varian tertentu saya jelaskan di atas.

cody
sumber

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

Saya tidak punya referensi dasar begitu saja, meskipun saya kira slide ini memberikan pengantar lembut yang bagus, dan bab 3 dari tesis Ralph Mattes masuk ke detail teknis yang sangat besar, meskipun memungkinkan jenis induktif non "first order".

cody

Saya baru-baru ini mengajukan pertanyaan ini, dan saya menemukan beberapa artikel yang menarik:

Logika Presentatif Induktif : (a) mendefinisikan logika yang memberikan gagasan generik tentang rekursi primitif atas semua tipe data yang memenuhi persyaratan tertentu (b) membuktikan logika ini adalah perpanjangan konservatif aritmatika rekursif primitif.

Kompleksitas Program Loop : membuktikan gagasan mereka tentang program loop setara dengan fungsi rekursif primitif.

Program Logika untuk Set Rekursif Primitif : membuktikan kelas program logika mereka setara dengan fungsi rekursif primitif.

Karakterisasi bukti-teoretis dari fungsi himpunan rekursif primitif : membuktikan semua fungsi rekursif primitif pada himpunan tertentu hanyalah yang dapat didefinisikan dalam himpunan teori yang sangat lemah.

Stephen Skeirik
sumber

Mungkin Anda sedang memikirkan konsep paramorphism ?

Dari Pemrograman Fungsional dengan Pisang, Lensa, Amplop dan Kawat Berduri :

$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 nol & = b \\ h (kontra Sebuah b) & = Sebuah \oplus (b, h b) \end{aligned}

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

pengguna76284
sumber