03:52 pm, 10 Dec 03

### linguistic side effects programming language

I spent a bunch more time last night reading the cognition book, and then I returned to this linguistic side effects paper.

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

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.

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.# 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.

zenspiderevanSee, for example, steps 0 and 1 in my second example. We have an add of 1 and an expression. One definition of add is to say that add of any two expressions is defined as the large step of ((reduce left side to a value) + (reduce right side to a value)).

Instead, what I do is the small step of evaluating the right expression, and split the definition of addition in two: add of two values is the sum of the values (step 1-2), and add of two nonvalues means step the left and right sides by one (step 0-1).

For this project it means that I can watch the AST slowly boil down to its result.

Small-step (as opposed to large-step) is, uh, hard for me to describe in more general terms, now that I think about it, so if you're already familiar with the term, I won't butcher it by trying. But if you aren't, let me know and I'll do my best to explain it.

bostonsteamer## OT

It's mostly over my head, but I thought you'd enjoy this blog entry from a co-worker.evan## Re: OT

I don't really want to respond to it directly, but I'll note here the interesting leap at "Object oriented programming works so well because it works very similarly to how our brains work."I think many programmers (myself included) get so involved in their code they forget how to think outside of it. I like OO programming a lot, but I'm also aware that it's supposed to be quite confusing to new programmers because it's not intuitive (or maybe in the sense that it reuses concepts we're familiar with in a way unrelated to the way we're used to thinking about them).

padparadsha