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

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

Started by	Alex Dowad <alexinbeijing@gmail.com>
First post	2016-07-24 10:41 -0700
Last post	2016-07-31 00:31 -0700
Articles	11 on this page of 31 — 12 participants

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

Page 2 of 2 — ← Prev page 1 [2]

#49701

From	anton@mips.complang.tuwien.ac.at (Anton Ertl)
Date	2016-07-31 05:49 +0000
Message-ID	<2016Jul31.074934@mips.complang.tuwien.ac.at>
In reply to	#49699

mhx@iae.nl writes:
>On Monday, July 25, 2016 at 10:32:57 AM UTC+2, humptydumpty wrote:
>> \ TEST:
>> \ create first 1 , 3 , 5 , 7 , 9 , here cell - constant last
>> \ first 0 cells + dup vp ! first last (bsearch) = . .s -1 <0>  ok
>> \ first 1 cells + dup vp ! first last (bsearch) = . .s -1 <0>
>> \ last dup vp ! first last (bsearch) = . .s -1 <0>  ok
>> \ first last 8 bsearch . .s 0 <0>  ok
...
>There is another observation we can make here. Not
>only are the factors of bsearch not used *here*,
>the end test suggests that useful general factors
>of the underlying Forth system are also not used:
>
>  here cell - constant XX
>  + dup YY !
>  = . .s
>
>These factors are not used because the author
>doesn't remember them, or considers them
>non-standard, or thinks it is easier to write
>them out than to look them up.

I don't remember such factors, either.  Could you elaborate?

- 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/

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

#49703

From	mhx@iae.nl
Date	2016-07-31 00:17 -0700
Message-ID	<1f722ceb-ffb3-4fb6-afe7-397b6fa2a4a7@googlegroups.com>
In reply to	#49701

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes Re: Implementing binary search without going deeper than top 2 items on stack?

> mhx@iae.nl writes:
[..]
>>the end test suggests that useful general factors
>>of the underlying Forth system are also not used:

>>  here cell - constant XX
>>  + dup YY !
>>  = . .s

>>These factors are not used because the author
>>doesn't remember them, or considers them
>>non-standard, or thinks it is easier to write
>>them out than to look them up.

> I don't remember such factors, either.  Could you elaborate?

I pointed out 3 useful factors that pop up in the post discussed.

It should be obvious that with "useful general factors of the
underlying Forth system" I do not mean the Standard Forth
system, but the implementation of it that is used by the OP, or
the extensions and libraries for it that are written by
the OP (if he uses the style of BSEARCH).

When just looking at "HERE CELL- CONSTANT" it is not as common
as I thought, however, subfactors can be found

Searching for: cell- =:
profiler.frt(59): PID CELL- =: 'inspect PRIVATE
Found 1 occurrence(s) in 1 file(s)

Searching for: - constant
C:\dfwforth\examples\ansi\lc.frt(28): 2 dim lshift 2 - constant row-mask
C:\dfwforth\examples\ansi\uc.frt(28): 2 dim LSHIFT 2 - CONSTANT row-mask
C:\dfwforth\examples\benchmar\fannkuch.frt(94): CREATE a      NUM allot   a NUM + 1- constant a-last
[..]
C:\dfwforth\examples\benchmar\recursive.frt(14): ( N -- ) 1- constant NUM
C:\dfwforth\examples\benchmar\taxi4p-x.frt(62): : ]:                   here swap - constant ;
C:\dfwforth\examples\benchmar\taxi4p.frt(38): : ]:                here swap - constant ;
C:\dfwforth\examples\games\go\go-bitmap.frt(24): 2 dim LSHIFT 2- CONSTANT row-mask
C:\dfwforth\examples\games\go\go-bitmap2.frt(28): 2 dim LSHIFT 2- CONSTANT row-mask
C:\dfwforth\examples\graphics\wcons.frt(20): C/L 2/ 1- CONSTANT  WIDTH
C:\dfwforth\examples\graphics\wcons.frt(21): L/SCR 2/ 1- CONSTANT  HEIGHT
debug-io.frt(56): CELLS 3 - CONSTANT #lsize PRIVATE

Found 43 occurrence(s) in 33 file(s)

Same goes for "+ dup YY !" and "= . .s"

Searching for: \+ dup [a-x][A-Z] \!
C:\dfwforth\examples\misc\iloops.frt(33): 1+ dup ct !
Found 1 occurrence(s) in 1 file(s)

