flat assembler
Message board for the users of flat assembler.

Index > Programming Language Design > Challenger Interpreter

Goto page 1, 2, 3  Next
Author
Thread Post new topic Reply to topic
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 8356
Location: Kraków, Poland
Tomasz Grysztar 30 Aug 2009, 19:42
A recent thread about the Befunge programming language inspired me to design another language, similar but with quite different ideology.

The main similarity to Befunge is the instruction flow on the two-dimensional characters plane. However, as opposed to Befunge, this language is register-based, and generally a bit inspired by the architecture of processors like x86 family. Also there are no input and output instructions - as the character plane serves similar role to memory in x86 system, you can use some parts of it to present the output, a bit like you'd be writing to video memory. Well, since this memory is two-dimensional, you could even try some drawing on it. The interpreter displays the contents of character plane in real time, thus you may see everything that happens there at any moment.

Because of it being inspired by both *Funge languages and x86 architecture, I first thought of naming it like Funge-86. However, as this reminded me of year 1986, when some memorable events took place, I decided to choose a name after one of those events, which is - in my feeling - less remembered than others, though I recall it clearly that I was watching it happening on TV when I was a small child. So, remembering the space shuttle that disintegrated in 1986, I named this language Challenger.

Each memory cell is a 32-bit signed value, presented as Unicode character. (This causes some problem with current implementation, because I've discovered that even with fixed pitch font in Windows not every character has the same width - if someone has a good idea how to correct this, please let me know).
The program is loaded from UTF-8 text file and initializes this way some area on plane. The plane will be expanded in any direction when needed.

There are two main pointers operated by Challenger machine, the instruction pointer (IP) and data pointer (DP). The pointer not only determines the character cell on the plane, but also the direction of movement. The direction of IP is always specified directly, while direction of DP is always specified as rotation of the previous one. Both the IP and DP begin in the left upper corner of program code, with direction of moving right. Apart from this pointers, the machine has just one register, accumulator (A), which is used to perform the arithmetic operations and condition testing.

The basic instruction set is:
Code:
>    Set IP direction to "right"
<    Set IP direction to "left"
^    Set IP direction to "up"
v    Set IP direction to "down"
|    Set IP direction to "down" if A=0, "up" otherwise
_    Set IP direction to "right" if A=0, "down" otherwise
.    Move DP one cell forward
:    Move DP forward by amount of cells specified in A
)    Rotate DP direction clockwise
(    Rotate DP direction counterclockwise
=    Set DP to be the same as IP
\    Exchange A with cell at DP
+    Add value of cell at DP to A
-    Substract value of cell at DP from A
*    Multiply A by value of cell at DP
/    Divide A by value of cell at DP
%    Calculate A modulo value of cell at DP
`    Load sign of value in A (so if A<0, set A=1; set A=0 otherwise)
"    Load immediate value (the character that follows this instruction) to A - this is the only instruction that takes more than one character
0-9  Load corresponding value in range 0-9 into A
A-F  Load corresponding value in range 10-15 into A (hexadecimal digits)    


Now some examples. This simple example (which is included in the interpreter package) writes the characters in range A-Z in the area just below the code:
Code:
)3:("A\>1+.\v
       | -Z"<
       >    
I suggest to simply download the interpreter and trace this program step by step to see how the things work. You should get the general idea on what this language is like.

Because there's just one register and one data pointer, tt's not so easy to get anything done with it. Here's my try at writing the program that would copy the string of characters from one place to another:
Code:
  v
v           <     <
  >=)3:1\0-\^
   >..1+\       v
     v          <
>=" : >)5:0+=).\^
   " =v)7: " \0+v
   = >(.\(.\((.\  ^
   |       -.)= <
   <
This string has to end with dot.    
The self-modifying code is the only way to do it with this basic set of instructions.

Thus, to make things at least a tiny little bit easier, I decided to add additional pointer and a few instructions operating on it. It's the stack pointer (SP), therefore you operate on it with "push" and "pop" instructions.
This additional instruction set is:
Code:
!    Move SP backwards by one cell, and write A at this new position ("push" instruction)
?    Read A from cell at SP and move SP forward by one cell ("pop" instruction)
,    Move SP one cell forward
;    Move SP forward by amount of cells specified in A
]    Rotate SP direction clockwise
[    Rotate SP direction counterclockwise
@    Set SP to be the same as IP    

I personally call the Challenger language extended with these instructions the "Framed Challenger" (thanks to stack frame), opposed to "Pure Challenger" described before. Of course writing anything interesting with Pure Challenger is much more challenging. ;) The program that copies string from one place to another written in Framed Challenger may look like this:
Code:
)4:(]3;[>?\"!-.|
               <
        ^      <
Hello!    

If you want, you may also try implementing your own additional instructions - I think it's quite easy to extend the interpreter I've written.

Some final notes:
  • Both the 0 and 32 (space) are NOP instructions.
  • The uninitialized parts of plane are filled with 0 values.
  • The initial value of accumulator is 0.
  • There are no absolute coordinates in this language - everything is relative. For the data and stack pointers even the directions are relative.
  • The interpreter displays the pointers with tiny arrows - the instruction pointer is green, data pointer is red, stack pointer is yellow.
  • Note that the instruction pointer wraps when it reaches the end of the initialized part of the plane.
  • There are two exceptions that may happen - division by zero and invalid opcode. The interpreted halts when any of them occurs and the machine cannot be resumed from such state. You can utilize it to end your program if you'd like to.
  • Maybe I should also add some option to recognize the Pure Challenger and Framed Challenger programs?
  • The execution at maximum speed is still a bit slow - that's because of the constant refreshing of windows. Without the GUI overhead it would be much faster, but you wouldn't be able to see what's going on.
  • As this is a very fresh idea, I may still make some modifications to the language. Though I will perhaps try to leave it compatible with the program written so far.


EDIT: Uploaded a new version of interpreter. It has an improved drawing algorithm (and it is no longer is prone to errors due to some characters having different width), and adds two new instructions to the basic set:
Code:
#    Make IP skip the next cell ("trampoline")
x    Generate an exception to stop program flow ("trap")    

At first I forgot about trampoline, and it's a nice thing to have.
As for the trap, you may use it to stop your program.

Also one instruction added to the Framed instruction set:
Code:
&    Exchange DP with SP    
I didn't need to use it so far, but I think it may come in handy sometimes.


Description: Challenger Intepreter for Windows
version 1.01

Download
Filename: challenger.zip
Filesize: 14.04 KB
Downloaded: 1507 Time(s)

Post 30 Aug 2009, 19:42
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 8356
Location: Kraków, Poland
Tomasz Grysztar 30 Aug 2009, 19:45
And now some more interesting example - this is a program written in Pure Challenger, which copies itself into a new place below, and executes its own copy:
Code:
 v>..1+\)4:1\0-\((4:0+5-  v>v
v                    < <  >|
 >  =)3:5\0-\(4:1\0-\^   >v <
        >..1+\0+=).\F-\F+|
  ^ <     v      "   <    <
>=)" :(" : >)0:0+=).\^
    "   " =v)A: " \  v
    =   = >(.\(.\((.\  ^
        ^            <
 v  ^                    < >    
It's a kind of "worm", that will slowly chew through the plane towards the infinity. :)
Anyone cares to try making a similar one in Framed Challenger? I'm already too tired after writing the interpreter. ;)

This makes me think that it could be interesting to allow multi-threading on such plane. You could even get some programs competiting for areas. Reminds me a fascinating text about Tierran Mutants I once read.
Post 30 Aug 2009, 19:45
View user's profile Send private message Visit poster's website Reply with quote
Pinecone_



Joined: 28 Apr 2008
Posts: 180
Pinecone_ 31 Aug 2009, 03:10
Very good Tomasz, but I think you need an instruction to end the scripts execution.
Post 31 Aug 2009, 03:10
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 20363
Location: In your JS exploiting you and your system
revolution 31 Aug 2009, 03:17
Tomasz Grysztar wrote:
This makes me think that it could be interesting to allow multi-threading on such plane. You could even get some programs competiting for areas. Reminds me a fascinating text about Tierran Mutants I once read.
Also the Core Wars did this.
Post 31 Aug 2009, 03:17
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 8356
Location: Kraków, Poland
Tomasz Grysztar 31 Aug 2009, 07:26
Pinecone_ wrote:
Very good Tomasz, but I think you need an instruction to end the scripts execution.

No, I don't. Does the x86 CPU has any instruction to "end the execution"? Wink Well, you can halt the Challenger machine with an exception anyway (as I wrote in the notes above) if you really wish to.
Post 31 Aug 2009, 07:26
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 8356
Location: Kraków, Poland
Tomasz Grysztar 31 Aug 2009, 07:29
revolution wrote:
Tomasz Grysztar wrote:
This makes me think that it could be interesting to allow multi-threading on such plane. You could even get some programs competiting for areas. Reminds me a fascinating text about Tierran Mutants I once read.
Also the Core Wars did this.

If you read that page I linked to (and I strongly recommend it, it's really an interesting one) you're going to find Core Wars mentioned, too.


Last edited by Tomasz Grysztar on 31 Aug 2009, 07:31; edited 1 time in total
Post 31 Aug 2009, 07:29
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 20363
Location: In your JS exploiting you and your system
revolution 31 Aug 2009, 07:30
Tomasz Grysztar wrote:
Does the x86 CPU has any instruction to "end the execution"?
Well it kind of does, a triple fault can be invoked with 'int3' (once other conditions have been properly applied of course). Wink
Post 31 Aug 2009, 07:30
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 8356
Location: Kraków, Poland
Tomasz Grysztar 31 Aug 2009, 07:33
revolution wrote:
Tomasz Grysztar wrote:
Does the x86 CPU has any instruction to "end the execution"?
Well it kind of does, a triple fault can be invoked with 'int3' (once other conditions have been properly applied of course). Wink

So, as you see, choosing exception to be the only way to halt the Challanger machine was not a half-baked decision. Wink
Post 31 Aug 2009, 07:33
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 20363
Location: In your JS exploiting you and your system
revolution 31 Aug 2009, 07:34
Tomasz Grysztar wrote:
If you read that page I linked to (and I strongly recommend it, it's really an interesting one) you're going to find Core Wars mentioned, too.
Embarassed
Post 31 Aug 2009, 07:34
View user's profile Send private message Visit poster's website Reply with quote
rugxulo



Joined: 09 Aug 2005
Posts: 2341
Location: Usono (aka, USA)
rugxulo 31 Aug 2009, 07:55
Tomasz Grysztar wrote:

| Set IP direction to "down" if A=0, "up" otherwise
_ Set IP direction to "right" if A=0, "down" otherwise

[*] The | and _ commands work exactly the opposite way as the same commands in Befunge. I felt that this variant is better.


This confuses me. Especially since Befunge says this:

Quote:

_ Pop a value; move right if value=0, left otherwise
| Pop a value; move down if value=0, up otherwise


I suspect a typo, but I am easily confu^H^H^H^H^H Befunged without trying it first. Wink
Post 31 Aug 2009, 07:55
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 8356
Location: Kraków, Poland
Tomasz Grysztar 31 Aug 2009, 08:10
rugxulo wrote:
I suspect a typo, but I am easily confu^H^H^H^H^H Befunged without trying it first. Wink

Oh, you're right. I misread the Befunge docs. Embarassed
But that's good, so I'm not that different still. Very Happy
Post 31 Aug 2009, 08:10
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6115
Location: Poland
MHajduk 31 Aug 2009, 08:32
Very good work, Tomasz. I liked especially the idea of the visualisation of the interpreting process (this interpreter becomes also some kind of Challenger debugger that way Wink).

Some user remarks:
  • As it was said already, optional "stop" instruction would be a good idea (it would be even necessary for some scripts).

  • Maybe it would be better to integrate Challenger plane with the Challenger controller (all controls in one window)?

  • Accordingly to the characters alignment: you could divide Challenger plane into square cells (maybe show even the grid lines?) and center every character horizontally inside them.

  • Addition of the (optional) "tick" sound signal for every interpreter step would be an advantage.
Post 31 Aug 2009, 08:32
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 8356
Location: Kraków, Poland
Tomasz Grysztar 31 Aug 2009, 08:49
MHajduk wrote:
As it was said already, optional "stop" instruction would be a good idea (it would be even necessary for some scripts).
Just generate an exception. Wink However I may want to define some guaranteed character for this, like "trap" instruction.

MHajduk wrote:
Maybe it would be better to integrate Challenger plane with the Challenger controller (all controls in one window)?

You mean, like with toolbar? I've chosen this separate "palette-like" window, because I like the ability to move it anywhere independently.

MHajduk wrote:
Accordingly to the characters alignment: you could divide Challenger plane into square cells (maybe show even the grid lines?) and center every character horizontally inside them.

But this would make drawing extremely slow, as I would need a separate TextOut for each character.

MHajduk wrote:
Addition of the (optional) "tick" sound signal for every interpreter step would be an advantage.
Adding it to may TODO list. Smile
Post 31 Aug 2009, 08:49
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6115
Location: Poland
MHajduk 31 Aug 2009, 09:13
Tomasz Grysztar wrote:
MHajduk wrote:
Accordingly to the characters alignment: you could divide Challenger plane into square cells (maybe show even the grid lines?) and center every character horizontally inside them.
But this would make drawing extremely slow, as I would need a separate TextOut for each character.
I've just got another (maybe crazy Wink ) idea: you really don't need to draw anything. You can store all used characters as predefined icons (for example 32 x 32 in dimensions) and place them dynamically in the proper coordinates of the Challenger plane. It should be much faster than use of 'TextOut' function (you can just exchange pointers to the proper icons when needed).

What do you think about it?
Post 31 Aug 2009, 09:13
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 8356
Location: Kraków, Poland
Tomasz Grysztar 31 Aug 2009, 10:20
I was thinking about it, but generating 65536 icons at program startup would take some noticeable time. (BTW, do you know if it's possible in Windows to draw Unicode characters with codes larger than 10000h?).

Anyway, I used a separate TextOut for each character, however combined with checking, whether the character is inside an update region, and not issue TextOut at all if it's not. I got a decent speed this way, and got rid of the problem with variable widths as well.

I edited first post with the new version of interpreter. It also add a two new instructions (including a "trap", so you now have some "official" exception for program termination Wink).
Post 31 Aug 2009, 10:20
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 20363
Location: In your JS exploiting you and your system
revolution 31 Aug 2009, 10:24
Tomasz Grysztar: Perhaps you can consider disabling smilies in code sections? Your code in the first post is broken because of the smilies.
Post 31 Aug 2009, 10:24
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 8356
Location: Kraków, Poland
Tomasz Grysztar 31 Aug 2009, 10:26
revolution wrote:
Tomasz Grysztar: Perhaps you can consider disabling smilies in code sections? Your code in the first post is broken because of the smilies.
Hmm, right, so it seems I just discovered another bug in phpBB - when I use attachment panel to upload a new version of attachment, the smilies are "magically" re-enabled. Very Happy
Post 31 Aug 2009, 10:26
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 20363
Location: In your JS exploiting you and your system
revolution 31 Aug 2009, 10:28
Perhaps make it a forum wide thing. I don't think any code section needs smilies enabled (except for some posts in the "test" section of course).
Post 31 Aug 2009, 10:28
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 8356
Location: Kraków, Poland
Tomasz Grysztar 31 Aug 2009, 10:34
Are you tellling me to dig into PHP code once again? Sigh... And the Challenger is much more fun! ;)

A new version of Framed Challenger string copy program, which uses the newly added # and x instructions:
Code:
)3:(]2;[>?\"!-.v
x       ^   _ #<
Hello!    

And a funny little one that runs around the clock:
Code:
(.)>"A\>1+.\v
       | -Z"<
   ^ ).<    

And this one draws a spiral:
Code:
(.)[F!!>"+\0+.v
       !
  >!)  |-?\1  <
  ^+?\1<    


One more instruction, adding of which I consider, is the one that would exchange the DP with SP. What do you think?
Post 31 Aug 2009, 10:34
View user's profile Send private message Visit poster's website Reply with quote
ManOfSteel



Joined: 02 Feb 2005
Posts: 1154
ManOfSteel 31 Aug 2009, 15:38
Tomasz Grysztar wrote:
Reminds me a fascinating text about Tierran Mutants I once read.

Very interesting article. Truly fascinating, especially the part about Tierra. Thanks for sharing.
Post 31 Aug 2009, 15:38
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page 1, 2, 3  Next

< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2024, Tomasz Grysztar. Also on GitHub, YouTube.

Website powered by rwasa.