Re: Implementing binary search without going deeper than top 2 items on stack?

Subject	Re: Implementing binary search without going deeper than top 2 items on stack?
References	<5db2ff24-c31d-45a0-a4f9-6b0515203925@googlegroups.com> <2016Jul25.095102@mips.complang.tuwien.ac.at>
Newsgroups	comp.lang.forth
From	"Elizabeth D. Rather" <erather@forth.com>
Organization	FORTH, Inc.
Date	2016-07-24 22:48 -1000
Message-ID	<vsCdncXT4IXrTwjKnZ2dnUU7-RnNnZ2d@supernews.com> (permalink)

Show all headers | View raw

On 7/24/16 9:51 PM, Anton Ertl wrote:
> Alex Dowad <alexinbeijing@gmail.com> writes:
>> Dear comp.lang.forth,
>>
>> In his "1x Forth" talk (and other talks), Chuck Moore advocates for coding style whereby:
>>
>> 1. All definitions are at most 2 lines, and
>> 2. Words do not directly access anything deeper than the top 2 items on the stack
>>
>> In line with #2, Moore's colorForth has DUP, DROP, and OVER built in, but not PICK, ROLL, and so on.
>>
>> I'd like to see examples of how this can be practical. For example, how would you implement a binary
>> search without violating these rules?
>
> I think there are several answers typical of Chuck Moore style:
>
> 1) Implement it as CODE word.
>
> 2) On his Forth processors, where you cannot work around the
>    restriction with CODE words, he introduced address registers (A, R)
>    which allowed reducing the stack load; or seen the other way, it
>    allowed dealing with more values without violating the restriction.
>
> 3) Use the return stack.
>
> 4) Use global VARIABLEs.
>
> You can find various ways to reduce the stack load in the following
> paper:
>
> @InProceedings{ertl11euroforth,
>   author =       {M. Anton Ertl},
>   title =        {Ways to Reduce the Stack Depth},
>   crossref =     {euroforth11},
>   pages =        {36--41},
>   url =          {http://www.complang.tuwien.ac.at/papers/ertl11euroforth.ps.gz},
>   url2 =         {http://www.complang.tuwien.ac.at/anton/euroforth/ef11/papers/ertl.pdf},
>   OPTnote =      {not refereed},
>   abstract =     {Having to deal with many different data can lead to
>                   problems in Forth: The data stack is the preferred
>                   place to store data; on the other hand, dealing with
>                   too many data stack items is cumbersome and usually
>                   bad style. This paper presents and discusses ways to
>                   unburden the data stack; some of them are used
>                   widely, others are almost unknown or new.}
> }
>
> @Proceedings{euroforth11,
>   title = 	 {27th EuroForth Conference},
>   booktitle = 	 {27th EuroForth Conference},
>   year = 	 {2011},
>   key =		 {EuroForth'11},
>   url =          {http://www.complang.tuwien.ac.at/anton/euroforth/ef11/papers/proceedings.pdf}
> }
>
>> ("Directly accessing deeper items on the stack" would include using >R to get the top item(s) out of the way, then working with the deeper items.)
>
> No.  Forth has the words >R R> R@ for a reason.
>
>> Or is the answer "if you're using binary search, you're doing it wrong. Don't use binary search"?
>
> I don't know if Chuck Moore holds this opinion.  However, I find that
> I almost never actually use binary search.  I do consider it
> relatively often, but usually find a solution that works without it.

I recall that he wrote several binary searches back in the day, 
searching indexes of text keys in a database. Each identified key would 
include the record number of the data record associated with the key.

Chuck's definitions were sometimes more than 2 lines long; that was a 
desiderata, not an ultimatum. The context was the database package that 
was a feature of polyFORTH for a number of years, and searches worked on 
an index that was maintained in sorted order (insertions and deletions 
took longer, but searches were very fast).

I also must point out that Chuck had no reluctance to use global 
variables, and never understood the horror that some people seem to have 
of variables. Variables that needed to be task-specific were user 
variables, but there weren't that many of them; others were useful 
mechanisms for inter-task communication.

> BTW, I wonder why so many people who wonder what Chuck Moore would do
> don't care for Usenet conventions like limiting the line length to
> about 70 characters.

:-)

Cheers,
Elizabeth

-- 
==================================================
Elizabeth D. Rather   (US & Canada)   800-55-FORTH
FORTH Inc.                         +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

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

Thread

csiph-web