Are re-entrant functions not such a big deal?
CuppoJava
I've started reading through more and more Forth code, and noticed
heavy use of variables and values to factor functions. I admit that
this sometimes results in really elegant code, but I'm worried about
none of these functions being properly re-entrant.
Is the lack of re-entrant functions not such a big deal for Forth
programs? Don't you run into hard-to-find bugs if some user calls your
functions in the wrong order?
Thanks
-Patrick
Hugh Aguilar
Reentrancy is important in any language. The use of global variables
and values is not elegant; it is bad Forth. This was most likely being
done by people who did not have local variables available in their
Forth system. Also, the LOCALS| that we get with ANS-Forth is screwed
up; it has all the names backwards. This largely prevented me from
using locals for a long time. Then I wrote the { function that is in
my novice package
(http://www.forth.org/novice.html) and after that I started to use
locals more.
I'm guilty of using globals occasionally too. My <CSTR pad is global,
and it is not reentrant. This is something that I should fix one of
these days. Also, If you look in my list.4th file you will see that
FIND-PRIOR uses a global variable. It is somewhat unlikely that
anybody would call FIND-PRIOR for one list and, in the toucher, call
FIND-PRIOR for another list. If this happened though, the result would
be chaos. This point was brought up recently:
http://groups.google.com/group/comp.lang.forth/browse_thread/thread/907f253d229d5b7d/a3cb4b69440ef3c3
Just last night I fixed the problem:
macro: rdrop ( -- ) \ r: a --
r> drop ;
macro: 2rdrop ( -- ) \ r: a b --
rdrop rdrop ;
macro: rr@ ( -- a ) \ r: a b -- a b
2r@ drop ;
: each ( i*x head toucher -- j*x )
\ toucher: i*x node -- j*x
>r
begin ?dup while
r@ over .fore @ >r
execute r> repeat
rdrop ;
: find-node ( i*x head toucher -- j*x node|false )
\ toucher: i*x node -- j*x flag
>r
begin dup while
r@ over .fore @ >r over >r
execute if r> 2rdrop exit then
rdrop r> repeat
rdrop ;
FIND-NODE is like EACH except that it stops when the toucher returns
true, and it either returns the found node or false
: find-prior ( i*x head toucher -- j*x node|false )
\ toucher: i*x node -- j*x flag
>r -1 >r
begin dup while
rr@ over .fore @ >r over >r
execute if 2rdrop r> rdrop exit then
2r> rdrop >r repeat
2rdrop ;
FIND-PRIOR is like FIND-NODE except that it returns the node prior to
the found node, or -1 if the found node was the head --- or false if
no node was found.
The above functions are pretty hard to read (write too!) due to heavy
use of the return stack. The following are versions that use local
variables. These are easier to read, but are slower executing:
: each ( i*x head toucher -- j*x )
{ toucher | next -- }
begin ?dup while
dup .fore @ to next
toucher execute
next repeat ;
: find-node ( i*x head toucher -- j*x node|false )
{ node toucher | next -- node|false }
begin node while
node .fore @ to next
node toucher execute if node exit then
next to node repeat
false ;
: find-prior ( i*x head toucher -- j*x node|false )
-1 { node toucher prior | next -- prior|false }
begin node while
node .fore @ to next
node toucher execute if prior exit then
node to prior next to node repeat
false ;
BruceMcF
> Hi everyone,
>
> I've started reading through more and more Forth code, and noticed
> heavy use of variables and values to factor functions. I admit that
> this sometimes results in really elegant code, but I'm worried about
> none of these functions being properly re-entrant.
> Is the lack of re-entrant functions not such a big deal for Forth
> programs?
Its sometimes more the Forth tendency do things explicitly, and solve
the problem at hand and build up from there.
... X @ >R Word-over-writing-X R> X ! ...
Alex McDonald
For single-threaded code, or where careful programming or locking is
employed, it's not a problem; some Forths provides USER variables too,
which are per-task.
Paul Rubin
> For single-threaded code, or where careful programming or locking is
> employed, it's not a problem; some Forths provides USER variables too,
> which are per-task.
Single-threaded code might still involve recursion.
John Passaniti
> programs? Don't you run into hard-to-find bugs if some user calls your
> functions in the wrong order?
There are basically two camps on the issue. The first says that all
code should be reenterant because you can never know how those
functions may be used by someone else. The second says that it's
better to worry about reenterancy when it becomes an issue and not
needlessly complicate things until it's needed. Both camps are of
course simultaneously right and wrong. The Forth answer is to do what
makes sense for the application.
I guess it largely depends on the kind of work you do. If you're
working on smaller embedded systems, and if you're primarily a "lone
wolf" programmer, then you probably value the efficiency of globals
and you aren't worried about other programmers calling your words
incorrectly, since it's just you. But if you're working on larger
systems with more than just yourself, then concerns about reenterancy
start to matter more, and you're going to move to a style where there
is less of a need to have an intimate awareness of if the words you
call are reenterant.
Jerry Avins
I used an embedded Forth whose multiply routine wasn't reentrant, so I
couldn't use it in an interrupt routine. I was able to use the machine's
native unsigned multiply, so I wrote a CODE word to do that. There would
have been a strange bug had I not thought to check.
Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Andrew Haley
Those Forths that support concurrency generally have USER variables,
where every task gets its own copy. Passing state between words with
global variables is often considered to be bad style, but some people
do it.
Having said all that, there's no harm in global state if only a single
thread touches it.
Andrew.
Hugh Aguilar
wrote:
Writing non-reentrant code is *always* a bad idea. This is not just an
issue in concurrent systems.
Consider my <CSTR in my novice package which uses a pad that is
defined globally. There is a huge potential for bugs here. Consider
this code:
<cstr c" hello" +cstr my-str +cstr c" world" +cstr cstr>
This concatenates three strings:
"hello"
whatever string the MY-STR function returns
"world"
What happens if MY-STR uses <CSTR ... CSTR> internally? Chaos!
As another example we have my old FIND-PRIOR that used a global
variable. The argument given to FIND-PRIOR is an xt of a function with
this stack picture:
node --
What happens if that function (what I call a toucher) accesses
*another* list internally using FIND-PRIOR? Chaos!
Note that none of this has anything to do with concurrent programming.
It is really a bad idea to tell Patrick: "there's no harm in global
state if only a single thread touches it." Just because Patrick is new
to Forth doesn't mean that he is new to computer programming. In all
likelihood he is aware of basic programming concepts such as I have
described above. There are a lot of C programmers around who will tell
you that they tried Forth and were unimpressed and gave up on it. It
is because they encountered Forth programmers who didn't really know
anything about computer programming. Now those C programmers will
*never* consider Forth again. The same thing could happen with
Patrick. We have got to be more careful about spouting foolishness on
comp.lang.forth --- Forth's reputation will eventually be completely
ruined and Forth will become a haven for the incompetent.
Hugh Aguilar
> The argument given to FIND-PRIOR is an xt of a function with
> this stack picture:
> node --
The stack picture for FIND-PRIOR's toucher is actually:
node -- flag
John Passaniti
> Writing non-reentrant code is *always* a bad idea. This is not just an
> issue in concurrent systems.
Spoken as someone who would rather following a set of rules than
consider the unique context of a specific system. I guess if one
wants to shut off their brain and mindlessly write code in some
canonical style, then your advice holds. Forth's primary problem
domain has always been in embedded systems-- systems that by
definition are often purpose-built and have unique design challenges.
The enemy of such work is cookie-cutter programming and mindlessly
following rules.
I agree that *often* writing non-reenterant code is a bad idea.
Certainly, it's easy to point to lots of cases where it will cause
systems to fail in stunning ways. But that's no excuse for an anti-
intellectual approach to solving problems which relies on following
rules rather than asking if those rules make sense.
Jerry Avins
I replied earlier in this thread about an embedded system where not
recognizing the need for reentrancy would have been a severe error. Even
there, the special-purpose multiply written for the interrupt routine as
a work-around bought me precious time. Your words reminded me of what a
supervisor and mentor once said: "I would rather make decisions than
make policy".
Jerry
--
Engineering is the art of making what you want from things you can get.
ŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻ
Alex McDonald
Some of Hugh's code might be improved by it; for instance, his node
traversal routines.
BruceMcF
But where the recursion takes place, it is straightforward to make the
code re-entrant at that point.
Albert van der Horst
Alex McDonald <bl...@rivadpm.com> wrote:
>On 9 July, 20:34, CuppoJava <patrickli_2...@hotmail.com> wrote:
>> Hi everyone,
>>
>> I've started reading through more and more Forth code, and noticed
>> heavy use of variables and values to factor functions. I admit that
>> this sometimes results in really elegant code, but I'm worried about
>> none of these functions being properly re-entrant.
>>
>> Is the lack of re-entrant functions not such a big deal for Forth
>> programs? Don't you run into hard-to-find bugs if some user calls your
>> functions in the wrong order?
>>
>> Thanks
>
>For single-threaded code, or where careful programming or locking is
>employed, it's not a problem; some Forths provides USER variables too,
>which are per-task.
Reentrant code is overrated. I for me I'm certainly not being dogmatic
about it.
1. Sometimes you do want global variables. I had a bug once
created by a lisper. He had a counter for errors, and with
each recursive call he set the counter to 0. Causing endless
loops.
2. You can't have reentrant code in parallel processes anyway,
i.e. a transputer process can't be called recursively. The best
you can do is create processes concurrently.
3. Reentrant code makes sense in libraries, but beware!
A typical situation (and one bug I had because code was not
reentrant) was using an output port of a Z80 by a c-routine.
That code was 8080 based, and generated a piece of code for
the exact port in a global data area. Making that
code reentrant solved the problem.
This code manifested itself in interrupts. (I got one more of
these situations. 1]
Bottom line: the abundance of reentrant code in libraries lulls
everybody in carelessness in this respect. So having more of
non-reentrant code and the need to take care could actually be more
productive. With all the things we need to take care of in Forth, I
don't think it is a big deal. I myself are certainly not going over
the top to create reentrancy. It also comes at a price. In early
FORTRAN you had to tell the compiler to allow recursion, because it
had to generate slower code, a big deal at the time.
1] These two bugs compare unfavorable to "normal" bugs I had.
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
Andrew Haley <andr...@littlepinkcloud.invalid> wrote:
>CuppoJava <patrick...@hotmail.com> wrote:
>> Hi everyone,
>>
>> I've started reading through more and more Forth code, and noticed
>> heavy use of variables and values to factor functions. I admit that
>> this sometimes results in really elegant code, but I'm worried about
>> none of these functions being properly re-entrant.
>>
>> Is the lack of re-entrant functions not such a big deal for Forth
>> programs? Don't you run into hard-to-find bugs if some user calls your
>> functions in the wrong order?
>
>Those Forths that support concurrency generally have USER variables,
>where every task gets its own copy. Passing state between words with
>global variables is often considered to be bad style, but some people
>do it.
That is the definition of object orientation. In Python you always
pass a this pointer. In C++ it is implicit. Most Forth OO requires
you to pass an object pointer. My class/endclass has a ``current
object'' which is global state, like C++ damned convenient (and
probably political incorrect.)
Some call it data hiding and consider it good style.
My 1979 FORTRAN program NSEAF contains a bunch of named COMMON's,
by some considered an abomination. But in fact they were a database
of objects of sorts, making the best of what was available in the
language. If I wanted to calculate the pressure drop over a pipeline,
I passed two numbers, indices into an array of pipe-piece objects
and identifying a subtree of the network. This kind of thing is
only bad if the architecture behind it is unsound.
>
>Having said all that, there's no harm in global state if only a single
>thread touches it.
OO puts a fence around the global state, then makes it local, and
allows you to have duplicates. Go as far along this path as you
need to. Being a Forther you don't want to go farther than you need
to.
>
>Andrew.
Elizabeth D Rather
Except that one of the major functions of global variables is to
communicate state data between tasks. Harkening back to telescope
control, an Operator task sets wanted positions; a Tracking task moves
the telescope to follow the wanted position and records actual
positions; a Sampling task records data at a specified interval, and may
not record samples if the difference between wanted and actual positions
is too great; and a Monitor task displays the real-time state of both
the tracking and sampling activities. All this info *has* to be kept in
global variables; that's what they're primarily designed for.
The essential issue is system design: what tasks read or write which
variables under what circumstances, and which variables should have
per-task copies and which should not.
Global variables are used to maintain state of a shared device, too,
such as a single graphics screen. Again, the overall system design
needs to set and maintain rules of usage.
That said, there's also no harm in using technically global variables in
a local set of words, providing that you understand what the rules of
usage are. You may, for example, have a SIZE variable in several
different parts of the application, with no overlap or conflict whatever.
Cheers,
Elizabeth
--
==================================================
Elizabeth D. Rather (US & Canada) 800-55-FORTH
FORTH Inc. +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com
"Forth-based products and Services for real-time
applications since 1973."
==================================================
John Passaniti
wrote:
> That is the definition of object orientation.
Ummm, no. It's a common implementation strategy for object-oriented
systems-- especially class-based object oriented systems. But you can
certainly do object orientation without a "self" pointer. Think about
what "self" actually is-- it's a pointer to a context; it isn't the
context itself. There are other ways to provide context. Closures
capture context, and they can be used to implement object-oriented
systems.
Incidentally, there seems to be a rash these days of people stepping
up before software engineering conferences and offering statements
that few people are actually doing object orientation right, and that
the key to object orientation has been slowly lost over the years.
Alan Kay famously wrote a decade-ish ago that the most fundamental
idea in object orientation isn't encapsulation, inheritance, or
polymorphism-- it's messaging. Those other things are fine and good
and often helpful, but if you strip it all down, object orientation is
about messaging. And by that he (mostly) means flexible, dynamic
dispatch systems. These days, in the interest of efficiency most
object orientated programming languages (and in the case of Forth, add
on libraries) try to do their best to statically bind. And when they
can't, they'll usually adopt some sort of class-based model with some
notion of tables of virtual functions. In most such systems, the
"message" is literally and semantically a function call, possibly with
a tiny bit of indirection. His vision is more along the lines of a
message being something that you could possibly not be able to respond
to, like with the Smalltalk "doesNotUnderstand" response from an
object that can't handle a message. And there is something to be said
for this view-- classes are unnecessarily limiting and don't neatly
reflect the real world, especially with single-inheritance systems.
It's why for years whenever the subject of object orientation comes up
in comp.lang.forth and there are the usual arguments over syntax and
how to make it as insanely fast as possible, I usually offer that
there are other ways to think about objects that are more flexible and
better able to model the real world. And shortly after that, everyone
goes back to arguments over syntax and speed.
A growing trend these days is to move away from static type systems
and class-based object orientation and embrace more dynamic systems.
This is related to the notion of roles-- that objects can freely take
on different roles in a system. For example, I might have a traffic
simulation that models vehicles. In a traditional class-based system,
I would design a hierarchy that had methods that described a vehicle.
So from some base class representing a vehicle, I might derive cars
and trucks and motorcycles-- these are all vehicles that share
attributes (they have tires, they have engines, etc.). But if I want
to model bicycles in this simulation? They don't have an engine (the
human doesn't count), so in order to handle bicycles, you might have
to juggle the classes around so that bicycles don't inherit engines.
Maybe that's easy or maybe it's hard, depending on how you set up the
classes. Now what if I want to model skateboards and hovercraft and
shoes with springs in them. These could all be considered vehicles,
but how they relate to classes may not be easy to model. So instead,
the prototype-based object world (and the dynamic message-oriented
world of Alan Kay) avoids the issue of class by instead makes the
object respond to a set of vehicle-oriented messages. As long as the
object knows how to respond to those messages, it can participate as a
vehicle in the simulation.
Right now, you see this notion of role being modeled in languages like
Java and C# using interfaces. In more dynamic languages like Ruby and
Python and JavaScript and Lua, you would add appropriate methods to
the dictionary that represented an object. And this effectively gives
you an "isa" relationship to a role without classes, giving you
flexibility to have more fine-grained models.
Andrew Haley
> On Jul 10, 2:28?am, Andrew Haley <andre...@littlepinkcloud.invalid>
> wrote:
>> CuppoJava <patrickli_2...@hotmail.com> wrote:
>> > Hi everyone,
>>
>> > I've started reading through more and more Forth code, and noticed
>> > heavy use of variables and values to factor functions. I admit that
>> > this sometimes results in really elegant code, but I'm worried about
>> > none of these functions being properly re-entrant.
>>
>> > Is the lack of re-entrant functions not such a big deal for Forth
>> > programs? Don't you run into hard-to-find bugs if some user calls your
>> > functions in the wrong order?
>>
>> Those Forths that support concurrency generally have USER variables,
>> global variables is often considered to be bad style, but some people
>> do it.
>>
>> Having said all that, there's no harm in global state if only a single
>> thread touches it.
>
> issue in concurrent systems.
>
> Consider my <CSTR in my novice package which uses a pad that is
> defined globally. There is a huge potential for bugs here. Consider
> this code:
>
> <cstr c" hello" +cstr my-str +cstr c" world" +cstr cstr>
>
> This concatenates three strings:
> "hello"
> whatever string the MY-STR function returns
> "world"
>
> What happens if MY-STR uses <CSTR ... CSTR> internally? Chaos!
>
> As another example we have my old FIND-PRIOR that used a global
> variable. The argument given to FIND-PRIOR is an xt of a function with
> this stack picture:
> node --
>
> What happens if that function (what I call a toucher) accesses
> *another* list internally using FIND-PRIOR? Chaos!
> Note that none of this has anything to do with concurrent programming.
Re-entrancy is a red herring here. A re-entrant routine is one that
can be started while another activation of the same routine is still
running. (Hence the name.) This can only happen with concurrent
activation or recursion. Clearly the <cstr words have a bug, which is
that they use share data in a statically-allocated buffer.
Andrew.
Hugh Aguilar
wrote:
Its not a bug when its intentional!
Hugh Aguilar
When you say "improved by it," do you mean by recursion or by the use
of global variables?
I'm in the process right now of rewriting most of the code in list.4th
for improved speed. I rewrote INSERT-ORDERED last night to get rid of
all those locals and just use the stack, and I've already rewritten
EACH, FIND-NODE and FIND-PRIOR as posted elsewhere. If you have a
improved version of anything in list.4th, please feel free to post it
--- I'll use it if it is better than what I've got. I don't really
want to use globals though, as it is conceivable that one of the user-
written toucher functions that get passed in as an xt will access
another list --- so the list traversal functions have to be reentrant.
Doug Hoffman
> These days, in the interest of efficiency most
> object orientated programming languages (and in the case of Forth, add
> on libraries) try to do their best to statically bind.
If the compiler can simply determine the call, totally transparent to
the programmer, where is the harm of the (faster) static bind?
> His [ Kay's ] vision is more along the lines of a
> message being something that you could possibly not be able to respond
> to, like with the Smalltalk "doesNotUnderstand" response from an
> object that can't handle a message. And there is something to be said
> for this view-- classes are unnecessarily limiting and don't neatly
> reflect the real world, especially with single-inheritance systems.
The PowerMops (and Neon/Neon-like) object system is duck typed, like
Smalltalk. PowerMops even has a (very complete and robust) multiple
inheritance mechanism which Smalltalk doesn't have.
> It's why for years whenever the subject of object orientation comes up
> in comp.lang.forth and there are the usual arguments over syntax and
> how to make it as insanely fast as possible,
I agree that the syntax issue has been an unfortunate diversion. I
don't care about the issue of contention and would gladly do it either
way. Re: speed. Why would one take issue with faster execution as long
as the side effects, if any, are negligible?
> A growing trend these days is to move away from static type systems
I don't know of any "front runner" Forth object extensions that are
purely static, but perhaps that's not what you meant here.
Sounds interesting. I've no experience with prototype-based object
systems. Thank you for the explanation.
On the downside, that may make for one more significant decision to make
if there is ever to be a Forth objects standard. ;-)
-Doug
Roelf Toxopeus
Doug Hoffman <glid...@gmail.com> wrote:
Indeed a nice explanation.
Doug, you could try (if you're still able to run MacClassic): Kevo, the
PrototypebasedOO Forth system from the 1990's:
http://tunes.org/wiki/kevo.html
by Antero Taivalsaari. Now into JavaScript, for instance:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.133.4831
A little bit more info on protoetc. something like:
http://www.idt.mdh.se/kurser/cd5130/msl/2003lp4/reports/prototypebased.pd
f
-r
Alex McDonald
> On Jul 10, 4:21 pm, Alex McDonald <b...@rivadpm.com> wrote:
>
> > On 10 July, 02:19, Paul Rubin <no.em...@nospam.invalid> wrote:
>
> > > Alex McDonald <b...@rivadpm.com> writes:
> > > > For single-threaded code, or where careful programming or locking is
> > > > employed, it's not a problem; some Forths provides USER variables too,
> > > > which are per-task.
>
> > > Single-threaded code might still involve recursion.
>
> > Some of Hugh's code might be improved by it; for instance, his node
> > traversal routines.
>
> When you say "improved by it," do you mean by recursion or by the use
> of global variables?
Recursion.
Hugh Aguilar
I don't know how a linked list traversal could be improved by
recursion because there is no backtracking like in a tree. I would
expect that any use of recursion would be tail recursion, which just
turns into iteration anyway. Can you show me what you mean?
These are my major list traversal functions. If anything can get
improved, I'd like to see TAIL improved, because it is used in LINK
which very common. Every time I append a node onto the end of a list,
LINK has to call TAIL for the list.
: each ( i*x head 'toucher -- j*x )
\ toucher: i*x node -- j*x
>r
begin ?dup while \ --
node
r@ over .fore @ >r \ -- node
toucher
execute r> repeat \ --
next
rdrop ;
: find-node ( i*x head 'toucher -- j*x node|false )
\ toucher: i*x node -- j*x flag
>r
begin dup while \ -- node
r@ over .fore @ >r over >r \ -- node toucher
execute if r> 2rdrop exit then
rdrop r> repeat \ -- next
rdrop ;
: find-prior ( i*x head 'toucher -- j*x -1|node|false )
\ toucher: i*x node -- j*x flag
>r -1 >r \ prior is -1, meaning found node was the head
begin dup while \ -- node
rr@ over .fore @ >r over >r \ -- node toucher
execute if 2rdrop r> rdrop exit then
2r> rdrop >r repeat \ -- next
2rdrop ;
: length ( head -- count )
0 swap begin dup while
.fore @ swap 1+ swap repeat drop ;
: tail ( head -- node )
nil swap begin dup while
nip dup .fore @ repeat drop ;
: nth ( head n -- node )
begin dup while
over 0= if drop exit then
swap .fore @ swap 1- repeat drop ;
\ comparer: i*x new-node node -- j*x new-node ?
\ insert new-node prior to node?
: insert-ordered ( head 'comparer node -- new-head 'comparer )
init-list rover rover
find-prior
dup 0= if drop rot swap link swap exit then
dup -1 = if drop rot link swap exit then
insert ;
: sort-list ( head 'comparer -- new-head )
nil swap rot each[ insert-ordered ]each drop ;
w_a_x_man
> a tiny bit of indirection. His vision is more along the lines of a
> message being something that you could possibly not be able to respond
> to, like with the Smalltalk "doesNotUnderstand" response from an
> object that can't handle a message.
Ruby:
class String
def method_missing x
self + x.to_s
end
end
==>nil
"hello".foo_bar
==>"hellofoo_bar"
Hugh Aguilar
> : each ( i*x head 'toucher -- j*x )
> \ toucher: i*x node -- j*x
> >r
> begin ?dup while \ --
> node
> r@ over .fore @ >r \ -- node
> toucher
> execute r> repeat \ --
> next
> rdrop ;
Here's EACH without the wordwrap messing it up:
: each ( i*x head 'toucher -- j*x )
\ toucher: i*x node -- j*x
>r
begin ?dup while \ -- node
r@ over .fore @ >r \ -- node toucher
execute r> repeat \ -- next
rdrop ;
Maybe the reason why so little code ever gets posted is because of
this wordwrap problem. What possible point could there be in setting
the right margin at the halfway mark of the screen?
jacko
the list points to the tail, and the tail addresses the head. In this
way the tail can be found faster than the head. It does limit common
tails. :-(
Insert on the head and delete from head are still fast and append
becomes very fast on long lists.
The null item is detected by tail detection.
Cheers Jacko
Hugh Aguilar
That is a pretty interesting idea; I never heard of that before. If I
am understanding you, before each traversal (EACH, etc.) I would have
to fix the tail node so that its .FORE pointer is NIL, and after the
traversal unfix it again so that it points to the head. Considering
how long my lists are (in the slide-rule program), a little overhead
is worthwhile to speed up TAIL. The only problem I foresee is the case
(in the current system) where the pointer to the head of the list
actually points to a node in the middle, and there is an expectation
of the traversal functions (EACH etc.) traversing only the latter part
of the list. To the best of my recollection, I don't do this anywhere.
I would have to outlaw the practice, but I don't think that would be a
problem --- I can't think of any reason why anybody would want to do
this.
> It does limit common
> tails. :-(
Are you referring to the possibility of multiple lists having the same
tail? I had never thought of that before you mentioned it, and I'm
sure I don't do it anywhere. If I outlawed the practice, I doubt that
anybody would complain --- I can't think of any reason why anybody
would want to do this.
> The null item is detected by tail detection.
I don't know what you mean by this. An empty list would just be
represented by a NIL pointer, same as before.
I am definitely thinking about implementing your suggestion. This
algorithm is totally new to me; can you provide a link to a reference?
Thanks for your tip. This is actually a constructive criticism! :-)
Most of what I hear on c.l.f. is along the lines of: "Your binary tree
isn't any good because it isn't a hash table." Arguments like that are
just a hijacking of the thread. By comparison, you stayed on topic and
yet introduced a new idea. Good job!
Doug Hoffman
> Indeed a nice explanation.
>
> Doug, you could try (if you're still able to run MacClassic): Kevo, the
> PrototypebasedOO Forth system from the 1990's:
> http://tunes.org/wiki/kevo.html
Thanks Roelf. I'm not set up for MacClassic. But that's OK. John's
explanation was very good and I believe I get the idea about prototype
based objects.
Trying to think of a situation where using class-based caused a problem
that prototype-based would have solved. Not sure, have to think some
more about that.
I *can* recall many times wishing for multiple inheritance while using a
single inheritance system.
-Doug
Alex McDonald
You're in desperate need of a good text on data structures and
algorithms. Try here; http://www.itl.nist.gov/div897/sqg/dads/
Alex McDonald
> On Jul 13, 12:35 pm, Alex McDonald <b...@rivadpm.com> wrote:
>
>
>
> > On 12 July, 18:18, Hugh Aguilar <hughaguila...@yahoo.com> wrote:
>
> > > On Jul 10, 4:21 pm, Alex McDonald <b...@rivadpm.com> wrote:
>
> > > > On 10 July, 02:19, Paul Rubin <no.em...@nospam.invalid> wrote:
>
> > > > > Alex McDonald <b...@rivadpm.com> writes:
> > > > > > For single-threaded code, or where careful programming or locking is
> > > > > > employed, it's not a problem; some Forths provides USER variables too,
> > > > > > which are per-task.
>
> > > > > Single-threaded code might still involve recursion.
>
> > > > Some of Hugh's code might be improved by it; for instance, his node
> > > > traversal routines.
>
> > > When you say "improved by it," do you mean by recursion or by the use
> > > of global variables?
>
> > Recursion.
>
> I don't know how a linked list traversal could be improved by
> recursion because there is no backtracking like in a tree. I would
> expect that any use of recursion would be tail recursion, which just
> turns into iteration anyway. Can you show me what you mean?
>
> : find-prior ( i*x head 'toucher -- j*x -1|node|false )
> \ toucher: i*x node -- j*x flag
> >r -1 >r \ prior is -1, meaning found node was the head
> begin dup while \ -- node
> rr@ over .fore @ >r over >r \ -- node toucher
> execute if 2rdrop r> rdrop exit then
> 2r> rdrop >r repeat \ -- next
> 2rdrop ;
>
Consider your FIND-PRIOR word; it's using a backtrack of 1 by
returning the previous node.
By inspecting the next node with the "toucher" (that word is just so
wrong!), if it's NULL or you get back SUCCESS then the current node is
the desired node. If not, make next=current and recurse. Some of the
stack juggling gets hidden by the recursion, and it might be clearer.
Might; I'm not laying any great claims to recursion for this specific
example, but where the non-recursive solution is unclear or complex
due to handling lots of data, recursion and factoring may improve it.
Hugh Aguilar
In my LC53 encryption cracking program, I escaped from a recursive-
descent search when I found the seed, using a THROW to a CATCH that I
had set up prior to the call to the recursive function. With FIND-
PRIOR I would have to do something similar; I don't know of any other
way to escape, although CATCH and THROW are normally used for errors.
In Factor, they have a mechanism for escaping from recursive-descent
searches that Slava used when he rewrote my code, but we don't have
anything like that in Forth. The use of CATCH and THROW seems like a
rather heavy-weight solution for a linked list, but it might work.
I agree that the word "toucher" is awkward. Do you have a suggestion
for a better term?
Hugh Aguilar
Well, I think there are three limitations with your system:
1.) We can't start a traversal in the middle of list.
2.) We can't have multiple lists with the same latter portion.
3.) We can't remove nodes from the list because, if we remove the tail
node, chaos will result when we try to unfix the tail node after the
traversal.
I already mentioned the first two limitations; I only thought of #3
last night. The first two are pretty minor and shouldn't be a problem
to anybody. The last one is more serious. I had explicitly stated that
removing nodes inside of the EACH toucher was okay, and the upgrade to
your system would prevent that. Besides that, I think I do this myself
in the slide-rule program. I will have to look through the program as
I don't recall off the top of my head, but I think that is how I
remove unwanted marks.
I will likely end up providing both systems in my novice package. If
people can live with the three limitations mentioned above, they can
use the system you described and get a speed boost. If they can't,
then they can use the simpler system.
jacko
> On Jul 13, 4:15 pm, jacko <jackokr...@gmail.com> wrote:
>
> > You could improve TAIL by using tail circular lists. The pointer to
> > the list points to the tail, and the tail addresses the head. In this
> > way the tail can be found faster than the head. It does limit common
> > tails. :-(
>
> > Insert on the head and delete from head are still fast and append
> > becomes very fast on long lists.
>
> > The null item is detected by tail detection.
>
> > Cheers Jacko
>
> Well, I think there are three limitations with your system:
>
> 1.) We can't start a traversal in the middle of list.
You can have pointers to any node.
> 2.) We can't have multiple lists with the same latter portion.
Good for list compression.
> 3.) We can't remove nodes from the list because, if we remove the tail
> node, chaos will result when we try to unfix the tail node after the
> traversal.
To remove a node the useual method of fixing the previous bypassing
the deleted. The zero test for nil end, is replaced by an UNTIL tail =
test, and there is no need to unlink to traverse the list. Removing
the tail is a matter of a reallocation of a node to the tail i.e.
delete the before tail and place the value in the tail. Or a reentrant
method involves a handle dereferance of the TAIL. This handle object
node may freely do with its value as it sees fit. Object type or node
counter or ...
> I already mentioned the first two limitations; I only thought of #3
> last night. The first two are pretty minor and shouldn't be a problem
> to anybody. The last one is more serious. I had explicitly stated that
> removing nodes inside of the EACH toucher was okay, and the upgrade to
> your system would prevent that. Besides that, I think I do this myself
> in the slide-rule program. I will have to look through the program as
> I don't recall off the top of my head, but I think that is how I
> remove unwanted marks.
>
> I will likely end up providing both systems in my novice package. If
> people can live with the three limitations mentioned above, they can
> use the system you described and get a speed boost. If they can't,
> then they can use the simpler system.
I did write Java for them once, but got distracted, and a while later
I'd lost the code. It does simplify garbage collection too, due to the
need for copying of the list, and its implication of just the one
referer handle node, and implied copying.
jacko
structure may decend (from)/to the tail and point back to all the
multi-heads. This would regain tail common form, at the expense of a
lot more logically processing.
jacko
This is maybe a divergent FIFOO for the multi out head emphisis.
jacko
A sub factor instance vartiable often provides all the inheritance,
now if only there was an autosuper(instancevarname) method creator...
Hugh Aguilar
> On 14 July, 21:24, Hugh Aguilar <hughaguila...@yahoo.com> wrote:
> > 1.) We can't start a traversal in the middle of list.
>
> You can have pointers to any node.
Isn't it true that the pointer to the list is to the tail node, and
the tail node's .FORE link provides us with the pointer to the head of
the list? In this case, there can't be multiple head nodes in the
list, which is what you effectively want when you begin a traversal in
the middle of the list.
I'm not saying that it *can't* be done, but seems pretty awkward.
> > 2.) We can't have multiple lists with the same latter portion.
>
> Good for list compression.
My slide-rule program wouldn't benefit from this feature. I can't
think of any application that would benefit, but maybe it is
possible.
> > 3.) We can't remove nodes from the list because, if we remove the tail
> > node, chaos will result when we try to unfix the tail node after the
> > traversal.
>
> To remove a node the useual method of fixing the previous bypassing
> the deleted. The zero test for nil end, is replaced by an UNTIL tail =
> test, and there is no need to unlink to traverse the list. Removing
> the tail is a matter of a reallocation of a node to the tail i.e.
> delete the before tail and place the value in the tail. Or a reentrant
> method involves a handle dereferance of the TAIL. This handle object
> node may freely do with its value as it sees fit. Object type or node
> counter or ...
I did think of a solution to the #3 problem that I was concerned
about. I could have a dummy node as the tail node of *every* list.
This would ensure that the tail node never gets removed by the
toucher. Also, it should speed up the search because I can compare the
node address fetched from .FORE of every node against the dummy node's
address, which can be compiled as a literal. There is no need to hang
onto the tail node's address on the already-crowded return stack.
Also, there is no need to "fix" the list so that it isn't circular as
I was describing before.
I don't like the idea of having a handle for the list. I want to keep
my code compatible with what I've already got so I don't have to
rewrite the slide-rule program.
> It does simplify garbage collection too, due to the
> need for copying of the list, and its implication of just the one
> referer handle node, and implied copying.
I don't know what you are talking about in regard to copying.
On the subject of copying though, that can be avoided if it is
possible to remove nodes from a list. Without this ability, the
solution is to copy the list and only copy the desired nodes, and then
clobber the entire original list. This is pretty inefficient though,
because ALLOCATE is *very* slow on SwiftForth and likely is slow on
any Forth that uses the MALLOC function from the GLIBC library
internally.
Hugh Aguilar
Are you talking about doubly-linked lists now?
jacko
> Java and C# using interfaces. In more dynamic languages like Ruby and
> Python and JavaScript and Lua, you would add appropriate methods to
> the dictionary that represented an object. And this effectively gives
> you an "isa" relationship to a role without classes, giving you
> flexibility to have more fine-grained models.
This is not supprising given the Java security model. The actual class
hierachy supplied in the runtime is
WellSubClassLoopHoleAdaptedLongName in places, but suffices. Handling
RuntimeException via some callback methods would speed up the
debugging cycle. So if I used arrays in a class it would require me to
write a handle(ArrayIndexOutOfBoundsException) method, without
excessive try/catch. Still would have problems with dynamic array
sizes etc.
Instanciating Vehicle would be a silly way of doing a traffic
simulation. Moves would be better, in essence nouns are bad class
trees. Verbs are better class trees, factoring the essence of a method
group. Nouns can then be built by instance variables of verbers with
method groups. Of course they would all subclass VerbRelator, a
synchronized abstract interface/method group which ran the
actionPrincipal method as a thread to inter-relate the noun
constituents. Obvious, for things that implement Runnable.
But static binding is good. Is static typing good?
IllegalClassCastException is a real pain on Objects. Surely some kind
of switch(Object) case Class: would be more useful, or a cast MyObject
obj.fn(blah) to save all the (MyObject) typing...
It's all a load of bowl lacks.
Alex McDonald
A lot of these "problems" that you see in list processing have already
been solved, and it's naive to assume that no-one has tackled these
issues before. If you're looking for a general purpose library of
functions, then take a look at this extensive Forth library of
algorithms; http://code.google.com/p/ffl/.
For a good text, see the Java based book here;
http://java-alg.info/Addison.Wesley-Algorithms.in.Java-Parts.1-4.Third.Edition/tindex.htm
[As a side note, I am not sure of the copyright on this website or
others associated with it. I offer it up as an example; if you find it
useful, I'm sure Addison Wesley and Robert Sedgwick (the author
http://www.cs.princeton.edu/~rs/) would appreciate it if you purchased
the book.]
Alex McDonald
Recursion escapes by design. If you are recursing and you can't see
how to exit, then your recursion is wrongly coded and you're not
understanding how the return stack unwinds.
: x 1+ dup 10 < if dup . recurse then 1- dup . ;
3 x
4 5 6 7 8 9 9 8 7 6 5 4 3 ok.
> although CATCH and THROW are normally used for errors.
> In Factor, they have a mechanism for escaping from recursive-descent
> searches that Slava used when he rewrote my code, but we don't have
> anything like that in Forth. The use of CATCH and THROW seems like a
> rather heavy-weight solution for a linked list, but it might work.
It's not necessary. In general CATCH and THROW are most useful when
you have no control over the exit, or where the bookkeeping to unwind
is too expensive or complex to maintain. For example, an INCLUDE [of
an INCLUDE [of an INCLUDE...]] that suffers an IO error during a read
of a file.
>
> I agree that the word "toucher" is awkward. Do you have a suggestion
> for a better term?
The word that does the iterating is an iterator. The word executed on
each iteration doesn't need a name; it's a general purpose word, not
specific to the iteration.
jacko
> On Jul 14, 2:53 pm, jacko <jackokr...@gmail.com> wrote:
>
> > On 14 July, 21:24, Hugh Aguilar <hughaguila...@yahoo.com> wrote:
> > > 1.) We can't start a traversal in the middle of list.
>
> > You can have pointers to any node.
>
> Isn't it true that the pointer to the list is to the tail node, and
> the tail node's .FORE link provides us with the pointer to the head of
> the list? In this case, there can't be multiple head nodes in the
> list, which is what you effectively want when you begin a traversal in
> the middle of the list.
>
> I'm not saying that it *can't* be done, but seems pretty awkward.
The trick to handle the tail delete problem also helps with this. The
list is represented so:
->ObNode->Tail->Head->Node1-N->Tail ... circular. Now it is possible
to have the other pointer in the object node handle be a pointer to
any node element. And so the iterator problem is solved at the same
time as the tail delete problem (although tail delete is slow.
> > > 2.) We can't have multiple lists with the same latter portion.
>
> > Good for list compression.
>
> My slide-rule program wouldn't benefit from this feature. I can't
> think of any application that would benefit, but maybe it is
> possible.
Heavy use of lists in any application would benefit from the lower
cache thrashing as long as a garbage collector did not need to be
called.
> > > 3.) We can't remove nodes from the list because, if we remove the tail
> > > node, chaos will result when we try to unfix the tail node after the
> > > traversal.
Using a pointer to pointer a.k.a. a handle in the object node solves
this.
> I did think of a solution to the #3 problem that I was concerned
> about. I could have a dummy node as the tail node of *every* list.
> This would ensure that the tail node never gets removed by the
> toucher. Also, it should speed up the search because I can compare the
> node address fetched from .FORE of every node against the dummy node's
> address, which can be compiled as a literal. There is no need to hang
> onto the tail node's address on the already-crowded return stack.
> Also, there is no need to "fix" the list so that it isn't circular as
> I was describing before.
This just deferes the problem. i.e. how do you keep it on the tail if
there is a tail insert/append without traversal?
> I don't like the idea of having a handle for the list. I want to keep
> my code compatible with what I've already got so I don't have to
> rewrite the slide-rule program.
ok.
> > It does simplify garbage collection too, due to the
> > need for copying of the list, and its implication of just the one
> > referer handle node, and implied copying.
>
> I don't know what you are talking about in regard to copying.
If you can not have common tails, then an append to a list which is
itself appened, will also affect that list, and so the common tail is
broken by the extra length. This implies a copy if this is not what is
desired.
> On the subject of copying though, that can be avoided if it is
> possible to remove nodes from a list. Without this ability, the
> solution is to copy the list and only copy the desired nodes, and then
> clobber the entire original list. This is pretty inefficient though,
> because ALLOCATE is *very* slow on SwiftForth and likely is slow on
> any Forth that uses the MALLOC function from the GLIBC library
> internally.
Remove should work fine.
Instead of making the list tail point to the head, it can point to
another circular list of all current heads. In this way the common
tail can be supported. In this case the second pointer in the object
node would point to the head 'used' indirectly through the tail ring
of heads list. This type of structure has tail order matching ... and
is a multiple iterator. It has easy to garbage collect on calculation
of common traversal elements, or simpler but not as efficiently in
terms of space, with the tail of the tail's ring of heads list being
the counter of active heads, also removing the tail delete on the
tail's ring of heads list.. I'm sure this could be speeded up by
ordering the tail ring of heads list. This FIFOO ... would allow a
fast tail append, and multiple head output interators, with a bounded
gc performance.
jacko
other types. Minus number for example, as each handle to a structure
limits the number of possible active heads.
jacko
No this 'count' is actually a good place to put another quality
structure, including things like the tuple processor preference
reference. A well snoopy avoidance idea.
John Passaniti
> A lot of these "problems" that you see in list
> processing have already been solved, and it's
> naive to assume that no-one has tackled these
> issues before. If you're looking for a general
> purpose library of functions, then take a look
> at this extensive Forth library of algorithms;
> http://code.google.com/p/ffl/.
I remember how in my mid-teens I got interested in computers and
programming. It was a rare week that I didn't "discover" some
entirely new facet of computer science that nobody else had the genius
to see. And my awesome intellect extended to coming up with new,
completely original algorithms and data structures that clearly were
solving problems with more speed, precision, efficiency, and elegance
than everyone else. I knew this because the public library near my
home only had a handful of books on the subject of programming, and
the information in those books was pretty basic, introductory stuff.
Then I learned that I could hop on a bus and visit the technical
libraries of the University of Rochester and Rochester Institute of
Technology. And suddenly, what I thought was my brilliance was not
only listed in /their/ introductory books, but was often coded better,
using insights I didn't have. Oh, and when dated, those algorithms
and data structures were often before I was born, or when I was still
in a high-chair, inverting bowls of cereal on my head.
I look forward to the day Hugh makes the same discovery.
jacko
> programming. It was a rare week that I didn't "discover" some
> entirely new facet of computer science that nobody else had the genius
> to see. And my awesome intellect extended to coming up with new,
> completely original algorithms and data structures that clearly were
> solving problems with more speed, precision, efficiency, and elegance
> than everyone else. I knew this because the public library near my
> home only had a handful of books on the subject of programming, and
> the information in those books was pretty basic, introductory stuff.
>
> Then I learned that I could hop on a bus and visit the technical
> libraries of the University of Rochester and Rochester Institute of
> Technology. And suddenly, what I thought was my brilliance was not
> only listed in /their/ introductory books, but was often coded better,
> using insights I didn't have. Oh, and when dated, those algorithms
> and data structures were often before I was born, or when I was still
> in a high-chair, inverting bowls of cereal on my head.
>
> I look forward to the day Hugh makes the same discovery.
I remember my suprise when I resaw structures, or more to the point
structures of arrays rather than arrays of structures. The simple idea
of sequentially splitting the list node haeads to be seperate from the
list node tails in one example. In this way a search can become
without the overhead of cache line prefetch of the link pointers. Or
the sector load of the other fields of the record of a database ... I
think FoxPro?
Hugh Aguilar
> A lot of these "problems" that you see in list processing have already
> been solved, and it's naive to assume that no-one has tackled these
> issues before. If you're looking for a general purpose library of
> functions, then take a look at this extensive Forth library of
> algorithms;http://code.google.com/p/ffl/.
I don't use other people's code.
Alex McDonald
I've seen some remarkable posts in my time, but this one is a keeper.
Please remove my code for the EACH word and Andrew's EACH[ from your
library that you recently borrowed. Then delete all the code you use
that was written by other people; any Forth compilers you may have and
your operating system for starters. That way, you can remain in self
imposed ignorance, and I'll be spared your assinine comments, since
you won't have access to the internet.
Alex McDonald
Based on his latest response, you may die unrewarded.
jacko
A thread for the strong no circularity argument. It can be virtualized
as self reference. Can say sorting of method variables be optimized by
the underlaying FIFOO?
I'd say use any algorithmic technique that provides useful, and always
read any source you use to program something. Obviously somethings are
there to be looked at and somethings are compiled to run.
Cheers Jacko
Hugh Aguilar
I don't *use* other people's code. When you suggest that I use that
FFL library, you are essentially suggesting that I discard my own code
and use the FFL library on the assumption that it *must* be better
than mine. While it may be true that my own code can be improved,
possibly with that algorithm that Jacko suggested, my code already
works pretty well; I'm not going to discard it. I haven't bothered to
look at the FFL library, but I'm pretty sure that I'm already way
ahead of anything they've got.
The problem that I see on c.l.f. is that people too easily make the
jump from having *heard about* some code or algorithm, to imagining
themselves to be advanced programmers. This is what Passaniti was
doing when he told me that my symtab algorithm (that I invented)
"sucks" and that I should use a Splay Tree instead. He hadn't actually
*implemented* a Splay Tree, he had just *heard about* the Splay Tree
algorithm and assumed that it must be far superior to what I invented,
without bothering to look at my code or understand my algorithm. Same
thing with Bernd Payson who says that he examined binary trees 20
years ago and found them to be inferior, and that nothing has changed
since then. He has implemented a hash table, but he never bothered to
look at my code or understand my algorithm before he denounced it.
That is very closed minded. You're doing the same thing. You *heard
about* the FFL, and you are assuming that it must be far superior to
my code. You didn't write it though. All of this is reminiscent of
that guy in my cab who was telling me that he is the city champion
cage-fighter. Most likely he just watches a lot of cage-fighting on
television and that was his launching pad into fantasy land.
I'll sometimes look at other people's code and rewrite it. I can
pretty much always improve it. For example, here is Andrew's code that
you mentioned:
: list[ postpone begin postpone ?dup postpone while
postpone dup postpone >r ;
immediate
: ]list postpone r> postpone @ postpone repeat ;
immediate
And here is mine:
macro: each[
begin ?dup while
dup .fore @ >r ;
macro: ]each
r> repeat ;
Note also that it was *myself* who wrote MACRO: which improves the
readability so much. Also note that I fetch the next node *before* I
execute the code in the middle. If the code in the middle removes the
node from the list, I already have the next node on the return stack.
Andrew's code has a bug in that, if the node is removed, the @ at the
end will accessing deallocated heap memory. This might work sometimes,
but it is not guaranteed to work, and the result will be that the
program sometimes works and sometimes crashes. Also note that my EACH
is superior to EACH[ most of the time, because a child data-type can
call the toucher function in its own toucher function that does the
same thing. For example, see how <SHOW-DECOMMA> calls <SHOW-SEQ>, and
<KILL-DECOMMA> calls <KILL-SEQ> as I described previously:
http://groups.google.com/group/comp.lang.forth/browse_thread/thread/907f253d229d5b7d/2df16523e5543803?lnk=raot#2df16523e5543803
I'm definitely interested in seeing code. Your EACH was pretty good. I
had already said that my list traversal functions could be made faster
executing, but the fact that you rewrote EACH to do this was
definitely a good thing. My INSERT-ORDERED actually used local
variables, so it certainly could be made faster, but I've already done
that now. The fact that you and Andrew are posting code at all puts
you at an infinitely higher level than people like John Passaniti and
Elizabeth Rather who *never* post code. They are at zero, so *any*
code is infinitely better. I was also interested in Jacko's suggestion
regarding the algorithm for linked lists. There is a huge difference
between making a pertinent suggestion such as that, and making a
suggestion that I throw out all of my code and use a library that
neither of us know anything about, on the assumption that it must be
better than my code.
jacko
memory block, an wire up soft software opcodes for the vm to serialize
and unserialize LLITERALS, and perform TOP and JOIN. I'll have to
think about it. Some may say that to build it in Java is pointless but
it's supposed to be useful to many, and optimized where possible
within the bounds of availability of such an optimizer. Or should that
be specilizer...
A memory protection fault... really?
Alex McDonald
> On Jul 15, 4:23 pm, Alex McDonald <b...@rivadpm.com> wrote:
>
>
>
> > On 15 July, 21:24, Hugh Aguilar <hughaguila...@yahoo.com> wrote:
>
> > > On Jul 15, 4:59 am, Alex McDonald <b...@rivadpm.com> wrote:
>
> > > > A lot of these "problems" that you see in list processing have already
> > > > been solved, and it's naive to assume that no-one has tackled these
> > > > issues before. If you're looking for a general purpose library of
> > > > functions, then take a look at this extensive Forth library of
> > > > algorithms;http://code.google.com/p/ffl/.
>
> > > I don't use other people's code.
>
> > I've seen some remarkable posts in my time, but this one is a keeper.
> > Please remove my code for the EACH word and Andrew's EACH[ from your
> > library that you recently borrowed. Then delete all the code you use
> > that was written by other people; any Forth compilers you may have and
> > your operating system for starters. That way, you can remain in self
> > imposed ignorance, and I'll be spared your assinine comments, since
> > you won't have access to the internet.
>
> I don't *use* other people's code. When you suggest that I use that
> FFL library, you are essentially suggesting that I discard my own code
> and use the FFL library on the assumption that it *must* be better
> than mine.
I can only suggest that you re-read what I said; "then *take a look*
at this extensive Forth library of algorithms".
> While it may be true that my own code can be improved,
> possibly with that algorithm that Jacko suggested, my code already
> works pretty well; I'm not going to discard it. I haven't bothered to
> look at the FFL library, but I'm pretty sure that I'm already way
> ahead of anything they've got.
Yeah, sure.
> <KILL-DECOMMA> calls <KILL-SEQ> as I described previously:http://groups.google.com/group/comp.lang.forth/browse_thread/thread/9...
Bloviation noted.
>
> I'm definitely interested in seeing code.
But not the ffl. Consistency isn't your major suit, is it.
> Your EACH was pretty good. I
> had already said that my list traversal functions could be made faster
> executing, but the fact that you rewrote EACH to do this was
> definitely a good thing. My INSERT-ORDERED actually used local
> variables, so it certainly could be made faster, but I've already done
> that now. The fact that you and Andrew are posting code at all puts
> you at an infinitely higher level than people like John Passaniti and
> Elizabeth Rather who *never* post code. They are at zero, so *any*
> code is infinitely better. I was also interested in Jacko's suggestion
> regarding the algorithm for linked lists. There is a huge difference
> between making a pertinent suggestion such as that, and making a
> suggestion that I throw out all of my code and use a library that
> neither of us know anything about, on the assumption that it must be
> better than my code.
G'nite.
Hugh Aguilar
> > I don't *use* other people's code. When you suggest that I use that
> > FFL library, you are essentially suggesting that I discard my own code
> > and use the FFL library on the assumption that it *must* be better
> > than mine.
>
> I can only suggest that you re-read what I said; "then *take a look*
> at this extensive Forth library of algorithms".
Why are you so emotional about promoting the FFL library? I didn't see
your name listed as the author of the linked-list code. If you did
actually write that code, then I will look at it. It would only be
fair that I look at other people's code when I expect them to look at
mine. On the other hand though, if you are only promoting the FFL
library as being good code because it was *not* written by *me*, then
I'm not going to bother to look at it.
> > While it may be true that my own code can be improved,
> > possibly with that algorithm that Jacko suggested, my code already
> > works pretty well; I'm not going to discard it. I haven't bothered to
> > look at the FFL library, but I'm pretty sure that I'm already way
> > ahead of anything they've got.
>
> Yeah, sure.
I glanced over the FFL library lined-list code. It doesn't have
anything comparable to my INSERT-ORDERED or FIND-PRIOR. It would need
a lot of work to be done on it before it could be used in my slide-
rule program, or in any serious application. I don't really consider
it to be my job to fix the problems in the FFL library though, when I
already have code of my own that does everything I need.
I don't know what "bloviation" means. That sounds like something that
John Passaniti does. ;-)
Another problem with Andrew Haley's code is that it uses the return
stack. If the function that EACH[...]EACH is used in has local
variables, the code will work on some Forth systems and fail on other
Forth systems. On SwiftForth locals have their own stack, but on a lot
of Forth systems, the locals are held on the return stack and code
such as EACH[...]EACH will cause chaos. This will be very confusing to
the user, especially if he doesn't know that EACH[...]EACH uses the
return stack internally, which he wouldn't know unless he examined the
source-code for EACH[...]EACH.
On a related note, I upgraded my <CSTR...CSTR> words so that they are
now nestable. They can also be repeated; they use a circular buffer
internally. I rewrote S" to use these internally, so we can now have
multiple S" strings used interpretively and they don't have to be
compiled into the dictionary as I was doing before. My <CSTR...CSTR>
words don't use the return stack though. I had to implement my own
stack. There are a lot of functions throughout my extensive software
that use <CSTR...CSTR> and also use either local variables or the
return stack.
This has been my experience with other people's code. There are always
problems. This is why I really prefer to use my own code rather than
other people's code. My code is the best code.
I only included EACH[...]EACH in the novice package as a concession to
Andrew Haley. It is bad code though. I was well aware of how to write
code like this before Andrew made his suggestion, and I was also well
aware of the problems with using the return stack in regard to local
variables. Now you are suggesting that my novice package is dependent
upon code written by people such as Andrew Haley and yourself. That is
a lot of baloney --- I'm generally way ahead of everybody else. I'll
look at other people's code for ideas, but I don't actually *use*
their code without rewriting it first, and I normally just write my
own code from scratch without concern for what the rest of the world
is doing.
This thread is now up to 56 posts, and so far the only intelligent
thing that has been said was Jacko's suggestion regarding having the
pointer to the list aimed at the tail node, and the tail node's .FORE
field pointing to the head of the list. To have one intelligent post
out of 56 posts is actually pretty good by comp.lang.forth standards.
In general, I would say that the ratio is more like 1/200.
John Passaniti
> The problem that I see on c.l.f. is that people too easily make
> the jump from having *heard about* some code or algorithm, to
> imagining themselves to be advanced programmers. This is what
> Passaniti was doing when he told me that my symtab algorithm
> (that I invented) "sucks" and that I should use a Splay Tree
> instead.
Correct. Your algorithm does indeed "suck" relative to splay trees,
and for many symbol table applications, splay trees "suck" relative to
hashes. This isn't just opinion, but can be *easily* demonstrated by
measurement, which you refuse to do. Splay trees are simpler than
your algorithm, take less memory, are less computationally intense,
and for the application of symbol tables, ultimately provide the user
with faster access to items. The advantages, disadvantages, and
performance of splay trees are all well studied. In contrast, you
provide *no* measurement of your "symtab" and make *no* effort to
compare and contrast against splay trees or any other data structure.
So we just have to take it on faith that "symtab" represents something
better.
You seem to operate with a kind of "plausible deniability" mindset.
You avoid any serious research into competitive algorithms or even
minimal attempts at measurement so that when you say you don't know of
a better algorithm than "symtab" you are honestly representing the
case. But that's a claim that comes from willful ignorance, not from
knowing you created something better.
> He hadn't actually *implemented* a Splay Tree, he had just *heard
> about* the Splay Tree algorithm and assumed that it must be far
> superior to what I invented, without bothering to look at my code
> or understand my algorithm.
A splay tree is far superior to what you "invented" for a symbol table
application. Measurement would prove this, but you're terrified of
that. But without bothering with measurement, the simple analysis I
provided would show you that the frequency of a symbol is far less
important than locality of reference. So ultimately, an understanding
of your algorithm is irrelevant as what you predicated your design on
is *wrong*. Your algorithm may indeed be the best possible way to
implement your idea-- but your idea is flawed on its face.
I've found splay trees useful twice in my work. Implementing them
wasn't difficult-- there are plenty of references available to guide
anyone trying to get the splay operations right. The first time I
implemented this was for a sort of object cache for which the cost of
hashing was higher than the cost of splaying. The second time was as
part of a memory allocator. Both are happily running inside
commercial products.
> All of this is reminiscent of
> that guy in my cab who was telling me that he is the city champion
> cage-fighter. Most likely he just watches a lot of cage-fighting on
> television and that was his launching pad into fantasy land.
Weird. The fact that I get paid to write code certainly suggests I...
write code. I'm sure I wouldn't last too long as a software engineer
if lacked that ability. If I did, I might have to find work in a
different field-- like maybe a cab driver.
> The fact that you and Andrew are posting code at all puts
> you at an infinitely higher level than people like John
> Passaniti and Elizabeth Rather who *never* post code.
Ironic. I've been told that I post too much code that isn't Forth,
and now you tell me I don't post any code at all.
Andrew Haley
> Another problem with Andrew Haley's code is that it uses the return
> stack. If the function that EACH[...]EACH is used in has local
> variables, the code will work on some Forth systems and fail on other
> Forth systems.
That's an interesting point. I'm going to find it pretty hard to
agree that using the return stack is a bug, though.
> On SwiftForth locals have their own stack, but on a lot of Forth
> systems, the locals are held on the return stack and code such as
> EACH[...]EACH will cause chaos. This will be very confusing to the
> user, especially if he doesn't know that EACH[...]EACH uses the
> return stack internally, which he wouldn't know unless he examined
> the source-code for EACH[...]EACH.
Or read the documentation, if it's to be used as a canned routine.
But again, an interesting point. I suppose there are some Forth
implementations on which local variables break as soon as something is
put onto the return stack, but it's pretty horrible from a QOI point
of view. Well, let's see: has anyone here used a system with this
property? Or ever worse, written one?
There's no restriction on the use of locals in the case of DO .. LOOP,
so I suppose the code could be rewritten as
: list[ postpone begin postpone ?dup postpone while
postpone dup postpone @ postpone dup postpone do ;
immediate
: ]list postpone i postpone loop postpone repeat ;
immediate
... but this is so horrible I can't imagine anyone actually doing it.
> I only included EACH[...]EACH in the novice package as a concession
> to Andrew Haley.
Please don't.
Andrew.
Alex McDonald
wrote:
> Hugh Aguilar <hughaguila...@yahoo.com> wrote:
> > Another problem with Andrew Haley's code is that it uses the return
> > stack. If the function that EACH[...]EACH is used in has local
> > variables, the code will work on some Forth systems and fail on other
> > Forth systems.
>
> That's an interesting point. I'm going to find it pretty hard to
> agree that using the return stack is a bug, though.
If locals are implemented according to the standard, then this is not
an issue.
: list[ postpone begin postpone ?dup postpone while
postpone dup postpone @ postpone >r ;
immediate
: ]list postpone r> postpone repeat ;
immediate
: test list[ <<word>> ]list ;
generates
begin ?dup while dup @ >r <<word>> r> postpone repeat
Perfectly valid Forth, and the use of the return stack is balanced.
<<word>> will run fine on a system that meets the standard; locals
defined on the return stack, in a separate area, or even if recorded
on slabs of cheese. If it was a problem then
: each( i*x node iterator -- i*x' )
>r
begin ?dup
while
r@ over @
>r execute r> \ iterator sees ( i*x node), returns( i*x'))
repeat r> drop ( rdrop) ;
would have truly horrendous problems if the execute word used locals.
This code doesn't, and neither does yours. Hugh's superior code is
obviously being written for some system that isn't Forth.
Andrew Haley
> On 18 July, 12:20, Andrew Haley <andre...@littlepinkcloud.invalid>
> wrote:
>> Hugh Aguilar <hughaguila...@yahoo.com> wrote:
>> > Another problem with Andrew Haley's code is that it uses the return
>> > stack. If the function that EACH[...]EACH is used in has local
>> > variables, the code will work on some Forth systems and fail on other
>> > Forth systems.
>>
>> agree that using the return stack is a bug, though.
>
> If locals are implemented according to the standard, then this is not
> an issue.
>
> : list[ postpone begin postpone ?dup postpone while
> postpone dup postpone @ postpone >r ;
> immediate
> : ]list postpone r> postpone repeat ;
> immediate
>
> : test list[ <<word>> ]list ;
>
> generates
>
> begin ?dup while dup @ >r <<word>> r> postpone repeat
Sure, but <<word>> here may be a whole bunch of words, some of which
are locals.
> Perfectly valid Forth, and the use of the return stack is balanced.
> <<word>> will run fine on a system that meets the standard; locals
> defined on the return stack, in a separate area, or even if recorded
> on slabs of cheese.
Unfortunately not.
"13.3.3.2 Syntax restrictions
"d) After a definition's locals have been declared, a program may
place data on the return stack. However, if this is done, locals shall
not be accessed until those values have been removed from the return
stack; "
That's nasty, and I've never come across a system with such a broken
implementation of locals, but there it is.
Andrew.
Alex McDonald
wrote:
Ah, I see; I misunderstood Hugh's use of the word "function" and
misinterpreted it as "word" or colon definition (that is, a separate
definition where locals can be used without restriction).
It's not one any version of Win32Forth suffers from, as locals are
based off a pointer into the rstack, not relative position on the
rstack;
: x 10 20 { a b } 30 >r a . b . r> ." r=" . a . b . ; ok
x 10 20 r=30 10 20 ok
I'd never given it much thought until now, as I'm not a big user of
locals. It's a valid point.
Alex McDonald
And as a followup;
: x ... { node } list[ <<do stuff using local node>> ]list ;
: x ... list[ { node } <<do stuff using local node>> ]list ;
The second would also cause problems; perhaps not on Gforth that
allows block level locals, but certainly on Win32Forth and possibly a
number of other Forths. { is global to the colon definition, and
Win32forth tidies up on ';'; the WHILE clause makes it conditional,
and we'd be tidying up something that may never have been executed.
There's a lesson here, but I can't quite work out whether it's "don't
use locals" or "don't use postponed code when you don't understand
what's being generated". Either way...
Andrew Haley
> On 19 July, 09:38, Andrew Haley <andre...@littlepinkcloud.invalid>
> wrote:
>>
>> "13.3.3.2 Syntax restrictions
>>
>> "d) After a definition's locals have been declared, a program may
>> place data on the return stack. However, if this is done, locals shall
>> not be accessed until those values have been removed from the return
>> stack; "
>>
>> That's nasty, and I've never come across a system with such a broken
>> implementation of locals, but there it is.
>
> misinterpreted it as "word" or colon definition (that is, a separate
> definition where locals can be used without restriction).
>
> It's not one any version of Win32Forth suffers from, as locals are
> based off a pointer into the rstack, not relative position on the
> rstack;
Indeed, and locals must be handled that way or DO ... LOOP won't work.
Given that, I have no idea why the restriction exists. Maybe
13.3.3.2d should be ignored if there exist no Forth systems with such
a restriction. If there's anyone reading this who knows of such a
system, please shout.
Andrew.
Andrew Haley
> Alex McDonald <bl...@rivadpm.com> wrote:
>> On 19 July, 09:38, Andrew Haley <andre...@littlepinkcloud.invalid>
>> wrote:
>>>
>>> "13.3.3.2 Syntax restrictions
>>>
>>> "d) After a definition's locals have been declared, a program may
>>> place data on the return stack. However, if this is done, locals shall
>>> not be accessed until those values have been removed from the return
>>> stack; "
>>>
>>> That's nasty, and I've never come across a system with such a broken
>>> implementation of locals, but there it is.
>>
>> Ah, I see; I misunderstood Hugh's use of the word "function" and
>> misinterpreted it as "word" or colon definition (that is, a separate
>> definition where locals can be used without restriction).
>>
>> It's not one any version of Win32Forth suffers from, as locals are
>> based off a pointer into the rstack, not relative position on the
>> rstack;
>
> Indeed, and locals must be handled that way or DO ... LOOP won't work.
(Rather, DO ... LOOP and locals won't work together.)
Andrew.
Coos Haak
: x 2 { y } 5 0 do i y = if leave then cr i . loop ;
x
0
1 ok
Runs on Win32Forth, Gforth and a lot more.
--
Coos
CHForth, 16 bit DOS applications
http://home.hccnet.nl/j.j.haak/forth.html
David N. Williams
> Alex McDonald<bl...@rivadpm.com> wrote:
>> On 19 July, 09:38, Andrew Haley<andre...@littlepinkcloud.invalid>
>> wrote:
>>>
>>> "13.3.3.2 Syntax restrictions
>>>
>>> "d) After a definition's locals have been declared, a program may
>>> place data on the return stack. However, if this is done, locals shall
>>> not be accessed until those values have been removed from the return
>>> stack; "
>>>
>>> That's nasty, and I've never come across a system with such a broken
>>> implementation of locals, but there it is.
>>
>> It's not one any version of Win32Forth suffers from, as locals are
>> based off a pointer into the rstack, not relative position on the
>> rstack;
>
> Indeed, and locals must be handled that way or DO ... LOOP won't work.
> Given that, I have no idea why the restriction exists. Maybe
> 13.3.3.2d should be ignored if there exist no Forth systems with such
> a restriction. If there's anyone reading this who knows of such a
> system, please shout.
I believe my notes to myself, according to which *neither* pfe
*nor* gforth are such systems. Somehow I discovered and fixed a
use of >R...local...R> in my dstrings code about two years ago,
even though tests with pfe and gforth didn't blink at it. It
must have been just code inspection for the new project I was
working on.
I agree it's a really nasty and illogical thing, that ought to
be abolished!
-- David
Hugh Aguilar
wrote:
> Hugh Aguilar <hughaguila...@yahoo.com> wrote:
> > Another problem with Andrew Haley's code is that it uses the return
> > stack. If the function that EACH[...]EACH is used in has local
> > variables, the code will work on some Forth systems and fail on other
> > Forth systems.
>
> That's an interesting point. I'm going to find it pretty hard to
> agree that using the return stack is a bug, though.
The "bug" is the ANS-Forth standard. The standard should have
specified that locals and >R...R> are compatible. The problem with the
standard is that it is too liberal. It allows pretty much anything to
be standard. We see the same problem in regard to floats, that they
can either be on their own stack or on the parameter stack. Anything
goes! The result of all this liberalism is that the programmer who
wants his code to run on *any* ANS-Forth standard system (as I do with
my novice package) must program for the lowest-common denominator. As
a practical matter, nobody really does this. For example, in my novice
package I have a comment at the top that says my software only works
if the floats have their own stack. Every program has a list of
comments including the phrase "only works if..." at the top. The
result is that essentially *nobody* is actually writing ANS-Forth
standard code. As a practical matter, the standard doesn't exist.
The ANS-Forth standard isn't a standard at all; it is an embodiment of
Elizabeth Rather's California-Liberal ideology in which *everything*
is tolerated and *everything* is "standard." When the idea of local
variables (that didn't exist in the 1970s FIG implementations) was
introduced, the ANS-Forth committee tried to support the local
variables without providing them with their own stack, but allowing
them to reside on the return stack. Of course, if the locals are on
the return stack, and the return stack continues to be used for
>R...R>, then chaos will result --- but chaos is considered to be
*standard* with Elizabeth Rather at the helm!
I think most novices are baffled by the idea that >R...R> don't work
across DO...LOOP boundaries. That is a problem that could have been
solved a long time ago by requiring that DO...LOOP have its own stack.
Also, at the same time, the problem with locals being incompatible
with >R...R> could have been solved at the same time by requiring
locals to use the same stack as DO...LOOP uses. All of this could have
been solved in 1994 when the ANS-Forth standard came out, but it
wasn't. The result is that in 2010 we are using micro-controllers that
typically have 16 registers with orthogonal addressing-modes, but we
are programming in a language that seems to have been designed for the
8080. It is as if we never escaped from the 1970s. We have really got
to start focusing on the future rather than the past!
Hugh Aguilar
> On 18 July, 12:20, Andrew Haley <andre...@littlepinkcloud.invalid>
> wrote:
>
> > Hugh Aguilar <hughaguila...@yahoo.com> wrote:
> > > Another problem with Andrew Haley's code is that it uses the return
> > > stack. If the function that EACH[...]EACH is used in has local
> > > variables, the code will work on some Forth systems and fail on other
> > > Forth systems.
>
> > That's an interesting point. I'm going to find it pretty hard to
> > agree that using the return stack is a bug, though.
>
> If locals are implemented according to the standard, then this is not
> an issue.
That isn't true; read section 13.3.3
"After a definition's locals have been declared. a program may place
data on the return stack. However, if this is done, locals shall not
be accessed until those values have been removed from the return
stack."
> on slabs of cheese. If it was a problem then
>
> : each( i*x node iterator -- i*x' )
> >r
> begin ?dup
> while
> r@ over @
> >r execute r> \ iterator sees ( i*x node), returns( i*x'))
> repeat r> drop ( rdrop) ;
>
> would have truly horrendous problems if the execute word used locals.
> This code doesn't, and neither does yours. Hugh's superior code is
> obviously being written for some system that isn't Forth.
What??? You're not making any sense at all.
Hugh Aguilar
> Well, I think there are three limitations with your system:
>
> 1.) We can't start a traversal in the middle of list.
>
>
> node, chaos will result when we try to unfix the tail node after the
> traversal.
What I said here is still true. As a practical matter, what I've got
right now works fine for what I need and doesn't have any limitations.
It might be possible to implement Jacko's algorithm with #3 relieved,
but it would result in pretty complicated code. It is getting
complicated enough that just upgrading to doubly-linked circular lists
might be simpler.
Most of the speed issues with my algorithm are due to SwiftForth's
lack of code optimization. Here are a couple of possible definitions
for TAIL:
: tail ( head -- node )
begin dup .fore @ dup while \ -- node next
nip repeat drop ;
: tail ( head -- node )
nil swap begin dup while \ -- prev node
nip dup .fore @ repeat drop ;
The first definition doesn't lend itself very well to optimization
because some of the code is on one side of the WHILE and some of the
code is on the other side of the WHILE. The second definition is
better because all of the code is on the right side of the WHILE and
it can get optimized. The NIP and the DUP are adjacent, so they can be
combined together. Unfortunately, SwiftForth doesn't do this:
see tail
47F46F 4 # EBP SUB 83ED04
47F472 0 # 0 [EBP] MOV C7450000000000
47F479 EBX EBX OR 09DB
47F47B 47F491 JZ 0F8410000000
47F481 4 # EBP ADD 83C504
47F484 4 # EBP SUB 83ED04
47F487 EBX 0 [EBP] MOV 895D00
47F48A 0 [EBX] EBX MOV 8B1B
47F48C 47F479 JMP E9E8FFFFFF
47F491 0 [EBP] EBX MOV 8B5D00
47F494 4 # EBP ADD 83C504
47F497 RET C3 ok
Notice this amazing code snippet:
47F481 4 # EBP ADD 83C504
47F484 4 # EBP SUB 83ED04
This is what I mean about Forth Inc. being an embarrassment to the
Forth community. C programmers see such awful code and they think that
it is representative of *all* Forth compilers. Forth Inc. *owns* the
name "Forth" and they represent themselves as being the epitome of
Forth. They are dragging the name "Forth" through the mud, and they
have been doing so for over 30 years.
Alex McDonald
As someone who has spent a lot of time trying to generate optimised
x86 code from Forth, I'd point out that it's non-trivial. Try writing
one yourself; you'll soon find out that reducing loads, stores and
stack adjustment is not easy, even something that appears as simple as
NIP DUP. The alternative of writing a peephole optimiser to remove
these statements is hardly worth the effort when NIP DUP is so
infrequently encountered, and possibly a symptom of not using DROP or
SWAP early enough in the source code.
The assertion that "The second definition is better because all of the
code is on the right side of the WHILE and it can get optimized"
doesn't make sense; why would it matter which side it's on? If you
eliminate .FORE, the parts you show between BEGIN and WHILE, and the
parts between WHILE and REPEAT are both basic blocks (one entry and
one exit), and both sides are equally optimisable.
(.FORE terminates the basic block because the compiler doesn't
know .FOREs stack effects or other side effects during compilation of
TAIL without complex analysis & storing the effects of .FORE during
the compilation of .FORE itself. Doing that analysis and using it
during future compilations of the word is non-trivial.)
I'd also really appreciate it if you could lay off knocking Elizabeth
Rather and SwiftForth at every available opportunity.
Elizabeth D Rather
> On 19 July, 21:27, Hugh Aguilar<hughaguila...@yahoo.com> wrote:
>> Notice this amazing code snippet:
>>
>> 47F481 4 # EBP ADD 83C504
>> 47F484 4 # EBP SUB 83ED04
>>
>
> As someone who has spent a lot of time trying to generate optimised
> x86 code from Forth, I'd point out that it's non-trivial. Try writing
> one yourself; you'll soon find out that reducing loads, stores and
> stack adjustment is not easy, even something that appears as simple as
> NIP DUP. The alternative of writing a peephole optimiser to remove
> these statements is hardly worth the effort when NIP DUP is so
> infrequently encountered, and possibly a symptom of not using DROP or
> SWAP early enough in the source code.
May I point out that Hugh is still using SwiftForth 2.x. He raised a
ruckus a few years ago about a bug, which we fixed in version 3.0 a
couple of years before he complained. He refused to upgrade, even with
a discount, and we fixed his particular bug gratis, but he is still
quite a few years out of date. This may affect many issues, ranging
from code generation to all-over performance and user interface issues.
The current version of Swift is 3.2.2.
Cheers,
Elizabeth
--
==================================================
Elizabeth D. Rather (US & Canada) 800-55-FORTH
FORTH Inc. +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com
"Forth-based products and Services for real-time
applications since 1973."
==================================================
Richard Owlett
>{facts}
You, Mr. Pelc, and a few others keep asserting FACTS are relevant
*on CLF* LOL!!!!!!
Aleksej Saushev
> On Jul 18, 5:20 am, Andrew Haley <andre...@littlepinkcloud.invalid>
> wrote:
>> Hugh Aguilar <hughaguila...@yahoo.com> wrote:
>> > Another problem with Andrew Haley's code is that it uses the return
>> > stack. If the function that EACH[...]EACH is used in has local
>> > variables, the code will work on some Forth systems and fail on other
>> > Forth systems.
>>
>> That's an interesting point. I'm going to find it pretty hard to
>> agree that using the return stack is a bug, though.
>
> The "bug" is the ANS-Forth standard.
When dancer is bad, the problem is music.
> The standard should have
> specified that locals and >R...R> are compatible.
Why? Using local variables elimiate needs in these stupid stack shuffling.
> The problem with the
> standard is that it is too liberal.
Oh, "Forth isn't yet another bondage and domination language." :D
> It allows pretty much anything to
> be standard. We see the same problem in regard to floats, that they
> can either be on their own stack or on the parameter stack.
Yes, they should be on the parameters stack, since they are conceptually
the very same numbers as anything else.
> Anything
> goes! The result of all this liberalism is that the programmer who
> wants his code to run on *any* ANS-Forth standard system (as I do with
> my novice package) must program for the lowest-common denominator.
Non sequitur.
> As
> a practical matter, nobody really does this.
It is you who doesn't, others do.
> For example, in my novice
> package I have a comment at the top that says my software only works
> if the floats have their own stack. Every program has a list of
> comments including the phrase "only works if..." at the top. The
> result is that essentially *nobody* is actually writing ANS-Forth
> standard code. As a practical matter, the standard doesn't exist.
Why are you using floating point numbers anyway? Fixed point numbers can
do the same, your "Thinking Forth" teaches you how.
> The ANS-Forth standard isn't a standard at all; it is an embodiment of
> Elizabeth Rather's California-Liberal ideology in which *everything*
> is tolerated and *everything* is "standard." When the idea of local
> variables (that didn't exist in the 1970s FIG implementations) was
> introduced, the ANS-Forth committee tried to support the local
> variables without providing them with their own stack, but allowing
> them to reside on the return stack. Of course, if the locals are on
> the return stack, and the return stack continues to be used for
>>R...R>, then chaos will result --- but chaos is considered to be
> *standard* with Elizabeth Rather at the helm!
I know at least one Forth implementor who intends to allocate local
frames on the return stack.
> I think most novices are baffled by the idea that >R...R> don't work
> across DO...LOOP boundaries. That is a problem that could have been
> solved a long time ago by requiring that DO...LOOP have its own stack.
> Also, at the same time, the problem with locals being incompatible
> with >R...R> could have been solved at the same time by requiring
> locals to use the same stack as DO...LOOP uses.
So, how many stacks does your Forth have? Does a dozen fit your needs?
> All of this could have
> been solved in 1994 when the ANS-Forth standard came out, but it
> wasn't. The result is that in 2010 we are using micro-controllers that
> typically have 16 registers with orthogonal addressing-modes, but we
> are programming in a language that seems to have been designed for the
> 8080. It is as if we never escaped from the 1970s. We have really got
> to start focusing on the future rather than the past!
Why are you programming in Forth still then? There're better programming
languages that don't have those archaic features, having more modern
things instead.
--
HE CE3OH...
ron
>
> Notice this amazing code snippet:
>
> 47F481 4 # EBP ADD 83C504
> 47F484 4 # EBP SUB 83ED04
>
> This is what I mean about Forth Inc. being an embarrassment to the
> Forth community.
> C programmers see such awful code ...
No, they don't. Firstly because most C programmers don't use Forth.
Secondly, because most C programmers don't look at disassembly and
finally because the generated code is fast enough that most C
programmers will have no reason to look *there* for a problem.
In Reva there is no optimization (except tail-recursion removal).
This is on-purpose: I don't want surprising code from my compiler. My
naive approach generates code that is as fast as I need.
I might add that my dictionary is a simple singly-linked list, and I
have not yet found that interpret speed is a problem. Of course, I
don't abuse the dictionary as a general-purpose database...
Try writing your own Super Optimizing Forth, instead of B&M about
SwithForth every chance you get. You may learn much of use in the
process.
Andrew Haley
> On Jul 18, 5:20?am, Andrew Haley <andre...@littlepinkcloud.invalid>
> wrote:
>> Hugh Aguilar <hughaguila...@yahoo.com> wrote:
>> > Another problem with Andrew Haley's code is that it uses the return
>> > stack. If the function that EACH[...]EACH is used in has local
>> > variables, the code will work on some Forth systems and fail on other
>> > Forth systems.
>>
>> That's an interesting point. I'm going to find it pretty hard to
>> agree that using the return stack is a bug, though.
>
> The "bug" is the ANS-Forth standard. The standard should have
> specified that locals and >R...R> are compatible.
Arguably, that's right. We could simply get this paragraph deleted,
since AFAIK it doesn't apply to any Forth ssystems anyway.
> [ demented ranting deleted ]
> I think most novices are baffled by the idea that >R...R> don't work
> across DO...LOOP boundaries. That is a problem that could have been
> solved a long time ago by requiring that DO...LOOP have its own
> stack.
It could, but that would mean that every task, even on very small
systems, would need three stacks. I don't think the slight extra
benefit is worth it.
Andrew.
Alex McDonald
wrote:
> Hugh Aguilar <hughaguila...@yahoo.com> wrote:
>
> > The "bug" is the ANS-Forth standard. The standard should have
> > specified that locals and >R...R> are compatible.
>
> Arguably, that's right. We could simply get this paragraph deleted,
> since AFAIK it doesn't apply to any Forth ssystems anyway.
Time for an Forth 200x RfD methinks (if that's the right mechanism).
Bernd Paysan
It's probably not a complete deletion. The Forths that use the return stack
for locals I know still work with >R and R>, if those follow a certain
discipline. I.e.
: foo { a b } >r a b + r> * ;
works but
: bar >r { a b } a b + r> * ;
won't. And you will confuse a system like bigForth if you do
: foobar { a b } >r a 0> IF b r> - ELSE r> b - THEN ;
The mechanism for correcting the return stack to adjust for DO LOOP and >R
R> is too simple to deal with that kind of code.
--
Bernd Paysan
"If you want it done right, you have to do it yourself!"
http://www.jwdt.com/~paysan/
Andrew Haley
> Alex McDonald wrote:
>
>> On 20 July, 09:58, Andrew Haley <andre...@littlepinkcloud.invalid>
>> wrote:
>>> Hugh Aguilar <hughaguila...@yahoo.com> wrote:
>>>
>>> > The "bug" is the ANS-Forth standard. The standard should have
>>> > specified that locals and >R...R> are compatible.
>>>
>>> Arguably, that's right. We could simply get this paragraph deleted,
>>> since AFAIK it doesn't apply to any Forth ssystems anyway.
>>
>> Time for an Forth 200x RfD methinks (if that's the right mechanism).
>
> It's probably not a complete deletion. The Forths that use the
> return stack for locals I know still work with >R and R>, if those
> follow a certain discipline. I.e.
>
> : foo { a b } >r a b + r> * ;
That breaks Para d, and that's what I want to allow.
> works but
>
> : bar >r { a b } a b + r> * ;
That breaks Para c. No-one was proposing deleting Para c.
> won't. And you will confuse a system like bigForth if you do
>
> : foobar { a b } >r a 0> IF b r> - ELSE r> b - THEN ;
Surely this can be fixed. I would have thought that every local lived
in a fixed place for the duration of the word. Why not?
Andrew.
Bernd Paysan
>> : bar >r { a b } a b + r> * ;
>
> That breaks Para c. No-one was proposing deleting Para c.
Ok, so we agree on that.
>> won't. And you will confuse a system like bigForth if you do
>>
>> : foobar { a b } >r a 0> IF b r> - ELSE r> b - THEN ;
>
> Surely this can be fixed. I would have thought that every local lived
> in a fixed place for the duration of the word. Why not?
The locals are addressed by the top of return stack. >R and R> adjust
an additional offset to be added; the same happens when further locals
are added to the picture. To track this correctly accross control flow
can be arbitrary complex - the pattern above is certainly possible to
solve, but when you allow unbalanced return stack effects in conditional
loops, it soon becomes too difficult to solve.
Therefore my recommendation is that this sort of return stack tracking
should only be required to work when the balancing is straight-forward
(no control flow involved).
--
Bernd Paysan
"If you want it done right, you have to do it yourself"
Alex McDonald
wrote:
> Bernd Paysan <bernd.pay...@gmx.de> wrote:
> > Alex McDonald wrote:
>
> >> On 20 July, 09:58, Andrew Haley <andre...@littlepinkcloud.invalid>
> >> wrote:
> >>> Hugh Aguilar <hughaguila...@yahoo.com> wrote:
>
> >>> > The "bug" is the ANS-Forth standard. The standard should have
> >>> > specified that locals and >R...R> are compatible.
>
> >>> Arguably, that's right. We could simply get this paragraph deleted,
> >>> since AFAIK it doesn't apply to any Forth ssystems anyway.
>
> >> Time for an Forth 200x RfD methinks (if that's the right mechanism).
>
> > It's probably not a complete deletion. The Forths that use the
> > return stack for locals I know still work with >R and R>, if those
> > follow a certain discipline. I.e.
>
> > : foo { a b } >r a b + r> * ;
>
> That breaks Para d, and that's what I want to allow.
"After a definition's locals have been declared, a program may
place
data on the return stack. However, if this is done, locals shall
not
be accessed until those values have been removed from the return
stack"
Mine passes, and I suspect most Forths (all? all except ...?) do too.
>
> > works but
>
> > : bar >r { a b } a b + r> * ;
>
> That breaks Para c. No-one was proposing deleting Para c.
"Locals shall not be declared until values previously placed on the
return
stack within the definition have been removed"
That's the one that breaks my code. I think I can "fix" this one at no
cost.
>
> > won't. And you will confuse a system like bigForth if you do
>
> > : foobar { a b } >r a 0> IF b r> - ELSE r> b - THEN ;
>
> Surely this can be fixed. I would have thought that every local lived
> in a fixed place for the duration of the word. Why not?
>
Pass. Now, that's an oddball; can you explain what's going on here
that it should be a problem on bigForth?
> Andrew.
Alex McDonald
OK, I see you have in your reply to Andrew.
Hugh Aguilar
How are you going to explain to the novice what is "straight-forward"
and what is not? The return stack is already one of the more confusing
aspects of Forth for novices to learn, especially because of the issue
with DO loops, and locals have made it worse. If we just specify a
separate stack for use by locals and the DO loop, then >R...R> will
*become* straight-forward.
Modern processors have enough registers that we can afford to dedicate
one of them to this separate stack. This was pretty much true in 1994,
and is definitely true in 2010. What I mean is, we have to stop
supporting the 8080. Nowadays, if people want a small processor, they
will likely choose the MSP430 --- but it has sixteen 16-bit registers
--- that is "small" by modern standards.
An argument could be made that we could just get rid of >R...R>
altogether and just use locals. The locals and the DO loop information
could be held on the return stack in this case, and there would be no
need for a separate stack. I would be hesitant to do this, as there is
a lot of legacy code floating around that uses >R...R>. Also, there
are some things that can be done with >R...R> that can't be done with
locals. Specifically, cases in which you have a variable number of
parameters on the stack with some marker (usually zero) underneath
them. For example, in my novice package I have these functions:
: non-zeros ( 0 numbers... -- 0 numbers... count )
0 \ -- count
0 >r begin over while swap >r 1+ repeat nip
0 swap begin r> ?dup while swap repeat ;
: reverse-stack ( 0 numbers... -- 0 numbers... )
non-zeros 0 ?do I roll loop ;
I think the best solution is to make locals and the DO loop standard,
and make >R...R> an optional extension. Also, if >R...R> are provided,
then they *must* use a separate stack from what locals and DO use. A
Forth for a small processor with very few registers (such as the 6812)
could decline to support >R...R>. Most Forths however, would support
>R...R>. The use of >R...R> would be deprecated; the programmers would
be encouraged to use locals instead, which would assure them that
their programs will run on *all* Forth systems --- just in case they
ever want to use the 6812 for something.
John Passaniti
> Modern processors have enough registers that we can afford to dedicate
> one of them to this separate stack. This was pretty much true in 1994,
> and is definitely true in 2010. What I mean is, we have to stop
> supporting the 8080. Nowadays, if people want a small processor, they
> will likely choose the MSP430 --- but it has sixteen 16-bit registers
> --- that is "small" by modern standards.
I see at least four problems with your statements:
1) You are absolutely right that 8-bit microprocessors are seeing far
less use in embedded systems these days. And the reason is obvious--
microprocessors need supporting hardware (ROM, RAM, peripherals) and
the system cost of an 8-bit microprocessor solution. So yes, nobody
is going to put a 8080 in a modern design (unless they enjoy a high
system cost and providing -5, +5, and +12 volt rails). And the same
is largely true for Z80's, 6502's, and other microprocessors.
2) You are however dead wrong in when the discussion turns away from
microprocessors and moves to microcontrollers. In 2010, 8-bit
microcontrollers still rule the Earth because of the relatively low
system cost and thus are still number one for applications that are
cost sensitive or mass produced. 16-bit and 32-bit microcontrollers
are starting to creep into areas where 8-bit microcontrollers rule,
but it's mostly only for applications that may require a bit more
speed or a bit more address space. Every year, plenty of industry
pundits are more than happy to predict the death of 8-bit
microcontrollers. And every year, I still have manufacturer's
representatives in my office who continue to provide me 8-bit
microcontrollers that continue to easily meet needs and have lower
costs than 16-bit solutions. And not only that, but all the major
players are still providing endless derivative parts that permute
every combination of flash, RAM, and peripheral. They wouldn't be
doing that if it wasn't profitable for them.
3) You are also forgetting about programmable logic. It is very
common these days to take a FPGA and implement not just the hardware,
but to instantiate 8-bit processors in the logic for system control.
And quite often, that processor will be functionally equivalent to a
popular 8-bit microprocessor so the designers have access to existing
tools.
4) You're also forgetting that these days, a typical embedded system
may have multiple processors. In the industries I work in, its very
common to have a powerful DSP for processing audio, a beefy MCU (often
32-bit) for control, and one or more 8-bit MCUs for various tasks--
user interfaces (displays, switches, encoders, faders, etc.),
generating control voltages, offloading serial protocols, etc. One of
the last major projects I worked on (an environmental monitoring and
control system) used a 32-bit ARM microcontroller for all the major
processing, but each sense/control module used an 8-bit
microcontroller to do things like read thermocouples, drive relays,
and monitor power line voltages.
A lot of people don't seem to get this. They'll look at their 32-bit
or 64-bit desktop computer, and completely ignore the keyboard they
are typing on and the mouse they are pointing with are probably 8-bit
systems. They'll point to the 128-bit GPU that makes their games
scream, but they'll ignore the game controllers the use to play those
games.
So the point is that 8-bit systems-- including those with creaky old
instruction sets like the 8051-family-- are still very much alive and
well and continuing to dominate sales. As time goes forward, that is
less likely to be true, but it's been true for the past 23 years that
I've been an embedded systems software engineer, and I fearlessly
predict it will be for some time into the future.
Andrew Haley
> Andrew Haley wrote:
>>> : bar >r { a b } a b + r> * ;
>>
>> That breaks Para c. No-one was proposing deleting Para c.
>
> Ok, so we agree on that.
>
>>> won't. And you will confuse a system like bigForth if you do
>>>
>>> : foobar { a b } >r a 0> IF b r> - ELSE r> b - THEN ;
>>
>> Surely this can be fixed. I would have thought that every local lived
>> in a fixed place for the duration of the word. Why not?
>
> The locals are addressed by the top of return stack.
I see that, but why? Surely there's a register you can use for a
frame pointer.
> >R and R> adjust an additional offset to be added; the same happens
> when further locals are added to the picture. To track this
> correctly accross control flow can be arbitrary complex - the
> pattern above is certainly possible to solve, but when you allow
> unbalanced return stack effects in conditional loops, it soon
> becomes too difficult to solve.
>
> Therefore my recommendation is that this sort of return stack
> tracking should only be required to work when the balancing is
> straight-forward (no control flow involved).
I don't know how to specify that.
Andrew.
Bernd Paysan
>> The locals are addressed by the top of return stack.
>
> I see that, but why? Surely there's a register you can use for a
> frame pointer.
No. x86 has only 8 registers. I already have a stack pointer, a return
stack pointer, a current object pointer, a user pointer, and a loop counter
register. Leaves 3 free registers, which is just barely enough. And those
three remaining registers are the special-purpose registers which are used
by instructions like multiplication or shift.
--
Bernd Paysan
"If you want it done right, you have to do it yourself!"
http://www.jwdt.com/~paysan/
Elizabeth D Rather
> Andrew Haley wrote:
>>> The locals are addressed by the top of return stack.
>>
>> I see that, but why? Surely there's a register you can use for a
>> frame pointer.
>
> No. x86 has only 8 registers. I already have a stack pointer, a return
> stack pointer, a current object pointer, a user pointer, and a loop counter
> register. Leaves 3 free registers, which is just barely enough. And those
> three remaining registers are the special-purpose registers which are used
> by instructions like multiplication or shift.
I concur, on most platforms we have good use for whatever registers
there are, and locals are definitely lower priority than the overall
function of the VM. Of course, on the small microcontrollers we don't
implement locals at all.
Andrew Haley
> Andrew Haley wrote:
>>> The locals are addressed by the top of return stack.
>>
>> I see that, but why? Surely there's a register you can use for a
>> frame pointer.
>
> No. x86 has only 8 registers. I already have a stack pointer, a
> return stack pointer, a current object pointer, a user pointer, and
> a loop counter register. Leaves 3 free registers, which is just
> barely enough.
Ah, I see, we're talking legacy x86. Fair enough, but it'll be gone
soon. Very soon, I hope!
A couple of observations: it wouldn't be that hard to stash the frame
pointer and/or the object pointer in a user variable, but I accept
that's a performance hit for a (very?) few rare cases.
A dedicated object pointer register seems a bit odd: couldn't that
register be used for the top local variable, which just happens to be
the current object when OO is in use?
Andrew.
Stephen Pelc
wrote:
>Andrew Haley wrote:
>>> The locals are addressed by the top of return stack.
>>
>> I see that, but why? Surely there's a register you can use for a
>> frame pointer.
>No. x86 has only 8 registers. I already have a stack pointer, a return
>stack pointer, a current object pointer, a user pointer, and a loop counter
>register. Leaves 3 free registers, which is just barely enough.
Yes. VFX for x86 uses a frame pointer, but keeps the current object
pointer in a USER variable and does not cache DO ... LOOP data.
The performance trade-off will depend heavily on coding style
and compiler complexity. For MPE, the benefits of a real locals
pointer were important.
The example below appears to break bigForth. This is in itself a
non-issue as the code is not ANS standard.
: foo { a b } >r a b + r> * ;
I too think that removing the restriction of ANS 13.3.3.2 para d is a
good thing. It seems that bigForth is not in line with current common
practice.
Stephen
--
Stephen Pelc, steph...@mpeforth.com
MicroProcessor Engineering Ltd - More Real, Less Time
133 Hill Lane, Southampton SO15 5AF, England
tel: +44 (0)23 8063 1441, fax: +44 (0)23 8033 9691
web: http://www.mpeforth.com - free VFX Forth downloads
Bernd Paysan
> The example below appears to break bigForth. This is in itself a
> non-issue as the code is not ANS standard.
> : foo { a b } >r a b + r> * ;
No, *that* example works with the current bigForth release.
: foo { a b } >r a b + r> * ; ok
2 3 4 foo . 14 ok
The result looks good to me.
> I too think that removing the restriction of ANS 13.3.3.2 para d is a
> good thing. It seems that bigForth is not in line with current common
> practice.
What won't work is something like
: foo { a b } n>r a b + nr> 1+ ;
or other conditional or counted moves to and from the return stack. >r and
r> just allocate and destroy an unnamed local variable.
Since I use much more object oriented code than locals, I favor using a
register for the object pointer over using it as frame pointer.
Alex McDonald
wrote:
> Bernd Paysan <bernd.pay...@gmx.de> wrote:
> > Andrew Haley wrote:
> >>> The locals are addressed by the top of return stack.
>
> >> I see that, but why? Surely there's a register you can use for a
> >> frame pointer.
>
> > No. x86 has only 8 registers. I already have a stack pointer, a
> > return stack pointer, a current object pointer, a user pointer, and
> > a loop counter register. Leaves 3 free registers, which is just
> > barely enough.
>
> Ah, I see, we're talking legacy x86. Fair enough, but it'll be gone
> soon. Very soon, I hope!
>
> A couple of observations: it wouldn't be that hard to stash the frame
> pointer and/or the object pointer in a user variable, but I accept
> that's a performance hit for a (very?) few rare cases.
That's what Win32Forth does. Locals are very expensive in terms of
cycles with unoptimised code generation, and not much better with some
optimisation. The only solution is full analysis, and as Bernd has
pointed out, that's not easy (and given that locals are largely
avoidable, may be a waste of effort).
: x 10 { a b | c } a b + to c c ; ok
see x
: x ( ? -- ? ) \ std call compiles
\ len=102 type=7 flag=00
\ in file (console)
( $42E9FC ' x ) mov $-4 [ebp], eax \ 8945FC \ 10
( $42E9FF ' x+$3 ) mov eax, # $A \ C7C00A000000 \ { a b |
c }
( $42EA05 ' x+$9 ) lea ebp, $-4 [ebp] \ 8D6DFC
( $42EA08 ' x+$C ) push $4 [ebx] \ FF7304 \ $4 [ebx]
is
( $42EA0B ' x+$F ) mov $4 [ebx], esp \ 896304 \ local
frame var
( $42EA0E ' x+$12 ) push $0 [ebp] \ FF7500
( $42EA11 ' x+$15 ) push eax \ 50
( $42EA12 ' x+$16 ) sub esp, # $4 \ 83EC04
( $42EA15 ' x+$19 ) mov eax, $4 [ebp] \ 8B4504
( $42EA18 ' x+$1C ) lea ebp, $8 [ebp] \ 8D6D08
( $42EA1B ' x+$1F ) mov $-4 [ebp], eax \ 8945FC \ a
( $42EA1E ' x+$22 ) mov ecx, $4 [ebx] \ 8B4B04
( $42EA21 ' x+$25 ) lea ebp, $-4 [ebp] \ 8D6DFC
( $42EA24 ' x+$28 ) mov eax, $-4 [ecx] \ 8B41FC
( $42EA27 ' x+$2B ) mov $-4 [ebp], eax \ 8945FC \ b
( $42EA2A ' x+$2E ) mov ecx, $4 [ebx] \ 8B4B04
( $42EA2D ' x+$31 ) lea ebp, $-4 [ebp] \ 8D6DFC
( $42EA30 ' x+$34 ) mov eax, $-8 [ecx] \ 8B41F8
( $42EA33 ' x+$37 ) add eax, $0 [ebp] \ 034500 \ +
( $42EA36 ' x+$3A ) lea ebp, $4 [ebp] \ 8D6D04
( $42EA39 ' x+$3D ) mov $-4 [ebp], eax \ 8945FC \ to c
( $42EA3C ' x+$40 ) mov ecx, $4 [ebx] \ 8B4B04
( $42EA3F ' x+$43 ) lea ebp, $-4 [ebp] \ 8D6DFC
( $42EA42 ' x+$46 ) lea eax, $-C [ecx] \ 8D41F4
( $42EA45 ' x+$49 ) mov ecx, $0 [ebp] \ 8B4D00
( $42EA48 ' x+$4C ) mov [eax], ecx \ 8908
( $42EA4A ' x+$4E ) mov eax, $4 [ebp] \ 8B4504
( $42EA4D ' x+$51 ) lea ebp, $8 [ebp] \ 8D6D08 \ c
( $42EA50 ' x+$54 ) mov $-4 [ebp], eax \ 8945FC
( $42EA53 ' x+$57 ) mov ecx, $4 [ebx] \ 8B4B04
( $42EA56 ' x+$5A ) lea ebp, $-4 [ebp] \ 8D6DFC
( $42EA59 ' x+$5D ) mov eax, $-C [ecx] \ 8B41F4
( $42EA5C ' x+$60 ) mov esp, $4 [ebx] \ 8B6304 \ tidy up
rstack
( $42EA5F ' x+$63 ) pop $4 [ebx] \ 8F4304
( $42EA62 ' x+$66 ) ret near \ C3 ( end ) ok
: y 10 + ; ok
see y
: y ( ? -- ? ) \ std call compiles
\ len=3 type=7 flag=00
\ in file (console)
( $42EA68 ' y ) add eax, # $A \ 83C00A
( $42EA6B ' y+$3 ) ret near \ C3 ( end ) ok
Although a bit of an artificial example, it does demonstrate some of
the issues & noisy code generated even for simple use cases.
Andrew Haley
> On 22 July, 10:36, Andrew Haley <andre...@littlepinkcloud.invalid>
> wrote:
>> Bernd Paysan <bernd.pay...@gmx.de> wrote:
>> > Andrew Haley wrote:
>> >>> The locals are addressed by the top of return stack.
>>
>> >> frame pointer.
>>
>> > No. x86 has only 8 registers. ?I already have a stack pointer, a
>> > return stack pointer, a current object pointer, a user pointer, and
>> > barely enough.
>>
>> Ah, I see, we're talking legacy x86. ?Fair enough, but it'll be gone
>> soon. ?Very soon, I hope!
>>
>> A couple of observations: it wouldn't be that hard to stash the frame
>> pointer and/or the object pointer in a user variable, but I accept
>> that's a performance hit for a (very?) few rare cases.
>
> That's what Win32Forth does. Locals are very expensive in terms of
> cycles with unoptimised code generation, and not much better with some
> optimisation. The only solution is full analysis, and as Bernd has
> pointed out, that's not easy (and given that locals are largely
> avoidable, may be a waste of effort).
I guess so. Still, as long as there's one current Forth that doesn't
allow mixing of lcoals and return stack usage, then no matter how
misguided I think the design decision is, I'm not going to pursue any
standard change.
By the way, I'm a bit surprised at the way most Forth compiler authors
choose not to optimize locals. I would have thought that locals were
a splendid opportunity to optimize by placing a few of them in
registers. I'll grant that the x86 architecture really doesn't help
with that, though.
Andrew.
Aleksej Saushev
> Bernd Paysan <bernd....@gmx.de> wrote:
>> Andrew Haley wrote:
>>>> The locals are addressed by the top of return stack.
>>>
>>> I see that, but why? Surely there's a register you can use for a
>>> frame pointer.
>>
>> No. x86 has only 8 registers. I already have a stack pointer, a
>> return stack pointer, a current object pointer, a user pointer, and
>> a loop counter register. Leaves 3 free registers, which is just
>> barely enough.
>
> Ah, I see, we're talking legacy x86. Fair enough, but it'll be gone
> soon. Very soon, I hope!
What is going to replace it and how soon?
Mythical Forth-CPU you'll design and ship in a year?
--
HE CE3OH...
Marcel Hendrix
[..]
> Locals are very expensive in terms of
> cycles with unoptimised code generation, and not much better with some
> optimisation. The only solution is full analysis, and as Bernd has
> pointed out, that's not easy (and given that locals are largely
> avoidable, may be a waste of effort).
> : x 10 { a b | c } a b + to c c ; ok
> see x
> : x ( ? -- ? ) \ std call compiles
[.. 41 lines of disassembly snipped ..]
> : y 10 + ; ok
> see y
> : y ( ? -- ? ) \ std call compiles
> \ len=3D3 type=3D7 flag=3D00
> \ in file (console)
> ( $42EA68 ' y ) add eax, # $A \ 83C00A
> ( $42EA6B ' y+$3 ) ret near \ C3 ( end ) ok
> Although a bit of an artificial example, it does demonstrate some of
> the issues & noisy code generated even for simple use cases.
FORTH> : x 10 0 params| a b c | a b + to c c ;
FORTH> ' x idis
$01242680 : [trashed]
$0124268A pop rbx
$0124268B lea rbx, [rbx #10 +] qword
$0124268F push rbx
$01242690 ;
FORTH> : y 10 + ; ' y idis
$01242700 : [trashed]
$0124270A pop rbx
$0124270B lea rbx, [rbx #10 +] qword
$0124270F push rbx
$01242710 ;
And, of course:
FORTH> : test 6 x y . ; ok
FORTH> see test
Flags: ANSI
$01242780 : test
$0124278A push #26 b#
$0124278C jmp .+10 ( $01139242 ) offset NEAR
$01242791 ;
-marcel
Alex McDonald
> Alex McDonald <b...@rivadpm.com> writes Re: Locals (Was: Are re-entrant functions not such a big deal?)
> [..]
>
> > Locals are very expensive in terms of
> > cycles with unoptimised code generation, and not much better with some
> > optimisation. The only solution is full analysis, and as Bernd has
> > pointed out, that's not easy (and given that locals are largely
> > avoidable, may be a waste of effort).
> > : x 10 { a b | c } a b + to c c ; ok
> > see x
> > : x ( ? -- ? ) \ std call compiles
>
> [.. 41 lines of disassembly snipped ..]
I know. Still, thanks for counting.
>
> > : y 10 + ; ok
> > see y
> > : y ( ? -- ? ) \ std call compiles
> > \ len=3D3 type=3D7 flag=3D00
> > \ in file (console)
> > ( $42EA68 ' y ) add eax, # $A \ 83C00A
> > ( $42EA6B ' y+$3 ) ret near \ C3 ( end ) ok
> > Although a bit of an artificial example, it does demonstrate some of
> > the issues & noisy code generated even for simple use cases.
>
> FORTH> : x 10 0 params| a b c | a b + to c c ;
> FORTH> ' x idis
> $01242680 : [trashed]
> $0124268A pop rbx
> $0124268B lea rbx, [rbx #10 +] qword
> $0124268F push rbx
> $01242690 ;
>
> FORTH> : y 10 + ; ' y idis
> $01242700 : [trashed]
> $0124270A pop rbx
> $0124270B lea rbx, [rbx #10 +] qword
> $0124270F push rbx
> $01242710 ;
>
That could be add [esp], # 10, surely?
> And, of course:
>
> FORTH> : test 6 x y . ; ok
> FORTH> see test
> Flags: ANSI
> $01242780 : test
> $0124278A push #26 b#
> $0124278C jmp .+10 ( $01139242 ) offset NEAR
> $01242791 ;
>
> -marcel
Interesting. One of the reasons the code I showed is so noisy is (1)
use of EBP as the stack, and ESP as the rstack; you don't get short &
snappy opcodes on stack operations as a result and (2) the optimiser
is a bit (understatement; very) broken at the moment when eliminating
unnecessary stack ops. But I do use ADD to set the flags for + , as
the flags can be used by the optimiser; they appear as a pseudo flags
variable at the top of the virtual stack during optimisation.
More work required. Thanks for the poke.
Alex McDonald
wrote:
The x86 architecture is register starved in 32 bit mode, and even 16
in 64bit mode is a bit mean. W32F (my STC version) uses EBP=stack,
ESP=rstack, EAX=tos, EBX=task based user area leaving ECX, EDX, ESI
and EDI to serve multiple duties. Lots of spilling even with very
clever optimisations.
ron
> The x86 architecture is register starved in 32 bit mode, and even 16
> in 64bit mode is a bit mean. W32F (my STC version) uses EBP=stack,
> ESP=rstack, EAX=tos, EBX=task based user area leaving ECX, EDX, ESI
> and EDI to serve multiple duties. Lots of spilling even with very
> clever optimisations.
True enough. In Reva we use EAX as TOS, ESI as the data stack and ESP
as the rstack, with all other registers "up for grabs". Since we
don't have "task data" there's no need to take up another register.
The choice of ESI remains from Reva's parent, RetroForth, which
utilized the LODSD instruction to fetch data into TOS. Reva still
does that sometimes, but as you know, the string instructions are not
as fast as they were on the older CPUs...
A very big advantage of W32F and Reva's use of EAX as TOS is that
interfacing with external libraries is far easier and more efficient,
since the return value from external function calls is (in Windows,
Linux and Mac OS/X at least) returned in EAX -- so an external
function call already places its results in TOS, ready to use.
Andrew Haley
You know the answer to this, surely: even in Russia you presumably get
the same x86-64 parts as the rest of the world. There are a few
32-bit x86 parts made, but AFAIK these are reserved for niche
applications: the Intel Atom is still 32-bit, but the Pineview, maybe
eventually to replace it, is 64-bit. I suspect proportion of 32-bit
only x86 parts isn't going to increase.
Andrew.
Paul Rubin
> You know the answer to this, surely: even in Russia you presumably get
> the same x86-64 parts as the rest of the world. There are a few
> 32-bit x86 parts made, but AFAIK these are reserved for niche
> applications: the Intel Atom is still 32-bit, but the Pineview, maybe
> eventually to replace it, is 64-bit. I suspect proportion of 32-bit
> only x86 parts isn't going to increase.
Eh? For embedded purposes there's tons of 32-bit and probably 16-bit
x86 processors. AMD Elan and Geode, Via Nano, NVidia Ion, etc. The
x86-64 in so-called "real mode" is still 16-bit, I think, and that is
where (if anywhere) you'd expect Forth code to run on such a chip: in
low level BIOS and bootup code.
Andrew Haley
> Andrew Haley <andr...@littlepinkcloud.invalid> writes:
>> You know the answer to this, surely: even in Russia you presumably get
>> the same x86-64 parts as the rest of the world. There are a few
>> 32-bit x86 parts made, but AFAIK these are reserved for niche
>> applications: the Intel Atom is still 32-bit, but the Pineview, maybe
>> eventually to replace it, is 64-bit. I suspect proportion of 32-bit
>> only x86 parts isn't going to increase.
>
> Eh? For embedded purposes there's tons of 32-bit and probably 16-bit
> x86 processors. AMD Elan and Geode, Via Nano, NVidia Ion, etc.
Well, yes, these are precisely the niche applications I mentioned.
Given the lead of Pineview, I expect that these will eventually be
replaced by 64-bit designs.
> The x86-64 in so-called "real mode" is still 16-bit, I think, and
> that is where (if anywhere) you'd expect Forth code to run on such a
> chip: in low level BIOS and bootup code.
It's not where *I*'d expect Forth code to run! Your mileage may
vary... :-)
Andrew.
Paul Rubin
> Well, yes, these are precisely the niche applications I mentioned.
> Given the lead of Pineview, I expect that these will eventually be
> replaced by 64-bit designs.
I don't see it. Pineview is for netbooks and lightweight desktop
computers, which these days are very powerful boxes expected to run
multimedia applications. Nothing like what we usually think of as
embedded processors. 32-bit x86's are a lot smaller and will stay
around for those who don't want to use ARM's. I even wonder if the
Intel Larrabee GPU cores will run the 64-bit instruction set.
>> .... real mode...
> It's not where *I*'d expect Forth code to run!
OpenBIOS?