Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #60476 > unrolled thread

Heap's algorithm

Back to article view | Back to comp.lang.forth

Contents

  Heap's algorithm Julian Fondren <julian.fondren@gmail.com> - 2017-06-08 23:21 -0700
    Re: Heap's algorithm Raimond Dragomir <raimond.dragomir@gmail.com> - 2017-06-09 00:27 -0700
      Re: Heap's algorithm Julian Fondren <julian.fondren@gmail.com> - 2017-06-09 01:40 -0700
        Re: Heap's algorithm Raimond Dragomir <raimond.dragomir@gmail.com> - 2017-06-09 02:15 -0700
          Re: Heap's algorithm Julian Fondren <julian.fondren@gmail.com> - 2017-06-09 03:04 -0700
            Re: Heap's algorithm Raimond Dragomir <raimond.dragomir@gmail.com> - 2017-06-09 03:50 -0700
              Re: Heap's algorithm Julian Fondren <julian.fondren@gmail.com> - 2017-06-09 07:37 -0700
                Re: Heap's algorithm Coos Haak <htrofhc@gmail.com> - 2017-06-09 19:50 +0200
                  Re: Heap's algorithm Julian Fondren <julian.fondren@gmail.com> - 2017-06-09 11:32 -0700
              Re: Heap's algorithm Julian Fondren <julian.fondren@gmail.com> - 2017-06-09 07:54 -0700
              Re: Heap's algorithm Andrew Haley <andrew29@littlepinkcloud.invalid> - 2017-06-09 10:11 -0500
                Re: Heap's algorithm Alex <alex@rivadpm.com> - 2017-06-09 18:43 +0100
            Re: Heap's algorithm rickman <gnuarm@gmail.com> - 2017-06-09 11:18 -0400
              Re: Heap's algorithm Julian Fondren <julian.fondren@gmail.com> - 2017-06-09 08:42 -0700
                Re: Heap's algorithm rickman <gnuarm@gmail.com> - 2017-06-09 13:43 -0400
        Re: Heap's algorithm Lars Brinkhoff <lars.spam@nocrew.org> - 2017-06-09 13:08 +0200
      Re: Heap's algorithm hughaguilar96@gmail.com - 2017-06-09 09:35 -0700
        Re: Heap's algorithm Julian Fondren <julian.fondren@gmail.com> - 2017-06-09 23:31 -0700
          Re: Heap's algorithm hughaguilar96@gmail.com - 2017-06-10 14:28 -0700
            Re: Heap's algorithm Julian Fondren <julian.fondren@gmail.com> - 2017-06-10 14:44 -0700
              Re: Heap's algorithm hughaguilar96@gmail.com - 2017-06-10 18:56 -0700
                Re: Heap's algorithm Julian Fondren <julian.fondren@gmail.com> - 2017-06-10 19:19 -0700
                  Re: Heap's algorithm hughaguilar96@gmail.com - 2017-06-10 21:04 -0700
                    Re: Heap's algorithm Julian Fondren <julian.fondren@gmail.com> - 2017-06-10 21:08 -0700
                      Re: Heap's algorithm Ron Aaron <rambamist@gmail.com> - 2017-06-11 07:19 +0300
                        Re: Heap's algorithm Alex <alex@rivadpm.com> - 2017-06-11 09:43 +0100
                          Re: Heap's algorithm minforth@arcor.de - 2017-06-11 02:35 -0700
                            Re: Heap's algorithm Alex <alex@rivadpm.com> - 2017-06-11 10:45 +0100
                              Re: Heap's algorithm rickman <gnuarm@gmail.com> - 2017-06-11 12:32 -0400
                                Re: Heap's algorithm Alex <alex@rivadpm.com> - 2017-06-11 17:52 +0100
                                  Re: Heap's algorithm rickman <gnuarm@gmail.com> - 2017-06-12 23:26 -0400
                                Re: Heap's algorithm hughaguilar96@gmail.com - 2017-06-12 19:55 -0700
                            Re: Heap's algorithm krishna.myneni@ccreweb.org - 2017-06-11 14:40 -0700
                            Re: Heap's algorithm hughaguilar96@gmail.com - 2017-06-12 09:02 -0700
                  Re: Heap's algorithm hughaguilar96@gmail.com - 2017-06-10 21:30 -0700
                    Re: Heap's algorithm Julian Fondren <julian.fondren@gmail.com> - 2017-06-10 21:51 -0700
                  Re: Heap's algorithm "Robert L." <No_spamming@noWhere_7073.org> - 2017-06-12 02:24 +0000
                    Re: Heap's algorithm Julian Fondren <julian.fondren@gmail.com> - 2017-06-11 19:28 -0700
                      Re: Heap's algorithm Melzzzzz <Melzzzzz@zzzzz.com> - 2017-06-12 03:41 +0000
                  Re: Heap's algorithm hughaguilar96@gmail.com - 2017-06-14 22:15 -0700
                    Re: Heap's algorithm Ron Aaron <rambamist@gmail.com> - 2017-06-15 08:29 +0300
                      Re: Heap's algorithm Alex <alex@rivadpm.com> - 2017-06-15 12:24 +0100
                        Re: Heap's algorithm Ron Aaron <rambamist@gmail.com> - 2017-06-15 15:59 +0300
                      Re: Heap's algorithm hughaguilar96@gmail.com - 2017-06-16 01:25 -0700
                    Re: Heap's algorithm awegel@arcor.de (Alexander Wegel) - 2017-06-15 14:08 +0200
                      Re: Heap's algorithm hughaguilar96@gmail.com - 2017-06-16 10:46 -0700
                        Re: Heap's algorithm awegel@arcor.de (Alexander Wegel) - 2017-06-17 02:47 +0200
    Re: Heap's algorithm Julian Fondren <julian.fondren@gmail.com> - 2017-06-09 00:31 -0700
    Re: Heap's algorithm Coos Haak <htrofhc@gmail.com> - 2017-06-09 12:32 +0200
    Re: Heap's algorithm hum9 <obi65537@gmail.com> - 2017-06-09 10:03 -0700
      Re: Heap's algorithm hum9 <obi65537@gmail.com> - 2017-06-09 22:28 -0700
    Re: Heap's algorithm hum9 <obi65537@gmail.com> - 2017-06-10 03:07 -0700
      Re: Heap's algorithm Julian Fondren <julian.fondren@gmail.com> - 2017-06-10 05:41 -0700
        Re: Heap's algorithm hum9 <obi65537@gmail.com> - 2017-06-10 18:05 +0300
    Re: Heap's algorithm "Robert L." <No_spamming@noWhere_7073.org> - 2017-06-12 03:32 +0000
      Re: Heap's algorithm "Robert L." <No_spamming@noWhere_7073.org> - 2017-06-12 03:35 +0000
        Re: Heap's algorithm "Robert L." <No_spamming@noWhere_7073.org> - 2017-06-12 04:01 +0000
        Re: Heap's algorithm "Robert L." <No_spamming@noWhere_7073.org> - 2017-06-12 11:01 +0000
      Re: Heap's algorithm Julian Fondren <julian.fondren@gmail.com> - 2017-06-11 21:14 -0700
        Re: Heap's algorithm Julian Fondren <julian.fondren@gmail.com> - 2017-06-11 22:00 -0700
          Re: Heap's algorithm Melzzzzz <Melzzzzz@zzzzz.com> - 2017-06-12 07:54 +0000
            Re: Heap's algorithm Julian Fondren <julian.fondren@gmail.com> - 2017-06-12 01:13 -0700
              Re: Heap's algorithm Melzzzzz <Melzzzzz@zzzzz.com> - 2017-06-12 08:20 +0000
    Re: Heap's algorithm Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2017-06-14 20:17 +0100
      Re: Heap's algorithm hughaguilar96@gmail.com - 2017-06-16 01:16 -0700
        Re: Heap's algorithm Alex <alex@rivadpm.com> - 2017-06-16 15:14 +0100
          Re: Heap's algorithm Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2017-06-16 20:15 +0100
        Re: Heap's algorithm Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2017-06-16 20:14 +0100
          Re: Heap's algorithm hughaguilar96@gmail.com - 2017-06-16 19:35 -0700

