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

Ссылки сюда (1) →

Короткая ссылка: 20240629Q

Докладчик

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

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

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

Презентация

Thesis

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

Введем базовые понятия и определения.

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

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

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

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

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

():

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

():

Минимизация

():

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

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

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

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

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

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

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

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