r3wp [groups: 83 posts: 189283]
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search
 

World: r3wp

[rebcode] Rebcode discussion

Gabriele
14-Oct-2005
[279x2]
Steve: but you need a loop! so, unless you have that in hardware 
(and it still doesn't seem doable to me for floating point), log-e 
will be easier to compute (see wikipedia article)
petr: PARSE is probably going to be much faster than rebcode for 
something like that, IMHO. after all, PARSE is a specialized virtual 
machine.
Ladislav
14-Oct-2005
[281x2]
the REMOVE-EACH success is based on a better algorithm. It is possible 
to implement a pure REBOL mezzanine doing much better than a "dummy 
approach does"
...as well as you may be able to implement a C algorithm doing worse 
than a proper REBOL approach can do
Pekr
14-Oct-2005
[283x2]
Gabriele - thanks for the idea with parse and the note about it being 
a VM of some kind .... now I get it a little bit better :-)
we currently have insert, copy, do you think 'find would make sense? 
It is like moving in loop till some char :-) well, could be done 
in rebcode itself or so it seems :-)
Gabriele
14-Oct-2005
[285x2]
apply result find [series value]   :-)
Brian: it's confirmed, BRAW takes a relative offset like BRA.
BrianH
14-Oct-2005
[287x4]
Ladislav, looking back on the code I've written in REBOL using logarithms, 
it turns out that the integer part of log-2 was all I was interested 
in. Apparently I have just been using it to find out how many bits 
are needed to hold a particular integer value when I've needed such 
info. I haven't used logarithms for regular computation since I was 
in grade school. Oh well, I guess I'm not the target market for the 
log-* functions. Thanks for the link, it's been interesting reading!
Gabriele, a relative offset. Darn. That is going to make BRAW a lot 
more difficult to use for me. What kind of programming tasks are 
made easier with a relative computed goto?
See, even BRA is converted from an absolute offset to a relative 
offset at assembly time. Having BRAW be relative would mean making 
that conversion at runtime every time you want to make the jump, 
and then rewriting that computation every time you make a minor adjustment 
to your code, recounting instructions by hand and subtracting the 
new constant.
I suppose a new opcode BRAWA could be added as a rewrite rule to 
a calculation and a BRAW, but that kind of rewrite rule adds a temporary 
variable and so isn't recursion-safe or safe for use by multiple 
rebcode functions without some tricks.
Volker
14-Oct-2005
[291x2]
HAve not looked close in rebcode. But maybe switch-statements? There 
you know where the branch is, and can calculate the right table. 
another switch could be implemented by reserving enough space for 
each branch, say 8 opcodes. and then simply shift the switch-argument 
by 3 (= *8) and braw.
Also makes it easierto port redcode to rebcode *g*
BrianH
14-Oct-2005
[293x5]
Watch out, I have been giving this some thought and have a big message 
coming :)
(Thinking out loud) It occurs to me that computed branches would 
be a lot easier if you could reference the target values in your 
code, so that you have something to compute with. If the offsets 
were absolute you could just assign them to the label words (something 
that could be done in the first pass of the assembler rewrite of 
the branch statements). Relative offsets could be calculated pretty 
easily if you had something like a HERE opcode that would assign 
the current position to a variable that could be used soon afterwards 
to calculate the relative offset. For that matter, the HERE opcode 
could perform the assignment of the original label as well, and even 
be accomplished by a rewrite rule in the branch fixup pass of the 
assembler.


Here's my proposal for a HERE assembler directive. No native opcodes 
would need to be added - this would be another directive like label. 
This directive could be used to set the target values to words for 
later computation. Assuming BRAW stays relative and no absolute computed 
branch is added, it could also be used in computations to convert 
from absolute to relative offsets. This would be sufficient to make 
computed branches practical.


- A new directive HERE, taking two arguments, a word and a literal 
integer.

It would set the word to the position of the HERE directive, plus 
an offset specified in the second parameter. The offset would need 
to be a literal because the calculation would be performed ahead 
of time by the assembler - 0 would mean no offset. If you don't want 
to reset the position every time you branch to the word use an offset 
of 3. Resetting the word after every branch would allow its use as 
a temporary in absolute-to-relative calculations, but that would 
only be an advantage until the JIT or optimizer is implemented - 
the choice would be up to the developer. Having a mandatory second 
argument is necessary for reasons that will become clear later.


- The HERE directive would be rewritten away in the fix-bl function 
of the assembler like this:

REBOL []  ; So I could use SciTE to write this message

