[lambda.git] / offsite_reading.mdwn

Many of these links are to Wikipedia. You can learn a lot from such articles,
so long as you remember they may sometimes mislead or make mistakes. However, I
hope at this point in your education you'll have learned to be a guarded reader
even of authoritative treatises by eminent authors. So you shouldn't need any
Wikipedia-specific warnings.

For most readers, many bits of reading we point you to will be hairy in one way
or another. It may be aimed at audiences with more programming experience; it
may be aimed at audiences with specific logical background you don't yet have;
it may be aimed at audiences familiar with technical areas in linguistics you're
first encountering. Or perhaps several of these at once. We hope you will
already have mastered the skill of leveraged reading: getting what you can out
of an article you don't fully understand, so that you can discuss it with the rest of
the group and hopefully get to a point where you can read it again and
get more out of. (Rinse and repeat.)

## Functions ##

*       [[!wikipedia Higher-order function]]
*       [[!wikipedia First-class function]]
*       [[!wikipedia Currying]]

## Functional vs imperative programming ##

*       [[!wikipedia Declarative programming]]
*       [[!wikipedia Functional programming]]
*       [[!wikipedia Purely functional]]
*       [[!wikipedia Referential transparency (computer science)]]
*       [[!wikipedia Imperative programming]]

## General issues about variables and scope in programming languages ##

*       [[!wikipedia Variable (programming) desc="Variables"]]
*       [[!wikipedia Free variables and bound variables]]
*       [[!wikipedia Variable shadowing]]
*       [[!wikipedia Name binding]]
*       [[!wikipedia Name resolution]]
*       [[!wikipedia Parameter (computer science) desc="Function parameters"]]
*       [[!wikipedia Scope (programming) desc="Variable scope"]]
*       [[!wikipedia Closure (computer science) desc="Closures"]]

##[[Learning Scheme]]##

## Untyped lambda calculus and combinatory logic ##

*       [[!wikipedia Lambda calculus]]
<!-- Haskell Curry had ideas that he felt were validated upon reading a 1924 paper by M. Schönfinkel "Uber die Bausteine der mathematischen Logik" which used combinators in a similar way to his own ideas. Haskell then wrote "An analysis of logical substitution" which appeared in the American Journal of Mathematics in 1929. -->
*       [[!wikipedia Moses Schönfinkel]]
*       [[!wikipedia Haskell Curry]]
*       [[!wikipedia Alonzo Church]]<p>
*       [[!wikipedia Church encoding]]