Searching for:  = .
floatest.frt(418): ape2 DUP FALIGNED = .BOOL
Found 1 occurrence(s) in 12 file(s)

However, I have noted many times that when a word *IS* available, and it has
a remarkable name, it will get used more and more (other than by hacking it
out explicitly). An example is 2- 2+ 2* etc.

More involved examples (most are trivial to write, but remembering them is shorter):

"   TIMER-RESET     \ ( -- )"
"   TIMER-PRESET    \ ( u -- ) offset for .elapsed"
"   ?MS             \ ( -- u ) ms since machine turned on"
"   MS?             \ ( -- u ) ms since TIMER-RESET"
"   .ELAPSED        \ ( -- ) prints number of ms since last TIMER-RESET"

"   PROCESSOR-CLOCK \ ( -- mhz )
"   TICKS-INITED?   \ ( -- TRUE=inited )"
"   CALIBRATE       \ ( -- ) compute processor-clock"
"   RECALIBRATE     \ ( -- ) recompute processor-clock"
"   TICKS-RESET     \ ( -- )"
"   TICKS-GET       \ ( -- ud ) ticks since machine turned on"
"   TICKS?          \ ( -- ud ) ticks since TICKS-RESET"
"   TICKS>US        \ ( ud -- ud ) convert to microseconds"
"   TICKS>MS        \ ( ud -- u ) convert to milliseconds"
"   US?             \ ( -- ud ) microseconds since last TICKS-RESET"
"   DTICKS-RESET    \ ( -- )"
"   [TICKS          \ ( -- )"
"   TICKS]          \ ( -- ) accumulates ticks since [TICKS"
"   D-US?           \ ( -- ud ) us since last DTICKS-RESET"
"   .TICKS"         \ ( <text>" -- ) time in clock ticks"

" ((n,3))           \ ( ud -- caddr u )"
" (n,3)             \ ( ud -- )"
" ((.KB))           \ ( ud -- caddr u )"
" (.KB)             \ ( ud -- )"
" .KB               \ ( u -- ) prints 12345678 as 12,345.678"
" .MB               \ ( u -- ) prints 12345678 as 12.345"
" .MSECS            \ ( ud -- )"

" ENUM              \ definer; ( init -- ) ENUM name:  then use name: red name: blue etc."
" 2^x               \ ( x -- 2^x )"
" LOG2              \ ( u -- hi_bit# | -1 )"
" #BITS             \ ( u -- #bits )"
" LOWEST-BIT        \ ( u -- lo_bit# | -1 )"
" POWER-OF-2?       \ ( u -- bool )"
" 16B->S            \ ( 16b -- n ) sign-extend a character/word"
" DXOR              \ ( d1 d2 -- d1^d2 )"
" DAND              \ ( d1 d2 -- d1&d2 )"
" DOR               \ ( d1 d2 -- d1|d2 )"
" DINVERT           \ ( d -- ~d )"
" RANDOMIZE         \ ( -- )  (Re)initialize random number generator"
" RANDOM            \ ( -- u ) Fairly random number (integer)"
" CHOOSE            \ ( n -- u )  0 <= u < n  pick random number from range"
" FRANDOM           \ ( F: -- r )  Random floating-point number < 2^63"
" FCHOOSE           \ ( n -- ) ( F: -- ur ) 0 <= ur < r  pick random number from range"
" FPREM             \ ( F: r1 r2 -- rem[r1/r2] ) take FP remainder"
" FP/REM            \ ( F: r1 r2 -- rem[r1/r2] ) ( -- div[r1/r2] ) take FP remainder and quotient"
" NOW?              \ ( cfa -- ) Compile if compiling, else execute"
" 32B, 16B,         \ ( n -- )  comma 32 and 16-bit numbers without aligning"
" F#80              \ text is ignored if package is not extended precision"
" F#64              \ text is ignored if package is not double precision"
" F#32              \ text is ignored if package is not single precision"
" +E.R              \ ( fieldwidth> -- ) ( F: r -- ) print in field"
" +E.               \ ( -- ) ( F: r -- ) print in default field"
" (F.N1)            \ ( -- c-addr u ) ( F: r -- ) format in engineering notation"
" F.N1              \ ( F: r -- ) print in engineering notation with trailing space"
" (F.N2)            \ ( -- c-addr u ) ( F: r -- ) format in engineering notation, no space"
" F.N2              \ ( F: r -- ) print in engineering notation, no space"
" FDUMP             \ ( a-addr +n -- ) print +n floats from a-addr"
" DFDUMP            \ ( a-addr +n -- ) print +n dfloats from a-addr"
" SFDUMP            \ ( a-addr +n -- ) print +n sfloats from a-addr"
" SOURCELINE#       \ ( -- +n )"
" SOURCEFILENAME    \ ( -- c-addr u )"
" EXEC: .. EXEC;    \ ( index -- ? ) EXEC: in-line jump (call) table"
" BIT?              \ ( base bit# -- ? ) test a bit"
" -BIT?             \ ( base bit# -- bit# ? ) test a bit"
" BIT-RESET         \ ( base bit# -- ) reset a bit"
" BIT-SET           \ ( base bit# -- ) set a bit"
" BIT-FLIP          \ ( base bit# -- ) flip a bit"
" ?FILE             \ ( error# -- ) Default error handler for file I/O"
" PAD$              \ create: ( u -- )  use: ( -- addr )"
" NPAD$             \ ( size -- ) "
" RINGBUFFER        \ ( number_8K_buffers -- ) ( -- addr )"
" CELLPACK          \ ( c-addr1 u1 addr2 -- addr2 )"
" CELLPLACE+        \ ( c-addr1 u a2 -- )"
" CELLCHAR+         \ ( char addr -- )"

" $TEMP             \ ( c-addr1 u1 -- c-addr2 u2 )"
" $FREE             \ ( c-addr2 u2 -- )"
~ OVERWRITES        \ ( c-addr u "name" -- ) uses (overw) ( c-addr u c-addr2 u2 -- c-addr3 u3 )~
~ $+TO              \ ( c-addr u "name" -- ) uses (addto) ( c-addr u c-addr2 u2 -- c-addr3 u3 )~

~ MULTI-LINE        \ ( quote "ccc<quote>" -- str len ) Limited to 4096 characters~
" C!+  C+!+  D+!+   \ ( <type> addr1 -- addr2 )"
" CHAR-APPEND       \ ( c-addr u c -- c-addr2 u2 )"
" CHAR-PREPEND      \ ( c-addr u c -- c-addr2 u2 )"
" CPLACE+           \ ( char addr -- )"
" Split-At-WS       \ ( addr1 n1 -- addr1 n2 addr1+n2 n1-n2 )"
" Split-At-Char     \ ( addr1 n1 char -- addr1 n2 addr1+n2 n1-n2 )"
" Split-At-Word     \ ( addr1 n1 addr2 n2 -- addr1 n3 addr1+n4 n1-n4 )"
" -LEADING          \ ( c-addr u -- c-addr2 u2 )"
" -LEADING-WS       \ ( c-addr u -- c-addr2 u2 )"
" -TRAILING-WS      \ ( c-addr u -- c-addr2 u2 )"

~ MACRO%            \ ( "param1" ... "paramn" -- ) Macro creation word allowing parameter insertion if "%" found.~
" LOOP~ LOOP[       \ ( end start -- ) use % to insert compile-time loop index"
" +LOOP~ +LOOP[     \ ( end start step -- ) use % to insert compile-time loop index"

" ?EXIT  ?LEAVE"

" CD$               \ ( -- c-addr u ) Current workding directory"
" ONLY-PATH         \ ( c-addr u1 -- c-addr u2 ) Only path"
" ONLY-FILENAME     \ ( c-addr u1 -- c-addr u2 ) Only filename"
" ONLY-BASEFILENAME \ ( c-addr1 u1 -- c-addr2 u2 ) filename without extension ( .xxxxxx )"
" PATH-HERE         \ ( -- c-addr u ) The dirpath to the file currently being interpreted"
" +INCLUDED         \ ( c-addr u -- ) INCLUDE the file (c-addr u), in the same directory as the current file"
~ +INCLUDE          \ ( "name" -- ) Parsing version of +INCLUDE~
" FILE-EXISTS?      \ ( c-addr u -- TRUE=exists ) TRUE if the file exists (See: FILE-STATUS)."
" FILE-TIME         \ ( c-addr u -- ftime|0 ) 100ns increments since the last write to this file (0 is probably FILE NOT FOUND)."
" FILE-BIRTH        \ ( c-addr u -- u ) Alias for FILE-TIME"
" UNTAB             \ ( c-addr u -- addr2 u2 ) remove TABs from this string (note: in-place!)"
" UNQUOTE           \ ( c-addr u -- addr2 u2 ) Remove a leading and trailing double quote character"
~ UNEXE             \ ( c-addr u -- addr2 u2 ) Remove a trailing ".exe" string~
~ +SLASH?           \ ( c-addr u -- addr2 u2 ) Add a trailing "\" or "/" when it is not there yet~
" SLURP-FILE        \ ( c-addr u -- addr2 u2 ) The location addr2 is transient"
" SLURP-FILE(1)     \ ( c-addr u -- addr2 u2 ) User must deallocate addr2. Also: SLURP-FILE(2) and (3)"

~ $"                \ ( 'cccc' -- addr ) compile string, leave address~
" PLACE+            \ ( c-addr u 'sum$ -- ) add string to sum"
" $+                \ ( c-addr1 u1 c-addr2 u2 -- c-addr3 u3 )"
"                   \   add str2 to str1. Result str3 is member of a bufferpool"
" $>UPC             \ ( c-addr u -- c-addr u ) convert (in place) to uppercase"
" $>LWC             \ ( c-addr u -- c-addr u ) convert (in place) to lowercase"
" ZCOUNT            \ ( zaddr -- addr u ) length of a C-string" ;

-marcel

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

#49707

From	anton@mips.complang.tuwien.ac.at (Anton Ertl)
Date	2016-07-31 13:13 +0000
Message-ID	<2016Jul31.151313@mips.complang.tuwien.ac.at>
In reply to	#49703

mhx@iae.nl writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes Re: Implementing binary search without going deeper than top 2 items on stack?
>
>> mhx@iae.nl writes:
>[..]
>>>the end test suggests that useful general factors
>>>of the underlying Forth system are also not used:
>
>>>  here cell - constant XX
>>>  + dup YY !
>>>  = . .s
[...]
>I pointed out 3 useful factors that pop up in the post discussed.

I don't see any conceptual unity in these sequences, so I would not
factor them into a word.  And looking at the search results you show,
you don't do it, either, but just write the sequence.  The only
exception I see is:

>C:\dfwforth\examples\benchmar\taxi4p-x.frt(62): : ]:                   here swap - constant ;