Page 1 of 4  [1] 2 3 4  Next page →

#60476 — Heap's algorithm

Hello clf,

The following thread on reddit /r/Forth may interest you. The poster
has some difficulty with showing permutations in Forth, but powers
through it, and then asks for feedback on his code. There's another
implementation of the task among the replies.

https://www.reddit.com/r/Forth/comments/6fzpkd/applying_forths_principles_in_practice/

Here's mine:

  : third 2 pick ;
  
  : permute-start ( addr u -- addr u permute-state )
    align here dup third cells dup allot erase ;
  
  : permute-free ( addr u permute-state -- )
    drop nip 1+ cells negate allot ;
  
  : switch ( a1 a2 -- )
    over @ over @ swap rot ! swap ! ;
  
  : next-permute ( addr u permute-state -- addr u permute-state f )
    over 0 do
      dup i cells + @ i < if
        i 2 mod 0= if
          third dup i cells + switch
        else
          third dup i cells + swap
          third i cells + @ cells + switch
        then
        1 over i cells + +!
        true unloop exit
      then
    0 over i cells + ! loop false ( no more permutations ) ;
  
  create blah 1 , 2 , 3 , 4 , 5 ,
  : show ( -- ) blah 5 cells bounds cr do i ? 1 cells +loop ;
  : show-blahs ( -- )
    blah 5 permute-start
    begin show next-permute 0= until permute-free ;

ALLOCATE and FREE variants of PERMUTE-START and PERMUTE-FREE could
easily be supplied; NEXT-PERMUTE won't care either way. I don't really
like all the repetitions of I CELLS + and at a glance the inner stack
manipulation could probably be simplified by swapping ( addr u ) ahead
of time. Another option: assume the caller has his own convenient
access to the array -- as is actually the case above with BLAH -- and
include ADDR U in the temporary array.

This is an implementation of the non-recursive version of Heap's
algorithm, which is written as a self-contained function with an
output(A) to supply the permutations. By taking an xt you could write
a Forth word that more closely mirrors the pseudocode, but I like
NEXT-PERMUTE as its own factor, since that lets you be a little bit
more clever with the temporary array.

Another place to hold the 'temporary array' is in the actual array
that you're generating permutations for, if you've bits to spare. You
need at least enough to represent the length of the array. I can't
think of use for that though... maybe if there's a lot of permutation
done with DNA strings?

(Unrelatedly, I have now a 159-line definition in Forth. I may post
about it later. After slaying the beast, of course.)

[toc] | [next] | [standalone]

#60477

