notes_and_schedule.mdwn

   1 # Lecture Notes #
   2
   3 [[Week1]] (13 Sept) Applications; Basics of Lambda Calculus; Comparing Different Languages
   4
   5
   6
   7 # Still To Come #
   8
   9 This is very sketchy at this point, but it should give a sense of our intended scope.
  10
  11 ## More on the "pure" or untyped lambda calculus ##
  12
  13 1.      Eta reduction and "extensionality"
  14 1.      Different evaluation strategies (call by name, call by value, etc.)
  15 1.      Strongly normalizing vs weakly normalizing vs non-normalizing; Church-Rosser Theorem(s)
  16 1.      Lambda calculus compared to combinatorial logic<p>
  17 1.      Church-like encodings of numbers, defining addition and multiplication
  18 1.      Defining the predecessor function; alternate encodings for the numbers
  19 1.      Homogeneous sequences or "lists"; how they differ from pairs, triples, etc.
  20 1.      Representing lists as pairs
  21 1.      Representing lists as folds
  22 1.      Typical higher-order functions: map, filter, fold<p>
  23 1.      Recursion exploiting the fold-like representation of numbers and lists ([[!wikipedia Deforestation (computer science)]], [[!wikipedia Zipper (data structure)]])
  24 1.      General recursion using omega
  25 1.      The Y combinator(s); more on evaluation strategies<p>
  26 1.      Introducing the notion of a "continuation", which technique we'll now already have used a few times
  27
  28 ## Types ##
  29
  30 1.      Product or record types, e.g. pairs and triples
  31 2.      Sum or variant types; tagged or "disjoint" unions
  32 3.      Maybe/option types; representing "out-of-band" values
  33 4.      Zero/bottom types
  34 5.      Unit type
  35 6.      Inductive types (numbers, lists)
  36 7.      "Pattern-matching" or type unpacking<p>
  37 8.      The simply-typed lambda calculus<p>
  38 9.      Parametric polymorphism, System F, "type inference"<p>
  39 10.     [Phil/ling application] inner/outer domain semantics for positive free logic
  40         <!-- <http://philosophy.ucdavis.edu/antonelli/papers/pegasus-JPL.pdf> --><p>
  41 11.     [Phil/ling application] King vs Schiffer in King 2007, pp 103ff. [which paper?](http://rci.rutgers.edu/~jeffreck/pub.php)
  42 12. [Phil/ling application] King and Pryor on that clauses, predicates vs singular property-designators
  43 13.     Possible excursion: [Frege's "On Concept and Object"](http://www.persiangig.com/pages/download/?dl=http://sahmir.persiangig.com/document/Frege%27s%20Articles/On%20Concept%20And%20object%20%28Jstore%29.pdf)<p>
  44 14.     Curry-Howard isomorphism between simply-typed lambda and intuitionistic propositional logic<p>
  45 15.     The types of continuations; continuations as first-class values
  46 16.     [Phil/ling application] Partee on whether NPs should be uniformly interpreted as generalized quantifiers, or instead "lifted" when necessary. Lifting = a CPS transform.
  47 17.     [Phil/ling application] Expletives<p>
  48 18.     Some references:
  49        * [de Groote on the lambda-mu calculus in linguistics](http://www.loria.fr/%7Edegroote/papers/amsterdam01.pdf)
  50        * [on donkey anaphora and continuations](http://dx.doi.org/10.3765/sp.1.1)
  51        * [Wadler on symmetric sequent calculi](http://homepages.inf.ed.ac.uk/wadler/papers/dual-reloaded/dual-reloaded.pdf)
  52 19.     Dependent types
  53
  54 ## Side-effects and mutation ##
  55
  56 1.      What difference imperativity makes
  57 2.      Monads we've already seen, and the "monadic laws" [computer science version: Wadler](http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf)
  58 3.      Side-effects in a purely functional setting, via monads
  59 4.      The basis of monads in category theory
  60 5.      Other interesting monads: reader monad, continuation monad<p>
  61 6.      [Phil/ling application] Monsters and context-shifting, e.g. Gillies/von Fintel on "ifs" [not sure which paper]
  62 7.      Montague / Ben-avi and Winter,  [A modular approach to intensionality](http://citeseerx.ist.psu.edu/viewdocsummary?doi=10.1.1.73.6927)<p>
  63 8.      Passing by reference
  64 9.      [Phil/ling application] Fine and Pryor on "coordinated contents" (see, e.g., [Hyper-Evaluativity](http://www.jimpryor.net/research/papers/Hyper-Evaluativity.txt))
  65
  66 ## Continuations (continued) ##
  67
  68 1.      Using CPS to handle abortive computations (think: presupposition failure, expressives)
  69 2.      Using CPS to do other handy things, e.g., coroutines
  70 3.      Making evaluation order explicit with continuations (could also be done earlier, but I think will be helpful to do after we've encountered mutation)
  71 4.      Delimited (quantifier scope) vs undelimited (expressives, presupposition) continuations
  72 5.      [Phil/ling application] [Barker/Shan on donkey anaphora](http://dx.doi.org/10.3765/sp.1.1)
  73
  74 ## Preemptively parallel computing and linear logic ##
  75
  76 1.      Basics of parallel programming: semaphores/mutexes
  77 2.      Contrasting "preemptive" parallelism to "cooperative" parallelism (coroutines, above)
  78 3.      Linear logic
  79 4.      [Phil/ling application] Barker on free choice, imperatives
  80
  81