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)