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

From	anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups	comp.lang.forth
Subject	Re: Implementing binary search without going deeper than top 2 items on stack?
Date	2016-07-25 07:51 +0000
Organization	Institut fuer Computersprachen, Technische Universitaet Wien
Message-ID	<2016Jul25.095102@mips.complang.tuwien.ac.at> (permalink)
References	<5db2ff24-c31d-45a0-a4f9-6b0515203925@googlegroups.com>

Show all headers | View raw

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.

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.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2016: http://www.euroforth.org/ef16/

Thread

csiph-web