Один мой друг, историк по профессии, подкинул мне замечательную идею об использовании древней мнемонической и счетной систем в современной криптографии. В процессе его рассказов об узелковой письменности Инков, я начал соображать, что все новое — хорошо забытое старое и было бы не плохо как-то применить древний опыт в современном мире. Первое, что пришло в голову — криптография. Это самое очевидное — просто сконвертировать узлы с ниток в байты и шифр готов. С одной стороны все казалось понятным, но потом я вспомнил про криптостойкость и другие параметры шифров и понял, что не обладаю достаточным опытом и знаниями в области криптографии, чтобы в одиночку разработать новый шифр.
Дальше я решил попытаться представить некий эзотерический язык программирования, конструкции которого могут быть записаны с помощью узелковой письменности Кипу. Поначалу казалось, что это невозможно: я придумывал язык и пытался написать на нем программу вычисления факториала. Первые три черновика спецификаций ушли в урну: языки никуда не годились. Они выглядели как полагалось для эзотерических языков, но не помогали мне решать поставленную задачу, т.к. не были полными по Тьюрингу. Энтузиазм потихоньку угасал и эта задача казалась мне не по-плечу. Собравшись с силами, я решил, что если смогу написать программу вычисления факториала — то язык работает.
Четвертая версия языка оказалось удачной: я написал факториал, затем генерацию последовательности Фибоначи и дюжину простых примерчиков аля “сумма чисел от 0 до 99”. Язык получился что надо: необычный, крайне эзотерический, с простой и понятной идеей. Главное — язык может решить любую (ну или почти любую) задачу которую можно выразить в виде вычислимой функции.
Инки и Кипу
(Абзац из Википедии)
Ки́пу — древняя мнемоническая и счётная система Инков, своеобразная письменность: представляет собой сложные верёвочные сплетения и узелки, изготовленные из шерсти южноамериканских верблюдовых (альпаки и ламы) либо из хлопка. В кипу может быть от нескольких свисающих нитей до 2000. Она использовалась для передачи сообщений посыльными часки по специально проложенным имперским дорогам, а также в самых разных аспектах общественной жизни (в качестве календаря, топографической системы, для фиксации налогов и законов, и др.).
В кипу использовалась десятичная система счисления и преимущественно на них записывались числа с помощью трех видов узлов. Первые изображали десятки, вторые — группу единиц (2-9) и третий узел обозначал единицу. Таким образом, группа узлов интерпретировалась как число, в котором на месте тысяч, сотен, десяток и единиц были навязаны соответствующие узлы.
Положим что запись “7d” — обозначает последовательность из 7 узлов обозначающих десятки. “5i” — группу единичных улов из 5 штук и “I” — единицу, а “x” — как пропуск. Тогда число 703 можно представить следующей последовательностью узлов: “7dx3i”, число 2013 — 2dx1d3i и и т.д.
Эти идеи и легли в основу языка Quipu за некоторыми изменениями.
Спецификации языка
Программа на Quipu представляет собой матрицу узелков (knots), каждый столбец которой образует нить (thread). Количество нитей ограничено числом 26, по количеству символов в латинском алфавите (на самом деле их 52, но об этом позже). Количество узелков на нити не ограничено. Каждая нить должна быть отделена от соседних как минимум одним пробелом и быть выравненной на фиксированное количество отступов от начала файла на всем ее протяжении. Иными словами нить в виде “лесенки”, а не столбца сложно назвать валидной.
Quipu может оперировать двумя типами данных — целыми числами и строками.
Программа исполняется по нитям (сначала первая нить, потом вторая и т.д) сверху в низ. На каждом шаге исполнения вычисляется значение текущего узелка. Исполнение продолжается до тех пор, пока не будет вычислено значение последнего узелка последней нити или не встретится узелок останов. “::”.
Узелки можно разделить на два типа — простые и составные. Простые состоят из одной ячейки матрицы (пара символов в строке, например “$a”). Составные узелки представляют собой последовательность простых узелков в нити. Составные узелки используются для представления чисел и строк. Например строку “Habr” на языке Quipu можно записать так:
‘H ‘a ‘b ‘r А число 2013 так:
2# 1@ 3& Каждая нить может быть обозначена символьной меткой. Если меток нет — все нити нумеруются по-порядку метками “a” — “z”. Кроме того, каждая нить имеет свое значение, которое равно значению последнего в ней узелка. Обращаться к значению нити можно с помощью специального узелка — “$a” (значение нити “a”). Значение каждой нити записывается в ее нулевой узелок, что позволяет использовать его как неявный аргумент в выражениях.
Нить имеет две составляющие — основную и инициализирующую. Например “a:” — инициализирующая составляющая нити “а”, “а.” — основная. Нить может представляться как двумя составляющими, так и каждой в отдельности. В последовательном исполнении программы используются только основные нити. Инициализирующие нити исполняются единожды при первом явном или неявном обращении к значению нити. Под явным подразумевается исполнение узелка “$a”, под неявным — использование верхнего нулевого узелка нити в выражениях. Если у нити нет инициализирующей составляющей, то ее начальное значение равно нулю.
Некоторые узлы не имею своего собственного значения, поэтому их значение вычисляется как значение ближайшего значащего узелка перед ними (если таких нет — то значению нити, которое является нулевым узелком). Примерами таких узелков служат узелки вывода и условных переходов.
Таблицу узелков (n — текущий узел нити)
| Узелок | Значение |
|---|---|
| $a | Значение нити «а». |
| >> | Ввод значения с терминала. |
| << | Вывод значения (n-1) узла в терминал. |
| 1#4%5@1& | Число 1451: "#" — тысячи, "%" — сотни, "@" — десятки, "&" — единицы. |
| — | Разница между (n — 2) и (n — 1) узелками. |
| ++ | Сумма (n — 2) и (n — 1) узелков. |
| ** | Произведение узелка (n — 2) и узелка (n — 1). |
| // | Целочисленное деление узелка (n — 2) на узелок (n — 1). |
| %% | Остаток от деления нацело узелка (n — 2) на узелок (n — 1). |
| <c | Условный переход на нить “с”, если значение предыдущего узла меньше нуля. |
| >c | Условный переход на нить «c», если значение предыдущего узла больше нуля. |
| =с | Условный переход на нить «с», если значение предыдущего узла равно нулю. |
| ? с | Безусловный переход на нить “с”. |
| :: | Останов. |
| ‘ | Символ. |
| \n | Спец символ. |
Примеры программ
Hello World!
a: a. 'H << 'e 'l 'l 'o ' 'W 'o 'r 'l 'd '! \n Сумма чисел от 0 до 99
s. i. c. e. $i 1& $i $s ++ ++ 1% << -- =e ?s Факториал
a: a. b: b. e. >> $a 1& $a $b =e 1& << 1& ++ -- $b =e ** ?a Фибоначи
s. f. d. a: b: a. b. x: i. t. o. e. $x $x ', 1& 1& $b $f >> 1& 1& 1& '. =e 2& ' ?i ++ << << << 1& -- << ?f ', ?e -- $i $f ' =o -- << ?o 1& =e -- $a =t $b 1& ++ << ', ' << 1& << Реализация
Довольно давно меня преследует мысль о том, что пора бы изучить новый язык, для расширения кругозора так-сказать. Выбор пал на Scala. Меня всегда привлекала ее так называемая “чрезмерная сложность” о которой все говорят. Написав пару простых примеров аля “Hello World”, я возомнив себя прожженным скалистом, взялся за реализацию интерпретатора Quipu. Задача оказалась сложнее, чем я думал, не смотря на то, что в самом начале дал себе установку — сделать, что бы просто работало, не зацикливаясь на красоте дизайна и реализации.
В итоге, рабочий прототип я получил за полтора дня. Получил, действительно то, что хотел. Этакий proof-of-concept идеи. Кода написал довольно немного и выглядит он слегка пугающим особенно для людей имеющих опыт разработки на Scala. Однако, я считаю, что начало положено. Путь “идея -> реализация” пройден минимальными усилиями и следующие шаги могут быть направлены на улучшение текущей реализации. Я даже не исключаю возможности, что придется все переписывать с нуля, но все-же надеюсь, что разумное зерно в первоначальном коде есть и его может спасти масштабный рефакторинг.
В текущей реализации также есть пара незначительных проблем, которые я решил пока не фиксить, в свете перспективы “все переписывания с нуля”. Тем не менее проблемы эти больших неудобств не доставляют а даже наоборот приучают Quipu программистов правильно оформлять свои программы. Ниже приведен список текущих недочетов:
1) Каждая нить должна иметь метку. Нити без меток не поддерживаются.
2) Программа должна заканчиваться пустой строкой, иначе — узлы, находящиеся на последней строке не будут синтерпретированы.
Итак. Исходные коды интерпретатора доступны на GitHub: github.com/vkostyukov/quipu. Я буду очень рад pull-request’ам с исправлениями моего кодобреда. Кроме того, буду признателен за новые примеры использования языка, которые я обязательно размещу на странице проекта. Еще обещаю стилизованную футболку с надписью “%username%, the first Quipu hacker.” тому, кто напишет программу 99-bottles-of-beer на Quipu. Шутка 🙂
Зачем?
Есть убеждение, что придумывая новый язык программирования, автор практически обрекает себя на неудачу. С этим я полностью согласен и считаю, что на ближайшие 3-5 лет ресурс по языкам программирования у человечества есть. Сейчас уже сложно придумать, что-то новое, полезное и отличное от известных всем кофейных гигантов. Но это пожалуй справедливо для языков “больших” и “серьезных”, которые пытаются решить все мыслимые и немыслимые проблемы с которыми якобы сталкивается разработчик.
Эзотерические же языки решают другие проблемы — проблемы разминки мозгов, нездорового любопытства и самобичевания самообразования. Для таких случаев уже придумано и реализовано 1000+ языков, грамматика которых помещается на стандартный желтый стикер. Quipu — один из таких языков. Языков, которые помогают нам программистам, по-новому взглянуть на известные проблемы и получить новые ощущения и опыт от их решения тем самым развивая в нас ту самую способность “мыслить нестандартно”.
ссылка на оригинал статьи http://habrahabr.ru/post/165661/
Добавить комментарий