From Esolang
Jump to: navigation, search

This is actually a pretty cool language. I was expecting Yet Another BF Derivative at first, but this is really well-executed. Nice work! —ehird 22:01, 12 June 2011 (UTC)

Thanks for the compliment. I always wondered what a language based on binary trees would look like, so I decided to try my hand at it. I am working on an interpreter in Common Lisp, so if any lispers want to help, that would be great.--DocHerrings 23:42, 12 June 2011 (UTC)
Your language has won the inaugural A Brainfuck Derivative That Doesn't Make Me Want To Kill You Award. It also seems like it's asking to have a combinator graph reduction program in it. Phantom Hoover 13:00, 14 June 2011 (UTC)
Combinator graph reduction would actually be harder than I thought, because there's no easy way of copying or moving subtrees to arbitrary locations. Phantom Hoover 13:12, 14 June 2011 (UTC)
Oh wow. Having taken a peek at your user page, that sounds like high praise. The BF derivatives do get tiring. I just wanted to see if I could translate bounded but extensible storage into infinite storage. And something that interests me, although I am going to have to complete the interpreter before anyone can accurately investigate it, is that the shape of the tree is a way of storing state.--DocHerrings 13:28, 14 June 2011 (UTC)
If you're interested in storing state purely in the tree, you might want to look at Eodermdrome. Phantom Hoover 16:33, 14 June 2011 (UTC)

Quick clarification questions: For the paradox functions, do they try creating the non-favored child node if the favored child node already exists? For the conditional movers, are the four lines of conditional actions in the description tried in order until one succeeds? About Turing-completeness: The current "setup" seems insufficient, because with only finite number of cells times finite possible values per cell equals finite number of possible states, it can't be truly Turing complete. (I mean, I think Arborealis is TC, but the current proof isn't.) Thanks! —Maharba 01:22, 13 June 2011 (UTC)

I suppose I shall address your questions in order, and then clarify the specs for accuracy. The paradox functions do not create a child node in the case that the favored child does not exist. As for the conditional movers, your guess is correct - the conditions are checked in the order presented, with the first feasible one being executed. Your final point raises an interesting question - I have proven isomorphism with brainfuck, albeit with limitations. The question is, since brainfuck self-interpreters have been written, can I claim Turing completeness via simulation? And the size of the generated tape is honestly trivial. By chaining the generating loops together, it is possible to create a tape of arbitrary length. I suppose the final challenge would be to prove that ? or ! could be used in place of > and < in when the tape is in danger of being too short.--DocHerrings 01:42, 13 June 2011 (UTC)
Oh -- your isomorphism only simulates a BF with infinite tape? Sorry, then the language is not proved Turing complete by that. Plenty of languages would allow construction of an arbitrary fixed finite tape but no more; those languages, however, are not Turing complete. —ehird 02:50, 13 June 2011 (UTC)
The difficulty lies in the fact that ? and ! can expand the tape dynamically, creating a tape that never ends, because it is built as the program approaches the end. Since brainfuck can not move more then one cell per op, would it be safe to say that if all instructions are followed by +[->}]? then the tape will never end?--DocHerrings 02:56, 13 June 2011 (UTC)
Yep, that seems about right. —ehird 03:01, 13 June 2011 (UTC)
This language is nice but I just can't see the brainfuck translation working properly yet... For example, a brainfuck program like >+<++>< would end in the very first memory cell with value 2 in it. A program in this language, with the current translation rules, would end up in a node with 0 as its value. Unless I'm doing something wrong. Generally, I don't see the < translation working properly. --Keymaker 21:13, 13 June 2011 (UTC)
In Arborealis, that program would be \>(+<++\>(< which we can walk through, step by step. It begins in root node A (value 0) with no children. The \ creates A's right child B with value 0, the > moves to it, and the ) makes B's left child A. The + adds 1 to B (value now 1), then the < moves to B's left child, A (value 0). The two + commands add two to A (value now 2). The \ command does nothing as A already has a right child. The > command moves to this child, B. The ) command does nothing as B already has a left child, A. The < command moves to B's left child, A, which has value 2. The program is then done. The < translation works because of the paradox functions. —Maharba 21:46, 13 June 2011 (UTC)
Thanks, I see it now -- I had misunderstood the paradox functions; I thought they just took a copy of the entire tree and placed it as a new node but I see it's something different -- a great, 'esoteric' idea there! --Keymaker 23:10, 13 June 2011 (UTC)

Keymaker, I have made a slight change to your cat function - the final loop will never end unless the EOF is 0. I have changed it very slightly so that now, before it returns the pointer to the root node, it generates one extra right child. This will guarantee execution ends when all the input has been echoed back.--DocHerrings 23:35, 13 June 2011 (UTC)

Actually, there's no need to. See; On zero-length input, the first and only node remains zero (or becomes zero, whatever EOF actually is in this language). The two other loops are never executed, program reaches end. On input that's one character or more, the following happens: First read the first character, then enter the first loop. In the loop first create a new right node (value 0 initially), then move to it, then get input again. If the new input is non-zero, continue the loop again. If the new input is zero (EOF=0 or EOF=no change), the loop ends, and the new node remains a zero. This point is eventually always reached (unless you have infinite input, and in that case running a cat becomes a bit pointless), and thus, there's always a node at the end that is a zero. So the second loop always ends, too. So adding a \ to the original program actually isn't necessary. ;) By the way, I hope the interpreter's coming along well... --Keymaker 09:06, 14 June 2011 (UTC)

Skeleton outline of Arborealis interpreter is on Pastebin. Feel free to improve the code, critique, or continue working on it. This is as far as I have gotten in about an afternoon - I will finish it, just don't have the time right now :).--DocHerrings 17:27, 14 June 2011 (UTC)

Glanced at the code. I haven't done much with Lisp (one class in DrScheme and that's it), but here are some thoughts:
  • Should the paradox and child creation functions use copy-list? The spec specifically says that the paradox functions do not create a copy.
  • (You already know this, but) it needs some way of actually parsing Arborealis commands, to use all these functions you've written.
  • In the conditional movers, on an error, besides printing "How did you get here?" it should probably exit.
  • Probably others.
