Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

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

8 queens problem in Oforth

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

Contents

  8 queens problem in Oforth "WJ" <w_a_x_man@yahoo.com> - 2015-03-19 07:53 +0000
    Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-19 08:58 -0700
      Re: 8 queens problem in Oforth Doug Hoffman <glidedog@gmail.com> - 2015-03-20 08:16 -0400
        Re: 8 queens problem in Oforth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-03-21 10:11 +0000
          Re: 8 queens problem in Oforth franck.bensusan@gmail.com - 2015-03-21 03:45 -0700
            Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-21 14:14 -0700
              Re: 8 queens problem in Oforth franck.bensusan@gmail.com - 2015-03-21 14:28 -0700
                Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-21 14:38 -0700
                  Re: 8 queens problem in Oforth franck.bensusan@gmail.com - 2015-03-21 15:15 -0700
                    Re: 8 queens problem in Oforth hughaguilar96@gmail.com - 2015-03-21 18:23 -0700
                      Re: 8 queens problem in Oforth franck.bensusan@gmail.com - 2015-03-22 03:03 -0700
                        Re: 8 queens problem in Oforth hughaguilar96@gmail.com - 2015-03-22 14:04 -0700
                          Re: 8 queens problem in Oforth franck.bensusan@gmail.com - 2015-03-22 16:34 -0700
                            Re: 8 queens problem in Oforth hughaguilar96@gmail.com - 2015-03-22 21:49 -0700
                              Re: 8 queens problem in Oforth Raimond Dragomir <raimond.dragomir@gmail.com> - 2015-03-23 00:05 -0700
                                Re: 8 queens problem in Oforth hughaguilar96@gmail.com - 2015-03-23 21:43 -0700
                                  Re: 8 queens problem in Oforth franck.bensusan@gmail.com - 2015-03-24 04:13 -0700
                              Re: 8 queens problem in Oforth franck.bensusan@gmail.com - 2015-03-23 00:17 -0700
                    Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-21 19:47 -0700
                      Re: 8 queens problem in Oforth franck.bensusan@gmail.com - 2015-03-22 08:41 -0700
                        Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-22 13:37 -0700
                      Re: 8 queens problem in Oforth Bernd Paysan <bernd.paysan@gmx.de> - 2015-03-22 18:13 +0100
                        Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-22 13:55 -0700
                          Re: 8 queens problem in Oforth "Alex McDonald" <blog@rivadpm.com> - 2015-03-22 21:08 +0000
                            Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-22 14:39 -0700
                              Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-22 14:50 -0700
                              Re: 8 queens problem in Oforth Bernd Paysan <bernd.paysan@gmx.de> - 2015-03-22 22:58 +0100
                                Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-22 15:13 -0700
                                  Re: 8 queens problem in Oforth Bernd Paysan <bernd.paysan@gmx.de> - 2015-03-23 01:03 +0100
                                    Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-22 17:33 -0700
                                      Re: 8 queens problem in Oforth Bernd Paysan <bernd.paysan@gmx.de> - 2015-03-23 02:37 +0100
                                        Re: 8 queens problem in Oforth hughaguilar96@gmail.com - 2015-03-22 20:53 -0700
                                        Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-22 21:11 -0700
                                          Re: 8 queens problem in Oforth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-03-23 11:34 +0000
                                            Re: 8 queens problem in Oforth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-03-23 19:31 +0000
                                            Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-23 15:56 -0700
                                              Re: 8 queens problem in Oforth Bernd Paysan <bernd.paysan@gmx.de> - 2015-03-24 00:38 +0100
                                                Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-23 19:08 -0700
                                                Re: 8 queens problem in Oforth hughaguilar96@gmail.com - 2015-03-30 05:02 -0700
                                                  Re: 8 queens problem in Oforth hughaguilar96@gmail.com - 2015-03-30 05:08 -0700
                                                    Re: 8 queens problem in Oforth "Alex McDonald" <blog@rivadpm.com> - 2015-03-30 15:36 +0100
                                          Re: 8 queens problem in Oforth Bernd Paysan <bernd.paysan@gmx.de> - 2015-03-23 16:46 +0100
                                            Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-23 15:32 -0700
                                              Re: 8 queens problem in Oforth Bernd Paysan <bernd.paysan@gmx.de> - 2015-03-23 23:48 +0100
                                                Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-23 16:14 -0700
                                    Re: 8 queens problem in Oforth hughaguilar96@gmail.com - 2015-03-22 17:54 -0700
                              Re: 8 queens problem in Oforth "Alex McDonald" <blog@rivadpm.com> - 2015-03-22 23:09 +0000
                          Re: 8 queens problem in Oforth Bernd Paysan <bernd.paysan@gmx.de> - 2015-03-22 22:11 +0100
                            Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-22 14:48 -0700
                              Re: 8 queens problem in Oforth hughaguilar96@gmail.com - 2015-03-22 15:11 -0700
                              Re: 8 queens problem in Oforth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-03-23 11:29 +0000
                                Re: 8 queens problem in Oforth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-03-23 12:20 +0000
                          Re: 8 queens problem in Oforth hughaguilar96@gmail.com - 2015-03-22 14:21 -0700
                          Re: 8 queens problem in Oforth Coos Haak <chforth@hccnet.nl> - 2015-03-22 22:30 +0100
              Re: 8 queens problem in Oforth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-03-23 14:45 +0000
                Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-23 14:53 -0700
                  Re: 8 queens problem in Oforth "Elizabeth D. Rather" <erather@forth.com> - 2015-03-24 09:16 -1000
                    Re: 8 queens problem in Oforth Paul Rubin <no.email@nospam.invalid> - 2015-03-24 12:40 -0700
                    Re: 8 queens problem in Oforth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-03-30 12:24 +0000
            Re: 8 queens problem in Oforth Coos Haak <chforth@hccnet.nl> - 2015-03-21 22:27 +0100
    Re: 8 queens problem in Oforth "WJ" <w_a_x_man@yahoo.com> - 2015-03-19 20:31 +0000
    Re: 8 queens problem in Oforth "WJ" <w_a_x_man@yahoo.com> - 2015-03-19 20:35 +0000
    Re: 8 queens problem in Oforth "WJ" <w_a_x_man@yahoo.com> - 2015-03-21 17:31 +0000
      Re: 8 queens problem in Oforth "WJ" <w_a_x_man@yahoo.com> - 2015-03-21 20:50 +0000
      Re: 8 queens problem in Oforth "WJ" <w_a_x_man@yahoo.com> - 2015-03-21 21:52 +0000

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

