lambda + currying (bigforth gforth question)

[pliz]

Hi,

I am trying to treat words as first class objects by defining words
inside other words and returning their xts. For gforth's:

: :[ postpone ahead :noname ; immediate
: ]; postpone ; ] >r postpone then r> postpone literal ; immediate

and bigforth's lambda.fs

I want to
: test ( -- xt ) :[ 0 do i . loop ]; ;
10 test execute

Now instead I want to pass a value to test that gets compiled into the
returned word. Something like
: test ( n -- xt ) :[ *n* 0 do i . loop ]; ;

How it is usually done? I can't figure out the way with does> since I
want no named words but just lambda functions.

Thank you!

--
Sergey

[m_l_g3]

pliz:

I have seen such a system, it used dynamic compilation and garbage
collection of the generated code. It was not exactly what you want to
do.

So:

: PASS >R ' EXECUTE R> ; IMMEDIATE
: PLEASE" POSTPONE S" POSTPONE EVALUATE ; IMMEDIATE
: test ( n -- xt ) PLEASE" PASS :NONAME LITERAL 0 do i . loop ; " ;
or
: curry ( n xt -- xt' ) 2>R :NONAME 2R> SWAP POSTPONE LITERAL COMPILE,
POSTPONE ; ;
and this *leaves garbage in the dictionary*.

Gforth 0.6.2[...]
: curry ( n xt -- xt' ) 2>R :NONAME 2R> SWAP POSTPONE LITERAL COMPILE,
POSTPONE ; ; ok
: t S" hello, world!" ; ok
t ' type curry curry ok
.s <1> 140273906899296 ok
constant .hw ok
.hw execute hello, world! ok

It's interesting to look at what vfx does:

: [compile,] compile, ; immediate ok
: PASS >R ' EXECUTE R> ; IMMEDIATE ok
: curry ( n xt -- xt' ) 2>R :NONAME 2R> SWAP POSTPONE LITERAL COMPILE,
POSTPONE ; ; ok
ok
10 ' + curry pass : 10+ [compile,] ; ok
see 10+
10+
( 0049EC10 E8CFFFFFFF ) CALL 0049EBE4
( 0049EC15 C3 ) NEXT,
( 6 bytes, 2 instructions )
ok
$0049EBE4 (dis)
CURRY
( 0049EBE4 83C30A ) ADD EBX, 0A
( 0049EBE7 C3 ) NEXT,
( 4 bytes, 2 instructions )
ok

[Josh Grams]

I don't see how that would work: don't they happen at different times?

The lambda is compiled at the same time that `test` is compiled, but you
don't get the value for the literal until `test` is executed/interpreted.

--Josh

[Jeff M.]

Oddly enough I've been working on doing the exact same thing. I don't
quite have it working yet (been busy with other things first), but my
inclination was to use CREATE DOES> with any ol' xt, Instead of trying
to embed the argument into the lambda, the idea would be that a
wrapper word would first push the arguments and then execute
the :NONAME xt. Untested pseudo-code:

: @+ ( addr -- addr' x ) ... ;

\ Premise: LAMBDA will take an XT and ARGC arguments off the
\ stack and save them in memory in a CREATE DOES>
\ object. When called, the arguments will be put back
\ onto the stack and the XT will be executed.

: lambda ( <name> xt argc -- )
create tuck , , 0 ?do , loop
does> @+ >r @+ 0 ?do @+ swap loop ;

: print ( c-addr -- ) count type ;

c" Hello!" ' print lambda say-hi
c" Bye!" ' print lambda say-bye

Of course, the limitation here is that the "anonymous" functions have
to be named (because of CREATE), but I'm sure there's a simple work-
around for that to where the XT for the LAMBDA could be returned
instead, and still keep all the DOES> functionality. It might also be
faster (better?) to break LAMBDA up into multiple definitions that
know the ARGC of itself (lambda0, lambda1, etc).

Jeff M.

[Jeff M.]

On Oct 22, 5:38 pm, "Jeff M." <mass...@gmail.com> wrote:
> On Oct 22, 2:13 pm, pliz <s.m.p...@gmail.com> wrote:
>
>
>
> > Hi,
>
> > I am trying to treat words as first class objects by defining words
> > inside other words and returning their xts. For gforth's:
>
> > : :[  postpone ahead :noname ; immediate
> > : ];  postpone ; ] >r postpone then r> postpone literal ; immediate
>
> > and bigforth's lambda.fs
>
> > I want to
> > : test ( -- xt ) :[ 0 do  i . loop ]; ;
> > 10 test execute
>
> > Now instead I want to pass a value to test that gets compiled into the
> > returned word. Something like
> > : test ( n -- xt ) :[ *n* 0 do i . loop ]; ;
>
> > How it is usually done? I can't figure out the way with does> since I
> > want no named words but just lambda functions.
>
> Oddly enough I've been working on doing the exact same thing. I don't
> quite have it working yet (been busy with other things first), but my

> inclination was to use CREATE DOES> with any ol' xt, ....

I forgot to mention this disclaimer:

I'm doing this strictly out of the curiosity of "can I?" Forth doesn't
garbage collect (natively) and if you got this working in some context
where :[ and ]; was working at runtime you'd be growing the dictionary
continuously until you ran out of memory.

Also, my CREATE DOES> idea is absolutely dumb outside the context of
getting it working at runtime. If I wanted "named" functions like what
my example code did, CREATE DOES> all by itself excepting a c-addr and
doing the COUNT TYPE would work just as well and have no ill side-
effects.

Bottom line: aside from doing it to do it, do you have a major need
for anonymous functions in Forth that could perhaps be accomplished
another way?

Jeff M.

[pliz]

Thank you everyone for suggestions. I am interested in learning how
these sorts of things get done. Maybe when factor collections are
implemented in forth the proper way these things can be easy and
fast :)

On Oct 22, 4:51 pm, "Jeff M." <mass...@gmail.com> wrote:
> Bottom line: aside from doing it to do it, do you have a major need
> for anonymous functions in Forth that could perhaps be accomplished
> another way?

Here is a chunk of code (not self contained) where (in ]]:[) I was
thinking to use something like that:

\ represent matrix data as a vector
: (]]![) ( A[[ -- c[ ) dup ]]data swap ]]dim * pvector ; \ in place
: ]]copy] ( a[ A[[ -- ) (]]![) tuck ]copy] ]free ;
: (]][) ( A[[ -- c[ ) dup ]]dim * :]# dup rot ]]copy] ; \ new copy
: preslice ( A[[ a[ i -- c[ ) rot ]]size2 dup >r * r> ]slice ;
: ]copy]] ( A[[ a[ -- )
over ]]size1 0 do
2dup over swap i preslice
tuck i ]'>]] ]free
loop 2drop ;
\ rowstack used when matrix values need to be modified
: ]]:[ ( A[[ -- c[ xt )
dup ]]contiguous? if
(]]![)
:[ ]free drop ];
else
]]clone dup (]][) swap ]]free
:[ tuck ]copy]] ]free ];
then ;
: ]]map ( m[[ xt -- ) >r dup ]]:[ over r> ]map execute ;

