From: Chris Barker <barker@kappa.linguistics.fas.nyu.edu>
Date: Tue, 14 Jun 2011 18:29:48 +0000 (-0400)
Subject: changes
X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=27ce0d45d4ab28840605ec2130f6ba4ecd9d6213

changes
---

diff --git a/cps.mdwn b/cps.mdwn
index 9617dad0..4c40a667 100644
--- 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.
+
+
+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.
+