#37540

franck.bensusan@gmail.com writes:
> I think Forth mecanisms are really great and could also apply to
> desktop/server programming.

Which mechanisms are those and what is their attraction?  Forth always
seemed to me about minimizing abstraction and shifting responsibilities
to the user that most languages keep with the compiler.  That permits
implementation on very limited hardware and allows users (typically
electrical engineers or physicists, i.e. very technical people but not
really software specialists) to completely understand and modify the
system.

Once you've got desktop/server-level hardware resources and the
willingness to implement complicated features like lexical closures and
a GC, you've lost the user benefit of implementation simplicity, and
added enough features to have lost the spirit of Forth minimalism, what
is really left?  Are the exposed data stack and stream-level
metaprogramming really that attractive?  I think of them as examples of
minimalistically doing things that more resource-hungry languages do
differently for good reasons.

> I don't think a GC will be added to ANS Forth, because it would be 
> disqualified too (see your arguments), and I don't think an extention 
> could give a fast, optimized GC. 

It's an interesting of ANS Forth that it turns out to even be possible
to add a GC as a user extension.  Would it be possible to do something
like that in Oforth, if Oforth didn't already have a GC?

> There are not many choices left if you want a higher level Forth to be
> used on desktop/server targets...

Have you tried Factor?  How is Oforth different if you don't mind my
asking?  I looked at Factor briefly but haven't actually run it.

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

#37538

Paul Rubin wrote:

> Sure, now tell me how that was done in Fortran: do you see where this is
> going?  Forth programs sometimes do stuff like that using OOP libraries,
> but Forth doesn't have first-class functions like Scheme.

Of course Forth has first-class functions.  We call them "xt", execution 
tokens.  You can pass them as parameters to other words, you can return an 
xt as result of a word, you can use xts to define higher order functions.

We don't have closures.  But then, locals are not an essential, but an 
optional feature of Forth - you could say we don't have first-class locals; 
they are an add-on, and the way they are specified is too opaque to say they 
are first-class Forth citizens.  xts however, are essential.  You can't have 
a Forth without xt; even very tiny systems like the instruction set of c18, 
b16 or j1 have EXECUTE.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/
net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*

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

#37545

Bernd Paysan <bernd.paysan@gmx.de> writes:
> Of course Forth has first-class functions.  We call them "xt", execution 
> tokens.  You can pass them as parameters to other words, you can return an 
> xt as result of a word, you can use xts to define higher order functions.

Hmm, ok, I hadn't thought of xt's as first-class functions but maybe
they are.  Is it possible to create them at runtime?  I.e. is there an
ANS portable way to do something like:

    \ given functions f and g, make a new function that composes them
    : compose ( xt1 xt2 -- xt3 ) .... ;