Thanks!

--
Sergey

[Gerry]

Another oddly enough (see Jeff M's reply), I published some code last
May that did this in ANS Forth and am in the process of revising it
and just about finished. The first attempt used text preprocessing.
The latest version uses 2 passes over the definition (using SAVE-INPUT
and RESTORE-INPUT) to compile the lambdas as separate :noname
definitions. To take your example you would write:

:lam test ( n -- ex ) {< a >} [: a 0 do i . loop ;] ;lam ok
10 test constant t1 ok
t1 exec 0 1 2 3 4 5 6 7 8 9 ok
5 test constant t2 ok
t2 exec 0 1 2 3 4 ok
t1 exec 0 1 2 3 4 5 6 7 8 9 ok

If you're interested I can email a copy. It takes quite a lot of code
to achieve the above, a lot more that bigforth's lambda.fs but then
it's in ANS Forth and does more.

Gerry

[pliz]

On Oct 22, 11:02 pm, "Gerry" <ge...@jackson9000.fsnet.co.uk> wrote:
> If you're interested I can email a copy. It takes quite a lot of code
> to achieve the above, a lot more that bigforth's lambda.fs but then
> it's in ANS Forth and does more.

I am interested. Please email it to me (email is in user info).

Thanks!

--
Sergey

[Gerry]

I've emailed it to your gmail address, the only one I could find. Let
me know if you don't receive it

Gerry

[Anton Ertl]

pliz <s.m....@gmail.com> writes:
>Now instead I want to pass a value to test that gets compiled into the
>returned word. Something like
>: test ( n -- xt ) :[ *n* 0 do i . loop ]; ;
>
>How it is usually done? I can't figure out the way with does> since I
>want no named words but just lambda functions.

: test1 0 do i . loop ;

: test ( n -- xt )

>r :noname r> postpone literal postpone test1 postpone ; ;

Or, using the ]] ... [[ construct to avoid POSTPONE clutter:

: test ( n -- xt )

>r :noname r> ]] literal test1 ; [[ ;

And while we are at using non-standard extentions, here's the
CREATE...DOES> variant:

: test2 does> @ test1 ;
: test noname create , test2 lastxt ;

Downside of all variants: Every time you invoke test, you consume a
bit of dictionary.

- 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 2009: http://www.euroforth.org/ef09/

[Anton Ertl]

m_l_g3 <m_l...@yahoo.com> writes:
>: PASS >R ' EXECUTE R> ; IMMEDIATE
>: PLEASE" POSTPONE S" POSTPONE EVALUATE ; IMMEDIATE
>: test ( n -- xt ) PLEASE" PASS :NONAME LITERAL 0 do i . loop ; " ;

That's not only longer than the correct version, it's also buggy:

: PASS >R ' EXECUTE R> ; IMMEDIATE
: PLEASE" POSTPONE S" POSTPONE EVALUATE ; IMMEDIATE
: test ( n -- xt ) PLEASE" PASS :NONAME LITERAL 0 do i . loop ; " ;

\ if TEST is correct, the following has no effect:
: PASS abort ;

Let's see what happens:

5 test execute
in file included from *the terminal*:7
*evaluated string*:-1: Aborted

PASS :NONAME LITERAL 0 do i . loop ;

^^^^

[Anton Ertl]

"Jeff M." <mas...@gmail.com> writes:
>I'm doing this strictly out of the curiosity of "can I?" Forth doesn't
>garbage collect (natively) and if you got this working in some context
>where :[ and ]; was working at runtime you'd be growing the dictionary
>continuously until you ran out of memory.

Yes, but that point may be later than you think, and your job may long
be finished by then. We don't worry too much about data memory
growing with data set size, either, do we?

In particular, I first encountered using Forth run-time code
generation for this stuff when I read:

@Article{belinfante87,
author = "Johan G.F. Belinfante",
title = "S/K/ID: Combinators in Forth",
journal = jfar,
year = "1987",
volume = "4",
number = "4",
pages = "555--580"
}

Every invocation of a combinator generates a new colon definition, and
in the programs shown almost everything is done through combinators
(including, e.g., if-then-else). I ran this code on a Commodore 64
(where I had about 32K of free RAM), and expected to run out of memory
even on small examples, but got surprisingly far before that happened.

[Hugh Aguilar]

On Oct 22, 11:02 pm, "Gerry" <ge...@jackson9000.fsnet.co.uk> wrote:

> If you're interested I can email a copy. It takes quite a lot of code
> to achieve the above, a lot more that bigforth's lambda.fs but then
> it's in ANS Forth and does more.
>
> Gerry

I would be interested too. If you can email me a copy, I would
appreciate that.

[Gerry]

I had other requests for it so I've put it on this web site
http://www.qlikz.org/forth/library/lambda.html

Gerry

[Anton Ertl]

pliz <s.m....@gmail.com> writes:

>On Oct 22, 4:51=A0pm, "Jeff M." <mass...@gmail.com> wrote:
>> Bottom line: aside from doing it to do it, do you have a major need
>> for anonymous functions in Forth that could perhaps be accomplished
>> another way?
>
>Here is a chunk of code (not self contained) where (in ]]:[) I was
>thinking to use something like that:

[code elided]

Could you add some explanations why you need anonymous functions here?
What would be the alternatives, and why are they worse? And, to make
the rest understandable, what's this code about?

Here's one example I have: Reusable code often needs CATCH to ensure
that all exits from a word go through some common cleanup code. CATCH
takes an xt, and in Forth-94 that often leads to adding a helper
definition, e.g.:

: hex.-helper ( u -- )
hex u. ;

: hex. ( u -- )
base @ >r
['] hex.-helper catch
r> base ! throw ;

With :[ ... ]; (or similar syntax) we can put the helper definition
right where it is used, and don't need to name it:

: hex. ( u -- )
base @ >r
:[ hex u. ]; catch
r> base ! throw ;

Shorter, and IMO easier to read.

[Anton Ertl]

pliz <s.m....@gmail.com> writes:
>Now instead I want to pass a value to test that gets compiled into the
>returned word. Something like
>: test ( n -- xt ) :[ *n* 0 do i . loop ]; ;

That's full closures.

The first idea would be to have a Forth system that allows access to
locals from within an enclosed definition. The problem is that this
is very expensive to implement: in the general case it requires
garbage collection frames or locals.

Another idea is to use run-time code generation:

: test1 0 do i . loop ;

: test ( n -- xt )

>r :noname r> postpone literal postpone test1 postpone ; ;

The disadvantage is that this leaves the anonymous definition in the
dictionary, with no easy way to reclaim that memory. A more involved
example of this technique can be found in

http://www.complang.tuwien.ac.at/forth/queens.fs

Then, you can build your own closure frames, pass them around, and use
whatever memory allocation method you want for these frames.
E.g. (untested):

: curry ( w xt -- frame )
2 cells allocate throw dup >r 2! r> ;

: call ( ... frame -- ... )
2@ execute ;

: test ( n -- frame )
:[ 0 do i . loop ]: curry ;

5 test call

>How it is usually done?

I don't think there is a usual solution for this. The solutions
outlinesd above are not frequent in Forth. My guess is that in the
most common cases where Forth programmers actually want to do this
kind of stuff, they define a CREATE...DOES> word, and give each word
generated by that word a different name; of course, that does not work
well if you want to invoke TEST in a loop or otherwise as a
lower-level word.

[pliz]

On Oct 27, 6:02 am, an...@mips.complang.tuwien.ac.at (Anton Ertl)
wrote:

> Could you add some explanations why you need anonymous functions here?
> What would be the alternatives, and why are they worse?  And, to make
> the rest understandable, what's this code about?

First, thank you for the examples in this and in the next email. I
will need a bit more free time to look at them carefully, but I think
your example code generation in the next email is what I was asking
for. Gerry's lambda package also does what I wanted, but I have not
have time to look inside how exactly it is done. The good part
compared to what you suggest in your next message - dictionary is not
polluted and generated lambdas can be reclaimed as needed by the
programmer (no need to GC).

The example that motivated me to ask the question was the following:

- I am taking a matrix slice of a multidimensional array
- It may either end up as a continuous chunk of memory or as a
collection of equispaced chunks
- I represent this matrix as a vector:
- if continuous it is easy - just treat the same memory as a vector
not a matrix
- if fractioned - copy to new place and treat as vector
- I apply different functions to this vector (there are many of these)
- At the end I either need to
- copy the vector back into the matrix and free the vector
or
- just free the vector

The example I have posted previously would leave it for each of the
functions applied to vector to take care of passing both the vector
and the matrix to the clean up function I am returning from code that
turns matrix into a vector: two different clean up procedures are
possible. This makes the code of functions look dirty. With Gerry's
package I would prepare the returned functions so that they are self
contained and need no parameters. This would make all further code
cleaner and easier to read.

Well, I will need to invest some time into studying your examples and
Gerry's code.

--
Sergey

[pliz]

On Oct 23, 2:00 am, Gerry <ge...@jackson9000.fsnet.co.uk> wrote:
...

Interesting code which does what I needed, only your mini oof can
conflict with the oof.fs of bigforth or gforth I assume. Will think
about how to encapsulate it all into vocabularies to avoid the
conflicts.

Reading your explanations about how you do the job in two passes I
immediately recalled this:

http://en.wikipedia.org/wiki/Stalin_%28Scheme_implementation%29

In fact, I wonder why no one yet has done such thing for forth. Seems
like a very good idea for applications requiring efficiency. I mean,
write and debug the code using regular forth single pass compiler but
then aggressively optimize it before running. I use code to run
simulations and this approach is very attractive.

--
Sergey

[Anton Ertl]

pliz <s.m....@gmail.com> writes:
>In fact, I wonder why no one yet has done such thing for forth. Seems
>like a very good idea for applications requiring efficiency. I mean,
>write and debug the code using regular forth single pass compiler but
>then aggressively optimize it before running.

Well, Gforth has the debugging engine (gforth) and the benchmarking
engine (gforth-fast); but gforth-fast still compiles faster and rund
benchmarks slower than, say, VFX or iforth (actually, gforth-fast
probably compiles faster than gforth).

In general, people don't like running code on a different compiler
than they one they developed on (and not just in Forth). First, they
often utilize some specific features of this particular compiler, and
don't want to rewrite the program for more portability.

Even if they think they wrote portable code, they have extensively
tested on one compiler, and who knows if the code will work as well on
another compiler.

If they have a good test suite, it's not that hard to check that on
the other compiler, but what happens if it reveals a problem? The
other compiler compiles slowly, and since it is written for ultimate
speed, not for ease of debugging, it's hard to find out what the
problem is. So typically after the first found problem the idea of
porting to this compiler is abandoned. As a result, this compiler
never gets as many bug reports and feedback as the simpler ones, even
though it needs more (because it has more complex optimizations).

I have seen the idea of a compiler that runs for a long time to
produce excellent code proposed many times (not in Forth, for other
languages), but very few such compilers exist in reality, and I don't
think they are used much. In the above you see my explanation for
this.

[Charles Turner]

On Nov 8, 2:47 pm, an...@mips.complang.tuwien.ac.at (Anton Ertl)
wrote:

> languages), but very few such compilers exist in reality, and I don't
> think they are used much.

Stalin is well worth a test drive for anyone curious about slow,
highly optimizing compilers.

Best, C