So the example could have loaded this benchmark in order to get "]:",
and then written

create first 1 , 3 , 5 , 7 , 9 , cell ]: last

I doubt that this was the intended usage of "]:" (I guess more like
FIRST ]: SIZE); in any case, it does not improve the code.  Actually,
if the intention was to make it shorter, it could have been written as

create first 1 , 3 , 5 , 7 , here 9 , constant last

but apparently the programmer found that less satisfactory.

- 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/

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

#49456

From	anton@mips.complang.tuwien.ac.at (Anton Ertl)
Date	2016-07-25 07:51 +0000
Message-ID	<2016Jul25.095102@mips.complang.tuwien.ac.at>
In reply to	#49393

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/

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

#49460

From	"Elizabeth D. Rather" <erather@forth.com>
Date	2016-07-24 22:48 -1000
Message-ID	<vsCdncXT4IXrTwjKnZ2dnUU7-RnNnZ2d@supernews.com>
In reply to	#49456

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."
==================================================

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

#49489

From	hughaguilar96@gmail.com
Date	2016-07-25 10:02 -0700
Message-ID	<1333f5db-e5a5-4176-bb79-f4e8867a2424@googlegroups.com>
In reply to	#49456

On Monday, July 25, 2016 at 1:11:40 AM UTC-7, Anton Ertl wrote:
> 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.