So this should work:

   ['] sin ['] sqrt compose constant sin-sqrt      => ok

   2e sin-sqrt execute f.       => 0.9877659459927356 ok

That number is sin(sqrt(2)).  "Compose" has made a new xt that combines
the actions of the previous two.  It's like adding two numbers in order
to create a new number.  I'd say that to call xt's first class
functions, you have to be able to do this.

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

#37547

on 22/03/2015 20:55:14, Paul Rubin wrote:
> Bernd Paysan <bernd.paysan@gmx.de> writes:
>> Of course Forth has first-class functions.  We call them "xt", execution
>> tokens.  You can pass them as parameters to other words, you can return an
>> xt as result of a word, you can use xts to define higher order functions.
> 
> Hmm, ok, I hadn't thought of xt's as first-class functions but maybe
> they are. Is it possible to create them at runtime? I.e. is there an
> ANS portable way to do something like:
> 
> \ given functions f and g, make a new function that composes them
> : compose ( xt1 xt2 -- xt3 ) .... ;
> 
> So this should work:
> 
> ['] sin ['] sqrt compose constant sin-sqrt      => ok
> 
> 2e sin-sqrt execute f.       => 0.9877659459927356 ok
> 
> That number is sin(sqrt(2)). "Compose" has made a new xt that combines
> the actions of the previous two. It's like adding two numbers in order
> to create a new number. I'd say that to call xt's first class
> functions, you have to be able to do this.
> 

Yes.

:noname sin sqrt ; constant sin-sqrt

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

#37551

"Alex McDonald" <blog@rivadpm.com> writes:
> :noname sin sqrt ; constant sin-sqrt

No, I asked how to do the composition at runtime.  Can you write a word
"compose" that takes two ARBITRARY xt's (not known at compile time, and
maybe themselves created by "compose") and makes a new xt that when you
run it, composes the functions implemented by the two xt's that you
passed?  "compose" or similar words must necessarily allocate heap space
to store their result.

I think the style is possible but not all that useful if you don't have GC.

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

#37553

Paul Rubin <no.email@nospam.invalid> writes:
>> :noname sin sqrt ; constant sin-sqrt
> No, I asked how to do the composition at runtime.  Can you write a word
> "compose" that takes two ARBITRARY xt's

Bernd and others answered: the magic word is "compile,".

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

#37554

Paul Rubin wrote:

> "Alex McDonald" <blog@rivadpm.com> writes:
>> :noname sin sqrt ; constant sin-sqrt
> 
> No, I asked how to do the composition at runtime.  Can you write a word
> "compose" that takes two ARBITRARY xt's (not known at compile time, and
> maybe themselves created by "compose") and makes a new xt that when you
> run it, composes the functions implemented by the two xt's that you
> passed?  "compose" or similar words must necessarily allocate heap space
> to store their result.

Coos Haak and I have posted such a compose.  And it's dictionary space.

> I think the style is possible but not all that useful if you don't have
> GC.

The usual Forth style for this sort of operation is to generate the composed 
xts you need during compilation or at startup, and not dynamically whenever 
you want them.  I.e.

: foo ( big-x -- )  0 ?DO
   ...  ['] fsin ['] fsqrt compose execute  ...
  LOOP ;

is a bad idea.

The good thing with Forth is that it allows you to do that stuff at compile 
time, when it is actually useful.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/
net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*

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

#37556

Bernd Paysan <bernd.paysan@gmx.de> writes:
> Coos Haak and I have posted such a compose.  And it's dictionary space.
Yes, I saw those examples after posting.

> The usual Forth style for this sort of operation is to generate the
> composed xts you need during compilation or at startup, and not
> dynamically whenever you want them.

Sure, that's fine, but it means they're not first-class values the way
numbers are.  Programs dynamically make new numbers all the time.
Languages with first class functions can do the same thing with
functions.  SICP has good examples of using that to implement OOP-like
functionality in Scheme.  The objects are function closures, and you
invoke operations on them by calling the functions, passing the method
and invocation parameters as arguments to the function.  So you are
constantly making and freeing new functions.  This is obviously not
typical Forth style.

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

#37563

Paul Rubin wrote:

> Bernd Paysan <bernd.paysan@gmx.de> writes:
>> Coos Haak and I have posted such a compose.  And it's dictionary space.
> Yes, I saw those examples after posting.
> 
>> The usual Forth style for this sort of operation is to generate the
>> composed xts you need during compilation or at startup, and not
>> dynamically whenever you want them.
> 
> Sure, that's fine, but it means they're not first-class values the way
> numbers are.  Programs dynamically make new numbers all the time.

