MERGE-SORT

[Albert van der Horst]

I've documented the MERGE-SORT of ciforth in a separate wiki.
https://github.com/albertvanderhorst/ciforth/wiki/MERGESORT

If you fetch the source for it from git, please use the latest
pre-release. I publish because finally I'm happy with it.
This facility is pretty canonical, I mean it could hardly be
done any other way. Suitable for a library?

Groetjes Albert
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[Albert van der Horst]

In article <p83ema$83r$1...@cherry.spenarnc.xs4all.nl>,

Albert van der Horst <alb...@cherry.spenarnc.xs4all.nl> wrote:
>I've documented the MERGE-SORT of ciforth in a separate wiki.
>https://github.com/albertvanderhorst/ciforth/wiki/MERGESORT

That must be
https://github.com/albertvanderhorst/ciforth/wiki/MERGE-SORT

>
>If you fetch the source for it from git, please use the latest
>pre-release. I publish because finally I'm happy with it.

That is not up to date, sorry.
What the hell, it is just 32 lines.

\ ---------------------------------------
\ (MERGE) \ AvdH A3dec02
\ list : sorted ulist : unsorted listp : list level
\ For EL1 and EL2, return EL1 and EL2 plus "el1 IS lower".
VARIABLE *<M : LL< 2DUP *<M @ EXECUTE ;
VARIABLE *->M \ Contains XT
\ For EL return next EL of list.
: >N *->M @ EXECUTE @ ;
\ For LIST and EL , hang the list off the element.
: LINK! *->M @ EXECUTE ! ;
\ For LIST1 ( > ) LIST2 return LIST1 (>) LIST2' advanced
: FIND-END BEGIN DUP >R >N DUP IF LL< 0= ELSE 0 THEN
WHILE RDROP REPEAT DROP R> ;
\ Merge LIST1 ( > ) LIST2.
: (MERGE) BEGIN FIND-END DUP >R DUP >N >R LINK!
R> R> OVER 0= UNTIL 2DROP ;

\ ---------------------------------------
( MERGE-SORT ) "(MERGE)" WANTED \ AvdH B7dec17

\ Merge LIST1 and LIST2, leave merged LIST.
: MERGE LL< IF SWAP THEN DUP >R (MERGE) R> ;
\ Cut ULIST in two. Return LIST and remaining ULIST.
: SNIP DUP BEGIN DUP >N DUP IF LL< ELSE 0 THEN
WHILE NIP REPEAT >R 0 SWAP LINK! R> ;
\ Keep on merging as long as two listp 's have the same level.
: TRY-MERGES BEGIN >R OVER R@ =
WHILE NIP MERGE R> 1+ REPEAT R> ;
\ Expand zero, ulist into zero list, level .... list, level
: EXPAND BEGIN SNIP >R 1 TRY-MERGES R> DUP WHILE REPEAT DROP ;
\ Keep on merging list-level pairs until end-sentinel.
: SHRINK DROP BEGIN OVER WHILE NIP MERGE REPEAT ;
\ For linked LIST compare XT, next XT, , leave a sorted LIST1.
: MERGE-SORT *->M ! *<M ! 0 SWAP EXPAND SHRINK NIP ;
\ ---------------------------------------

[hughag...@gmail.com]

On Sunday, March 11, 2018 at 7:32:42 AM UTC-7, Albert van der Horst wrote:
> I publish because finally I'm happy with it.
> This facility is pretty canonical, I mean it could hardly be
> done any other way. Suitable for a library?

I wrote a merge-sort last year. I actually wrote several versions --- both recursive and iterative, so there is more than one way to do it.

I'm sure your version is suitable for FFL --- Stephen Pelc enjoys being brown-nosed --- he has no standards for quality in the code that goes into FFL.

This is the iterative version, which is faster than recursion:
--------------------------------------------------------------------------

\ <SORT-LIST> does an InsertionSort. SORT-LIST does a MergeSort which has fewer comparisons and hence is theoretically faster.