vineri, 9 iunie 2017, 09:21:59 UTC+3, Julian Fondren a scris:
> Hello clf,
> 
> The following thread on reddit /r/Forth may interest you. The poster
> has some difficulty with showing permutations in Forth, but powers
> through it, and then asks for feedback on his code. There's another
> implementation of the task among the replies.
> 
> https://www.reddit.com/r/Forth/comments/6fzpkd/applying_forths_principles_in_practice/
> 
> Here's mine:
> 
>   : third 2 pick ;
>   
>   : permute-start ( addr u -- addr u permute-state )
>     align here dup third cells dup allot erase ;
>   
>   : permute-free ( addr u permute-state -- )
>     drop nip 1+ cells negate allot ;
>   
>   : switch ( a1 a2 -- )
>     over @ over @ swap rot ! swap ! ;
>   
>   : next-permute ( addr u permute-state -- addr u permute-state f )
>     over 0 do
>       dup i cells + @ i < if
>         i 2 mod 0= if
>           third dup i cells + switch
>         else
>           third dup i cells + swap
>           third i cells + @ cells + switch
>         then
>         1 over i cells + +!
>         true unloop exit
>       then
>     0 over i cells + ! loop false ( no more permutations ) ;
>   
>   create blah 1 , 2 , 3 , 4 , 5 ,
>   : show ( -- ) blah 5 cells bounds cr do i ? 1 cells +loop ;
>   : show-blahs ( -- )
>     blah 5 permute-start
>     begin show next-permute 0= until permute-free ;
> 
> ALLOCATE and FREE variants of PERMUTE-START and PERMUTE-FREE could
> easily be supplied; NEXT-PERMUTE won't care either way. I don't really
> like all the repetitions of I CELLS + and at a glance the inner stack
> manipulation could probably be simplified by swapping ( addr u ) ahead
> of time. Another option: assume the caller has his own convenient
> access to the array -- as is actually the case above with BLAH -- and
> include ADDR U in the temporary array.
> 
> This is an implementation of the non-recursive version of Heap's
> algorithm, which is written as a self-contained function with an
> output(A) to supply the permutations. By taking an xt you could write
> a Forth word that more closely mirrors the pseudocode, but I like
> NEXT-PERMUTE as its own factor, since that lets you be a little bit
> more clever with the temporary array.
> 
> Another place to hold the 'temporary array' is in the actual array
> that you're generating permutations for, if you've bits to spare. You
> need at least enough to represent the length of the array. I can't
> think of use for that though... maybe if there's a lot of permutation
> done with DNA strings?
> 
> (Unrelatedly, I have now a 159-line definition in Forth. I may post
> about it later. After slaying the beast, of course.)

This looks to me as a very write-only code. At least I cannot read it.
Using locals would have been great. Just a simple example, of the
switch:
: switch { a1 a2 -- } a1 @ a2 @ a1 ! a2 ! ;

'third' is an example of an egocentric word. It's names descibe the stack
effect. But although it's so much used inside the next-permute, it
doesn't show what it is for. It's like there is a 'third' thing envolved
there. Is that definition about the (forth) stack or about a sorting
algorithm? If you didn't hide '2 pick' in the 'third', at least things
would have been more clear.

Too much forth code is this kind of egocentric. It looks like it wants
to show/demonstrate some stack mechanics at any price. And the human
must need to 'decode' the intended functionality from this stack mechanics.

Sorry for my comments if this post is intended for discussing the real
functionality/implementation strategies. But I feel that it's about 
"is this good forth style?".

[toc] | [prev] | [next] | [standalone]

#60479

On Friday, June 9, 2017 at 2:27:08 AM UTC-5, Raimond Dragomir wrote:
> This looks to me as a very write-only code. At least I cannot read it.
> Using locals would have been great. Just a simple example, of the
> switch:
> : switch { a1 a2 -- } a1 @ a2 @ a1 ! a2 ! ;

This code reaches a depth of three instead of the original depth of
four. Why is that such an significant change for you?

Ths is how I read the original:

  ( a1 a2 -- )
  over @ over @   ( a1 a2 x1 x2 )
  swap            ( a1 a2 x2 x1 )
  rot !           \ x1 -> a2
  swap !          \ x2 -> a1

Maybe with SWAP as part of the first phrase and not as an indepedent
phrase.

I actually originally wrote NEXT-PERMUTE with locals (before I
realized that pseudocode 'i' didn't need to be preserved; that was the
additional cell accounted for by PERMUTE-FREE). It wasn't that nice.

> 
> 'third' is an example of an egocentric word. It's names descibe the stack
> effect. But although it's so much used inside the next-permute, it
> doesn't show what it is for.

The first DUP in NEXT-PERMUTE also doesn't show what it's for.
Obviously, you have to know what's on the stack to understand the
point of a stack-effect word.

> If you didn't hide '2 pick' in the 'third', at least things
> would have been more clear.

Eh, OK. I would say exactly the opposite of any 2 PICK found in Forth
code. 2 PICK is only present here because optimizers have as easy or
an easier time with it as they would with alternatives.

> Too much forth code is this kind of egocentric. It looks like it wants
> to show/demonstrate some stack mechanics at any price. And the human
> must need to 'decode' the intended functionality from this stack mechanics.

Sorry, but 'egocentric' means nothing to me, as a word. The desire
behind most of this code is to accomplish a given task, not to show
off stack mechanics or anything else. Of someone who can't read it, I
would just say that this is a person who can't read Forth. Or code at
all: the pseudocode also doesn't "say what it's for", it's a lot of

  for i := 0; i < n; i += 1 do
      c[i] := 0
  end for

and more of

  c[i] := 0
  i += 1

And I reckon, as I've found of Forth given such treatment, that after
you twist "c[i] := 0" to the point that it "reads like English", the
main result will be that it's now harder to understand what's actually
happening. When memory fades a bit, you can

1. piece things back together from multiple directions, from on high,
from the English meanings of words, but also but also from down low,
from what you can clearly see from mundane pushing-bits-around code,
or you can