That's not the point here.  You want to create a tuple of two (or maybe even 
more) xts, and either you keep that tuple on stack, and write a 2execute

: 2execute ( ... xt1 xt2 -- ... ) >r execute r> execute ;

to perform it (then the tuple can be kept on stack), or you want to create a 
concatenated version, which needs memory - when you do that with two numbers 
in Forth, it's the same, you need memory for that, too.

> Languages with first class functions can do the same thing with
> functions.  SICP has good examples of using that to implement OOP-like
> functionality in Scheme.  The objects are function closures, and you
> invoke operations on them by calling the functions, passing the method
> and invocation parameters as arguments to the function.  So you are
> constantly making and freeing new functions.  This is obviously not
> typical Forth style.

Sure, that would be stupid to do it that way.  Forth OOP works different, 
you allocate a piece of memory for the object's data, and have a vtable (or 
some other dispatch mechanism) to get from the object pointer to the method 
you want to call.  That works pretty well within the concepts Forth 
provides, and doesn't work with the concepts Scheme provides you.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/
net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*

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

#37565

Bernd Paysan <bernd.paysan@gmx.de> writes:
> That's not the point here.  You want to create a tuple of two (or
> maybe even more) xts, and either you keep that tuple on stack,... or
> you want to create a concatenated version, which needs memory - when
> you do that with two numbers in Forth, it's the same, you need memory
> for that, too.

The corresponding thing with numbers is addition: 3 5 + creates a new
number 8 on the stack.  We get avoid memory management by requiring
every number to fit in a cell, so numbers can be passed on the stack,
stored in variables, etc. without the need for dynamic allocation.  In a
Forth with bignums that has to support the same operations, you'd need
GC or something like it.

> Sure, that would be stupid to do it that way.  Forth OOP works
> different, you allocate a piece of memory for the object's data,...
> That works pretty well within the concepts Forth provides, and doesn't
> work with the concepts Scheme provides you.

Right, you can do the same things with other mechanisms, which is why
the concept of first class functions wasn't widely known before Scheme
and is barely part of the mainstream even now.  But, like OOP, they
support a certain programming style that is attractive for some
situations even though alternatives exist.

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

#37567

Paul Rubin wrote:
> The corresponding thing with numbers is addition: 3 5 + creates a new
> number 8 on the stack.  We get avoid memory management by requiring
> every number to fit in a cell, so numbers can be passed on the stack,
> stored in variables, etc. without the need for dynamic allocation.  In a
> Forth with bignums that has to support the same operations, you'd need
> GC or something like it.

It's not addition, it's concatenation.  You concatenate two xts, creating a 
third xt, you still need the two xts inside that third xt.

If you don't have the abstract view of the xt, you understand that the xt is 
actually a pointer to memory.  And as Forth programmer, you know that each 
such operation will consume memory, which isn't automatically reclaimed.

>> Sure, that would be stupid to do it that way.  Forth OOP works
>> different, you allocate a piece of memory for the object's data,...
>> That works pretty well within the concepts Forth provides, and doesn't
>> work with the concepts Scheme provides you.
> 
> Right, you can do the same things with other mechanisms, which is why
> the concept of first class functions wasn't widely known before Scheme
> and is barely part of the mainstream even now.  But, like OOP, they
> support a certain programming style that is attractive for some
> situations even though alternatives exist.

For cases like higher order functions, you don't need the dynamic generation 
at run-time.  In Forth, the quotation shares the stack with the quotation 
caller, which can be functionally identical to the Scheme situation where 
the quotation shares the environment.  This requires that the higher order 
function itself doesn't leave internal stuff on the data stack when calling 
the function passed to it.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/
net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*

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

#37570

On Sunday, March 22, 2015 at 6:37:09 PM UTC-7, Bernd Paysan wrote:
> For cases like higher order functions, you don't need the dynamic generation 
> at run-time.  In Forth, the quotation shares the stack with the quotation 
> caller, which can be functionally identical to the Scheme situation where 
> the quotation shares the environment.  This requires that the higher order 
> function itself doesn't leave internal stuff on the data stack when calling 
> the function passed to it.

