Chris Double — 2004-06-02 23:13:30

(I searched the archives and couldn't see a discussion related to this.
Apologies if it has been discussed)

Paul Graham poses a problem with example solutions in various programming
languages:

http://www.paulgraham.com/accgen.html

What would a solution in a concatenative language like Joy or Factor look
like? I tried my hand at Factor and got:

: adder ( n -- adder ) <namespace> swap over [ "n" swap put "call" [ "n"
get + dup "n" swap put ] put ] bind ;
: adder-call ( adder -- v ) [ "call" get call ] bind ;

5 adder
2 over adder-call .
=> 7
3 over adder-call .
=> 10

The downside is the needed 'adder-call' rather than a standard call. Any
other approaches to this type of problem or simulating 'closures' in
general?

Chris.
--
Chris Double
chris.double@...

Ivan Tomac — 2004-06-03 04:23:09

Hi Chris,

I'm not 100% sure if my solution in Joy meets all the requirements of
the challanage but here it is:

acc == [uncons [+ dup] dip dup [cons] dip cons] dup [cons] dip cons

to test it type something like:

1 acc 2 swap i 3 swap i 4 swap i pop stack.

Ivan

--- In concatenative@yahoogroups.com, "Chris Double"
<chris.double@d...> wrote:

> (I searched the archives and couldn't see a discussion related to

this.

> Apologies if it has been discussed)
>
> Paul Graham poses a problem with example solutions in various

programming

> languages:
>
> http://www.paulgraham.com/accgen.html
>
> What would a solution in a concatenative language like Joy or Factor

look

> like? I tried my hand at Factor and got:
>
> : adder ( n -- adder ) <namespace> swap over [ "n" swap put "call"

[ "n"

> get + dup "n" swap put ] put ] bind ;
> : adder-call ( adder -- v ) [ "call" get call ] bind ;
>
> 5 adder
> 2 over adder-call .
> => 7
> 3 over adder-call .
> => 10
>
> The downside is the needed 'adder-call' rather than a standard

call. Any

> other approaches to this type of problem or simulating 'closures' in
> general?
>
> Chris.
> --
> Chris Double
> chris.double@d...

Ivan Tomac — 2004-06-03 04:40:47

After digging a bit through the archives I found the post with Nick
Forde's original solution in Joy:

http://groups.yahoo.com/group/concatenative/message/1407

Ivan

--- In concatenative@yahoogroups.com, "Ivan Tomac" <e1_t@y...> wrote:
> Hi Chris,
>
> I'm not 100% sure if my solution in Joy meets all the requirements of
> the challanage but here it is:
>
> acc == [uncons [+ dup] dip dup [cons] dip cons] dup [cons] dip cons
>
> to test it type something like:
>
> 1 acc 2 swap i 3 swap i 4 swap i pop stack.
>
> Ivan
>
> --- In concatenative@yahoogroups.com, "Chris Double"
> <chris.double@d...> wrote:
> > (I searched the archives and couldn't see a discussion related to
> this.
> > Apologies if it has been discussed)
> >
> > Paul Graham poses a problem with example solutions in various
> programming
> > languages:
> >
> > http://www.paulgraham.com/accgen.html
> >
> > What would a solution in a concatenative language like Joy or Factor
> look
> > like? I tried my hand at Factor and got:
> >
> > : adder ( n -- adder ) <namespace> swap over [ "n" swap put "call"
> [ "n"
> > get + dup "n" swap put ] put ] bind ;
> > : adder-call ( adder -- v ) [ "call" get call ] bind ;
> >
> > 5 adder
> > 2 over adder-call .
> > => 7
> > 3 over adder-call .
> > => 10
> >
> > The downside is the needed 'adder-call' rather than a standard
> call. Any
> > other approaches to this type of problem or simulating 'closures' in
> > general?
> >
> > Chris.
> > --
> > Chris Double
> > chris.double@d...

Slava Pestov — 2004-06-03 20:44:34

Ivan Tomac wrote:

> Hi Chris,
>
> I'm not 100% sure if my solution in Joy meets all the requirements of
> the challanage but here it is:
>
> acc == [uncons [+ dup] dip dup [cons] dip cons] dup [cons] dip cons

This works in Factor too. The only thing you have to change is the word
definition syntax, and adding whitespace around [ and ]:

: acc
[ uncons [ + dup ] dip dup [ cons ] dip cons ] dup
[ cons ] dip cons ;

In practice, I avoid writing functions that return new functions.

Slava

Chris Double — 2004-06-03 22:17:19

On Thu, 03 Jun 2004 04:23:09 -0000, "Ivan Tomac" <e1_t@...> said:

>
> acc == [uncons [+ dup] dip dup [cons] dip cons] dup [cons] dip cons
>

