On Thursday, March 17, 2022 at 10:07:00 AM UTC+1, minf...@arcor.de wrote:
> A practical application example:
> Alarm logs in realtime control systems are one area where sorting is
> required for output on display, reports, data extraction and analysis.
> When this could touch time-critical functions, sorting is often supported by
> background indexing while new alarms are added to the alarm tables.
> IOW fancy sorting algorithms or data movement are not necessary here.

Well, I guess that's the point here - different problems require different techniques.
I often find myself in situations where I got A, but I need an association with B.

Now I see myself people crying to me "trees, associative arrays, hash tables" - but very,
very often these things are fixed. They MIGHT have the occasional maintenance for one
reason or another, but in essence: fixed.

Now it REALLY depends on the problem. Is it consulted very often with large amounts of
data or just once at startup? Since the "lookup" routine doesn't change it would be weird to
introduce a lot of overhead (bloat if you will) - especially if other fast techniques are available.

If speed is not an issue, I do a linear search O(n). I got a lib for that, so that's a one liner. If speed
is an issue, then I do a binary search O(log n). If I can enumerate the data (offset may be required)
I do a direct lookup O(1).

Strings may be sped up by doing a hash. Sometimes I use a mix of hashing and binary search to
keep the required amount of space down.

Anyway, my life revolves around tables and structures. That's why.. ;-)

Hans Bezemer

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> What are the use cases? I have not found a serious use for search
> trees in my programming, much less balanced search trees.

They have deterministic access time unlike hash tables, and it is easy
to traverse them in key order. Also, if you are willing to mutate them,
you can do fast updates and deletions by occasionally splitting nodes.
Databases do this with B-trees all the time.

Also, in the case where you don't need to update, they can use more
compact storage than hash tables do (Patricia trees). Search engines
typically store indexes that way. You have a big index, then one or
more generations of smaller indexes for updates, and now and then you do
a big merge to get a new big index.

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> The typical approach on memory-starved systems was static arrays

I don't know about true memory starvation (microcontroller with a few
hundred bytes of ram) but I remember working on a PDP-11 text editor.
Its buffer representation was linked lists of up to something like 64
bytes, so insertions and deletions operated on those list nodes and
could split and merge them.

Ron AARON <clf@8th-dev.com> writes:
> I'm unsure what you mean, then, by 'mutation'...

Mutation means modifying the contents of computer memory. Like the
memory contents are written on graph paper in pencil, and you can update
a cell by erasing the old contents and writing something new in its
place.

Functional or immutable programming is a style where you write with a
pen instead of a pencil, so you can't update or erase. You can only
write stuff in new empty squares. In reality, gc finds
no-longer-accessible old squares and recycles them into new squares, but
your program can't tell that this is happening. Instead of hash tables
you use balanced trees, instead of loops with a mutable index you use
recursion, etc. Functional languages always optimize away tail calls so
you can write recursive loops that don't overflow the stack.

SICP (mitpress.mit.edu/sicp) presents Scheme in mostly functional style,
and Haskell (learnyouahaskell.com is a good place to start) is a
"purely" (well, almost purely) functional languages.

This approach has costs, but gives various theoretical and practical
advantages for validating properties of programs. Basically certain
classes of bugs go away, just like programming without the "goto"
statement has costs but cleans up some control flow confusion.

On 18/03/2022 3:43, Paul Rubin wrote:
> Ron AARON <clf@8th-dev.com> writes:
>> I'm unsure what you mean, then, by 'mutation'...
>
> Mutation means modifying the contents of computer memory. Like the
> memory contents are written on graph paper in pencil, and you can update
> a cell by erasing the old contents and writing something new in its
> place.

Right, that's what I had thought you meant by the term.

8th's model is that containers are mutable (arrays, maps, etc); that
eliminates excessive copying (when you just want to change one item in
an array, for instance).

This can lead to a little excitement when the programmer didn't read the
documentation, and wonders why an array embedded in a word seems to
change...

>
> Functional or immutable programming is a style where you write with a
> pen instead of a pencil, so you can't update or erase. You can only
> write stuff in new empty squares. In reality, gc finds
> no-longer-accessible old squares and recycles them into new squares, but
> your program can't tell that this is happening. Instead of hash tables
> you use balanced trees, instead of loops with a mutable index you use
> recursion, etc. Functional languages always optimize away tail calls so
> you can write recursive loops that don't overflow the stack.