Again, I don't know much Lisp so I may be misinterpreting these. —Maharba 18:47, 14 June 2011 (UTC)
I'll admit, I just threw the code together, so I wouldn't even call it functional yet, but I suppose I will answer your questions:
  • copy-list is actually perfect for the paradox functions, because it does not copy sublists. Instead, it creates a new list who's car point to the original sublists. Every node consists of a list of sublists, with the sublists being (parent) (value) (left child) (right child). So:
(copy-list nodeA) -> []->[]->[]->[]
                      \   \   \   \
                      AP  AV  AL  AR
                      /   /   /   /
           nodeA  -> []->[]->[]->[]
  • Like I said, rough draft.
  • That's a joke. :) It won't make it into the final version.
  • I will finish this, but some people might want to play with the language NOW, so I thought I would provide them with what I had already done.--DocHerrings 19:20, 14 June 2011 (UTC)

I've started on an interpreter in Python. A couple details that have come up: What happens if you try and use a paradox function at the root node? (I assume nothing.) What value does EOF have? (I assume 0.) —Maharba 21:51, 14 June 2011 (UTC)

Using a paradox function from the root node results in the root node (the root node is treated as its own parent). Your assumption about the EOF is fine.--DocHerrings 02:00, 15 June 2011 (UTC)
I have the interpreter working except for I/O (I'm having some difficulty with Python's buffering). —Maharba 01:27, 15 June 2011 (UTC)
I fixed the IO and will upload the interpreter as soon as I've documented it properly! –Maharba 04:50, 15 June 2011 (UTC)
Interpreter finished. I've uploaded it here. —Maharba 18:35, 15 June 2011 (UTC)

I've written an interpreter in C, available on Github here. It's still in its early stages, and I don't have many Arborealis programs to test it with, so please feel free to submit your own programs! Dweymouth (talk) 17:04, 5 July 2014 (UTC)

DocHerrings, if you're still involved with this language, I'm just curious: why did you decide not to include an instruction to move to the parent of the current node (say '^')? I understand you can approximate a BF tape with the paradox functions but having a move-to-parent instruction would make traversal of a more complex tree structure much easier. (Of course, it means a little overhead for interpreters to keep track of each node's parent, rather than just the previous node visited.) Dweymouth (talk) 05:57, 9 July 2014 (UTC)