: merge-sorted-lists ( headA headB 'comparer -- head ) \ merge headA into headB
>r
nil >r begin \ -- headA headB
over 0= if nip r> swap link rdrop exit then \ if headA is done, append headB and exit
dup 0= if drop r> swap link rdrop exit then \ if headB is done, append headA and exit
2dup rr@ execute nip
if swap delink-one r> rot link >r swap \ headA < headB
else delink-one r> rot link >r then \ headA => headB
again ;

: sort-list { head 'comparer | chunks partial-size -- new-head } \ iterative; 4 hard-coded as SHORT-LIST value
0 \ -- 0 \ sentinel
head length dup 2 rshift to chunks 3 and to partial-size \ CHUNKS does not include the partial
head dup partial-size nth <delink> \ -- 0 chunk rest \ split partial chunk from rest
>r 'comparer <sort-list> r>
?dup if
chunks 0 do
delink-four
>r 'comparer <sort-list> r>
loop \ -- 0 chunks... nil \ split REST into chunks
drop then \ -- 0 chunks... \ the last DELINK-FOUR left a NIL as the REST list
begin over while \ assumes at least one chunk
0 >r \ sentinel
begin ?dup while
over if 'comparer merge-sorted-lists then
>r repeat \ --
0 \ sentinel
begin r> ?dup while
r@ if r> 'comparer merge-sorted-lists then
repeat \ -- 0 chunks...
repeat \ -- 0 head
nip ; \ -- head

\ According to my tests, SORT-LIST is slightly better than <SORT-LIST> for big lists.
\ Both SORT-LIST and <SORT-LIST> are close to 1/4 second to sort a SEQ list of about 4000 elements, so there is no practical difference.
\ If you have a lot of short lists to sort, then <SORT-LIST> may be better because SORT-LIST has a lot of overhead.
\ Setting the SHORT-LIST value to a small number boosts the speed, but increases the memory usage. <SORT-LIST> has no memory usage at all.

--------------------------------------------------------------------------

[hughag...@gmail.com]

On Sunday, March 11, 2018 at 11:26:09 AM UTC-7, hughag...@gmail.com wrote:
> On Sunday, March 11, 2018 at 7:32:42 AM UTC-7, Albert van der Horst wrote:
> > I publish because finally I'm happy with it.
> > This facility is pretty canonical, I mean it could hardly be
> > done any other way. Suitable for a library?
>
> I wrote a merge-sort last year. I actually wrote several versions --- both recursive and iterative, so there is more than one way to do it.

Every time that I post working ANS-Forth code, I kill the thread!

Working ANS-Forth code is like kryptonite to the ANS-Forth cult.
The ANS-Forth cult appear to be Superman here on comp.lang.forth, boasting about how they set the Standard for the entire Forth community.
But when they encounter working ANS-Forth code they run away in fear!

[Gerry Jackson]

In article <p83ema$83r$1...@cherry.spenarnc.xs4all.nl>,
Albert van der Horst <alb...@cherry.spenarnc.xs4all.nl> wrote:

>I've documented the MERGE-SORT of ciforth in a separate wiki.
>https://github.com/albertvanderhorst/ciforth/wiki/MERGESORT

That must be
https://github.com/albertvanderhorst/ciforth/wiki/MERGE-SORT
>

>If you fetch the source for it from git, please use the latest

- hide quoted text -

>This facility is pretty canonical, I mean it could hardly be
>done any other way. Suitable for a library?
>

For a ciforth library - perhaps.

For an ANS Forth library -certainly not, a library program should be
usable without the user needing to modify it or (if he has to)
understand it:
1. It has ciforth-isms e.g. WANTED
2. Any non-standard words should be defined e.g. RDROP
3. It enhances Forth's reputation for unreadability which is typical of
code written in blocks i.e. constrained to 16 lines of 64 characters and
hence 'rectangular' in appearance.
4. No stack comments - what does MERGE expect on the stack?
5. No test program so a user can't try it out on the forth system being
used.

In short a user would have to do quite a bit of work to use it on
another system and would probably write his own version.

--

Gerry

[Albert van der Horst]

In article <pttgdp$4sg$1...@dont-email.me>,

You don't like this style, so noted.
I can't argue with a negative attitude.

I'll point out one thing. The wiki about this thing makes it
usable above the 1% percentile of Forth tools.
This is library code, all words except MERGE could be hidden.

Okay two things, you don't need stack comment if the word is
documented like it is. There actually is stack comment, just not in
the preposterous style Forthers are used to.

This piece of code could be transformed by a blank line here and
there and uppercasing. What is really offputting for non-Forthers
is (addr1 addr2 -- ).

>Gerry

[m...@iae.nl]

On Saturday, December 1, 2018 at 12:35:54 PM UTC+1, Albert van der Horst wrote:
> In article <pttgdp$4sg$1...@dont-email.me>,
> Gerry Jackson <ge...@jackson9000.fsnet.co.uk> wrote:
> >
> >In article <p83ema$83r$1...@cherry.spenarnc.xs4all.nl>,
> >Albert van der Horst <alb...@cherry.spenarnc.xs4all.nl> wrote:

[..]

I decided to document my thoughts when reading the code
for the first time.

> >\ ---------------------------------------
> >\ (MERGE) \ AvdH A3dec02
> >\ list : sorted ulist : unsorted listp : list level

What does that mean?

> >\ For EL1 and EL2, return EL1 and EL2 plus "el1 IS lower".

What are EL1 and EL2? Does this mean ( el1 el2 -- el1 el2 bool ) ?
Why does it return EL1 and EL2?

Is the comment referring to LL< ? Why is *<M in front there?
Why isn't it called *<-M ?

What is the structure of the list EL1..EL2 that come from?

> >VARIABLE *<M : LL< 2DUP *<M @ EXECUTE ;
> >VARIABLE *->M \ Contains XT
> >\ For EL return next EL of list.
> >: >N *->M @ EXECUTE @ ;
> >\ For LIST and EL , hang the list off the element.

"Hang the list .." ??

> >: LINK! *->M @ EXECUTE ! ;

Is this storing a _link_ or a _data_ item? Does the list
have data and links (probably ... )

> >\ For LIST1 ( > ) LIST2 return LIST1 (>) LIST2' advanced

Why the spaces? Are the brackets important? Why the quote?

> >: FIND-END BEGIN DUP >R >N DUP IF LL< 0= ELSE 0 THEN
> > WHILE RDROP REPEAT DROP R> ;
> >\ Merge LIST1 ( > ) LIST2.

Spaces? Probably some secret convention?

> >: (MERGE) BEGIN FIND-END DUP >R DUP >N >R LINK!
> > R> R> OVER 0= UNTIL 2DROP ;
> >
> >\ ---------------------------------------
> >( MERGE-SORT ) "(MERGE)" WANTED \ AvdH B7dec17
> >
> >\ Merge LIST1 and LIST2, leave merged LIST.

That would be OK, but I still have no idea what kind of lists.

> >: MERGE LL< IF SWAP THEN DUP >R (MERGE) R> ;

LL< does a @ EXECUTE of something, so I have really no
clue what is happening here.

> >\ Cut ULIST in two. Return LIST and remaining ULIST.
> >: SNIP DUP BEGIN DUP >N DUP IF LL< ELSE 0 THEN
> > WHILE NIP REPEAT >R 0 SWAP LINK! R> ;

What do I get back when the list is already ordered or
completely unordered?

> >\ Keep on merging as long as two listp 's have the same level.

Level?? Are we talking lists of lists here?

> >: TRY-MERGES BEGIN >R OVER R@ =
> > WHILE NIP MERGE R> 1+ REPEAT R> ;
> >\ Expand zero, ulist into zero list, level .... list, level

Gooi maar in mijn pet.

> >: EXPAND BEGIN SNIP >R 1 TRY-MERGES R> DUP WHILE REPEAT DROP ;
> >\ Keep on merging list-level pairs until end-sentinel.
> >: SHRINK DROP BEGIN OVER WHILE NIP MERGE REPEAT ;
> >\ For linked LIST compare XT, next XT, , leave a sorted LIST1.

XTs? So there are not just links and data?

> >: MERGE-SORT *->M ! *<M ! 0 SWAP EXPAND SHRINK NIP ;
> >\ ---------------------------------------

[..]

> >2. Any non-standard words should be defined e.g. RDROP

Because when it isn't, the user must be able to read the
code to find out what RDROP does.

> >3. It enhances Forth's reputation for unreadability which
> is typical of code written in blocks i.e. constrained to 16
> lines of 64 characters and hence 'rectangular' in appearance.

I am sure it is possible to write well-documented
code in blocks!

> >4. No stack comments - what does MERGE expect on the stack?

And the layout of these lists(?) should be documented.

> >5. No test program so a user can't try it out on the forth
> >system being used.

Indeed. A test program would have answered all
questions.

> >In short a user would have to do quite a bit of work to use it on
> >another system and would probably write his own version.

Worse, he wouldn't even realize that this code was doing
what he was looking for.

> You don't like this style, so noted.
> I can't argue with a negative attitude.

It's is not a negative attitude. Then he would have
ignored your post.

> I'll point out one thing. The wiki about this thing makes it
> usable above the 1% percentile of Forth tools.

Wiki? Where?
And what does the comment mean? Is that a good or a bad thing?

> This is library code, all words except MERGE could be hidden.

Why show them in a post then? It would have been more
appropriate to meticulously explain what MERGE does and
what kind of lists it works on.

> Okay two things, you don't need stack comment if the word is
> documented like it is. There actually is stack comment, just not in
> the preposterous style Forthers are used to.

It doesn't strike me as vastly superior, but who knows?
We could write our comments in Latin, or paste in
mirror-imaged bitmaps.

-marcel

[Anton Ertl]

He has advocated his style here for a number of years, but nobody has
picked it up. Either his style is not significantly superior, or the
Forthers are too dumb or too conservative to recongnize the
superiority of his style. There are some very conservative Forthers,
but there are also some that are going in new directions; are these
all dumb?

Looking beyond Forth, Postscript docoments the stack effect in a
similar way to Forth. E.g., instead of

swap ( x1 x2 -- x2 x1 )

Postscript documents the equivalent operator "exch" as follows:

ob1 ob2 *exch* ob2 ob1

For the JavaVM, the documentation of the stack effect of swap is:

value2, value1 -> value1, value2

Beyond stack-based languages, the parameters are not just
documentation, but part of the language. But if covering the
parameters in a pile of prose was really such a good idea, I expect
that some programming language designer would have thought of that,
and the programming language would have become highly popular.

- 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 2018: http://www.euroforth.org/ef18/

[foxaudio...@gmail.com]

On Saturday, December 1, 2018 at 6:55:47 PM UTC-5, m...@iae.nl wrote:

>Gooi maar in mijn pet.

For those of us who are amateur students of Dutch, what does this mean?
I understand the words but have never heard the expression.

My guess is that it means something like: "Good but, I already know that."

[m...@iae.nl]

Officially, "Gooi maar in mijn pet" means not being impressed by
something (implying the listener *did* understand what was being said
or written). What I meant however, is the variant "het zal wel,
daar kan ik niks mee", i.e. "It might well be, but I can't grok it."
It suggests the speaker is somewhat annoyed by the failure to
understand, and is not convinced it is his fault entirely.

-marcel

[Albert van der Horst]

In article <e8789ee0-3614-494f...@googlegroups.com>,

Instead of arguing with those points I'll demonstrate some practical
portability. The wiki, by the way is at
https://github.com/albertvanderhorst/ciforth/wiki/MERGE-SORT

The best way to use a library item is not trying to comprehend the source
but start from the manual.
"
The stack diagram of MERGE-SORT is ( list1 comparison-XT link-XT -- list2 )

A mergesort requires objects that have a link-field. During merging
those link-fields are altered. list objects are pointers, representing
the first object of a sublist. Following the links one must arrive at
a null pointer.
"
The above 4 lines are essential, more essential than stack diagrams.

In order to find a linked list in the wild, I use the lisp of Max Probst,
defined for gforth.
https://github.com/albertvanderhorst/forthlisp
( I would have used Probst github, but he has deleted it since I cloned it.
The clone has improved ISO compatibility, maybe that's why he deleted
the original.)
The following is basically a session dump, but I've interspersed some comments.
I've added a files easy.fs with some conveniences among them .symtab that
is the equivalent of Forth WORDS and nicely shows the linked list
that is the lisp symbl table.

gforth lisp.fs easy.fs

redefined offset redefined struct redefined field redefined end-struct
redefined cell% redefined %allocate redefined lisp redefined car
redefined cdr redefined number redefined nameu redefined namea
redefined xt redefined Body with body redefined lisp redefined lisp
Gforth 0.7.0, Copyright (C) 1995-2008 Free Software Foundation, Inc.
Gforth comes with ABSOLUTELY NO WARRANTY; for details type `license'
Type `bye' to exit
ok
.symtab
\ I've added a .symtab, similar to words in Forth
display
eq?
cdr
car
cons
*
-
+
cond
t
define
lambda
quote
ok
SEE .symtab
\ This is how it looks, spot the linked list in here?
\ Gforth decompiles WHILE as IF.
: .symtab
cr symtab-first @
BEGIN dup
IF dup symtab-name type cr symtab-next @
REPEAT ; ok
\ Lets include the code, scouts honour, just the above two screens
INCLUDE /tmp/m.fs

/tmp/m.fs:17: Undefined word

( MERGE-SORT ) >>>"(MERGE)"<<< WANTED \ AvdH B7dec17

Backtrace:
$F7133EDC throw
$F7140638 no.extensions
$F7134054 interpreter-notfound1
ok

\ Oops, ciforth-isms! Lets define them away. See if it even compiles.
: "(MERGE)" ; ok
: WANTED ; ok

INCLUDE /tmp/m.fs redefined *<M redefined LL< redefined *->M redefined
>N redefined LINK! redefined FIND-END redefined (MERGE) ok
\ Oops, it loads
\ What the heck, let's try it!
.S <0> ok
\ Now we can do a merge-sort on the list
\ Apparently we need a start position
symtab-first @
\ And a comparison xt
:NONAME >R symtab-name R> symtab-name compare 0< ;
\ And a next xt, but we have it.
' symtab-next ok

MERGE-SORT ok

.S <1> 138342264 ok
\ This is the start of the linked list, now we have to put it back
\ or the lisp is screwed up.
symtab-first ! ok

.symtab
\ There you are, sorted.
*
+
-
car
cdr
cond
cons
define
display
eq?
lambda
quote
t

Now you! Take any 32 portable lines from anywhere in iforth and
show it can do something sensible for some Forth without too much
fidling.

>
>-marcel

[Alex McDonald]

On 02-Dec-18 18:33, Albert van der Horst wrote:

>
> The best way to use a library item is not trying to comprehend the source
> but start from the manual.
> "
> The stack diagram of MERGE-SORT is ( list1 comparison-XT link-XT -- list2 )
>
> A mergesort requires objects that have a link-field. During merging
> those link-fields are altered. list objects are pointers, representing
> the first object of a sublist. Following the links one must arrive at
> a null pointer.
> "
> The above 4 lines are essential, more essential than stack diagrams.

They explain different things; and therefore one is not more essential
than the other.

--
Alex

[NN]

...> In order to find a linked list in the wild, I use the lisp of Max Probst,

> defined for gforth.
> https://github.com/albertvanderhorst/forthlisp
> ( I would have used Probst github, but he has deleted it since I cloned it.
> The clone has improved ISO compatibility, maybe that's why he deleted
> the original.)

...

Do you mean this one ?

https://github.com/schani/forthlisp

[foxaudio...@gmail.com]

Dank je wel

[Albert van der Horst]

In article <aeb16c1e-881d-48d9...@googlegroups.com>,

<foxaudio...@gmail.com> wrote:
>On Saturday, December 1, 2018 at 6:55:47 PM UTC-5, m...@iae.nl wrote:
>
>>Gooi maar in mijn pet.
>
>For those of us who are amateur students of Dutch, what does this mean?
>I understand the words but have never heard the expression.

Literally, "throw it in my hat".

It is commonly used by people who in their heart feel they are
intellectually inferior, about a subject they don't understand and
are not willing to study.
It is something Trump would say with respect to climat change,
if he spoke Dutch.

Hope this helps

>
>My guess is that it means something like: "Good but, I already know
that."

[Gerry Jackson]

The fact that you had to any fiddling to make a 32 line program work on
a standard Forth system means it is unsuitable for an ANS Forth library.
It should have been *you* to make it compliant in the first place,
otherwise every user has to do the fiddling to get it to work.

--
Gerry

[Albert van der Horst]

In article <pu5avo$a71$1...@dont-email.me>,
Gerry Jackson <ge...@jackson9000.fsnet.co.uk> wrote:
<SNIP>

>>
>
>The fact that you had to any fiddling to make a 32 line program work on
>a standard Forth system means it is unsuitable for an ANS Forth library.
>It should have been *you* to make it compliant in the first place,
>otherwise every user has to do the fiddling to get it to work.

This is not a supposedly library candidate. It is a working piece lifted
from ciforth where almost nothing need to be done to work on an other
forth. As I demonstrated.

>
>--
>Gerry

[m...@iae.nl]

On Sunday, December 2, 2018 at 7:33:08 PM UTC+1, Albert van der Horst wrote:
> In article <e8789ee0-3614-494f...@googlegroups.com>,
> <m...@iae.nl> wrote:
> >On Saturday, December 1, 2018 at 12:35:54 PM UTC+1, Albert van
> > der Horst wrote:

[..]

> Instead of arguing with those points I'll demonstrate some practical
> portability. The wiki, by the way is at
> https://github.com/albertvanderhorst/ciforth/wiki/MERGE-SORT
>
> The best way to use a library item is not trying to comprehend the source
> but start from the manual.
> "
> The stack diagram of MERGE-SORT is ( list1 comparison-XT link-XT -- list2 )
>
> A mergesort requires objects that have a link-field. During merging
> those link-fields are altered. list objects are pointers, representing
> the first object of a sublist. Following the links one must arrive at
> a null pointer.
> "
> The above 4 lines are essential, more essential than stack diagrams.

They are indeed essential, but essentially still tell me nothing.
Enfin, we now have a first stack diagram, how hard was that.

What do these two XT's do? The link-XT probably is needed to
manipulate the link field of list objects. We would need its
stack diagram to gain insight what is expected of it. The
comparison-XT probably compares something in the list object,
but without a stack diagram we still can not use MERGE-SORT.
It isn't clear in what sense the list will be sorted (up? down?
stable?). We see that a list2 is returned, but is this
a NEW list, or is it the original data but now linked
in a sorted way?

> In order to find a linked list in the wild, I use the lisp of Max Probst,
> defined for gforth.
> https://github.com/albertvanderhorst/forthlisp
> ( I would have used Probst github, but he has deleted it since I cloned it.
> The clone has improved ISO compatibility, maybe that's why he deleted
> the original.)

So your Wiki doesn't have any good examples?

[..]

> \ Apparently we need a start position
> symtab-first @

And what is symtab-first's definition? How do I know that
this conforms to what MERGE-SORT wants?

> \ And a comparison xt
> :NONAME >R symtab-name R> symtab-name compare 0< ;
> \ And a next xt, but we have it.
> ' symtab-next ok

It seems likely, but I can't be sure. By name, I'd assume
symtab-next just gives me an XT to go to the next link, not
to relink something. This means I made a wrong turn in my
trying to understand above. I must start from the top.

> MERGE-SORT ok
>
> .S <1> 138342264 ok
> \ This is the start of the linked list, now we have to put it back
> \ or the lisp is screwed up.

The lisp or the list?

> symtab-first ! ok

Oh yes, that final store is perfectly obvious.
Why doesn't MERGE-SORT do this by itself? Apparently
sometimes we don't want that, and it is so blaringly
obvious, especially without reading the source code,
that it needs no comment.

> Now you! Take any 32 portable lines from anywhere in iforth and
> show it can do something sensible for some Forth without too much
> fidling.

If the above is your definition of something useful ("The wizard
explains that what the audience saw was clearly not a random
event"), I can just take any 32 lines from iForth :-) "Type the
final word "!" and the terminal magically closes! As a bonus,
your Linux partition has been erased in a very efficient way!"

Now don't take me wrong -- MERGE-SORT does very probably exactly
what you promise and is without a doubt vastly superior to any
32 lines in iForth. My only peeve is that, from what you have
posted in this thread, it is not obvious at all how *I* should
use it. This can be easily fixed, as it is only comments.

-marcel

[Albert van der Horst]

In article <0ec110b2-5fe5-453e...@googlegroups.com>,

<m...@iae.nl> wrote:
>On Sunday, December 2, 2018 at 7:33:08 PM UTC+1, Albert van der Horst wrote:
>
>> In order to find a linked list in the wild, I use the lisp of Max Probst,
>> defined for gforth.
>> https://github.com/albertvanderhorst/forthlisp
>> ( I would have used Probst github, but he has deleted it since I cloned it.
>> The clone has improved ISO compatibility, maybe that's why he deleted
>> the original.)
>
>So your Wiki doesn't have any good examples?

Apparently you didn't look. However sorting the dictionary of
ciforth itself might be less convincing in this context.

<SNIP>

[minf...@arcor.de]

Am Mittwoch, 5. Dezember 2018 02:09:02 UTC+1 schrieb Albert van der Horst:
> In article <0ec110b2-5fe5-453e...@googlegroups.com>,
> <m...@iae.nl> wrote:
> >On Sunday, December 2, 2018 at 7:33:08 PM UTC+1, Albert van der Horst wrote:
> >
> >> In order to find a linked list in the wild, I use the lisp of Max Probst,
> >> defined for gforth.
> >> https://github.com/albertvanderhorst/forthlisp
> >> ( I would have used Probst github, but he has deleted it since I cloned it.
> >> The clone has improved ISO compatibility, maybe that's why he deleted
> >> the original.)
> >
> >So your Wiki doesn't have any good examples?
>
> Apparently you didn't look. However sorting the dictionary of
> ciforth itself might be less convincing in this context.
>

Test data are also available from
https://www.random.org/

[Doug Hoffman]

On 12/2/18 1:33 PM, Albert van der Horst wrote:


> Now you! Take any 32 portable lines from anywhere in iforth and
> show it can do something sensible for some Forth without too much
> fidling.

The following is primarily about my idea of code documentation and
compatibility on different Forths, not necessarily the perfection
of the code:

-Doug

\ Compatibility tested on:
\ MacForth v 10.550
\ SwiftForth i386-Mac OS X 3.4.5
\ Gforth 0.7.3
\ VFX Forth for OS X Version: 4.81
\ Mergesort algorithm verified on Oforth V1.2.0

\ *** begin region words
0 value base-ptr
0 value max-ptr
variable current-ptr
: allocate-region ( n -- )
dup >r allocate throw to base-ptr
base-ptr current-ptr ! base-ptr r> + to max-ptr ;
: region-reset base-ptr current-ptr ! ;
: allocate' ( n -- ptr ) \ use allocate' instead of " allocate throw "
current-ptr @ >r current-ptr +!
current-ptr @ max-ptr > abort" region size exceeded" r> ;
\ *** end region words

300 allocate-region \ plenty to run the program below

\ *** begin list words
\ These lists are just contiguous cells with
\ each cell containing an element or element
\ reference.
\ General form of list is "addr size" where
\ addr is addr of first element and size is
\ number of elements in list.
\ Addr can be in dictionary or heap.
: first ( addr -- elem ) @ ;
: removeFirst ( addr size -- elem addr2 size-1 )
over first >r swap cell+ swap 1- r> -rot ;

\ add elem to list
: add ( elem addr size -- ) cells + ! ;

\ create a new empty list in the region with given max size
: new ( size -- addr ) cells allocate' ;

\ print a list
: .list ( addr size xt -- ) locals| xt |
0 ?do dup i cells + xt execute loop drop ;
\ *** end list words

\ *** begin mergesort
0 value compare-xt
\ merge 2 sorted lists
: merge ( left ls right rs -- result rs )
0 0 locals| result ts rs right ls left |
ls rs + new to result
begin
ls 0 > rs 0 > and
while
left first right first compare-xt execute
if left ls removeFirst to ls to left
else right rs removeFirst to rs to right
then result ts add ts 1+ to ts
repeat

\ By now either left or right is empty,
\ it remains to empty the other list.
\ Only one loop will be entered.
begin
ls 0 >
while
left ls removeFirst to ls to left result ts add ts 1+ to ts
repeat
begin
rs 0 >
while
right rs removeFirst to rs to right result ts add ts 1+ to ts
repeat
result ts ;

: mergesort ( m ms -- result ts )
dup 1 <= if ( m ms) exit then
0 0 0 0 locals| left ls right rs |

\ Divide the list into two sublists.
dup 2 / to ls swap to left
( ms) ls - to rs left ls cells + to right

\ Recursively sort both sublists.
left ls recurse to ls to left
right rs recurse to rs to right

\ Then merge the now-sorted sublists.
left ls right rs merge ;
\ *** end mergesort


\ Examples:

\ Integer sort
' <= to compare-xt \ use >= for descending sort
create list1 100 , 2 , 5 , 88 , 1 , 75 , 50 , 66 ,

list1 8 mergesort ' ? .list
\ 1 2 5 50 66 75 88 100 ok
region-reset \ GC


\ String sort
: $, ( adr len -- ) dup 1+ allocate' dup >r place r> , ;
create list2 s" bird" $, s" Zebra" $, s" zebra" $, s" ape" $,
s" cat" $, s" Antalope" $,

: $<= ( ptr1 ptr2 -- flag ) >r count r> count compare 1 < ;
' $<= to compare-xt
: .$ ( adr --) @ space count type ;

list2 6 mergesort ' .$ .list
\ Antalope Zebra ape bird cat zebra ok
region-reset \ GC


\ Oforth:
tvar: compare-xt
# <= to compare-xt \ use >= for descending sort

: removeFirst \ ( array -- elem )
1 swap removeAt ;

\ left and right must be sorted lists.
\ lists are Oforth arrays, which are 1-based.
: merge ( left right -- result )
| result | Array new -> result

while ( left size 0 > right size 0 > and ) [
left first right first compare-xt execute
if left else right then removeFirst result add ]

\ By now either left or right is empty,
\ it remains to empty the other list.
\ Only one loop will be entered.
while ( left size 0 > ) [ left removeFirst result add ]
while ( right size 0 > ) [ right removeFirst result add ]
result ;

\ m is the list to be sorted
: mergesort ( m -- result )
| left right i |
m size 1 <= if m return then
Array new -> left Array new -> right

\ Divide the list into two sublists.
m size 2 /
1 over for: i [ i m at left add ]
1+ m size for: i [ i m at right add ]

\ Recursively sort both sublists.
left mergesort -> left
right mergesort -> right

\ Then merge the now-sorted sublists.
left right merge return ;

\ Example use:
[100, 2, 5, 88, 1, 75, 50, 66] mergesort .
\ [1, 2, 5, 50, 66, 75, 88, 100]
[28.3, 100, 77.0, 1.5, 8.89, 8.8, 2, 77.01] mergesort .
\ [1.5, 2, 8.8, 8.89, 28.3, 77, 77.01, 100]
["bird", "Zebra", "zebra", "ape", "cat", "Antalope"] mergesort .
\ [Antalope, Zebra, ape, bird, cat, zebra]

[hughag...@gmail.com]

On Wednesday, December 5, 2018 at 5:22:42 AM UTC-7, Doug Hoffman wrote:
> \ *** begin region words
> 0 value base-ptr
> 0 value max-ptr
> variable current-ptr

> ...

> 300 allocate-region \ plenty to run the program below

You are using global variables. My code is reentrant.

> \ These lists are just contiguous cells with
> \ each cell containing an element or element
> \ reference.
> \ General form of list is "addr size" where
> \ addr is addr of first element and size is
> \ number of elements in list.
> \ Addr can be in dictionary or heap.

This is an array, not a list.

This also assumes that every element is one cell in size.
This limitation is very familiar!
This is the same limitation that Alex McDonald was promoting for arrays,
when he was attacking my SORT function.
This is the same limitation that Andrew Haley had in his array defining word.
I upgraded this to support any size of element for my ARY in the novice-package.

Keep trying!
When you get some working code that roughly corresponds to my MergeSort,
I will compare it for speed.

[Gerry Jackson]

On 04/12/2018 16:38, Albert van der Horst wrote:
> In article <pu5avo$a71$1...@dont-email.me>,
> Gerry Jackson <ge...@jackson9000.fsnet.co.uk> wrote:
> <SNIP>
>>>
>>
>> The fact that you had to any fiddling to make a 32 line program work on
>> a standard Forth system means it is unsuitable for an ANS Forth library.
>> It should have been *you* to make it compliant in the first place,
>> otherwise every user has to do the fiddling to get it to work.
>
> This is not a supposedly library candidate.

You asked the question about its suitability for a library and I
answered your question.

> It is a working piece lifted
> from ciforth where almost nothing need to be done to work on an other
> forth. As I demonstrated.

Yes but in the (unlikely) event that a 1000 users used your MERGE-SORT
that 'almost nothing' would have to be repeated 1000 times, and it
wouldn't almost nothing as they wouldn't have your knowledge. This is
still true if only half a dozen users.

--
Gerry

[hughag...@gmail.com]

On Sunday, March 11, 2018 at 7:32:42 AM UTC-7, Albert van der Horst wrote:
> I publish because finally I'm happy with it.
> This facility is pretty canonical, I mean it could hardly be
> done any other way. Suitable for a library?

Wow! Canonical implies that it was approved by the Pope!
If it could hardly be done any other way, then it must be perfect --- you don't need any help on improving it!

On Tuesday, December 4, 2018 at 9:38:36 AM UTC-7, Albert van der Horst wrote:
> This is not a supposedly library candidate. It is a working piece lifted
> from ciforth where almost nothing need to be done to work on an other
> forth. As I demonstrated.

So, it was suitable for a library in March but it is not a library candidate now? What happened in between?

If you get enough help on improving it from Anton Ertl etc., you might eventually obtain something that you can be happy with.
It still won't be as good as my code though, because Anton Ertl etc. aren't as good at Forth as I am.

[Albert van der Horst]

In article <5c07c317$0$688$1472...@news.sunsite.dk>,

Doug Hoffman <glid...@gmail.com> wrote:
>
>
>The following is primarily about my idea of code documentation and
>compatibility on different Forths, not necessarily the perfection
>of the code:
>
>-Doug

>: mergesort ( m ms -- result ts )
> dup 1 <= if ( m ms) exit then
> 0 0 0 0 locals| left ls right rs |
>
> \ Divide the list into two sublists.
> dup 2 / to ls swap to left
> ( ms) ls - to rs left ls cells + to right
>
> \ Recursively sort both sublists.
> left ls recurse to ls to left
> right rs recurse to rs to right
>
> \ Then merge the now-sorted sublists.
> left ls right rs merge ;
>\ *** end mergesort

This looks like nice code, but are this really lists?

Demonstrate how it runs on the symbol table in
https://github.com/schani/forthlisp
without adapting the original code of schani, like I dud.

While it is better documented on the micro level than most Forth
programs, and I would happily undertake maintenance for it,
For instance

There is no requirement about the size of the region.
Must it be able to contain a copy of a whole list to be sorted?

(mergesort on general makes sense only where you can't use quicksort.)

Groetjes Albert

[Doug Hoffman]

On 12/6/18 6:07 AM, Albert van der Horst wrote:
> In article <5c07c317$0$688$1472...@news.sunsite.dk>,
> Doug Hoffman <glid...@gmail.com> wrote:
>>
>>
>> The following is primarily about my idea of code documentation and
>> compatibility on different Forths, not necessarily the perfection
>> of the code:
>>
>> -Doug
>> : mergesort ( m ms -- result ts )
>> dup 1 <= if ( m ms) exit then
>> 0 0 0 0 locals| left ls right rs |
>>
>> \ Divide the list into two sublists.
>> dup 2 / to ls swap to left
>> ( ms) ls - to rs left ls cells + to right
>>
>> \ Recursively sort both sublists.
>> left ls recurse to ls to left
>> right rs recurse to rs to right
>>
>> \ Then merge the now-sorted sublists.
>> left ls right rs merge ;
>> \ *** end mergesort
>
> This looks like nice code, but are this really lists?

Arrays are certainly used as lists. We know that mergesort is better
suited for linked-lists, quicksort is better suited for array lists.
But those were not my points.

> Demonstrate how it runs on the symbol table in
> https://github.com/schani/forthlisp
> without adapting the original code of schani, like I dud.

My example showed how to mergesort an array of strings. I'll leave it at
that.

> While it is better documented on the micro level than most Forth
> programs, and I would happily undertake maintenance for it,

Those were two of my points, documentation and maintainability. The
third was the ability to run on any standard Forth, as presented
in the post. As an extra I provided a version for a non-standard Forth
(Oforth).

> For instance
> There is no requirement about the size of the region.
> Must it be able to contain a copy of a whole list to be sorted?

That is a valid point and a weakness of using mergesort with arrays.
Also a weakness of my documentation.
I chose a simple region for garbage collection instead of manual FREE.
Actually the region will need to hold more than just a copy of the
original list.

-Doug

[Albert van der Horst]

In article <5c0909a7$0$691$1472...@news.sunsite.dk>,
Doug Hoffman <glid...@gmail.com> wrote:
<SNIP>

>
>> For instance
>> There is no requirement about the size of the region.
>> Must it be able to contain a copy of a whole list to be sorted?
>
>That is a valid point and a weakness of using mergesort with arrays.
>Also a weakness of my documentation.
>I chose a simple region for garbage collection instead of manual FREE.
>Actually the region will need to hold more than just a copy of the
>original list.

In this case it would be best to have a functioning ALLOCATE and CATCH.

Then
' MERGE-SORT CATCH DUP ALLOCATION-ERROR = IF
." your allocation system can't pull of merge sorting for "
print-more-information
ELSE THROW THEN

After the merge all extra memory would be free again. This approach
would need no documentation effort, normally.

(Note that merge-sort-using-links needs only the stack for storage.)

>
>-Doug

[Doug Hoffman]

On 12/6/18 7:40 AM, Albert van der Horst wrote:

> (Note that merge-sort-using-links needs only the stack for storage.)

I almost used the Rosettacode example (and maybe should have)
which also simply uses the stack for storage. But I was not in love
with the (lack of) documentation, which again was my point. Though
it does appear to be clever code and I congratulate the author.
It also runs as-is on any standard Forth and will also handle strings
or any size data element with the trivial modification I show in my code.

: merge-step ( right mid left -- right mid+ left+ )
over @ over @ < if
over @ >r
2dup - over dup cell+ rot move
r> over !
>r cell+ 2dup = if r> drop dup else r> then
then cell+ ;
: merge ( right mid left -- right left )
dup >r begin 2dup > while merge-step repeat 2drop r> ;
: mid ( l r -- mid ) over - 2/ cell negate and + ;
: mergesort ( right left -- right left )
2dup cell+ <= if exit then
swap 2dup mid recurse rot recurse merge ;
: sort ( addr len -- ) cells over + swap mergesort 2drop ;

create test 8 , 1 , 5 , 3 , 9 , 0 , 2 , 7 , 6 , 5 ,
: .array ( addr len -- ) 0 do dup i cells + @ . loop drop ;
test 10 2dup sort .array \ 0 1 2 3 5 5 6 7 8 9

[Doug Hoffman]

On 12/2/18 1:33 PM, Albert van der Horst wrote:

Albert,

> The stack diagram of MERGE-SORT is ( list1 comparison-XT link-XT -- list2 )
>
> A mergesort requires objects that have a link-field. During merging
> those link-fields are altered. list objects are pointers, representing
> the first object of a sublist. Following the links one must arrive at
> a null pointer.
> "
> The above 4 lines are essential, more essential than stack diagrams.

> \ Now we can do a merge-sort on the list
> \ Apparently we need a start position
> symtab-first @
> \ And a comparison xt
> :NONAME >R symtab-name R> symtab-name compare 0< ;
> \ And a next xt, but we have it.
> ' symtab-next ok
>
> MERGE-SORT ok

I finally got around to testing your MERGE-SORT.

I had to replace RDROP with R> DROP. For a basic
linked-list the next xt is a NOOP, took a little
digging to figure that out. So for the linked lists
I work with *->M can be eliminated from your code,
replacing >N with @ and LINK! with !. This makes
it faster and with smaller source.

I created a ll of 50,000 random integers. Your
code sorted that in 0.016 seconds on my rather
slow machine. Impressive! Nice work.

Yes, I think your mergesort could (should) be part
of anyone's library.

-Doug

[hughag...@gmail.com]

On Monday, December 17, 2018 at 4:11:15 AM UTC-7, Doug Hoffman wrote:
> On 12/2/18 1:33 PM, Albert van der Horst wrote:
> > MERGE-SORT ok
>
> I finally got around to testing your MERGE-SORT.

> ...

> I created a ll of 50,000 random integers. Your
> code sorted that in 0.016 seconds on my rather
> slow machine. Impressive! Nice work.
>
> Yes, I think your mergesort could (should) be part
> of anyone's library.

I assume that you mean a "linked list" of 50,000 random integers.
16 milliseconds to sort 50,000 elements is very fast!
By comparison, my test of my own SORT required about 250 milliseconds for about 4000 elements.
This is about 15.6 times faster than mine, on a list that is about 12.5 times longer than mine.
IIRC, my list contained strings, so COMPARE would be slower than an integer comparison.
I discarded the test code so I can't be sure what I had exactly, but my recollection was strings.
It is also possible that my computer is significantly slower than your "rather slow machine," but I doubt it.

I switch to an insertion sort for partial-lists that are <= 4 elements in length.
There is a slight speed improvement for using MergeSort all the way down to partial-lists that are 2 elements in length, but not much.
I have SHORT-LIST hard-coded at 4 because this reduces memory usage with minimal loss of speed.

All in all, I think that your 16 millisecond time is not true.

You are the same guy who previously posted code in which you described an array of cells as being a "list."
At that time, I said:

On Wednesday, December 5, 2018 at 1:17:58 PM UTC-7, hughag...@gmail.com wrote:
> Keep trying!
> When you get some working code that roughly corresponds to my MergeSort,
> I will compare it for speed.

I haven't seen anything yet.

[Doug Hoffman]

On 12/17/18 6:11 AM, Doug Hoffman wrote:

> Albert,

> I finally got around to testing your MERGE-SORT.

> I created a ll of 50,000 random integers. Your
> code sorted that in 0.016 seconds on my rather
> slow machine. Impressive! Nice work.
>
> Yes, I think your mergesort could (should) be part
> of anyone's library.

Further, it was easy to translate your mergesort
into Oforth code. I benchmarked sort times for:

50,000 random integers
50,000 random integers mixed with floats
50,000 random strings, 1-10 chars each, chars a-z,A-Z

integers: 0.085 seconds
ints/floats: 0.167 seconds
strings: 0.153 seconds

All Oforth code with tests shown below.

Note that the exact same comparator is used for
each data type, thanks to polymorphism. This
enables one to freely mix integers and floats
(using the same code).

All data was dynamically created and subsequently
garbage-collected (transparent GC).

-Doug

p.s., I'm confident Franck Bensusan could improve this.

\ *** begin linked-list code
Object Class new: ll-node ( mutable link, mutable data )
m: initialize \ data --
0 := link := data ;
m: << @link << printcr @data << ;
m: getData \ -- data
@data ;
m: getLink \ -- link
@link ;
m: putLink \ link --
:= link ;

: link \ node n -- node
ll-node new swap over putLink ;
\ *** end linked-list code

import: collect \ to get Stack
tvar: r
Stack new to r
: >r r push ;
: r> r pop ;
: r@ r top ;

\ *** begin merge-sort code based on Albert van der Horst's
\ post on c.l.f. 3/11/2018

\ list : sorted ulist : unsorted listp : list level

\ For EL1 and EL2, return EL1 and EL2 plus "el1 IS lower".

tvar: *<m
: ll< 2dup getData swap getData *<m execute ;

\ For LIST1 ( > ) LIST2 return LIST1 (>) LIST2' advanced

: find-end
while ( dup >r getLink dup if ll< 0= else 0 then ) [ r> drop ]
drop r> ;

\ Merge LIST1 ( > ) LIST2.

: do-merge
begin find-end dup >r dup getLink >r putLink
r> r> over 0=
until 2drop ;

\ Merge LIST1 and LIST2, leave merged LIST.

: merge ll< if swap then dup >r do-merge r> ;

\ Cut ULIST in two. Return LIST and remaining ULIST.

: snip dup
while ( dup getLink dup if ll< else 0 then ) [ nip ]
>r 0 swap putLink r> ;

\ Keep on merging as long as two listp 's have the same level.

: try-merges while ( >r over r@ = ) [ nip merge r> 1+ ] r> ;

\ Expand zero, ulist into zero list, level .... list, level

: expand while ( snip >r 1 try-merges r> dup ) [ ] drop ;

\ Keep on merging list-level pairs until end-sentinel.

: shrink drop while ( over ) [ nip merge ] ;
\ For linked LIST compare XT, leave a sorted LIST1.
: merge-sort to *<m 0 swap expand shrink nip ;
\ ---------------------------------------
\ The stack diagram of merge-sort is ( list1 comparison-XT -- list2 )
\ *** end merge-sort code

tvar: list

: build-linkedlist \ node size -- node \ build with integers
| i | loop: i [ 10000 rand link ] ;
1 ll-node new 50000 build-linkedlist to list
#[ list #> merge-sort to list ] bench
\ [1] (Integer) 84976 \ = 0.085 seconds for 50000 integers

: build-linkedlistf \ node size -- node \ with floats and ints
| i | loop: i [ 10000 rand >float 1000 rand / link ] ;
3.4 ll-node new 50000 build-linkedlistf to list
#[ list #> merge-sort to list ] bench
\ [1] (Integer) 167265
\ = 0.167 seconds for 50000 floats and integers


: one-char \ ( -- c ) \ alpha
| c |
begin
'z' rand -> c
'A' 'Z' c between
'a' 'z' c between or
until c ;
: make-string \ random str of 1 to 10 chars, chars = a-z,A-Z
| s i |
String new -> s
10 rand loop: i [ one-char s add ] s ;

: build-linkedlistS \ node size -- node \ build with strings
| i | loop: i [ make-string link ] ;
"Hello" ll-node new 50000 build-linkedlistS to list
#[ list #> merge-sort to list ] bench
\ [1] (Integer) 152668 \ = 0.153 seconds for 50000 random strings

[Doug Hoffman]

On 12/17/18 8:15 PM, hughag...@gmail.com wrote:
> On Monday, December 17, 2018 at 4:11:15 AM UTC-7, Doug Hoffman wrote:

>> I created a ll of 50,000 random integers. (Albert's)

>> code sorted that in 0.016 seconds on my rather
>> slow machine.

> 16 milliseconds to sort 50,000 elements is very fast!

> All in all, I think that your 16 millisecond time is not true.

16 milliseconds is correct.

You have had plenty of time to test Albert's algorithm against your
own merge-sort. How did they compare?

-Doug

[hughag...@gmail.com]

This is what I said:

On Wednesday, December 5, 2018 at 1:17:58 PM UTC-7, hughag...@gmail.com wrote:
> Keep trying!
> When you get some working code that roughly corresponds to my MergeSort,
> I will compare it for speed.

I have yet to see code that roughly corresponds to my MergeSort:
1.) Written in ANS-Forth.
2.) A general-purpose linked-list that works with any data type for the struct.

[Albert van der Horst]

In article <05ab7f7b-c248-4a33...@googlegroups.com>,

My MERGE-SORT fits that bill. We already know that you're not keen on testing.
You're scared that your results are no what you claim. Or maybe you just
don't know how to test.

16 ms for 50,000 items is not unrealistic. Worst case is sublists of size one.
This translates in this case to 16*50k = 800K operations.
There are 16 M instructions in 16 mS.
16 is the 2-logarithm of 50K .

Now analyse your merge and gives us the results.
Dough cheated a bit by inlining the execution tokens. You're allowed to
do the same.

Groetjes Albert

[Doug Hoffman]

On 1/6/19 8:40 AM, Albert van der Horst wrote:
> In article <05ab7f7b-c248-4a33...@googlegroups.com>,
> <hughag...@gmail.com> wrote:

>> I have yet to see code that roughly corresponds to my MergeSort:
>> 1.) Written in ANS-Forth.
>> 2.) A general-purpose linked-list that works with any data type for the struct.

