headers
phimvt | 2 May 2003 09:03
Picon
Picon

Re: [stack] Patterns, recursion combinators and a programming challenge

On Mon, 28 Apr 2003, Nick Forde wrote:

> phimvt <at> lurac.latrobe.edu.au writes:

>  > Thanks for that. My response to the pattern movement had been
>  > tepid until now, but after your mail I might well have another look.
> 
> When I first read about design patterns I wasn't particularly
> impressed as they didn't really give me any new insights into OO
> design. I'd encountered many of the patterns over the years and the
> books seemed to only offer labels for patterns already in common use.
> 
> In hindsight I was missing the point. Naming these patterns IS their
> benefit.

Yes, that is the conclusion I reached when writing my previous note.
The "structured flow of control" patterns IF, WHILE, REPEAT, CASE
LOOP-and-a-half (with single exit somewhere) are useful, common,
descriptive and adequate almost everywhere. Similarly the various
recursion patterns for lists MAP FOLD FILTER, and I suspect the
other more general recursion patterns are useful, common, descriptibe
and adequate almost everywhere.

What goes on in the mind of programmers I do not know, but having
found the right (common) pattern, it helps to give it a name.
It also helps future maintainers to "see the pattern" as fast
as they can read its name.

> patterns to be a useful level of abstraction above objects. Of course
> ideally programmers wouldn't need patterns as they could be considered
(Continue reading)

Permalink | Reply | 0 comments |
headers
phimvt | 2 May 2003 11:05
Picon
Picon

Re: [stack] Patterns, recursion combinators and a programming challenge


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
(Continue reading)

Permalink | Reply | 7 comments |
headers
Nick Forde | 2 May 2003 11:33
Picon

Re: [stack] Patterns, recursion combinators and a programming challenge

phimvt <at> lurac.latrobe.edu.au writes:
 > > "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:

Yes, me too. Looking at some of the other solutions I now think my
initial attempt was over engineered.

 > [..]
 > 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. 

Looking at some of the other solutions the following may be
sufficient:

DEFINE foo == [+] cons.

7 foo 2 swap i.      # => 9
4 foo 'A swap i.     # => 'E
(Continue reading)

Permalink | Reply | 4 comments |
headers
Nick Forde | 2 May 2003 15:15
Picon

Re: [stack] Patterns, recursion combinators and a programming challenge

Nick Forde writes:
 > Looking at some of the other solutions the following may be
 > sufficient:
 > 
 > DEFINE foo == [+] cons.
 > 
 > 7 foo 2 swap i.      # => 9
 > 4 foo 'A swap i.     # => 'E
 > 0.5 foo 0.25 swap i. # => 0.75
 > 
 > This of course can only be executed once but may be all that is
 > required(?).

Here's a slightly better description of the problem:

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

   1.  Takes, and returns functions that take, exactly one argument.

   2. Works for any numeric type-- i.e. can take both ints and floats
      and returns functions that can take both ints and floats.

   3. Generates functions that return the sum of every number ever
      passed to them, not just the most recent.

OK, so this rules out the above solution. Ignore what I said earlier :-)

   4. Returns a real function, meaning something that you can use
      wherever you could use a function you had defined in the
      ordinary way in the text of your program.
(Continue reading)

Permalink | Reply | 2 comments |
headers
Martin Young | 2 May 2003 17:28
Picon

Re: [stack] Patterns, recursion combinators and a programming challenge

On Fri, 2003-05-02 at 14:15, Nick Forde wrote:
> So my best solution is still:
> 
>   DEFINE foo ==
>     [+] cons [infra dup rest cons] cons
>     [dupd swons swons].
> 
> Are there no other takers? There must be a better Joy implementation
> than this. Also the first call to this function only initialises the
> accumulator, whereas it should actually execute the first accumulate
> operation.

The problem statement is still opaque to me so I've probably
misunderstood.  Below is a solution (?) in Monkey (my Joy-alike) but the
Joy version (untested) would be:

DEFINE foo ==
  [ + foo ] cons .

Or is explicit recursion not allowed?

----snip--snip----

<< ----------------------- 
   Accumulator generators.
   ----------------------- >>

module main provides main .
            uses     io .
(Continue reading)

Permalink | Reply | 1 comment |
headers
Nick Forde | 2 May 2003 18:35
Picon

