From oerjan@nvg.ntnu.no Thu Aug 23 18:52:09 2001
Date: Thu, 23 Aug 2001 18:47:55 +0200 (CEST)
From: Orjan Johansen
Reply-To: lang@esoteric.sange.fi
To: Esoteric Languages List
Subject: [lang] Bag language
I recall reading somewhere, possibly in the Klouwer Encyclopedia of
Mathematics, although I can't find it again now, about a certain
Turing-complete formalism.
A "program" consists of a list of positive fractions (rational
numbers), and the state of the "computer" is a positive integer n.
Naturally, input is whatever n you start with.
Computation consists of going through the list from top to bottom
until you find a fraction p/q such that np/q is an integer. Then n is
replaced by np/q, and the search is restarted from the top. The
program stops if you reach the end of the list without a match, and
the final n is the output.
Now some of you might find this esoterically interesting to program
directly, but I thought a bit about why this must be Turing-complete,
and came to an equivalent formalism which makes a simple programming
language, and without the need to invent and multiply primes all the
time. It seems like this must have been thought of before, if nothing
else by the person who proved the fraction computer Turing-complete.
Basically, by the fundamental theorem of arithmetic, a fraction is a
product of prime powers (some negative if the fraction is not an
integer), and the primes serve sort of as variable names. So here is
a syntax for the equivalent formalism in yacc/lex format (though I
haven't written an interpreter/compiler yet):
program : /* empty */
| program transformation
;
transformation : tokenlist ':' tokenlist ';' ;
tokenlist : /* empty */
| tokenlist tokenterm ;
tokenterm : TOKEN
| NUMBER TOKEN
;
[ \t\n\r]+ { /* skip space */ }
[#].* { /* skip comments */ }
[:] { return ':' }
[;] { return ';' }
[0-9][1-9]* { ...; return NUMBER; }
[']([^']|[\\].|[\\][0-9]+)['] { ... ; return NUMBER; }
[-_.[:alpha:]][-_.[:alpha:]0-9]*
{ ...; return TOKEN; }
Here, "number token" is simply an abbreviation for several
appearances of a token in the list, and the number could be given
by a character, i.e. 'a' = 65. The current state of the program is
itself a tokenlist.
Now the computation becomes as follows: Search through the program
until reaching a transformation such that the current state of the
program contains all the tokens on the left hand side of the
transformation, and as least as many times. Then remove that many of
those tokens, and add those on the right hand side of the
transformation. Then, as before, repeat from the top of the program.
The positions of a token in a tokenlist don't matter, only its total
number of occurrences. I.e. a tokenlist is a "bag".
For convenience, a token will be allowed to occur both on the left
and on the right hand side of a transformation, although this is not
strictly permitted in the fraction case; it would be simple enough to
simulate with temporary renaming.
So, here is an example (untested, naturally) program to multiply two
numbers, given as the number of occurrences of X and Y, respectively,
and returning the result in Z:
T Y: T Y2 Z;
T: ;
Y2: Y;
X: T;
Now once we have this formulation, new opportunities for I/O present
themselves, by making special tokens. I.e.
Get, a token that causes a character to be read, and that number
of Input tokens to be added, or an EOF token;
Put, a token that causes a character to be written, corresponding to
the number of Output tokens;
Exit, a token for exiting the program immediately.
Even general file I/O could be done by adding stream tokens and the
like. Anyhow, "cat" is then simple:
EOF: Exit;
Input: Output;
Output: Output Put;
: Get;
I note that the Exit is necessary only because of the ": Get;" which
makes it impossible to exit the program by falling off the end. If
the program instead had a Start token to begin with, a different
possibility would be:
EOF Start: ;
Input: Output;
Output: Output Put;
Start : Start Get;
Anyhow, I suppose a suitable name for this language would be "Bag",
although I am very open to suggestions as well as to being informed
that this has been done before...
Greetings,
Ørjan.