Нормальные алгоритмы Маркова как основание языка программирования

В этой статье хотелось бы поделиться мыслями о применении Нормальных Алгоритмов Маркова (далее по тексту: НАМ) в качестве основания для языка программирования.

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

К истории вопроса

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

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

Первой, и самой очевидной для нас сейчас, формализацией алгоритма была машина Тьюринга (а также её собратья: машина Поста и машина Минского). Машина представляла собой устройство, последовательно читающее ленту с командами и выполняющее их. Всё просто и понятно: алгоритм в данном случае являлся последовательностью шагов, которые приводят к какому-либо результату.

Иной, «более математический» вариант предложил Алонзо Чёрч: разработанная им теория лямбда-исчисления представляла алгоритм как совокупность аппликации — применения функции к аргументу и абстракции — создания новой функции.

Наконец, третью составляющую важность для нас теорию предложил советский математик Андрей Андреевич Марков. Нормальный алгоритм, введённый Марковым состоял из трёх частей:

1. Алфавита, с которым работает алгоритм.

2. Правил подстановки.

3. Начального состояния.

Алфавит представляет собой множество символов которые алгоритм будет распознавать. К алфавиту применяются правила подстановки. Правила подстановки есть правила вида: A → B, означающее, что всякое A мы заменяем на B. Для наглядности рассмотрим пример:

Алфавит = A, B, C
Правила = A → B,
          B → CC,
          C → ø
Исходное состояние = ABC

Шаг 0. ABC
Шаг 1. BBC
Шаг 2. CCBC
Шаг 3. øCBC
Шаг 4. øøBC
Шаг 5. øøCCC
Шаг 6. øøøCC
Шаг 7. øøøøC
Шаг 8. øøøøø

В кратце, именно в этом и состоит суть НАМ.

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

Не унывать! — отвечу я, ­— переходим ближе к делу.

Итак, мы имеем три основных формализации алгоритмов — в основу каких парадигм и языков программирования они легли? Машина Тьюринга стала базой для императивного программирования, в лоне лямбда-исчисления сформировался функциональный подход. Что же с НАМ? А они стали основой для продукционной парадигмы, о которой ни то, что статьи в Википедии, но и в обозримой части Интернета материалов нет (соглашусь, если Вы скажете, что есть, но они очень низкого качества). Да, из всё той же Википедии вы узнаете, что нормальные алгоритмы воплотились в языке РЕФАЛ, но я спешу сообщить следующее: (1) к сожалению, он не обрёл должной популярности, не смог распространить идеи продукционного программирования среди широких масс, (2) концепт языка, который я хотел представить сильно отличается от РЕФАЛа, (3) кроме нормальных алгоритмов РЕФАЛ содержит множество других средств, моей же задачей было исследовать язык содержащий только НАМ. (Про Thue и MarkovJunior я молчу, позже вы поймёте, почему).

Перейдём же теперь от теории к практике.

LN — язык, основанный на нормальных алгоритмах

LN (Language of Normal Markov algorithms, знаю, сокращение необычное) — это язык, основанный на НАМ, который навязывает их так же, как C — императивный подход, а Haskell — доску, мел и учебник по теории категорий.

В отличие от других «Марковских» ЯП — Thue и MarkovJunior, LN работает не с отдельными символами, а со словами и последовательностями, то бишь, в нём возможно создать правило типа python → shit, c_coding → Segmentation fault, best language → lisp или maybe vim? → no, emacs better.

Словом будем называть любую совокупность символов, ограниченную пробелами, последовательностью — слова ограниченные специальными словами [ и ]. Таким образом JS — слово, JS is evil — 3 разных слова, [ JS is evil ] — последовательность слов.

Основу языка составляет единственное ключевое слово: rule, посредством которого создаются новые правила подстановки, имеет оно следующий синтаксис:

rule .word .word (выполняем подстановку типа слово → слово)
rule .word .seq (выполняем подстановку типа слово → последовательность)
rule .seq .word (выполняем подстановку типа последовательность → слово)
rule .seq .seq (выполняем подставноку типа последовательность → последовательность)

