Re: Heap's algorithm

From	rickman <gnuarm@gmail.com>
Newsgroups	comp.lang.forth
Subject	Re: Heap's algorithm
Date	2017-06-09 11:18 -0400
Organization	A noiseless patient Spider
Message-ID	<ohee0q$el2$1@dont-email.me> (permalink)
References	<069c58c6-434c-4dc3-b365-8e3b70bc3d05@googlegroups.com> <df29f23c-bec1-439d-af50-c461b58f4670@googlegroups.com> <774d2d0e-81f4-4219-a17d-858494f100a1@googlegroups.com> <7931b062-2ae1-4810-a14b-c29cf7721dd8@googlegroups.com> <2fc231bf-4c5a-45fd-9718-ced9d9c65238@googlegroups.com>

Show all headers | View raw

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

Thread

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

csiph-web