sa@dfa.com — 2003-05-05 15:04:59

paul should get an award for writing the most baffling specification
of a simple problem ever. i think what he's after is a function which
takes a number, adds it to a state, and then returns that state. so
if acc is such a function, generated with initial state 0, then

acc 3
3 / state is now 3
acc 4
7 / state is now 7
acc 2
9 / state is now 9

additionally, he wants you to write the generator function:

acc:gen 0

so you need both first class functions to write gen, and closures (or
something equivalent) to write acc.

i don't think you need, or even want, global assignment to solve this
problem, since then other programs could mess with acc's state.

[ for k lurkers:

if k had closures, written

f:{[closure:initial] ...

then we could define acc something like this:

acc:{[k:0]k+:x} / return incremented closure k

and gen like this:

gen:{[n]{[k:n]k+:x}} / define: return incremented closure k, k
initialized to n

but it doesn't, so we can't ]

On Mon, 28 Apr 2003, Nick Forde wrote:

[..]

> This is actually very similar to a problem I was pondering over the
> weekend. I was reading a bit about Paul Graham's programming language
> Arc (http://www.paulgraham.com/arcfaq.html) and came across his
> Accumulator Generator challenge:
>
> "Write a function foo that takes a number n and returns a function
> that takes a number i, and returns n incremented by i. Note: (a)
> that's number, not integer, (b) that's incremented by, not plus."

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

I found the specification of the problem quite inscrutable, and
eventually understood it only when I read some of the solutions
in various languages. Apparantly I am not alone:

In the "listbox archives" at htp://www.kx.com/listbox.k/msg05906.html
I found what confirmed my reaction:
[...]
Similarly the input is ambiguous, is "number n" a variable of type number;
or s
uch a variable _and_ an initial value; or just an initial value and use a
priva
te storage location (forget he even mentioned "n")? i suppose there is a
better
language to state problems in than English... Clearly a lot of other
people ha
d much less difficulty deciding what the heck he means than i. So maybe
this is
just one of my dense days. Or maybe it is just a chance for all us
language bi
gots to show off our best -- In which case i prefer
[...]
greg heil
[END OF QUOTE]

First, "returns a function": that rules out languages which do not treat
functions as first class values. Next, "number, not integer": that
requires not too-rigid-typing. Then, "incremented, not plus": only when I
read the imperative "set!" in the Scheme version did it become clear to me
what he had in mind. So ... the problem requires assignable variables in
the language, perhaps? And therefore it cannot be done in Joy. I am not
so sure any more, mainly after reading your clever solution.

> I thought I'd submit a Joy implementation but it turned out to be a
> bit trickier than I first thought and I'm not sure I've got the best
> solution.

I cannot do justice to your solution now, but I'll think about it more.

[..]

- Manfred

To unsubscribe from this group, send an email to:
concatenative-unsubscribe@egroups.com

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

Stevan Apter — 2003-05-08 12:02:33

although [[+ foo]cons] meets the "acc" part of the
spec, i think the explicit reference to "foo" means
that you can't satisfy the "gen" part.

in some other programming languages, you can use "self"
to refer to the current program. it seems to me that
in joy, you would need a hierarchy of such operators:

0 self -> self
[1 self]i -> [1 self]
[[2 self]]i i -> [[2 self]]

and so forth.

where the integer parameter indicates the reverse scope,
or "context" of the self operator. self would need to be
able to reach both back in time to get its left scope and
forward in time to get its right scope. (i have this nagging
suspicion that this is somehow connected to reversability.)

then

[[+ 2 self] cons]

would be the accumulator, and

[[[+ 2 self] cons]]

its generator.

Nick Forde — 2003-05-08 13:44:45

Stevan Apter writes:

> although [[+ foo]cons] meets the "acc" part of the
> spec, i think the explicit reference to "foo" means
> that you can't satisfy the "gen" part.

Hi Stevan,

In the previous example the foo definition was the "gen" part.
i.e. DEFINE gen == [+ gen] cons.

Calling "gen" returns a quotation, which we can call "acc". This takes
one argument and returns another ("acc") quotation.

Using your earlier example:

> acc:gen 0

> acc 3
> 3 / state is now 3
> acc 4
> 7 / state is now 7
> acc 2
> 9 / state is now 9

In Joy:

0 gen # => [0 + gen]
3 swap i # => [3 + gen]
4 swap i # => [7 + gen]
2 swap i # => [9 + gen]
first. # => 9

Of course as acc is a quotation and not a definition it must be
maintained on the Joy stack (hence the swaps), executed using the i
combinator, and the accumulator value must be extracted using first.

Regards,

Nick.

wtanksleyjr@cox.net — 2003-05-08 20:32:36

From: "Stevan Apter" <sa@...>

>although [[+ foo]cons] meets the "acc" part of the
>spec, i think the explicit reference to "foo" means
>that you can't satisfy the "gen" part.

I'm going to put my foot in my mouth here -- but how
about this?

foo = [[+ foo i]cons];
gen = foo i.

To generate an accumulator, for any /n/:

n gen -> [n + foo i]

To use an accumulator:

m [n + foo i] i
-> m n + foo i
-> m+n [[+ foo i]cons] i
-> m+n [+ foo i] cons
-> [m+n + foo i]

At this point you can either extract the value of the
accumulator using first, or accumulate again using i
(or do both using dup).

>in some other programming languages, you can use "self"
>to refer to the current program. it seems to me that
>in joy, you would need a hierarchy of such operators:

This is like a return stack manipulator, except
that it's magical. I think I prefer return stack
manipulations.

> 0 self -> self

This is not clearly defined; I'm guessing that 0 self
returns either the entire current continuation (not
expressible in Joy, so not a good idea), or a quotation
containing the rest of the current block (odd, but
workable), or an empty quotation.

But this hardly matters; the rest of the behavior of
this function doesn't make any sense to me.

> [1 self]i -> [1 self]
> [[2 self]]i i -> [[2 self]]
>and so forth.

I don't see how to make this work at all; the problem
is that you seem to be expecting 'self' to know where
it originally came from, not merely where it is now.
What if the programmer has made changes to the quotation,
as in:

[[2 self] [3] append] i i

does this give
[[2 self 3]]
or
[[2 self] [3] append]
?

A harder to answer question is what happens when the
quotation is entirely constructed, rather than
literal as is the case above?

What if the argument to self is computed rather than
literal?

>where the integer parameter indicates the reverse
>scope, or "context" of the self operator. self
>would need to be able to reach both back in time
>to get its left scope and forward in time to get
>its right scope. (i have this nagging suspicion
>that this is somehow connected to reversability.)

I'm not sure that reversibility would help, since
it's not clear from the specifications which
operations should be reversed and which left alone.
If you're going to claim that 'self' only fetches
literal source code, there's no question of what
to return, but that makes 'self' useless in
generated programs.

-Billy

phimvt@lurac.latrobe.edu.au — 2003-05-09 07:29:53

I think we should first specify what an accumulator is
supposed to do. Here is an all too vague attempt:

An accumulator "contains" a current value, and it
"contains" a binary operator. (don't know a better word)
There are at least three operations for accumulators:

1: CREATE a new accumulator. The initial value and
the binary operator need to be given. In many cases
the initial value will be the unit element for the
binary operation (e.g. 0 for +, or 1 for *). But
a different value may be wanted. Also, the initial value
need not be a unit element (e.g. [] for cons, although
[] is a left-and-right unit for concat).

2: TRIGGER an existing accumulator. Takes an argument,
applies the binary operator to the argument and the
current value, produces new value. [This still leaves
it open whether: a) the argument is actually consumed
or merely inspected, and whether b) the new value is
returned.

3: DISPLAY current value of accumulator. May not be needed
in case of 2b) above. This also leaves it open whether
DISPLAY is the "death breath" which then destroys it.
Maybe two versions are needed, or separate KILL (= pop).

My inclination is this:
0 [+] CREATE ===> [..0..+..] # mysterious insides
1 [*] CREATE ===> [..1..*..] # ditto

Whatever TRIGGER might be,
1 2 3 4 [..0..+..] TRIGGER TRIGGER ==> 1 2 [..7..+..]
or 1 2 3 4 [..0..+..] TRIGGER TRIGGER ==> 1 2 3 4 [..7..+..]
or 1 2 3 4 [..0..+..] TRIGGER TRIGGER ==> 1 2 7 [..7..+..]
Nick Forde started the discussion with TRIGGER == i, and concluded
(I think correctly) that an accu must be a kind of self-reproducing
program, resembling the construction of the y-combinator. I wrote
something similar. I also tried to use the x-combinator instead,
but got nowhere.

But, maybe TRIGGER == cons i ? WHy not? Or something else?
Maybe TRIGGER should be the same for all accumulators (have we
assumed that)?

If we were to allow specific triggers depending
on the binary operator, then it becomes too trivial:
CREATE == pop and hence 0 [+] CREATE == 0
TRIGGER-PLUS == + or == [+] unary or == + dup
Then the three earlier possibilities for TRIGGER can all be
implemented. But clearly this trivialises the problem.

So, TRIGGER should be the same for all accumulators.
Whether it should be TRIGGER == i or not remains to be
discussed. But we should keep in mind: all sorts of possible
binary operators, and, even more generally, some kind
of ACTIVATING combinator for other kinds of quotations,
in a way that transmits a local state to the next activation.
Transmitting an accumulated value is really just a special
case, as Nick already anticipated. Any Haskell experts on
the group might consider whether there is some connection
to monads (which can be used to transmit or hide "imperative
features" in other functional languages). If that turns
out to be true, one might well consider some new combinators
in Joy for such activations (to avoid the overhead of
self-replication). Another afterthought: since "combining monads"
is so useful, perhaps activateable quotations should be combinable
in some way.

- Manfred

wtanksleyjr@cox.net — 2003-05-09 16:51:58

From: phimvt@...

>But, maybe TRIGGER == cons i ? WHy not?

I think the specification was pretty clear that every
accumulator has to be a function; quotations are
arguably functions, and 'i' calls them, but anything
more takes us into the realm of something other than
functions.

Do you have any idea whether my suggestion might work?
I don't trust my judgement -- I thought the original
[+ foo cons] suggestion was correct until I started
trying to defend it to sa :-).

> - Manfred

-Billy