X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=readings.mdwn;fp=readings.mdwn;h=c15315d63acf623d48a3f66a3721988cd4b724f2;hp=d4ce173871a5ce637c6cdae2483c392ea217566e;hb=b5f033198b60cd8029897619b49fd966b6a59291;hpb=3a75b22ef54002db4bc86c3eada18319c80daa87

diff --git a/readings.mdwn b/readings.mdwn
index d4ce1738..c15315d6 100644
--- a/readings.mdwn
+++ b/readings.mdwn
@@ -8,7 +8,258 @@
 <!--
 *   [[Translating between OCaml Scheme and Haskell]]
 
-_offsite_reading.mdwn
+-->
+
+<!--
 There's lots of links here already to tutorials and encyclopedia entries about many of the notions we'll be dealing with.
 
+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 Side effect (computer science) desc="Side effects"]]
+*	[[!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/)
+
+## Folds ##
+
+*    [[!wikipedia Fold (higher-order function)]]
+
+
+## Types ##
+
+*	[[!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]]
+<p>
+*	[[!wikipedia Tagged union]]
+*	[[!wikipedia Algebraic data type]]
+*	[[!wikipedia Recursive data type]]
+*	[[!wikipedia Pattern matching]]
+*	[[!wikipedia Unit type]]
+*	[[!wikipedia Bottom type]]
+
+
+##[[Learning OCaml]]##
+
+
+## Monads ##
+*	[[!wikipedia Monad (functional programming) desc="Monads in Functional Programming"]]
+*	[Daniel Friedman. A Schemer's View of Monads](/schemersviewofmonads.ps): from <https://www.cs.indiana.edu/cgi-pub/c311/doku.php?id=home> but the link above is to a local copy.
+*	[A Gentle Intro to Haskell: About Monads](http://www.haskell.org/tutorial/monads.html) (link currently broken, check <http://www.haskell.org/haskellwiki/Tutorials>)
+*	[All About Monads](http://haskell.org/all_about_monads/html/index.html) (also broken, here's an [archived version](http://web.archive.org/web/20071013115156/haskell.org/all_about_monads/html/index.html))
+*	From HaskwellWiki:
+	[Monad tutorials timeline](http://www.haskell.org/haskellwiki/Monad_tutorials_timeline)
+	| [Monad laws](http://www.haskell.org/haskellwiki/Monad_Laws)
+	| [Monads as computation](http://www.haskell.org/haskellwiki/Monads_as_computation)
+	| [Monads as containers](http://www.haskell.org/haskellwiki/Monads_as_containers)
+	| [What a monad is not](http://www.haskell.org/haskellwiki/What_a_Monad_is_not)
+*	[Haskell wikibook: Understanding monads](http://en.wikibooks.org/wiki/Haskell/Understanding_monads)
+*	[Haskell wikibook: Monad Transformers](http://en.wikibooks.org/wiki/Haskell/Monad_transformers)
+
+*	[A State Monad Tutorial](http://strabismicgobbledygook.wordpress.com/2010/03/06/a-state-monad-tutorial/)
+*	[You Could Have Invented Monads! (And Maybe You Already Have.)](http://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html)
+*	Yet Another Monad Tutorial: [part 1](http://mvanier.livejournal.com/3917.html) [part 2](http://mvanier.livejournal.com/4305.html)
+*	[Monads for the Working Haskell Programmer -- a short tutorial](http://www.engr.mun.ca/~theo/Misc/haskell_and_monads.htm)
+*	[Introduction to Haskell: Monads](http://onlamp.com/pub/a/onlamp/2007/08/02/introduction-to-haskell-pure-functions.html)
+*	[SPb Haskell User Group: Monad tutorial](http://spbhug.folding-maps.org/wiki/MonadsEn)
+*	[Understanding Haskell Monads](http://ertes.de/articles/monads.html)
+*	[A Monad Tutorial for OCaml](http://enfranchisedmind.com/blog/posts/a-monad-tutorial-for-ocaml/)
+*	[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)
+*	[Abstraction, intuition, and the "monad tutorial fallacy"](http://byorgey.wordpress.com/2009/01/12/abstraction-intuition-and-the-monad-tutorial-fallacy/)
+*	[How you should(n't) use Monad](http://noordering.wordpress.com/2009/03/31/how-you-shouldnt-use-monad/)
+*	[The Mother of all Monads](http://blog.sigfpe.com/2008/12/mother-of-all-monads.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)
+*	[How not to explain Haskell monads](http://mvanier.livejournal.com/1205.html)
+*	[The State Monad: a tutorial for the confused?](http://coder.bsimmons.name/blog/2009/10/the-state-monad-a-tutorial-for-the-confused/)
+*	Haskell state monads: [part 1](http://mvanier.livejournal.com/1765.html) [part 2](http://mvanier.livejournal.com/1901.html) [part 3](http://mvanier.livejournal.com/4586.html) [part 4](http://mvanier.livejournal.com/4647.html)<p>
+*	[Research Papers/Monads and Arrows](http://www.haskell.org/haskellwiki/Research_papers/Monads_and_arrows)
+*	[Eugenio Moggi, Notions of Computation and Monads](http://www.disi.unige.it/person/MoggiE/ftp/ic91.pdf): Information and Computation 93 (1) 1991.
+*	[Philip Wadler. The essence of functional programming](http://homepages.inf.ed.ac.uk/wadler/papers/essence/essence.ps):
+invited talk, *19'th Symposium on Principles of Programming Languages*, ACM Press, Albuquerque, January 1992.
+<!~-	This paper explores the use monads to structure functional programs. No prior knowledge of monads or category theory is required.
+	Monads increase the ease with which programs may be modified. They can mimic the effect of impure features such as exceptions, state, and continuations; and also provide effects not easily achieved with such features. The types of a program reflect which effects occur.
+	The first section is an extended example of the use of monads. A simple interpreter is modified to support various extra features: error messages, state, output, and non-deterministic choice. The second section describes the relation between monads and continuation-passing style. The third section sketches how monads are used in a compiler for Haskell that is written in Haskell.~->
+*	[Philip Wadler. Monads for Functional Programming](http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf):
+in M. Broy, editor, *Marktoberdorf Summer School on Program Design Calculi*, Springer Verlag, NATO ASI Series F: Computer and systems sciences, Volume 118, August 1992. Also in J. Jeuring and E. Meijer, editors, *Advanced Functional Programming*, Springer Verlag, LNCS 925, 1995. Some errata fixed August 2001.
+<!~-	The use of monads to structure functional programs is described. Monads provide a convenient framework for simulating effects found in other languages, such as global state, exception handling, output, or non-determinism. Three case studies are looked at in detail: how monads ease the modification of a simple evaluator; how monads act as the basis of a datatype of arrays subject to in-place update; and how monads can be used to build parsers.~->
+*	Ken Shan [Monads for natural language semantics](http://arxiv.org/abs/cs/0205026v1) (2001) uses reader monad to implement intensionality.
+*	Ben-Avi and Winter [A modular approach to intensionality](http://parles.upf.es/glif/pub/sub11/individual/bena_wint.pdf) (2007) reinvents the technique.
+	<!~- http://citeseerx.ist.psu.edu/viewdocsummary?doi=10.1.1.73.6927 ~->
+*	Monsters and context-shifting, e.g. Gillies/von Fintel on "ifs" [not sure which paper]
+
+
+## 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)
+
+
+## Side-effects / mutation ##
+
+*	[[!wikipedia Referential transparency (computer science)]]
+*	[[!wikipedia Side effect (computer science) desc="Side effects"]]
+*	[[!wikipedia Imperative programming]]
+*	[[!wikipedia Reference (computer science) desc="References"]]
+*	[[!wikipedia Pointer (computing) desc="Pointers"]]
+*	[Pointers in OCaml](http://caml.inria.fr/resources/doc/guides/pointers.html)
+
+
+## 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)
+*	[Haskell wikibook on Continuation Passing Style](http://en.wikibooks.org/wiki/Haskell/Continuation_passing_style)<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/)
+
+
+## The Curry-Howard Correspondence ##
+*	The [[!wikipedia Curry-Howard isomorphism]]
+*	[The Curry-Howard correspondence in Haskell](http://www.thenewsh.com/~newsham/formal/curryhoward/)
+*	[Haskell wikibook on the Curry-Howard Isomorphism](http://en.wikibooks.org/wiki/Haskell/The_Curry-Howard_isomorphism) at Haskell wiki<p>
+
+
+
+## Linear Logic ##
+
+*	[[!wikipedia Linear logic]]
+
+
 -->