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.