Учитывая это, приведённые выше холиварные примеры можно переписать так:

rule python shit
rule c_coding [ Segmentation fault ]
rule [ Best language ] Lisp
rule [ maybe vim? ] [ no, Emacs better ]

Теперь, имея правила, неплохо было бы их применять. Условимся всё, что не является вызовом ключевого слова, считать исходным состоянием. Тогда нашу одиозную программу выше можно дополнить так:

python
c_coding
[ Best language ] [ maybe vim? ]

После ряда подстановок мы получим следующий код:

shit
[ Segmentation fault ]
Lisp no, emacs better

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

Важно отметить тот факт, что представленный выше результат работы программы весьма условен: на самом деле сначала интерпретатор прочтёт слово python, обнаружит, что для него существует правило, выполнит подстановку и придёт к ошибке.

Создание простейших программ

Как можно использовать такой необычный язык программирования? Ну, например, он может решать задачи по готовым формулам, т.е. выполнять роль мощного калькулятора. Приведём пример:

Задача. Воде, массой 5 кг и теплоёмкостью 4200 Дж/кг×°C, сообщили теплоту. В результате её температура изменилась на 20°C. Какую теплоту сообщили воде? Теплообменом с сосудом и окружающей средой пренебречь.

Для решения этой задачи достаточно написать простейшую программу:

rule Q [ * C m dT ]
rule C 4200
rule m 5
rule dT 20

print Q

Из приведённого выше примера можно сделать следующие выводы:

1. В языке используется префиксная нотация для записи выражений.

2. Функция print реализует вывод на экран.

3. Программа написана в декларативном стиле, т.е. мы лишь описали саму задачу, решение же её возложено на компьютер.

Кроме того, такой язык «из коробки» может решать системы уравнений методом подстановки, достаточно лишь задать саму систему и выразить одну из переменных.

Ну а что же с реальными задачами? — спросит неутомимый практик, — Уравнения решать и энергию расчитывать это одно, а скажем ветвления, циклы? Как их реализовать в таком ЯП?

Создаём управляющие конструкции: начало

Ну что же, давайте смотреть. Начнём с ветвлений. Для начала добавим в язык новое ключевое слово — atom, оно сообщит интерпретатору, что, то или иное слово атомарно, пытаться вычислять его не нужно. Зная это, можно реализовать ветвление следующим образом:

atom simple-if
rule [ simple-if 1 ] [ print "True" ]
rule [ simple-if 0 ] [ print "False" ]

[ simple-if some-condition ]

some-condition в данном случае, это некоторое условие, результатом которого становится 1 — истина, и 0 — ложь. Так же можно заметить, что каждый раз, когда требуется ввести условие, потребуется вводить два правила (при условии, что атом simple-if уже введён, ибо его можно использовать повторно). Исправить это можно, но мы сделаем это чуть позже, сейчас же заострим внимание на другой детали: зачем нам simple-if?

Сначала может показаться что это вещь совсем ненужная, результат работы твердолобого теоретика, который спит и видит, как бы ввести новую бесполезную абстракцию, насолить бравым программистам. На самом же деле simple-if выполняет очень важную роль: он позволяет отделить выражения ветвлений от всего остального, это в некотором смысле маяк, увидев который интерпретатор понимает, что перед не очередное баловство программиста, а самое обыкновенное ветвление. Впредь такие, с виду бесполезные атомы, мы и будем называть маяками.

Переходим к циклам. Здесь, уже набившего оскомину инструментария atom и rule будет не достаточно, нам потребуются некоторые абстракции — введём их. Пусть слово .word обозначает любое корректное слово, а .seq — любую корректную последовательность. Внимательный читатель подметит мою забывчивость, и действительно, мы уже встречались с этими word и seq, однако тогда, я так и не дал им объяснения, да и использовал в другом контексте. Условимся .word и .seq называть заполнителями. Теперь с их помощью мы можем реализовать цикл while:

