git @ Cat's Eye Technologies
master

# Case Study: Parsing and Evaluating S-Expressions in Tamsin

``````-> Tests for functionality "Intepret Tamsin program"
``````

We now have enough tools at our disposal to parse and evaluate simple S-expressions (from Lisp or Scheme).

Note that we no longer have `\$.tamsin`, so these examples don't work. They're left here to demonstrate the development process. For now, see `eg/sexpr-eval.tamsin`.

We can write such a parser with `{}`, but the result is a bit messy.

``````| main = sexp using \$.tamsin.
| sexp = symbol | list.
| list = "(" &
|        set L = nil &
|        {sexp → S & set L = pair(S, L)} &
|        ")" &
|        return L.
| symbol = "cons" | "head" | "tail" | "nil" | "a" | "b" | "c".
+ (cons (a (cons b nil)))
= pair(pair(pair(nil, pair(b, pair(cons, nil))), pair(a, nil)), pair(cons, nil))
``````

So let's write it in the less intuitive, recursive way:

``````| main = sexp using \$.tamsin.
|
| sexp = symbol | list.
| list = "(" & listtail(nil).
| listtail(L) = sexp → S & listtail(pair(S, L))
|             | ")" & return L.
| symbol = "cons" | "head" | "tail" | "nil" | "a" | "b" | "c".
+ (a b)
= pair(b, pair(a, nil))
``````

Nice. But it returns a term that's backwards. So we need to write a reverser. In Erlang, this would be

``````reverse([H|T], A) -> reverse(T, [H|A]).
reverse([], A) -> A.
``````

In Tamsin, it's:

``````| main = sexp → S using \$.tamsin & reverse(S, nil) → SR & return SR.
|
| sexp = symbol | list.
| list = "(" & listtail(nil).
| listtail(L) = sexp → S & listtail(pair(S, L))
|             | ")" & return L.
| symbol = "cons" | "head" | "tail" | "nil" | "a" | "b" | "c".
|
| reverse(pair(H, T), A) =
|   reverse(T, pair(H, A)) → TR &
|   return TR.
| reverse(nil, A) =
|   return A.
+ (a b)
= pair(a, pair(b, nil))
``````

But it's not deep. It only reverses the top-level list.

``````| main = sexp → S using \$.tamsin & reverse(S, nil) → SR & return SR.
|
| sexp = symbol | list.
| list = "(" & listtail(nil).
| listtail(L) = sexp → S & listtail(pair(S, L))
|             | ")" & return L.
| symbol = "cons" | "head" | "tail" | "nil" | "a" | "b" | "c".
|
| reverse(pair(H, T), A) =
|   reverse(T, pair(H, A)) → TR &
|   return TR.
| reverse(nil, A) =
|   return A.
+ (a (c b) b)
= pair(a, pair(pair(b, pair(c, nil)), pair(b, nil)))
``````

So here's a deep reverser.

``````| main = sexp → S using \$.tamsin & reverse(S, nil) → SR & return SR.
|
| sexp = symbol | list.
| list = "(" & listtail(nil).
| listtail(L) = sexp → S & listtail(pair(S, L))
|             | ")" & return L.
| symbol = "cons" | "head" | "tail" | "nil" | "a" | "b" | "c".
|
| reverse(pair(H, T), A) =
|   reverse(H, nil) → HR &
|   reverse(T, pair(HR, A)) → TR &
|   return TR.
| reverse(nil, A) =
|   return A.
| reverse(X, A) =
|   return X.
+ (a (c b) b)
= pair(a, pair(pair(c, pair(b, nil)), pair(b, nil)))
``````

Finally, a little sexpr evaluator.

``````| main = sexp → S using \$.tamsin & reverse(S, nil) → SR & eval(SR).
|
| sexp = symbol | list.
| list = "(" & listtail(nil).
| listtail(L) = sexp → S & listtail(pair(S, L))
|             | ")" & return L.
| symbol = "cons" | "head" | "tail" | "nil" | "a" | "b" | "c".
|
| head(pair(A, B)) = return A.
| tail(pair(A, B)) = return B.
| cons(A, B) = return pair(A, B).
|
| eval(pair(head, pair(X, nil))) = eval(X) → R & head(R) → P & return P.
| eval(pair(tail, pair(X, nil))) = eval(X) → R & tail(R) → P & return P.
| eval(pair(cons, pair(A, pair(B, nil)))) =
|    eval(A) → AE & eval(B) → BE & return pair(AE, BE).
| eval(X) = return X.
|
| reverse(pair(H, T), A) =
|   reverse(H, nil) → HR &
|   reverse(T, pair(HR, A)) → TR &
|   return TR.
| reverse(nil, A) =
|   return A.
| reverse(X, A) =
|   return X.
+ (cons a b)
= pair(a, b)