Are there any (serious) languages which don't optimize tail calls by
default?

> SICP (mitpress.mit.edu/sicp) presents Scheme in mostly functional style,
> and Haskell (learnyouahaskell.com is a good place to start) is a
> "purely" (well, almost purely) functional languages.

Java, for that matter, has a lot of the immutable-data philosophy; but
it's applied inconsistently. Of course, it's not functional (in more
than one way, IMO).

>
> This approach has costs, but gives various theoretical and practical
> advantages for validating properties of programs. Basically certain
> classes of bugs go away, just like programming without the "goto"
> statement has costs but cleans up some control flow confusion.

I'll just say that the hand-wringing over 'goto' is overwrought. I don't
make a habit of using it (in C code), but sometimes it really is the
best way to do something.

Ron AARON <clf@8th-dev.com> writes:
> Are there any (serious) languages which don't optimize tail calls by
> default?

Forth? :)

> Java, for that matter, has a lot of the immutable-data philosophy;

No I mean it's much different: functional style generally prefers trees
or lists over arrays, for example.

On 18/03/2022 8:13, Paul Rubin wrote:
> Ron AARON <clf@8th-dev.com> writes:
>> Are there any (serious) languages which don't optimize tail calls by
>> default?
>
> Forth? :)

You might be joking, but Reva and 8th both did that optimization, and
I'm pretty sure others do as well. It's almost a no-brainer.

>
>> Java, for that matter, has a lot of the immutable-data philosophy;
>
> No I mean it's much different: functional style generally prefers trees
> or lists over arrays, for example.

Well, I'll concede the point, not having a horse in the race.

Ron AARON <clf@8th-dev.com> writes:
>Are there any (serious) languages which don't optimize tail calls by
>default?

What is "by default" supposed to mean? Given that you say
"languages", the question is about guaranteeing tail-call
optimization. And looking at
<https://en.wikipedia.org/wiki/Tail_call#Language_support>, the
question becomes if there is any language that a significant
proportion of programmers take serious that guarantees tail-call
optimization. Most languages that guarantee it are niche languages
(not taken seriously by most programmers), and for the most popular
language that at least comes close to guaranteeing it (the wording is
not very enlightening), JavaScript, two out of three implementations
are listed as "rejecting" (whatever this means) this standard feature.

Interesting cases of languages that do not guarantee tail-call
optimization although I expected it are Common Lisp and F#.

- 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 2021: https://euro.theforth.net/2021

On 3/17/22 1:30 AM, Paul Rubin wrote:

> I think resizeable arrays are more usable now than they were in the old
> days on memory starved systems. [snip] ...
>
> Lists are also natural if you program in functional style, since you
> don't have to mutate existing objects (consing is just new allocations:
> the old stuff stays the same).

Yes. Stroustrup says to use arrays instead of lists because lists use
more memory (for the link address(s)) and lists cost time because
finding the insertion/deletion point is slow due to the required linear
search.

I use arrays for most all of my list needs. Though linked lists are
useful for some things such as adding items to the end without having to
allocate memory.

-Doug

On 2022-03-18 9:49, Anton Ertl wrote:
> Ron AARON <clf@8th-dev.com> writes:
>> Are there any (serious) languages which don't optimize tail calls by
>> default?
>
> What is "by default" supposed to mean? Given that you say
> "languages", the question is about guaranteeing tail-call
> optimization. ...

So I've always turn on some optimization with gcc and clang, and though
that the default was to do tail-call optimization. Turns out I was
wrong, and so I retract...

On Friday, March 18, 2022 at 6:26:50 AM UTC+1, Ron AARON wrote:
> On 18/03/2022 3:43, Paul Rubin wrote:
[..]
> I'll just say that the hand-wringing over 'goto' is overwrought. I don't
> make a habit of using it (in C code), but sometimes it really is the
> best way to do something.

If it is good enough for Knuth, it is good enough for me.

-marcel

Ron AARON <clf@8th-dev.com> writes:
> You might be joking, but Reva and 8th both did that optimization, and
> I'm pretty sure others do as well. It's almost a no-brainer.

gforth doesn't seem to:

Gforth 0.7.3, ...
: foo ( n -- 0 ) dup 0<> IF 1- recurse THEN ; ok
100 foo . 0 ok
1000 foo . 0 ok
100000 foo .
:4: Return stack overflow
100000 >>>foo<<< .

Python chooses not to, on the grounds that it makes debugging harder.

