changes
authorChris Barker <barker@kappa.linguistics.fas.nyu.edu>
Tue, 14 Jun 2011 18:29:48 +0000 (14:29 -0400)
committerChris Barker <barker@kappa.linguistics.fas.nyu.edu>
Tue, 14 Jun 2011 18:29:48 +0000 (14:29 -0400)
cps.mdwn

index 9617dad..4c40a66 100644 (file)
--- a/cps.mdwn
+++ b/cps.mdwn
@@ -252,3 +252,34 @@ term.
 
 Excercise: what should the function ' be for the CBV xform?  Hint: 
 see the Meyer and Wand abstract linked above for the answer.
 
 Excercise: what should the function ' be for the CBV xform?  Hint: 
 see the Meyer and Wand abstract linked above for the answer.
+
+
+Other CPS transforms
+--------------------
+
+It is easy to think that CBN and CBV are the only two CPS transforms.
+(We've already seen a variant on call-by-value one of the excercises above.) 
+
+In fact, the number of distinct transforms is unbounded.  For
+instance, here is a variant of CBV that uses the same types as CBN:
+
+    <x> = x
+    <\xM> = \k.k(\x<M>)
+    <MN> = \k.<M>(\m.<N>(\n.m(\k.kn)k))
+
+Try reducing `<(\x.x) ((\y.y) (\z.z))> I` to convince yourself that
+this is a version of call-by-value.
+
+Once we have two evaluation strategies that rely on the same types, we
+can mix and match:
+
+    [x] = x
+    <x> = x
+    [\xM] = \k.k(\x<M>)
+    <\xM] = \k.k(\x[M])
+    [MN] = \k.<M>(\m.m<N>k)
+    <MN> = \k.[M](\m.[N](\n.m(\k.kn)k))
+
+This xform interleaves call-by-name and call-by-value in layers,
+according to the depth of embedding.
+