readings.mdwn

   1 [[!toc levels=3]]
   2
   3 ## Links to tutorials and other resources on Scheme, OCaml, and Haskell ##
   4
   5 *   Help on [[Learning Scheme]]
   6 *   Help on [[Learning OCaml]]
   7 *   Help on [[Learning Haskell]]
   8
   9
  10 <!-- -->
  11 *   This site's [[explanation of the differences|rosetta1]] between these languages
  12
  13
  14 ## Other Offsite Reading ##
  15
  16 *   [[Famous Computer Scientists|people]]
  17
  18
  19 ## Old links ##
  20
  21 *The links below are from the last time we taught the course; we should check them again...*
  22
  23 There's lots of links here already to tutorials and encyclopedia entries about many of the notions we'll be dealing with.
  24
  25 Many of these links are to Wikipedia. You can learn a lot from such articles,
  26 so long as you remember they may sometimes mislead or make mistakes. However, I
  27 hope at this point in your education you'll have learned to be a guarded reader
  28 even of authoritative treatises by eminent authors. So you shouldn't need any
  29 Wikipedia-specific warnings.
  30
  31 For most readers, many bits of reading we point you to will be hairy in one way
  32 or another. It may be aimed at audiences with more programming experience; it
  33 may be aimed at audiences with specific logical background you don't yet have;
  34 it may be aimed at audiences familiar with technical areas in linguistics you're
  35 first encountering. Or perhaps several of these at once. We hope you will
  36 already have mastered the skill of leveraged reading: getting what you can out
  37 of an article you don't fully understand, so that you can discuss it with the rest of
  38 the group and hopefully get to a point where you can read it again and
  39 get more out of. (Rinse and repeat.)
  40
  41 ### Functions ###
  42
  43 *       [[!wikipedia Higher-order function]]
  44 *       [[!wikipedia First-class function]]
  45 *       [[!wikipedia Currying]]
  46
  47 ### Functional vs imperative programming ###
  48
  49 *       [[!wikipedia Declarative programming]]
  50 *       [[!wikipedia Functional programming]]
  51 *       [[!wikipedia Purely functional]]
  52 *       [[!wikipedia Referential transparency (computer science)]]
  53 *       [[!wikipedia Side effect (computer science) desc="Side effects"]]
  54 *       [[!wikipedia Imperative programming]]
  55
  56 ### General issues about variables and scope in programming languages ###
  57
  58 *       [[!wikipedia Variable (programming) desc="Variables"]]
  59 *       [[!wikipedia Free variables and bound variables]]
  60 *       [[!wikipedia Variable shadowing]]
  61 *       [[!wikipedia Name binding]]
  62 *       [[!wikipedia Name resolution]]
  63 *       [[!wikipedia Parameter (computer science) desc="Function parameters"]]
  64 *       [[!wikipedia Scope (programming) desc="Variable scope"]]
  65 *       [[!wikipedia Closure (computer science) desc="Closures"]]
  66
  67
  68 ### Untyped lambda calculus and combinatory logic ###
  69
  70 *       [[Dana Scott's Turing centenary address on the lambda calculus|http://turing100.acm.org/lambda_calculus_timeline.pdf]]
  71 *       [[!wikipedia Lambda calculus]]
  72 <!~- 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. Curry then wrote "An analysis of logical substitution" which appeared in the American Journal of Mathematics in 1929. ~->
  73 *       [[!wikipedia Moses Schönfinkel]]
  74 *       [[!wikipedia Haskell Curry]]
  75 *       [[!wikipedia Alonzo Church]]<p>
  76 *       [[!wikipedia Church encoding]]
  77
  78 *       [[!wikipedia Combinatory logic]]
  79 *       [Combinatory logic](http://plato.stanford.edu/entries/logic-combinatory/) at the Stanford Encyclopedia of Philosophy
  80 *       [[!wikipedia SKI combinatory calculus]]
  81 *       [[!wikipedia B,C,K,W system]]
  82 *       Jeroen Fokker, "The Systematic Construction of a One-combinator Basis for Lambda-Terms" <cite>Formal Aspects of Computing</cite> 4 (1992), pp. 776-780.
  83         <http://people.cs.uu.nl/jeroen/article/combinat/combinat.ps>
  84 *       [Chris Barker's Iota and Jot](http://semarch.linguistics.fas.nyu.edu/barker/Iota/)<p>
  85
  86 *       [To Dissect a Mockingbird](http://dkeenan.com/Lambda/index.htm)
  87 *       [Combinator Birds](http://www.angelfire.com/tx4/cus/combinator/birds.html)
  88 *   [Les deux combinateurs et la totalite](http://www.paulbraffort.net/j_et_i/j_et_i.html) by Paul Braffort.
  89
  90 ### Evaluation Order ###
  91
  92 *       [[!wikipedia Evaluation strategy]]
  93 *       [[!wikipedia Eager evaluation]]
  94 *       [[!wikipedia Lazy evaluation]]
  95 *       [[!wikipedia Strict programming language]]
  96
  97 ### Confluence, Normalization, Undecidability ###
  98
  99 *       [[!wikipedia Church-Rosser theorem]]
 100 *       [[!wikipedia Normalization property]]
 101 *       [[!wikipedia Turing completeness]]<p>
 102 *       [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
 103
 104
 105 ### Recursion and the Y Combinator ###
 106
 107 *       [[!wikipedia Recursion (computer science) desc="Recursion"]]
 108 *       [[!wikipedia Y combinator]]
 109 *       [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..."
 110 *       [The Y combinator](http://mvanier.livejournal.com/2700.html)
 111 *       [The Why of Y](http://www.dreamsongs.com/NewFiles/WhyOfY.pdf)
 112 *       [The Y Combinator (Slight Return), or: How to Succeed at Recursion Without Really Recursing](http://mvanier.livejournal.com/2897.html)
 113 *       [Y Combinator for Dysfunctional Non-Schemers](http://rayfd.wordpress.com/2007/05/06/y-combinator-for-dysfunctional-non-schemers/)
 114 *       [The Y Combinator](http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html)
 115 *       [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...
 116 *   [The church of the least fixed point, by Sans Pareil](http://www.springerlink.com/content/n4t2v573m58g2755/)
 117
 118 ### Folds ###
 119
 120 *    [[!wikipedia Fold (higher-order function)]]
 121
 122
 123 ### Types ###
 124
 125 *       [[!wikipedia Typed lambda calculus]]
 126 *       [[!wikipedia Simply typed lambda calculus]]
 127 *       [Type Theory](http://plato.stanford.edu/entries/type-theory/) at the Stanford Encyclopedia of Philosophy
 128 *       [Church's Type Theory](http://plato.stanford.edu/entries/type-theory-church/) at the Stanford Encyclopedia of Philosophy
 129 *       [[!wikipedia Type polymorphism]]
 130 *       [[!wikipedia System F]]
 131 <p>
 132 *       [[!wikipedia Tagged union]]
 133 *       [[!wikipedia Algebraic data type]]
 134 *       [[!wikipedia Recursive data type]]
 135 *       [[!wikipedia Pattern matching]]
 136 *       [[!wikipedia Unit type]]
 137 *       [[!wikipedia Bottom type]]
 138
 139
 140
 141 ### Monads ###
 142 *       [[!wikipedia Monad (functional programming) desc="Monads in Functional Programming"]]
 143 *       [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.
 144 *       [A Gentle Intro to Haskell: About Monads](http://www.haskell.org/tutorial/monads.html) (link currently broken, check <http://www.haskell.org/haskellwiki/Tutorials>)
 145 *       [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))
 146 *       From HaskwellWiki:
 147         [Monad tutorials timeline](http://www.haskell.org/haskellwiki/Monad_tutorials_timeline)
 148         | [Monad laws](http://www.haskell.org/haskellwiki/Monad_Laws)
 149         | [Monads as computation](http://www.haskell.org/haskellwiki/Monads_as_computation)
 150         | [Monads as containers](http://www.haskell.org/haskellwiki/Monads_as_containers)
 151         | [What a monad is not](http://www.haskell.org/haskellwiki/What_a_Monad_is_not)
 152 *       [Haskell wikibook: Understanding monads](http://en.wikibooks.org/wiki/Haskell/Understanding_monads)
 153 *       [Haskell wikibook: Monad Transformers](http://en.wikibooks.org/wiki/Haskell/Monad_transformers)
 154
 155 *       [A State Monad Tutorial](http://strabismicgobbledygook.wordpress.com/2010/03/06/a-state-monad-tutorial/)
 156 *       [You Could Have Invented Monads! (And Maybe You Already Have.)](http://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html)
 157 *       Yet Another Monad Tutorial: [part 1](http://mvanier.livejournal.com/3917.html) [part 2](http://mvanier.livejournal.com/4305.html)
 158 *       [Monads for the Working Haskell Programmer -- a short tutorial](http://www.engr.mun.ca/~theo/Misc/haskell_and_monads.htm)
 159 *       [Introduction to Haskell: Monads](http://onlamp.com/pub/a/onlamp/2007/08/02/introduction-to-haskell-pure-functions.html)
 160 *       [SPb Haskell User Group: Monad tutorial](http://spbhug.folding-maps.org/wiki/MonadsEn)
 161 *       [Understanding Haskell Monads](http://ertes.de/articles/monads.html)
 162 *       [A Monad Tutorial for OCaml](http://enfranchisedmind.com/blog/posts/a-monad-tutorial-for-ocaml/)
 163 *       [Beyond Monads](http://blog.sigfpe.com/2009/02/beyond-monads.html)
 164 *       [Simple Explanation of a Monad](http://math.stackexchange.com/questions/405/simple-explanation-of-a-monad)
 165 *       [What is a Monad?](http://stackoverflow.com/questions/44965/what-is-a-monad)
 166 *       [Can Anyone Explain Monads?](http://stackoverflow.com/questions/2366/can-anyone-explain-monads)
 167 *       [Monad in Plain English...](http://stackoverflow.com/questions/2704652/monad-in-plain-english-for-the-oop-programmer-with-no-fp-background)
 168 *       [Monad in non-programming terms](http://stackoverflow.com/questions/3261729/monad-in-non-programming-terms)
 169 *       [Real World Haskell: chapter on Monads](http://book.realworldhaskell.org/read/monads.html)
 170 *       [Learn You a Haskell for Great Good: chapter on Functors, Applicative Functors and Monoids](http://www.learnyouahaskell.com/functors-applicative-functors-and-monoids)
 171 *       Monads are Elephants:
 172 [Part 1](http://james-iry.blogspot.com/2007/09/monads-are-elephants-part-1.html)
 173 [Part 2](http://james-iry.blogspot.com/2007/10/monads-are-elephants-part-2.html)
 174 [Part 3](http://james-iry.blogspot.com/2007/10/monads-are-elephants-part-3.html)
 175 [Part 4](http://james-iry.blogspot.com/2007/11/monads-are-elephants-part-4.html)
 176 *       [Brian Beckman: Don't fear the Monad (67 minute video)](http://channel9.msdn.com/shows/Going+Deep/Brian-Beckman-Dont-fear-the-Monads/)
 177 *       [A monad non-tutorial...or why you shouldn't ask what a monad is](http://strongtyped.blogspot.com/2010/01/monad-non-tutorial.html)
 178 *       [Abstraction, intuition, and the "monad tutorial fallacy"](http://byorgey.wordpress.com/2009/01/12/abstraction-intuition-and-the-monad-tutorial-fallacy/)
 179 *       [How you should(n't) use Monad](http://noordering.wordpress.com/2009/03/31/how-you-shouldnt-use-monad/)
 180 *       [The Mother of all Monads](http://blog.sigfpe.com/2008/12/mother-of-all-monads.html)
 181 *       [Monads! (and Why Monad Tutorials Are All Awful)](http://ahamsandwich.wordpress.com/2007/07/26/monads-and-why-monad-tutorials-are-all-awful/)
 182 *       [Of monads and spacesuits (archived)](http://www.iterasi.net/openviewer.aspx?sqrlitid=ixx7fcluvek_9lfolsxr_g)
 183 *       [How not to explain Haskell monads](http://mvanier.livejournal.com/1205.html)
 184 *       [The State Monad: a tutorial for the confused?](http://coder.bsimmons.name/blog/2009/10/the-state-monad-a-tutorial-for-the-confused/)
 185 *       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>
 186 *       [Research Papers/Monads and Arrows](http://www.haskell.org/haskellwiki/Research_papers/Monads_and_arrows)
 187 *       [Eugenio Moggi, Notions of Computation and Monads](http://www.disi.unige.it/person/MoggiE/ftp/ic91.pdf): Information and Computation 93 (1) 1991.
 188 *       [Philip Wadler. The essence of functional programming](http://homepages.inf.ed.ac.uk/wadler/papers/essence/essence.ps):
 189 invited talk, *19'th Symposium on Principles of Programming Languages*, ACM Press, Albuquerque, January 1992.
 190 <!~-    This paper explores the use monads to structure functional programs. No prior knowledge of monads or category theory is required.
 191         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.
 192         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.~->
 193 *       [Philip Wadler. Monads for Functional Programming](http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf):
 194 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.
 195 <!~-    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.~->
 196 *       Ken Shan [Monads for natural language semantics](http://arxiv.org/abs/cs/0205026v1) (2001) uses reader monad to implement intensionality.
 197 *       Ben-Avi and Winter [A modular approach to intensionality](http://parles.upf.es/glif/pub/sub11/individual/bena_wint.pdf) (2007) reinvents the technique.
 198         <!~- http://citeseerx.ist.psu.edu/viewdocsummary?doi=10.1.1.73.6927 ~->
 199 *       Monsters and context-shifting, e.g. Gillies/von Fintel on "ifs" [not sure which paper]
 200
 201
 202 ### Monads in Category Theory ###
 203
 204 *       [Category Theory at SEP](http://plato.stanford.edu/entries/category-theory/)
 205 *       [[!wikipedia Category theory]]
 206 *       [[!wikipedia Category (mathematics) desc="Category"]]
 207 *       [[!wikipedia Morphism]]
 208 *       [[!wikipedia Functor]]
 209 *       [[!wikipedia Natural transformation]]
 210 *       [[!wikipedia Monad (category theory) desc="Monads in category theory"]]
 211 *       [Haskell/Category Theory](http://en.wikibooks.org/wiki/Haskell/Category_theory)
 212 *       [Category Theory & Functional Programming](http://blog.mestan.fr/2009/01/09/category-theory-functional-programming/)
 213 *       [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/)
 214 *       [Resources for learning practical category theory](http://mathoverflow.net/questions/903/resources-for-learning-practical-category-theory)
 215 *       [A Partial Ordering of some Category Theory applied to Haskell](http://blog.sigfpe.com/2010/03/partial-ordering-of-some-category.html)
 216
 217
 218 ### Side-effects / mutation ###
 219
 220 *       [[!wikipedia Referential transparency (computer science)]]
 221 *       [[!wikipedia Side effect (computer science) desc="Side effects"]]
 222 *       [[!wikipedia Imperative programming]]
 223 *       [[!wikipedia Reference (computer science) desc="References"]]
 224 *       [[!wikipedia Pointer (computing) desc="Pointers"]]
 225 *       [Pointers in OCaml](http://caml.inria.fr/resources/doc/guides/pointers.html)
 226
 227
 228 ### Continuations ###
 229
 230 *       [[!wikipedia Continuation]]
 231 *       [[!wikipedia Continuation-passing style]]
 232 *       [[!wikipedia Call-with-current-continuation]]
 233 *       [Intro to call/cc](http://community.schemewiki.org/?call-with-current-continuation) at SchemeWiki
 234 *       [Call With Current Continuation](http://www.c2.com/cgi/wiki?CallWithCurrentContinuation)
 235 *       [Continuations Made Simple and Illustrated](http://www.ps.uni-saarland.de/~duchier/python/continuations.html)
 236 *       [Continuation kata](http://programming-musings.org/2006/02/12/continuation-kata/)
 237 *       [Understanding continuations](http://keithdevens.com/weblog/archive/2004/Jul/11/continuations) [Commentary](http://lambda-the-ultimate.org/node/86)
 238 *       [Continuations In Scheme](http://tech.phillipwright.com/2010/05/23/continuations-in-scheme/)
 239 *       [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.
 240 *       [Continuations for Curmudgeons](http://www.intertwingly.net/blog/2005/04/13/Continuations-for-Curmudgeons) [Commentary](http://lambda-the-ultimate.org/node/643)
 241 *       [Haskell wiki on Continuations](http://www.haskell.org/haskellwiki/Continuation)
 242 *       [Haskell wikibook on Continuation Passing Style](http://en.wikibooks.org/wiki/Haskell/Continuation_passing_style)<p>
 243 *       [[!wikipedia Delimited continuation]]
 244 *       [Composable Continuations Tutorial](http://community.schemewiki.org/?composable-continuations-tutorial) at SchemeWiki
 245 *       [Post by Ken](http://lambda-the-ultimate.org/node/1197#comment-12927) on Lambda the Ultimate explaining difference between undelimited and delimited continuations
 246 *       [shift, reset and streams](http://chneukirchen.org/blog/archive/2005/04/shift-reset-and-streams.html)
 247 *       [guile and delimited continuations](http://www.wingolog.org/archives/2010/02/26/guile-and-delimited-continuations)
 248 *       [Delimited continuations in Scala](http://blog.richdougherty.com/2009/02/delimited-continuations-in-scala_24.html)
 249 *       [Delimited Continuations Explained (in Scala)](http://dcsobral.blogspot.com/2009/07/delimited-continuations-explained-in.html)
 250 *       [Partial Continuations](http://www.bluishcoder.co.nz/articles/scheme/partial-continuations.html)
 251 *       Delimited Continuations in MzScheme:
 252 [Part 1](http://schemekeys.blogspot.com/2006/11/prompts-their-interaction-with-dynamic.html)
 253 [Part 2](http://schemekeys.blogspot.com/2006/12/delimited-continuations-in-mzscheme.html)
 254 [Part 3](http://schemekeys.blogspot.com/2007/01/going-further-with-primitives.html)
 255 [Part 4](http://schemekeys.blogspot.com/2007/01/odd-and-ends.html)<p>
 256 *       [Online Bibliography of Scheme Research: Continuations and Continuation Passing Style](http://library.readscheme.org/page6.html)
 257 *       [Delimited continuations in natural language semantics](http://okmij.org/ftp/gengo/)
 258
 259
 260 ### The Curry-Howard Correspondence ###
 261 *       The [[!wikipedia Curry-Howard isomorphism]]
 262 *       [The Curry-Howard correspondence in Haskell](http://www.thenewsh.com/~newsham/formal/curryhoward/)
 263 *       [Haskell wikibook on the Curry-Howard Isomorphism](http://en.wikibooks.org/wiki/Haskell/The_Curry-Howard_isomorphism) at Haskell wiki<p>
 264
 265
 266
 267 ### Linear Logic ###
 268
 269 *       [[!wikipedia Linear logic]]
 270
 271