flat assembler
Message board for the users of flat assembler.
 Home   FAQ   Search   Register 
 Profile   Log in to check your private messages   Log in 
flat assembler > Programming Language Design > Challenger Interpreter

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


Joined: 16 Jun 2003
Posts: 6599
Location: Kraków, Poland
Challenger Interpreter
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 intepreter 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 a few truly moving events took place, I decided to choose a name after one of those events, which is - in my feeling - less remembered that others, though I recall it clearly that I was watching it happening on TV when I was a small child. So to honor the crew of 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 explanded 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<0set 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 celland 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 those 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 a 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 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 happen 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 Windows bloat 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 the 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: 443 Time(s)



Last edited by Tomasz Grysztar on 15 Dec 2010, 13:05; edited 17 times in total
Post 30 Aug 2009, 19:42
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 6599
Location: Kraków, Poland
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
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: 15158
Location: GW170817

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
Assembly Artist


Joined: 16 Jun 2003
Posts: 6599
Location: Kraków, Poland

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
Assembly Artist


Joined: 16 Jun 2003
Posts: 6599
Location: Kraków, Poland

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: 15158
Location: GW170817

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
Assembly Artist


Joined: 16 Jun 2003
Posts: 6599
Location: Kraków, Poland

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: 15158
Location: GW170817

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: 2124
Location: Usono (aka, USA)
Re: Challenger Interpreter

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
Assembly Artist


Joined: 16 Jun 2003
Posts: 6599
Location: Kraków, Poland
Re: Challenger Interpreter

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: 5909
Location: Poland
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 Send e-mail Visit poster's website Reply with quote
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 6599
Location: Kraków, Poland

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: 5909
Location: Poland

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 Send e-mail Visit poster's website Reply with quote
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 6599
Location: Kraków, Poland
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 aswell.

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: 15158
Location: GW170817
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
Assembly Artist


Joined: 16 Jun 2003
Posts: 6599
Location: Kraków, Poland

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: 15158
Location: GW170817
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
Assembly Artist


Joined: 16 Jun 2003
Posts: 6599
Location: Kraków, Poland
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: 1133

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


Powered by phpBB © 2001-2005 phpBB Group.

Main index   Download   Documentation   Examples   Message board
Copyright © 2004-2016, Tomasz Grysztar.