[racket] Mutable state vs RAM on fire

From: Danny Yoo (dyoo at cs.wpi.edu)
Date: Wed May 2 17:12:50 EDT 2012

> Been playing around with some code to multiply polynomials to calculate dice probabilities.
> Is based on a paper by Doron Zeilberger that I read years ago and can't find at the moment.
> My first attempt represented polynomials as lists of coefficient/exponent pairs.
> I tried to make it completely functional, with no set! operations.  You can see it here:
> https://github.com/TurtleKitty/Dice/blob/2fff16e198cb84d725c786ecc624fb9b9468e778/dice.rkt
> It worked, but only to a point.  At 9 or 10 dice, it started blowing up the RAM in my machine.
> I swear I smelled smoke.  It grabbed like 4G and slowed to a crawl.

Hmmm!  What sample inputs do you pass to this program?  It may be
worth taking the Racket statistical profiler to it and see if it
produces useful results.

Without profiler support, I'm looking at the program, and what does
look interesting is the choice of representation you've used for the
polynomials.  In your first functional version, it appears that the
representation for a given polynomial isn't unique.  The code does a
simplification step at the very end.  In comparison, in the imperative
version, the simplification is unnecessary by taking advantage of the
dense vector representation.

In the functional version of poly-mul, why doesn't it call poly-simp?
I'm concerned that if you leave the simplification up to the very end,
it might not be as effective as if it were being done all the time.

> Knowing that the Perl and Javascript versions of this program can calculate distributions for 300 dice in the space of a heartbeat,
> I rewrote the thing to use vectors instead, and altered the polynomial multiplication function to use (begin) and (vector-set!):

To be pedantic, we can write Perl and JavaScript code in a functional style too.

I think what's being compared is not truly dependent on the language
implementation, but rather on the functional vs. imperative models and
data representations.

Best of wishes!

Posted on the users mailing list.