Charles Moore is supposedly dead-set against local variables, yet #2 above is essentially an implementation of local variables (they are always given the names A and R rather than allowing the user to declare the names). I assume that the A and R registers were saved somewhere (most likely the return-stack) at the entry to the colon word and were then restored again at the exit from the colon word, so they don't clobber the A and R values being used by the calling function.

When I was programming in UR/Forth, which lacked local variables, I routinely relied on #1 above --- a lot of code was easier in x86 assembly-language than in Forth-83 because it the x86 has several free registers for holding intermediate values --- I still do the same thing in SwiftForth despite the fact that SwiftForth has local variables (SwiftForth's local variables are abysmally slow due to the local-frame pointer being a user-variable rather than a register).

Anyway, all of this is old-school Forth going back to the 1980s or early 1990s --- MFX written in 1994/1995 had local variables --- I am opposed to the overuse of local variables, which I consider to be the sign of the recalcitrant C programmer, but I will use local variables when necessary.

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

#49491

From	humptydumpty <ouatubi@gmail.com>
Date	2016-07-25 10:10 -0700
Message-ID	<76c43271-8ea8-4440-8f32-63c3f5f7e289@googlegroups.com>
In reply to	#49489

On Monday, July 25, 2016 at 8:02:27 PM UTC+3, hughag...@gmail.com wrote:
> On Monday, July 25, 2016 at 1:11:40 AM UTC-7, Anton Ertl wrote:
> > 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.
> 
> Charles Moore is supposedly dead-set against local variables, yet #2 above is essentially an implementation of local variables (they are always given the names A and R rather than allowing the user to declare the names). I assume that the A and R registers were saved somewhere (most likely the return-stack) at the entry to the colon word and were then restored again at the exit from the colon word, so they don't clobber the A and R values being used by the calling function.
> 
> When I was programming in UR/Forth, which lacked local variables, I routinely relied on #1 above --- a lot of code was easier in x86 assembly-language than in Forth-83 because it the x86 has several free registers for holding intermediate values --- I still do the same thing in SwiftForth despite the fact that SwiftForth has local variables (SwiftForth's local variables are abysmally slow due to the local-frame pointer being a user-variable rather than a register).
> 
> Anyway, all of this is old-school Forth going back to the 1980s or early 1990s --- MFX written in 1994/1995 had local variables --- I am opposed to the overuse of local variables, which I consider to be the sign of the recalcitrant C programmer, but I will use local variables when necessary.