2. read a 80k word treatise (that was never written--so actually you
can't read it, and this option is a lie) to completely restore to you
the original context of GLEEBLE and FWIPSLUSH and DECIMATE? and all
the other cute once-off pseudofactors that made sense at the time.

Take this code from the reddit thread:

  : odd? ( n i -- n f ) over 1+ 1 and ;
  : switch ( n i -- ) odd? if drop 0 then exch ;

"odd? if" reads nicely in the definition of SWITCH. But what the hell
is it doing? It certainly isn't doing

  : odd? ( n -- f ) 1 and ;

It's doing something that makes sense *only* in the context of
SWITCH. That stack comment was originally ( n - n f ); on reddit it
was pointed out that OVER is obviously assuming more on the stack, so
this was 'fixed' -- and the new stack comment is still wrong. Because
this isn't a real factor.

I don't have a good metaphor for this, but: it's OK for the inside of
your body to look, in some areas, like a muscle that pushes blood
through tubes. That part of your body doesn't have to meet the beauty, 
dryness, emotive, and other standards of your face. In its own way it
supports you having something like a face.

> Sorry for my comments if this post is intended for discussing the real
> functionality/implementation strategies. But I feel that it's about 
> "is this good forth style?".

It's fine by me, even if I don't agree with you. The reddit thread had
a similar focus.

[toc] | [prev] | [next] | [standalone]

#60481

> Ths is how I read the original:
> 
>   ( a1 a2 -- )
>   over @ over @   ( a1 a2 x1 x2 )
>   swap            ( a1 a2 x2 x1 )
>   rot !           \ x1 -> a2
>   swap !          \ x2 -> a1

Given the task: "swap the content of two memory addresses",
if besides the obvious two stores and two fetches you need
two SWAPs, two OVERs and a ROT, something may not be ok,
at least to me. 

Note that I was using the stack in a "clever" way, even with
the locals:
: switch { a1 a2 -- }
  a1 @
  a2 @ a1 !
  a2 !
;
In a variables-only language you will need a temp variable.

Maybe you are right: I can't read forth code. At least not
next-permute one. I was able to read 'switch' in my mind
although at the ROT moment it was quite hard to visualize the
order of the parameters on the stack. Maybe I'm not good
at blind chess also. And from what I've read, three parameters
on the stack are manageable, four are not. It's not my 
saying however. Even three are sometimes hard, especially 
when they hide in a longer definition. In my short definition of
switch the parameters are almost named (because of the local
names) and consumed immediately.

What's funny is that in the original post, the guy admits his
limit in writing "forth" code (although tried hard with the 'switch'):

: 3dup { a b c } a b c a b c ;

Otherwise, he's not using locals in any other definition.

[toc] | [prev] | [next] | [standalone]

#60486

On Friday, June 9, 2017 at 4:15:44 AM UTC-5, Raimond Dragomir wrote:
> Given the task: "swap the content of two memory addresses",
> if besides the obvious two stores and two fetches you need
> two SWAPs, two OVERs and a ROT, something may not be ok,
> at least to me. 

You have two addresses.
You have @ and ! , which both consume an address.
You need to call @ twice and ! twice -- consuming a total of four
addresses.

You have two addresses but must consume four of them?
Two OVERs supply the two additional addresses that you need.

@ takes an address from the top of the stack and puts the value at
that address back on the top of the stack. If you consume two copies
of addresses, and leave two values on the stack -- where will those
values be?
On the top of the stack of course, until you move them.

! takes an address from the top of the stack, and a value from the
next on the stack. In other words it expects addresses to be above
values on the stack.
At this point though, your values are above your addresses.
ROT and SWAP rectify that.

So if something is wrong, apparently it's @ and !

Or rather, why don't you try it? You can use 2DUP , or DUP and THIRD ,
or >R R@ OVER . You need two copies and you need @'s return to be
deeper in the stack.

Or do you prefer this?

  : switch ( a1 a2 -- )
    dup pad       1 cells move
    2dup          1 cells move
    drop pad swap 1 cells move ;

[toc] | [prev] | [next] | [standalone]

#60488

vineri, 9 iunie 2017, 13:04:55 UTC+3, Julian Fondren a scris:
> On Friday, June 9, 2017 at 4:15:44 AM UTC-5, Raimond Dragomir wrote:
> > Given the task: "swap the content of two memory addresses",
> > if besides the obvious two stores and two fetches you need
> > two SWAPs, two OVERs and a ROT, something may not be ok,
> > at least to me. 
> 
> You have two addresses.
> You have @ and ! , which both consume an address.
> You need to call @ twice and ! twice -- consuming a total of four
> addresses.
> 
> You have two addresses but must consume four of them?
> Two OVERs supply the two additional addresses that you need.
> 
> @ takes an address from the top of the stack and puts the value at
> that address back on the top of the stack. If you consume two copies
> of addresses, and leave two values on the stack -- where will those
> values be?
> On the top of the stack of course, until you move them.
> 
> ! takes an address from the top of the stack, and a value from the
> next on the stack. In other words it expects addresses to be above
> values on the stack.
> At this point though, your values are above your addresses.
> ROT and SWAP rectify that.
> 
> So if something is wrong, apparently it's @ and !
> 
> Or rather, why don't you try it? You can use 2DUP , or DUP and THIRD ,
> or >R R@ OVER . You need two copies and you need @'s return to be
> deeper in the stack.
> 
> Or do you prefer this?
> 
>   : switch ( a1 a2 -- )
>     dup pad       1 cells move
>     2dup          1 cells move
>     drop pad swap 1 cells move ;

I try it, here it is again:
: switch { a1 a2 -- } a1 @ a2 @ a1 ! a2 ! ;

Some things just don't fit to the stack model. They are more 
random access than ordered in some way. The traditional forth
doesn't want to admit this reality and solves everything by
stack juggling, no matter how awfull the code looks (and
probably is).

I don't like stack juggling at all. In this respect, PICK is
my friend not my enemy but I prefer named access (locals)
rather than numbered (PICK).

[toc] | [prev] | [next] | [standalone]

#60498

On Friday, June 9, 2017 at 5:33:01 AM UTC-5, Coos Haak wrote:
> Op Thu, 8 Jun 2017 23:21:57 -0700 (PDT) schreef Julian Fondren:
> >   : permute-start ( addr u -- addr u permute-state )
> >     align here dup third cells dup allot erase ;
> I don't like PICK at all. Why not

I'm not using PICK. I'm using THIRD. The definition there is "in case
you don't have this". On SwiftForth THIRD's a CODE word. On iForth and
VFX it compiles identically to PICK-averse code.

>       align dup cells here swap allot erase

  create box 100 allot

  box 100
  align dup cells here swap allot .s

Outputs:

  Data: 270663760 100 270666160 ---
  System: ---
  Float: --- ok

I don't want to go on to ERASE that...

> or
>       aligh here over cells dup allot erase

  box 100
  align here over cells dup allot erase .s

  Data: 270663760 100 ---
  System: ---
  Float: --- ok

You've done this before :-)

But it's a different word.

[toc] | [prev] | [next] | [standalone]

#60520

Op Fri, 9 Jun 2017 07:37:26 -0700 (PDT) schreef Julian Fondren:

your follow-ups are stronly mixed up

> On Friday, June 9, 2017 at 5:33:01 AM UTC-5, Coos Haak wrote:
<snip>
>>       align dup cells here swap allot erase
I forgot a dup
      align dup cells here swap dupa allot erase

groet Coos

[toc] | [prev] | [next] | [standalone]

#60522

On Friday, June 9, 2017 at 12:50:23 PM UTC-5, Coos Haak wrote:
> Op Fri, 9 Jun 2017 07:37:26 -0700 (PDT) schreef Julian Fondren:
> 
> your follow-ups are stronly mixed up

Mixed up how?

> 
> > On Friday, June 9, 2017 at 5:33:01 AM UTC-5, Coos Haak wrote:
> <snip>
> >>       align dup cells here swap allot erase
> I forgot a dup
>       align dup cells here swap dupa allot erase

OK, but this is still not the same word.

The word you're replacing has this stack effect:

  ( addr u -- addr u permute-state ) 

[toc] | [prev] | [next] | [standalone]

#60499

On Friday, June 9, 2017 at 5:50:31 AM UTC-5, Raimond Dragomir wrote:
> I try it, here it is again:
> : switch { a1 a2 -- } a1 @ a2 @ a1 ! a2 ! ;

> Some things just don't fit to the stack model.

This is a word that consumes two items on the stack, and only goes to
a depth of four on the stack. Its only stack manipulation words are
OVER SWAP and ROT

You say it doesn't fit the stack model and aren't willing to write it.

Occasionally I'm annoyed when people pass off knowledge they gained by
reading about it in a blog (or worse, a news report) as if it were an
opinion drawn from their personal professional experience. Like a fan
of webMD not saying "oh no I read about this on webMD, you should--"
but rather "I'm a doctor, I've seen this hundreds of times, and you
need to--". People hesitate before claiming to be doctors but on
technology a CNET article is enough to authoritatively declare that
the OS is dead, whatever CNET specifically meant by that.

Here I'm annoyed by someone making a presumptuous claim on a matter of
taste.

So, good start to the weekend :-)

