From: Chris Date: Wed, 13 May 2015 13:20:47 +0000 (-0400) Subject: edits X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=36e5cafb9453eb4c59283903a951b30f69915038 edits --- diff --git a/topics/_week15_continuation_applications.mdwn b/topics/_week15_continuation_applications.mdwn index fd25ccec..3bdbd2a1 100644 --- a/topics/_week15_continuation_applications.mdwn +++ b/topics/_week15_continuation_applications.mdwn @@ -11,17 +11,13 @@ In the past couple of weeks, we've introduced continuations, first as a functional programming technique, then in terms of list and tree zippers, then as a monad. In this lecture, we will generalize continuations slightly beyond a monad, and then begin to outline some -of the applications of monads. In brief, the generalization can be -summarized in terms of types: instead of using a Kleisli arrow mapping -a type α to a continuized type (α -> ρ) -> ρ, we'll allow the result -types to differ, i.e., we'll map α to (α -> β) -> γ. This will be -crucial for some natural language applications. +of the applications of the generalized continuations. Many (though not all) of the applications are discussed in detail in Barker and Shan 2014, *Continuations in Natural Language*, OUP. -In terms of list zippers, the continuation of a focused element in -the list is the front part of the list. +To review, in terms of list zippers, the continuation of a focused +element in the list is the front part of the list. list zipper for the list [a;b;c;d;e;f] with focus on d: @@ -33,28 +29,42 @@ the list is the front part of the list. In terms of tree zippers, the continuation is the entire context of the focused element--the entire rest of the tree. -[drawing of a broken tree] +[drawing of a tree zipper] -Last week we had trouble computing the doubling task when there was more -than one shifty operator after moving from a list perspective to a -tree perspective. That is, it remained unclear why "aScSe" was +We explored continuations first in a list setting, then in a tree +setting, using the doubling task as an example. - "aacaceecaacaceecee" + "abSd" ~~> "ababd" + "ab#deSfg" ~~> "abdedefg" -We'll burn through that conceptual fog today. The natural thing to -try would have been to defunctionalize the continuation-based solution -using a tree zipper. But that would not have been easy, since the -natural way to implement the doubling behavior of the shifty operator -would have been to simply copy the context provided by the zipper. -This would have produced two uncoordinated copies of the other shifty -operator, and we'd have been in the situation described in class of -having a reduction strategy that never reduced the number of shifty -operators below 2. (There are ways around this limitation of tree zippers, -but they are essentially equivalent to the technique given just below.) +The "S" functions like a shifty operator, and "#" functions like a reset. + +Although the list version of the doubling task was easy to understand +thoroughly, the tree version was significantly more challenging. In +particular, it remained unclear why + + "aScSe" ~~> "aacaceecaacaceecee" + +We'll burn through that conceptual fog today by learning more about +how to work with continuations. + +The natural thing to try would have been to defunctionalize the +continuation-based solution using a tree zipper. But that would not +have been easy, since the natural way to implement the doubling +behavior of the shifty operator would have been to simply copy the +context provided by the zipper. This would have produced two +uncoordinated copies of the other shifty operator, and we'd have been +in the situation described in class of having a reduction strategy +that never reduced the number of shifty operators below 2. The +limitation is that zippers by themselves don't provide a natural way +to establish a dependency between two distant elements of a data +structure. (There are ways around this limitation of tree zippers, +but they are essentially equivalent to the technique given just +below.) Instead, we'll re-interpreting what the continuation monad was doing -in more or less defunctionalized terms by using Quantifier Raising, a technique -from linguistics. +in more or less defunctionalized terms by using Quantifier Raising, a +technique from linguistics. But first, motivating quantifier scope as a linguistic application. @@ -101,13 +111,19 @@ The standard technique for handling scope-taking in linguistics is Quantifier Raising (QR). As you might suppose, the rule for Quantifier Raising closely resembles the reduction rule for shift: - Quantifier Raising: given a sentence [... [QDP] ...], build a new - sentence [QDP (\x.[... [x] ...])]. + Quantifier Raising: given a sentence of the form + + [... [QDP] ...], + + build a new sentence of the form + + [QDP (\x.[... [x] ...])]. Here, QDP is a scope-taking quantificational DP. Just to emphasize the similarity between QR and shift, we can use QR -to provide insight into the tree task that mystified us earlier. +to provide insight into the tree version of the doubling task that +mystified us earlier. Here's the starting point: