Лучший язык программирования родом из СССР
Сегодня в среде российских IT-специалистов считается, что в нашей стране Computer Sciense очень плохо развита. Скажем, в качестве примеров хороших языков программирования “From Russia, with Love” многие могут привести только Kotlin и Nemerle.
Но это не так. Я считаю, что лучший язык программирования был придуман в СССР одним из величайших IT-специалистов. Не верите? Давайте разберемся.
РЕФАЛ
Что говорит об этом Wikipedia:
Рефал (акроним от слов «рекурсивных функций алгоритмический») — один из
старейших функциональных языков программирования, ориентированный на
символьные вычисления:
- обработку символьных строк (например, алгебраические выкладки);
- перевод с одного языка (искусственного или естественного) на другой; решение проблем, связанных с искусственным интеллектом.
Соединяет в себе математическую простоту с практической направленностью на написание больших и сложных программ.
Но РЕФАЛ - это не только метаязык, а еще и один из языков так называемого -
метапрограммирования. Все дело в том, что отличительной чертой РЕФАЛА является использование сопоставления с образцом и переписывания термов как основного способа определения функций.
Что это значит на практике? РЕФАЛ - это язык фактически лишенный синтаксиса, но обладающей семантикой. Самым близким родственником из метаязыков является Lisp и Tcl. Оба эти сородича способны дают примерно те же возможности - с помощью использования специальной семантики писать код, который позволит в время компиляции расширять синтаксическую базу языка или реализовывать новую. Развитием идей расширения синтаксиса для решения задачи является подход Dawn Smal Language (DSL) для предметной области, а
эталонной реализацией для него - Racket, потомок Scheme с частичной обратной
совместимостью.
Но, тогда зачем нужен РЕФАЛ, если уже есть такие языки? Все достаточно просто:
- У РЕФАЛ нет типов данных, а значит программист может самостоятельно реализовать свою версию системы типов. Таким образом - РЕФАЛ более гибкий при разработке DSL или полноценных компиляторов.
- В РЕФАЛ применен подход под названием “суперкомпиляция”, обеспечивающий хорошую скорость исполнения. Если очень упрощенно - компилятор РЕФАЛ вычисляет все очевидные варианты алгоритма и дополняет ими полученный машкод. Таким образом, тяжеловесный
не детерменированный алгоритм применяется только для не очевидных сразу вариантов. - У РЕФАЛ очень низкий порог входа. Существенно ниже чем в Lisp family, Smalltalk, Ruby, etc. Синтаксис языка - компактный и простой. Его может освоить даже не IT-специалист.
- У современных реализаций компиляторов РЕФАЛ реализована очень хорошая интеграция с С++, что позволяет легко встраивать готовые решения. Таким образом - расширение функциональности языка становится тривиальной задачей.
А теперь, для закрепления всего, что я описал - давайте напишем реализацию нескольких простых функций. Для наших экспериментов возьмем задачи работы со строками. Но сначала - пара слов о создателе этого языка.
Создатель языка РЕФАЛ
По данным той же Wikipedia:
Валентин Фёдорович Турчин (14 февраля 1931, г. Подольск, Московская область — 7 апреля 2010, Нью-Йорк) — советский и американский физик и кибернетик, создатель языка Рефал и новых направлений в программировании и информатике, участник правозащитного движения в СССР, автор «самиздата», председатель Советской секции «Международной амнистии». С 1977 года работал в Университете Нью-Йорка.
Если говорить емко и коротко - Турчин был одним из виднейших деятелей в IT и развитии понимания кибернетики, формировании ее правил. Его работы и философия оказали огромное влияние на развитие Computer Sciense в целом, а так же на такие более “нишевые” науки как футурология (например, в книге С. Лема “Сумма технологии” хорошо чувствуется влияние философии Турчина и стремление к упрощению систем, взгляд на производственный цикл как на некую метасистему, которая проходит стадии от простого к сложному, удаление всего лишнего и последующему упрощению).
Одним из значимых вкладов Турчина является теория о суперкомпиляции, которая отражена в рефал-машине/рефал-автомате (виртуальная машина для языка РЕФАЛ, описывающая базовую семантику).
Суперкомпиляция (иногда называемая метакомпиляцией), — специальная техника оптимизации алгоритмов, основанная на знании конкретных входных данных алгоритма.
Суперкомпилятор (рефал-автомат) принимает исходный код алгоритма плюс некоторые данные о входных параметрах. Он возвращает новый исходный код, который исполняет свою задачу на этих данных быстрее или является лучше исходного алгоритма по каким-то другим показателям.
Очень часто суперкомпиляцией ошибочно считают глобальную оптимизацию программ, из-за чего технология она очень мало распространена, а сама идея имеет невысокую оценку в профессиональном сообществе.
Иными словами, все как всегда - непризнанный гений, до идей которого еще нужно дорасти.
Примеры имплементации простейших функций на РЕФАЛ
Для того, чтобы показать мощность языка мы реализуем функции работы со строками (как уже говорилось ранее). Выбор пал на них, так как работа со строками - всегда была и будет одной из сложнейших задач для любого языка программирования. И сложностей тут очень много - от представления типа данных “Строка” до обработки таких факторов как кодировка.
Конечно, в рамках статьи мы рассмотрим простейшие реализации предложенных функций. Но их задача все же не полная имплементация, а пример того, как легко на языке РЕФАЛ решаются сложные задачи.
Работа со строками: первый элемент
Чаще всего, в языках программирования, строки являются неким списком
(последовательностью) символов. Отталкиваясь от этого мы можем на языке РЕФАЛ написать такой простой код:
Head {
/* Empty */ = '';
s.Head e.Tail = s.Head;
e.Other = e.Other;
}
Пока не понятно? Давайте разберемся.
Head {} является простым определением функции, где Head - ее имя. Внутри - мы определяем алгоритм вычисления “головы” списка (первого символа строки). На самом деле, у нас есть всего три варианта стратегии:
- Входящий поток оказался пустым. В этом случае мы возвращаем пустую строку (
/* Empty */ = '';). - Входящий поток можно разбить на первый символ (
s.Head) и остальной поток (e.Tail), тогда значение этого символа и будет искомым ответом (s.Head e.Tail = s.Head;). - По каким-то причинам, хоть поток и не пустой, но мы не можем получить из него первого символа. Тогда весь поток и является головой списка ( e.Other = e.Other; ).
Просто? Я бы даже сказал очевидно. Осталось объяснить, что такое s и e в данном коде. В РЕФАЛ переменные делятся на несколько типов - s, e (появился в спецификации РЕФАЛ-2) и t. Они отличаются по смыслу:
- Значением s-переменной (записываются как `s.varname`) или переменной символа может быть любой одиночный символ (symbol).
- E-переменные (записывается как `e.varname`) могут принимать произвольную последовательность термов, т.е. значением e-переменной может быть только выражение с правильной скобочной структурой.
- Значением t-переменных (записываются как `t.varname`) может быть любой одиночный терм — как символ (symbol), так и выражение в скобках.
Используя эти простые правила обработки входящих в функцию параметров мы можем легко организовать сравнение с образцом в рамках декларативного описания функции для сравнения с образцом.
Работа со строками: последний элемент
Напишем реализацию функции, которая позволяет получить последний элемент из списка символов строки:
Tail {
/* Empty */ = '';
s.Head e.Tail = e.Tail;
e.Other = e.Other;
}
Что тут имеем? Просто инвертированное описание функции Head для второго возможного варианта. Все чуть сложнее с получением среза строки.
Работа со строкам: получение срезов
Для начала срез любого списка зависит от точки отсчета начала. Очевидны тут две координаты - начало и конец списка как точка отсчета. Имплементируем получение среза для каждого из них.
Для удаления символов от начала строки реализуем:
RemoveFirst {
/* Empty */ = '';
0 e.String = e.String;
s.Count s.Head e.Tail = <RemoveFirst <Sub s.Count 1> e.Tail>;
e.Other = '';
}
Первая строка - уже понятны по реализации функций Head и Tail . С остальными давайте разберемся:
- Сначала разберем образец с условием s.
Count s.Head e.Tail(третий по счету). В нем мы говорим, что если входящий поток данных имеет некий счетчик (s.Count), имеет голову (s.Head) и хвост (s.Tail), то нужно рекурсивно вызывать функциюRemoveFirst, отнять от счетчика (функцияSub) 1, а в качестве данных для обработки передать хвост (RemoveFirst<Sub s.Count 1> e.Tail>). Через “острые” скобки (<>) в РЕФАЛ обозначается вызов функции. - На второй строке мы говорим, что если в качестве входящего потока мы имеем счетчик равный 0, то любой оставшийся поток - и есть исходные срез (
0 e.String = e.String;).
Аналогичным образом имплементируем удаление с конца:
RemoveLast {
/* Empty */ = '';
0 e.String = e.String;
s.Count e.Head s.Tail = <RemoveFirst <Sub s.Count 1> e.Head>;
e.Other = '';
}
Просто? В целом - да, чуть сложнее отделения “головы” и “хвоста” списка, но сильно проще посимвольного перебора в Pure C.
Остался один случай, который мы не описали - когда мы хотим получить срез не от начала или конца переданного списка символов, а откуда-то из тела. То есть начало отсчета и конца - это индексы обрабатываемой последовательности.
Имея уже реализованные RemoveFirst и RemoveLast имплементация полноценной функции Slice становится тривиальной задачей.
Slice {
/* Empty */ = '';
s.Count e.String = <RemoveFirst s.Count e.String>;
s.From s.To e.String = <RemoveLast s.To <RemoveFirst s.From e.String>>;
e.Other = e.Other;
}
Давайте разберем теперь, что мы тут делаем:
- В первой строке мы говорим, что если у нас поток данных не передан/является пустым, то и срез строки является пустым. Тут все просто.
- Во втором случае мы говорим, что если нам передан только (
s.Count) одно значение (счетчик) и непустой поток (e.String), то мы считаем точкой начала среза - началом списка. Следовательно - результатом выполнения функции является вызовRemoveFirst(s.Count e.String = <RemoveFirst s.Count e.String>;). - В третьем случае мы говорим, что нам передана количество удаляемых символов с начала (
s.From) и конца (s.To) потока, а так же поток данных (e.String). Тогда для получения среза нам сначала надо вызывать функции удаления символов из начала потока (RemoveFirst), а затем из полученного потока удалить символы с конца (RemoveLast). В итоге получаем:s.From s.To e.String = <RemoveLast s.To <RemoveFirst s.From e.String>>;. - И последний вариант. Мы получили просто некий не поток (
e.Other), без каких-то данных по тому, что надо “отрезать” от него. Тогда результатом выполнения функции будет является этим потоком (e.Other = e.Other;).
Таким образом - мы декларативно, в минимальное количество строк уместили описание достаточно сложной функции по получению среза строки.
Работа со строками: склеиваем две строки в одну
Склейка (объединение) строк является типовой операцией. На самом деле РЕФАЛ по умолчанию умеет это делать, но реализуем некий “сахар” для большего удобства:
Concat {
/* Empty */ = '';
e.First e.Second = e.First e.Second;
e.Other = e.Other;
}
Что делает данная программа? У тех, кто дочитал три первых примера вызовет вопрос только вторая строка.
В ней мы говорим о том, что если у нас пришло два потока (e.First e.Second) результатом является поток, который состоит из этих двух потоков.
То есть, РЕФАЛ сам объединит данные строки в одну:e.First e.Second = e.First e.Second;
Работа со строками: сравнение двух строк
Ну и последнее на сегодня - сравним две строки на эквивалентность. Пусть в функции будет учитываться регистр, будем считать строки “Нет” и “нет” - разными. Такое допущение призвано минимизировать исходный код и показать только сам принцип реализации сравнения строк на языке РЕФАЛ. Имплементация будет иметь вид:
Compare {
/* Empty */ = "True";
s.Equal s.Equal = "True";
s.Equal e.SliceOne s.Equal e.SliceTwo = <Compare e.SliceOne e.SliceTwo>;
e.Other = "False";
}
Первая и последняя строка не нуждаются в объяснении. Объясним вторую и третью:
- Во второй строке, мы говорим, что если у нас есть два одинаковых символа (
s.Equal s.Equal), то результатом данной вычисления функции является ИСТИНА (True). - В третьей строке мы говорим, что если у нас есть два потока, каждый из которых можно разбить на символ и поток (
s.Equal e.SliceOne s.Equal e.SliceTwo) и отделенные символы равны, то требуется вызывать функцию Compare для оставшейся части данных двух потоков (<Compare e.SliceOne e.SliceTwo>).
Стоит только дополнить, что в РЕФАЛ принято последовательность символов заключенных в одиночные кавычки ('True') воспринимается
рефал-машиной как множество разделяемых символов (то есть ее можно разделить на ‘T’, ‘r’, ‘u’, ‘e’). А вот строка заключенная в двойные кавычки ("True") является целостной и воспринимается как один символ.
Так же в рефал-машине, так как типов данных не существует может не быть имплементации логического результата (т.е. True или False). Поэтому для его обозначения часто используется символ-строки “True” и “False”, реже - 0 и 1 (как в Pure C).
Печальный итог
Сейчас дела у РЕФАЛ обстоят не совсем хорошо. Иначе бы статья о нем не понадобилась.
После того, как Турчин уехал в США развитием РЕФАЛ он уже фактически не занимался.
Сегодня имплементациями языка и его стандартов заняты различные ВУЗы и наиболее “живой” реализацией компилятора является Рефал-5λ. Все примеры из статьи писались как раз под него.
Данная версия языка РЕФАЛ направлена на практические применение, имеет хорошую интеграцию с С++ и позволяет писать достаточно сложные прикладные программы.
Так же большим плюсом этого компилятора является возможность его собирать под современные UNIX-like системы, что расширяет возможности применения полученных программ.
Минусы? Они очевидны - скудная стандартная библиотека и отсутствие привычных “батареек” и удобств.
Но это - вопрос решаемый. Ведь каждый может начать реализовывать
части экосистемы. Сам по себе РЕФАЛ - язык очень простой, с очень низким порогов вхождения. А это значит, что развитие экосистемы Рефал-5λ вполне позволит ему применяться не только в исследовательских целях (обратный инжиниринг, разработка компиляторов и интерпретаторов) или для узких задач (парсинг данных, экспертные системы), но и для набивших оскомину - написание GUI приложений, CLI утилит, backend’a для web-приложений и так далее.