Интерпретатор частично рекурсивных функций (Дмитрий Астраханцев, OSEDUCONF-2024) — различия между версиями

;{{SpeakerInfo}}: {{Speaker|Дмитрий Астраханцев}}
<blockquote>
В работе предлагается язык, основанный на концепции использования частично 
рекурсивных функций, описан его синтаксис и реализация его интерпретатора. 

Данный язык предлагается использовать для включения в курсы по программированию 
и расширения понятия Тьюринг полноты, знакомства с основами функционального 
подхода к программированию.
</blockquote>

{{VideoSection}}

{{vimeoembed|993361569|800|450}}
{{youtubelink|}}
|U64LYG3Rxq4}}
{{SlidesSection}}
[[File:Интерпретатор частично рекурсивных функций (Дмитрий Астраханцев, OSEDUCONF-2024).pdf|left|page=-|300px]]

{{----}}

== Thesis ==

* https://github.com/Dugit0/GRF_emulator

Введем базовые понятия и определения<ref name="algo_and_rec_func"><i>Мальцев&nbsp;А.&nbsp;И.</i> Алгоритмы и рекурсивные функции. 2-е изд. М. : Наука. Гл. ред. физ.-мат. лит., 1986. 368&nbsp;с.</ref><ref name="rec_func"><i>Петер&nbsp;Р.</i> Рекурсивные функции // Под ред. и с пред. Колмогорова&nbsp;А.&nbsp;Н. М. : Издательство иностранной литературы, 1954. 264&nbsp;с.</ref>.

Классом частично рекурсивных функций называется класс функций, которые могут быть получены 
путём применения трёх операций (суперпозиции, примитивной рекурсии и минимизации) к трём 
базовым функциям (функции тождественного нуля, функции следования и функции выбора).

Базовыми рекурсивными функциями называются функции:

* Тождественный ноль: <m>o(x) = 0</m>
* Функция следования: <m>s(x) = x + 1</m>
* Функции выбора: <m>I^n_m(x_1, …, x_n) = x_m</m> (<m>n, m \in \mathbb{Z}, 0 < m \le n</m>)


Операции над функциями называются:

;Суперпозиция: (<m>g = \mathbf S^{n+1}(f, f_1, …, f_n)</m>): <latex>g(x_1, …, x_m) = f(f_1(x_1, …, x_m), …, f_n(x_1, …, x_m))</latex>
;Примитивная рекурсия: (<m>f = \mathbf R(g, h)</m>): 
<latex>
f(x_1, …, x_n, 0) = g(x_1, …, x_n)
        
f(x_1, …, x_n, y + 1) = h(x_1, …, x_n, y, f(x_1, …, x_n, y))
</latex>
;Минимизация: (<m>g = \mu(f)</m>): <latex>g(x_1, …, x_n) = \min\{y : f(x_1, …, x_{n}, y) = 0\}</latex>


Основным достоинством класса частично рекурсивных функций является тот факт, что он совпадает с классом 
вычислимых по Тьюрингу функций. Другими словами, множество всех частично рекурсивных функций совпадает 
со множеством всех функций, которые могут быть реализованы машиной Тьюринга<ref name="mathlog_and_algo_theory"><i>Верещагин&nbsp;Н.&nbsp;К., Шень&nbsp;А.</i> Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. 4-е изд., исправленное. М. : МЦНМО, 2012. 160&nbsp;c.</ref>.

Таким образом, изучение частично рекурсивных функций может быть использовано для демонстрации студентам 
первых курсов высших учебных заведений основных принципов функционального программирования без необходимости 
изучать для этого
какой-либо функциональный язык. Однако для этого необходимо наличие программного обеспечения, которое могло 
бы вычислять функции, записанные с помощью базовых функций и операций над ними.

Целью данной работы ставилось предоставление такого программного обеспечения. Очевидно, что оно должно 
включать в себя язык, который был бы основан на частично рекурсивных функциях и только на них, его 
интерпретатор, графический интерфейс и средство отладки.

В ходе данной работы был разработан именно такой язык и средства работы с ним.
Язык включает в себя

* Базовые функции
** Функция тождественного нуля, обозначаемая <tt>o</tt>.
** Функция следования, обозначаемая <tt>s</tt>.
** Функция выбора, обозначаемая <tt>I\^{</tt><n>_{}<m>}. Например, <tt>I\^{</tt>5_3}.
** Функции констант, которые были введены для удобства работы, обозначаются <tt><const>\^{</tt><n>}, где <tt>const</tt>  —  это значение константы, а <tt>n</tt>  —  количество аргументов данной функции. Например, <tt>12\^{</tt>3} обозначает функцию <m>f(x_1, x_2, x_3) \equiv 12</m>.
* Операции
** Операция суперпозиции, обозначаемая <tt>F\{G, H, K\</tt>}.
** Операция примитивной рекурсии, обозначаемая <tt>F <- G</tt>.
** Операция минимизации, обозначаемая <tt>?F</tt>.

Графический интерфейс:
[[File:osseduconf-2024-astrachan-astrahancev-astrakhantsev_gui.png|center|640px|thumb|]]

Получившийся язык носит декларативный характер, и эту особенность было решено подчеркнуть, 
полностью отделив вызов функций от их определения. Для этого вызов функций был перенесён 
в отдельное окно графического интерфейса. 

Таким образом, графический интерфейс приобретает 
деление на 3 области: определения функций, вызова функций и вывода результатов, ошибок 
и отладочной информации.


{{----}}
[[File:{{#setmainimage:Интерпретатор частично рекурсивных функций (Дмитрий Астраханцев, OSEDUCONF-2024)!.jpg}}|center|640px]]
{{LinksSection}}
<!-- <blockquote>[©]</blockquote> -->

<references/>

[[Категория:OSEDUCONF-2024]]
[[Категория:Draft]]
[[Категория:СПО в образовании]]