Indeed, one might think that there is very little new :) <div><br></div><div>I also recommend the following handy book on functional programming (based on Landin's ideas among others ) by William H Burge called recursive Programming Techniques from 1975.</div>
<div><br></div><div><a href="http://www.amazon.com/gp/product/0201144506?SubscriptionId=0QCHRJVSKG6F3BRGBNG2&tag=pbs_00017-20&linkCode=xm2&camp=2025&creative=165953&creativeASIN=0201144506">http://www.amazon.com/gp/product/0201144506?SubscriptionId=0QCHRJVSKG6F3BRGBNG2&tag=pbs_00017-20&linkCode=xm2&camp=2025&creative=165953&creativeASIN=0201144506</a></div>
<div><br></div><div><a href="http://www.amazon.com/gp/product/0201144506?SubscriptionId=0QCHRJVSKG6F3BRGBNG2&tag=pbs_00017-20&linkCode=xm2&camp=2025&creative=165953&creativeASIN=0201144506"></a><br><br>
<div class="gmail_quote">On Wed, Dec 29, 2010 at 1:13 AM, <span dir="ltr"><<a href="mailto:oleg@okmij.org">oleg@okmij.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<br>
The unabated debate about exactly how much category theory one needs<br>
to know to understand that strange beast of IO prompts a thought if<br>
monads, like related continuations, are the things that are destined<br>
to be rediscovered time and time again.<br>
<br>
An old (1994) paper on category theory monads and functional<br>
programming included an interesting historical side-note. It turns out<br>
that the RealWorld-passing trick underlying the implementation of the<br>
IO monad, the trick that made it possible to embed truly side-effecting<br>
operations into pure Haskell -- the trick is 45 years old. It has been<br>
first published in February 1965.<br>
<br>
That 1965 paper also anticipated State and Writer monad, call/cc,<br>
streams and delayed evaluations, relation of streams with co-routines,<br>
and even stream fusion.<br>
<br>
First, here is the historical aside, cited from<br>
<br>
Jonathan M. D. Hill and Keith Clarke<br>
An Introduction to Category Theory, Category Theory Monads,<br>
and Their Relationship to Functional Programming. 1994<br>
<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.6497" target="_blank">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.6497</a><br>
<br>
<br>
[blockquote]<br>
3 An historical aside<br>
<br>
Monads are typically equated with single-threadedness, and are<br>
therefore used as a technique for incorporating imperative features<br>
into a purely functional language. Category theory monads have little<br>
to do with single-threadedness; it is the sequencing imposed by<br>
composition that ensures single-threadedness. In a Wadler-ised monad<br>
this is a consequence of bundling the Kleisli star and flipped compose<br>
into the bind operator. There is nothing new in this connection. Peter<br>
Landin in his Algol 60 used functional composition to model<br>
semi-colon. Semi-colon can be thought of as a state transforming<br>
operator that threads the state of the machine throughout a program.<br>
The work of Peyton-Jones and Wadler has turned full circle back to<br>
Landin's earlier work as their use of Moggi's sequencing monad enables<br>
real side-effects to be incorporated into monad operations such as<br>
print. This is similar to Landin's implementation of his sharing<br>
machine where the assignandhold function can side-effect the store of<br>
the sharing machine because of the sequencing imposed by functional<br>
composition. Landin defined that `Imperatives are treated as null-list<br>
producing functions' [In Landin's paper, () is the syntactic<br>
representation of the empty list and not the unit.]. The assignandhold<br>
imperative is subtly different in that it enables Algol's compound<br>
statements to be handled. The function takes a store location and a<br>
value as its argument, and performs the assignment to the store of the<br>
sharing machine, returning the value assigned as a result of the<br>
function. Because Landin assumed applicative order reduction, the<br>
K combinator was used to return (), and the imperative was evaluated<br>
as a side effect by the unused argument of the K-combinator. Statements<br>
are formed by wrapping such an imperative in a lambda expression that<br>
takes () as an argument. Two consecutive Algol-60 assignments would be<br>
encoded in the lambda calculus as:<br>
<br>
Algol 60 | Lambda Calculus<br>
x:= 2; | ( (\() -> K () (assignandhold x 2)) .<br>
x:= -3; | (\() -> K () (assignandhold x (-3))) ) ()<br>
<br>
By using a lambda with () as its parameter, () can be thought of as<br>
the `state of the world' that is threaded throughout a program by<br>
functional composition.<br>
[/blockquote]<br>
<br>
<br>
Peter Landin's paper is remarkable indeed:<br>
<br>
P. J. Landin. A correspondence between ALGOL 60 and Church's lambda<br>
notation.<br>
Communications of the ACM, 8(2):89-101, February 1965.<br>
(Part 2 in CACM Vol 8(2) 1965, pages 158-165.)<br>
<a href="http://portal.acm.org/citation.cfm?id=363749" target="_blank">http://portal.acm.org/citation.cfm?id=363749</a><br>
<br>
First the reader will notice the `where' notation. Peter Landin even<br>
anticipated the debate on `let' vs `where', saying<br>
``The only consideration in choosing between `let' and `where'<br>
will be the relative convenience of writing an auxiliary<br>
definition before or after the expression it qualifies.''<br>
<br>
The ()-passing trick is described in full on p100, with remarkable<br>
clarity:<br>
``Statements. Each statement is rendered as a 0-list-<br>
transformer, i.e. a none-adic function producing the nullist<br>
for its result. It achieves by side-effects a transformation of<br>
the current state of evaluation. ...<br>
Compound statements are considered as functional products (which we<br>
indicate informally by infixed dots).''<br>
<br>
A remark<br>
``However, input/output devices can be modeled as named lists, with<br>
special, rather restricted functions associated. ... Writing is<br>
modeled by a procedure that, operates on a list, and appends a new<br>
final segment derived from other variables. (Alternatively, a purely<br>
functional approach can be contrived by including the transformed list<br>
among the results.)''<br>
<br>
anticipated the State and Writer monads as well.<br>
<br>
<br>
Another remark, in the section on Streams,<br>
``This correspondence [laws of head/tail/cons] serves two related<br>
purposes. It enables us to perform operations on lists (such as<br>
generating them, mapping them, concatenating them) without using an<br>
`extensive,' item-by-item representation of the intermediately<br>
resulting lists; and it enables us to postpone the evaluation of the<br>
expressions specifying the items of a list until they arc actually<br>
needed. The second of these is what interests us here.''<br>
<br>
and footnote 6,<br>
``It appears that in stream-transformers we have a functional analogue<br>
of what Conway [12] calls "co-routines."<br>
<br>
show that Peter Landin understood streams, on-demand evaluation and<br>
even stream fusion.<br>
<br>
<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</blockquote></div><br></div>