Интерпретатор частично рекурсивных функций (Дмитрий Астраханцев, OSEDUCONF-2024) — различия между версиями
Материал из 0x1.tv
StasFomin (обсуждение | вклад) (Новая страница: «;{{SpeakerInfo}}: {{Speaker|Дмитрий Астраханцев}} <blockquote> </blockquote> {{VideoSection}} {{vimeoembed||800|450}} {{youtubelink|}} {{Slid…») |
StasFomin (обсуждение | вклад) |
||
(не показаны 3 промежуточные версии этого же участника) | |||
;{{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>Мальцев А. И.</i> Алгоритмы и рекурсивные функции. 2-е изд. М. : Наука. Гл. ред. физ.-мат. лит., 1986. 368 с.</ref><ref name="rec_func"><i>Петер Р.</i> Рекурсивные функции // Под ред. и с пред. Колмогорова А. Н. М. : Издательство иностранной литературы, 1954. 264 с.</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>Верещагин Н. К., Шень А.</i> Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. 4-е изд., исправленное. М. : МЦНМО, 2012. 160 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]] [[Категория:СПО в образовании]] |
Текущая версия на 12:32, 7 августа 2024
- Докладчик
- Дмитрий Астраханцев
В работе предлагается язык, основанный на концепции использования частично рекурсивных функций, описан его синтаксис и реализация его интерпретатора.
Данный язык предлагается использовать для включения в курсы по программированию и расширения понятия Тьюринг полноты, знакомства с основами функционального подхода к программированию.
Содержание
Видео
Презентация
Thesis
Введем базовые понятия и определения[1][2].
Классом частично рекурсивных функций называется класс функций, которые могут быть получены путём применения трёх операций (суперпозиции, примитивной рекурсии и минимизации) к трём базовым функциям (функции тождественного нуля, функции следования и функции выбора).
Базовыми рекурсивными функциями называются функции:
- Тождественный ноль:
- Функция следования:
- Функции выбора: ()
Операции над функциями называются:
- Суперпозиция
- ():
- Примитивная рекурсия
- ():
- Минимизация
- ():
Основным достоинством класса частично рекурсивных функций является тот факт, что он совпадает с классом
вычислимых по Тьюрингу функций. Другими словами, множество всех частично рекурсивных функций совпадает
со множеством всех функций, которые могут быть реализованы машиной Тьюринга[3].
Таким образом, изучение частично рекурсивных функций может быть использовано для демонстрации студентам первых курсов высших учебных заведений основных принципов функционального программирования без необходимости изучать для этого какой-либо функциональный язык. Однако для этого необходимо наличие программного обеспечения, которое могло бы вычислять функции, записанные с помощью базовых функций и операций над ними.
Целью данной работы ставилось предоставление такого программного обеспечения. Очевидно, что оно должно включать в себя язык, который был бы основан на частично рекурсивных функциях и только на них, его интерпретатор, графический интерфейс и средство отладки.
В ходе данной работы был разработан именно такой язык и средства работы с ним. Язык включает в себя
- Базовые функции
- Функция тождественного нуля, обозначаемая o.
- Функция следования, обозначаемая s.
- Функция выбора, обозначаемая I\^{<n>_{}.
- Операции
- Операция суперпозиции, обозначаемая F\{G, H, K\}.
- Операция примитивной рекурсии, обозначаемая F <- G.
- Операция минимизации, обозначаемая ?F.
Графический интерфейс:
Получившийся язык носит декларативный характер, и эту особенность было решено подчеркнуть, полностью отделив вызов функций от их определения. Для этого вызов функций был перенесён в отдельное окно графического интерфейса.
Таким образом, графический интерфейс приобретает деление на 3 области: определения функций, вызова функций и вывода результатов, ошибок и отладочной информации.
Примечания и ссылки
- ↑ Мальцев А. И. Алгоритмы и рекурсивные функции. 2-е изд. М. : Наука. Гл. ред. физ.-мат. лит., 1986. 368 с.
- ↑ Петер Р. Рекурсивные функции // Под ред. и с пред. Колмогорова А. Н. М. : Издательство иностранной литературы, 1954. 264 с.
- ↑ Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. 4-е изд., исправленное. М. : МЦНМО, 2012. 160 c.