Loading ...
Sorry, an error occurred while loading the content.

Paul Grahams Accumulator

Expand Messages
  • Chris Double
    (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
    Message 1 of 10 , Jun 2, 2004
    View Source
    • 0 Attachment
      (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
      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]
      Message 2 of 10 , Jun 2, 2004
      View Source
      • 0 Attachment
        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
        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
        Message 3 of 10 , Jun 2, 2004
        View Source
        • 0 Attachment
          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
          ... This works in Factor too. The only thing you have to change is the word ... [ uncons [ + dup ] dip dup [ cons ] dip cons ] dup [ cons ] dip cons ; In
          Message 4 of 10 , Jun 3, 2004
          View Source
          • 0 Attachment
            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
            ... 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
            Message 5 of 10 , Jun 3, 2004
            View Source
            • 0 Attachment
              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
              On Thu, 03 Jun 2004 16:44:34 -0400, Slava Pestov ... Why is that? Or are functions that capture state an example of the type of thing
              Message 6 of 10 , Jun 3, 2004
              View Source
              • 0 Attachment
                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
                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: [ . ]
                Message 7 of 10 , Jun 3, 2004
                View Source
                • 0 Attachment
                  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
                  On Thu, 03 Jun 2004 19:18:28 -0400, Slava Pestov ... over [ over cons? [ ... ] [ call ] ifte ] [ 2drop ] ifte ; [ 1 2 [ 3 4 ] 5 ] [ . ]
                  Message 8 of 10 , Jun 3, 2004
                  View Source
                  • 0 Attachment
                    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
                    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
                    Message 9 of 10 , Jun 3, 2004
                    View Source
                    • 0 Attachment
                      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
                    • Chris Double
                      On Thu, 03 Jun 2004 21:53:19 -0400, Slava Pestov ... Thanks! ... Sure, that d be great. Chris. -- Chris Double chris.double@double.co.nz
                      Message 10 of 10 , Jun 3, 2004
                      View Source
                      • 0 Attachment
                        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@...
                      Your message has been successfully submitted and would be delivered to recipients shortly.