[Haskell-cafe] The IO monad is 45 years old

[Vinod Grover]

Indeed, one might think that there is very little new :)

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.

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>

On Wed, Dec 29, 2010 at 1:13 AM, <oleg at okmij.org> wrote:

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