anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:

> Ron AARON <clf@8th-dev.com> writes:
>>On 17/03/2022 7:30, Paul Rubin wrote:
>>> 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). The immutable equivalent of arrays is
>>> balanced trees, which are way more complicated to implement.
>>
>>I don't understand this. Arrays are just as immutable as balanced trees.
>>Or, rather, just as mutable. Either can be modified.
>
> His point is: If you have a language that does not support changing
> existing data structures, you program by creating a new item that
> represents the new state. In case of an array this means copying all
> the data that is not changed. In the case of a tree this means
> copying only the unchanged data in changed nodes and their ancestor
> nodes. For large data structures, this is much more efficient.
> Therefore, functional programs use trees instead of arrays.

There are implementations of functional arrays that do not require
copying all of the data that is not changed on each update. To
implement the "update" operation, you build and return a "view" of the
original array which implements the "update" and "lookup" operations so
that a view can be used wherever an array can itself be used. The view
contains a map of {index, value} representing changed values, as well as
a reference to the original array. The "lookup" operation on a view
first checks the map, then the underlying array. The "update" operation
on the view returns a new view with a modified map and reference to the
same array. It is straight forward to implement various policies which
will perform a full array copy when the number of elements in the map
reaches some threshold, whether it be a fixed number of items, or a
percentage of the size of the underlying array. In this way the cost of
copies can be amoritized.

-russ

russell...@yahoo.com schrieb am Donnerstag, 31. März 2022 um 21:24:58 UTC+2:
> an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>
> > Ron AARON <c...@8th-dev.com> writes:
> >>On 17/03/2022 7:30, Paul Rubin wrote:
> >>> 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). The immutable equivalent of arrays is
> >>> balanced trees, which are way more complicated to implement.
> >>
> >>I don't understand this. Arrays are just as immutable as balanced trees..
> >>Or, rather, just as mutable. Either can be modified.
> >
> > His point is: If you have a language that does not support changing
> > existing data structures, you program by creating a new item that
> > represents the new state. In case of an array this means copying all
> > the data that is not changed. In the case of a tree this means
> > copying only the unchanged data in changed nodes and their ancestor
> > nodes. For large data structures, this is much more efficient.
> > Therefore, functional programs use trees instead of arrays.
>
> There are implementations of functional arrays that do not require
> copying all of the data that is not changed on each update. To
> implement the "update" operation, you build and return a "view" of the
> original array which implements the "update" and "lookup" operations so
> that a view can be used wherever an array can itself be used. The view
> contains a map of {index, value} representing changed values, as well as
> a reference to the original array. The "lookup" operation on a view
> first checks the map, then the underlying array. The "update" operation
> on the view returns a new view with a modified map and reference to the
> same array. It is straight forward to implement various policies which
> will perform a full array copy when the number of elements in the map
> reaches some threshold, whether it be a fixed number of items, or a
> percentage of the size of the underlying array. In this way the cost of
> copies can be amoritized.
Thanks for the clarification. Given the typical amount of views and/or slices even
in moderate NumPy or Matlab code, I assume that garbage collection can become
rather complex.

Given the typical compactness of Forth, automatic garbage collection would
mean overkill. OTOH dynamically allocated/resized/freed maps and arrays are no
rocket science, but unfortunately with everybody's homebrewed syntax.

On Sunday, March 20, 2022 at 11:16:58 PM UTC+1, Anton Ertl wrote:
> 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.
I can't look in anyones implementation, but I CAN give a few hints how 4tH pulled it of:
(1) There is a FENCE (not to be confused with Forth-79 FENCE), which determines the point where
no more optimization is allowed. E.g. in this case:

15 BEGIN 10+ (..) REPEAT

4tH's peephole optimizer would be triggered to do constant folding (since BEGIN compiles to nothing).
By letting BEGIN move the FENCE to "15" it will NOT be considered for ANY optimization.
The same goes for THEN, so:

: dummy IF this ELSE that THEN ;

Will not result in a BRANCH at the very end (because "that" is called), but still trigger an EXIT. Of course,

: dummy IF this EXIT THEN that ;

Will result in much tighter code (since both "this" and "that" can be tail optimized). For that reason 4tH
supports ;THEN (which should be considered "syntactical sugar"):

: dummy IF this ;THEN that ;

(2) Disabling the optimizer - but this is RARE (and mostly manual). It is also very temporary, because the
compiler will reenable it after compiling the next instruction (unoptimized).

Hans Bezemer