Hi!

See
   http://www.ultratechnology.com/1xforth.htm
at the end of page.

Have a nice day,
humptydumpty

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

#49551

From	Alex Dowad <alexinbeijing@gmail.com>
Date	2016-07-26 22:56 -0700
Message-ID	<641bdaff-a4e1-4d23-bd79-eb2a48e7b5b0@googlegroups.com>
In reply to	#49393

Thanks to all for the informative answers!

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

#49702

From	lehs <skydda.barnen@gmail.com>
Date	2016-07-30 23:28 -0700
Message-ID	<058a99a7-3484-42da-a26e-11b707cb2b36@googlegroups.com>
In reply to	#49393

Den söndag 24 juli 2016 kl. 19:41:40 UTC+2 skrev Alex Dowad:
> 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?
> 
> ("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.)
> 
> Or is the answer "if you're using binary search, you're doing it wrong. Don't use binary search"?
> 
> Thanks all,
> Alex Dowad
I which I could produce such ideal code still being productive. It's worth striving towards, but I wouldn't let it be an obstacle in my programming. A good programming style is a style that produce efficient and well documented code. I understand Charles Moores directives as ideals, pointing out the right direction, rather than as demands stopping me from programming.

But I'm very pleased when I sometimes succeed with ideal programming.

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

#49704

From	hughaguilar96@gmail.com
Date	2016-07-31 00:19 -0700
Message-ID	<cf785e1f-bc80-4b45-9994-2c522f674df7@googlegroups.com>
In reply to	#49702

On Saturday, July 30, 2016 at 11:28:37 PM UTC-7, lehs wrote:
> But I'm very pleased when I sometimes succeed with ideal programming.

BTW: Did you ever get my new novice-package with string-stack.4th in it? I emailed it multiple times, but you seemed to be having problems with your email because you kept saying that you hadn't gotten it.

I'm going to put it on a webpage pretty soon, so it can just be downloaded.

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

#49705

From	lehs <skydda.barnen@gmail.com>
Date	2016-07-31 00:31 -0700
Message-ID	<7c00e3bf-3663-44ba-9529-feaf5d0d4303@googlegroups.com>
In reply to	#49704

Den söndag 31 juli 2016 kl. 09:19:04 UTC+2 skrev hughag...@gmail.com:
> On Saturday, July 30, 2016 at 11:28:37 PM UTC-7, lehs wrote:
> > But I'm very pleased when I sometimes succeed with ideal programming.
> 
> BTW: Did you ever get my new novice-package with string-stack.4th in it? I emailed it multiple times, but you seemed to be having problems with your email because you kept saying that you hadn't gotten it.
> 
> I'm going to put it on a webpage pretty soon, so it can just be downloaded.

Yes thank you!
It might have handled the gmail app wrong? Suddenly it was there, but was invivible a long time. I haven't evaluated it yet, but soon will.

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

csiph-web

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

Contents

#49701

#49703

#49707

#49456

#49460

#49489

#49491

#49551

#49702

#49704

#49705