That does it, thanks! It works in Factor too. I missed the previous
discussion on the list. I tried the search feature on yahoo groups and it
failed to pick it up.

Chris.
--
Chris Double
chris.double@...

Chris Double — 2004-06-03 22:35:22

On Thu, 03 Jun 2004 16:44:34 -0400, "Slava Pestov" <slava@...>
said:

> In practice, I avoid writing functions that return new functions.

Why is that? Or are functions that 'capture state' an example of the type
of thing that needs to return new functions? I wrote a 'generator'
function in Factor to traverse a tree. Given a tree calling the generator
function will return a function that when called will return the leaves
of the tree in order:

[ 1 2 [ 3 4 ] 5 ] tree->generator
=> a-function

call .
=> 1
call .
=> 2
call .
=> 3
call .
=> 4
call .
=> 5

I did this by having the generated function return the continuation to
call to resume the function and the value of the tree. I couldn't think
of a way to do this without having the function value returned. Any
thoughts on a better interface for the generator function?

BTW, this was working through a Scheme exercise, translating it to
Factor. It's the 'Same Fringe' problem:
http://c2.com/cgi/wiki?SameFringeProblem

My basic example without continuations flattened the trees and compared
for equality. The idea for this one was to use co-routines to go through
the trees one by one and return on the first in-equality, avoiding the
need to cons up and flatten the tree.

Chris.
--
Chris Double
chris.double@...

Slava Pestov — 2004-06-03 23:18:28

I think a better solution to this would be to write a word tree-each (
tree code -- ) that is like 'each' but recursive. Then you could do, for
example:

[ . ] tree-each

Note that tree->generator can be implemented in terms of tree-each and
continuations. Having the more primitive tree-each word available is an
advantage because continuation-using code cannot be compiled.

Chris Double wrote:

> On Thu, 03 Jun 2004 16:44:34 -0400, "Slava Pestov" <slava@...>
> said:
>
>>In practice, I avoid writing functions that return new functions.
>
>
> Why is that? Or are functions that 'capture state' an example of the type
> of thing that needs to return new functions? I wrote a 'generator'
> function in Factor to traverse a tree. Given a tree calling the generator
> function will return a function that when called will return the leaves
> of the tree in order:
>
> [ 1 2 [ 3 4 ] 5 ] tree->generator
> => a-function
>
> call .
> => 1
> call .
> => 2
> call .
> => 3
> call .
> => 4
> call .
> => 5
>
> I did this by having the generated function return the continuation to
> call to resume the function and the value of the tree. I couldn't think
> of a way to do this without having the function value returned. Any
> thoughts on a better interface for the generator function?
>
> BTW, this was working through a Scheme exercise, translating it to
> Factor. It's the 'Same Fringe' problem:
> http://c2.com/cgi/wiki?SameFringeProblem
>
> My basic example without continuations flattened the trees and compared
> for equality. The idea for this one was to use co-routines to go through
> the trees one by one and return on the first in-equality, avoiding the
> need to cons up and flatten the tree.
>
> Chris.

Chris Double — 2004-06-04 01:40:48

On Thu, 03 Jun 2004 19:18:28 -0400, "Slava Pestov" <slava@...>
said:

> I think a better solution to this would be to write a word tree-each (
> tree code -- ) that is like 'each' but recursive.

Here's my attempt at tree-each in Factor:

: tree-each ( [ tree ] [ quotation ] -- )
over [
over cons? [

>r uncons r> tuck [ tree-each ] 2dip tree-each

] [
call
] ifte
] [
2drop
] ifte ;

[ 1 2 [ 3 4 ] 5 ] [ . ] tree-each

Regarding formatting code, is the nesting approach above the generally
preferred way to present it?

I can't the above to compile in 0.58 though. I do:

"tree-each" compile
"tree-each" worddef compiled? .
=> f

Is there something I'm doing that's preventing the compilation? Or am I
using an incorrect check to see if it is compiled?

Chris.
--
Chris Double
chris.double@...

Slava Pestov — 2004-06-04 01:53:19

Hi,

Nicely done!

The reason it doesn't compile is because it is a higher-order word. Only
specific *instances* of higher order words compile. For example, the
following word compiles:

: tree-each-test [ drop ] tree-each ;

To find out why a word doesn't compile, enable verbose compilation:

t "verbose-compile" set

Although the error messages are quite cryptic right now.

Do you want me to include this word in the library?

Slava

On Thu, 03 Jun 2004 21:53:19 -0400, "Slava Pestov" <slava@...>
said:

>
> Nicely done!

Thanks!

> Do you want me to include this word in the library?

Sure, that'd be great.

Chris.
--
Chris Double
chris.double@...

Paul Grahams Accumulator