[plt-scheme] Re: Project Euler was Hash Table implementation

I had intended to wait until I had finished all of the problems before
writing up my observations, but I will respond your statements.  The
Project Euler problems are sort of advanced versions of what HTDP
calls finger exercises, and make a great way of observing ones own
programming technique.  I think that they are too small to be useful
for comparing programming languages, as they are mainly about choosing
data structures and algorithms, and none of the complicated
interfacing and error handling that real world programming entails.

To address your criticisms, srfi-40 does a pretty good job of making
streams easy, and srfi-42 and/or misc.ss from swindle provide
comprehensions.  Srfi-40 is a bit tricky, as it doesn't always delay
what I expected it would, but that could be just me.  It would be nice
to have an implementation of SICP streams to play with, they may take
more forcing than srfi-40, but they seem more intuitive to me.

Srfi-42 is very easy to use (see Jens' blog for a great exposition),
but there are some gotchas. (list-ec (: a 1 5) a) evalutaes to (1 2 3
4).  This off by one error has been my most frequent programming
language related[1] bug so far in the Project Euler problems.    Note:
 PLT has an old, buggy version of Srfi-42.

I'll say more when I'm done.


[1]failure to RTFP carefully is by far my most common cause of bugs in
the Project Euler problems (and elsewhere)

On 8/3/07, Mark Engelberg <mark.engelberg at gmail.com> wrote:
> On 8/3/07, David Einstein <deinst at gmail.com> wrote:
> > Inspired by Jens and Grant, I decided to try my hand at some of the Project
> > Euler problems using PLT scheme, to see what it was capable of.  It has
> > proven itself capable on the few problems that I have completed so far, but
> > I just ran into what appears to be a bug of sorts.  It appears that the
> > hash-table implementation does not expand as more keys are added, and so if
> > the table reaches a certain size things slow down dramatically.  For example
>
> I've also had a lot of fun doing the Project Euler problems in various
> languages.  I find it interesting to see which lanuage features are
> useful for these sorts of programming exercises.  After solving a
> given problem, you get to see how other people solved it in their
> respective languages of choice, which is always interesting as well.
> Some of my observations:
>
> 1.  You really want a language with good syntactic support for BigNums
> / infinite-precision / exact integers.  In Java/C/C#, you can use some
> sort of add-on BigNum class, but the code starts looking ugly, and
> poorly reflects the underlying math.
> 2.  For maximum reuse, streams are essential.  Many of the problems
> have you searching a sequence of numbers for some property, and you
> don't know in advance how many elements of that sequence you will need
> to generate.  When you read through C solutions, they typically say,
> "I started by generating the first 10,000 primes and trying to solve
> the problem with those.  When that didn't work, I started over again,
> but using a table of 20,000 primes..."  You really want to be using
> streams, and a language with a rich set of constructs for combining,
> filtering, and mapping streams.
> 3.  Comprehensions are wonderful syntactic sugar.  They noticeably cut
> down the length of code while increasing clarity.  When reading
> through the solutions, the shortest programs are typically in Haskell,
> Python, J, or Mathematica.  The shortness of the J or Mathematica code
> usually comes from some built-in function that suits the mathematical
> problem.  The Haskell and Python code is short because of the
> expressiveness of the languages, and the use of comprehensions.
>
> Other things are of course important as well, but these are probably
> the top three.  I have worked through many of the Project Euler
> problems in Scheme, Haskell, Python, and Scala.
>
> Scheme satisfies the first criterion, but not the second and third.
> Of course, you can extend Scheme however you would like, but there is
> no "off-the-shelf" solution for comprehension manipulation of streams.
>  The syntax for vectors and hash tables are also more verbose than
> their counterparts in other languages.  As a result, the Scheme
> programs tend to end up on the verbose side, and is not my preferred
> language for Project Euler.  (Scheme's built-in support for fractions
> has come in handy on a couple of problems, however).
>
> I have found Haskell to be a good fit for many of the Project Euler
> problems.  I've run into problems, however, when I needed to use
> memoization, or other non-pure optimization techniques.
>
> Python works surprisingly well for Project Euler problems.  Many of
> the "streams" can be expressed very elegantly as iterators using
> Python's nice "yield" syntax (although you have to do a bit more work
> if you want to cache the stream for multiple passes).  For problems
> with a more "iterative" feel, or with a lot of string mainpulation,
> hash table manipulation, or i/o, Python often feels more pleasant than
> Haskell.
>
> Scala allows you to write "iterative" or "recursive" style code
> equally well.  It has functional and non-functional versions of most
> data structures, including built-in support for comprehensions,
> filter, map, etc. over both (non-functional) iterators a la Python and
> (functional) cached streams a la Haskell.  Although ints are 32-bit by
> default, the BigInt class is much less obtrusive than in other OO
> languages because ints are auto-converted to BigInts if any of the
> numbers in the arithmetic expression are of BigInt type (sort of like
> the way Scheme's inexact numbers cause exact numbers to be converted).
>  My main objection to Scala is that the static type system is fairly
> complicated.  For these sorts of short programming tasks, it seems
> unnecessarily verbose.
>
> Anyone else want to comment on the relative strengths of languages for
> Project Euler?
>
> --Mark
>