[toc] | [prev] | [next] | [standalone]

#60500

Raimond Dragomir <raimond.dragomir@gmail.com> wrote:
> 
> I try it, here it is again:
> : switch { a1 a2 -- } a1 @ a2 @ a1 ! a2 ! ;
> 
> Some things just don't fit to the stack model. They are more 
> random access than ordered in some way. The traditional forth
> doesn't want to admit this reality and solves everything by
> stack juggling, no matter how awfull the code looks (and
> probably is).

If you're going to insist on traditional, Forth would do something
like this:

code switch ( a1 a2)
   0 [ebp] eax mov ( a1 -> eax)
   0 [eax] ecx mov ( n1 -> ecx)
   0 [ebx] ecx xchg ( n1 -> a2, n2 -> ecx)
   cell [ebp] ebx mov
   ecx 0 [eax] mov ( n2 -> a1)
   2 cells # ebp add ( pop a1 and a2)
   ret
end-code

This is a semi-serious point: when it was commonplace to write fiddly
low-level definitions like this in code, there wasn't much of a
perceived problem.

Andrew.

[toc] | [prev] | [next] | [standalone]

#60519

On 6/9/2017 16:11, Andrew Haley wrote:
> Raimond Dragomir <raimond.dragomir@gmail.com> wrote:
>>
>> I try it, here it is again:
>> : switch { a1 a2 -- } a1 @ a2 @ a1 ! a2 ! ;
>>
>> Some things just don't fit to the stack model. They are more
>> random access than ordered in some way. The traditional forth
>> doesn't want to admit this reality and solves everything by
>> stack juggling, no matter how awfull the code looks (and
>> probably is).
> 
> If you're going to insist on traditional, Forth would do something
> like this:
> 
> code switch ( a1 a2)
>     0 [ebp] eax mov ( a1 -> eax)
>     0 [eax] ecx mov ( n1 -> ecx)
>     0 [ebx] ecx xchg ( n1 -> a2, n2 -> ecx)
>     cell [ebp] ebx mov
>     ecx 0 [eax] mov ( n2 -> a1)
>     2 cells # ebp add ( pop a1 and a2)
>     ret
> end-code
> 
> This is a semi-serious point: when it was commonplace to write fiddly
> low-level definitions like this in code, there wasn't much of a
> perceived problem.
> 
> Andrew.
> 

