[Haskell-cafe] Re: Problems with strictness analysis?

[Achim Schneider]

"Luke Palmer" <lrpalmer at gmail.com> wrote:

> On Wed, Nov 5, 2008 at 4:33 AM, Achim Schneider <barsoap at web.de>
> wrote:
> > I know that I, coming from a C/Scheme POV, in the beginning
> > attributed much magic to Haskell's inner workings and assumed,
> > because of the general wizardly air of the whole language, avg to
> > run in O(n) time and constant resp. O(n) space.
> 
> Haskell's great strength is its equational semantics.  I would like
> Haskell programmers to think equationally, mathematically, rather than
> operationally, when writing Haskell programs.  If I were to teach a
> course in Haskell, I would like to launch off of denotational
> semantics, hopefully without ever having to say "lazy evaluation".
> (It's a pipe dream, of course, but you get the idea)
> 
> However, this strength is also a weakness when we want to analyze the
> efficiency of programs.  The denotational semantics of Haskell say
> nothing about time or space complexity, and give us no tools to reason
> about it.  A Haskell interpreter which randomly rewrites terms until
> it happens upon a normal form is considered correct (or rather,
> "correct with probability 1" :-).
> 
> How can we support analysis of time and space complexity without
> expanding ourselves into the complicated dirty world of operational
> thinking?
> 
You can't clean a student's mind from "bad, dirty operational thoughts"
by not talking about it as much as you can't exterminate the human race
by discontinuing sexual education. Fumbling the keyboard and making
things go "blink" and "swoosh" is just too much fun.

A natural understanding of what's "clean, elegant and fun" develops
over time, and students have to rub their nose into gory and dirty
details and code until it bleeds before they see what all that
abstract nonsense is good for: Not so much to formalise thinking, but
to enable one to speak axiomatically, just like one thinks.  

-- 
(c) this sig last receiving data processing entity. Inspect headers
for copyright history. All rights reserved. Copying, hiring, renting,
performance and/or quoting of this signature prohibited.