russell_mcmanus@yahoo.com writes:
>There are implementations of functional arrays that do not require
>copying all of the data that is not changed on each update. To
>implement the "update" operation, you build and return a "view" of the
>original array which implements the "update" and "lookup" operations so
>that a view can be used wherever an array can itself be used. The view
>contains a map of {index, value} representing changed values, as well as
>a reference to the original array. The "lookup" operation on a view
>first checks the map, then the underlying array. The "update" operation
>on the view returns a new view with a modified map and reference to the
>same array. It is straight forward to implement various policies which
>will perform a full array copy when the number of elements in the map
>reaches some threshold, whether it be a fixed number of items, or a
>percentage of the size of the underlying array. In this way the cost of
>copies can be amoritized.

How is the map implemented?

Most likely with some trie or search tree, i.e., the same you would
use if you did not have the flat array, only with only a part of the
members. You would probably use the balance of reads vs. updates to
decide when to consolidate the updates into a new flat array: with
mostly updates, the flat array does not pay off, whereas with very
rare upates, it may pay off to consolidate on a flat array after only
a few of them.

Another approach is known as "linear logic": If you know that the
original array is no longer alive after the update, you can update the
flat array directly.

- 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

"minf...@arcor.de" <minforth@arcor.de> writes:
>Thanks for the clarification. Given the typical amount of views and/or slic=
>es even
>in moderate NumPy or Matlab code, I assume that garbage collection can bec=
>ome
>rather complex.

Garbage collection typically does not care about the actual complexity
of the data structures, and a stop-the-world garbage collector for
single-threaded programs is not particularly complex. Things that
make it complex are simultaneous multiprocessing (SMP) and (soft)
real-time requirements.

- 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

Hans Bezemer <the.beez.speaks@gmail.com> writes:
>The same goes for THEN, so:
>
>: dummy IF this ELSE that THEN ;
>
>Will not result in a BRANCH at the very end (because "that" is called), but still trigger an EXIT.

Note that in this example the calls to THIS and THAT are tail-calls
and can be tail-call optimized by a sufficiently sophisticated
compiler. However, I recently did some measurements that showed that
the dynamic sequence

call branch ;s

(e.g., for the THIS tail-call in the example above) is relatively rare
rare, so it does not pay to go to great lengths to optimize such
cases. But optimizing the THAT call into a branch would be fine (you
just cannot leave the ;S/EXIT after the THEN away).

- 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:
> Another approach is known as "linear logic": If you know that the
> original array is no longer alive after the update, you can update the
> flat array directly.

It's enough to just analyze the data flow for that. That's how STRef
and mutable arrays in Haskell work: they have special datatypes that
ensure that the mutable values are never used in two different places.
If the program tries to do otherwise, the type checker complains.

On Saturday, April 2, 2022 at 7:47:51 PM UTC+2, Anton Ertl wrote:
> Hans Bezemer <the.bee...@gmail.com> writes:
> Note that in this example the calls to THIS and THAT are tail-calls
> and can be tail-call optimized by a sufficiently sophisticated
> compiler.

I stand corrected by both you AND my compiler! The EXIT is required for the
IF part of the conditional - but not the ELSE part. And that's what 4tH does:

: this ; : that ;
: bla 0 if this else that then ;

4tH message: No errors at word 11
Object size: 11 words
String size: 0 chars
Variables : 0 cells
Strings : 0 chars
Symbols : 0 names
Reliable : Yes

Addr| Opcode Operand Argument

0| branch 2
1| exit 0
2| branch 4
3| exit 0
4| branch 11
5| literal 0
6| 0branch 8
7| call 1
8| branch 10
9| branch 3
10| exit 0

BTW, I edited the BRANCH addresses for those unfamiliar with 4tH.

Hans Bezemer

Paul Rubin <no.email@nospam.invalid> writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>> Another approach is known as "linear logic": If you know that the
>> original array is no longer alive after the update, you can update the
>> flat array directly.
>
>It's enough to just analyze the data flow for that. That's how STRef
>and mutable arrays in Haskell work: they have special datatypes that
>ensure that the mutable values are never used in two different places.
>If the program tries to do otherwise, the type checker complains.

Well, of course Haskell uses its type checker to achieve this.

How would a Forth solution look like? Here's my take: Have a stack of
arrays (or, more generally, objects), and, e.g., array variables. An
array variable fetch pushes the array from the value to the array
stack, and zeros the array variable (unlike an ordinary variable
fetch). An array variable write deallocates the array currently in
the variable (if it is non-zero), and stores the array reference
there. There is no ADUP for the array stack, or if there is, it
creates a new copy. Likewise, all other array operations (e.g.,
updates of an element) are designed such that the reference to the
array is not copied.

My vector words <http://www.euroforth.org/ef17/papers/ertl.pdf> have
value semantics, which requires an implementation along the lines
outlined above. It does not follow a strict linear logic approach,
but there is, e.g., v@', which is the variant of v@ that zeros the
variable. As an alternative to copying on vdup (called "linear" in
the paper), there is also the possibility to use reference counting
(and copy on write).

- 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