----- Forwarded message from Dave Long <[email protected]> ----- Date: Tue, 27 Mar 2012 14:44:42 +0200 From: Dave Long <[email protected]> To: Kragen Javier Sitaker <[email protected]> Cc: [email protected] Subject: Re: higher-order programming and concurrency in low-level languages X-Mailer: Apple Mail (2.753.1)
> You feed an AVR executable to their > analyzer, and it tells you what its maximum stack depth is, or the > maximum stack depth of each thread. This is **awesome**. Ken Iverson's 1962 book: http://www.softwarepreservation.org/projects/apl/book/APROGRAMMING% 20LANGUAGE/view has a nice section on "Metaprograms" in which he first discusses transforming expressions (albeit not whole programs) to minimize stack depth p.166 > A formula whose maximum suffix dispersion is minimal with respect > to the set of all equivalent formulas is said to be in *minimax > form*. > > The dimension of the stack vector *y* employed in the evaluation of > a formula *z* (cf. Program 5.4) takes on successive values equal to > the number of roots in the tree represented by the suffix of *z* > currently scanned. It therefore assumes the values (in reverse > order) of the components of the associated suffix dispersion vector > *s*. The maximum dimension of the stack vector determines, in > turn, the amount of auxiliary storage required in the evaluation of > the formula or in the compilation of a function program for its > evaluation. It also determines, in part, the number of transfers > of intermediate results to and from storage in evaluating the > formula in a computer having a limited number of central registers. > A formula in minimax form minimizes the maximum dimension of the > stack vector and is therefore to be preferred and then presents a program to automatically rewrite formulas in minimax form. -Dave apropos the general theme, there's a nice thread on LTU which touches on the relation between delimited continuations, iterators, and exceptions in which Oleg argues that the iterators which you really want produce something like the control-flow equivalent of a zipper*: they produce a value from within the computation, combined with its continuation as context. From this point of view, an exception is an iteration that categorically refuses to budge any further. http://lambda-the-ultimate.org/node/4481 "Programming with Algebraic Effects and Handlers" *actually, that's only half of a zipper. if the iterator produced a predecessor context as well as a continuation context surrounding the value, it should be possible to roll it back as well as forward ... probably Chung-chieh Shan's already written something about this? ----- End forwarded message ----- -- To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-discuss
