# accgen

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