This is what I've been doing in the novice-package for years --- this is just a clumsy work-around for the lack of true quotations. This doesn't work very well because it requires that there be only one higher-order function and it is customized to do this, which isn't always going to be true. The user may call a function of his own, passing the xt into it, then that function calls my higher-order function (such as EACH in LIST.4TH) passing the xt to it --- only my higher-order function will be custom-written to hold its internal data on the return-stack, but the user's function won't be, and so the whole thing will fail. Another problem is that the higher-order function has to keep the same number of data on the data-stack before and after. So, if it is changing the data on the data-stack, it has to ROLL it forward, make the change, then ROLL it back into place --- this is is very awkward and hard to read --- local variables would be much better (see my TopRank code for an example of this: http://rosettacode.org/wiki/Top_Rank_Per_Group#Forth).

I remember that everybody was praising FFL and putting down my novice-package, so I looked at FFL's linked-list implementation and I discovered that its higher-order function (corresponding to my EACH) didn't hold its internal data on the return-stack when calling the quotation --- I pointed this out --- then the problem got fixed. I haven't checked the rest of FFL to find out if the problem was fixed throughout, or just in the linked-list code. I have no interest in FFL, as I'm way ahead of them.

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

#37571

Bernd Paysan <bernd.paysan@gmx.de> writes:
> If you don't have the abstract view of the xt, you understand that the
> xt is actually a pointer to memory.  And as Forth programmer, you know
> that each such operation will consume memory, which isn't
> automatically reclaimed.

Sure, that's why the practice of creating a lot of such xt's dynamically
isn't really common in Forth.  But suppose you have a numerical
zero-finding function using your favorite algorithm.  A stylistically
clean though unoptimized way to compute square roots in Haskell might
be:

  sqrt a = solve (\x -> x * x - a)

