X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=offsite_reading.mdwn;h=0a660be07032010e6dfa02028e2076eead952aac;hp=076f77d21d4f7c26c6bd4705a93f31619e181252;hb=HEAD;hpb=781ff6c24a02a8e7fb75d1eef00313d8f22d3644 diff --git a/offsite_reading.mdwn b/offsite_reading.mdwn deleted file mode 100644 index 076f77d2..00000000 --- a/offsite_reading.mdwn +++ /dev/null @@ -1,223 +0,0 @@ -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]]## - -* [Try Scheme in your web browser](http://tryscheme.sourceforge.net/) - -## Untyped lambda calculus and combinatory logic ## - -* [[!wikipedia Lambda calculus]] -* Our [[Lambda evaluator]] -* [Chris Barker's Lambda Tutorial](http://homepages.nyu.edu/~cb125/Lambda) -* [Lambda Animator](http://thyer.name/lambda-animator/) -* [Penn lambda calculator](http://www.ling.upenn.edu/lambda/) Pedagogical software developed by Lucas Champollion, Josh Tauberer and Maribel Romero.

- - - -* [[!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]] -* Jeroen Fokker, "The Systematic Construction of a One-combinator Basis for Lambda-Terms" Formal Aspects of Computing 4 (1992), pp. 776-780. - -* [Chris Barker's Iota and Jot](http://semarch.linguistics.fas.nyu.edu/barker/Iota/)

- -* [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/) - - -## 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 -* 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

-* [[!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) -* [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. -* [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. - -## 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) - - -## 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)

-* [[!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/) - - -## Linear Logic ## - -* [[!wikipedia Linear logic]] - -