| main = sexp → S using \$.tamsin & reverse(S, nil) → SR & eval(SR).
|
| sexp = symbol | list.
| list = "(" & listtail(nil).
| listtail(L) = sexp → S & listtail(pair(S, L))
|             | ")" & return L.
| symbol = "cons" | "head" | "tail" | "nil" | "a" | "b" | "c".
|
| head(pair(A, B)) = return A.
| tail(pair(A, B)) = return B.
| cons(A, B) = return pair(A, B).
|
| eval(pair(head, pair(X, nil))) = eval(X) → R & head(R) → P & return P.
| eval(pair(tail, pair(X, nil))) = eval(X) → R & tail(R) → P & return P.
| eval(pair(cons, pair(A, pair(B, nil)))) =
|    eval(A) → AE & eval(B) → BE & return pair(AE, BE).
| eval(X) = return X.
|
| reverse(pair(H, T), A) =
|   reverse(H, nil) → HR &
|   reverse(T, pair(HR, A)) → TR &
|   return TR.
| reverse(nil, A) =
|   return A.
| reverse(X, A) =
|   return X.
+ (head (cons b a))
= b

| main = sexp → S using \$.tamsin & reverse(S, nil) → SR & eval(SR).
|
| sexp = symbol | list.
| list = "(" & listtail(nil).
| listtail(L) = sexp → S & listtail(pair(S, L))
|             | ")" & return L.
| symbol = "cons" | "head" | "tail" | "nil" | "a" | "b" | "c".
|
| head(pair(A, B)) = return A.
| tail(pair(A, B)) = return B.
| cons(A, B) = return pair(A, B).
|
| eval(pair(head, pair(X, nil))) = eval(X) → R & head(R) → P & return P.
| eval(pair(tail, pair(X, nil))) = eval(X) → R & tail(R) → P & return P.
| eval(pair(cons, pair(A, pair(B, nil)))) =
|    eval(A) → AE & eval(B) → BE & return pair(AE, BE).
| eval(X) = return X.
|
| reverse(pair(H, T), A) =
|   reverse(H, nil) → HR &
|   reverse(T, pair(HR, A)) → TR &
|   return TR.
| reverse(nil, A) =
|   return A.
| reverse(X, A) =
|   return X.
+ (tail (tail (cons b (cons b a))))
= a
``````

In this one, we make the evaluator print out some of the steps it takes.

``````| main = sexp → S using \$.tamsin & reverse(S, nil) → SR & eval(SR).
|
| sexp = symbol | list.
| list = "(" & listtail(nil).
| listtail(L) = sexp → S & listtail(pair(S, L))
|             | ")" & return L.
| symbol = "cons" | "head" | "tail" | "nil" | "a" | "b" | "c".
|
| head(pair(A, B)) = return A.
| tail(pair(A, B)) = return B.
| cons(A, B) = return pair(A, B).
|
| eval(pair(head, pair(X, nil))) = eval(X) → R & head(R) → P & return P.
| eval(pair(tail, pair(X, nil))) = eval(X) → R & tail(R) → P & return P.
| eval(pair(cons, pair(A, pair(B, nil)))) =
|    eval(A) → AE & eval(B) → BE &
|    \$.print(y(AE, BE)) & cons(AE, BE) → C & return C.
| eval(X) = return X.
|
| reverse(pair(H, T), A) =
|   reverse(H, nil) → HR &
|   reverse(T, pair(HR, A)) → TR &
|   return TR.
| reverse(nil, A) =
|   return A.
| reverse(X, A) =
|   return X.
+ (cons (tail (cons b a)) (head (cons b a)))
= y(b, a)
= y(b, a)
= y(a, b)
= pair(a, b)
``````