offsite_reading.mdwn

   1 Many off these links are to Wikipedia. You can learn a lot from such articles,
   2 so long as you remember they may sometimes mislead or make mistakes. However, I
   3 hope at this point in your education you'll have learned to be a guarded reader
   4 even of authoritative treatises by eminent authors. So you shouldn't need any
   5 Wikipedia-specific warnings.
   6
   7 For most readers, many bits of reading we point you to will be hairy in one way
   8 or another. It may be aimed at audiences with more programming experience; it
   9 may be aimed at audiences with specific logical background you don't yet have;
  10 it may be aimed at audiences familiar with technical areas in linguistics you're
  11 first encountering. Or perhaps several of these at once. We hope you will
  12 already have mastered the skill of leveraged reading: getting what you can out
  13 of an article you don't fully understand, so that you can discuss it with the rest of
  14 the group and hopefully get to a point where you can read it again and
  15 get more out of out. (Rinse and repeat.)
  16
  17
  18 ## General issues about variables and binding in programming languages ##
  19
  20 *       [[!wikipedia Variable (programming) desc="Variables"]]
  21 *       [[!wikipedia Variable shadowing]]
  22 *       [[!wikipedia Scope (programming) desc="Variable scope"]]
  23 *       [[!wikipedia Free variables and bound variables]]
  24 *       [[!wikipedia Name binding]]
  25 *       [[!wikipedia Name resolution]]
  26 *       [[!wikipedia Parameter (computer science) desc="Function parameters"]]
  27
  28 ## Functions as values, etc ##
  29
  30 *       [[!wikipedia Higher-order function]]
  31 *       [[!wikipedia First-class function]]
  32 *       [[!wikipedia Closure (computer science) desc="Closures"]]
  33 *       [[!wikipedia Currying]]
  34
  35 ## Functional vs imperative programming ##
  36
  37 *       [[!wikipedia Declarative programming]]
  38 *       [[!wikipedia Functional programming]]
  39 *       [[!wikipedia Purely functional]]
  40 *       [[!wikipedia Referential transparency (computer science)]]
  41 *       [[!wikipedia Imperative programming]]
  42
  43 ## Untyped lambda calculus and combinatory logic ##
  44
  45 *       [[!wikipedia Lambda calculus]]
  46 *       [Chris Barker's Lambda Tutorial](http://homepages.nyu.edu/~cb125/Lambda)
  47 *       [Lambda Animator](http://thyer.name/lambda-animator/)<p>
  48 *       [[!wikipedia Haskell Curry]]
  49 *       [[!wikipedia Moses Schönfinkel]]
  50 *       [[!wikipedia Alonzo Church]]<p>
  51 *       [[!wikipedia Combinatory logic]]
  52 *       [Combinatory logic](http://plato.stanford.edu/entries/logic-combinatory/) at the Stanford Encyclopedia of Philosophy
  53 *       [[!wikipedia SKI combinatory calculus]]<p>
  54 *       [[!wikipedia B,C,K,W system]]
  55 *       [[!wikipedia Church-Rosser theorem]]
  56 *       [[!wikipedia Normalization property]]
  57 *       [[!wikipedia Turing completeness]]<p>
  58 *       [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
  59 *       [[!wikipedia Church encoding]]
  60
  61 ## Learning Scheme ##
  62
  63 *       [[!wikipedia Scheme (programming language) desc="Wikipedia overview of Scheme"]]
  64
  65 *       If you are new to programming or if you have the patience to work through a textbook, you should work through a textbook. Some good choices are The Little Schemer book(s) we recommended for the seminar; and also:
  66
  67         +       [How to Design Programs](http://www.htdp.org/2003-09-26/), by Matthias Felleisen, et al., which the Racket groups recommends. Whenever the book says "Scheme," you can read it as "Racket."
  68
  69         Another warmly-recommended introduction available online is [Teach Yourself Scheme in Fixnum Days](http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme.html) This is a short introductory text that introduces common Scheme techniques.
  70
  71 *       If you're already a programmer and you're in more of a hurry, you could instead look at the [Quick Introduction to Racket](http://docs.racket-lang.org/quick/index.html). This tutorial provides a brief introduction to the Racket programming language by using DrRacket and one of Racket's picture-drawing libraries.
  72
  73 *       [An Introduction to Lambda Calculus and Scheme](http://www.jetcafe.org/~jim/lambda.html) is also aimed at programmers.
  74
  75 *       After any of the preceding, you could move on to [Racket Guide](http://docs.racket-lang.org/guide/index.html). This starts with a tutorial on Racket basics; then it describes the rest of the Racket language. This guide is intended for programmers who are new to Racket or new to some part of Racket. It assumes programming experience, so if you are new to programming, you should instead start with one of the textbooks listed above. This Guide describes parts of the Racket language which go beyond the learning-oriented fragments of How to Design Programs.
  76
  77 *       The [Complete Racket Reference Manual](http://docs.racket-lang.org/reference/index.html) defines the core Racket language and describes its most prominent libraries. The Racket Guide is friendlier; though less precise and less complete.
  78
  79 *       The Scheme language is standardized; the various implementations of the
  80 language usually adhere to what's published in the current standard and add on
  81 different handy extensions. The first standard was published in 1975. A
  82 revision was published in 1978 called "The revised report on Scheme, a
  83 dialect of Lisp." Thereafter, revisions of the standard were titled "The
  84 Revised Revised Report..." and so on, or "The Revised^n Report..." for
  85 short. One widely implemented standard is [The
  86 Revised^5 Report on Scheme](http://www.schemers.org/Documents/Standards/R5RS/HTML/),
  87 or R5RS, published in 1998.
  88 A new standard [R6RS](http://www.r6rs.org/final/html/r6rs/r6rs.html) was ratified
  89 in 2007, but this has many detractors and has not been fully accepted in the
  90 community. ([Libraries for R6RS](http://www.r6rs.org/final/html/r6rs-lib/r6rs-lib.html))
  91
  92 *       [Scheme FAQ](http://community.schemewiki.org/?scheme-faq)
  93 *       [Scheme Requests for Implementation](http://srfi.schemers.org/) (SRFI)
  94 *       The [Schematics Scheme Cookbook](http://schemecookbook.org/) is a collaborative effort to produce documentation and recipes for using Scheme for common tasks.
  95
  96
  97 ## Recursion and the Y Combinator ##
  98
  99 *       [[!wikipedia Recursion (computer science) desc="Recursion"]]
 100 *       [[!wikipedia Y combinator]]
 101 *       [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..."
 102 *       [The Y combinator](http://mvanier.livejournal.com/2700.html)
 103 *       [The Why of Y](http://www.dreamsongs.com/NewFiles/WhyOfY.pdf)
 104 *       [The Y Combinator (Slight Return), or: How to Succeed at Recursion Without Really Recursing](http://mvanier.livejournal.com/2897.html)
 105 *       [Y Combinator for Dysfunctional Non-Schemers](http://rayfd.wordpress.com/2007/05/06/y-combinator-for-dysfunctional-non-schemers/)
 106 *       [The Y Combinator](http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html)
 107 *       [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...
 108
 109 ## Evaluation Order ##
 110
 111 *       [[!wikipedia Evaluation strategy]]
 112 *       [[!wikipedia Eager evaluation]]
 113 *       [[!wikipedia Lazy evaluation]]
 114 *       [[!wikipedia Strict programming language]]
 115
 116
 117 ## Types ##
 118
 119 *       [[!wikipedia Tagged union]]
 120 *       [[!wikipedia Algebraic data type]]
 121 *       [[!wikipedia Pattern matching]]
 122 *       [[!wikipedia Unit type]]
 123 *       [[!wikipedia Bottom type]]
 124 *       [[!wikipedia Typed lambda calculus]]
 125 *       [[!wikipedia Simply typed lambda calculus]]
 126 *       [Type Theory](http://plato.stanford.edu/entries/type-theory/) at the Stanford Encyclopedia of Philosophy
 127 *       [Church's Type Theory](http://plato.stanford.edu/entries/type-theory-church/) at the Stanford Encyclopedia of Philosophy
 128 *       The [[!wikipedia Curry-Howard isomorphism]]
 129 *       [The Curry-Howard correspondence in Haskell](http://www.thenewsh.com/~newsham/formal/curryhoward/)<p>
 130 *       [[!wikipedia Type polymorphism]]
 131 *       [[!wikipedia System F]]
 132
 133 ## Learning OCaml ##
 134
 135 *       [[!wikipedia Objective Caml desc="Wikipedia overview of OCaml"]]
 136
 137 *       [A Concise Introduction to Objective Caml](http://www.csc.villanova.edu/~dmatusze/resources/ocaml/ocaml.html)
 138
 139 *       Here are [two](http://www.cs.jhu.edu/~scott/pl/lectures/caml-intro.html) [other](http://pauillac.inria.fr/caml/FAQ/stephan.html) brief overviews of OCaml, aimed at readers who already have some programming experience. Here are [two](http://pauillac.inria.fr/caml/FAQ/exemples-eng.html) [more](http://pauillac.inria.fr/caml/FAQ/qrg-eng.html), even briefer.
 140
 141 *       Here's a [more detailed tutorial](http://www.ocaml-tutorial.org/) for OCaml.
 142
 143 *       Jason Hickey has posted a [draft of a nice book introducing OCaml](http://www.cs.caltech.edu/courses/cs134/cs134b/book.pdf).
 144
 145 *       FAQs for [OCaml Beginners](http://pauillac.inria.fr/caml/FAQ/FAQ_DEBUTANT-eng.html), and [a few more](http://caml.inria.fr/resources/doc/faq/). Also FAQs for [OCaml Experts](http://pauillac.inria.fr/caml/FAQ/FAQ_EXPERT-eng.html).
 146
 147
 148 ## Side-effects / mutation ##
 149
 150 *       [[!wikipedia Side effect (computer science) desc="Side effects"]]
 151 *       [[!wikipedia Reference (computer science) desc="References"]]
 152 *       [[!wikipedia Pointer (computing) desc="Pointers"]]
 153 *       [Pointers in OCaml](http://caml.inria.fr/resources/doc/guides/pointers.html)
 154
 155 ## Monads ##
 156
 157 *       [[!wikipedia Monad (functional programming) desc="Monads in Functional Programming"]]
 158
 159 *       [A Gentle Intro to Haskell: About Monads](http://www.haskell.org/tutorial/monads.html)
 160
 161 *       [Understanding Haskell Monads](http://ertes.de/articles/monads.html)
 162
 163 *       [The State Monad: a tutorial for the confused?](http://coder.bsimmons.name/blog/2009/10/the-state-monad-a-tutorial-for-the-confused/)
 164
 165 *       [Beyond Monads](http://blog.sigfpe.com/2009/02/beyond-monads.html)
 166
 167 *       [Simple Explanation of a Monad](http://math.stackexchange.com/questions/405/simple-explanation-of-a-monad)
 168
 169 *       [What is a Monad?](http://stackoverflow.com/questions/44965/what-is-a-monad)
 170
 171 *       [Can Anyone Explain Monads?](http://stackoverflow.com/questions/2366/can-anyone-explain-monads)
 172
 173 *       [Monad in Plain English...](http://stackoverflow.com/questions/2704652/monad-in-plain-english-for-the-oop-programmer-with-no-fp-background)
 174
 175 *       [Monad in non-programming terms](http://stackoverflow.com/questions/3261729/monad-in-non-programming-terms)
 176
 177 *       [Real World Haskell: chapter on Monads](http://book.realworldhaskell.org/read/monads.html)
 178
 179 *       [Learn You a Haskell for Great Good: chapter on Functors, Applicative Functors and Monoids](http://www.learnyouahaskell.com/functors-applicative-functors-and-monoids)
 180
 181 *       Monads are Elephants:
 182 [Part 1](http://james-iry.blogspot.com/2007/09/monads-are-elephants-part-1.html)
 183 [Part 2](http://james-iry.blogspot.com/2007/10/monads-are-elephants-part-2.html)
 184 [Part 3](http://james-iry.blogspot.com/2007/10/monads-are-elephants-part-3.html)
 185 [Part 4](http://james-iry.blogspot.com/2007/11/monads-are-elephants-part-4.html)
 186
 187 *       [Brian Beckman: Don't fear the Monad (67 minute video)](http://channel9.msdn.com/shows/Going+Deep/Brian-Beckman-Dont-fear-the-Monads/)
 188
 189 *       [A monad non-tutorial...or why you shouldn't ask what a monad is](http://strongtyped.blogspot.com/2010/01/monad-non-tutorial.html)
 190
 191 *       [The Mother of all Monads](http://blog.sigfpe.com/2008/12/mother-of-all-monads.html)
 192
 193 *       [You Could Have Invented Monads! (And Maybe You Already Have.)](http://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html)
 194
 195 *       [Monads! (and Why Monad Tutorials Are All Awful)](http://ahamsandwich.wordpress.com/2007/07/26/monads-and-why-monad-tutorials-are-all-awful/)
 196
 197 *       [Of monads and spacesuits (archived)](http://www.iterasi.net/openviewer.aspx?sqrlitid=ixx7fcluvek_9lfolsxr_g)
 198
 199 *       [Haskell wikibook: Understanding monads](http://en.wikibooks.org/wiki/Haskell/Understanding_monads)
 200
 201 *       Haskell state monads: [part 1](http://mvanier.livejournal.com/1765.html) [part 2](http://mvanier.livejournal.com/1901.html)
 202
 203 *       [How not to explain Haskell monads](http://mvanier.livejournal.com/1205.html)
 204
 205 *       Yet Another Monad Tutorial: [part 1](http://mvanier.livejournal.com/3917.html) [part 2](http://mvanier.livejournal.com/4305.html)
 206         [part 3](http://mvanier.livejournal.com/4586.html) [part 4](http://mvanier.livejournal.com/4647.html)
 207
 208 *       [Research Papers/Monads and Arrows](http://www.haskell.org/haskellwiki/Research_papers/Monads_and_arrows)
 209
 210 *       [Philip Wadler. Monads for Functional Programming](http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf):
 211 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.
 212
 213         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.
 214
 215 *       [Philip Wadler. The essence of functional programming](http://homepages.inf.ed.ac.uk/wadler/papers/essence/essence.ps):
 216 invited talk, *19'th Symposium on Principles of Programming Languages*, ACM Press, Albuquerque, January 1992.
 217
 218         This paper explores the use monads to structure functional programs. No prior knowledge of monads or category theory is required.
 219
 220         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.
 221
 222         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.
 223
 224 ## Monads in Category Theory ##
 225
 226 *       [Category Theory at SEP](http://plato.stanford.edu/entries/category-theory/)
 227 *       [[!wikipedia Category theory]]
 228 *       [[!wikipedia Category (mathematics) desc="Category"]]
 229 *       [[!wikipedia Morphism]]
 230 *       [[!wikipedia Functor]]
 231 *       [[!wikipedia Natural transformation]]
 232 *       [[!wikipedia Monad (category theory) desc="Monads in category theory"]]
 233 *       [Haskell/Category Theory](http://en.wikibooks.org/wiki/Haskell/Category_theory)
 234 *       [Category Theory & Functional Programming](http://blog.mestan.fr/2009/01/09/category-theory-functional-programming/)
 235 *       [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/)
 236 *       [Resources for learning practical category theory](http://mathoverflow.net/questions/903/resources-for-learning-practical-category-theory)
 237 *       [A Partial Ordering of some Category Theory applied to Haskell](http://blog.sigfpe.com/2010/03/partial-ordering-of-some-category.html)
 238
 239
 240 ## Continuations ##
 241
 242 *       [[!wikipedia Continuation]]
 243 *       [[!wikipedia Continuation-passing style]]
 244 *       [[!wikipedia Call-with-current-continuation]]
 245 *       [Intro to call/cc](http://community.schemewiki.org/?call-with-current-continuation) at SchemeWiki
 246 *       [[!wikipedia Delimited continuation]]
 247 *       [Delimited/composable continuations tutorial](composable-continuations-tutorial) at SchemeWiki
 248
 249 *       [Call With Current Continuation](http://www.c2.com/cgi/wiki?CallWithCurrentContinuation)
 250
 251 *       [Continuations Made Simple and Illustrated](http://www.ps.uni-saarland.de/~duchier/python/continuations.html)
 252
 253 *       [Continuation kata](http://programming-musings.org/2006/02/12/continuation-kata/)
 254
 255 *       [Understanding continuations](http://keithdevens.com/weblog/archive/2004/Jul/11/continuations) [Commentary](http://lambda-the-ultimate.org/node/86)
 256
 257 *       [[!wikipedia Continuation]]
 258
 259 *       [Haskell wiki on Continuations](http://www.haskell.org/haskellwiki/Continuation)
 260
 261 *       [Continuations In Scheme](http://tech.phillipwright.com/2010/05/23/continuations-in-scheme/)
 262
 263 *       [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.
 264
 265 *       [Continuations for Curmudgeons](http://www.intertwingly.net/blog/2005/04/13/Continuations-for-Curmudgeons) [Commentary](http://lambda-the-ultimate.org/node/643)
 266
 267 *       [composable-continuations-tutorial](http://community.schemewiki.org/?composable-continuations-tutorial)
 268
 269 *       [Post by Ken on Lambda the Ultimate explaining difference btw undelimited and delimited continuations](http://lambda-the-ultimate.org/node/1197#comment-12927)
 270
 271 *       [shift, reset and streams](http://chneukirchen.org/blog/archive/2005/04/shift-reset-and-streams.html)
 272
 273 *       [guile and delimited continuations](http://www.wingolog.org/archives/2010/02/26/guile-and-delimited-continuations)
 274
 275 *       [Delimited continuations in Scala](http://blog.richdougherty.com/2009/02/delimited-continuations-in-scala_24.html)
 276
 277 *       [Delimited Continuations Explained (in Scala)](http://dcsobral.blogspot.com/2009/07/delimited-continuations-explained-in.html)
 278
 279 *       [Partial Continuations](http://www.bluishcoder.co.nz/articles/scheme/partial-continuations.html)
 280
 281 *       [Online Bibliography of Scheme Research: Continuations and Continuation Passing Style](http://library.readscheme.org/page6.html)
 282
 283 *       Delimited Continuations in MzScheme:
 284 [Part 1](http://schemekeys.blogspot.com/2006/11/prompts-their-interaction-with-dynamic.html)
 285 [Part 2](http://schemekeys.blogspot.com/2006/12/delimited-continuations-in-mzscheme.html)
 286 [Part 3](http://schemekeys.blogspot.com/2007/01/going-further-with-primitives.html)
 287 [Part 4](http://schemekeys.blogspot.com/2007/01/odd-and-ends.html)
 288
 289 *       [Delimited continuations in natural language semantics](http://okmij.org/ftp/gengo/)
 290
 291
 292 ## Linear Logic ##
 293
 294 *       [[!wikipedia Linear logic]]
 295
 296