From 36e5cafb9453eb4c59283903a951b30f69915038 Mon Sep 17 00:00:00 2001
From: Chris
Date: Wed, 13 May 2015 09:20:47 -0400
Subject: [PATCH] edits
---
topics/_week15_continuation_applications.mdwn | 157 ++++++++++++++++++--------
1 file changed, 109 insertions(+), 48 deletions(-)
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: