(495) 925-0049, ITShop интернет-магазин 229-0436, Учебный Центр 925-0049
  Главная страница Карта сайта Контакты
Поиск
Вход
Регистрация
Рассылки сайта
 
 
 
 
 

Quipu - эзотерический язык программирования на основе узелковой письменности Инков (исходники)

Источник: habrahabr
spiff

Один мой друг, историк по профессии, подкинул мне замечательную идею об использовании древней мнемонической и счетной систем в современной криптографии. В процессе его рассказов об узелковой письменности Инков, я начал соображать, что все новое - хорошо забытое старое и было бы не плохо как-то применить древний опыт в современном мире. Первое, что пришло в голову - криптография. Это самое очевидное - просто сконвертировать узлы с ниток в байты и шифр готов. С одной стороны все казалось понятным, но потом я вспомнил про криптостойкость и другие параметры шифров и понял, что не обладаю достаточным опытом и знаниями в области криптографии, чтобы в одиночку разработать новый шифр. 

Дальше я решил попытаться представить некий эзотерический язык программирования, конструкции которого могут быть записаны с помощью узелковой письменности Кипу. Поначалу казалось, что это невозможно: я придумывал язык и пытался написать на нем программу вычисления факториала. Первые три черновика спецификаций ушли в урну: языки никуда не годились. Они выглядели как полагалось для эзотерических языков, но не помогали мне решать поставленную задачу, т.к. не были полными по Тьюрингу. Энтузиазм потихоньку угасал и эта задача казалась мне не по-плечу. Собравшись с силами, я решил, что если смогу написать программу вычисления факториала - то язык работает. 

Четвертая версия языка оказалось удачной: я написал факториал, затем генерацию последовательности Фибоначи и дюжину простых примерчиков аля "сумма чисел от 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 - один из таких языков. Языков, которые помогают нам программистам, по-новому взглянуть на известные проблемы и получить новые ощущения и опыт от их решения тем самым развивая в нас ту самую способность "мыслить нестандартно".

Ссылки по теме


 Распечатать »
 Правила публикации »
  Написать редактору 
 Рекомендовать » Дата публикации: 15.01.2013 
 

Магазин программного обеспечения   WWW.ITSHOP.RU
Microsoft Office 365 Персональный 32-bit/x64. 1 ПК/MAC + 1 Планшет + 1 Телефон. Все языки. Подписка на 1 год.
Zend Server with Z-Ray Developer Edition - Standard
JIRA Software Commercial (Cloud) Standard 10 Users
YourKit Profiler for .NET - Floating License - 1 year of e-mail support and upgrades
SAP Crystal Server 2011 WIN INTL 5 CAL License
 
Другие предложения...
 
Курсы обучения   WWW.ITSHOP.RU
 
Другие предложения...
 
Магазин сертификационных экзаменов   WWW.ITSHOP.RU
 
Другие предложения...
 
3D Принтеры | 3D Печать   WWW.ITSHOP.RU
 
Другие предложения...
 
Новости по теме
 
Рассылки Subscribe.ru
Информационные технологии: CASE, RAD, ERP, OLAP
Безопасность компьютерных сетей и защита информации
Новости ITShop.ru - ПО, книги, документация, курсы обучения
OS Linux для начинающих. Новости + статьи + обзоры + ссылки
Новые материалы
Работа в Windows и новости компании Microsoft
ЕRP-Форум. Творческие дискуссии о системах автоматизации
 
Статьи по теме
 
Новинки каталога Download
 
Исходники
 
Документация
 
 



    
rambler's top100 Rambler's Top100