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

;{{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

Докладчик

Дмитрий Астраханцев

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

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

Видео

on youtube

Презентация

Thesis

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

Введем базовые понятия и определения^[1][2].

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

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

• Тождественный ноль:
• Функция следования:
• Функции выбора: ()

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

Суперпозиция

():

Примитивная рекурсия

():

Минимизация

():

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

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

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

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

• Базовые функции
  • Функция тождественного нуля, обозначаемая o.
  • Функция следования, обозначаемая s.
  • Функция выбора, обозначаемая I\^{<n>_{}.
• Операции
  • Операция суперпозиции, обозначаемая F\{G, H, K\}.
  • Операция примитивной рекурсии, обозначаемая F <- G.
  • Операция минимизации, обозначаемая ?F.

Графический интерфейс:

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

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

Примечания и ссылки

1. ↑ Мальцев А. И. Алгоритмы и рекурсивные функции. 2-е изд. М. : Наука. Гл. ред. физ.-мат. лит., 1986. 368 с.
2. ↑ Петер Р. Рекурсивные функции // Под ред. и с пред. Колмогорова А. Н. М. : Издательство иностранной литературы, 1954. 264 с.
3. ↑ Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. 4-е изд., исправленное. М. : МЦНМО, 2012. 160 c.