XCHG LOCKs for memory operands.

see exchange
code exchange ( 2 -- 0 )
\ exchange is defined in src/kernel/gkernel32.fs at line 1288
\ call compiled
\ code=$401D0F len=17 type=129
( $0 )    mov     ecx dword { $0 ebp }              \ 8B4D00
( $3 )    mov     edx dword { eax }                 \ 8B10
( $5 )    mov     edi dword { ecx }                 \ 8B39
( $7 )    mov     dword { eax } edi                 \ 8938
( $9 )    mov     dword { ecx } edx                 \ 8911
( $B )    mov     eax dword { $4 ebp }              \ 8B4504
( $E )    add     ebp $8                            \ 83C508
( $11 )   ret                                       \ C3 ( end ) ok

EAX is cached TOS, EBP is stack.

-- 
Alex

[toc] | [prev] | [next] | [standalone]

#60501

Julian Fondren wrote on 6/9/2017 6:04 AM:
> On Friday, June 9, 2017 at 4:15:44 AM UTC-5, Raimond Dragomir wrote:
>> Given the task: "swap the content of two memory addresses",
>> if besides the obvious two stores and two fetches you need
>> two SWAPs, two OVERs and a ROT, something may not be ok,
>> at least to me.
>
> You have two addresses.
> You have @ and ! , which both consume an address.
> You need to call @ twice and ! twice -- consuming a total of four
> addresses.
>
> You have two addresses but must consume four of them?
> Two OVERs supply the two additional addresses that you need.
>
> @ takes an address from the top of the stack and puts the value at
> that address back on the top of the stack. If you consume two copies
> of addresses, and leave two values on the stack -- where will those
> values be?
> On the top of the stack of course, until you move them.
>
> ! takes an address from the top of the stack, and a value from the
> next on the stack. In other words it expects addresses to be above
> values on the stack.
> At this point though, your values are above your addresses.
> ROT and SWAP rectify that.
>
> So if something is wrong, apparently it's @ and !
>
> Or rather, why don't you try it? You can use 2DUP , or DUP and THIRD ,
> or >R R@ OVER . You need two copies and you need @'s return to be
> deeper in the stack.
>
> Or do you prefer this?
>
>   : switch ( a1 a2 -- )
>     dup pad       1 cells move
>     2dup          1 cells move
>     drop pad swap 1 cells move ;

This is the sort of stack juggling that my stack processor gets around 
(somewhat) by using the return stack for memory addresses.  I sometimes call 
it the address stack for this reason.

In this case the addresses are not known to be literals (which are also 
generated on the return stack) so on entry to the routine they are on the 
data stack and must be moved to the return stack which is not so convenient 
but it seems to be pretty brief.

: switch ( a1 a2 -- )  >R >R ROVER @ RDUP ! @ ! ;

These are all machine instructions including the call and return.  The 
return can not be combined with the ! because they both use the return 
stack... unless a pathway is added to allow the next instruction address to 
be fetched from the second on the return stack.  I've tried to minimize the 
machine size so I didn't implement this path.

I've never dug into how local variables are implemented.  Does it require 
the use of separate memory, space on the return stack or is there a special 
stack?  I'm curious how efficient local variables could be.  Are they worthy 
of dedicated hardware (which might be as simple as a data path somewhere)?

-- 

Rick C

[toc] | [prev] | [next] | [standalone]

#60502

On Friday, June 9, 2017 at 10:18:10 AM UTC-5, rickman wrote:
> : switch ( a1 a2 -- )  >R >R ROVER @ RDUP ! @ ! ;

Does this actually work? It looks like it sets both addresses to the
same value instead of swapping their values. Just look at the
store/fetch words: @ ! @ ! instead of @ @ ! !

I would think you'd need

  : switch ( a1 a2 -- ) >R >R ROVER @ RDUP @ SWAP ! ! ;

Or more neatly:

  : switch ( a1 a2 -- ) >R >R RDUP @ ROVER @ ! ! ;

That saves a SWAP , which is also what the locals version saves.

[toc] | [prev] | [next] | [standalone]

#60518

Julian Fondren wrote on 6/9/2017 11:42 AM:
> On Friday, June 9, 2017 at 10:18:10 AM UTC-5, rickman wrote:
>> : switch ( a1 a2 -- )  >R >R ROVER @ RDUP ! @ ! ;
>
> Does this actually work? It looks like it sets both addresses to the
> same value instead of swapping their values. Just look at the
> store/fetch words: @ ! @ ! instead of @ @ ! !
>
> I would think you'd need
>
>   : switch ( a1 a2 -- ) >R >R ROVER @ RDUP @ SWAP ! ! ;
>
> Or more neatly:
>
>   : switch ( a1 a2 -- ) >R >R RDUP @ ROVER @ ! ! ;
>
> That saves a SWAP , which is also what the locals version saves.

Let's try it one instruction at a time...

: switch ( a1 a2 -- )  >R >R ROVER @ RDUP ! @ ! ;

         ( a1 a2 -- )    (R: -- )                 ( a1:x1 a2:x2 )
 >R      ( a1 a2 -- a1 ) (R: -- a2 )              ( a1:x1 a2:x2 )
 >R      ( -- )          (R: a2 -- a2 a1 )        ( a1:x1 a2:x2 )
