Esoteric Language Idea

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Esoteric Language Idea

Postby quintopia » Tue Nov 06, 2007 5:54 am UTC

I came up with this esoteric programming language idea. Of course it's a tarpit, but like none I've seen. Maybe a cross between Biota, CAs, and Unlambda-style all-functional languages.

Here's the basic spec:

A program is an array of cells, each cell containing some code, and they are all connected to their neighbors in a grid lattice, with the connections being represented by pointers to queues (A can put data in B's queue and B can put data in A's queue, because A and B are neighbors in the grid). Syntactically, you separate cells in the same row by "|" and rows by newlines.

Each cell has four pieces of code (which may be blank, thus, NOPs), separated by ":", so a single cell has this structure:

<other cells>|<code response for message received from up>:<response for right>:<response for down>:<response for left>|<other cells>

Within each code block the following instructions can be used:
T<expr1><expr2> - Returns the value of expr1.value-expr2.value.
C<loc><expr> - Sends the value of expr to loc and returns the value of expr.
G<loc> - Returns the oldest message in the queue from loc. If no message from loc exists, block until a message arrives and intercept it.
A<expr><expr1><expr2> - Evaluate to expr1 if expr is 0, otherwise evaluate to expr2.
Fix'd. Thx guys!

Other characters will be ignored and may be used for comment and code clarification. "(",",", and ")" may be useful.

Each of the "<loc>" type arguments above can take a single character, which gives a reference to "up neighbor","right neighbor", "down neighbor", and "left neighbor" respectively, in this manner:

Code: Select all

  A
G   C
  T


The entire zeroth row is predefined with cells that always receive user input and send it to the cell below it.
The entire zeroth column is predefined to block waiting for messages from cells to their right, and output the data to standard out.
All cells left undefined are given the default cell code of:
GA:GC:GT:GG
That is, they consume any messages they are passed immediately and do nothing with them.
All messages sent between cells consist of a single byte.

Every program begins with an initialization string like so:
init:0

Program interpretation goes in this manner.
To begin, the init string is processed in order as if it were user input.
For the rest of the time:
All cells will execute code corresponding to messages it received in FCFS order. That is, if a cell has a message delivered to its queue from its right neighbor, it will execute its "code response for message from right." The only exception is if a cell is currently blocking waiting for a message, in which case it will ignore all messages until that message is received. If it is not blocked, it will greedily consume messages until it blocks again or runs out, whichever comes first. (As you can see, this would operate quite nicely on parallel processors.)

So, e.g., a program to add two numbers together might look like:

