I’ve been wanting to try to implement a language that involved some sort of continuations, so I just sat down and tried the one from the paper. Just to make it extra-hard, I implemented it using small-step, which also means I can print the entire program out as it transforms itself to its result. I’m pretty proud of the result--I’ve never really used lex and yacc for a real project yet. And I managed to verify his examples, something I was often even unable to do on my whiteboard because I kept getting confused (this shift stuff really turns code over on its head).
I’m a little tired of typing, so I’ll just include my sample program’s output below. (There's also a bit of linguistic quantification output!) There’s two layers of parsing, which means that you can intermix normal text and expressions and it interprets the expressions inline. So all of the text below is from the sample program’s code, not in the interpreter.
The input is text intermixed with expressions, like this:
# 1 + 2
0. (1 + 2)
1. 3
>> Result: 3
I haven’t done pretty-printing parenthesis quite yet:
# 1 + 2 * 3
0. (1 + (2 * 3))
1. (1 + 6)
2. 7
>> Result: 7
But good stuff like lambdas are:
# (\x. (\y. x + y)) 1 2
0. (((\x y. (x + y)) 1) 2)
1. ((\y. (1 + y)) 2)
2. (1 + 2)
3. 3
>> Result: 3
And, more significantly, “shift” and “reset” are implemented.
This expression should result in 21 (see (40), page 8):
# 10 * (shift f: 1 + f 2)
0. [(10 * (shift f: (1 + (f 2))))]
1. (1 + ((\v. (10 * v)) 2))
2. (1 + (10 * 2))
3. (1 + 20)
4. 21
>> Result: 21
This one is 70:
# 10 * [3 + (shift f: f 0 + f 1)]
0. [(10 * [(3 + (shift f: ((f 0) + (f 1))))])]
1. [(10 * (((\v. (3 + v)) 0) + ((\v. (3 + v)) 1)))]
2. (10 * (((\v. (3 + v)) 0) + ((\v. (3 + v)) 1)))
3. (10 * ((3 + 0) + ((\v. (3 + v)) 1)))
4. (10 * (3 + ((\v. (3 + v)) 1)))
5. (10 * (3 + (3 + 1)))
6. (10 * (3 + 4))
7. (10 * 7)
8. 70
>> Result: 70
I do allow some simple linguistic expressions.
This is “Alice liked every course”, where “every” ought to be
(shift s: \forall x COURSE(x) => s(x)), but I don’t have the
logic parsing done yet, so you’ll have to imagine that “FOR_ALL_COURSES_X”
means that forall statement.
Note that this approach doesn’t need to explicitly invert word order
(logical form) to accomplish the raising.
# ((\x. (\f. f x)) ALICE) (((\f. (\x. f x)) LIKED) (shift s: FOR_ALL_COURSES_X (s X)))
0. [(((\x f. (f x)) ALICE) (((\f x. (f x)) LIKED) (shift s: (FOR_ALL_COURSES_X (s X)))))]
1. [((\f. (f ALICE)) (((\f x. (f x)) LIKED) (shift s: (FOR_ALL_COURSES_X (s X)))))]
2. [((\f. (f ALICE)) ((\x. (LIKED x)) (shift s: (FOR_ALL_COURSES_X (s X)))))]
3. (FOR_ALL_COURSES_X ((\v. ((\f. (f ALICE)) ((\x. (LIKED x)) v))) X))
4. (FOR_ALL_COURSES_X ((\f. (f ALICE)) ((\x. (LIKED x)) X)))
5. (FOR_ALL_COURSES_X ((\f. (f ALICE)) (LIKED X)))
6. (FOR_ALL_COURSES_X ((\f. (f ALICE)) LIKED(X)))
7. (FOR_ALL_COURSES_X (LIKED(X) ALICE))
8. (FOR_ALL_COURSES_X LIKED(X,ALICE))
9. FOR_ALL_COURSES_X(LIKED(X,ALICE))
>> Result: FOR_ALL_COURSES_X(LIKED(X,ALICE))
LIKED takes X as its first parameter because it binds tighter to
its object: [S Alice [VP liked x]].
And I’m not sure yet why [[ALICE]] needs to be thunked like that,
except to make the process work.
Another fun task is to write a parser for more “natural” text.
I’m thinking of syntax like: Alice \ (liked / every course),
where the slashes represent either forward or backward combination,
and “every” is a keyword with the above meaning. That parser would
probably ought to just generate input into the above parser, though.