ROVER   ( -- )          (R: a2 a1 -- a2 a1 a2 )  ( a1:x1 a2:x2 )
@       ( -- x2 )       (R: a2 a1 a2 -- a2 a1 )  ( a1:x1 a2:x2 )
RDUP    ( -- x2 )       (R: a2 a1 -- a2 a1 a1 )  ( a1:x1 a2:x2 )
!       ( -- )          (R: a2 a1 a1 -- a2 a1 )  ( a1:x2 a2:x2 ) oops!
@
!
;

Yes, your final word looks good.

I've also looked at an addressable stack machine that allows a very small 
offset into the stack to retrieve operands which saves a *lot* more stack 
juggling.  It would require a compiler to be aware of operand positions to 
be able to use this effectively.  I haven't done much other than to code up 
an example app, but it was much more instruction efficient.  The variations 
on instruction set use between 103 and 60 instructions with the 103 being my 
basic stack processor and 60 being the stack indexed instruction set.

The app for this comparison is an interrupt routine for a software DDS which 
generates the value to feed a DAC on the fly.  Maybe I'll get around to 
working on this and produce an FPGA design.  I think it could produce 
significantly more compact code than a straight stack design.  Not sure what 
it would take to write an optimizing compiler for it.

-- 

Rick C

[toc] | [prev] | [next] | [standalone]

#60491

Julian Fondren wrote:
> "odd? if" reads nicely in the definition of SWITCH. But what the hell
> is it doing? It certainly isn't doing
>
>   : odd? ( n -- f ) 1 and ;
>
> It's doing something that makes sense *only* in the context of SWITCH.

Yes, that's right.  I put some emphasis on making words that make sense
in the context of the call site.  That's how I write Forth code that is
easy for me to read.  It wasn't intended as an example of good Forth
style.

[toc] | [prev] | [next] | [standalone]

#60504

On Friday, June 9, 2017 at 12:27:08 AM UTC-7, Raimond Dragomir wrote:
> This looks to me as a very write-only code. At least I cannot read it.
> Using locals would have been great. 

My heap-sort in the novice-package uses locals. Also, I support arrays of structs --- the ANS-Forth crowd seems to be obsessed with forcing everybody to use arrays of cells.

This is my code:
---------------------------------------------------------------------------

SwiftForth? [if]        \ SwiftForth's optimization is so bad that no Forth version is any good

icode exchange ( adrX adrY size -- )    \ the size of the record must be a multiple of W
    0 [ebp] edx mov  w [ebp] ecx mov    \ EDX<>ECX, with EBX being the size
    begin  non-zero? while
        0 [ecx] eax mov
        0 [edx] eax xor  eax 0 [edx] xor  0 [edx] eax xor
        eax 0 [ecx] mov
        w # edx add  w # ecx add
        w # ebx sub  repeat
    w 2 * [ebp] ebx mov
    w 3 * # ebp add  ret end-code

[else]

macro: exchange ( adrX adrY size -- )   \ the size of the record must be a multiple of W
    begin  dup while                    \ -- adrX adrY remaining
        -rot                            \ -- remaining adrX adrY
        dup @  rover @                  \ -- remaining adrX adrY Y X
        rover !  rover !                \ -- remaining adrX adrY
        w +  swap w +  rot w -          \ -- adrY adrX remaining        \ adrY and adrX change places
        repeat
    3drop ;

\ Under VFX the SWAP to get adrY and adrX back to how they were doesn't cost anything.
\ Having them change places might help on a non-optimizing compiler though.

[then]

\ If FIELD is used to define records, the size of the records will be a multiple of W, as required by EXCHANGE.


\ ******
\ ****** This is our array sort. We are using the heap-sort because it provides consistent times and it is not recursive.
\ ****** This code was ported from C++ at: http://www.snippets.24bytes.com/2010/06/heap-sort.html
\ ****** Our array record size must be a multiple of W. This is assured if FIELD is used for creating the record.
\ ****** The easiest way to speed this up is to rewrite EXCHANGE in assembly language.
\ ******

\ All of these macros use the locals from SORT, and can only be called from SORT.
\ Because they access locals, they have to be defined with LATE-MACRO: --- this is something MACRO: can't do.

late-macro: adr ( index -- adr )
    recsiz *  array + ;

late-macro: left ( x -- y )      2*  1+ ;

late-macro: right ( x -- y )     2*  2 + ;

late-macro: heapify ( x -- )
    dup >r  begin   \ r: -- great
        dup left    dup limit < if      dup adr  rover adr  'comparer execute if    rdrop  dup >r   then then  drop
        dup right   dup limit < if      dup adr  r@ adr     'comparer execute if    rdrop  dup >r   then then  drop
        dup r@ <> while
            adr  r@ adr  recsiz exchange
            r@ repeat
    drop rdrop ;

late-macro: build-max-heap ( -- )
    limit 1- 2/  begin  dup 0>= while  dup heapify  1- repeat drop ;