*       [[!wikipedia Combinatory logic]]
*       [Combinatory logic](http://plato.stanford.edu/entries/logic-combinatory/) at the Stanford Encyclopedia of Philosophy
*       [[!wikipedia SKI combinatory calculus]]
*       [[!wikipedia B,C,K,W system]]
*       Jeroen Fokker, "The Systematic Construction of a One-combinator Basis for Lambda-Terms" <cite>Formal Aspects of Computing</cite> 4 (1992), pp. 776-780.
        <http://people.cs.uu.nl/jeroen/article/combinat/combinat.ps>
*       [Chris Barker's Iota and Jot](http://semarch.linguistics.fas.nyu.edu/barker/Iota/)<p>

*       [To Dissect a Mockingbird](http://dkeenan.com/Lambda/index.htm)
*       [Combinator Birds](http://www.angelfire.com/tx4/cus/combinator/birds.html)
*   [Les deux combinateurs et la totalite](http://www.paulbraffort.net/j_et_i/j_et_i.html) by Paul Braffort.

## Evaluation Order ##

*       [[!wikipedia Evaluation strategy]]
*       [[!wikipedia Eager evaluation]]
*       [[!wikipedia Lazy evaluation]]
*       [[!wikipedia Strict programming language]]

## Confluence, Normalization, Undecidability ##

*       [[!wikipedia Church-Rosser theorem]]
*       [[!wikipedia Normalization property]]
*       [[!wikipedia Turing completeness]]<p>
*       [Scooping the Loop Snooper](http://www.cl.cam.ac.uk/teaching/0910/CompTheory/scooping.pdf), a proof of the undecidability of the halting problem in the style of Dr Seuss by Geoffrey K. Pullum


## Recursion and the Y Combinator ##

*       [[!wikipedia Recursion (computer science) desc="Recursion"]]
*       [[!wikipedia Y combinator]]
*       [Chapter 9 from The Little Schemer](http://www.ccs.neu.edu/home/matthias/BTLS/sample.ps) on the Y Combinator "...and Again, and Again, and Again..."
*       [The Y combinator](http://mvanier.livejournal.com/2700.html)
*       [The Why of Y](http://www.dreamsongs.com/NewFiles/WhyOfY.pdf)
*       [The Y Combinator (Slight Return), or: How to Succeed at Recursion Without Really Recursing](http://mvanier.livejournal.com/2897.html)
*       [Y Combinator for Dysfunctional Non-Schemers](http://rayfd.wordpress.com/2007/05/06/y-combinator-for-dysfunctional-non-schemers/)
*       [The Y Combinator](http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html)
*       [The Y Combinator](http://dangermouse.brynmawr.edu/cs245/ycomb_jim.html) derives the applicative-order Y-combinator from scratch, in Scheme. This derivation is similar in flavor to the derivation found in The Little Schemer, but uses a slightly different starting approach...
*   [The church of the least fixed point, by Sans Pareil](http://www.springerlink.com/content/n4t2v573m58g2755/)


## Types ##

*       [[!wikipedia Tagged union]]
*       [[!wikipedia Algebraic data type]]
*       [[!wikipedia Recursive data type]]
*       [[!wikipedia Pattern matching]]
*       [[!wikipedia Unit type]]
*       [[!wikipedia Bottom type]]
*       [[!wikipedia Typed lambda calculus]]
*       [[!wikipedia Simply typed lambda calculus]]
*       [Type Theory](http://plato.stanford.edu/entries/type-theory/) at the Stanford Encyclopedia of Philosophy
*       [Church's Type Theory](http://plato.stanford.edu/entries/type-theory-church/) at the Stanford Encyclopedia of Philosophy
*       [[!wikipedia Type polymorphism]]
*       [[!wikipedia System F]]


##[[Learning OCaml]]##


## Side-effects / mutation ##

*       [[!wikipedia Side effect (computer science) desc="Side effects"]]
*       [[!wikipedia Reference (computer science) desc="References"]]
*       [[!wikipedia Pointer (computing) desc="Pointers"]]
*       [Pointers in OCaml](http://caml.inria.fr/resources/doc/guides/pointers.html)

## Monads ##

*       [[!wikipedia Monad (functional programming) desc="Monads in Functional Programming"]]
*       [A Gentle Intro to Haskell: About Monads](http://www.haskell.org/tutorial/monads.html)
*       [Understanding Haskell Monads](http://ertes.de/articles/monads.html)
*       [The State Monad: a tutorial for the confused?](http://coder.bsimmons.name/blog/2009/10/the-state-monad-a-tutorial-for-the-confused/)
*       [Beyond Monads](http://blog.sigfpe.com/2009/02/beyond-monads.html)
*       [Simple Explanation of a Monad](http://math.stackexchange.com/questions/405/simple-explanation-of-a-monad)
*       [What is a Monad?](http://stackoverflow.com/questions/44965/what-is-a-monad)
*       [Can Anyone Explain Monads?](http://stackoverflow.com/questions/2366/can-anyone-explain-monads)
*       [Monad in Plain English...](http://stackoverflow.com/questions/2704652/monad-in-plain-english-for-the-oop-programmer-with-no-fp-background)
*       [Monad in non-programming terms](http://stackoverflow.com/questions/3261729/monad-in-non-programming-terms)
*       [Real World Haskell: chapter on Monads](http://book.realworldhaskell.org/read/monads.html)
*       [Learn You a Haskell for Great Good: chapter on Functors, Applicative Functors and Monoids](http://www.learnyouahaskell.com/functors-applicative-functors-and-monoids)
*       Monads are Elephants:
[Part 1](http://james-iry.blogspot.com/2007/09/monads-are-elephants-part-1.html)
[Part 2](http://james-iry.blogspot.com/2007/10/monads-are-elephants-part-2.html)
[Part 3](http://james-iry.blogspot.com/2007/10/monads-are-elephants-part-3.html)
[Part 4](http://james-iry.blogspot.com/2007/11/monads-are-elephants-part-4.html)
*       [Brian Beckman: Don't fear the Monad (67 minute video)](http://channel9.msdn.com/shows/Going+Deep/Brian-Beckman-Dont-fear-the-Monads/)
*       [A monad non-tutorial...or why you shouldn't ask what a monad is](http://strongtyped.blogspot.com/2010/01/monad-non-tutorial.html)
*       [The Mother of all Monads](http://blog.sigfpe.com/2008/12/mother-of-all-monads.html)
*       [You Could Have Invented Monads! (And Maybe You Already Have.)](http://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html)
*       [Monads! (and Why Monad Tutorials Are All Awful)](http://ahamsandwich.wordpress.com/2007/07/26/monads-and-why-monad-tutorials-are-all-awful/)
*       [Of monads and spacesuits (archived)](http://www.iterasi.net/openviewer.aspx?sqrlitid=ixx7fcluvek_9lfolsxr_g)
*       [Haskell wikibook: Understanding monads](http://en.wikibooks.org/wiki/Haskell/Understanding_monads)
*       Haskell state monads: [part 1](http://mvanier.livejournal.com/1765.html) [part 2](http://mvanier.livejournal.com/1901.html)
*       [How not to explain Haskell monads](http://mvanier.livejournal.com/1205.html)
*       Yet Another Monad Tutorial: [part 1](http://mvanier.livejournal.com/3917.html) [part 2](http://mvanier.livejournal.com/4305.html)
        [part 3](http://mvanier.livejournal.com/4586.html) [part 4](http://mvanier.livejournal.com/4647.html)
*       [Research Papers/Monads and Arrows](http://www.haskell.org/haskellwiki/Research_papers/Monads_and_arrows)

## Monads in Category Theory ##

*       [Category Theory at SEP](http://plato.stanford.edu/entries/category-theory/)
*       [[!wikipedia Category theory]]
*       [[!wikipedia Category (mathematics) desc="Category"]]
*       [[!wikipedia Morphism]]
*       [[!wikipedia Functor]]
*       [[!wikipedia Natural transformation]]
*       [[!wikipedia Monad (category theory) desc="Monads in category theory"]]
*       [Haskell/Category Theory](http://en.wikibooks.org/wiki/Haskell/Category_theory)
*       [Category Theory & Functional Programming](http://blog.mestan.fr/2009/01/09/category-theory-functional-programming/)
*       [Learning Haskell through Category Theory, and Adventuring in Category Land](http://dekudekuplex.wordpress.com/2009/01/16/learning-haskell-through-category-theory-and-adventuring-in-category-land-like-flatterland-only-about-categories/)
*       [Resources for learning practical category theory](http://mathoverflow.net/questions/903/resources-for-learning-practical-category-theory)
*       [A Partial Ordering of some Category Theory applied to Haskell](http://blog.sigfpe.com/2010/03/partial-ordering-of-some-category.html)


## The Curry-Howard Correspondence ##
*       The [[!wikipedia Curry-Howard isomorphism]]
*       [The Curry-Howard correspondence in Haskell](http://www.thenewsh.com/~newsham/formal/curryhoward/)
*       [The Curry-Howard Isomorphism](http://en.wikibooks.org/wiki/Haskell/The_Curry-Howard_isomorphism) at Haskell wiki<p>


## Continuations ##

*       [[!wikipedia Continuation]]
*       [[!wikipedia Continuation-passing style]]
*       [[!wikipedia Call-with-current-continuation]]
*       [Intro to call/cc](http://community.schemewiki.org/?call-with-current-continuation) at SchemeWiki
*       [Call With Current Continuation](http://www.c2.com/cgi/wiki?CallWithCurrentContinuation)
*       [Continuations Made Simple and Illustrated](http://www.ps.uni-saarland.de/~duchier/python/continuations.html)
*       [Continuation kata](http://programming-musings.org/2006/02/12/continuation-kata/)
*       [Understanding continuations](http://keithdevens.com/weblog/archive/2004/Jul/11/continuations) [Commentary](http://lambda-the-ultimate.org/node/86)
*       [Continuations In Scheme](http://tech.phillipwright.com/2010/05/23/continuations-in-scheme/)
*       [Understanding Scheme Continuations](http://sanjaypande.blogspot.com/2004/06/understanding-scheme-continuations.html). This is tagged "Part I" but I think there's no further parts.
*       [Continuations for Curmudgeons](http://www.intertwingly.net/blog/2005/04/13/Continuations-for-Curmudgeons) [Commentary](http://lambda-the-ultimate.org/node/643)
*       [Haskell wiki on Continuations](http://www.haskell.org/haskellwiki/Continuation)<p>
*       [[!wikipedia Delimited continuation]]
*       [Composable Continuations Tutorial](http://community.schemewiki.org/?composable-continuations-tutorial) at SchemeWiki
*       [Post by Ken](http://lambda-the-ultimate.org/node/1197#comment-12927) on Lambda the Ultimate explaining difference between undelimited and delimited continuations
*       [shift, reset and streams](http://chneukirchen.org/blog/archive/2005/04/shift-reset-and-streams.html)
*       [guile and delimited continuations](http://www.wingolog.org/archives/2010/02/26/guile-and-delimited-continuations)
*       [Delimited continuations in Scala](http://blog.richdougherty.com/2009/02/delimited-continuations-in-scala_24.html)
*       [Delimited Continuations Explained (in Scala)](http://dcsobral.blogspot.com/2009/07/delimited-continuations-explained-in.html)
*       [Partial Continuations](http://www.bluishcoder.co.nz/articles/scheme/partial-continuations.html)
*       Delimited Continuations in MzScheme:
[Part 1](http://schemekeys.blogspot.com/2006/11/prompts-their-interaction-with-dynamic.html)
[Part 2](http://schemekeys.blogspot.com/2006/12/delimited-continuations-in-mzscheme.html)
[Part 3](http://schemekeys.blogspot.com/2007/01/going-further-with-primitives.html)
[Part 4](http://schemekeys.blogspot.com/2007/01/odd-and-ends.html)<p>
*       [Online Bibliography of Scheme Research: Continuations and Continuation Passing Style](http://library.readscheme.org/page6.html)
*       [Delimited continuations in natural language semantics](http://okmij.org/ftp/gengo/)


## Linear Logic ##

*       [[!wikipedia Linear logic]]