January 13, 2013 at 19:53Quipu - Inca esoteric programming language based on the nodal script
A friend of mine, a historian by profession, gave me a wonderful idea about using ancient mnemonic and counting systems in modern cryptography. In the process of his stories about the Inca nodular writing , I began to realize that everything new is well forgotten old and it would not be bad to somehow apply the ancient experience in the modern world. The first thing that came to mind was cryptography. This is the most obvious - just convert the nodes from threads to bytes and the cipher is ready. On the one hand, everything seemed clear, but then I remembered the cryptographic strength and other parameters of the ciphers and realized that I did not have enough experience and knowledge in the field of cryptography to single-handedly develop a new cipher.Then I decided to try to introduce some esoteric programming language, the construction of which can be written using Kipu's nodal script . At first it seemed that this was impossible: I invented a language and tried to write a factorial calculation program on it. The first three draft specifications went into the bin: the languages were no good. They looked as expected for esoteric languages, but did not help me solve the task, because were not Turing complete. Enthusiasm was slowly fading away, and this task seemed to me too much. Having gathered strength, I decided that if I can write a factorial calculation program, then the language works.
The fourth version of the language turned out to be successful: I wrote a factorial, then generating a Fibonacci sequence and a dozen simple examples of ala “the sum of numbers from 0 to 99”. The language turned out right: unusual and at the same time with a simple clear idea. The main thing is that a language can solve any (or almost any) problem that can be expressed as a computable function.
Inca and Kipu
(Wikipedia paragraph)
Kipu is an ancient Inca mnemonic and counting system, a kind of writing: it is a complex rope plexus and nodules made from the wool of South American camelids (alpacas and llamas) or from cotton. There can be from a few hanging threads up to 2000. It was used to send messages by messenger messengers along specially laid imperial roads, as well as in various aspects of public life (as a calendar, topographic system, for fixing taxes and laws, etc.) .
The decimal number system was used in the pile, and mainly numbers were written on them using three kinds of nodes. The former depicted dozens, the latter a group of units (2-9), and the third node represented a unit. Thus, the group of nodes was interpreted as a number in which, in place of thousands, hundreds, tens and units, the corresponding nodes were imposed.
We put the notation “7d” - denotes a sequence of 7 nodes representing tens. “5i” is a group of unit nodes of 5 pieces and “I” is a unit, and “x” is a pass. Then the number 703 can be represented by the following sequence of nodes: “7dx3i”, the number 2013 is 2dx1d3i, etc.
These ideas formed the basis of the Quipu language for some changes.
Language specifications
A Quipu program is a matrix of knots, each column of which forms a thread. The number of threads is limited to 26, according to the number of characters in the Latin alphabet (in fact, there are 52, but more on that later). The number of knots per thread is not limited. Each thread should be separated from the neighboring ones by at least one space and be aligned on a fixed number of indents from the beginning of the file throughout its entire length. In other words, a thread in the form of a “ladder”, and not a column, can hardly be called valid.
Quipu can handle two types of data - integers and strings.
The program is executed by threads (first the first thread, then the second, etc.) from top to bottom. At each step of execution, the value of the current node is calculated. Execution continues until the value of the last knot of the last thread is calculated or a stop knot is encountered. “::”.
Nodules can be divided into two types - simple and compound. Simple ones consist of one matrix cell (a pair of characters per line, for example “$ a”). Compound nodules are a sequence of simple nodules in a thread. Compound nodules are used to represent numbers and strings. For example, the string “Habr” in Quipu can be written like this:
‘H
‘a
‘b
‘r
And the number 2013 is like this:
2#
1@
3&
Each thread can be marked with a symbol mark. If there are no marks, all threads are numbered in order with the marks “a” - “z”. In addition, each thread has its own value, which is equal to the value of the last nodule in it. You can access the value of the thread with the help of a special knot - “$ a” (value of the thread “a”). The value of each thread is recorded in its zero knot, which allows you to use it as an implicit argument in expressions.
The thread has two components - the main and initializing. For example, “a:” is the initializing component of the thread “a”, “a.” Is the main one. A thread can be represented as two components, or each separately. In sequential execution of the program, only the main threads are used. Initializing threads are executed once at the first explicit or implicit call to the value of the thread. By explicit means the execution of the knot “$ a”, by implicit - the use of the top zero thread knot in expressions. If the thread does not have an initializing component, then its initial value is zero. There is a restriction on the types of nodules used in initializing threads: it is forbidden to use nodules that change the flow of program execution, i.e. transitions and a nodal stop.
Some nodes do not have their own value, so their value is calculated as the value of the nearest significant node in front of them (if there are none, then the value of the thread, which is the zero node). Examples of such nodules are output nodules and conditional jumps.
Knots table (n - current thread node)
| Knot | Value |
|---|---|
| $ a | The value of the thread is “a”. |
| >> | Entering a value from the terminal. |
| << | Outputting the value (n-1) of the node to the terminal. |
| 1 # 4% 5 @ 1 & | Number 1451: "#" - thousands, "%" - hundreds, "@" - tens, "&" - units. |
| - | The difference between (n - 2) and (n - 1) nodules. |
| ++ | The sum of (n - 2) and (n - 1) nodules. |
| ** | The product of a nodule (n - 2) and a nodule (n - 1). |
| // | Integer division of a nodule (n - 2) into a nodule (n - 1). |
| %% | The remainder of the division of the whole nodule (n - 2) into a nodule (n - 1). |
| Conditional jump to thread “c” if the value of the previous node is less than zero. | |
| > c | Conditional jump to thread “c” if the value of the previous node is greater than zero. |
| = s | Conditional jump to thread “c” if the value of the previous node is zero. |
| ? from | Unconditional transition to a thread "s". |
| :: | Stop. |
| '' | Symbol. |
| \ n | Special symbol. |
Program Examples
Hello World!
a: a.
'H <<
'e
'l
'l
'o
'
'W
'o
'r
'l
'd
'!
\n
Sum of numbers from 0 to 99
s. i. c. e.
$i 1& $i $s
++ ++ 1% <<
--
=e
?s
Factorial
a: a. b: b. e.
>> $a 1& $a $b
=e 1& <<
1& ++
-- $b
=e **
?a
Fibonacci
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&
<<
Implementation
For quite some time now I have been haunted by the idea that it is time to learn a new language, in order to broaden my horizons, so to speak. The choice fell on Scala. I have always been attracted to her so-called “excessive complexity” which everyone is talking about. After writing a couple of simple examples ala “Hello World”, I imagining myself a burnt rocky, took up the implementation of the Quipu interpreter. The task turned out to be more difficult than I thought, despite the fact that at the very beginning I gave myself the installation - to make it just work, without focusing on the beauty of design and implementation.
As a result, I received a working prototype in a day and a half. Got, really, what I wanted. A kind of proof-of-concept idea. I wrote quite a bit of code and it looks a little intimidating especially for people who have experience developing on Scala. However, I believe that a start has been made. The path “idea -> implementation” has been completed with minimal efforts and the following steps can be aimed at improving the current implementation. I don’t even exclude the possibility that I’ll have to rewrite everything from scratch, but I still hope that there is a reasonable grain in the original code and that large-scale refactoring can save it.
There are also a couple of minor issues in the current implementation that I decided not to fix yet, in the light of the prospect of “all rewriting from scratch”. Nevertheless, these problems do not cause any major inconvenience, and on the contrary, they teach Quipu programmers to properly format their programs. The following is a list of current flaws:
1) Each thread should have a label. Threads without tags are not supported.
2) The program should end with an empty line, otherwise - the nodes located on the last line will not be interpreted.
So. The interpreter source code is available on GitHub: github.com/vkostyukov/quipu. I will be very happy to pull-requests with corrections of my codebase. In addition, I will be grateful for new examples of using the language, which I will definitely post on the project page. I also promise a stylized T-shirt that says “% username%, the first Quipu hacker.” To someone who writes the 99-bottles-of-beer program on Quipu. Joke :)
What for?
There is a belief that by inventing a new programming language, the author practically dooms himself to failure. With this I completely agree and believe that for the next 3-5 years, humanity has a resource on programming languages. Now it’s hard to come up with something new, useful and different from the coffee giants known to everyone. But this is perhaps true for the languages of "big" and "serious", which are trying to solve all conceivable and unimaginable problems that the developer allegedly faces.
Esoteric languages solve other problems - the problems of warming up the brain, unhealthy curiosity and