init:00
C(G,T(G(C),T(T(T(G(A),G(A)),G(A)),G(A)):::|C(G,T(G(A),G(A))

The second cell will subtract the second input "0" from the first input "0" for a result of zero, which it puts in the first cell's queue. The first cell will subtract "0" from "0" also, giving zero, and then proceed to block for user input, consecutively subtracting from zero the next two values input for a total of -sum. Finally, it subtracts this value from the value of zero it retrieved from the cell to the right earlier to give a result of 0-(-sum)=sum, which it sends to the left into column 0. As previously stated, this will cause sum to be printed to stdout.



So, for those of you who have read this far, what do you think? I think it's Turing-complete.
What things do you think would be nice to change? Would you consider writing code for it if an interpreter were available, just to challenge yourself? What if there were a GUI to edit cells graphically and watch the contents of queues as the program runs?
Last edited by quintopia on Tue Nov 13, 2007 10:12 pm UTC, edited 4 times in total.

photosinensis
Posts: 163
Joined: Wed Aug 22, 2007 6:17 am UTC

Re: Esoteric Language Idea

Postby photosinensis » Wed Nov 07, 2007 10:25 pm UTC

Hmm...sounds familiar to this old bio major turned computer scientist.

That said, I can't really tell if the language is Turing-complete, though it very well could be. However, I'm not a fan of minimalist languages, and thus would steer clear of something like this.

A GUI for editing everything either statically or on-the-fly and chemical-to-machine code compiler, however, would be absolutely awesome. Besides, a compiler for most minimalist languages shouldn't be that hard to write. The parse tree should be minimal, the regular expressions are regular, and the rest of it is chaining bits.

Another interesting idea along similar lines (really primitive biocomputing) would be to use the single-letter amino acid codes to generate a similar language that can actually handle more complex data types, and then create a coding system on top of that which is similar to your language.
While I clicked my fav'rite bookmark, suddenly there came a warning,
And my heart was filled with mournng, mourning for my dear amour.
"'Tis not possible!" I uttered, "Give me back my free hardcore!"
Quoth the server: 404.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Esoteric Language Idea

Postby quintopia » Thu Nov 08, 2007 12:46 am UTC

I just realized it might be nice if there way for a program in this language to halt on its own. . .and the best way I can think of doing this is by adding a a "death" character (which might possibly be decided by the program, and then the following will work:

The program halts when a "death" character is received by any cell in the zeroth row.

photosinensis wrote:The parse tree should be minimal, the regular expressions are regular, and the rest of it is chaining bits.


In fact, I designed the language so that there would be no parse tree necessary. All interpretation can be done using string splits and switches on initial characters.

photosinensis wrote:Another interesting idea along similar lines (really primitive biocomputing) would be to use the single-letter amino acid codes to generate a similar language that can actually handle more complex data types, and then create a coding system on top of that which is similar to your language.


I'm intrigued. What exactly do you mean "complex data types"? And how would you represent them with A,C,T,G?

User avatar
Dustbin
Posts: 39
Joined: Sun Nov 19, 2006 5:54 am UTC

Re: Esoteric Language Idea

Postby Dustbin » Thu Nov 08, 2007 4:47 am UTC

Very cool idea, I'm not a fan of minimalist languages either though.
The first thing that came to mind when I was reading your explanation was TRIPS
http://www.cs.utexas.edu/~trips/
It's a hardware architecture where each core is connected to neighbors on it's four sides. I don't fully understand it, but it's pretty interesting. Also as part of the project they did some work on DNUCA(Dynamic Non-Uniform Cache Access) where they have a sorta gradient cache rather than assuming all L1 cache accesses take the same length of time.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Esoteric Language Idea

Postby quintopia » Thu Nov 08, 2007 11:38 pm UTC

Based on the halting rule I mentioned above, I *conjured* a new addition program that halts after it outputs an answer:

init:00
death:0
C(G,T(G(C),T(T(T(G(A),G(A)),G(A)),G(A)))):C(A,G(C))::|C(G,T(G(A),G(A))):C(G,G(C))::|C(G,T(G(C),G(A)):::|C(G,T(G(A),G(A))):::

photosinensis
Posts: 163
Joined: Wed Aug 22, 2007 6:17 am UTC

Re: Esoteric Language Idea

Postby photosinensis » Fri Nov 09, 2007 3:44 pm UTC

Well, in the genetic code, there are three stop signals: UAA, UGA, and UAG, as well as only one start signal, AUG (methionine/met/M). These translate to TAA, TGA, and TAC in DNA and methionine translates as ATG. A really interesting idea would be to actually make a coding sequence based on the codons, which would allow for 20 operators (yes, there are 64 possible codons, but most are redundant). Again, a little less minimalist, but closer to the original biology. But that's just tangentially related to the question at hand.

When I say "complex data type", I mean something that has rules governing its form and structure, such as binary search/AVL trees, ordered tables, and things of that nature.
While I clicked my fav'rite bookmark, suddenly there came a warning,
And my heart was filled with mournng, mourning for my dear amour.
"'Tis not possible!" I uttered, "Give me back my free hardcore!"
Quoth the server: 404.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Esoteric Language Idea

Postby quintopia » Sun Nov 11, 2007 12:42 am UTC

Well, if this thing is Turing-complete (and I'm fairly certain it is), I should be able to write all those things in it. Not that it would be easy, but given that memory is "two-dimensional," I suspect it would be easier than in something like BF.

User avatar
xyzzy
Meta-Titled
Posts: 263
Joined: Sun Mar 18, 2007 10:02 pm UTC
Location: Colossal Cave
Contact:

Re: Esoteric Language Idea

Postby xyzzy » Sun Nov 11, 2007 5:35 pm UTC

photosinensis wrote:Well, in the genetic code, there are three stop signals: UAA, UGA, and UAG, as well as only one start signal, AUG (methionine/met/M). These translate to TAA, TGA, and TAC in DNA and methionine translates as ATG. A really interesting idea would be to actually make a coding sequence based on the codons, which would allow for 20 operators (yes, there are 64 possible codons, but most are redundant). Again, a little less minimalist, but closer to the original biology. But that's just tangentially related to the question at hand.

When I say "complex data type", I mean something that has rules governing its form and structure, such as binary search/AVL trees, ordered tables, and things of that nature.


If you've read Godel, Escher, Bach, you'll note that Hofstadter has already played with some of those ideas. I don't think there's a full programming language based on the codons, but there is a lot of stuff that comes rather close.
"Wile E. Coyote was a theoretical mathematician." - Leliel
"Modern life can be so boring without elements of the bizarre or the fantastical. Hence, we have steampunk." - Me

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Esoteric Language Idea

Postby quintopia » Sun Nov 11, 2007 5:43 pm UTC

Any ideas then for a name for this language?


Here's another code snippet. This one's a memory cell. The cell above the left cell can write to it. The cell above the right cell can read from it.

<other_cells>
<other_cells>|C(C,G(A)):::|C(A,G(G)):::|<other_cells>
<other_cells>

RockHawk
Posts: 19
Joined: Sun Nov 11, 2007 6:30 pm UTC

Re: Esoteric Language Idea

Postby RockHawk » Sun Nov 11, 2007 7:18 pm UTC

This looks like it would be fun to play with! If I understanding correctly, you're memory cell would be a read once for every write affair.

You could make something that remembered inputs coming from the cell marked <in> and then sent that value to <out> any time you sent an input from <out> (which could take any value) like this:
<other cells>|<other cell>|<in>|<other cells>
<other cells>|<out>|C(T,G(A)):C(G,C(T,G(C)))::C(C,G(G))|:::G(G)C(G,G(T))|<other cells>
<other cells>|<other cell>|C(C,G(A)):::|C(A,G(G)):::|<other cells>
<other cells>

Interesting points:
- You can use the C(P,C(Q,...)) construct to split one input into an output to multiple other cells.
- I've assumed you can do multiple instructions (that is non-nested instructions). Is that allowable? You could do C(A(G(G),G,G),G(T)) instead to avoid this.

A compiler for this would be nice, but a web app where you could see it working would be really cool (something like that will be pretty much required if anyone's going to write anything even marginally complicated :-)

As for names, how about CellBrain?

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Esoteric Language Idea

Postby quintopia » Mon Nov 12, 2007 7:53 am UTC

I like CellBrain. And yes, the code I posted above was read once per write, but is easily modified to remember the value after it's read, because C returns the message it sent, like so:

<other_cells>|<in>|<out>|<other_cells>
<other_cells>|C(C,G(A)):::C(C,G(C))|C(G,C(A,G(G))):::|<other_cells>
<other_cells>

This accomplishes what your code does, but moves around the input and output cells. To put them where you do, I would do:

<other_cells>|<default_cell>|<in>
<other_cells>|<out>|C(C,G(A)):::C(C,C(G,G(C)))|:::C(G,G(C))|<other_cells>



And no, no multiple instructions in the same code area. Everything must be nested.

RockHawk
Posts: 19
Joined: Sun Nov 11, 2007 6:30 pm UTC

Re: Esoteric Language Idea

Postby RockHawk » Mon Nov 12, 2007 9:35 am UTC

I like it, though does that not leak messages on the queue from the <out> cell?

Though as I said, it's easy to get rid of them with an A(G(A),A,A) where you have just A in the second cell of your first fragment.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Esoteric Language Idea

Postby quintopia » Mon Nov 12, 2007 4:15 pm UTC

No, it will not leak messages on the out cell. It only sends messages to the out cell when it receives a message from the out cell. Note that it ignores messages coming from the right, letting them sit in its queue, and then when it receives a message from out, it gets the message from right out of its queue and sends it left.

RockHawk
Posts: 19
Joined: Sun Nov 11, 2007 6:30 pm UTC

Re: Esoteric Language Idea

Postby RockHawk » Tue Nov 13, 2007 9:29 am UTC

What I meant was, there is no G(A) in the cell below the <out> cell, so the messages prompting data to be returned to the <out> cell will get queued forever.

This is not necesarily a problem - maybe the environment could spot they could never be received (by checking all 4 code entries for a G(A) and just dump them), and/or you could impose a maximum queue length and discard older messages if it is exceeded.

Also, I'm worried about the A operation - it is defined to return a location, so presumably you should expect it to be used instead of a location in the G and C expressions. I'm worried it's possible to come up with ambiguous code if this is the case because it is not obvious whether by A you mean "up" or the operation (though I can't quickly come up with a case where it is ambiguous).

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Esoteric Language Idea

Postby quintopia » Tue Nov 13, 2007 1:04 pm UTC

Oh, I didn't think of that. You're right, it could be ambiguous, and at the very least, couldn't be greedily consumed.

What if I had it as
A<expr><expr><expr>
instead? It seems like the same structures should be possible.

User avatar
M.qrius
Rainbow Brite
Posts: 519
Joined: Sat Nov 10, 2007 12:54 am UTC
Location: Rainbow's end
Contact:

Re: Esoteric Language Idea

Postby M.qrius » Tue Nov 13, 2007 4:29 pm UTC

quintopia wrote:Oh, I didn't think of that. You're right, it could be ambiguous, and at the very least, couldn't be greedily consumed.

What if I had it as
A<expr><expr><expr>
instead? It seems like the same structures should be possible.

Nice programming language :)
I think A<expr><expr><expr> is more versatile than A<expr><loc><loc>... You've got my vote on that.
edit: Only now I see your point on the ambiguousness... and changing it to A<ex><ex><ex> won't help, as shown by this example:
C(A,G(C)) G(C) G(C) G(C)
C(A(G(C),G(C),G(C)),G(C))
And the old one doesn't work either:
C(A,G(C)) G(G) G(G)
C(A(G(C),G,G),G(G))
Maybe you should just make the brackets and commas part of the language, to avoid these ambiguousities.


Another question: Do you think just a number or a hex code should count as an expression? I'd say no, but it makes it difficult to store predefined values in your program: You'd have to put them in the init, then move them somewhere through your program, and use them to check if the value coming in is a constant or an input... if that's at all possible.
edit:
I'm trying to store the value 1 somewhere in my program, so I can decrement... but I can't think of a way to do that yet. The problem is: you want to check if your memory cell's constant value is set yet, and if it is, then don't store the value to it. But when you ask whether it's set yet if it's not set, then the memory cell will block for input.

Also: The input you give, is it in hex, or in ascii value of the character? It seems like your programs so far are assuming hex, but then we need to define how the input's going to be formatted, if anyone's going to write an interpreter (I'm considering it).

Also: Instead of defining a death character, you could also just halt the program when any character is outputted to the zeroth row, since that's not supposed to happen during normal program execution anyway.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Esoteric Language Idea

Postby quintopia » Tue Nov 13, 2007 5:42 pm UTC

The "counterexamples" you gave assume that multiple expressions in the same code block are allowed. I really think the A<expr><expr><expr> removes the ambiguities. This is because the character after a G always represents the end of an (innermost) expression. So to define the grammar (for a single code block) more clearly (in Chomsky Normal form, no less):

S->ε|exp
exp-> aop aoparg | cop coparg | top dexp | gop loc
aoparg-> exp dexp
dexp -> exp exp
coparg -> loc exp
loc-> 'A' | 'C' | 'T' | 'G' | 'a' | 'c' | 't' | 'g'
aop-> 'A' | 'a'
gop-> 'G' | 'g'
top-> 'T' | 't'
cop-> 'C' | 'c'

Does anyone have yacc or the like on hand or otherwise know how to look for ambiguities?

About the death character: you're right, of course. there may be a reason why someone would want to be able to let random messages fall into the zeroth row and not worry about halting, so maybe the death character(s) could still be optional?
About the inputs: I've assumed ASCII so far. ('0'-'0' = 0)

About getting 1 in a cell's queue: What do you need to do this for? There is probably a workaround. For example, how about group of cells that constantly spit out 1's in a stream so that whenever a cell needs a 1, it just grabs it off the stream and uses it immediately?

User avatar
M.qrius
Rainbow Brite
Posts: 519
Joined: Sat Nov 10, 2007 12:54 am UTC
Location: Rainbow's end
Contact:

Re: Esoteric Language Idea

Postby M.qrius » Tue Nov 13, 2007 6:14 pm UTC

About the ambiguity, I'll have a look at that later when I have more time (I don't know Chomsky Normal yet). You may be right that it's not ambiguous when you don't allow multiple commands.

Ah, I didn't realize you subtracted '0' from the numbers.

Personally, I think the init and the death statements aren't in style with the rest of the code, so removing a death statement would make it more aesthetically pleasing.

About the 1, I was thinking about building a multiplication. I'd need to add value a, b times, which could be done by decrementing b every iteration... But you'd need a 1 for that. Could you build a program that repeatedly subtracts 1 for the input value until it is zero to show what you mean?

RockHawk
Posts: 19
Joined: Sun Nov 11, 2007 6:30 pm UTC

Re: Esoteric Language Idea

Postby RockHawk » Tue Nov 13, 2007 8:16 pm UTC

quintopia wrote:Oh, I didn't think of that. You're right, it could be ambiguous, and at the very least, couldn't be greedily consumed.

What if I had it as
A<expr><expr><expr>
instead? It seems like the same structures should be possible.


Yes, I think that should work - as long as it's only the chosen expression is evaluated it allows you to do basically the same as with the old C(A(...),...) construct and more as well (e.g. conditionally get messages from a queue or send a message).

I agree your syntax now looks fine (though I haven't put it through anything to rigorously check it).

Have you thought any further about actually implementing this yet? I might see if I can knock something simple up in Python tonight, but I don't have so much experience with GUI stuff.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Esoteric Language Idea

Postby quintopia » Tue Nov 13, 2007 10:39 pm UTC

@M.qrius:
This program should take in an argument n, decrement it n times, then halt.
It uses the "all characters are death characters" idea you mentioned.
Check and make sure it does what I claim tho. . .


init:110
|C(T,A(G(A),G(A),G(A)):::|::C(A,G(T)):|C(T,A(G(A),G(C),T(G(A),G(A)))||
|C(T,A(G(A),G(A),G(A))::C(T,G(T)):|::C(A,G(T)):|C(T,G(A))::C(T,G(T)):|
|C(C,G(A)):::|:C(T,C(T,C(C,C(G,T(G(G),G(C)))))):C(A,G(T)):C(T,C(T,C(C,C(G,T(G(G),G(C))))))|C(G,C(T,G(A))):::C(G,C(T,G(T)))|
||A(G(A),C(A,G(A)),G(A)):::|C(A,G(A)):::|

This should easily be modified to do the multiplication algorithm.

@RockHawk: Honestly, I don't have the time to implement it. I don't even have time to finish debugging the editor for my other esolang. Feel free to attempt to implement it, even if it's only an interpreter that reads in text files. If it works, I'll post it on my website with a description of the language and add the page to the esolang ring to see if anyone else in the esolang community wants to write stuff for it.
Last edited by quintopia on Tue Nov 13, 2007 11:07 pm UTC, edited 3 times in total.

RockHawk
Posts: 19
Joined: Sun Nov 11, 2007 6:30 pm UTC

Re: Esoteric Language Idea

Postby RockHawk » Tue Nov 13, 2007 10:48 pm UTC

Ok, I've started work on some python to run this language, and I've coded the basic cells. I now need to put together some glue logic for the queues (currently they don't notify the cells or support blocking). I'll post the code somewhere once I've got a bit further.

I've used quintopia's adder for testing, and it does indeed work as expected.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Esoteric Language Idea

Postby quintopia » Tue Nov 13, 2007 11:09 pm UTC

Awesome. Are you running the cells in separate threads? I fell like a CellBrain programmer should always have to worry about race conditions.

RockHawk
Posts: 19
Joined: Sun Nov 11, 2007 6:30 pm UTC

Re: Esoteric Language Idea

Postby RockHawk » Wed Nov 14, 2007 1:07 am UTC

Yep, each cell has its own thread (in fact for the moment, I spawn a new thread each time a cell is notified and that thread just dies when the command completes).

I've got the adder working from a proper input file now - the decrementer you posted doesn't seem to work out of the box but I need to add in some more debugging.

I've slightly changed the input file syntax - the inputs are read as numbers, and must each be on their own line, and the code block must have a "code:" header to denote where it starts. For example:

Code: Select all

init:
0
0

code:
C(G,T(G(C),T(T(T(G(A),G(A)),G(A)),G(A)):::|C(G,T(G(A),G(A)):::


This seems to make more sense to me as the basic operation is a subtract, but that does mean you can't get strings of ASCII out which might be a bit limiting.

When run the program loops round waiting for input (again given by writing numbers one per line). So running that program looks like:

Code: Select all

user@localbox:~/cellbrain$ python test.py test.cb
[0, 0]
[['C(G,T(G(C),T(T(T(G(A),G(A)),G(A)),G(A)):::', 'C(G,T(G(A),G(A)):::']]
23
7
Out: 30


I'll post the files once I've done some more debugging and made it so you can exit it without killing it :D

For now it's time for bed!

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Esoteric Language Idea

Postby quintopia » Wed Nov 14, 2007 1:37 am UTC

For those who do BF and other esolang work, ASCII is a more logical input language. However, if you can support arbitrary numbers as input (72,101,108,111,etc.) and always output ASCII characters, that will be fine.

However, I still feel in the long run, it would be better to have ASCII inputs, as there are programs which might possibly ask users for info other than numbers, so the CellBrain should be able to process ASCII anyway. It is easier to have the init: be a regular string in this case, as the interpreter could then just pass the string straight into the input stream buffer and know that the rest of the code will still handle it just fine.

Also my original spec called for a "code:" specifier, but I realized it was unnecessary if all of the init inputs were a single string, 1 character per input, on a single line. In other words, given that you are taking in numbers as input, that's fine.

I'm curious: how did you implement the queues? one queue per cell and it runs through linearly looking for the first message from a given source? or four queues per cell and it just pops immediately? I feel like the latter would be faster, despite the additional overhead.

User avatar
M.qrius
Rainbow Brite
Posts: 519
Joined: Sat Nov 10, 2007 12:54 am UTC
Location: Rainbow's end
Contact:

Re: Esoteric Language Idea

Postby M.qrius » Thu Nov 15, 2007 10:59 am UTC

quintopia wrote:@M.qrius:
This program should take in an argument n, decrement it n times, then halt.
It uses the "all characters are death characters" idea you mentioned.
Check and make sure it does what I claim tho. . .


init:110
|C(T,A(G(A),G(A),G(A)):::|::C(A,G(T)):|C(T,A(G(A),G(C),T(G(A),G(A)))||
|C(T,A(G(A),G(A),G(A))::C(T,G(T)):|::C(A,G(T)):|C(T,G(A))::C(T,G(T)):|
|C(C,G(A)):::|:C(T,C(T,C(C,C(G,T(G(G),G(C)))))):C(A,G(T)):C(T,C(T,C(C,C(G,T(G(G),G(C))))))|C(G,C(T,G(A))):::C(G,C(T,G(T)))|
||A(G(A),C(A,G(A)),G(A)):::|C(A,G(A)):::|

This should easily be modified to do the multiplication algorithm.

@RockHawk: Honestly, I don't have the time to implement it. I don't even have time to finish debugging the editor for my other esolang. Feel free to attempt to implement it, even if it's only an interpreter that reads in text files. If it works, I'll post it on my website with a description of the language and add the page to the esolang ring to see if anyone else in the esolang community wants to write stuff for it.


I've rewritten it to more readable format, and I've boldified what I think is unreachable/useless code. I've written in green what I think should be added (read below)

|sendv(ifz^(^,^)):::...........|::send^(v):..........................................................................................|sendv(ifz^(>,sub(^,^)):::||
|sendv(ifz^(^,^))::sendv(v):|::send^(v):...........................................................................................|sendv(^)::sendv(v):|
|send>(^):send>(>)::.........|:sendv(sendv(send>(send<(sub(<,>))))):send^(v):sendv(sendv(send>(send<(sub(<,>)))))|send<(sendv(^)):::send<(sendv(v))|
|................................|ifz^(send^(^),^):::..................................................................................|send^(^):::|

The right side nicely delivers a 1, by substracting '0' from the second '1'. I'd think the left side should deliver the first '1', but as I see it, it doesn't. (I might have interpreted the commands wrong though...)
First, cell A1 sends a '1' down, then it sends the next character the user inputs down. Cell A2 sends the last character (the one the user wrote) down. Cell A3 sends this to the right.
Cell C1 at this moment has found that that character is not 0, so is waiting for input to do the sub(^,^)
Cell B3 substracts value(1) from the character, then sends the result everywhere. This prompts C3 to send another value(1), prompting B3 to do a substract again... but then it waits for input from the left. So if you add what I wrote in lime, I think it should work... (Or write send>(send<(^)):send>(send<(>)):: to output every number :P)

But this program is specially made to decrement just 1 number, I think it would be more difficult to output every number until a character is reached... but it might be possible.


You said:
The only exception is if a cell is currently blocking waiting for a message, in which case it will ignore all messages until that message is received.
Do you mean by that that every message sent during that time goes into void, or that it just waits until it gets its value, then continues working on the next message? I'd go for the latter, otherwise you might lose input values while programs are running.

You also said multithreading would be possible... but I'm wondering, how do you do this then?

|send>(ifz^(^,^)):::|:sendv(>)::sendv(<)|send<(sub(^,sub(^,^))):::
|......................|--Do something--:::|

or ACTG notation if you prefer:
|C(C,A(A,G(A),G(A))):::|:C(T,C)::C(T,G)|C(G,A(A,G(A),G(A))):::
|...........................|--Do somethn:::|

Which value gets in B2 first?

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Esoteric Language Idea

Postby quintopia » Thu Nov 15, 2007 5:05 pm UTC

Yes, you're right. I think I may have had that green part in there at some point, but for some reason removed it and forgot to put it back. And yes, the two C(T,G(T)) on row 2 are useless. . .also byproducts of a previous version of the code. (Oh, twopence for an interpreter to test on!) However, the two C(T, in B3 are absolutely needed as the conditional test in B4 will consume the message testing it the first time it gets it, and won't have anything left to send back (to indicate a halt) if the message is not sent again.

M.qrius wrote:Do you mean by that that every message sent during that time goes into void, or that it just waits until it gets its value, then continues working on the next message?


The latter, obviously. I'm pretty sure RockHawk is implementing it this way. . .it's not only more useful, but more natural to implement.

M.qrius wrote:Which value gets in B2 first?

First of all, you misused the A command here. A(A, is illegal. I'll assume you meant A(G(A),

If *do something* needs to behave differently depending on whether its input came from the left or right branch, then in a multi-threaded environment, your program is a good example of a race condition, which is something that all programmers for multi-threaded apps must avoid, precisely because the results are unpredictable. Thus, it is the responsibility of the CellBrain programmer to avoid writing such programs, and not CellBrain's responsibility to fix such mistakes.

RockHawk
Posts: 19
Joined: Sun Nov 11, 2007 6:30 pm UTC

Re: Esoteric Language Idea

Postby RockHawk » Sat Nov 17, 2007 3:11 pm UTC

Hi guys,

Sorry for the lack of activity for the last couple of days - real life got busy!

I've got something which I think is good enough to post now. I've changed it to use ASCII according to quintopia's original ideas. Included are the decrement program ("dec.cb") and the adder ("test.cb").

Usage is:
./cellbrain.py [-v] <cellbrain input file>

Then enter strings of characters to process. Nothing will actually happen until you press Enter, then all characters on the line are sent in to the top row. If the optional "-v" verbose flag is given you can see the messages propagating around the cells. Termination should happen if any message is sent to the input row, or you can get out with Ctrl-C.

As for the implementation, there are four queues per cell, and they pop immediately if the cell is not blocked. I know there is a window condition where a message delivery won't cause the cell to pop if it has only just become unblocked, but I haven't quite worked out the best way to deal with it yet - the current implementation works for simple programs, let me know if you see odd things happening.

I've only tested it on Linux, but there's no reason it shouldn't work on Windows if you've got Python installed.

Let me know how it goes!

Edit: Deleted attachment as it is very bugged - download the one below.
Last edited by RockHawk on Sun Nov 18, 2007 12:01 pm UTC, edited 1 time in total.

User avatar
M.qrius
Rainbow Brite
Posts: 519
Joined: Sat Nov 10, 2007 12:54 am UTC
Location: Rainbow's end
Contact:

Re: Esoteric Language Idea

Postby M.qrius » Sat Nov 17, 2007 3:52 pm UTC

The supplied test.cb works for me (python under windows, but with unix newlines), but the dec.cb doesn't work. For one, there's an error in A3: C(C,G(A)):C(G,G(C)):: should be C(C,G(A)):C(C,G(C))::
Spoiler:
D:\Esoteric Languages\Cellbrain\Cellbrain Debugger>cellbrain.py -v dec1.cb
Message 49 sent from (Input) to A1
Message 49 sent from (Input) to B1
Message 49 sent from (Input) to C1
Message 49 sent from (Input) to D1
Message 49 sent from (Input) to E1
Message 49 sent from (Input) to F1
Message 49 sent from (Input) to A1
Message 49 sent from (Input) to B1
Message 49 sent from (Input) to C1
Message 49 sent from B1 to B2
Message 49 sent from (Input) to D1
Message 49 sent from (Input) to E1
Message 49 sent from (Input) to F1
Message 48 sent from (Input) to A1
Message 48 sent from (Input) to B1
Message 48 sent from (Input) to C1
Message 48 sent from (Input) to D1
Message 48 sent from (Input) to E1
Message 1 sent from D1 to D2
Message 48 sent from (Input) to F1
Message 1 sent from D2 to D3
Message 1 sent from D3 to D4
Message 1 sent from D3 to C3
Message 1 sent from D4 to D3
b
Message 98 sent from (Input) to A1
Message 98 sent from (Input) to B1
Message 98 sent from (Input) to C1
Message 98 sent from B1 to B2
Message 98 sent from (Input) to D1
Message 98 sent from B2 to B3
Message 98 sent from (Input) to E1
Message 98 sent from (Input) to F1
Message 98 sent from B3 to C3
Message 97 sent from C3 to B3
Message 97 sent from C3 to D3
Message 97 sent from B3 to C3
Message 97 sent from C3 to C4
Message 97 sent from C3 to C4
After that it's waiting for input.

RockHawk
Posts: 19
Joined: Sun Nov 11, 2007 6:30 pm UTC

Re: Esoteric Language Idea

Postby RockHawk » Sat Nov 17, 2007 5:57 pm UTC

Yes you're right, sorry I introduced a bug while I was trying to sort out empty cells. Just delete these lines:

Code: Select all

      if self.code[i] == "":
        self.code[i] = "G" + Cell.letters[i]

From lines 26 and 27 of cell.py.

However, if you do this it doesn't terminate. The problem being that cell B3 is blocked in it's receive from left (waiting on input from up) when the receive from down happens. I've solved this by piping the terminate message all the way round the side:

Code: Select all

init:110
C(T,A(G(A),G(A),G(A)):::         |:::                                                                |C(T,A(G(A),G(C),T(G(A),G(A))):::|::CAGT:
C(T,A(G(A),G(A),G(A))::C(T,G(T)):|:::                                                                |C(T,G(A))::C(T,G(T)):           |::CAGT:
C(C,G(A)):C(C,C(G,G(C)))::       |:C(T,C(T,C(C,C(G,T(G(G),G(C))))))::C(T,C(T,C(C,C(G,T(G(G),G(C))))))|C(G,C(T,G(A))):::C(G,C(T,G(T))) |::CAGT:
                                 |A(G(A),C(C,G(A)),G(A)):::                                          |C(A,G(A)):::C(C,G(G))           |:::CAGG


It actually manages to print -1 before the program terminates, but it's basically working now.

RockHawk
Posts: 19
Joined: Sun Nov 11, 2007 6:30 pm UTC

Re: Esoteric Language Idea

Postby RockHawk » Sat Nov 17, 2007 6:02 pm UTC

Ah, one thing you probably don't want to print all those special characters to your console!

Attached version has the bug fix and a change to print (number) instead of the character if it's unprintable.
Attachments
cellbrain.tar.gz
Cellbrain interpreter v2
(2.33 KiB) Downloaded 177 times

User avatar
M.qrius
Rainbow Brite
Posts: 519
Joined: Sat Nov 10, 2007 12:54 am UTC
Location: Rainbow's end
Contact:

Re: Esoteric Language Idea

Postby M.qrius » Sat Nov 17, 2007 6:13 pm UTC

It's working now, although the time it exits is very variable (but I blame that on the program design, not the debugger :P)
In some cases, however, it doesn't end at all. Here's the output:
Spoiler:
--snip--
Out: (9)
Message 9 sent from B3 to B4
Message 9 sent from A3 to B3
Message 1 sent from C3 to C4
Message 9 sent from B3 to B4
Message 1 sent from C3 to B3
Message 1 sent from C4 to C3
Message 8 sent from B3 to A3
Message 8 sent from B3 to C3
Out: (8)
Message 8 sent from A3 to B3
Message 8 sent from B3 to B4
Message 1 sent from C3 to C4
Message 8 sent from B3 to B4
Message 1 sent from C3 to B3
Message 7 sent from B3 to A3
Message 1 sent from C4 to C3
Message 7 sent from B3 to C3
Message 7 sent from B3 to B4
Out: (7)
Message 7 sent from A3 to B3
Message 1 sent from C3 to C4
Message 7 sent from B3 to B4
Message 1 sent from C3 to B3
Message 1 sent from C4 to C3
Message 6 sent from B3 to A3
Message 6 sent from B3 to C3
Out: (6)
Message 6 sent from A3 to B3
Message 6 sent from B3 to B4
Message 6 sent from B3 to B4
Message 1 sent from C3 to C4
Message 1 sent from C3 to B3
Message 5 sent from B3 to A3
Message 5 sent from B3 to C3
Message 1 sent from C4 to C3
Out: (5)
Message 5 sent from B3 to B4
Message 5 sent from A3 to B3
Message 1 sent from C3 to C4
Message 5 sent from B3 to B4
Message 1 sent from C3 to B3
Message 4 sent from B3 to A3
Message 1 sent from C4 to C3
Message 4 sent from B3 to C3
Message 4 sent from B3 to B4
Out: (4)
Message 4 sent from A3 to B3
Message 1 sent from C3 to C4
Message 4 sent from B3 to B4
Message 1 sent from C3 to B3
Message 1 sent from C4 to C3
Message 3 sent from B3 to A3
Message 3 sent from B3 to C3
Out: (3)
Message 3 sent from A3 to B3
Message 3 sent from B3 to B4
Message 1 sent from C3 to C4
Message 3 sent from B3 to B4
Message 1 sent from C3 to B3
Message 1 sent from C4 to C3
Message 2 sent from B3 to A3
Message 2 sent from B3 to C3
Out: (2)
Message 2 sent from B3 to B4
Message 2 sent from A3 to B3
Message 2 sent from B3 to B4
Message 1 sent from C3 to C4
Message 1 sent from C3 to B3
Message 1 sent from C4 to C3
Message 1 sent from B3 to A3
Message 1 sent from B3 to C3
Out: (1)
Message 1 sent from A3 to B3
Message 1 sent from B3 to B4
Message 1 sent from C3 to C4
Message 1 sent from B3 to B4
Message 1 sent from C3 to B3
Message 0 sent from B3 to A3
Message 1 sent from C4 to C3
Message 0 sent from B3 to C3
Out: (0)
Message 0 sent from A3 to B3
Message 0 sent from B3 to B4
Message 0 sent from B3 to B4
Message 1 sent from C3 to C4
Message 0 sent from B4 to C4
Message 1 sent from C3 to B3
Message -1 sent from B3 to A3
Message 1 sent from C4 to C3
Message -1 sent from B3 to C3
Out: (-1)
Message -1 sent from A3 to B3
Message -1 sent from B3 to B4
Message 1 sent from C3 to C4
Message -1 sent from B3 to B4
Message 1 sent from C3 to B3
Message 1 sent from C4 to C3
Message -2 sent from B3 to A3
Message -2 sent from B3 to C3
Out: (-2)
Message -2 sent from A3 to B3
Message -2 sent from B3 to B4
Message 1 sent from C3 to C4
Message -2 sent from B3 to B4
Message 1 sent from C3 to B3
Message -3 sent from B3 to A3
Message 1 sent from C4 to C3
Message -3 sent from B3 to C3
Out: (-3)
Message -3 sent from A3 to B3
Message -3 sent from B3 to B4
Message 1 sent from C3 to C4
Message -3 sent from B3 to B4
Message 1 sent from C3 to B3
Message 1 sent from C4 to C3
Message -4 sent from B3 to A3
Message -4 sent from B3 to C3
Message -4 sent from B3 to B4
Out: (-4)
Message -4 sent from A3 to B3
Message 1 sent from C3 to C4
Message -4 sent from B3 to B4
Message 1 sent from C3 to B3
Message 1 sent from C4 to C3
Message -5 sent from B3 to A3
Message -5 sent from B3 to C3
Out: (-5)
--snip--
Then it keeps on going until I break it.
It seems like the zero is getting to C4, but isn't forwarded from there...

RockHawk
Posts: 19
Joined: Sun Nov 11, 2007 6:30 pm UTC

Re: Esoteric Language Idea

Postby RockHawk » Sat Nov 17, 2007 6:35 pm UTC

I suspect that is because you hit the window where C4 is "blocked" waiting for input from C3, even though input is actually available. This is the subtle problem I mentioned earlier. I'll have a think about the best way to solve it - moral of the story is you can't get away with writing code without really thinking it through properly when multi-threading is involved :-)

The easiest solution is just to drive termination off the input to A3, as then you are never trying to route 2 messages through the same cell simultaneously, like so:

Code: Select all

init:110
C(T,A(G(A),G(A),G(A)))::C(A,G(T)):          |:::                                                                |C(T,A(G(A),G(C),T(G(A),G(A))):::
C(T,A(G(A),G(A),G(A)))::C(A,G(T)):          |:::                                                                |C(T,G(A))::C(T,G(T)):
C(C,G(A)):C(C,C(G,A(G(C),C(A,G(C)),G(C))))::|:C(T,C(C,C(G,C(G,T(G(G),G(C))))))::C(T,C(C,C(G,C(G,T(G(G),G(C))))))|C(G,C(T,G(A))):::C(G,C(T,G(T)))
                                            |C(A,G(A)):::                                                       |C(A,G(A)):::C(C,G(G))

I've run this a few times and it hasn't yet got past 0. This is as expected because the exit path is now shorter.

User avatar
M.qrius
Rainbow Brite
Posts: 519
Joined: Sat Nov 10, 2007 12:54 am UTC
Location: Rainbow's end
Contact:

Re: Esoteric Language Idea

Postby M.qrius » Sat Nov 17, 2007 7:02 pm UTC

That new program gives me loads of blocked bugs...
Personally I was thinking about solving the -1 print problem roughly like this:

Code: Select all

init:110
C(T,A(G(A),G(A),G(A)):::         |:::                                                 |C(T,A(G(A),G(C),T(G(A),G(A))):::|::CAGT:
C(T,A(G(A),G(A),G(A))::C(T,G(T)):|:::                                                 |C(T,G(A))::C(T,G(T)):           |::CAGT:
C(C,G(A)):C(C,C(G,G(C)))::       |:C(T,C(T,G(G)))::A(G(T),G(T),C(C,C(G,T(G(G),G(C)))))|C(G,C(T,G(A))):::C(G,C(T,G(T))) |::CAGT:
                                 |A(G(A),C(C,G(A)),C(A,G(A))):::                      |C(A,G(A)):::C(C,G(G))           |:::CAGG

B3 doesn't continue if it doesn't get a value from B4.
The program doesn't work however... Not sure why.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Esoteric Language Idea

Postby quintopia » Mon Nov 19, 2007 1:27 am UTC

I've been thinking about this process-starvation-due-to-blocking problem, and here's how I would handle it (implementation-wise):

Since we are retaining all incoming messages while blocking, it only makes sense to process all messages that built up in the order they were received. There are (at least) two ways to ensure this:

1) Associate every message with a timestamp (easiest done with a Message object of some sort) and, after each message is processed, check all four queues for a new message, picking the oldest and processing it. If none have messages, sleep or expire thread.

2) Create a 5th queue that receives location-message-from directives every time a message is received, and have this queue be the only one that can trigger events in a cell. The event handlers retrieve the top directive, and then get the message associated with it.


Notice how similar the second looks to standard OO eventqueue implementations. I think it a very clean solution.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 5 guests