X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?a=blobdiff_plain;f=offsite_reading.mdwn;h=018758017c7572a3a2ec0897cf7545fb43b2271e;hb=87abf2f5507409788f94c7f9ac0efdec212ec11d;hp=019edd2e46ef150c5cffaa7f31a8c5ada19caeee;hpb=dc94d6df9cb7f1a5b3a28770895f4f5f66716b1b;p=lambda.git diff --git a/offsite_reading.mdwn b/offsite_reading.mdwn index 019edd2e..01875801 100644 --- a/offsite_reading.mdwn +++ b/offsite_reading.mdwn @@ -1,4 +1,4 @@ -Many off these links are to Wikipedia. You can learn a lot from such articles, +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 @@ -12,26 +12,13 @@ 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 out. (Rinse and repeat.) +get more out of. (Rinse and repeat.) - -## General issues about variables and binding in programming languages ## - -* [[!wikipedia Variable (programming)]] -* [[!wikipedia Variable shadowing]] -* [[!wikipedia Scope (programming)]] -* [[!wikipedia Free variables and bound variables]] -* [[!wikipedia Name binding]] -* [[!wikipedia Name resolution]] -* [[!wikipedia Parameter (computer science)]] - -## Functions as values, etc ## +## Functions ## * [[!wikipedia Higher-order function]] * [[!wikipedia First-class function]] -* [[!wikipedia Closure (computer science)]] * [[!wikipedia Currying]] -* [[!wikipedia Recursion (computer science)]] ## Functional vs imperative programming ## @@ -39,63 +26,220 @@ get more out of out. (Rinse and repeat.) * [[!wikipedia Functional programming]] * [[!wikipedia Purely functional]] * [[!wikipedia Referential transparency (computer science)]] +* [[!wikipedia Side effect (computer science) desc="Side effects"]] * [[!wikipedia Imperative programming]] -## Scheme and OCaml ## +## General issues about variables and scope in programming languages ## -* [[!wikipedia Scheme (programming language)]] -* [[!wikipedia Objective Caml]] +* [[!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]]
-* [[!wikipedia Haskell Curry]] +* [[!wikipedia Lambda calculus]] + * [[!wikipedia Moses Schönfinkel]] +* [[!wikipedia Haskell Curry]] * [[!wikipedia Alonzo Church]]
+* [[!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]] -* [[!wikipedia SKI combinatory calculus]]
-* [[!wikipedia Church-Rosser theorem]] -* [[!wikipedia Normalization property]] -* [[!wikipedia Turing completeness]]
-* [[!wikipedia Church encoding]] -* [[!wikipedia Y combinator]]
-* [[!wikipedia Curry-Howard isomorphism]]
+* Jeroen Fokker, "The Systematic Construction of a One-combinator Basis for Lambda-Terms" Formal Aspects of Computing 4 (1992), pp. 776-780.
+
+
+* [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]]
+* [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]]
+
* [[!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]]
-* [[!wikipedia Type polymorphism]]
-* [[!wikipedia System F]]
+
+
+##[[Learning OCaml]]##
+
+
+## Monads ##
+* [[!wikipedia Monad (functional programming) desc="Monads in Functional Programming"]]
+* [Daniel Friedman. A Schemer's View of Monads](/schemersviewofmonads.ps): from
+* [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.
+
+* [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.
+
+* 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.
+
+* 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 Side effect (computer science)]]
-* [[!wikipedia Reference (computer science)]]
-* [[!wikipedia Pointer (computing)]]
+* [[!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)
+
+
+## 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
+
## Continuations ##
* [[!wikipedia Continuation]]
* [[!wikipedia Continuation-passing style]]
-* [[!wikipedia Call-with-current-continuation]]
+* [[!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)
* [[!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)
+* [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/)
-## Monads ##
-
-* [[!wikipedia Monad (functional programming)]]
## Linear Logic ##
* [[!wikipedia Linear logic]]
+