: sort { array limit recsiz 'comparer -- }
    recsiz  [ w 1- ] literal  and  abort" *** SORT: record size must be a multiple of the cell size ***"
    build-max-heap
    begin  limit while  -1 +to limit
        0 adr  limit adr  recsiz exchange
        0 heapify  repeat ;

\ The SORT locals:
\ array             \ the address of the 0th element
\ limit             \ the number of records in the array
\ recsiz            \ the size of a record in the array     \ this must be a multiple of W (FIELD assures this)
\ 'comparer         \ adrX adrY -- X>Y?

\ Note for the novice:
\ This code was originally written with colon words rather than macros, and using items rather than local variables.
\ After it was debugged, it was changed to use macros and locals so that it would be fast and reentrant.
\ One of the reasons why the heap-sort was chosen is because it is not recursive, which allows macros to be used.
\ Using macros allows the data (array, limit, recsiz, 'comparer) to be held in locals rather than items, which is reentrant.
\ See the file SORT.4TH for an early version.

[toc] | [prev] | [next] | [standalone]

#60542

On Friday, June 9, 2017 at 11:35:35 AM UTC-5, hughag...@gmail.com wrote:
> Also, I support arrays of structs --- the ANS-Forth crowd seems to be obsessed with forcing everybody to use arrays of cells.

  cells: 3.475 seconds elapsed.
  structs: 21.650 seconds elapsed.

  cells: 3.672 seconds elapsed.
  structs: 22.101 seconds elapsed.

  cells: 3.680 seconds elapsed.
  structs: 22.145 seconds elapsed. ok

It's just malice I guess.

'cells' is a permutation benchmark using code above.

'structs' is the same but MOVEing 10 cells:

  : structs 10 cells * ;
  1 structs buffer: pad
  : switch ( a1 a2 -- )
    dup pad       1 structs move
    2dup          1 structs move
    drop pad swap 1 structs move ;
  : next-permute ( c-addr u permute-state -- c-addr u permute-state f )
    over 0 do
      dup i structs + @ i < if
        i 2 mod 0= if
          third dup i structs + switch
        else
          third dup i structs + swap
          third i structs + @ cells + switch
        then
        1 over i structs + +!
        true unloop exit
      then
    0 over i structs + ! loop false ( no more permutations ) ;

[toc] | [prev] | [next] | [standalone]

#60578

On Friday, June 9, 2017 at 11:31:45 PM UTC-7, Julian Fondren wrote:
> On Friday, June 9, 2017 at 11:35:35 AM UTC-5, hughag...@gmail.com wrote:
> > Also, I support arrays of structs --- the ANS-Forth crowd seems to be obsessed with forcing everybody to use arrays of cells.
> 
>   cells: 3.475 seconds elapsed.
>   structs: 21.650 seconds elapsed.
> 
>   cells: 3.672 seconds elapsed.
>   structs: 22.101 seconds elapsed.
> 
>   cells: 3.680 seconds elapsed.
>   structs: 22.145 seconds elapsed. ok
> 
> It's just malice I guess.
> 
> 'cells' is a permutation benchmark using code above.
> 
> 'structs' is the same but MOVEing 10 cells:
> 
>   : structs 10 cells * ;
>   1 structs buffer: pad
>   : switch ( a1 a2 -- )
     dup pad       1 structs move
>     2dup          1 structs move
>     drop pad swap 1 structs move ;
>   : next-permute ( c-addr u permute-state -- c-addr u permute-state f )
>     over 0 do
>       dup i structs + @ i < if
>         i 2 mod 0= if
>           third dup i structs + switch
>         else
>           third dup i structs + swap
>           third i structs + @ cells + switch
>         then
>         1 over i structs + +!
>         true unloop exit
>       then
>     0 over i structs + ! loop false ( no more permutations ) ;

This is not my code.

[toc] | [prev] | [next] | [standalone]

#60581

On Saturday, June 10, 2017 at 4:28:59 PM UTC-5, hughag...@gmail.com wrote:
> On Friday, June 9, 2017 at 11:31:45 PM UTC-7, Julian Fondren wrote:
> > On Friday, June 9, 2017 at 11:35:35 AM UTC-5, hughag...@gmail.com wrote:
> > > Also, I support arrays of structs --- the ANS-Forth crowd seems to be obsessed with forcing everybody to use arrays of cells.
> > 
> >   cells: 3.475 seconds elapsed.
> >   structs: 21.650 seconds elapsed.
> > 
> >   cells: 3.672 seconds elapsed.
> >   structs: 22.101 seconds elapsed.
> > 
> >   cells: 3.680 seconds elapsed.
> >   structs: 22.145 seconds elapsed. ok
> > 
> > It's just malice I guess.
> > 
> > 'cells' is a permutation benchmark using code above.
> > 
> > 'structs' is the same but MOVEing 10 cells:
> > 
> >   : structs 10 cells * ;
> >   1 structs buffer: pad
> >   : switch ( a1 a2 -- )
>      dup pad       1 structs move
> >     2dup          1 structs move
> >     drop pad swap 1 structs move ;
> >   : next-permute ( c-addr u permute-state -- c-addr u permute-state f )
> >     over 0 do
> >       dup i structs + @ i < if
> >         i 2 mod 0= if
> >           third dup i structs + switch
> >         else
> >           third dup i structs + swap
> >           third i structs + @ cells + switch
> >         then
> >         1 over i structs + +!
> >         true unloop exit
> >       then
> >     0 over i structs + ! loop false ( no more permutations ) ;
> 
> This is not my code.

No, that's QUITE OBVIOUSLY my code, seeing as it's almost identical to
the cell-permuting code that I claimed as my own in the very first
post of the thread. What's your point? Do you think you have code
that shows that moving more data is faster than moving less data?

It's actually possible for that to be the case, since contiguous
access to memory is faster than random access to it, but you would
still need an apples-to-oranges comparison somewhere. Where's your
struct-sorter that's faster than the equivalent cell-sorter?

[toc] | [prev] | [next] | [standalone]

Page 1 of 4  [1] 2 3 4  Next page →

Back to top | Article view | comp.lang.forth

csiph-web