atom simple-while
rule [ simple-while 1 .seq ]
     [ simple-while
	     cond [ some data ]
	     print "Hello, world" ]

[ simple-while
  cond
  print "Hello, world!" ]

Как видно, заполнитель .seq в данном случае мы используем, чтобы сократить первую часть правила.

С виду может показаться, что наш язык совершенно не пригоден для использования на практике. И действительно, представленные реализации if и while крайне ограничены и просты. Однако, позже мы дополним их, сделаем их мощь сопоставимой с таковой в императивных ЯП. Сейчас же отойдём в сторону, поговорим о переменных и функциях.

Переменные и функции

Что же, перейдём к... переменным? Сначала значит, мы рассуждаем о циклах и ветвлениях, а тут вдруг о переменных вспомнили. Странно, не правда ли? В свою защиту могу сказать, что переменные в LN вещь более сложная, чем простейшие управляющие конструкции. Почему? — Спросите вы. Потому что их нет! — Отвечу я.

Действительно, при детальном рассмотрении окажется, что реализовать переменные при помощи rule нельзя. Наоборот, переменные в LN, в том смысле, в котором они есть например в C, не существуют. В языках императивных переменная — как мы помним из детского сада — это некоторая именованная область памяти, контейнер куда мы можем что-то положить. В LN же, мы можем лишь создать правило, согласно которому the-best-coder будет заменяться на "you, my dear ❤️". Да, это будет похоже на переменные, но ими являться не будет. Не возможны потому и указатели.

С точки зрения типов наш язык будет очень близок к Common Lisp — переменные, которых нет, типов иметь не будут, типизированы будут данные. Как и CL, концептуальный язык обладает сильной динамической типизацией. Судить о том, хорошо это или плохо не берусь, ибо совсем не являюсь экспертом в данной теме. Сами основные типы таковы:

• seq — последовательности (например: [ a b c ])

• word — слова (например: peace)

• numeric — необычный тип, описывающий «что-то числовое» (необязательно число), представляет собой слово, состоящее из числовых символов — цифр, . (точки), / (косой черты, деления), - (минуса), : (двоеточия), | (вертикальной черты), e (сокращение для 10^). Данный тип позволяет описывать как числа, так и различные совокупности чисел: коды, номера, даты, время и т.п. Пример: 7, 3.14, 2/3, 12.45.6, --34/56.89:1||15.

• complex — комплексные числа (например: 89|12)

• rational — рациональные числа (например: 6.626e-34)

• integer — целые числа (например: 9)

• fraction — обыкновенные дроби (например: 8/9)

• symbolic — тип, сходный numeric, описывает «что-то символьное».

• character — UTF-8 символ

• string — UTF-8 строка

Представленные типы имеют следующую иерархию:

seq
└── word
    ├── numeric
    │   └── complex
    │       ├── rational
    │       │   └── integer
    │       └── fraction
    └── symbolic
        ├── character
        └── string

Теперь, введём для наших типов пару простых правил:

1. Типы, находящиеся в иерархии на одном уровне будем называть равноправными. Например, numeric и symbolic — равноправны, rational и fraction — равноправны, complex и character ­— равноправны, а вот string и rational уже не равноправны.

2. Равноправные типы не заменяемы. Это означает, что в следующее правило: rule [ + .integer .integer ] ... передать character или string нельзя.

3. Типы, могут иметь подтипы, т.е. такие типы, которые находятся в иерархии на более низком уровне. Например, word — подтип seq, numeric — подтип word, complex — подтип numeric.

4. Типы заменяемы подтипами, но не наоборот. Другими словами, типу numeric можно передать значение любого его подтипа: complex, rational, integer, fraction — это не вызовет ошибок. Например, в следующее правило: rule [ example .word .word ] ... можно передать не только слова, но и любые числа, символы и строки.

Всем типам соответствуют заполнители, имена которых, это имя типа с точкой в начале (типу seq соответствует .seq, word — .word и т.д.).

