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

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

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

    Четвертая версия языка оказалось удачной: я написал факториал, затем генерацию последовательности Фибоначи и дюжину простых примерчиков аля “сумма чисел от 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 — один из таких языков. Языков, которые помогают нам программистам, по-новому взглянуть на известные проблемы и получить новые ощущения и опыт от их решения тем самым развивая в нас ту самую способность “мыслить нестандартно”.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 40

      +24
      Этот язык видимо внебрачный сын Brainfuck'а.
        +3
        Как бы не случайно, на совести автора Brainfuck MediaWiki Extension
          +2
          Есть такой грешок :)

          Но на самом деле я честно вижу мало аналогии с Brainfuck. Разве что одна — это тоже эзотерический язык.
            +4
            Надо будет написать интерпретатор Quipu на Brainfuck-е.
              +3
              Не думаю, что любому адекватному человеку это под силу :)
        +5
        Не совсем понял, как вы переходите от узелков на нитях к символам в матрице, но сочту это недостатком моего нынешнего состояния, уверен, завтра текст будет выглядеть для меня иным. Но очень здорово видеть такие примеры пытливости человеческой мысли, с удовольствием читал рассуждения до и после.

        Меня зацепило сильно, что я узнал узел на рисунке. В википедии что то другое нарисовано, но узел на рисунке очень похож на шкотовый узел (как мне его называли), главная штука которого, что это простой обычный узел, самый простой, который повторен много раз в правильном порядке. Я его знаю от отца, он яхтсмен, узел применяется обычно за счет его свойства не затягиваться, это, мне кажется, главное качество всех узлов. Когда кладешь много шлагов такого узла, если он крепит шкот к парусу, или веревку к якорю, когда все время есть натяжение, то этот узел потом легко развязать.

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

        Узел кажется совсем древним, и такую конструкцию, как на рисунке, очень легко развязывать, и менять, мне вот так кажется, что они на самом деле могли быстро вязать узлы, манипулировать ими и использовать как счеты.
          +2
          >… моего нынешнего состояния, уверен, завтра текст будет выглядеть для меня иным…
          Все еще под впечатлениями Алтая :-D
          0
          Сначала подумал, что $a вызывает повторное рекурсивное вычисление нити — получилась ерунда. Потом, кажется, разобрался. Интересная идея, поиграем.
            0
            "$a" — это вроде переменной с ленивой инициализацией. О рекурсии я думал. Это и был один из первых трех черновиков. Идея с ленивой инициализацией меня спасла :)
            –1
            Вот это да. Знать эзотерический язык программирования — это не круто. Круто — это придумать свой интересный, нетривиальный, и, естественно, полный по Тьюрингу язык! Браво!
              –1
              эзотерический_яп !=! полный_по_Т_яп
                0
                Язык не выглядит Тьюринг-полным. Программа имеет конечное число ячеек памяти и конечное число значений «счетчика команд» — вряд ли это позволит реализовать любой алгоритм. Единственная лазейка это целые числа неограниченной разрядности, на которых, теоретически, можно реализовать сколь угодно сложные структуры, но без рекурсии это тоже выглядит проблематичным. Вот если наряду с прямым чтением значения нити $x добавить её перевычисление (с возвратом по прекращению вычисления какой-нибудь нити), дела будут интереснее.
                  0
                  Честно говоря, не могу себе представить такую логику — возврат по вычислению какой-нибудь нити. Тут очень много неявных моментов появляется и подводных камней. Например — что делать с начальным значением — когда мы значение нити используем впервые и в самой нити. Или как понять когда надо остановиться когда очередной раз мы пытаемся рекурсивно вычислить значении нити (просто принять что call на нить вычисляет только ее одну не делая стандартного перехода на следующую нить — тоже думаю не выход).

                  Идея очень хорошая я тоже о ней сначала думал, но отверг из за подобных неясностей.
                    +1
                    Сначала надо посмотреть, что получится, если логика не меняется — то есть, значение нити переприсваивается в момент выхода или перехода из неё (но не в случае вызова), и если после этого значение используется в предыдущем исполнении нити — оно уже будет новым.
                    Про выход — именно так: call работает, аккуратно отслеживая все переходы, но как только дойдёт до конца какой-то нити, в которой не стоит явного ?next_thread, возвращается. То есть, конец нити работает как переход в случае главной программы и как return в случае подпрограммы. Или можно сделать более логично и ввести команду return (а конец нити оставить, как переход) — это будет даже лучше. Совпадает ли return с :: — в эзотерическом языке должен совпадать, все вызванные функции обязаны завершаться нормально.
                    Рекурсивные числа Фибоначчи попробую написать.
                      0
                      Я правильно понимаю, что если интерпретировать следующий код на основе ваших рассуждений, то он будет выполнятся бесконечно?
                      a.
                      
                      $a
                      &1
                      ++
                      


                      Или я что-то упустил? Можно ли вообще делать call из нити на саму себя? Будет ли он хоть когда нибудь работать и не зависать?
                        0
                        Я предлагаю оставить оба механизма — $a чтобы взять значение последнего вычисления нити, и ^a — чтобы вызвать перевычисление и взять получившееся значение.

                        Рекурсивное вычисление n-го числа Фибоначчи у меня получилось так:
                        a. b. c. q. e. f. r. d. n. i. j.
                        
                        >> 1& ^i 1& ^f ^j :: 2& 1& ^n ^d
                           --    ?b 2& ^j    $d ++ 0& ^n
                           $a       ++ $n    -- ^d :: ^d
                           --       << <r    :: --    0&
                           $q       :: ^f       ::    :: 
                           **          ^i
                           $a          ++
                           ++          ^f
                           =e          ++
                                       ^i
                                       ++
                                       2&
                                       ++
                                       ::
                        

                        Здесь предполагается, что ^f возвращает последнее значение, вычисленное именно нитью f (тонкий вопрос: что произойдет, если f перескочит на g, а та снова вызовет f? По логике, должно вернуться значение последнего вызванного инстанса f, чтобы ^f и последующий за ним $f давали одинаковый результат).
                        Небольшая тонкость — значение предыдущего вычисленного узла при вызове функции должно сохраняться (в моём примере считается, что рекурсивный вызов ^f не портит предыдущего ++).
                        Видно, что очень не хватает условного перехода, который бы использовал знак не последнего, а предпоследнего узла. Чтобы можно было сначала вычислить условие, потом взять результат и по условию выйти из нити (а результат сохранить в качестве результата нити).
                    0
                    Я к тому, что если вам удастся показать мне пример (да тот же факториал) — написанный по вашей идеи с объяснениями как такую программу интерпретировать — я буду только рад. Получится — что я придумал начало, а вы поставили отличную жирную точку :)

                    И тогда уже можно буде смело писать статью на esolangs.org/wiki/Main_Page.
                  +3
                  Программа исполняется по нитям (сначала первая нить, потом вторая и т.д) сверху в низ.

                  А вот тут идею можно развить. Программу надо выполнять сразу параллельно по всем нитям, предусмотрев синхронизирующие узелки типа семафоров, очередей, рандеву. И можно попытаться придумать графическое представление вместо текстового — будет гораздо нагляднее.
                    +1
                    Отличная идея для Quipu++ или Parallel Quipu :)
                  0
                  Такое ощущение, что однократная инициализация нитей не вписывается в общую схему: она имеет смысл только для участка кода, который исполняется ровно один раз. Стоит попытаться использовать этот участок, как функцию, или поместить его внутрь цикла — окажется, что инициализация уже не помогает, надо заменять её на более сложные механизмы, допускающие повторное использование. И зачем же она тогда вообще?
                  Пример: написать вычисление суммы 1^1+2^2+...+n^n :)
                    0
                    Без инициализации никак. Попробуйте написать вычисление факториала без инициализирующих нитей на Quipu и поймете о чем я говорю. Вам как минимум нужно присвоить начальную единицу в переменную в которой будете накапливать результат.

                    А ваш пример я обязательно попробую написать.
                      +2
                      Как-то так:
                      n. a. b. c. q. f.
                      
                      >> $b 1& $q 1& $a
                         ** -- =q $q <<
                         1& $n $b --
                         -- -- >a >a
                         $q $q
                         ** **
                         1& $n
                         ++ ++
                      

                      Здесь, конечно, используется, что на входе в блок a..q значение q равно 0, но при выходе оно тоже остается нулевым, так что код можно использовать повторно.
                      Кстати, вопрос. «Значение нити равно значению последнего узла» — имеется в виду значение последнего вычисления, которое до этого узла дошло? Или значение последнего вычисленного узла последнего вычисления нити? Речь о случае, когда в нити есть условные переходы, а после них какие-то вычисления.
                        +1
                        Это прекрасно. Еще вчера у Quipu был только один пользователь — я. Уже сегодня есть программист, который пишет на нем лучше автора :)

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

                        BTW, вы забыли обработку входного нуля. Т.е. 0! = 1

                        n. a. b. c. q. f.  o.
                        
                        >> $b 1& $q 1& $a  &1
                        =o ** -- =q $q <<  <<
                           1& $n $b --
                           -- -- >a >a
                           $q $q
                           ** **
                           1& $n
                           ++ ++
                        


                        На самом деле, код без инициализирующих нитей сейчас прекрасно обрабатывается текущим интерпретатором.

                        У меня к вам еще просьба. Не могли бы вы подобным способом написать еще пару примеров «сумма чисел от 1 до 100» и «генерация последовательности Фибоначчи.»? Буду очень признателен за помощь. Эти примеры помогут мне утвердиться во мнении, что ":" нити не нужны.

                        Отвечаю на ваш вопрос: значение нити равно значению последнего вычисленного на ней узелка. Т.е. даже если был переход, то нити присваивается значение узелка перед переходом.
                          0
                          Фраза «последнего вычисленного на ней узелка» остаётся двусмысленной: последнего по времени или по положению на нити? Если нить
                          a.
                          
                          $q
                          =b
                          1&
                          

                          вызывается сначала для q=1, а потом для q=0, то каким будет её значение при втором вызове?
                            0
                            Данная нить при первом вызове (q=1) будет равна «1». Перехода же не будет, поэтому вычистился последний узелок — а он — единица. При втором — будет переход и значение нити поменяется на 0 (так как последний вычисленный узелок в нити перед переходом — $q, а он равен 0).
                              0
                              А в какой момент фиксируется значение нити? При завершении её вычисления/переходе из неё?
                                0
                                Фиксируется при переходе. Есть два вида переходов — естественный — вызванный тем, что узелки на нити кончились, тогда переход осуществляется на следующую нить. Есть принудительный переход — вызываемый узелками переходов.
                            0
                            Вычисление последовательности Фибоначчи (с печатью) без инициализации (опять не проверялось):
                            a. b. z. x. y. w. v. q. e.
                            
                            >> 1& $x $y $x $q $x 1& $q
                               --    1& $z =v << $q >q
                               $a    -- ++ ', $q -- '.
                               --    $q    << >b >b <<
                               $q    **    ' 
                               **    1&    <<
                               $a    ++
                               ++
                               =e
                            
                              0
                              Спасибо! Это просто прекрасно.

                              Вот вывод программы для 10.
                              1, 1, 2, 3, 5, 8, 13, 21, 34, 55.
                              


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

                              А вообще вы мне очень помогли. Язык без инициализирующих нитей выглядит куда более чище. Сейчас он мне очень нравится. Если бы не претензии на полноту, я бы его таковым и оставил.
                                0
                                Кстати почитал тут elosangs понял что у многих языков в описании стоит: " It is unknown if it is Turing-complete or not.". Думаю, что про Quipu можно что-то вроде этого и написать в его текущей реализации (без call'ов).
                                  0
                                  Еще мне кажется что проблемы полноты можно решить добавив возможность адресовывать бесконечное число нитей. Например разрешив задавать символьную метку произвольной длины. Или нумеровать нити числами 1...N, и оператор получения значения нити использовать так:

                                  &1
                                  $$
                                  


                                  Получение значения нити номер 1. Или:

                                  &4
                                  $$ - получение значения нити номер 4
                                  $$ - получение значения нити номер которой был записан в нити 4
                                  


                                    0
                                    Даже какая-то мнимая поддержка массивов получается.
                                      0
                                      Чтобы исходная программа была конечной длины, придётся добавить механизм создания нитей (с их кодами). Будет жутко забавно :)
                                      Для начала можно взять пример с Excel с его абсолютной и относительной адресациями, и использовать их при клонировании…
                            0
                            Самое интересное, что на Scala можно написать DSL этого языка. :)
                              0
                              А можете кинуть ссылку о том как это сделать?
                                0
                                www.scala-lang.org/node/1403 вот для примера можно глянуть, можете исходники посмотреть.

                                Знать то особо не надо, просто использование основных фич Scala. В Scala 2.10.0 ввели макросы, можно еще круче делать.

                            Only users with full accounts can post comments. Log in, please.