Эмулятор частично рекурсивных функций

(пример реализации, заброшенный и без исходников)

NEWПроект Дмитрия Астраханцева

Rationale

Курс «Алгоритмы и алгоритмические языки» (самый первый семестр обучения на ВМК!) начинается не с описания какого-либо языка программирования, а с изучения алгоритмически полных формализмов — Машины Тьюринга и Нормальных алгорифмов Маркова (ещё там проходят БНФ, но это другая история). Цель этого раздела — расшатать принесённые из школы представления о то, что такое «алгоритм» и «программирование». Школьные представления мало того, что обычно нечёткие, они ещё почти наверняка основаны как каких-то частных вариантах процедурного ЯП (неважно, это Python, Scratch, Basic или КуМир), то есть сильно уже академического понимания алгоритма. Очень хочется добавить в этот список частично рекурсивные функции: это классический алгоритмически полный формализм, близкий функциональной парадигме, изначально основанный на математическом аппарате (в отличие от Машины Тьюринга, которую проще понимать на модели, а математический аппарат к ней как раз довольно сложный/неочевидный).

Проблематика

Не хватает прикладной составляющей. Для МТ и НАМ написано уже достаточно работающих реализаций, в том числе работающих прямо в браузере (см., например, тут и тут; за компанию посоветую ещё и Railroad diagram generator, онлайн демо тут). Работающий в командной строке простой эмулятор НАМ занимает 16 строк на Python, эмулятор МТ — примерно 50 строк. А вот эмулятор ЧРФ мне известен только один, причём это EXE-шник под WidnowsXP, и след его в интернетах потерян, не говоря уж об исходниках (однако сохранилась документация). Между тем простой эмулятор ЧРФ представляется не более сложным, чем той же МТ.

Базовая задача

Разработать синтаксис языка ЧРФ (кажется, в примере выше он слишком «формален») и модель ввода-вывода (в примере вместо ввода — непосредственное значение в тексте программы); написать простой интерпретатор, которому на вход подаётся программа на этом языке и входные данные, после чего выводится результат

Возможные исследования

Можно исследовать как саму модель, так и особенности реализации

• Автоматическое определение арности функции (вообще-то она не нужна) (см. несколько кринжовый проект синтаксиса)

• Ограничения алгоритмической полноты данной модели. Может оказаться, что модель принципиально не соответствует теоретическому базису — привести контрпример. Или же она ему соответствует — доказать, что ограничения алгоритмической полноты только ресурсные

• Эффективность реализации операторов примитивной рекурсии и минимизации. Вроде бы и то, и то — линия, но (1) нельзя ли оптимизировать? и (2) а относительно чего линейна минимизация?

• Оптимизация наиболее одиозных проблем, например, кубической сложности операции вычитания, без расширения синтаксиса (зачем изобретать новый Лисп?)
• Оценка вычислительной сложности алгоритмов. Перенос методик оценки вычислительной сложности из императивной или функциональной парадигм.
• Расширение синтаксиса — арифметические выражения, условные операторы (примитивная рекурсия уровня 1), строки…

Возможные программные доработки

Интерфейс, предметная облать и юзабилити

1. Оформление в виде отдельного модуля, с прицелом на включение в другие приложения
   • В том числе написание высокоэффективной библиотеки на Си
2. Реализация логики на объектах другой предметной области (например, packet processing)
3. Отладчик: пошаговый проход и трассировка, мониторинг значений
4. GUI (условно в стиле из примера)