[plt-scheme] Project Euler was Hash Table implementation

From: David Einstein (deinst at gmail.com)
Date: Fri Aug 3 21:05:20 EDT 2007

If you are looking for comments on comprehensions, I have a few.

The ease of adding generators to srfi-42 is great, as is the ability
to add new dispatching generators.  It would be great to be able to
replace the existing generators, so for example on could fix the
ridiculous behavior of the :range generator skipping the last element.
 In the best of all possible worlds one would be able to specify the
generators in the macro equivalent of a unit, but I'm not sure that
that is possible (it is way beyond me)

The restriction of :while and :until to having only one generator
seems gratuitous, Swindle's behavior here is much more sensible.  Yes,
it is possible to work around using the nested operator, but the macro
should be able to do that automatically.

On 8/3/07, Matthias Felleisen <matthias at ccs.neu.edu> wrote:
> Mark, why don't you try two different things:
>   1. use the srfis for lazy streams and comprehension to rewrite the
> solutions
>   2. use Lazy Scheme and hack together a comprehension macro.
> These are interesting design experiments that Matthew can use for his
> comprehension work and you could report on it with a paper at the
> next Scheme workshop, which will be in the US. I bet that Bruce (also
> in Seattle) would love to "play" with you on this code and experiment.
> -- Matthias
> On Aug 3, 2007, at 4:55 PM, Mark Engelberg 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
> > _________________________________________________
> >   For list-related administrative tasks:
> >   http://list.cs.brown.edu/mailman/listinfo/plt-scheme

Posted on the users mailing list.