limited test-less loop-less call-full repetition 
Author Message
 limited test-less loop-less call-full repetition

I just thought of this.  I also just had my message erased, so I'm
not in the greatest of moods now.

The idea is very simple, for some types of inner interpreters, and
not too interesting for others.  You create an array of XTs of a
single kind, stick a NEXT or suitable returning word at the end of
it, and then with a calculated BRANCH enter this structure at a
certain point.  Repetition without tests or loops, but lots of
subroutine calls.  Just to fill in this idea, I'll define a couple
of the words involved, and offer trivial use.

  : XTARY create 0 do dup , loop drop ['] next , ;
  : GOTO [ 4 cells here + ] literal ! if [ drop ] ;

  : star [char] * emit ;
  ' star 50 XTARY 50stars
  : stars [ 50stars 50 cells + ] literal swap cells - GOTO ;

There.  I think that's clear enough, and hopefully correct.

Does anyone know of a practical use for such a construct?
Has anyone seen one before?



Sun, 25 Jan 2004 03:15:40 GMT  
 limited test-less loop-less call-full repetition

Quote:

> The idea is very simple, for some types of inner interpreters, and
> not too interesting for others.  You create an array of XTs of a
> single kind, stick a NEXT or suitable returning word at the end of
> it, and then with a calculated BRANCH enter this structure at a
> certain point.  Repetition without tests or loops, but lots of
> subroutine calls.  ...
> Does anyone know of a practical use for such a construct?
> Has anyone seen one before?

I picked up the technique from Chuck's video code a
decade ago.  IMHO it works even better with a native code
Forth that can inline primitives where there is no
subroutine call overhead on the unrolled and inlined
inner loop.  In MachineForth address is in cells and
a single cell can hold several inlined Forth opcodes
depending on the type of machine.  The very short
opcodes reduce the penalties of the inlined code.

Chuck used this for pixel flood fill originally and
since the maximum horizontal video line length was only
96 words of data on that machine and it addresssed 1M
words of memory it seemed a resonable tradeoff to inline
and unroll the inner loop of that routine.  The
result was zero inner loop overhead and zero internal
subroutine call overhead in his pixel flood fill routine.

I used a similar technique in the graphics words in
the GUI that I wrote for graphics and character bitmap
and logical bitmap transfer words.  I even unrolled
and inlined both the inner and outer loops in some
character transfer words since the X*Y cell size
of the transfers are still quite small.  I have
also used the techique where multiple words were
inlined for each inner loop and 2* or 2* 2* was
used in the computed jump (into code table)
calculation.

For graphics words that take X Y paramters there is
a tiny overhead to compute the entry point into
the table, but it is a simple jump for a given
fixed size font bit block transfer.

While Chuck is famous for factoring his code more than
most people he also occasionally unrolls and inlines
inner loops and used computed jump code tables on
low level code that is more highly optimized for
speed. Knowing when and where to factor and when
and where to inline is part of the art of programming.

He also occasionally uses the technique as an
alternative to a CASE statement or nested IF
statements in his code.  I have used that
technique also.



Sun, 25 Jan 2004 01:48:35 GMT  
 limited test-less loop-less call-full repetition


Quote:
>The idea is very simple, for some types of inner interpreters, and
>not too interesting for others.

Actually, as long as the compiler does not reorder or combine code, it
can be extended to work for any Forth implementation.

Quote:
>  You create an array of XTs of a
>single kind, stick a NEXT or suitable returning word at the end of
>it, and then with a calculated BRANCH enter this structure at a
>certain point.  Repetition without tests or loops, but lots of
>subroutine calls.  Just to fill in this idea, I'll define a couple
>of the words involved, and offer trivial use.

>  : XTARY create 0 do dup , loop drop ['] next , ;

The generalization would look like this:

: XTARY ( xt u "name" -- )
  >r :
  0 ?do

  loop
  POSTPONE ;
  r> drop
;

Of course, computing the jump target address is system-dependent.

Quote:
>Does anyone know of a practical use for such a construct?

Well, this kind of unrolling, but without jumping into the middle, is
used in http://www.complang.tuwien.ac.at/forth/bench.zip (file
forth/mm-rtcg.fs), if you consider a benchmark a practical
application, and also in
http://www.complang.tuwien.ac.at/forth/garbage-collection.zip.  Here's
the code:

\ I want to avoid having a DO LOOP in mark at run-time (for time and
\ space reasons), so I unroll it at compile-time using gen-mark.  "see
\ mark" to see what is actualy generated.
: gen-mark ( -- ; generated code: addr1 -- addr2 )
    \ generates the recursive calls for mark
    \ addr2=addr1+grain
    grain 0 ?do

        1 cells +loop ;

: mark ( x -- )
    \ if x is a pointer to a gc chunk, mark it and its descendents

    dup mark? if

        begin ( x1 )
            [ gen-mark ]

    endif
    drop ;

Quote:
>Has anyone seen one before?

Not sure if that's what you have in mind, but in C there is a
technique called Duff's device.

- anton
--
M. Anton Ertl                    Some things have to be seen to be believed

http://www.complang.tuwien.ac.at/anton/home.html



Sun, 25 Jan 2004 17:06:00 GMT  
 limited test-less loop-less call-full repetition
Impressive uses!

Quote:
> He also occasionally uses the technique as an
> alternative to a CASE statement or nested IF
> statements in his code.  I have used that
> technique also.

I've made a lot of use out of tables of XTs
and wrote a simple extensible block editor
about one block in length based around one.
Obviously I've more to think about jumping
into one.

Thanks for your responses, Jeff!



Sun, 25 Jan 2004 20:19:36 GMT  
 limited test-less loop-less call-full repetition

Quote:

> Actually, as long as the compiler does not reorder or combine code, it
> can be extended to work for any Forth implementation.

<snip>

Quote:
> The generalization would look like this:

> : XTARY ( xt u "name" -- )
>   >r :
>   0 ?do

>   loop
>   POSTPONE ;
>   r> drop
> ;

Oh, of course.  Thank you =)

