[plt-scheme] Imperative programming : missing the flow

From: Bill Wood (william.wood3 at comcast.net)
Date: Sat May 12 23:42:08 EDT 2007

On Sat, 2007-05-12 at 21:58 -0400, Anton van Straaten wrote:
   . . .
> Perhaps this is too obvious to mention in the present company, but since 
> you didn't mention it, the world-passing (monadic) view of imperative 
> programming might provide a useful perspective.  It provides an easily 
> understood theory (at a high level) of imperative programming, which 
> lets you compare imperative programs to functional programs using a 
> common model.  (Admittedly, the model is skewed in favor of the 
> functional approach, but I'm guessing you won't object to that.)
> The resulting explanations end up not being all that different from 
> those that have already been given, but introducing "the world" as a 
> first-class feature of the explanatory model helps to discuss and reason 
> about the issues.
> For example, the world-passing perspective explains why the imperative 
> puzzle pieces (statements) that Joe described are perfect squares: the 
> only functional/algebraic dependency between statements is "the world", 
> so there's no way to fit statements together based on what kind of value 
> they consume and produce -- they all consume and produce a version of 
> the world.
> Another point is that every statement in an imperative program can 
> change the value of any currently visible variable in the world.  In 
> contrast, a functional program can only "change" the value of variables 
> at function application time.  So every single imperative statement is 
> like a function in its own right, which complicates reasoning.
> If the students can handle a functional model of an imperative program 
> looking something like:
>    ((lambda (world) stmt-n)
>     ((lambda (world) ...)
>      ((lambda (world) stmt-1)
>       '())))
> ...then there are quite a few concrete points and comparisons that could 
> be made with it.  It's also good preparation for teaching monads later... :)
> Anton

This is an excellent point. Even without monads the functional model of
an imperative program as a function taking a state and returning a
modified state is common and useful within both functional and
relational languages (the example of state threads in Prolog comes to
mind).  I had occasion to model a special-purpose SIMD-style processor
this way in SML.  With some syntactic sugar providing a reverse compose
HOF It was even possible to write SML programs that looked like assembly
language to non-SML programmers.  Your point about the uniform
input/output arguments making it impossible to infer ordering from type
analysis was stunningly apparent.

 -- Bill Wood

Posted on the users mailing list.