Проект синтаксиса

Исходный синтаксис более или менее нормальный, хотя некоторые конструкции в нём тяжеловаты. Нижеследующее — мои попытки «облегчить» и расширить запись функций; я отдаю себе отчёт в некоторой вкусовщине.

• Обозначения:

  • «n» и «m»— число, «ⁿ» и «ₙ» — числа, записанные в нижнем или верхнем индексе

• Алфавит:

  • Идентификатор: буквы, цифры, символ «_» + опционально цифры верхних и нижних индексов («₀₁₂₃₄₅₆₇₈₉⁰¹²³⁴⁵⁶⁷⁸⁹»

  • Число в верхнем индексе указывает арность функции; ⁿ может быть записано как `n, например ¹² ≡ `12

• Область определения — целые неотрицательный числа с отношением строгого порядка
• Базовые функции

  1. Ноль. 0(x) ↝ 0

     • Возвращает 0 при любом значении параметра

     • Многоместный ноль (возвращает 0 при любых значениях параметров): 0ⁿ(x₁,…,xₙ) ↝ 0(x₁,…,xₙ) ↝ 0; моделируется как суперпозиция 0(1ⁿ)(x₁,…,xₙ)

     • Нуль-местный ноль 0⁰() ↝ 0 (или просто 0 без скобок), моделируется как минимизация одноместного нуля, ?(0¹)

  2. Следование. ⇒(x) ↝ x + 1; допускается форма +(x)

     • Возвращает следующий по порядку за x элемент области определения

     • Например, ⇒(7) ↝ 8

  3. Проекция. mⁿ(x₁,…,xₙ) ↝ m(x₁,…,xₙ) ↝ xₘ

     • Возвращает m-й операнд

     • Например, 3⁵(9,8,7,6,5) ↝ 3(9,8,7,6,5) ↝ 7

• Операторы (в порядке убывания приоритета при разборе выражения)

  1. Суперпозиция. gᵐ(fⁿ₁, …, fⁿₘ)(x₁, …, xₙ) ↝ g(f₁(x₁, …, xₙ), …, fₘ(x₁, …, xₙ))

     • На заданных x₁, …, xₙ вычисляется m значений fⁿᵢ(), затем вычисляется gᵐ() от этих значений

  2. Минимализация. ?ⁿ(fⁿ⁺¹)(x₁, …, xₙ) ↝ ?f(x₁, …, xₙ) ↝ k: f(x₁, …, xₙ, k)=0 min(k ∈ 0…∞)

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

     • (fⁿ⁻¹@gⁿ⁺¹)(x₁, …, xₙ₋₁, у) ↝ f@g(x₁, …, xₙ₋₁, у) ↝

       • f(x₁, …, xₙ₋₁) | y = 0

       • g(x₁, …, xₙ₋₁, у - 1, f@g(x₁, …, xₙ₋₁, у - 1) | y > 0

     • Возвращает:

       • Если последний операнд равен 0, вычисляется базис рекурсии f()

       • Если последний операнд больше нуля:

         1. Заново вызывается рекурсивная функция, но с последним параметром, уменьшенным на 1

         2. Результат, вместе с исходными параметрами и последним параметром, уменьшенным на 1, обрабатывается функцией g()

     • Для каждого набора xᵢ возвращает минимально возможное k, на котором f(x₁, …, xₙ, k)=0

• Задание функции: функция → комбинация базовых функций и операторов

  • Вместо «→» можно использовать «->»

Примеры

• Функция, возвращающая n - 1 на натуральном n, и 0 на 0:

  • Одной строкой

      decr → 0⁰@1²

  • …с автоматическим определением арности:

      decr -> 0@1

• Сложение и умножение:
  • Полный вариант

    next3 → +(3³)
    add → 1¹@next3
    add3 → add(1³, 3³)
    mult → 0¹@add3

  • Короче (с автоматическим определением арности):

    add → 1@+(3)
    mult -> 0@add(1, 3)

  • Одной строкой:

    mult -> 0@(1@+(3))(1, 3)

TODO пример минимизации