Re: [stack] Patterns, recursion combinators and a programming challenge

Hi Martin,

Martin Young writes:
 > On Fri, 2003-05-02 at 14:15, Nick Forde wrote:
 > > So my best solution is still:
 > > 
 > >   DEFINE foo ==
 > >     [+] cons [infra dup rest cons] cons
 > >     [dupd swons swons].
 > > 
 > > Are there no other takers? There must be a better Joy implementation
 > > than this. Also the first call to this function only initialises the
 > > accumulator, whereas it should actually execute the first accumulate
 > > operation.
 > 
 > The problem statement is still opaque to me so I've probably
 > misunderstood.  Below is a solution (?) in Monkey (my Joy-alike) but the
 > Joy version (untested) would be:
 > 
 > DEFINE foo ==
 >   [ + foo ] cons .

Nice! I think this _is_ a valid solution.

I've also just noticed that my solution returns i incremented by n
rather than n incremented by i. Oops.

If nothing else this problem certainly highlights how bad English is
for specifying such challenges.
(Continue reading)

Permalink | Reply | 0 comments |
headers
phimvt | 5 May 2003 09:15
Picon
Picon

Re: [stack] Patterns, recursion combinators and a programming challenge


On Fri, 2 May 2003, Nick Forde wrote:

[.. a propos solutions to the "accumulator challenge" ..]

> Yes, me too. Looking at some of the other solutions I now think my
> initial attempt was over engineered.

No, I think you were exactly right. Over the weekend I did some
paper-and-pencil programming at home and came up with something
very similar to what you had. It is also based on the true/false
alternating self-reproducing program in "Recursion Theory ..",
as you suggested. Here is what I came up with. (A small
modification was needed for non-commutative operators like "cons":
without the first line "[swap] swoncat" the definition of
cons-accu would have to be "[] [swons] accu-make" which would have
been more efficient but not as clean.)

FILE accu.joy:

-----------------------------------------------------------

2 setecho.

# accumulator challenge
# accumulators are similar to folding a list (by + or by * etc)
# so they should be constructed by the same program constructor
# from a binary operator and a suitable initial (unit) element.
# The operator accu-make does that. For example,
#   0 [+] accu-make   ==>  [..0..]     and then
(Continue reading)

Permalink | Reply | 0 comments |
headers
sa | 5 May 2003 17:04

[stack] accgen


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:
(Continue reading)

Permalink | Reply | 0 comments |
headers
phimvt | 7 May 2003 12:19
Picon
Picon

Re: [stack] patterns and recursion combinators


On Thu, 24 Apr 2003 phimvt <at> LURAC.LATROBE.EDU.AU wrote:

[...]

> Coming soon:
    [...]
>   More on nested recursion, Ackermann, non-recursive definition.

07-MAY  On the Joy page, NEW:
   A (longish) note on nested recursion, several examples, several styles. 
   A new combinator "condnestrec" (similar to condlinrec) in interp.c

And belatedly, happy birthday concatenative !  (Thanks Billy)

  - Manfred

------------------------ Yahoo! Groups Sponsor ---------------------~-->
Rent DVDs from home.
Over 14,500 titles. Free Shipping
& No Late Fees. Try Netflix for FREE!
http://us.click.yahoo.com/BVVfoB/hP.FAA/uetFAA/saFolB/TM
---------------------------------------------------------------------~->

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

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

Permalink | Reply | 14 comments |
headers
cyfododd | 7 May 2003 19:45
Favicon

[stack] the accumulator generator

Hello,    

I'm new to this group.  I've skimmed most of the early messages (the 
first 800 or so), as well as a few of the more recent ones.      

  
Anyway, regarding the accumulator generator: it was suggested earlier  
that the following meets the requirements for foo...    

DEFINE foo == [+ foo] cons.    

...and here is a primitive example trace:    

newstack; 30 11 5 4 stack;   
foo stack;     
cons i stack; cons i stack; cons i stack;     
14 swons i stack; 36 swons i stack;     
first; 
2 1 foo stack first; cons i first. 

[4 5 11 30]    
[[4 + foo] 5 11 30]    
[[9 + foo] 11 30]    
[[20 + foo] 30]    
[[50 + foo]]    
[[64 + foo]]    
[[100 + foo]]    
100    
[1 + foo] 
3
(Continue reading)

Permalink | Reply | 0 comments |

Gmane