GCC and some other compilers implement it as an optimization, but the
language specs don't require it, so it doesn't entirely count. However,
I'm surprised to hear (per Anton's post) that F# doesn't require it.
Scheme, OCaml, and Haskell all require it, as there is basically no
other way to write a loop.

Give Haskell a try, it is like a mind expanding drug ;)

On 3/17/22 02:57, Anton Ertl wrote:
> Ron AARON <clf@8th-dev.com> writes:
>>
>>
>> On 16/03/2022 18:06, Anton Ertl wrote:
>>> What's the obsession with sorting? I have not needed a
>>> sort in Forth in the 38 years since I started using it. And IIRC not
>>> in C, either.
>>
>> Really? I've needed sorting for a variety of applications (in 8th, or
>> C/C++, or any other language -- the language is besides the point).
>
> The language is important. In most languages sorting is not needed,

> but the shell has tools such as join and uniq that require sorted
> inputs (or, in the case of many uses of uniq, are useless without
> sorting first); with hash-table-based equivalents of these tools most
> of my uses of sort in shell scripts could be eliminated, and thus most
> of my uses of sorting. Of course, in my shell usage there is still
> the following usage:
>
> Sorting is useful for human consumption, so I sometimes do it as last
> step on the output of a Forth or C program (and I have a nice shell
> tool called sort for that). But sorting is normally not useful for
> internal operations of programs; hashing is almost always better
> there.
> ...

Try writing a trapezoid integrator or Simpson's rule integrator without
using sorted (x, y) pairs, sorted on x. Algorithms for numerical
integration, differentiation, fast-Fourier and other types of transforms
are a few of the cases where sorting is essential. Sorting is not just
for user-convenient output.

--
Krishna

Krishna Myneni schrieb am Freitag, 18. März 2022 um 17:26:26 UTC+1:
> On 3/17/22 02:57, Anton Ertl wrote:
> > Ron AARON <c...@8th-dev.com> writes:
> >>
> >>
> >> On 16/03/2022 18:06, Anton Ertl wrote:
> >>> What's the obsession with sorting? I have not needed a
> >>> sort in Forth in the 38 years since I started using it. And IIRC not
> >>> in C, either.
> >>
> >> Really? I've needed sorting for a variety of applications (in 8th, or
> >> C/C++, or any other language -- the language is besides the point).
> >
> > The language is important. In most languages sorting is not needed,
>
>
>
> > but the shell has tools such as join and uniq that require sorted
> > inputs (or, in the case of many uses of uniq, are useless without
> > sorting first); with hash-table-based equivalents of these tools most
> > of my uses of sort in shell scripts could be eliminated, and thus most
> > of my uses of sorting. Of course, in my shell usage there is still
> > the following usage:
> >
> > Sorting is useful for human consumption, so I sometimes do it as last
> > step on the output of a Forth or C program (and I have a nice shell
> > tool called sort for that). But sorting is normally not useful for
> > internal operations of programs; hashing is almost always better
> > there.
> > ...
>
> Try writing a trapezoid integrator or Simpson's rule integrator without
> using sorted (x, y) pairs, sorted on x. Algorithms for numerical
> integration, differentiation, fast-Fourier and other types of transforms
> are a few of the cases where sorting is essential. Sorting is not just
> for user-convenient output.
>

Well, yes.. but practically you get your numeric data already sorted
eg as signal (sorted) over time. I can't remember ever having to sort
such data, only having to preprocess it (fill in gaps, Butterworth smoothing etc)

On 3/18/22 11:35, minf...@arcor.de wrote:
> Krishna Myneni schrieb am Freitag, 18. März 2022 um 17:26:26 UTC+1:
....
>> Try writing a trapezoid integrator or Simpson's rule integrator without
>> using sorted (x, y) pairs, sorted on x. Algorithms for numerical
>> integration, differentiation, fast-Fourier and other types of transforms
>> are a few of the cases where sorting is essential. Sorting is not just
>> for user-convenient output.
>>
>
> Well, yes.. but practically you get your numeric data already sorted
> eg as signal (sorted) over time. I can't remember ever having to sort
> such data, only having to preprocess it (fill in gaps, Butterworth smoothing etc)

Not always. It is normal in some instances to collect data for which the
independent variable (x) is not sorted, e.g. a drifting parameter which
covers the region of interest. I have collected data in this mode when
it is less noisy than controlling the independent variable, or when the
drift is slow enough to provide finer resolution in x than my minimum
control step size.