> My MERGE-SORT fits that bill.

Yes it does. I have used it for a variety of data types and see no
limitations.

> Dough cheated a bit by inlining the execution tokens.

Actually I kept the compare xt:

VARIABLE *<M : LL< 2DUP *<M @ EXECUTE ;

-Doug

[hughag...@gmail.com]

On Sunday, January 6, 2019 at 8:30:22 AM UTC-7, Doug Hoffman wrote:
> On 1/6/19 8:40 AM, Albert van der Horst wrote:
> > In article <05ab7f7b-c248-4a33...@googlegroups.com>,
> > <hughag...@gmail.com> wrote:
>
> >> I have yet to see code that roughly corresponds to my MergeSort:
> >> 1.) Written in ANS-Forth.
> >> 2.) A general-purpose linked-list that works with any data type for the struct.
>
> > My MERGE-SORT fits that bill.
>
> Yes it does. I have used it for a variety of data types and see no
> limitations.

Note that #2 above says: "linked-list."
Your code was using an array, which you weirdly described as a "list."

Also, the node in the list needs to be able to contain any data type,
which means the node can be any size.
You can't have the limitation in which the node is cell-sized.

I know that it is possible to put a pointer in the cell to a struct in the heap.
(this is despite Alex McDonald and Julien Fondren saying that I don't know this)
Being limited to a cell-sized node is still a limitation though.
The programmer would normally want the struct in the node.

This is how OOP works.
The programmer defines a struct that has LIST as its parent,
so the new struct works with all of the LIST code including SORT-LIST.

For example:
----------------------------------------------------------------------------
list
w field .line
constant seq

: init-seq ( str node -- node )
init-list >r
hstr r@ .line !
r> ;

: new-seq ( str -- node )
seq alloc
init-seq ;

: <kill-seq> ( node -- )
dup .line @ dealloc
dealloc ;

: kill-seq ( head -- )
each[ <kill-seq> ]each ;

: <clone-seq> ( node -- new-node )
clone-node
dup .line @ hstr over .line ! ;

: clone-seq ( head -- new-head )
nil
swap each[ <clone-seq> link ]each ;

: concrete-str ( str -- new-str )
here swap count ,str ;

: <concrete-seq> ( node -- new-node )
concrete-node
dup .line @ concrete-str
over .line ! ;

: concrete-seq ( head -- new-head )
nil
swap each[ <concrete-seq> link ]each ;

: <read-seq> ( adr cnt -- head )
r/o <open-file> >r \ r: -- file-id
<cstr nil begin \ -- head
cstr 1+ cstr-size 1- r@ read-line abort" *** READ-SEQ failed to read line ***"
while \ -- head cnt
cstr c! \ -- head
cstr new-seq \ -- head node
link repeat drop \ -- head
r> <close-file>
cstr> drop ;

: read-seq ( name -- head )
count <read-seq> ;

: <write-seq> ( head adr cnt -- )
w/o <create-file> swap \ -- file-id head
each[ .line @ count rover write-line abort" *** <WRITE-SEQ> failed to write ***" ]each
<close-file> ;

: write-seq ( head name -- )
count <write-seq> ;

: <sort-seq> ( new-node node -- new-node flag )
.line @ count rover .line @ count compare A>B = ;

: sort-seq ( head -- new-head )
['] <sort-seq> sort-list ;
----------------------------------------------------------------------------

Notice that SORT-SEQ uses SORT-LIST that is part of the LIST class.
This works because SEQ is a child of LIST.

It is possible to define another class that is a child of SEQ.
This class will use SORT-SEQ because it inherits all of the parent functions.

Note that CLONE-NODE only works because I have ALLOCATED so it can determine
the size of the allocated block.
I originally called this SIZE but changed the name to ALLOCATED later.
Humorously, this is currently being discussed here:
https://groups.google.com/forum/#!topic/comp.lang.forth/Z-2BMo5Shx0

Before the ANS-Forth cult begins criticizing my SEQ as excessively limited,
let me say that the code I showed above is only a partial code-snippet.
I actually have a lot more code that works with SEQs.
My new novice-package is significantly larger than what I had in 2010.
I'm not really planning on releasing it publicly.
Everybody on comp.lang.forth has already said that they hate it,
so there is no need for me to provide the source-code for the same result.

[Paul Rubin]

alb...@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes:
> 16 ms for 50,000 items is not unrealistic. Worst case is sublists of
> size one. This translates in this case to 16*50k = 800K operations.
> There are 16 M instructions in 16 mS. 16 is the 2-logarithm of 50K .

It seems pretty good. I did a dumb implementation in Common Lisp and it
took 24ms to sort a 50k-element random list on an i5-3570S with SBCL,
which is a pretty smart compiler. On the other hand it took 386ms to do
1 million elements. So maybe there is some additive overhead someplace.
On i7-3770 50k elements took 14ms but 1M elements still took around
385ms, so maybe that is memory access bound.

[Doug Hoffman]

On 1/6/19 7:14 PM, hughag...@gmail.com wrote:

*** irrelevant text snipped ***

I can only conclude that Hugh's mergesort is much slower than
Albert's because rather than show comparison results he chooses to
deflect with unrelated and incorrect commentary.

[minf...@arcor.de]

There are memory- and CPU-cache-aware variants with better results, e.g.
http://web.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-00-6.pdf

[Anton Ertl]

These CPUs should have hardly any difference for the 50k case: The
cores are the same, the clock rates are almost the same (3.8GHz
vs. 3.9GHz Turbo, and they should run at Turbo for a single-threaded
program on an otherwise idle system), and the L3 cache size difference
(6MB vs. 8MB) should not play a role for 50k elements. I also would
not expect much difference between the CPUs for the 1M results,
despite the L3 cache size.

Apart from that, for some further perspective, integer (cell) array
quicksort on a 3GHz Core 2 Duo E8400 takes 31ms (gforth-fast) or 9.8ms
(vfxlin) for a 100k-element array and 361ms (gforth-fast) or 114ms
(vfxlin) for a 1M-element array
<2013Aug1...@mips.complang.tuwien.ac.at>.

- 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 2018: http://www.euroforth.org/ef18/

[Albert van der Horst]

In article <a210de6f-4027-49f0...@googlegroups.com>,

That document is not even applicable. It only considers 2, 4 and 8 byte
elements, not variable size elements with link fields.

[hughag...@gmail.com]

On Sunday, January 6, 2019 at 8:30:22 AM UTC-7, Doug Hoffman wrote:
> On 1/6/19 8:40 AM, Albert van der Horst wrote:

> > Doug cheated a bit by inlining the execution tokens.

>
> Actually I kept the compare xt:
> VARIABLE *<M : LL< 2DUP *<M @ EXECUTE ;
>
> -Doug

You are passing data between functions in global variables?
That is typical ANS-Forth cult programming!

Anyway, I have yet to see any code.

[Paul Rubin]

an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> These CPUs should have hardly any difference for the 50k case: The
> cores are the same, the clock rates are almost the same (3.8GHz
> vs. 3.9GHz Turbo

The i5-3570S is apparently a little slower (3.10 ghz) than the 3570
non-S. The i7 is running at 3.40 ghz. I do notice a speed difference
vs the i7 for other programs but it should only be 10% or so.

Maybe also relevant: I didn't notice this earlier but the i5 is running
a newer version of sbcl (1.3.14) than the i7 (1.0.57.0).

[Anton Ertl]

Paul Rubin <no.e...@nospam.invalid> writes:
>an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>> These CPUs should have hardly any difference for the 50k case: The
>> cores are the same, the clock rates are almost the same (3.8GHz
>> vs. 3.9GHz Turbo
>
>The i5-3570S is apparently a little slower (3.10 ghz) than the 3570
>non-S. The i7 is running at 3.40 ghz. I do notice a speed difference
>vs the i7 for other programs but it should only be 10% or so.

My experience with Intel CPUs is that, as long as the power and
temperature target is not reached, they increase the clock rate to the
Turbo speed (3.8 and 3.9GHz respectively). A single-threaded load
like this is unlikely to reach one of these limits. On Intel CPUs
you can observe it with

grep MHz /proc/cpuinfo

during the run, or by using

perf stat <command>

On AMD CPUs the former variant does not report turbo clocks, so use
the latter one.

[Paul Rubin]

an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> My experience with Intel CPUs is that, as long as the power and
> temperature target is not reached, they increase the clock rate to the
> Turbo speed (3.8 and 3.9GHz respectively).

Hmm, you are right, the i5-3570S did get to 3.8 ghz on one core and 3.7
ghz on the rest, even though only one core was doing anything.
Interesting, thanks.

[hughag...@gmail.com]

On Monday, January 7, 2019 at 4:53:59 AM UTC-7, Doug Hoffman wrote:
> On 1/6/19 7:14 PM, hughag...@gmail.com wrote:
>
> *** irrelevant text snipped ***
>
> I can only conclude that Hugh's mergesort is much slower than
> Albert's because rather than show comparison results he chooses to
> deflect with unrelated and incorrect commentary.

I feel confident that my SORT-LIST will be faster than anything you have.
I have yet to see your ANS-Forth code.
All I've seen so far is your code that used an array rather than a list.

You also mentioned that you pass data between functions in global variables.
Presumably you do this because Elizabeth Rather says that she "hates" locals.
Also, locals are slow in SwiftForth because the local-frame pointer
is not held in a register, but rather is held in a user-variable.
Also, the initialization code for locals in SwiftForth is over-complicated.

Anyway, just to make sure my SORT-LIST is faster,
I upgraded it with a SORT-FOUR function instead using <SORT-LIST>
(note that <SORT-LIST> does an insertion sort.
I also fixed a bug I found that was screwing me up on lists shorter than
4 elements total.
This is the new code:
--------------------------------------------------------------------------
\ ******
\ ****** The following are for sorting lists.
\ ******

: reverse ( head -- new-head ) \ reverses the order of all the nodes
nil swap each[ init-list swap link ]each ;

\ comparer: i*x new-node node -- j*x new-node flag \ insert new-node prior to node?

: insert-ordered ( head 'comparer node -- new-head 'comparer )
init-list rover rover \ -- head 'comparer node head 'comparer
find-prior \ -- head 'comparer node -1|prior|false
dup 0= if drop rot swap link swap exit then \ append
dup -1 = if drop rot link swap exit then \ prepend
insert ;

: <sort-list> ( head 'comparer -- new-head )
nil swap rot each[ insert-ordered ]each drop ;

\ <SORT-LIST> used to be our SORT-LIST --- it is better than SORT-LIST for short lists up to a few hundred elements.
\ If the comparer provides a TRUE on node > new-node, then the list will be sorted in ascending order.
\ The following is a typical comparer function:
\ : int> ( new-node node -- new-node flag ) \ assumes that we are sorting on a W field called .N
\ .n @ over .n @ u> ;

\ <SORT-LIST> does an InsertionSort. SORT-LIST does a MergeSort which has fewer comparisons and hence is theoretically faster.

: merge-sorted-lists ( headA headB 'comparer -- head ) \ merge headA into headB
>r
nil >r begin \ -- headA headB
over 0= if nip r> swap link rdrop exit then \ if headA is done, append headB and exit
dup 0= if drop r> swap link rdrop exit then \ if headB is done, append headA and exit
2dup rr@ execute nip
if swap delink-one r> rot link >r swap \ headA < headB
else delink-one r> rot link >r then \ headA => headB
again ;

\ Instead of SORT-FOUR I had previously just used <SORT-LIST> for the small lists.
\ A small list of 4 elements is okay because SORT-FOUR can be used. SORT-FOUR is much faster than <SORT-LIST> is.
\ A larger small list will save memory, but a function like SORT-FOUR is unrealistic because it would be too big and complicated.
\ For a larger small list, <SORT-LIST> would need to be used. The larger that the small list is, the slower SORT-LIST is.
\ The following need to be LATE-MACRO: because they use 'COMPARE internally, which is a SORT-LIST local.

late-macro: node<? ( nodeA nodeB -- flag ) \ used by SORT-FOUR
'comparer execute \ -- A A<B?
nip ;

late-macro: node>? ( nodeA nodeB -- flag ) \ used by SORT-FOUR
'comparer execute 0= \ -- A A>B?
nip ;

char & comment

\ This version of SORT-FOUR works, and it does 3 to 6 comparisons (120 total given the 24 possible input lists).
\ It works out well when the data is mostly reverse-sorted initially.
\ A similar version could be made that worked out when the data is mostly forward-sorted initially.

late-macro: sort-four ( head -- new-head ) \ used by SORT-LIST \ assumes the list is exactly 4 nodes in length
delink-one delink-one delink-one \ -- D C B A
2dup node<? if swap then \ -- D C B A \ we know now that A < B
2swap \ -- B A D C
2dup node<? if swap then \ -- B A D C \ we know now that C < D
swap >r rot >r \ -- A C \ return: -- D B \ A and C are both small, so one of them must be 1st
dup r@ node>? if \ we know now that B < C
r> swap r> \ -- A B C D \ we are done
else \ -- A C \ return: -- D B \ we know now that C < B
2dup node<? if \ -- A C \ return: -- D B \ we know now that A < C
r> r> \ -- A C B D
2dup node>? if swap then \ -- A C D B \ either A C B D or A C D B is good
else \ -- A C \ return: -- D B \ we know now that C < A
swap r> \ -- C A B \ return: -- D
over r@ node<? if \ we know now that A < D
r> \ -- C A B D
2dup node>? if swap then \ -- C A D B \ either C A B D or C A D B is good
else \ -- C A B \ return: -- D \ we know now that D < A
r> -rot \ -- C D A B
then
then
then
link link link ;

&

\ This version of SORT-FOUR works, and it does 4 to 5 comparisons (112 total given the 24 possible input lists).
\ It works out well when the data is randomly sorted initially.

late-macro: sort-four ( head -- new-head ) \ used by SORT-LIST \ assumes the list is exactly 4 nodes in length
delink-one delink-one delink-one \ -- D C B A
2dup node<? if swap then \ -- D C B A \ we know now that A < B
2swap \ -- B A D C
2dup node<? if swap then \ -- B A D C \ we know now that C < D
swap >r rot >r \ -- A C \ return: -- D B \ A and C are both small, so one of them must be 1st
2dup node<? if \ A is 1st
r> \ -- A C B \ return: -- D
2dup node<? if \ C is 2nd
r> \ -- A C B D
2dup node>? if swap then \ -- 1st 2nd 3rd 4th
else \ B is 2nd
swap r> \ -- A B C D \ we already know C < D
then
else \ C is 1st
swap \ -- C A \ return: -- D B
r> r> \ -- C A B D \ B and D are both big, so one of them must be 4th
2dup node>? if \ B is 4th else D is 4th and we are done
swap >r \ -- C A D \ return: -- B
2dup node>? if swap then \ -- C 2nd 3rd \ return: -- B
r> \ -- 1st 2nd 3rd 4th
then
then
link link link ;

: sort-list { head 'comparer | partial-size -- new-head } \ iterative; with SORT-FOUR used on lists of size 4
head 0= if head exit then
0 \ -- 0 \ sentinel
head length 3 and to partial-size \ the partial list needs <SORT-LIST> rather than SORT-FOUR
head \ -- 0 head
partial-size case \ PARTIAL-SIZE is in [0,3]
1 of delink-one swap 'comparer <sort-list> swap endof
2 of delink-two swap 'comparer <sort-list> swap endof
3 of delink-three swap 'comparer <sort-list> swap endof
endcase \ -- 0 head rest \ the HEAD chunk is the sorted partial list
begin dup while \ while the list on top is not empty
delink-four
swap sort-four swap \ -- 0 head chunk rest \ the CHUNK chunk is the sorted four-element list
repeat drop \ -- 0 chunks... \ drop the REST chunk which is NIL now
begin over while \ assumes at least one chunk
0 >r \ sentinel
begin ?dup while
over if 'comparer merge-sorted-lists then
>r repeat \ --
0 \ sentinel
begin r> ?dup while
r@ if r> 'comparer merge-sorted-lists then
repeat \ -- 0 chunks...
repeat \ -- 0 head
nip ; \ -- head

\ According to my tests, SORT-LIST is slightly better than <SORT-LIST> for big lists.
\ If you have a lot of short lists to sort, then <SORT-LIST> may be better because SORT-LIST has a lot of overhead.
\ Setting the SHORT-LIST value to a small number boosts the speed, but increases the memory usage. <SORT-LIST> has no memory usage at all.

\ char & comment \ test code for SORT-LIST

list
w field .num
constant num

: init-num ( n node -- node )
init-list >r
r@ .num !
r> ;

: new-num ( n -- node )
num alloc
init-num ;

: >>num ( head n -- new-head )
new-num link ;

: kill-num ( head -- )
each[ dealloc ]each ;

: show-num ( head -- )
each[ .num @ 7 .r ]each ;

: num> ( new-node node -- new-node flag )
.num @ over .num @ > ;

: sort-num ( head -- new-head )
['] num> sort-list ;

: num-sorted? { head | bad? -- good? } \ assumes NUM list filled with non-negative numbers
-1
head each[ .num @ tuck > if true to bad? then ]each
drop
bad? 0= ;

: test-sort-num-four ( -- )
nil 1 >>num 2 >>num 3 >>num 4 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 1 >>num 2 >>num 4 >>num 3 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 1 >>num 3 >>num 2 >>num 4 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 1 >>num 3 >>num 4 >>num 2 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 1 >>num 4 >>num 2 >>num 3 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 1 >>num 4 >>num 3 >>num 2 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 2 >>num 1 >>num 3 >>num 4 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 2 >>num 1 >>num 4 >>num 3 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 2 >>num 3 >>num 1 >>num 4 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 2 >>num 3 >>num 4 >>num 1 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 2 >>num 4 >>num 1 >>num 3 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 2 >>num 4 >>num 3 >>num 1 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 3 >>num 1 >>num 2 >>num 4 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 3 >>num 1 >>num 4 >>num 2 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 3 >>num 2 >>num 1 >>num 4 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 3 >>num 2 >>num 4 >>num 1 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 3 >>num 4 >>num 1 >>num 2 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 3 >>num 4 >>num 2 >>num 1 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 4 >>num 1 >>num 2 >>num 3 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 4 >>num 1 >>num 3 >>num 2 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 4 >>num 2 >>num 1 >>num 3 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 4 >>num 2 >>num 3 >>num 1 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 4 >>num 3 >>num 1 >>num 2 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 4 >>num 3 >>num 2 >>num 1 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
;

&

--------------------------------------------------------------------------

[Ron Aaron]

On 11/01/2019 6:59, hughag...@gmail.com wrote:
> On Monday, January 7, 2019 at 4:53:59 AM UTC-7, Doug Hoffman wrote:
>> On 1/6/19 7:14 PM, hughag...@gmail.com wrote:
>>
>> *** irrelevant text snipped ***
>>
>> I can only conclude that Hugh's mergesort is much slower than
>> Albert's because rather than show comparison results he chooses to
>> deflect with unrelated and incorrect commentary.
>
> I feel confident that my SORT-LIST will be faster than anything you have.

On what basis do you feel confident? Did you measure the speed of yours
vs (any other) version?

[Albert van der Horst]

In article <a5707c8e-50d0-47f9...@googlegroups.com>,

<SNIP>

<SNIP>

> nil 4 >>num 2 >>num 1 >>num 3 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
> nil 4 >>num 2 >>num 3 >>num 1 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
> nil 4 >>num 3 >>num 1 >>num 2 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
> nil 4 >>num 3 >>num 2 >>num 1 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
> ;
>
>&
>
>--------------------------------------------------------------------------

What is the purpose of publishing this code?
Do you hope that someone else will benchmark this to compare it
to other sorts?
And then you deny the correctness, because the results don't please you?

[Doug Hoffman]

On 1/11/19 7:12 AM, Albert van der Horst wrote:

> What is the purpose of publishing this code?

I wondered the same. I cannot even load it. Did I miss something?

OTOH the complete source for your algorithm is shown earlier in
this thread. Anyone can run it. He complains about a global
variable, but this is trivial to remove (if desired) and barely
affects the sort speed (a few %). I've stopped wasting my time
with him.

Thanks for the nice sort code.

-Doug

[hughag...@gmail.com]

On Sunday, January 6, 2019 at 6:40:03 AM UTC-7, Albert van der Horst wrote:
> In article <05ab7f7b-c248-4a33...@googlegroups.com>,
> <hughag...@gmail.com> wrote:
> >I have yet to see code that roughly corresponds to my MergeSort:
> >1.) Written in ANS-Forth.
> >2.) A general-purpose linked-list that works with any data type for the struct.
>
> My MERGE-SORT fits that bill. We already know that you're not keen on testing.
> You're scared that your results are no what you claim. Or maybe you just
> don't know how to test.

I have yet to see your MERGE-SORT written in ANS-Forth
or written to be general-purpose.

Doug Hoffman's code actually used an array rather than a list.

On Thursday, December 6, 2018 at 4:36:02 AM UTC-7, Doug Hoffman wrote:
> Arrays are certainly used as lists.

When I see some code that fits the bill, I will compare it to my code.

[hughag...@gmail.com]

I have SORT-FOUR that Albert's "canonical" version lacks.

I looked at a C version of SORT-FOUR on the internet.
It does 120 comparisons for the 24 possible permutations.
My version does 112 comparisons.

I also have a version that does 120 comparisons and would work out well
when the data is mostly reverse-sorted already.
The C version would work out well if the data is mostly forward-sorted already.
I commented out my 120-comparison version and went with the
112-comparison version that is faster when the data is randomly sorted.

Realistically, Albert van der Horst and Doug Hoffman aren't capable of
writing code like this.
Albert van der Horst has a history of faking code:
https://groups.google.com/forum/#!topic/comp.lang.forth/0iBCFp9l9IY%5B1-25%5D

On Monday, July 16, 2018 at 4:31:43 AM UTC-7, hughag...@gmail.com wrote:
> On Tuesday, July 3, 2018 at 2:14:22 AM UTC-7, Albert van der Horst wrote:
> > In article <0ff9666d-e22e-4370...@googlegroups.com>,
> > <hughag...@gmail.com> wrote:
> > >On Monday, July 2, 2018 at 3:54:28 AM UTC-7, Albert van der Horst wrote:
> > >>
> > >> \ You only need D- and D<=
> > >> : .cf2 BEGIN 100000 0 DO 2OVER D- 2DUP 0. D<= IF I . LEAVE THEN
> > >> LOOP 2DUP OR WHILE 2OVER D+
> > >> .S KEY DROP \ Can leave this out
> > >> 2SWAP REPEAT ;
> >
> > Make that correct by
> > 2SWAP REPEAT 1 . ;
> >
> > >> "
> > >>
> > >> 3.141592653589793238
> > >> 1.000000000000000000
> > >> 2DUP D. 2OVER D. KEY DROP .cf2
> > >
> > >You don't know what continued fractions are
> >
> > Said the cab-driver to the mathematician
> >
> > > --- your code is nonsense ---
> > It gives the same results as your code, except for the correction
> > I gave.
> >
> > > you posted this as a loyalty demonstration to Elizabeth Rather.
> > I must say, I feel a connection with ER, like we are in the
> > same camp or something.
> ...
> Your code doesn't work. It is nonsense. You posted it as a loyalty display for Elizabeth Rather and her nonsense about not needing D/ back in 2009.
> You are definitely in the same camp!

[hughag...@gmail.com]

On Saturday, January 12, 2019 at 3:11:42 PM UTC-7, hughag...@gmail.com wrote:
> On Thursday, January 10, 2019 at 10:38:04 PM UTC-7, Ron Aaron wrote:
> > On 11/01/2019 6:59, hughag...@gmail.com wrote:
> > > On Monday, January 7, 2019 at 4:53:59 AM UTC-7, Doug Hoffman wrote:
> > >> On 1/6/19 7:14 PM, hughag...@gmail.com wrote:
> > >>
> > >> *** irrelevant text snipped ***
> > >>
> > >> I can only conclude that Hugh's mergesort is much slower than
> > >> Albert's because rather than show comparison results he chooses to
> > >> deflect with unrelated and incorrect commentary.
> > >
> > > I feel confident that my SORT-LIST will be faster than anything you have.
> >
> > On what basis do you feel confident? Did you measure the speed of yours
> > vs (any other) version?
>
> I have SORT-FOUR that Albert's "canonical" version lacks.
>
> I looked at a C version of SORT-FOUR on the internet.
> It does 120 comparisons for the 24 possible permutations.
> My version does 112 comparisons.
>
> I also have a version that does 120 comparisons and would work out well
> when the data is mostly reverse-sorted already.
> The C version would work out well if the data is mostly forward-sorted already.
> I commented out my 120-comparison version and went with the
> 112-comparison version that is faster when the data is randomly sorted.

This is the C version I looked at:
https://stackoverflow.com/questions/2748749/fast-algorithm-implementation-to-sort-very-small-list/2748832#2748832

I was not impressed. My SORT-FOUR does fewer comparisons.

This is the C code:
-----------------------------------------------------------------------------
function sort(i,j,k,l) {
if (i < j) {
if (j < k) {
if (k < l) return [i,j,k,l];
if (j < l) return [i,j,l,k];
if (i < l) return [i,l,j,k];
return [l,i,j,k];
} else if (i < k) {
if (j < l) return [i,k,j,l];
if (k < l) return [i,k,l,j];
if (i < l) return [i,l,k,j];
return [l,i,k,j];
} else {
if (j < l) return [k,i,j,l];
if (i < l) return [k,i,l,j];
if (k < l) return [k,l,i,j];
return [l,k,i,j];
}
} else {
if (i < k) {
if (k < l) return [j,i,k,l];
if (i < l) return [j,i,l,k];
if (j < l) return [j,l,i,k];
return [l,j,i,k];
} else if (j < k) {
if (i < l) return [j,k,i,l];
if (k < l) return [j,k,l,i];
if (j < l) return [j,l,k,i];
return [l,j,k,i];
} else {
if (i < l) return [k,j,i,l];
if (j < l) return [k,j,l,i];
if (k < l) return [k,l,j,i];
return [l,k,j,i];
}
}
}
-----------------------------------------------------------------------------

[Ron Aaron]

On 13/01/2019 0:11, hughag...@gmail.com wrote:
> On Thursday, January 10, 2019 at 10:38:04 PM UTC-7, Ron Aaron wrote:
>> On 11/01/2019 6:59, hughag...@gmail.com wrote:
>>> On Monday, January 7, 2019 at 4:53:59 AM UTC-7, Doug Hoffman wrote:
>>>> On 1/6/19 7:14 PM, hughag...@gmail.com wrote:
>>>>
>>>> *** irrelevant text snipped ***
>>>>
>>>> I can only conclude that Hugh's mergesort is much slower than
>>>> Albert's because rather than show comparison results he chooses to
>>>> deflect with unrelated and incorrect commentary.
>>>
>>> I feel confident that my SORT-LIST will be faster than anything you have.
>>
>> On what basis do you feel confident? Did you measure the speed of yours
>> vs (any other) version?
>
> I have SORT-FOUR that Albert's "canonical" version lacks.
>
> I looked at a C version of SORT-FOUR on the internet.
> It does 120 comparisons for the 24 possible permutations.
> My version does 112 comparisons.

...

So to answer my question: no, you didn't actually measure the speed vs
other implementations.

To be clear, by "measure the speed" I mean to measure the elapsed time
for sorting various kinds of data, using your routine vs. other
implementations. I don't mean looking at the algorithm "on paper".

If you don't measure, you're only guessing. I've found that guessing
leads to incorrect conclusions very often. I recently changed the sort
routine in 8th from a good 'quicksort' implementation to a generally
much better 'timsort'. The algorithm is more complex, but the result is
considerably better. Measurably so.

[hughag...@gmail.com]

On Friday, January 11, 2019 at 5:12:29 AM UTC-7, Albert van der Horst wrote:
> What is the purpose of publishing this code?
> Do you hope that someone else will benchmark this to compare it
> to other sorts?
> And then you deny the correctness, because the results don't please you?

You insulted the entire world by using the word "canonical" to describe
your code, implying that your code is a gift from God.
Whenever the ANS-Forth cult puffs up their hollow chests with arrogance,
I make it my business to deflate them.

I upgraded my code to make it faster. These are the results of several runs:

50000 element liked-list was initially sorted:
randomly forward reverse
15ms 16ms 31ms
16ms 31ms 16ms
31ms 15ms 32ms
31ms 16ms 15ms
15ms 16ms 31ms
32ms 15ms 16ms
16ms 15ms 16ms
15ms 32ms 15ms

This is just my laptop running Windows.
I have no idea how this compares to Doug Hoffman's computer in speed.

On Monday, December 17, 2018 at 4:11:15 AM UTC-7, Doug Hoffman wrote:

> I created a ll of 50,000 random integers. Your

> code sorted that in 0.016 seconds on my rather

> slow machine. Impressive! Nice work.
>
> Yes, I think your mergesort could (should) be part
> of anyone's library.

I think that Doug Hoffman's claim of 16ms is not true.
This is a typical example of one ANS-Forth cult member supporting another.
There is a lot of variance in the time required from one run to the next.
The fact that he provided only one number, 16ms, indicates to me that
he cherry-picked your best result pretending that it is an average result.
He may have totally fabricated the 16ms result. There is no source-code!

I am presumably doing fewer comparisons because I have SORT-FOUR.
The comparison is so fast (comparing an integer) that the number of
comparisons has less of an effect than it would in a real-life application
that would presumably have a more complicated comparison.

You refuse to provide source-code in ANS-Forth for a function to sort
a general-purpose linked-list. Yet you want your code to be in a library!
This refusal implies that the 16ms result was not true.
You are afraid to benchmark your "canonical" code against mine.

I don't think the ANS-Forth cult should ever be allowed to succeed at anything!
In order for Forth to succeed, the ANS-Forth cult must first be discredited.
ANS-Forth is the reason why Forth lost popularity in the real world.

The following is my code.
This is not "canonical" of course --- it can be improved yet more.

--------------------------------------------------------------------------

\ ******
\ ****** The following are for sorting lists.
\ ******

\ char & comment \ test code for SORT-LIST

list
w field .num
constant num

: init-num ( n node -- node )
init-list >r
r@ .num !
r> ;

: new-num ( n -- node )
num alloc
init-num ;

: >>num ( head n -- new-head )
new-num link ;

: <rnd-num> ( how-many range seed -- head ) \ SEED can be any nonzero number
seed !
locals| range |
nil swap 0 ?do
range rnd >>num loop ;

: rnd-num ( how-many -- head )
1000000 1 <rnd-num> ;

: kill-num ( head -- )
each[ dealloc ]each ;

: show-num ( head -- )
each[ .num @ 7 .r ]each ;

&

macro: one-link ( 1stHead 2ndHead -- NewHead ) \ like LINK except requires that the 1stHead list has exactly 1 node
over .fore ! ;

\ The 1stHead doesn't need INIT-LIST done to it. If it has garbage in the .FORE field that will get over-written anyway.

macro: prepend-list ( head build -- new-head )
begin over while \ -- head build
over .fore @ -rot \ -- rest head build
one-link \ -- rest build
repeat nip ;

: reverse ( head -- new-head ) \ reverses the order of all the nodes

nil prepend-list ;

\ The hand-coded REVERSE is more efficient than the obvious way: nil swap each[ swap one-link ]each ;

macro: tail-reverse ( head -- new-tail new-head ) \ like REVERSE except also provides the tail node
dup \ -- tail head \ our current HEAD will be the TAIL afterward
nil prepend-list ; \ -- tail new-head

\ comparer: i*x new-node node -- j*x new-node flag \ insert new-node prior to node?

: insert-ordered ( head 'comparer node -- new-head 'comparer )
init-list rover rover \ -- head 'comparer node head 'comparer
find-prior \ -- head 'comparer node -1|prior|false
dup 0= if drop rot swap link swap exit then \ append

dup -1 = if drop rot one-link swap exit then \ prepend

insert ;

: <sort-list> ( head 'comparer -- new-head )
nil swap rot each[ insert-ordered ]each drop ;

\ <SORT-LIST> used to be our SORT-LIST --- INSERT-ORDERED is still a good choice if you need a list continuously sorted.

\ If the comparer provides a TRUE on node > new-node, then the list will be sorted in ascending order.
\ The following is a typical comparer function:
\ : int> ( new-node node -- new-node flag ) \ assumes that we are sorting on a W field called .N
\ .n @ over .n @ u> ;

\ <SORT-LIST> does an InsertionSort. SORT-LIST does a MergeSort which has fewer comparisons and hence is theoretically faster.

macro: <fast-delink> ( head last -- head rest ) \ requires that we have 1 or more nodes in the HEAD list
dup .fore @ \ -- head 2nd rest
nil rot .fore ! ;

macro: fast-delink-one ( head -- head rest ) \ requires that we have 1 or more nodes in the HEAD list
dup .fore @ \ -- head rest
nil rover .fore ! ;

macro: fast-delink-two ( head -- head rest ) \ requires that we have 2 or more nodes in the HEAD list
dup .fore @ \ -- head 2nd
<fast-delink> ;

macro: fast-delink-three ( head -- head rest ) \ requires that we have 3 or more nodes in the HEAD list
dup .fore @ .fore @ \ -- head 3rd
<fast-delink> ;

macro: fast-delink-four ( head -- head rest ) \ requires that we have 4 or more nodes in the HEAD list
dup .fore @ .fore @ .fore @ \ -- head 4th
<fast-delink> ;

macro: append-list ( tail head build -- build ) \ the TAIL is of the BUILD list
-rot \ -- build tail head
swap .fore ! ; \ -- build \ append HEAD to TAIL

\ APPEND-LIST will never have a BUILD being NIL because at least one node will already have been appended.

: merge-sorted-lists ( headA headB 'comparer -- head )

>r nil >r \ -- headA headB \ return: -- 'comparer build
begin \ -- tail A B \ the TAIL node is not there until the second pass
over 0= if nip r> append-list rdrop exit then \ if A is done, append B and exit (won't happen first pass)
dup 0= if drop r> append-list rdrop exit then \ if B is done, append A and exit (won't happen first pass)
1 comparisons +!
2dup rr@ execute nip \ -- A B A<B?
if swap then \ -- big sml \ we need to append the small node
r@ if \ -- tail big sml \ we have a TAIL from last time we appended
swap >r dup >r \ -- tail sml \ return: -- 'comparer build big sml
fast-delink-one -rot \ -- rest tail sml \ delink head node from rest of list
swap .fore ! \ -- rest \ append SML to TAIL
r> swap r> \ -- sml rest big \ SML is our new TAIL, REST is A and BIG is B
else \ -- big sml \ we don't have a TAIL yet because this is the first pass
tuck rdrop \ -- sml big sml \ return: -- 'comparer \ rdrop BUILD that was NIL
fast-delink-one swap >r \ -- sml big rest \ return: -- 'comparer build \ SML head is our new BUILD
then
again ;

\ There is no case in which MERGE-SORTED-LISTS is called with two either HEADA or HEADB being NIL nodes. We go through the loop at least once.
\ At least one list will have something at the start, so there is no case in which we return a NIL node.
\ The first time through the loop, there is no TAIL node on the data-stack. After that, we have a TAIL node which is the last node we appended.
\ By the time APPEND-LIST executes we are guaranteed to have a TAIL node because we have been through the loop at least once.

\ Instead of SORT-FOUR I had previously just used <SORT-LIST> for the small-lists.
\ A small-list of 4 elements is okay because SORT-FOUR can be used. SORT-FOUR is much faster than <SORT-LIST> is.
\ A larger small-list will save memory, but a function like SORT-FOUR is unrealistic because it would be too big and complicated.
\ For a larger small-list, <SORT-LIST> would need to be used. The larger that the small-list is, the slower SORT-LIST is.

\ The following need to be LATE-MACRO: because they use 'COMPARE internally, which is a SORT-LIST local.

late-macro: node<? ( nodeA nodeB -- flag ) \ used by SORT-FOUR etc.
1 comparisons +!

'comparer execute \ -- A A<B?
nip ;

late-macro: node>? ( nodeA nodeB -- flag ) \ used by SORT-FOUR etc.
1 comparisons +!

'comparer execute 0= \ -- A A>B?
nip ;

late-macro: sort-two ( head -- new-head ) \ used by SORT-LIST \ assumes the list is exactly 2 nodes in length
fast-delink-one \ -- B A
2dup node>? if swap then \ -- A B \ we know now that A < B
one-link ;

late-macro: sort-three ( head -- new-head ) \ used by SORT-LIST \ assumes the list is exactly 3 nodes in length
fast-delink-one fast-delink-one \ -- C B A
>r \ -- C B \ return: -- A
2dup node>? if swap then \ -- B C \ return: -- A \ we know now that B < C
dup r@ node<? if \ we know now that C < A
r> \ -- B C A
else \ we know now that A < C
over r@ node<? if \ -- B C \ return: -- A \ we know now that B < A
r> swap \ -- B A C
else \ we know now that A < B
r> -rot \ -- A B C \ we already know that B < C
then
then
one-link one-link ;

late-macro: sort-four ( head -- new-head ) \ used by SORT-LIST \ assumes the list is exactly 4 nodes in length

fast-delink-one fast-delink-one fast-delink-one \ -- D C B A

2dup node<? if swap then \ -- D C B A \ we know now that A < B
2swap \ -- B A D C
2dup node<? if swap then \ -- B A D C \ we know now that C < D
swap >r rot >r \ -- A C \ return: -- D B \ A and C are both small, so one of them must be 1st

2dup node<? if \ A < C so A is 1st

r> \ -- A C B \ return: -- D

2dup node<? if \ C < B so C is 2nd

r> \ -- A C B D

2dup node>? if swap then \ -- 1st 2nd 3rd 4th \ B or D the greater becomes 3rd
else \ B < C so B is 2nd

swap r> \ -- A B C D \ we already know C < D
then

else \ C < A so C is 1st

swap \ -- C A \ return: -- D B
r> r> \ -- C A B D \ B and D are both big, so one of them must be 4th

2dup node>? if \ B > D so B is 4th (else D is 4th and we are done)

swap >r \ -- C A D \ return: -- B

2dup node>? if swap then \ -- C 2nd 3rd \ return: -- B \ A or D the greater becomes 3rd

r> \ -- 1st 2nd 3rd 4th
then
then

one-link one-link one-link ;

\ SORT-FOUR does 112 comparisons for the 24 possibilities.
\ I also have a version that does 120 comparisons but is faster for data that is mostly presorted.

macro: sort-small-list ( 0 sorted-list rest -- 0 new-sorted-list new-rest ) \ REST is not NIL \ NEW-REST may be NIL if we are done
fast-delink-four swap sort-four swap ; \ delink a four-list and sort it \ the top list is unsorted and possibly NIL

: sort-list { head 'comparer -- new-head } \ iterative; with SORT-FOUR used on lists of size 4

head 0= if head exit then
0 \ -- 0 \ sentinel

head dup length 3 and \ -- 0 head partial-size \ the partial list is [0,3] in length
case \ special-case the partial list because SORT-FOUR won't work
1 of fast-delink-one endof
2 of fast-delink-two swap sort-two swap endof
3 of fast-delink-three swap sort-three swap endof
endcase \ -- 0 sorted-list rest \ REST may be NIL if the length is [0,3]
begin dup while \ the top list length is a multiple of 4 and any list underneath is sorted
sort-small-list \ sort the next one
dup if sort-small-list >r 'comparer merge-sorted-lists r> \ sort and merge the next one for a list of length 8
dup if sort-small-list >r 'comparer merge-sorted-lists r> then \ sort and merge the next one for a list of length 12
then
repeat drop \ -- 0 sorted-lists... \ drop the top list which is NIL now
begin over while \ assumes at least one sorted-list
0 >r \ sentinel
begin dup while

over if 'comparer merge-sorted-lists then
>r

dup if over if \ this helps to reduce memory usage
'comparer merge-sorted-lists r> 'comparer merge-sorted-lists >r then then
repeat drop \ --
0 \ sentinel
begin r> dup while

r@ if r> 'comparer merge-sorted-lists then

repeat drop

repeat \ -- 0 head
nip ; \ -- head

\ The first loop in SORT-LIST previously just did SORT-SMALL-LIST and that was it, so all the sorted lists were length 4.
\ Now we do one, two or three small lists, for a list of 4, 8 or 12 (most will be 12, but at the end you may get a list of 4 or 8).
\ The advantage is that fewer elements go onto the data stack, so there should be less data-cache thrashing.
\ Also, there is less chance of data-stack or return-stack overflow when sorting a gigantic list.
\ The disadvantage is that we are merging lists of length 8 and 4 which is less efficient than merging same-size lists.
\ When we get into the second loop, all of the lists are length 12 (except possibly the last of length 4 or 8).
\ So, in the second loop we are merging same-size lists, and the second loop is the most time-consuming so this is where efficiency matters.
\ The first loop in the second loop (data-stack to return-stack) also does four lists rather than two lists to reduce memory usage.

\ char & comment \ test code for SORT-LIST

: num> ( new-node node -- new-node flag )

.num @ over .num @ u> ;

: sort-num ( head -- new-head )
['] num> sort-list ;

: slow-sort-num ( head -- new-head )

['] num> <sort-list> ;

: num-sorted? { head | bad? -- good? } \ assumes NUM list filled with non-negative numbers
-1
head each[ .num @ tuck > if true to bad? then ]each
drop
bad? 0= ;

: test-sort-num-four ( -- )
nil 1 >>num 2 >>num 3 >>num 4 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num

nil 1 >>num 2 >>num 4 >>num 3 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 1 >>num 3 >>num 2 >>num 4 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 1 >>num 3 >>num 4 >>num 2 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 1 >>num 4 >>num 2 >>num 3 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 1 >>num 4 >>num 3 >>num 2 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 2 >>num 1 >>num 3 >>num 4 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 2 >>num 1 >>num 4 >>num 3 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 2 >>num 3 >>num 1 >>num 4 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 2 >>num 3 >>num 4 >>num 1 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 2 >>num 4 >>num 1 >>num 3 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 2 >>num 4 >>num 3 >>num 1 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 3 >>num 1 >>num 2 >>num 4 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 3 >>num 1 >>num 4 >>num 2 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 3 >>num 2 >>num 1 >>num 4 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num

nil 3 >>num 2 >>num 4 >>num 1 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 3 >>num 4 >>num 1 >>num 2 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 3 >>num 4 >>num 2 >>num 1 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 4 >>num 1 >>num 2 >>num 3 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 4 >>num 1 >>num 3 >>num 2 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num

nil 4 >>num 2 >>num 1 >>num 3 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 4 >>num 2 >>num 3 >>num 1 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 4 >>num 3 >>num 1 >>num 2 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
nil 4 >>num 3 >>num 2 >>num 1 >>num cr dup show-num ." >>> " sort-num dup show-num kill-num
;

&

VFX? [if]

: check-result ( head -- head )
cr dup num-sorted? if ." sort good" else ." sort bad" then
." comparisons done: " comparisons @ .
comparisons off ;

: <time-sort-num> ( list-size 'sort -- )
>r
0 comparisons !
ticks swap rnd-num ticks rot - cr ." MS to generate list: " .
comparisons off
ticks swap r@ execute ticks rot - cr ." MS to sort random: " .
check-result
ticks swap r@ execute ticks rot - cr ." MS to sort forward-sorted: " .
check-result
reverse
ticks swap r@ execute ticks rot - cr ." MS to sort reverse-sorted: " .
check-result
kill-num rdrop ;

: time-sort-num ( list-size -- )
['] sort-num <time-sort-num> ;

: time-slow-sort-num ( list-size -- )
['] slow-sort-num <time-sort-num> ;

[then]

--------------------------------------------------------------------------

[Cecil - k5nwa]

It is interesting to note that many that say that your code is crap do
not post their own code to demonstrate their "much better" code. As they
say talk is cheap.

--

Cecil - k5nwa

[Alex McDonald]

On 17-Jan-19 16:05, Cecil - k5nwa wrote:

>
> It is interesting to note that many that say that your code is crap do

Can you point out a post where someone other than Hugh describes his
code as crap?

> not post their own code to demonstrate their "much better" code. As they
> say talk is cheap.
>

Posting code snippets here is not a sign of competence or advanced
intelligence. I have posted a lot of code, but on github, because I'd
like it to be complete and be runnable. You?

--
Alex

[hughag...@gmail.com]

On Thursday, January 17, 2019 at 9:05:32 AM UTC-7, Cecil - k5nwa wrote:
> It is interesting to note that many that say that your code is crap do
> not post their own code to demonstrate their "much better" code. As they
> say talk is cheap.

I don't actually care about sort algorithms.
Worrying about sort algorithms is done by people who have never written
an application program. It is an educational exercise.
Writing a sort function is a step up from a "Hello World" program.

I originally put MergeSort in the novice package because Alex McDonald
was attacking me for having only InsertionSort (lists) and HeapSort (arrays).
IIRC this was the thread that inspired me to implement MergeSort:
https://groups.google.com/forum/#!topic/comp.lang.forth/gGkYxHDqWzY%5B1-25%5D
Now I have upgraded it to be fast.

ANS-Forth is a purely negative contribution to Forth.
The only way that Forth will succeed is for ANS-Forth to be discredited.
So long as Elizabeth Rather and her sycophants continue to claim
that ANS-Forth represents Forth, the Forth language
will continue to be smeared with their incompetence.

Every time that I write ANS-Forth code that works,
I hammer another nail into the coffin of ANS-Forth and Forth-200x.
Many many people have pointed out the problems with ANS-Forth.
The ANS-Forth cult responds by saying that the person is a C programmer
and doesn't know how to program in ANS-Forth, so the person's opinion
is worthless. Andrew Haley (Forth Inc. novice-class teacher) is fond of
telling critics that they don't understand the: "Forth Way."
I do know how to program in ANS-Forth though. I have code to prove it.
So, if I say that ANS-Forth has problems, that is because it does have problems.

When I implement general-purpose data-structures in ANS-Forth,
it becomes increasingly obvious that Elizabeth Rather the "leading expert"
of ANS-Forth and Stephen Pelc the Emperor of Forth-200x
have failed badly at providing general-purpose data-structures.
Anton Ertl and Bernd Paysan lied in their EuroForth paper when they
said that rquotations don't access the parent function's local variables
when the HOF has local variables of its own.

[dxf...@gmail.com]

On Friday, January 18, 2019 at 4:34:05 AM UTC+11, Alex McDonald wrote:
> On 17-Jan-19 16:05, Cecil - k5nwa wrote:
>
> >
> > It is interesting to note that many that say that your code is crap do
>
> Can you point out a post where someone other than Hugh describes his
> code as crap?

Not necessarily in those words. Hugh doesn't have a monopoly on criticism.

>
> > not post their own code to demonstrate their "much better" code. As they
> > say talk is cheap.
> >
>
> Posting code snippets here is not a sign of competence or advanced
> intelligence. I have posted a lot of code, but on github, because I'd
> like it to be complete and be runnable.

> ...

Do you have some links?

>
> --
> Alex

[hughag...@gmail.com]

On Saturday, January 19, 2019 at 6:57:21 PM UTC-7, dxf...@gmail.com wrote:
> On Friday, January 18, 2019 at 4:34:05 AM UTC+11, Alex McDonald wrote:
> > Can you point out a post where someone other than Hugh describes his
> > code as crap?
>
> Not necessarily in those words. Hugh doesn't have a monopoly on criticism.

There aren't any code-libraries for ANS-Forth
(except those of extremely low-quality, such as theforth.net and FFL),
because the criteria for getting the code in is brown-nosing.

Elizabeth Rather infamously said that she "hates locals."
She really demands that parameters be passed between functions
via global variables. Nobody will have their code accepted
by the ANS-Forth cult unless they do this.
This is why Doug Hoffman praised Albert van der Horst's MergeSort.

Elizabeth Rather said this:
----------------------------------------------------------------
Truly, I don't see the point of all this paranoia about reentrancy,
particularly in systems without a multitasker. VARIABLE was *designed*
for things that would be used in multiple definitions. I remember
the horror of (*gasp*) global variables back in the 1960's in Fortran.
But, frankly, in 30+ years of programming in Forth I never found them
a problem. I think this is all about mythical dragons.
----------------------------------------------------------------

Obviously, reentrancy is not just an issue within a multitasking system.
It is an issue because you may be holding data in a global variable
and call a sub-function that uses the same global variable.
Stephen Pelc got bit by this bug when he used the <# buffer in the
outer-interpreter to print the number of values on the data-stack,
but this corrupted data the user may have had in the <# buffer.
I fixed this bug in the novice-package, of course.

This failure to understand reentrancy is very dumb!
This is why ANS-Forth is not taken seriously in the real world.
ANS-Forth being the "Standard" discredits the entire Forth community.
Elizabeth Rather is personally responsible for killing Forth!

Now, in the 21st century, the ANS-Forth cult still struggles
with understanding reentrancy.
https://groups.google.com/forum/#!topic/comp.lang.forth/gGkYxHDqWzY%5B1-25%5D

On Sunday, June 30, 2013 at 12:59:38 PM UTC-7, Alex McDonald wrote:
> On Sunday, 30 June 2013 17:30:06 UTC+1, hughag...@yahoo.com wrote:
> > On Thursday, June 27, 2013 1:59:26 AM UTC-7, Alex McDonald wrote:
> >
> > > On Thursday, 27 June 2013 00:37:45 UTC+1, hughag...@yahoo.com wrote:
> >
> > > > It would be a lot better if the xt of the comparer function was passed
> > > > in as a parameter, and the size of the elements was also passed in as a
> > > > parameter. All of my code in the novice package is like this --- able to
> > > > work with any data type. After including the novice package,
> > > > it is possible to use SORT with multiple different data types,
> > > > without recompiling the novice package (actually, without even having
> > > > the source-code to the novice package).
> >
> > > PRECEDES is a DEFERed word. Perhaps you weren't aware of that.
> >
> > No, I wasn't aware of that.
> >
> > Anyway, as I said above, my novice package is reentrant
> > and doesn't use global variables.
>
> It suffers from requiring a contiguous array of fixed length records,
> *the elements of which it exchanges by swapping the entire element*.
> The exchange makes it non-reentrant, regardless of the use of locals.
>
> It's more efficient to sort fixed size pointers to the elements,
> which you could achieve with your sort implementation;
> but it's not clear from your code and comments that you understand that.

Alex McDonald clearly doesn't understand reentrancy.
This is why he qualifies in the ANS-Forth cult as a big expert!

He is promoting the use of deferred words for passing the xt of the
comparer function into the SORT, which is a global variable
Also, he says that my EXCHANGE is not reentrant. What???
Saying that my EXCHANGE is not reentrant is the same as saying that is crap.
Of course it is reentrant:
-------------------------------------------------------------------------
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 non-zero multiple of W
begin
-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
dup 0= until
3drop ;

[then]

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

He says that I don't know that it is possible to have an array of pointers
to structs. This is very novice-level programming though.
His accusation that I don't know this says more about his level of skill
than it says about my level of skill.
Apparently he thinks that this is advanced-level programming.

It is also not true that this is always more efficient.
If all those structs are on the heap, then there are a lot of ALLOCATE
calls needed, and ALLOCATE is very slow.
If you have small data, such as floats or small structs,
it is more efficient to just put them in the array directly.

It is not a good idea to contort a program because of some misguided
attempt at optimization (that may not be optimal anyway).
It is better to do what my SORT does, which is support any size of
array element (including one-cell, which could be a pointer).
Just let the application programmer use whatever programming technique
is most convenient for his application.
Don't force him to use an array of pointers and not allow any other technique.
The code is supposed to be "general-purpose," meaning that it can be used
in any reasonable way.

[dxf...@gmail.com]

On Monday, January 21, 2019 at 1:21:24 PM UTC+11, hughag...@gmail.com wrote:
> On Saturday, January 19, 2019 at 6:57:21 PM UTC-7, dxf...@gmail.com wrote:
> > On Friday, January 18, 2019 at 4:34:05 AM UTC+11, Alex McDonald wrote:
> > > Can you point out a post where someone other than Hugh describes his
> > > code as crap?
> >
> > Not necessarily in those words. Hugh doesn't have a monopoly on criticism.
>
> There aren't any code-libraries for ANS-Forth
> (except those of extremely low-quality, such as theforth.net and FFL),
> because the criteria for getting the code in is brown-nosing.

ForthNet appears quite agnostic to me, and while 'ANS-Forth' code
would obviously be an advantage getting one's ideas across, there's
nothing in the guidelines that says it must be. I don't have an
account so don't know if there's any vetting procedure. If ForthNet
is open to all and non-political, I don't see a problem. In fact
I'd find it a refreshing change.

>
> Elizabeth Rather infamously said that she "hates locals."

Chuck Moore and Jeff Fox have said much the same. Jeff spoke
at some length on this on c.l.f. and it completely turned me
around. Why hadn't someone told me this before - I thought.
Perhaps his posts on the topic may still be found.

> She really demands that parameters be passed between functions
> via global variables. Nobody will have their code accepted
> by the ANS-Forth cult unless they do this.

Hardly, given it was ANS that opened the hell-mouth to locals.

[foxaudio...@gmail.com]

On Sunday, January 20, 2019 at 9:21:24 PM UTC-5, hughag...@gmail.com wrote:

> Elizabeth Rather said this:
> ----------------------------------------------------------------
> Truly, I don't see the point of all this paranoia about reentrancy,
> particularly in systems without a multitasker. VARIABLE was *designed*
> for things that would be used in multiple definitions. I remember
> the horror of (*gasp*) global variables back in the 1960's in Fortran.
> But, frankly, in 30+ years of programming in Forth I never found them
> a problem. I think this is all about mythical dragons.
> ----------------------------------------------------------------
>
> Obviously, reentrancy is not just an issue within a multitasking system.
> It is an issue because you may be holding data in a global variable
> and call a sub-function that uses the same global variable.

Hi Hugh,

I take your point about Forth VARIABLES, but I don't see them as totally evil.
To me they are no different than people using DW or DATA statements in Assembler. Use them wisely and there is no problem. Use them badly and you are in trouble.

It also occurs to me that you can "protect" a variable in Forth so simply:

: PROTECT CREATE ;

VARIABLE X

: FOO 1 X +! ;

PROTECT X \ :-)

This is a lot less code than some alternatives and might be all that is needed in a little
embedded micro app.

But to your point, this is not re-entrant, but if I don't need re-entrancy in my program for
that data or the words that use it... is that a big deal?

[Ron Aaron]

On 21/01/2019 16:08, foxaudio...@gmail.com wrote:

> It also occurs to me that you can "protect" a variable in Forth so simply:
>
> : PROTECT CREATE ;
>
> VARIABLE X
>
> : FOO 1 X +! ;
>
> PROTECT X \ :-)

An interesting thought. Is "FORGET" not a standard word?

[Anton Ertl]

It is, but it will forget FOO, too.

Concerning this PROTECT, it's a bad implementation of a questionable
concept:

It's a bad implementation, because anyone who actually uses X after it
is "protected" will not notice the mistake where he made it. Better
implementation approaches are to make X an immediate word that
produces an error, or to hide the original X in a wordlist that is
removed from the search order when X should be "protected".

The concept of hiding X is questionable, because it runs counter to
the strengths of Forth: It makes it hard to work with the words
interactively; e.g., in the example above, I could call FOO, but I
could not check if it has actually increases X. Also, one idea
sometimes touted for Forth is to make the system so simple that you
can keep it all in your head. In that case you don't need this kind
of "protection".

[Ron Aaron]

On 21/01/2019 16:24, Anton Ertl wrote:

> Ron Aaron <ramb...@gmail.com> writes:
>
> It is, but it will forget FOO, too.

Ah, I forgot that :) In 8th, 'w:forget' only removes that word from
the dictionary, not subsequent entries.

> Concerning this PROTECT, it's a bad implementation of a questionable
> concept:
>
> It's a bad implementation, because anyone who actually uses X after it
> is "protected" will not notice the mistake where he made it. Better
> implementation approaches are to make X an immediate word that
> produces an error, or to hide the original X in a wordlist that is
> removed from the search order when X should be "protected".
>
> The concept of hiding X is questionable, because it runs counter to
> the strengths of Forth: It makes it hard to work with the words
> interactively; e.g., in the example above, I could call FOO, but I
> could not check if it has actually increases X.

Indeed. It's better to put such ancillary words in a different namespace.

Also, one idea
> sometimes touted for Forth is to make the system so simple that you
> can keep it all in your head. In that case you don't need this kind
> of "protection".

Alas, I find that my limit on what can fit in my head is trending
downward every day.

[Doug Hoffman]

On 1/21/19 9:08 AM, foxaudio...@gmail.com wrote:

> Hi Hugh,
>
> I take your point about Forth VARIABLES, but I don't see them as totally evil.

> But to your point, this is not re-entrant, but if I don't need re-entrancy in my program for
> that data or the words that use it... is that a big deal?

Further, as I have already pointed out, eliminating the VARIABLE in this
case is trivial and barely affects the code run time. The base algorithm
is unchanged. Anyone can make this change (if desired).

-Doug

[Stephen Pelc]

On Sun, 20 Jan 2019 21:19:05 -0800 (PST), dxf...@gmail.com wrote:

>If ForthNet
>is open to all and non-political, I don't see a problem. In fact
>I'd find it a refreshing change.

It is open to all. However, rude and nasty people are not
tolerated.

>Hardly, given it was ANS that opened the hell-mouth to locals.

Locals were in widespread use long before ANS. The notation
finally adopted by Forth-2012 was designed in the late 1980s
according to several correspondents.

Just because a system provides locals does not mean that you
have to use them. MPE data suggests that on, 32 bit targets,
non-local implementations are 50% faster and 25-50% smaller.
However, in some application domains, readability using locals
is much better IMHO.

Stephen

--
Stephen Pelc, ste...@mpeforth.com
MicroProcessor Engineering Ltd - More Real, Less Time
133 Hill Lane, Southampton SO15 5AF, England
tel: +44 (0)23 8063 1441, +44 (0)78 0390 3612
web: http://www.mpeforth.com - free VFX Forth downloads

[Gerry Jackson]

On 21/01/2019 02:21, hughag...@gmail.com wrote:
> On Saturday, January 19, 2019 at 6:57:21 PM UTC-7, dxf...@gmail.com wrote:
>> On Friday, January 18, 2019 at 4:34:05 AM UTC+11, Alex McDonald wrote:
>>> Can you point out a post where someone other than Hugh describes his
>>> code as crap?
>>
>> Not necessarily in those words. Hugh doesn't have a monopoly on criticism.
>
> There aren't any code-libraries for ANS-Forth

Don't forget the FSL

> (except those of extremely low-quality, such as theforth.net and FFL)

What is the basis for that assertion. Is it because:

1. You've carried out extensive tests on all the code contained therein?
2. You've reviewed all that code?
3. Anything not written by you is low quality by definition?
4. Because you got thrown out of the Forth 200X and Win32 Forth mailing
lists for being offensive and abusive?
5. Because you're afraid to release your code?
6. Ignorance?
7. Because you're a bigoted troll?

> because the criteria for getting the code in is brown-nosing.

Oh I see, that's the reason, technical merit is irrelevant. I was
forgetting you're a Forth Zen master.

--
Gerry

[Anton Ertl]

Gerry Jackson <do-no...@swldwa.uk> writes:
>On 21/01/2019 02:21, hughag...@gmail.com wrote:
>> (except those of extremely low-quality, such as theforth.net and FFL)

...

>Oh I see, that's the reason, technical merit is irrelevant.

FFL is the work of Dick van Oudheusden, and I am sure he considers
technical merit in his work on it. <https://github.com/irdvo/ffl> has
32 stars and 9 forks, so apparently there are a significant number of
other people who see value in it.

theforth.net has a very low barrier of entry. I would say that
technical merit is indeed irrelevant there; if a package is there, it
is not guaranteed to be of any quality, neither low nor high. Maybe
there will be a rating system (like github stars) for it one day.

[Gerry Jackson]

On 21/01/2019 17:45, Anton Ertl wrote:
> Gerry Jackson <do-no...@swldwa.uk> writes:
>> On 21/01/2019 02:21, hughag...@gmail.com wrote:
>>> (except those of extremely low-quality, such as theforth.net and FFL)
> ...

>>> because the criteria for getting the code in is brown-nosing.
>

>> Oh I see, that's the reason, technical merit is irrelevant.
>
> FFL is the work of Dick van Oudheusden, and I am sure he considers
> technical merit in his work on it. <https://github.com/irdvo/ffl> has
> 32 stars and 9 forks, so apparently there are a significant number of
> other people who see value in it.
> theforth.net has a very low barrier of entry. I would say that
> technical merit is indeed irrelevant there; if a package is there, it
> is not guaranteed to be of any quality, neither low nor high. Maybe
> there will be a rating system (like github stars) for it one day.

Unfortunately the way you've snipped Hugh's brown-nosing comment makes
it read as if I think the FFL has no technical merit. That is Hugh
Aguilar's criteria not mine - so I've reinstated his idiotic, malicious
reason for his assertion about low quality.

I agree there's no barrier to entry of code to theForth.net, even Hugh
could post his stringstack and novice packages there, but there's no
danger of that - he's afraid to do so!

--
Gerry

[dxf...@gmail.com]

On Tuesday, January 22, 2019 at 3:00:08 AM UTC+11, Stephen Pelc wrote:
> On Sun, 20 Jan 2019 21:19:05 -0800 (PST), dxf...@gmail.com wrote:
>
> >If ForthNet
> >is open to all and non-political, I don't see a problem. In fact
> >I'd find it a refreshing change.
>
> It is open to all. However, rude and nasty people are not
> tolerated.

If one were to exclude from the world of art and innovation
all the 'rude and nasty people' there would be a substantial
body of work absent.

>
> >Hardly, given it was ANS that opened the hell-mouth to locals.
>
> Locals were in widespread use long before ANS. The notation
> finally adopted by Forth-2012 was designed in the late 1980s
> according to several correspondents.
>
> Just because a system provides locals does not mean that you
> have to use them. MPE data suggests that on, 32 bit targets,
> non-local implementations are 50% faster and 25-50% smaller.
> However, in some application domains, readability using locals
> is much better IMHO.

However one may justify locals, they represent a different world
view - one that challenges Forth's proposition that stacks are
sufficient. Conflicts between the two systems inevitably arise
e.g. UNNEST - a simple idea easy to implement in Forth - becomes
problematic when locals are factored in.

The readability argument I believe Jeff answered nicely when
he said that, in Forth, it is the naming of words that provides
readability. Within code there are always comments.

[hughag...@gmail.com]

On Monday, January 21, 2019 at 9:00:08 AM UTC-7, Stephen Pelc wrote:
> rude and nasty people are not
> tolerated.

Your effort to get rid of immediacy in Forth is rude and nasty.
It is obvious that you are striving to prevent Forthers from
writing cross-compilers in Standard Forth in competition with MPE.
Certainly, immediacy is needed for a cross-compiler, or any meta-compiling.

Forth-200x will not be Forth anymore, given the recognizers.

I think that you are sabotaging Forth-200x so that it will not be
capable of being used in competition against VFX.
Your goal with Forth-200x is the same as Elizabeth Rather's goal with ANS-Forth.
You want to prevent portable programs.
Instead, you want "portable programmers," meaning that the Standard is a
toy language that students can learn on, but all features needed for writing
useful programs have been explicitly banned.

This is a typical example of you trying to sabotage Forth:

On Friday, May 18, 2018 at 4:57:19 AM UTC-7, Stephen Pelc wrote:
> On Thu, 17 May 2018 16:06:24 GMT, an...@mips.complang.tuwien.ac.at
> (Anton Ertl) wrote:
>
> >ste...@mpeforth.com (Stephen Pelc) writes:
> >>Why? Surely immediacy is just an implementation detail.
> >
> >There are two notions of immediacy in the standard:
> >
> >1) The one produced by IMMEDIATE
> >2) The one reported by FIND
> >
> >The intention of the Forth-94 committee was to support cmForth-like
> >implementations, and in cmForth FIND reports during compilation that,
> >e.g., + is immediate, althout it is not immediate according to notion
> >1) (it has default compilation semantics and is therefore not
> >immediate according to notion 1).
> >
> >So immediacy according to notion 2 is an implementation detail, while
> >immediacy according to notion 1 is not.
> >
> >Also, while according to notion 2, normal words like + can be
> >immediate or non-immediate, a word like IF must be reported as
> >immediate by FIND if we want the classical text interpreter to work.
> >
> >Note that notion 1 is the one that's more relevant in most cases,
> >exactly because that notion is not just an implementation issue.
>
> I'm sure you are right, if IMMEDIATE needs that amount of language
> lawyering, we ought to get rid of it.
>
> >> In terms of the
> >>ANS and Forth-2012 standards, IMMEDIATE behaviour has been a
> >>legacy behaviour for 23 years.

[hughag...@gmail.com]

On Monday, January 21, 2019 at 6:20:36 PM UTC-7, dxf...@gmail.com wrote:
> However one may justify locals, they represent a different world
> view - one that challenges Forth's proposition that stacks are
> sufficient. Conflicts between the two systems inevitably arise
> e.g. UNNEST - a simple idea easy to implement in Forth - becomes
> problematic when locals are factored in.

Forth doesn't make propositions --- people do.

I agree that overuse of locals is bad Forth ---
typical of recalcitrant C programmers.

Banning locals is a bad idea though.
My SORT-LIST needs locals. For example, we have 'COMPARER for the comparer xt.
Where are you going to put that other than a local?
It can't go on the return-stack because I have variable numbers of data
on the return-stack
(there are two loops that move data between the data-stack and return-stack).
Putting it on the data-stack would result in some horrific stack-juggling.

As for UNNEST I don't see any problem with implementing that.
UNNEST would be like EXIT except undoing two local-frames rather than one.
I don't think that UNNEST is a good idea though,
because this is unstructured programming. Too confusing!

I had locals in MFX. They had a lot more features than what ANS-Forth provided.
The MiniForth is the only Forth processor I know of that supported locals.

[m...@iae.nl]

On Tuesday, January 22, 2019 at 2:20:36 AM UTC+1, dxf...@gmail.com wrote:
> On Tuesday, January 22, 2019 at 3:00:08 AM UTC+11, Stephen Pelc wrote:
> > On Sun, 20 Jan 2019 21:19:05 -0800 (PST), dxf...@gmail.com wrote:

[..]

> If one were to exclude from the world of art and innovation
> all the 'rude and nasty people' there would be a substantial
> body of work absent.

[..]

There are many contemporary examples of that in art, where
people then proceed to avoid the works in question. However,
in innovation we don't see people stop using differential
calculus, semiconductor technology, or iphones. Or in other
words, the work first has to have unique and undeniable quality
for your statement to be applicable to it.

-marcel

[Anton Ertl]

dxf...@gmail.com writes:
>However one may justify locals, they represent a different world
>view - one that challenges Forth's proposition that stacks are
>sufficient.

It is more of a challenge to the view that minimalism (on the side of
the Forth system) is the only thing that is important.

Also, even for Chuck Moore and the Forth, Inc. school of locals-less
programming, stacks are not sufficient. They use VARIABLEs when there
are too many values around for them all to be kept on the stack.

>Conflicts between the two systems inevitably arise
>e.g. UNNEST - a simple idea easy to implement in Forth - becomes
>problematic when locals are factored in.

Not really. But EXIT may need to do more than just UNNEST/;S. So
what? Yes, you then cannot do ['] EXIT ... EXECUTE, but if I compare
the benefits of locals with that drawback, I go for locals.

>The readability argument I believe Jeff answered nicely when
>he said that, in Forth, it is the naming of words that provides
>readability.

Indeed, and locals have names, while stack items don't.

Anyway, Jeff Fox meant that one should factor code into short words
with well-chosen names, and this is a good idea when it works.
Several times, when someone rekindled the locals discussion, I posted
(e.g., in <2017Oct2...@mips.complang.tuwien.ac.at>) challenges of
real code where I had used locals, and did not see a way to use
factoring to make a locals-less version readable. IIRC nobody posted
any refactoring for F>BUF-RDP-TRY.

[dxf...@gmail.com]

On Tuesday, January 22, 2019 at 4:26:55 PM UTC+11, hughag...@gmail.com wrote:
> On Monday, January 21, 2019 at 6:20:36 PM UTC-7, dxf...@gmail.com wrote:
> > However one may justify locals, they represent a different world
> > view - one that challenges Forth's proposition that stacks are
> > sufficient. Conflicts between the two systems inevitably arise
> > e.g. UNNEST - a simple idea easy to implement in Forth - becomes
> > problematic when locals are factored in.
>
> Forth doesn't make propositions --- people do.

People in this case being Moore who created Forth.

>
> I agree that overuse of locals is bad Forth ---
> typical of recalcitrant C programmers.
>
> Banning locals is a bad idea though.

Only because it's unenforceable.

> My SORT-LIST needs locals.
> For example, we have 'COMPARER for the comparer xt.
> Where are you going to put that other than a local?
> It can't go on the return-stack because I have variable numbers of data
> on the return-stack
> (there are two loops that move data between the data-stack and return-stack).
> Putting it on the data-stack would result in some horrific stack-juggling.

It would appear you have created a set of criteria that demands
the use of locals.

> ...

[a...@littlepinkcloud.invalid]

m...@iae.nl wrote:
> On Tuesday, January 22, 2019 at 2:20:36 AM UTC+1, dxf...@gmail.com wrote:
>> On Tuesday, January 22, 2019 at 3:00:08 AM UTC+11, Stephen Pelc wrote:
>> > On Sun, 20 Jan 2019 21:19:05 -0800 (PST), dxf...@gmail.com wrote:
> [..]
>> If one were to exclude from the world of art and innovation
>> all the 'rude and nasty people' there would be a substantial
>> body of work absent.
> [..]
>
> There are many contemporary examples of that in art, where people
> then proceed to avoid the works in question. However, in innovation
> we don't see people stop using differential calculus, semiconductor
> technology, or iphones.

That's an excellent selection! :-)

> Or in other words, the work first has to have unique and undeniable
> quality for your statement to be applicable to it.

Indeed. And these days computer programming is very much a team sport:
we all progress by working with others. This is especially true in the
case of Free Software, the most dynamic, and I daresay innovative,
sector of the industry.

Andrew.

[a...@littlepinkcloud.invalid]

Anton Ertl <an...@mips.complang.tuwien.ac.at> wrote:
> dxf...@gmail.com writes:
>>However one may justify locals, they represent a different world
>>view - one that challenges Forth's proposition that stacks are
>>sufficient.
>
> It is more of a challenge to the view that minimalism (on the side of
> the Forth system) is the only thing that is important.

I don't think anybody holds that view.

> Also, even for Chuck Moore and the Forth, Inc. school of locals-less
> programming, stacks are not sufficient. They use VARIABLEs when there
> are too many values around for them all to be kept on the stack.

Exactly so.

Andrew.

[dxf...@gmail.com]

I seem to recall just recently on c.l.f. someone commenting
that we tend to overlook flaws of character when it's in our
interest to do so.

>
> -marcel

[Anton Ertl]

a...@littlepinkcloud.invalid writes:
>m...@iae.nl wrote:
>> On Tuesday, January 22, 2019 at 2:20:36 AM UTC+1, dxf...@gmail.com wrote:
>>> If one were to exclude from the world of art and innovation
>>> all the 'rude and nasty people' there would be a substantial
>>> body of work absent.
>> [..]
>>
>> There are many contemporary examples of that in art, where people
>> then proceed to avoid the works in question. However, in innovation
>> we don't see people stop using differential calculus, semiconductor
>> technology, or iphones.
>
>That's an excellent selection! :-)

Please elaborate! Was Leibniz rude and nasty? Or a key person in
semiconductors or the iPhone?

[dxf...@gmail.com]

On Tuesday, January 22, 2019 at 7:55:25 PM UTC+11, Anton Ertl wrote:
> dxf...@gmail.com writes:
> >However one may justify locals, they represent a different world
> >view - one that challenges Forth's proposition that stacks are
> >sufficient.
>
> It is more of a challenge to the view that minimalism (on the side of
> the Forth system) is the only thing that is important.

Minimalism is hard to ignore when it's the basis of a language.

>
> Also, even for Chuck Moore and the Forth, Inc. school of locals-less
> programming, stacks are not sufficient. They use VARIABLEs when there
> are too many values around for them all to be kept on the stack.
>
> >Conflicts between the two systems inevitably arise
> >e.g. UNNEST - a simple idea easy to implement in Forth - becomes
> >problematic when locals are factored in.
>
> Not really. But EXIT may need to do more than just UNNEST/;S. So
> what? Yes, you then cannot do ['] EXIT ... EXECUTE, but if I compare
> the benefits of locals with that drawback, I go for locals.

The benefit of UNNEST is the ability to bypass the calling definition
with a minimum of cost. I'm not sure what benefit locals have.

>
> >The readability argument I believe Jeff answered nicely when
> >he said that, in Forth, it is the naming of words that provides
> >readability.
>
> Indeed, and locals have names, while stack items don't.

I didn't come to forth via other languages that used locals and
don't miss them at all.

>
> Anyway, Jeff Fox meant that one should factor code into short words
> with well-chosen names, and this is a good idea when it works.

I don't factor for naming's sake and can't imagine Jeff did because
he found forth unreadable.

> Several times, when someone rekindled the locals discussion, I posted
> (e.g., in <2017Oct2...@mips.complang.tuwien.ac.at>) challenges of
> real code where I had used locals, and did not see a way to use
> factoring to make a locals-less version readable. IIRC nobody posted
> any refactoring for F>BUF-RDP-TRY.

I implemented a full-featured fp output package. Not only is there
no local to be found, the thought never arose.

[m...@iae.nl]

On Tuesday, January 22, 2019 at 11:56:10 AM UTC+1, Anton Ertl wrote:
> a...@littlepinkcloud.invalid writes:
> >m...@iae.nl wrote:
> >> On Tuesday, January 22, 2019 at 2:20:36 AM UTC+1, dxf...@gmail.com wrote:
> >>> If one were to exclude from the world of art and innovation
> >>> all the 'rude and nasty people' there would be a substantial
> >>> body of work absent.
> >> [..]
> >>
> >> There are many contemporary examples of that in art, where people
> >> then proceed to avoid the works in question. However, in innovation
> >> we don't see people stop using differential calculus, semiconductor
> >> technology, or iphones.
> >
> >That's an excellent selection! :-)
>
> Please elaborate! Was Leibniz rude and nasty? Or a key person in
> semiconductors or the iPhone?

I was thinking of Newton, Shockley, and Jobs.

-marcel

[Anton Ertl]

m...@iae.nl writes:
>> >> However, in innovation
>> >> we don't see people stop using differential calculus, semiconductor
>> >> technology, or iphones.
>> >
>> >That's an excellent selection! :-)
>>
>> Please elaborate! Was Leibniz rude and nasty? Or a key person in
>> semiconductors or the iPhone?
>
>I was thinking of Newton, Shockley, and Jobs.

If Newton had been shunned and never published because of his
behaviour, we would still have differential calculus thanks to
Leibniz. I don't know anything about Shockley.

I don't know much about Jobs, but what I read and saw about him showed
that he was pretty unpleasant in the Lisa and Mac days, but was better
in the iPhone days (essentially after returning to Apple); anyway, if
iPhones had never existed, people would have used Android Phones or
Windows Phones instead; would they look different if iPhones never
existed? I don't think there would be much difference.

[Paul Rubin]

a...@littlepinkcloud.invalid writes:
>> [Anton:] Also, even for Chuck Moore and the Forth, Inc. school of

>> locals-less programming, stacks are not sufficient. They use
>> VARIABLEs when there are too many values around for them all to be
>> kept on the stack.
>
> Exactly so.

Merge sorting is usually implemented using recursion. Using VARIABLEs
instead of locals for that sounds messy. Is there a goiod way to handle
it?

[m...@iae.nl]

What is 'good'?

v @ >R ... R> v !

-marcel

[m...@iae.nl]

On Tuesday, January 22, 2019 at 4:52:51 PM UTC+1, Anton Ertl wrote:
> m...@iae.nl writes:
> >> >> However, in innovation
> >> >> we don't see people stop using differential calculus, semiconductor
> >> >> technology, or iphones.
> >> >
> >> >That's an excellent selection! :-)
> >>
> >> Please elaborate! Was Leibniz rude and nasty? Or a key person in
> >> semiconductors or the iPhone?
> >
> >I was thinking of Newton, Shockley, and Jobs.
>
> If Newton had been shunned and never published because of his
> behaviour, we would still have differential calculus thanks to
> Leibniz.

Yes, but that is a different interesting phenomenon.

My off-topix point here was that if Leibniz hadn't invented
it too, we still would happily be using Newton's invention.

> I don't know anything about Shockley.

https://en.wikipedia.org/wiki/William_Shockley

> I don't know much about Jobs, but what I read and saw about him showed
> that he was pretty unpleasant in the Lisa and Mac days, but was better
> in the iPhone days (essentially after returning to Apple); anyway, if
> iPhones had never existed, people would have used Android Phones or
> Windows Phones instead; would they look different if iPhones never
> existed? I don't think there would be much difference.

See if you can swap some person's iPhone for your Windows phone
by telling him/her about Jobs' bad character :-)

Anyway, I was just trying to short-circuit the OPs
<good work> IF <bad character of person X overlooked> THEN
by questioning the <good work>, not the moral strength of
people wanting something of dubious provenance, however
interesting that discussion could be.

-marcel

[dxf...@gmail.com]

The second being a Nobel Prize winner. While one can say his personal
views had nothing to do with his achievements, it's not unusual to see the
art community for example defending works that fall into the obnoxious,
if not criminal, category. Just such a case occurred in Australia a
decade ago.

>
> -marcel

[none albert]

In article <871s54f...@nightsong.com>,

Paul Rubin <no.e...@nospam.invalid> wrote:
>a...@littlepinkcloud.invalid writes:
>>> [Anton:] Also, even for Chuck Moore and the Forth, Inc. school of
>>> locals-less programming, stacks are not sufficient. They use
>>> VARIABLEs when there are too many values around for them all to be
>>> kept on the stack.
>>
>> Exactly so.
>
>Merge sorting is usually implemented using recursion. Using VARIABLEs

That is your lisp background. Efficient implementations (like
mine) use an explicit stack. Recursion can be made to work using
tail recursion but that is a cludge, and now continuations.
Especially in Forth with a potentially huge data stack there are
alternatives to keeping track of where you left of using a
return stack.
I recognized one of the latest Euler problems as a disguised coin
change program. The recursive approach can be mitigated
by memoizing but other approaches are faster. The standard recursive
approached would not give the solution in a reasonable time,
say less than hundred years.

>instead of locals for that sounds messy. Is there a goiod way to handle
>it?

You realize that in fact you're stacking data on the return stack?
Then there is a way to use the data stack for that too.
Thinking it through you may find a surprisingly simple solution.
Disclaimer, solutions depend on the problem.

Groetjes Albert
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[Anton Ertl]

m...@iae.nl writes:
>On Tuesday, January 22, 2019 at 4:52:51 PM UTC+1, Anton Ertl wrote:
>> m...@iae.nl writes:
>> >> >> However, in innovation
>> >> >> we don't see people stop using differential calculus, semiconductor
>> >> >> technology, or iphones.
>> >> >
>> >> >That's an excellent selection! :-)
>> >>
>> >> Please elaborate! Was Leibniz rude and nasty? Or a key person in
>> >> semiconductors or the iPhone?
>> >
>> >I was thinking of Newton, Shockley, and Jobs.
>>
>> If Newton had been shunned and never published because of his
>> behaviour, we would still have differential calculus thanks to
>> Leibniz.
>
>Yes, but that is a different interesting phenomenon.
>
>My off-topix point here was that if Leibniz hadn't invented
>it too, we still would happily be using Newton's invention.

Probably. Anyway, his behaviour probably still damaged his potential
achievements. For a more contemporary figure, consider Edward Teller.
He cut himself off from his former Los Alamos collegues because of his
behaviour, and I doubt that he achieved as much as he could have
otherwise.

>> I don't know much about Jobs, but what I read and saw about him showed
>> that he was pretty unpleasant in the Lisa and Mac days, but was better
>> in the iPhone days (essentially after returning to Apple); anyway, if
>> iPhones had never existed, people would have used Android Phones or
>> Windows Phones instead; would they look different if iPhones never
>> existed? I don't think there would be much difference.
>
>See if you can swap some person's iPhone for your Windows phone
>by telling him/her about Jobs' bad character :-)

I don't know anything about bad behaviour in the iPhone days, but even
if there was, why should "some person" believe me, especially when I
am telling them something bad about his or her Messiah?

Apart from that, I don't have a Windows phone, and I would not swap my
trusty 10-year old foldable Nokia 2760 with exchangable battery, which
does exactly what I need for an iPhone even if Jobs was the Messiah.

[Anton Ertl]

albert@cherry.(none) (albert) writes:
>In article <871s54f...@nightsong.com>,
>Paul Rubin <no.e...@nospam.invalid> wrote:
>>Merge sorting is usually implemented using recursion. Using VARIABLEs
>
>That is your lisp background. Efficient implementations (like
>mine) use an explicit stack.

Show the numbers. In my experiments with quicksort
<2013Aug1...@mips.complang.tuwien.ac.at>, using recursion (for
one call) and manually eliminated tail-recursion (for the other call)
was consistently at least as fast or faster than the three versions
that use an explicit stack, on both Gforth and VFX.

>Recursion can be made to work using
>tail recursion but that is a cludge,

Please support this claim!

Anyway, the usual formulation of mergesort

: sort recursive
\ just a sketch
split
sort swap
sort
merge ;

is not tail-recursive, so one cannot eliminate tail-recursion.

[Anton Ertl]

an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>Several times, when someone rekindled the locals discussion, I posted
>(e.g., in <2017Oct2...@mips.complang.tuwien.ac.at>) challenges of
>real code where I had used locals, and did not see a way to use
>factoring to make a locals-less version readable. IIRC nobody posted
>any refactoring for F>BUF-RDP-TRY.

I have now put these challenges up on the web:

http://www.complang.tuwien.ac.at/forth/locals-challenge.html

[none albert]

In article <2019Jan2...@mips.complang.tuwien.ac.at>,

Anton Ertl <an...@mips.complang.tuwien.ac.at> wrote:
>albert@cherry.(none) (albert) writes:
>>In article <871s54f...@nightsong.com>,
>>Paul Rubin <no.e...@nospam.invalid> wrote:
>>>Merge sorting is usually implemented using recursion. Using VARIABLEs
>>
>>That is your lisp background. Efficient implementations (like
>>mine) use an explicit stack.
>
>Show the numbers. In my experiments with quicksort
><2013Aug1...@mips.complang.tuwien.ac.at>, using recursion (for
>one call) and manually eliminated tail-recursion (for the other call)
>was consistently at least as fast or faster than the three versions
>that use an explicit stack, on both Gforth and VFX.

I've no numbers but I hope I did set you thinking.
Knuth never gives a recursive version of his algorithms.

>
>>Recursion can be made to work using
>>tail recursion but that is a cludge,
>
>Please support this claim!
>
>Anyway, the usual formulation of mergesort
>
>: sort recursive
>\ just a sketch
> split
> sort swap
> sort
> merge ;
>
>is not tail-recursive, so one cannot eliminate tail-recursion.

Take a closer look at my merge-sort. It is not only non-recursive
it is also inside-out or upside-down. or dynamic programming
the wrong way.
E.g. If you apply the above to the lisp definitions in Probst lisp,
you have to parse the whole list just to split it.
My MERGE-SORT will parse until the first non-order pair.

The difference becomes apparent if you apply it on a sorted list.
My MERGE-SORT will parse once and conclude it is finished.

The situation with the coins problem is similar, but more
details would be a spoiler for an Euler problem.

>
>- anton

[Paul Rubin]

albert@cherry.(none) (albert) writes:
> I've no numbers but I hope I did set you thinking.
> Knuth never gives a recursive version of his algorithms.

Of course you can simulate recursion with a stack, and Knuth gives his
algorithms in assembly language so explicit recursion isn't available.
But higher level languages like (cough) Forth include recursion because
it really is the most natural way to write some algorithms. So if I'm
coding that type of algorithm I'd hope to be able to use the feature.

Yeah manually pushing VARIABLEs on the stacks works, though as Anton's
web page mentions, it can make testing harder. Also it seems to me that
an optimizing compiler might have an easier time putting locals in
registers than putting VARIABLEs in them.

[NN]

Forth is a stack language, just add more stacks.
I have recently started add 2 more stacks to my projects,
P and Q and it seems to help.

Just my 2 cents

[none albert]

In article <87o987d...@nightsong.com>,

Please note that in my MERGE-SORT nowhere VARIABLES are to be seen
except for the non-essential purpose to keep the execution tokens
of the comparison routines. Compared to recursion the looping
requires no fresh instances of variables or locals.

The difficult task for the optimiser is to realize that the execution
tokens are constant while merging, and can be inlined.
That is Just In Time compilation, but could be done in Forth by an
explicit OPTIMISE command.

Groetjes Albert

[Paul Rubin]

albert@cherry.(none) (albert) writes:
> Please note that in my MERGE-SORT nowhere VARIABLES are to be seen
> except for the non-essential purpose to keep the execution tokens of
> the comparison routines. Compared to recursion the looping requires no
> fresh instances of variables or locals.

I don't see that code in the thread any more, but ok, merge sort is
simple enough that maybe there aren't so many values to juggle. What I
often find myself doing if I prefer avoiding locals is 3 steps:

1) think about how to write the code without locals, and start getting
confused.

2) shrug my shoulders and write the code with locals, straightforwardly.

3) see that I can iteratively refactor the locals-based code, getting
rid of the locals one at a time until none are left. What remains is
usually harder to read than the locals version, but I then have a "pure"
Forth implementation.

Given that there is a working implementation at the end of step 2,
proceeding with step 3 seems to me to burn development time for some
nebulous benefit unrelated to getting the task done.

For "the journey is the reward" recreational programming, that's fine.
It's like going on a long bicycle trip instead of taking a car or
airplane. For professional programming where the idea is mainly to get
to the destination with as little fuss as possible, going by bicycle
seems like a counterproductive approach.

[dxf...@gmail.com]

On Thursday, January 24, 2019 at 2:57:18 AM UTC+11, Anton Ertl wrote:
> an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> >Several times, when someone rekindled the locals discussion, I posted
> >(e.g., in <2017Oct2...@mips.complang.tuwien.ac.at>) challenges of
> >real code where I had used locals, and did not see a way to use
> >factoring to make a locals-less version readable. IIRC nobody posted
> >any refactoring for F>BUF-RDP-TRY.
>
> I have now put these challenges up on the web:
>
> http://www.complang.tuwien.ac.at/forth/locals-challenge.html

Perhaps the challenge should be turned back on you. How far
are you prepared to re-think your approach? It seems to me
you have created your own hell. I see nothing appealing in
long definitions littered with locals which is the 'C' approach.

I observe you like to pass all inputs via the parameter stack.
Chances are that many of these already exist as constants or
values elsewhere in which case they may be referenced directly.

[dxf...@gmail.com]

All the evidence is that professionals in forth go to a forth solution
directly because they've seen how enough times before.

[hughag...@gmail.com]

On Wednesday, January 23, 2019 at 3:05:50 AM UTC-7, Anton Ertl wrote:
> m...@iae.nl writes:
> >On Tuesday, January 22, 2019 at 4:52:51 PM UTC+1, Anton Ertl wrote:
> >> m...@iae.nl writes:
> >> If Newton had been shunned and never published because of his
> >> behaviour, we would still have differential calculus thanks to
> >> Leibniz.
> >
> >Yes, but that is a different interesting phenomenon.
> >
> >My off-topix point here was that if Leibniz hadn't invented
> >it too, we still would happily be using Newton's invention.
>
> Probably. Anyway, his behaviour probably still damaged his potential
> achievements. For a more contemporary figure, consider Edward Teller.
> He cut himself off from his former Los Alamos collegues because of his
> behaviour, and I doubt that he achieved as much as he could have
> otherwise.

In regard to rquotations, I can paraphrase the above quote as:
"If Hugh Aguilar hadn't invented upgraded rquotations to access the
parent function's locals despite the HOF having locals of its own,
we would happily be using Stephen Pelc's invention of this as a
closed-source proprietary feature of VFX and
we would be happily paying Stephen Pelc big money for this feature."

Anton Ertl is really not the best candidate to present himself as
an expert on good and bad behavior, because Anton Ertl is a liar.

Anton Ertl and Bernd Paysan wrote a EuroForth 2018 paper:
"Closures --- the Forth way"
In this paper they said:
---------------------------------------------------------------------------
Of course, in classical Forth fashion, some users explored the idea of what outer-locals accesses can be performed with minimal effort.
In particular, Usenet user “humptydumpty” introduced rquotations, a simple quotation-like implementation that uses return-address manipulation.
The Forth system does not know about these rquotations and therefore treats any locals accessed inside rquotations as if they were accessed outside.
In the case of Gforth (as currently implemented) this works as long as the locals stack is not changed in the meantime;
e.g., the higher-order word that calls the rquotation must not use locals.

There is no easy way to see whether this restriction has been met; this is also classical Forth style, but definitely not user-friendly.
Static analysis could be used to find out in many cases whether the restriction has been met, but that would probably require more effort than implementing
the approach presented in this paper, while not providing as much functionality.
---------------------------------------------------------------------------

They are liars!
They are insulting myself and HumptyDumpty by describing rquotations as:
"a simple quotation-like implementation."
What they are presenting in their paper is just :NONAME with some syntactic sugar. This is a simple quotation-like faked-out implementation.
Anton Ertl and Bernd Paysan are straight-out lying when they say:
"the higher-order word that calls the rquotation must not use locals."

Both of these liars know perfectly well that my rquotations allow the HOF (higher-order function) to have local variables,
and simultaneously allow the rquotation to access the parent function's local variables
(the parent function in which the rquotation was defined and which called the HOF that executed the rquotation).

Stephen Pelc is not a fool. He knows that the post-Elizabeth future
of Forth will include general-purpose data-structures.
He also knows that general-purpose data-structures need quotations
that access the parent function's locals despite the HOF having locals
of its own.
Stephen Pelc's plan is that this will be a proprietary feature of VFX
and that Forth-200x will be limited to the worthless fake quotation.
Stephen Pelc's expectation is that stupid little Forth students (me)
will implement general-purpose data-structures that are vendor-specific
to VFX because they depend upon these quotations.
They will value-add to VFX for free.

Why did Anton Ertl and Bernd Paysan lie in their EuroForth paper?
EuroForth is supposedly a forum for presenting innovative ideas,
and is not supposed to be a platform for attacking other people.
Anton Ertl and Bernd Paysan broke the rules by using EuroForth to attack
my rquotations by blatantly lying about them, saying that they don't work.

Most likely, Stephen Pelc promised Anton Ertl and Bernd Paysan jobs at
MPE in exchange for attacking my rquotations at EuroForth by lying.
Stephen Pelc already has the Forth-200x committee member Peter Knaggs
in his employ, so it makes sense that he should also employ the other
Forth-200x committee members Anton Ertl and Bernd Paysan.
Stephen Pelc wants the entire Forth-200x committee to do what he tells
them to do, including lying for him.
Forth-200x is astro-turf --- it is faked up to look like a grassroots
project, but it is actually controlled entirely by MPE.
Stephen Pelc's goal is to maximize MPE's profits.
He considers the Forth community to be his most hated enemy.
He is purposely crippling Forth-200x so the Forth community won't have
a meaningful Forth standard that they can use in competition with VFX.

[hughag...@gmail.com]

I wrote SORT-LIST as recursive and using locals initially
because that was much easier and allowed me to learn how MergeSort works.
What I have now is several generations of upgrades later.
All of these upgrades were done with the intention of boosting efficiency.

I am a professional in Forth because I made money writing Forth.
I will use locals when I think they make the job easier.
This is a "Forth solution" assuming that locals are a valid part of Forth.
Elizabeth Rather is the only person who says that locals
are not a valid part of Forth.
She has never written a Forth program. She is not a valid part of Forth.

There is a lot of difference between writing code-library Forth
and writing application Forth.
In a code-library, efficiency is critical.
I avoided the use of locals as much as possible in SORT-LIST for efficiency.
In application code, convenience is more important than efficiency.
Most of the run-time will be spent in the low-level functions such as
SORT-LIST but the high-level application code can be less efficient.
Similarly, Python has traditionally been very inefficient,
but people were okay with this because the low-level functions were written
in C and were efficient. Python is just a scripting language on top of C.

[Anton Ertl]

NN <novembe...@gmail.com> writes:
>On Wednesday, 23 January 2019 15:57:18 UTC, Anton Ertl wrote:
>> I have now put these challenges up on the web:
>>
>> http://www.complang.tuwien.ac.at/forth/locals-challenge.html

...

>Forth is a stack language, just add more stacks.

That's a good plan for data which one does not want to process with
the existing words (which work on the data or FP stack), e.g., for
vectors (which get their own set of words), or for the current object
(which is only used by method and object-field words, which are
defined to access the current object).

But for, e.g., cells that one wants to compute with, we already have
the data stack. Adding another stack means that you have to move the
data to this stack and then, when you need to compute with it, from
this stack. I don't consider it superior to using locals. And it's
certainly not a demonstration of the claim that factoring can always
eliminate the problems that induce me to use locals.