fix-bl: func [block /local labels here label] [
    labels: make block! 16
    block-action: :fix-bl
    if debug? [print "=== Fixing binding and labels... ==="]
    parse block [
        some [
            here:
            subblock-rule (here/1: bind here/1 words)
            |

            'label word! (here/1: bind here/1 words insert insert tail labels 
            here/2 index? here)
            |  ; Beginning of the added code
            'here word! integer! (

                here/1: bind 'set words  ; This is why HERE needs two arguments

                here/3: here/3 + index? here  ; Offset from position of this directive
                if (here/3 < 1) or (here/3 > 1 + length? block) [
                    error/with here "Offset out of bounds:"
                ]
            )  ; End of the added code
            |
            opcode-rule (here/1: bind here/1 words)
            |
            skip (error here)
        ]
    ]
    parse block [
        some [
            here:
            ['bra word! | 'brat word! | 'braf word!] (

                if not label: select labels here/2 [error/with here "Missing label:"]
                here/2: label - index? here
            )
            |
            opcode-rule
            |
            skip (error here)
        ]
    ]
]
Note that the HERE directive would need to be implemented after the 
user-defined rewrite rules have been run because those can change 
the lengths of the offsets. This is the same reason the literal branches 
are calculated at this point.
In case you missed it in the code, the trick is to have the assembler 
calculate the offset and then convert the HERE directive to a SET.
Once you have something like this directive, a branch can be done 
with the addition of just two operations, a SET and a SUB, to the 
relative BRAW. The SET would be a converted HERE.
Gabriele
14-Oct-2005
[298x3]
about HERE... can't you just do that with:
(hmm, no can't, sorry.)
seems to make sense. i'll see what Carl thinks about it.
BrianH
14-Oct-2005
[301]
Feel free to rename it, but "here" made sense to me.
Gabriele
14-Oct-2005
[302x2]
maybe LABEL can serve both purposes, and set the label word to the 
absolute position.
(i.e. the word is set at compile time, so you don't need the SET 
in the rebcode.)
BrianH
14-Oct-2005
[304]
You would still need it to compute relative branches from absolute 
offsets. Plus, by making it a seperate operation you can be more 
likely to have the developer remember to make their label words into 
local variables.
Gabriele
14-Oct-2005
[305x2]
anyway, thinking more about it, probably BRAW was intended for things 
like switch, as Volker suggests above... in that case relative offset 
seems natural.
yes, you have, but you have anyway...
BrianH
14-Oct-2005
[307]
The whole reason I came up with this was because BRAW was relative. 
If you changed BRAW to absolute and wanted to do a computed relative 
branch, you could do so with the same two added instructions. If 
you can come up with an occasion to do a computed relative branch 
please tell me, because I can't. All of my examples either require 
absolute or are better with it.
Gabriele
14-Oct-2005
[308x3]
a function table could use a computed relative branch
i.e. you have a "table" of APPLY instructions and jump to the one 
you want.
but... i'm just playing the devil advocate. i don't know why Carl 
choose relative.
BrianH
14-Oct-2005
[311x7]
Really? Only one that would be used from a single branch statement. 
If that table is reused you would have to recalculate it for the 
new branch location.
For example, there are two ways that ProtoThreads is implemented. 
One way uses switch statements, using a variation of Duff's device. 
The other uses computed branches on compilers that support them. 
The computed branch version is faster, and branches to an absolute 
address. Computed branches to absolute addresses are used in threaded 
interpreters as well.
Switch statements are compiled to relative branches, but those branches 
are computed at compile time rather than run time - in that case 
there is only one branch statement so it's OK. A switch statement 
can be implemented with the other, direct branch statements.
I think Carl chose relative because then he would only have to implement 
one way to branch, relative. In practice, even the non-computed branches 
to label words (rather than literal numbers) are absolute: The assembler 
converts them to relative with the statement  here/2: label - index? 
here  , the same calculation you would have us perform at runtime 
before a relative BRAW could be used.
Thinking further, you could use relative computed branches to implement 
switch statements, though absolute would work too.
Maybe we can split the difference and have another opcode for absolute 
computed branches?
The method of assigning the block position to the word with the LABEL 
directive seems like a good idea - it was my first choice, but it 
didn't handle the offset calculations needed by the absolute-to-relative 
calculations needed by a relative BRAW.
Volker
14-Oct-2005
[318]
Here is another (odd) way: Have a braw on a fixed position. Have 
all addresses relative to that braw. then jump to it. from it all 
addresses like absolute :)
BrianH
14-Oct-2005
[319x2]
Why not do both? Change

    'label word! (here/1: bind here/1 words insert insert tail labels 
    here/2 index? here)
to
    'label word! (
        here/1: bind here/1 words
        set here/2 index? here
        insert insert tail labels here/2 index? here
    )


No, since it wouldn't be set at runtime, it wouldn't be recursion-safe. 
The only safe way to do that would be to replace every reference 
to a label other than the label directive and the literal branches 
with  a constant value of its absolute offset, the one in the labels 
block. Doable, but awkward.
(That last one was directed at Gabriele)
Volker
14-Oct-2005
[321x2]
(what is available on docu? i have to scroll a lot and can find it.)
can -> can't
BrianH
14-Oct-2005
[323x2]
Volker, so you would add one branch instead of an assignment to a 
temp variable and a subtraction. Sounds good, but branch prediction 
hardware would fall over if you JITed this kind of code :(
As for docu, there is the original blog, the succession of notes 
in the releases and the source. And our experimentation.
Volker
14-Oct-2005
[325x2]
I guess till jit some things change anyway. and the branch to the 
branch would be absolute, so branch prediction should handle that.
doc: yes, there where some words to inspect. but i forgot the name. 
system/internals or something?
BrianH
14-Oct-2005
[327]
system/internals, rebcode-define and rebcode* for now.
JaimeVargas
14-Oct-2005
[328]
system/internal/rebcodes