М.Двач / Программирование

856 Кб, 919x1070
Примитивная рекурсия 26 июля, 22:58 3506448 В конец треда | Веб

Анон, как бы выглядел ЯП, в котором возможны только примитивно-рекурсивные функции?

Проимущества такого языка очевидны - мы можем доказать, что программа всегда завершится (ибо любая программа на таком языка терминальна), а функции которые нельзя выразить в таком языке всё равно находятся в области кукаретики (не имеют отношения к real world программированию). Все так или иначе используют map, fold, filter и другие примитивно-рекурсивные комбинаторы.

И так анон, как бы он выглядел? Какой бы у него был синтаксис?

Ответы7886

2 26 июля, 23:08 2 3506458

Лямбда-исчисление Чёрча?

Ответы6493

3 26 июля, 23:36 3 3506493

>>3506458
Лямбда-исчисление позволяет выражать и общерекурсивные функции в том числе (Y-комбинатор). Речь идёт о языке, который допускает примитивную рекурсию, но не допускает общую.

То есть функция вида `f(x) = f(x+1)` не возможна в таком языке, но можно описать функции map, (+), factorial и другие примитивно-рекурсивные функции.

4 27 июля, 13:52 4 3506736

5 28 июля, 18:58 5 3507886

>>3506448 (OP)
Я не настоящий сварщик, но miniagda с sized types не попадает попадает в класс primitive recursion? https://www.cse.chalmers.se/~abela/miniagda/

1 Кб, 50x43
6 28 июля, 19:07 6 3507893

P.S. Вот тут
https://www21.in.tum.de/~traytel/papers/fscd16-coind_lang/paper.pdf пишут, что примитивная рекурсия является синонимом структурной. Хз, правда или нет, если да, то в тогда практически любой proof assistant является таким языком. Coq и его клоны построены на структурной рекурсии. Капча намекает, лол.

7 28 июля, 21:22 7 3507979

Да хуйня эта ваша примитивная рекурсия, и ФП это говно. Аниме, кстати, тоже кал, не смотри его, лучше баб еби.

Обновить тред

« /pr/В начало тредаВеб-версияНастройки

/a//b//mu//s//vg/Все доски

Скачать тред только с превьюс превью и прикрепленными файлами

Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах.Подробнее

Пользуетесь скринридером — пишите, что можно улучшить.
Host-Food.ru — надёжный хостинг от 12 руб/мес | Free DNS
Зеркала М.Двача: m2ch.hk, m2ch.gq, m2ch.cf, m2ch.fapp.in, m2ch.lib, m2chfapiswfw2wcakptqp4o6ltgchvjuxfab7urxlduraomtlnhw5xad.onion