Учитывая природу переменных в LN (а природа их исходит из rule), они будут глобальными и независящими от контекста создания: объявите переменную хоть в глобальной области видимости, хоть в теле функции — она будет видна везде.

А будут ли переменные, которых нет, переменными? Что с иммутабельностью? Чёткого ответа у меня нет. Вполне допустима как переписываемость правил:

rule best-poet Homer
rule best-poet John-Milton
print best-poet
(John-Milton)

так и константность их:

rule best-poet Homer
rule best-poet John-Milton
(ошибка)

На данный момент моё мнение состоит в следующем: правила должны быть мутабельны, обратное сделает язык менее гибким.

Хорошо, с переменными мы разобрались, перейдём к функциям.

Здесь читатель догадливо заметит, что и их нет в таком ЯП, и он окажется прав. Функций в LN нет, есть лишь правила, используемые в качестве таковых, несмотря на это, далее по тексту, слово «функция» будет повсеместно использоваться, сделано так для большей простоты и лёгкости материала.

Однако, для введения функций нам нужны параметры, а текущая версия rule позволяет определить лишь подстановки без параметризации. Что же, давайте изменим это. Условимся следующую запись заполнителя: .placeholder:name называть именованным заполнителем, где placeholder — тип заполнителя (.seq, .word и др.), а name — имя заполнителя. Учитывая это мы можем написать две классические функции — сумму аргументов, и приветствие:

rule [ sum .rational:a .rational:b ]
     [ + a b ]

rule [ greeting .string:name ]
     [ print [ "Hello, " name "!" ] ]

[ sum 6 9 ] → 15
[ greeting "Sasha" ] → "Hello, Sasha!"

В последний раз обратим своё внимание на типизацию. Ранее было сказано, что она динамическая и сильная, однако, не вооружённым глазом видно, что в объявлении «функции» чётко заданы типы аргументов. Поэтому, правильнее наверное будет сказать, что наш язык имеет типизацию близкую к динамической сильной.

Не трудно заметить, что в силу своей природы «функции» могут использовать собственный синтаксис. Например, математические операции в LN работают в префиксной форме, но это легко исправить (другой вопрос надо ли, ибо префикс совершенней инфикса, как мне кажется):

rule [ .rational:a my+ .rational:b ]
     [ + a b ]

[ 4 my+ 5 ] → 9

В этом примере мы пользуемся тем фактом, что функции ­— это правила, а потому, порядок следования элементов правила мы можем задать любой. Здесь, однако, следует сделать оговорку: правила не должны выглядеть одинаково, создание двух одинаковых правил означает создание одного, которое мы просто переписываем (или вообще получаем ошибку, если правила иммутабельны).

Так же правила могут порождать другие правила (или, если вам будет понятнее: «функции» могут порождать «функции»). Такие правила (функции) мы будем называть конструкторами. Например, ниже представлен простейший конструктор — синтаксический сахар для «переменных».

rule [ var .word:name .word:value ]
     [ rule name value ]

var pastille "very tasty stuff"

Заметьте, что здесь мы используем 4-е правило типизации: «функция» определена для двух слов, но мы спокойно можем передавать и строки и числа, а вот передача последовательности в качестве аргумента вызовет ошибку.

Создаём управляющие конструкции: продолжение

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

Начнём с ветвлений. Используя именованные заполнители, мы можем написать следующее:

atom if

rule [ if 1 .seq:true-body .seq:false-body ]
     true-body

rule [ if 0 .seq:true-body .seq:false-body ]
     false-body

[ if [ - 1 0 ]
     [ print "- 1 0 == 1" ]
     [ print "- 1 0 == 0" ] ] → [ print "- 1 0 == 1" ] → "- 1 0 == 1"
     
[ if [ - 1 1 ]
     [ print "- 1 1 == 1" ]
     [ print "- 1 1 == 0" ] ] → [ print "- 1 1 == 0" ] → "- 1 1 == 0"

С виду, этот код может показаться лёгким и понятным. Однако, эта простота обманчива, и потому советую вам сделать попытку самостоятельно решить поставленную задачу.