which creates a new function on the fly and passes it to the solver.
The solver might create new functions of its own, e.g. one using
Newton's method could create one mapping a function to its numerical
derivative.  

    derivative f x = (f (x+h) - f x) / h where h = 0.00001
    newton_step f x0 = x0 - (f x / f' x) where f' = derivative f

In Forth, this approach would probably be less convenient.

> For cases like higher order functions, you don't need the dynamic
> generation at run-time.  In Forth, the quotation shares the stack with
> the quotation caller, which can be functionally identical to the
> Scheme situation where the quotation shares the environment.

The quotation doesn't know if it might be called more than once or what
else might want to use its args, against the usual convention that
functions should consume their parameters.  Maybe it's ok to expect
quotations in this situation to ignore that convention and leave the
stack alone.  And you're left with the situation like "derivative"
above, where the HOF wants to return, leaving a callable xt behind.

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

#37585

Paul Rubin <no.email@nospam.invalid> writes:
>Bernd Paysan <bernd.paysan@gmx.de> writes:
>> If you don't have the abstract view of the xt, you understand that the
>> xt is actually a pointer to memory.  And as Forth programmer, you know
>> that each such operation will consume memory, which isn't
>> automatically reclaimed.
>
>Sure, that's why the practice of creating a lot of such xt's dynamically
>isn't really common in Forth.  But suppose you have a numerical
>zero-finding function using your favorite algorithm.  A stylistically
>clean though unoptimized way to compute square roots in Haskell might
>be:
>
>  sqrt a = solve (\x -> x * x - a)
>
>which creates a new function on the fly and passes it to the solver.
>The solver might create new functions of its own, e.g. one using
>Newton's method could create one mapping a function to its numerical
>derivative.  
>
>    derivative f x = (f (x+h) - f x) / h where h = 0.00001
>    newton_step f x0 = x0 - (f x / f' x) where f' = derivative f
>
>In Forth, this approach would probably be less convenient.

Why do you think so?  In this case, you get an additional derivative
definition for every word for which you want a derivative function,
i.e., a constant factor overhead.  Not really a problem.

Even for stuff where there is no limitation of this kind, it may still
be viable to allocate memory (e.g., for dynamically generated code)
and not free it.  E.g., there was an interesting paper about
combinators in Forth
<http://soton.mpeforth.com/flag/jfar/vol4/no4/article6.pdf> that uses
run-time code generation for implementing the combinators; so every
combinator call would generate some more code.  I ran this code on a
Commodore 64 with about 30KB of free memory, and I could run all the
examples from the paper, and did not really feel memory-constrained in
my own experiments: I only ran into the memory limitation when I did
things that I designed to run into the memory limitation.

Some other examples of successfully not worrying about storage
reclamation (but for data storage):

Gforth's interpretive S" allocates the string and never frees it.  No
complaints yet about the storage leak.

My parser generator Gray allocates and stores the sets it computes in
the dictionary, and never frees them.  Some of these sets are used by
the generated parser, others are just intermediate results used for
determining, e.g., conflicts.  The total memory consumed by the sets
for the largest grammar I tested with (Oberon) was IIRC 5KB.

>> For cases like higher order functions, you don't need the dynamic
>> generation at run-time.  In Forth, the quotation shares the stack with
>> the quotation caller, which can be functionally identical to the
>> Scheme situation where the quotation shares the environment.

I don't think it is functionally identical to the Scheme situation;
maybe to the pre-Scheme LISP situation (dynamic scoping).  E.g. you
have a hard time reproducing the objects-based-on-closures thingy with
non-closure quotations.  I think the reason is that there are many
different static environments, but only one stack, and one dynamic
"environment".

>The quotation doesn't know if it might be called more than once or what
>else might want to use its args, against the usual convention that
>functions should consume their parameters.

What makes you think that the quotation does not heed this convention?

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2014: http://www.euroforth.org/ef14/

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

#37599

In article <2015Mar23.123414@mips.complang.tuwien.ac.at>,
Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>Paul Rubin <no.email@nospam.invalid> writes:
>>Bernd Paysan <bernd.paysan@gmx.de> writes:
>>> If you don't have the abstract view of the xt, you understand that the
>>> xt is actually a pointer to memory.  And as Forth programmer, you know
>>> that each such operation will consume memory, which isn't
>>> automatically reclaimed.
>>
>>Sure, that's why the practice of creating a lot of such xt's dynamically
>>isn't really common in Forth.  But suppose you have a numerical
>>zero-finding function using your favorite algorithm.  A stylistically
>>clean though unoptimized way to compute square roots in Haskell might
>>be:
>>
>>  sqrt a = solve (\x -> x * x - a)
>>
>>which creates a new function on the fly and passes it to the solver.
>>The solver might create new functions of its own, e.g. one using
>>Newton's method could create one mapping a function to its numerical
>>derivative.
>>
>>    derivative f x = (f (x+h) - f x) / h where h = 0.00001
>>    newton_step f x0 = x0 - (f x / f' x) where f' = derivative f
>>
>>In Forth, this approach would probably be less convenient.
>
>Why do you think so?  In this case, you get an additional derivative
>definition for every word for which you want a derivative function,
>i.e., a constant factor overhead.  Not really a problem.
>
>Even for stuff where there is no limitation of this kind, it may still
>be viable to allocate memory (e.g., for dynamically generated code)
>and not free it.  E.g., there was an interesting paper about
>combinators in Forth
><http://soton.mpeforth.com/flag/jfar/vol4/no4/article6.pdf> that uses
>run-time code generation for implementing the combinators; so every
>combinator call would generate some more code.  I ran this code on a
>Commodore 64 with about 30KB of free memory, and I could run all the
>examples from the paper, and did not really feel memory-constrained in
>my own experiments: I only ran into the memory limitation when I did
>things that I designed to run into the memory limitation.
>
>Some other examples of successfully not worrying about storage
>reclamation (but for data storage):
>
>Gforth's interpretive S" allocates the string and never frees it.  No
>complaints yet about the storage leak.

I looked it up. In ciforth the " denotation for "NORMAL STRINGS" dates
from januari 3th 2001.
It ALLOTs the string and never frees is, same philosophy.

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

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

#37606

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>    derivative f x = (f (x+h) - f x) / h where h = 0.00001
>>    newton_step f x = x - (f x / f' x) where f' = derivative f
>>In Forth, this approach would probably be less convenient.
> Why do you think so?  In this case, you get an additional derivative
> definition for every word for which you want a derivative function,
> i.e., a constant factor overhead.  Not really a problem.

The derivative functions are per call, not per word.  E.g. if I call
sqrt(3), it creates the new function f(x)=x**2 - 3 and gives it to the
Newton solver, which calls the derivative HOF to create another new
function that is a numerical approximation of f'(x) = 2*x, so two new
functions were created.  Then if I call sqrt(5), it creates two more new
functions, and if my program computes a million square roots (not that
unusual), it ends up creating 2 million new functions (it can't tell
that the derivative functions are about the same for all of them).  It's
not optimized but it's mathematically expressive/convenient, and as you
say it's a constant factor overhead in computing time.  However, in a
non-GC'd system, creating 2 million new functions and leaving them
around is linear memory bloat, not good.  Therefore a less convenient
approach is probably required.

Better examples are in the Hughes paper that I linked in another post
just now.

> <http://soton.mpeforth.com/flag/jfar/vol4/no4/article6.pdf>...  I ran
> this code on a Commodore 64 with about 30KB of free memory, and I
> could run all the examples from the paper, and did not really feel
> memory-constrained in my own experiments: I only ran into the memory
> limitation when I did things that I designed to run into the memory
> limitation.

The paper says the program used 17k of memory to compute 6
factorial=720.  I think practical use of those methods will tend to
involve more computation and bigger numbers, so GC is needed.

>>The quotation doesn't know if it might be called more than once or what
>>else might want to use its args, against the usual convention that
>>functions should consume their parameters.
> What makes you think that the quotation does not heed this convention?

Because if it is called more than once and consumes its parameters, the
parameters are gone after the first call.  Am I missing something?

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

#37608

Paul Rubin wrote:

> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>>    derivative f x = (f (x+h) - f x) / h where h = 0.00001
>>>    newton_step f x = x - (f x / f' x) where f' = derivative f
>>>In Forth, this approach would probably be less convenient.
>> Why do you think so?  In this case, you get an additional derivative
>> definition for every word for which you want a derivative function,
>> i.e., a constant factor overhead.  Not really a problem.
> 
> The derivative functions are per call, not per word.  E.g. if I call
> sqrt(3), it creates the new function f(x)=x**2 - 3 and gives it to the
> Newton solver, which calls the derivative HOF to create another new
> function that is a numerical approximation of f'(x) = 2*x, so two new
> functions were created.  Then if I call sqrt(5), it creates two more new
> functions, and if my program computes a million square roots (not that
> unusual), it ends up creating 2 million new functions (it can't tell
> that the derivative functions are about the same for all of them).

Well, it's a stupid concept.  What you actually want is a parametrized 
function where you can change the parameter.  Forth can easily do that.  
Then you don't have to create full functions and throw them away after use.

Though, with marker, you just could do that.  Marker is just way more 
expensive than changing that one parameter.

> It's
> not optimized but it's mathematically expressive/convenient, and as you
> say it's a constant factor overhead in computing time.  However, in a
> non-GC'd system, creating 2 million new functions and leaving them
> around is linear memory bloat, not good.  Therefore a less convenient
> approach is probably required.

Or an approach where you just reuse that one created function when the 
parameter changes.  That wouldn't be "less convenient".

> The paper says the program used 17k of memory to compute 6
> factorial=720.  I think practical use of those methods will tend to
> involve more computation and bigger numbers, so GC is needed.

Well, seems to be an approach that is entirely counter all the traditions of 
Forth.  Just don't do that.  Find a way to do it elegantly, but without the 
bloat.

>>>The quotation doesn't know if it might be called more than once or what
>>>else might want to use its args, against the usual convention that
>>>functions should consume their parameters.
>> What makes you think that the quotation does not heed this convention?
> 
> Because if it is called more than once and consumes its parameters, the
> parameters are gone after the first call.  Am I missing something?

You seem to be particularly slow on that, so let's slow down and explain it 
slowly, maybe by example.  We have this traverse-wordlist higher order 
funktion.  It takes an xt, and passes the nt to that xt, and returns a flag 
for early termination (true to continue, i.e. ( nt -- flag )).  The stack 
underneath can be used by that xt.  So if I want to count the number of 
words in a dictionary, I do

: count-wl ( wordlist -- n )  0 [: drop 1+ true ;] rot traverse-wordlist ;

get-current count-wl . 1908  ok

(in Gforth).

You can use this part of the stack for whatever you want.  E.g. if you want 
to implement tab-completion, your function could check for a prefix and 
return a list of words which have that prefix.  That list would be 
accumulated on the stack.

So you have a combination of transient parameters, which exist for one call 
and are gone after that call, and persistent parameters, which the function 
can use but must keep (maybe updated).

Maybe you think of a Forth word as a word with one return value, like a Lisp 
function.  That's not the case.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/
net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*

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

#37614

Bernd Paysan <bernd.paysan@gmx.de> writes:
> Well, it's a stupid concept.  What you actually want is a parametrized 
> function where you can change the parameter.

That's an implementation technique.  The wanted concept is separate
functions.  Paramatrizing a single function is one way to implement it.
Coding it directly and letting the compiler handle it is another.

> Or an approach where you just reuse that one created function when the
> parameter changes.  That wouldn't be "less convenient".

The Chuck Moore approach to programming is code to solve your immediate
problem, and then rewrite the code if you want to solve a slightly
different problem.  But even Forth has re-usable design patterns, like
the data stack, that aren't always used optimally: sometimes the
convention of words consuming their parameters costs you a few extra
pushes, but we generally follow it to keep the code understandable.
Lisp, Scheme and their descendants have shown HOFs and GC are also
patterns that make the programmer's job easier at the cost of some CPU
cycles.  The benefits make themselves felt more as the programs get more
complicated: Anton's paper on Forth GC starts with one of the better
explanations that I've seen.

In the examples I gave, the HOF approach allowed using the same code for
multiple problems, which would have been required rewriting with the
manual approach.

>> The paper says the program used 17k of memory to compute 6
>> factorial=720.
> Well, seems to be an approach that is entirely counter all the
> traditions of Forth.  Just don't do that.

That was Anton saying he ran those programs on a C64.

> Find a way to do it elegantly, but without the bloat.

GC eliminates the bloat, completely behind the scenes.  Your program
doesn't have to show a trace of concern about it.  You just write your
mathematical thoughts from the clean pure light, and the compiler
carries them out.  What could be more elegant than that?

> : count-wl ( wordlist -- n )  0 [: drop 1+ true ;] rot traverse-wordlist ;
> ... So you have a combination of transient parameters, which exist for
> one call and are gone after that call, and persistent parameters,
> which the function can use but must keep (maybe updated).

OK, that handles a reasonable and useful set of cases.

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

#37751

On Monday, March 23, 2015 at 4:38:56 PM UTC-7, Bernd Paysan wrote:
> Paul Rubin wrote:
> 
> > anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> >>>    derivative f x = (f (x+h) - f x) / h where h = 0.00001
> >>>    newton_step f x = x - (f x / f' x) where f' = derivative f
> >>>In Forth, this approach would probably be less convenient.
> >> Why do you think so?  In this case, you get an additional derivative
> >> definition for every word for which you want a derivative function,
> >> i.e., a constant factor overhead.  Not really a problem.
> > 
> > The derivative functions are per call, not per word.  E.g. if I call
> > sqrt(3), it creates the new function f(x)=x**2 - 3 and gives it to the
> > Newton solver, which calls the derivative HOF to create another new
> > function that is a numerical approximation of f'(x) = 2*x, so two new
> > functions were created.  Then if I call sqrt(5), it creates two more new
> > functions, and if my program computes a million square roots (not that
> > unusual), it ends up creating 2 million new functions (it can't tell
> > that the derivative functions are about the same for all of them).
> 
> Well, it's a stupid concept.  What you actually want is a parametrized 
> function where you can change the parameter.  Forth can easily do that.  
> Then you don't have to create full functions and throw them away after use.
> ...
> > Because if it is called more than once and consumes its parameters, the
> > parameters are gone after the first call.  Am I missing something?
> 
> You seem to be particularly slow on that, so let's slow down and explain it 
> slowly, maybe by example.  We have this traverse-wordlist higher order 
> funktion.  It takes an xt, and passes the nt to that xt, and returns a flag 
> for early termination (true to continue, i.e. ( nt -- flag )).  The stack 
> underneath can be used by that xt.  So if I want to count the number of 
> words in a dictionary, I do
> 
> : count-wl ( wordlist -- n )  0 [: drop 1+ true ;] rot traverse-wordlist ;
> 
> get-current count-wl . 1908  ok
> 
> (in Gforth).

Bernd is still fixated on calling people stupid.

He is also still just faking his quotations. What he has here is no better than what I have in my novice-package. Bernd uses TRAVERSE-WORDLIST as an example of a higher-order function, and I use EACH (from LIST.4TH) as an example of a higher-order function --- the difference is that I admit that writing EACH was complicated because it had to hide its internal parameters on the return-stack so they wouldn't cover up the user's data on the data-stack --- Bernd never mentions this complication (he is hoping that the users will never write any higher-order functions themselves, but will just use the handful that he has written such as TRAVERSE-WORDLIST, and won't realize what a mess the higher-order functions are internally).

Bernd doesn't just like to call people stupid --- his position as a member of the Forth-200x committee depends upon everybody actually being stupid --- as Forest Gump would say: "Stupid is as stupid does".

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

#37752

On Monday, March 30, 2015 at 5:02:37 AM UTC-7, hughag...@gmail.com wrote:
> He is also still just faking his quotations. What he has here is no better than what I have in my novice-package. Bernd uses TRAVERSE-WORDLIST as an example of a higher-order function, and I use EACH (from LIST.4TH) as an example of a higher-order function --- the difference is that I admit that writing EACH was complicated because it had to hide its internal parameters on the return-stack so they wouldn't cover up the user's data on the data-stack --- Bernd never mentions this complication (he is hoping that the users will never write any higher-order functions themselves, but will just use the handful that he has written such as TRAVERSE-WORDLIST, and won't realize what a mess the higher-order functions are internally).

I'm being generous when I say that Bernd has written a "handful" of higher-order functions --- afaik, TRAVERSE-WORDLIST is the only one he has ever written --- he trots out this same example every time the subject comes up.

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

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

Back to top | Article view | comp.lang.forth

csiph-web