X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?a=blobdiff_plain;ds=sidebyside;f=offsite_reading.mdwn;h=0a660be07032010e6dfa02028e2076eead952aac;hb=d20a6e72fee5b4fc270b7756f99f9676297c38df;hp=4339092022925ab61b2870336a4e7bd19ede5c79;hpb=1848c1a9d840884193ba721c84902a146ab5eef8;p=lambda.git diff --git a/offsite_reading.mdwn b/offsite_reading.mdwn index 43390920..0a660be0 100644 --- a/offsite_reading.mdwn +++ b/offsite_reading.mdwn @@ -14,22 +14,10 @@ of an article you don't fully understand, so that you can discuss it with the re the group and hopefully get to a point where you can read it again and get more out of. (Rinse and repeat.) - -## General issues about variables and binding in programming languages ## - -* [[!wikipedia Variable (programming) desc="Variables"]] -* [[!wikipedia Variable shadowing]] -* [[!wikipedia Scope (programming) desc="Variable scope"]] -* [[!wikipedia Free variables and bound variables]] -* [[!wikipedia Name binding]] -* [[!wikipedia Name resolution]] -* [[!wikipedia Parameter (computer science) desc="Function parameters"]] - -## Functions as values, etc ## +## Functions ## * [[!wikipedia Higher-order function]] * [[!wikipedia First-class function]] -* [[!wikipedia Closure (computer science) desc="Closures"]] * [[!wikipedia Currying]] ## Functional vs imperative programming ## @@ -38,67 +26,56 @@ get more out of. (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]] +## 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]] -* [Chris Barker's Lambda Tutorial](http://homepages.nyu.edu/~cb125/Lambda) -* [Lambda Animator](http://thyer.name/lambda-animator/)
* [[!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]] - -* [Chris Barker's Iota and Jot](http://semarch.linguistics.fas.nyu.edu/barker/Iota/) -* [[!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
-* [[!wikipedia Church encoding]]
-
-## Learning Scheme ##
-
-* [[!wikipedia Scheme (programming language) desc="Wikipedia overview of Scheme"]]
-
-* 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:
-
- + [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."
+* Jeroen Fokker, "The Systematic Construction of a One-combinator Basis for Lambda-Terms" Formal Aspects of Computing 4 (1992), pp. 776-780.
+
- 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.
+* [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.
-* 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.
-
-* [An Introduction to Lambda Calculus and Scheme](http://www.jetcafe.org/~jim/lambda.html) is also aimed at programmers.
-
-* 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.
+## Evaluation Order ##
-* 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.
+* [[!wikipedia Evaluation strategy]]
+* [[!wikipedia Eager evaluation]]
+* [[!wikipedia Lazy evaluation]]
+* [[!wikipedia Strict programming language]]
-* The Scheme language is standardized; the various implementations of the
-language usually adhere to what's published in the current standard and add on
-different handy extensions. The first standard was published in 1975. A
-revision was published in 1978 called "The revised report on Scheme, a
-dialect of Lisp." Thereafter, revisions of the standard were titled "The
-Revised Revised Report..." and so on, or "The Revised^n Report..." for
-short. One widely implemented standard is [The
-Revised^5 Report on Scheme](http://www.schemers.org/Documents/Standards/R5RS/HTML/),
-or R5RS, published in 1998.
-A new standard [R6RS](http://www.r6rs.org/final/html/r6rs/r6rs.html) ([Libraries for R6RS](http://www.r6rs.org/final/html/r6rs-lib/r6rs-lib.html))
-was ratified in 2007, and this is implemented in Racket; but it also has many detractors and has not been fully
-accepted in the community. As a result, the Scheme language [may in the future split](http://scheme-reports.org/2009/position-statement.html)
-into a lean, minimal base, closer to
-R5RS Scheme, and a richer language like R6RS Scheme that standardizes many of the add-ons that programmers tend to build
-on top of the base.
+## Confluence, Normalization, Undecidability ##
-* [Scheme FAQ](http://community.schemewiki.org/?scheme-faq)
-* [Scheme Requests for Implementation](http://srfi.schemers.org/) (SRFI)
-* The [Schematics Scheme Cookbook](http://schemecookbook.org/) is a collaborative effort to produce documentation and recipes for using Scheme for common tasks.
+* [[!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 ##
@@ -112,63 +89,55 @@ on top of the base.
* [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/)
-## Evaluation Order ##
+## Folds ##
-* [[!wikipedia Evaluation strategy]]
-* [[!wikipedia Eager evaluation]]
-* [[!wikipedia Lazy evaluation]]
-* [[!wikipedia Strict programming language]]
+* [[!wikipedia Fold (higher-order function)]]
## 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 ##
-
-* [[!wikipedia Objective Caml desc="Wikipedia overview of OCaml"]]
-
-* [A Concise Introduction to Objective Caml](http://www.csc.villanova.edu/~dmatusze/resources/ocaml/ocaml.html)
-
-* 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.
-
-* Here's a [more detailed tutorial](http://www.ocaml-tutorial.org/) for OCaml.
-
-* The start of the [OCaml Reference Manual](http://caml.inria.fr/pub/docs/manual-ocaml/manual003.html) has another tutorial.
-
-* Jason Hickey has posted a [draft of a nice book introducing OCaml](http://www.cs.caltech.edu/courses/cs134/cs134b/book.pdf).
-
-* 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).
+
+* [[!wikipedia Tagged union]]
+* [[!wikipedia Algebraic data type]]
+* [[!wikipedia Recursive data type]]
+* [[!wikipedia Pattern matching]]
+* [[!wikipedia Unit type]]
+* [[!wikipedia Bottom type]]
-## Side-effects / mutation ##
+##[[Learning OCaml]]##
-* [[!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)
+* [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)
-* [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.
+* [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.
+
+* [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 ##
@@ -219,6 +193,16 @@ invited talk, *19'th Symposium on Principles of Programming Languages*, ACM Pres
* [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]]
@@ -232,7 +216,8 @@ invited talk, *19'th Symposium on Principles of Programming Languages*, ACM Pres
* [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 wiki on Continuations](http://www.haskell.org/haskellwiki/Continuation)
+* [Haskell wikibook on Continuation Passing Style](http://en.wikibooks.org/wiki/Haskell/Continuation_passing_style)
* [[!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
@@ -250,6 +235,13 @@ invited talk, *19'th Symposium on Principles of Programming Languages*, ACM Pres
* [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
+
+
+
## Linear Logic ##
* [[!wikipedia Linear logic]]