Поясняя же работу этой реализации ветвлений скажу, что устроены они так: мы определили маяк if. Далее задали два правила, пока не обращайте на них внимания. Далее написали 2 ветвления. Как они будут вычисляться? if является атомом, он будет пропущен, а вот выражение стоящее за ним будет вычислено и заменено своим результатом — нулём или единицей. Тут-то правила и выходят на сцену: последовательность if 1 .seq будет заменена на код if-ветки, соответственно if 0 .seq — на else-ветку.

Здесь некоторые вспомнят известную шутку про троллейбус из буханки хлеба и спросят: зачем вообще нужен ЯП на котором простые, базовые конструкции реализуются так сложно, в котором программист, будто человек эпохи первобытности, должен всё делать сам, бегать за мамонтом ногами, а не послать за ним робота. На этот сложный, и действительно важный вопрос я отвечу позже. Сейчас же вернёмся к делу.

И так, нашей задачей было улучшить цикл while, как же это сделать? Прежде всего, надо указать, что в языке, построенном на НАМ, цикл (а равно и рекурсия, ибо ни того, ни другого в чистом виде в нашем ЯП нет) есть правило, которое вычисляется в само себя с некоторыми отличиями (или без них). Легко понять, что под каждый цикл придётся писать отдельное правило, это не удобно, потому, как и в прошлый раз воспользуемся конструктором.

atom while

rule [ while .seq:cond .seq:body ]
     [ rule [ while 1 .seq ]
            [ while cond body ] ]

[ while [ some-condition ] [ print "Hi" ] ]

Устроен этот листинг достаточно просто: конструктор создаёт правило, согласно которому, истина условия в цикле порождает этот же цикл.

Зачем? Кому?

Этими вопросами любой здравомыслящий читатель задумался при прочтении статьи уже не единожды, пришло время ответить на них.

Для начала повторяя себя скажу, что изначально никакой практической цели перед ЯП не ставилось, а потому вопрос "Зачем?" не очень уместен. Однако, спрашивающий прав в некоторой степени, ибо любая технология имеет какое-то применение и цель. Зачем же может понадобиться LN? Приведу список своих мыслей по этому поводу:

1. LN интересен с точки зрения фундаментальной информатики. С одной стороны, он сочетает в себе простоту и минимализм возможностей и синтаксиса, а с другой — чрезвычайную мощь и выразительность. Может в будущем продукционное программирование приобретёт популярность, а LN будет известен как один из языков, где данная парадигма получила своё воплощение.

2. Обработка текстов и данных. Вы возможно заметили, что весь LN построен на идее анализа последовательностей. Это свойство можно применять и для обработки текстов (например для расстановки знаков препинания) где имеет место некоторая шаблонность и структурируемость. То же самое и с данными, хотя честно скажу, с Data Science я не знаком, и моя оценка может быть неверна.

3. LN так же может применяться для автоматического решения математических, физических и логических задач различного типа. Достаточно лишь задать условия и начальное состояние — далее система будет действовать сама.

В завершение этого скромного раздела скажу одно: пока судить о том, где такой ЯП можно применять сложно. Сейчас мы имеем лишь формальное описание, фантазию скрупулёзного теоретика, В перспективе, когда я таки сделаю интерпретатор (есть у меня таковое намерение) можно будет говорить более конкретно.

Заключение

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

Не относитесь к представленному слишком строго или снисходительно, это лишь скромное исследование не претендующие на оригинальность или новизну. Я лишь хотел исследовать ещё одну грань информатики.

Исследуйте новые технологии, учите новые языки, и конечно, «Sapere aude»! До встречи, читатель.

Спасибо моему другу Александру, без него этой статьи не было бы.

Полезные ссылки

Нормальные алгоритмы Маркова: Википедия
Язык программирования РЕФАЛ: Википедия, Содружество РЕФАЛ/Суперкомпиляция
Язык программирования Thue: Википедия, Github
Язык программирования MarkovJunior: Github