--
Krishna

Krishna Myneni schrieb am Freitag, 18. März 2022 um 17:46:39 UTC+1:
> On 3/18/22 11:35, minf...@arcor.de wrote:
> > Krishna Myneni schrieb am Freitag, 18. März 2022 um 17:26:26 UTC+1:
> ...
> >> Try writing a trapezoid integrator or Simpson's rule integrator without
> >> using sorted (x, y) pairs, sorted on x. Algorithms for numerical
> >> integration, differentiation, fast-Fourier and other types of transforms
> >> are a few of the cases where sorting is essential. Sorting is not just
> >> for user-convenient output.
> >>
> >
> > Well, yes.. but practically you get your numeric data already sorted
> > eg as signal (sorted) over time. I can't remember ever having to sort
> > such data, only having to preprocess it (fill in gaps, Butterworth smoothing etc)
> Not always. It is normal in some instances to collect data for which the
> independent variable (x) is not sorted, e.g. a drifting parameter which
> covers the region of interest. I have collected data in this mode when
> it is less noisy than controlling the independent variable, or when the
> drift is slow enough to provide finer resolution in x than my minimum
> control step size.
>

IIUC we call this resampling, but 100% okay, real world tasks determine
their own solution paths. Physics and related engineering software are only
mathematical models after all.

On 3/18/22 14:39, minf...@arcor.de wrote:
> Krishna Myneni schrieb am Freitag, 18. März 2022 um 17:46:39 UTC+1:
>> On 3/18/22 11:35, minf...@arcor.de wrote:
>>> Krishna Myneni schrieb am Freitag, 18. März 2022 um 17:26:26 UTC+1:
>> ...
>>>> Try writing a trapezoid integrator or Simpson's rule integrator without
>>>> using sorted (x, y) pairs, sorted on x. Algorithms for numerical
>>>> integration, differentiation, fast-Fourier and other types of transforms
>>>> are a few of the cases where sorting is essential. Sorting is not just
>>>> for user-convenient output.
>>>>
>>>
>>> Well, yes.. but practically you get your numeric data already sorted
>>> eg as signal (sorted) over time. I can't remember ever having to sort
>>> such data, only having to preprocess it (fill in gaps, Butterworth smoothing etc)
>> Not always. It is normal in some instances to collect data for which the
>> independent variable (x) is not sorted, e.g. a drifting parameter which
>> covers the region of interest. I have collected data in this mode when
>> it is less noisy than controlling the independent variable, or when the
>> drift is slow enough to provide finer resolution in x than my minimum
>> control step size.
>>
>
> IIUC we call this resampling, but 100% okay, real world tasks determine
> their own solution paths. Physics and related engineering software are only
> mathematical models after all.

Here's a loadable Forth module which performs exactly the type of
sorting I'm talking about within the graphical program XYPLOT-32:

https://github.com/mynenik/XYPLOT-32/blob/master/modules/xysort.4th

It's based on single array sort from the Forth Scientific Library.

--
Krishna

On Friday, March 18, 2022 at 7:17:28 AM UTC+1, Ron AARON wrote:
> On 18/03/2022 8:13, Paul Rubin wrote:
> > Ron AARON <c...@8th-dev.com> writes:
> >> Are there any (serious) languages which don't optimize tail calls by
> >> default?
> >
> > Forth? :)
> You might be joking, but Reva and 8th both did that optimization, and
> I'm pretty sure others do as well. It's almost a no-brainer.
Tail call optimization was the start of 4tH's peephole optimizer,
So it has been part of that one for at least a decade..

Hans Bezemer

On 19/03/2022 1:25, Hans Bezemer wrote:
> On Friday, March 18, 2022 at 7:17:28 AM UTC+1, Ron AARON wrote:
>> On 18/03/2022 8:13, Paul Rubin wrote:
>>> Ron AARON <c...@8th-dev.com> writes:
>>>> Are there any (serious) languages which don't optimize tail calls by
>>>> default?
>>>
>>> Forth? :)
>> You might be joking, but Reva and 8th both did that optimization, and
>> I'm pretty sure others do as well. It's almost a no-brainer.
> Tail call optimization was the start of 4tH's peephole optimizer,
> So it has been part of that one for at least a decade..

To be quite honest, I'm not sure why it wouldn't always be turned-on. It
really is a 'no-brainer'. But... well, apparently people disagree.

