Interesting musings. I think the author dismissed graphs a bit too early. Making lists another first-class object (e.g. by always having nodes be lists) might be a bit less elegant but would work for his constraints.

The data structure he describes in the last article is actually well known in Prolog as difference lists (except that you can't do higher order logic programming with them). Converting between terms and lists is also well supported by Prolog. Granted, the syntax is not as nice as using S-expressions with special sugar for terms.