-# fun f z -> z;; -- : 'a -> 'b -> 'b =- -Finally, we're getting consistent principle types, so we can stop. -These types should remind you of the simply-typed lambda calculus -types for Church numerals (`(o -> o) -> o -> o`) with one extra bit -thrown in (in this case, and int). + # fun f z -> z;; + - : 'a -> 'b -> 'b =-# fun f z -> f 1 z;; -- : (int -> 'a -> 'b) -> 'a -> 'b = -# fun f z -> f 2 (f 1 z);; -- : (int -> 'a -> 'a) -> 'a -> 'a = -# fun f z -> f 3 (f 2 (f 1 z)) -- : (int -> 'a -> 'a) -> 'a -> 'a = -

-# let cons h t = h :: t;; (* Ocaml is stupid about :: *) -# l'_bind (fun f z -> f 1 (f 2 z)) - (fun i -> fun f z -> f i (f (i+1) z)) cons [];; -- : int list = [1; 2; 2; 3] -+ # let cons h t = h :: t;; (* OCaml is stupid about :: *) + # l'_bind (fun f z -> f 1 (f 2 z)) + (fun i -> fun f z -> f i (f (i+1) z)) cons [];; + - : int list = [1; 2; 2; 3] Ta da! -Just for mnemonic purposes (sneaking in an instance of eta reduction -to the definition of unit), we can summarize the result as follows: - - type ('a, 'b) list' = ('a -> 'b -> 'b) -> 'b -> 'b - l'_unit x = fun f -> f x - l'_bind u f = fun k -> u (fun x -> f x k) - To bad this digression, though it ties together various elements of the course, has *no relevance whatsoever* to the topic of -continuations. +continuations... Montague's PTQ treatment of DPs as generalized quantifiers ---------------------------------------------------------- @@ -265,45 +299,44 @@ generalized quantifier `fun pred -> pred j` of type `(e -> t) -> t`. Let's write a general function that will map individuals into their corresponding generalized quantifier: - gqize (x:e) = fun (p:e->t) -> p x + gqize (a : e) = fun (p : e -> t) -> p a This function wraps up an individual in a fancy box. That is to say, we are in the presence of a monad. The type constructor, the unit and -the bind follow naturally. We've done this enough times that I won't +the bind follow naturally. We've done this enough times that we won't belabor the construction of the bind function, the derivation is similar to the List monad just given: - type 'a continuation = ('a -> 'b) -> 'b - c_unit (x:'a) = fun (p:'a -> 'b) -> p x - c_bind (u:('a -> 'b) -> 'b) (f: 'a -> ('c -> 'd) -> 'd): ('c -> 'd) -> 'd = - fun (k:'a -> 'b) -> u (fun (x:'a) -> f x k) + type 'a continuation = ('a -> 'b) -> 'b + c_unit (a : 'a) = fun (p : 'a -> 'b) -> p a + c_bind (u : ('a -> 'b) -> 'b) (f : 'a -> ('c -> 'd) -> 'd) : ('c -> 'd) -> 'd = + fun (k : 'a -> 'b) -> u (fun (a : 'a) -> f a k) How similar is it to the List monad? Let's examine the type constructor and the terms from the list monad derived above: type ('a, 'b) list' = ('a -> 'b -> 'b) -> 'b -> 'b - l'_unit x = fun f -> f x - l'_bind u f = fun k -> u (fun x -> f x k) + l'_unit a = fun f -> f a + l'_bind u f = fun k -> u (fun a -> f a k) -(I performed a sneaky but valid eta reduction in the unit term.) +(We performed a sneaky but valid eta reduction in the unit term.) The unit and the bind for the Montague continuation monad and the homemade List monad are the same terms! In other words, the behavior of the List monad and the behavior of the continuations monad are parallel in a deep sense. To emphasize the parallel, we can -instantiate the type of the list' monad using the Ocaml list type: +instantiate the type of the list' monad using the OCaml list type: type 'a c_list = ('a -> 'a list) -> 'a list - let c_list_unit x = fun f -> f x;; - let c_list_bind u f = fun k -> u (fun x -> f x k);; -Have we really discovered that lists are secretly continuations? -Or have we merely found a way of simulating lists using list +Have we really discovered that lists are secretly continuations? Or +have we merely found a way of simulating lists using list continuations? Both perspectives are valid, and we can use our intuitions about the list monad to understand continuations, and vice -versa. The connections will be expecially relevant when we consider -indefinites and Hamblin semantics on the linguistic side, and -non-determinism on the list monad side. +versa (not to mention our intuitions about primitive recursion in +Church numerals too). The connections will be expecially relevant +when we consider indefinites and Hamblin semantics on the linguistic +side, and non-determinism on the list monad side. Refunctionalizing zippers -------------------------