Quote:
> Of course, computing the jump target address is system-dependent.
> >Does anyone know of a practical use for such a construct?

> Well, this kind of unrolling, but without jumping into the middle, is
> used in http://www.complang.tuwien.ac.at/forth/bench.zip (file
> forth/mm-rtcg.fs), if you consider a benchmark a practical
> application, and also in
> http://www.complang.tuwien.ac.at/forth/garbage-collection.zip.  Here's
> the code:

> \ I want to avoid having a DO LOOP in mark at run-time (for time and
> \ space reasons), so I unroll it at compile-time using gen-mark.  "see
> \ mark" to see what is actualy generated.
> : gen-mark ( -- ; generated code: addr1 -- addr2 )
>     \ generates the recursive calls for mark
>     \ addr2=addr1+grain
>     grain 0 ?do

>         1 cells +loop ;

> : mark ( x -- )
>     \ if x is a pointer to a gc chunk, mark it and its descendents

>     dup mark? if

>         begin ( x1 )
>             [ gen-mark ]

>     endif
>     drop ;

Interesting.

Quote:
> >Has anyone seen one before?

> Not sure if that's what you have in mind, but in C there is a
> technique called Duff's device.

I've heard of that, and seen it described, but did not make
the connection.  I'll have to review it.

Thank's for your response!

- Show quoted text -

Quote:
> - anton



Sun, 25 Jan 2004 20:53:55 GMT  
 limited test-less loop-less call-full repetition

Quote:



>>  You create an array of XTs of a
>>single kind, stick a NEXT or suitable returning word at the end of
>>it, and then with a calculated BRANCH enter this structure at a
>>certain point.  Repetition without tests or loops, but lots of
>>subroutine calls.  Just to fill in this idea, I'll define a couple
>>of the words involved, and offer trivial use.

>>  : XTARY create 0 do dup , loop drop ['] next , ;
> The generalization would look like this:

>: XTARY ( xt u "name" -- )
>  >r :
>   0 ?do

>   loop
>   POSTPONE ;
>  r> drop
> ;

hmm, either this is just wrong or I do not understand at all...

Wouldn't ?do loop on the colon-sys produced by ':'
and then pass the loop parameter (i) to compile, ?

Robert Epprecht



Mon, 26 Jan 2004 02:18:46 GMT  
 limited test-less loop-less call-full repetition

(snip)

Quote:
> >: XTARY ( xt u "name" -- )
> >  >r :
> >   0 ?do

> >   loop
> >   POSTPONE ;
> >  r> drop
> > ;

> hmm, either this is just wrong or I do not understand at all...

> Wouldn't ?do loop on the colon-sys produced by ':'
> and then pass the loop parameter (i) to compile, ?

> Robert Epprecht

You're right.  It isn't ANS Forth.


here's an alternative:

: XTARY >r : ' r> 0 ?do dup compile, loop postpone ; drop r> drop ;



Mon, 26 Jan 2004 05:24:30 GMT  
 limited test-less loop-less call-full repetition

(snip)

Quote:
> Wouldn't ?do loop on the colon-sys produced by ':'
> and then pass the loop parameter (i) to compile, ?


yipe!  I'm really not on the ball today.  My 'alternative'
is the only code shown so far that works.
Quote:
> Robert Epprecht



Mon, 26 Jan 2004 05:27:17 GMT  
 limited test-less loop-less call-full repetition

Quote:

> > Wouldn't ?do loop on the colon-sys produced by ':'
> > and then pass the loop parameter (i) to compile, ?

> > Robert Epprecht

> You're right.  It isn't ANS Forth.


> here's an alternative:

> : XTARY >r : ' r> 0 ?do dup compile, loop postpone ; drop r> drop ;

Those aren't ANS Forth either.  The problem is that the colon-sys occupies an _unspecified_
number of stack positions, which may be zero, one, two, etc.  This discussion breaks out
periodically when someone wants to pass a literal into a colon definition.  It isn't
possible to do this with full portability.

Your alternative is better than your first version, because you don't know how many things
?do puts on the return stack, either.

Cheers,
Elizabeth

--
================================================
Elizabeth D. Rather   (US & Canada)       800-55-FORTH
FORTH Inc.                                      +1 310-491-3356
5155 W. Rosecrans Ave. #1018  Fax: +1 310-978-9454
Hawthorne, CA 90250
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
================================================



Mon, 26 Jan 2004 07:40:55 GMT  
 limited test-less loop-less call-full repetition


Quote:

>>: XTARY ( xt u "name" -- )
>>  >r :
>>   0 ?do

>>   loop
>>   POSTPONE ;
>>  r> drop
>> ;

>hmm, either this is just wrong or I do not understand at all...

It's just wrong.  Here's another go:

: XTARY ( xt u "name" -- )
   2>r : 2r>
   0 ?do
     dup compile,
   loop
   drop
   POSTPONE ;
;

This time I tested it, and it seems to work:

' 1+ 5 xtary 5+  ok      
see 5+
: 5+  
  1+ 1+ 1+ 1+ 1+ ; ok

- anton
--
M. Anton Ertl                    Some things have to be seen to be believed

http://www.complang.tuwien.ac.at/anton/home.html



Mon, 26 Jan 2004 13:59:52 GMT  
 
 [ 10 post ] 

 Relevant Pages 

1. 1 little, 2 little, 3 little endians...

2. Loading a page little by little

3. Idle loops - sometimes a little too idle?

4. what is wrong with this little, simple program (test for internal write)

5. Little Compiler Test for Rarely Seen Bug(s)

6. Little Smalltalk - Unable to call editor

7. less noisy 'call'

8. Spend Less On Your Phone Calls This Holiday Season

9. Calling all newbies (and at least one Cliki god)

10. LOGO-L> selection and pre-test repetition

11. little example (Re: "http_clt2srv.cmd" - little function to do http HEAD, GET, POST

12. Of Lisp and little sleep...the little monstrous questions that nag me.

 

 
Powered by phpBB® Forum Software