Ron AARON <clf@8th-dev.com> writes:
> To be quite honest, I'm not sure why it wouldn't always be
> turned-on. It really is a 'no-brainer'. But... well, apparently people
> disagree.

In imperative languages like Forth and descendants, it's usually easy
enough to write tail recursive functions as loops. If you instead write
them with tail recursion, you're relying on an optimization to be
present in the compiler even though the language spec doesn't require
it. So your program becomes less portable without a very compelling
reason. This is even true for Common Lisp, where most serious
implementations do implement TRO, and recursion comes naturally to
users.

Some languages and dialects such as Scheme require TRO in the language
spec, and favor a style that uses TR instead of loops, so using TR in
your programs is then a good thing, or in some cases (Haskell) a
necessary thing.

Paul Rubin <no.email@nospam.invalid> writes:
>In imperative languages like Forth and descendants, it's usually easy
>enough to write tail recursive functions as loops. If you instead write
>them with tail recursion

It's not about tail recursion, it's about tail-calls. In a call-heavy
language like Forth, that makes quite a bit of a difference. Looking
at <https://www.complang.tuwien.ac.at/forth/peep/sorted>, the sequence
";s ;s" (two returns in the dynamic sequence without other intervening
primitives) has rank 13 (not counting NEXT); eliminating that with
tail call optimization could have reduced the executed NEXTs by 2.65%;
plus, a branch is cheaper than a call.

The downside, of course, is that backtraces no longer contain all the
calls.

- 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 2021: https://euro.theforth.net/2021

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> It's not about tail recursion, it's about tail-calls. In a call-heavy
> language like Forth, that makes quite a bit of a difference.

Aha, good point. Does gforth get rid of those? I tested and it doesn't
eliminate tail recursion, but maybe that is different.

> The downside, of course, is that backtraces no longer contain all the
> calls.

Perhaps it is appropriate for gforth-fast but not the other variants. I
do like good backtraces.

Paul Rubin <no.email@nospam.invalid> writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>> It's not about tail recursion, it's about tail-calls. In a call-heavy
>> language like Forth, that makes quite a bit of a difference.
>
>Aha, good point. Does gforth get rid of those?

No.

>I tested and it doesn't
>eliminate tail recursion, but maybe that is different.

If it could optimize tail calls, it could also optimize tail recursion.

>> The downside, of course, is that backtraces no longer contain all the
>> calls.
>
>Perhaps it is appropriate for gforth-fast but not the other variants.

Yes, but that's not the reason why Gforth does not have it. It's just
not that easy to implement in combination with the other things that
Gforth does. Thinking of it, it's not that hard, either.

- 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 2021: https://euro.theforth.net/2021

On Saturday, March 19, 2022 at 5:57:08 PM UTC-4, Anton Ertl wrote:

> >Perhaps it is appropriate for gforth-fast but not the other variants.
> Yes, but that's not the reason why Gforth does not have it. It's just
> not that easy to implement in combination with the other things that
> Gforth does. Thinking of it, it's not that hard, either.
> - anton
> --

I have tail-call removal in a machine Forth compiler that I made
and I was really amazed at how simple it was and how much it
improved program size and speed.

H: -; ( -- )
THERE CELL- @ ( addr ) \ entry address of sub-routine
2 CELLS + ( addr' ) \ move past the sub-routine entry instructions
2 CELLS NEGATE TALLOT \ erase: addr @@ BL,
( addr') @@ B, \ compile a branch to the NEW sub-routine
;H

It's not clear to me how it would be done in an ITC implementation.

Perhaps you have to compile a replacement for DOCOL inline and
compile the BODY of the word right after?

Brian Fox <brian.fox@brianfox.ca> writes:
>It's not clear to me how it would be done in an ITC implementation.

Does not look that hard to me. E.g., you could remember where you
last ","ed the CFA of a word. When in ";", if that address is the
preceeding cell, and the code address in the code field is docol
(i.e., the preceeding word is a colon definition), change that word to
BRANCH, and "," the PFA of that word; otherwise just "," the CFA of
";s".

In Gforth it would be more complex, because there is some native code
compiled along with the threaded code. I think the way to go would be
to delay passing along a call to the later stages of compilation. If
the next thing to compile is a ";s", generate a branch, otherwise
generate a call followed by whatever is behind it.

- 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 2021: https://euro.theforth.net/2021