Интерпретатор частично рекурсивных функций (Дмитрий Астраханцев, OSEDUCONF-2024) — различия между версиями
Материал из 0x1.tv
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
(не показаны 2 промежуточные версии этого же участника) | |||
;{{SpeakerInfo}}: {{Speaker|Дмитрий Астраханцев}} <blockquote> В работе предлагается язык, основанный на концепции использования частично рекурсивных функций, описан его синтаксис и реализация его интерпретатора. Данный язык предлагается использовать для включения в курсы по программированию и расширения понятия Тьюринг полноты, знакомства с основами функционального подхода к программированию. </blockquote> {{VideoSection}} {{vimeoembed|993361569|800|450}} {{youtubelink|}} |U64LYG3Rxq4}} {{SlidesSection}} [[File:Интерпретатор частично рекурсивных функций (Дмитрий Астраханцев, OSEDUCONF-2024).pdf|left|page=-|300px]] {{----}} == Thesis == какой-либо функциональный язык. Однако для этого необходимо наличие программного обеспечения, которое могло бы вычислять функции, записанные с помощью базовых функций и операций над ними. Целью данной работы ставилось предоставление такого программного обеспечения. Очевидно, что оно должно включать в себя язык, который был бы основан на частично рекурсивных функциях и только на них, его интерпретатор, графический интерфейс и средство отладки. В ходе данной работы был разработан именно такой язык и средства работы с ним. Язык включает в себя # * Базовые функции ** \begin{enumerate} # Функция тождественного нуля, обозначаемая <tt>o</tt>. # ** Функция следования, обозначаемая <tt>s</tt>. # ** Функция выбора, обозначаемая <tt>I\^{</tt><n>_{}<m>}. Например,\\ <tt>I\^{</tt>5_3}. ** \item Функции констант, которые были введены для удобства работы, обозначаются <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>. * \item Операции ** # Операция суперпозиции, обозначаемая <tt>F\{G, H, K\</tt>}. # ** Операция примитивной рекурсии, обозначаемая <tt>F <- G</tt>. # ** Операция минимизации, обозначаемая <tt>?F</tt>. \end{enumerate} Графический интерфейс: [[File:osseduconf-2024-astrachan-astrahancev-astrakhantsev_gui.png|center|640px|thumb|]] Получившийся язык носит декларативный характер, и эту особенность было решено подчеркнуть, полностью отделив вызов функций от их определения. Для этого вызов функций был перенесён в отдельное окно графического интерфейса. Таким образом, графический интерфейс приобретает деление на 3 области: определения функций, вызова функций и вывода результатов, ошибок и отладочной информации. |
Текущая версия на 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.