[plt-scheme] Native code generation and immutable pairs

Thanks. You're point is well-taken.

In my POPL paper with Cormac Flanagan on removing future
synchronization from functional Scheme programs we
ran into exactly the same problems. So we restricted
it to purely functional programs, realized that set!
was evil, and abandoned parallelism -- at the time
it looked more important to create analyses that
summarize their work at module boundaries.

As you may know around that time PLT Scheme used
units (first-class components) as modules and this
made modular analysis impossible; componential analysis
is all we could get.

I am hoping that the module+contracts work from POPL06
may point in the right direction for future analyses
in our context.

-- Matthias


On Feb 10, 2006, at 12:07 PM, Jim Blandy wrote:

> On 2/10/06, Matthias Felleisen <matthias at ccs.neu.edu> wrote:
>> With Andrew's soft type Scheme system (based on Chez),
>> we could create speedups on benchmarks between 10% and
>> 8x. The average, if I recall this correctly, got close
>> to 40% (someone can also look up the published number).
>
> The original point I was trying to raise is that preemptive threads
> will erase all of these advantages, because in many --- I think most
> --- cases you will no longer be able to rely on the type of values
> remaining the same, even while control has "remained" in the code
> under analysis.  Because, of course, control has not remained there at
> all --- it has been proceeding in other threads as well.
>
> In C and C++, it suffices to have a rule, as the POSIX thread model
> does, saying that if you don't use mutexes to protect shared data
> structures properly, all bets are off.  But Scheme wants to be a safe
> language, and the consequence of getting a type wrong may be a crash,
> so this loophole isn't available to us.
>
> The other weakness in these analyses appears as sort of a footnote
> towards the end of J. Michael Ashley's paper on n-CFA flow analysis
> (where he introduces functions that act as "tuning parameters" on the
> resolution of the analysis): in the presence of separate compilation,
> the win from flow analysis, which was substantial in the context of
> Chez, would vanish.
>
> So you need two things to make this analysis pay:
> 1) You need to restrict mutation of the objects you're traversing by
> other threads.  Since pairs are so common, restricting pair mutation
> is pretty much required.
> 2) You need a separate compilation system that somehow summarizes the
> results of the analysis of one module in a way that can be used to
> retain more information when compiling modules that import it.
>
> If you're interested, I can look up the POSIX rule and find the bit of
> Mike's paper that I have in mind.