An SEXP, or s-expression, is a data format for representing a ordered tree of typed values. (s stands for symbolic). The s stands for symbolic.

See Also

Converts SEXP to Tcl.


S-Expressions, draft-rivest-sexp-00.txt , by Ron Rivest
The original Internet Draft for s-expressions.
SEXP---(S-expressions), by Ron Rivest
The official home page for S-Expressions.


zarutian is half in love with the canonical form because of ease of parsing.

lars h is more sceptical. syntactically, plain old Tcl lists are simpler and more readable.

zarutian: But is it as easily parsed by programs that don't have an embedded Tcl interpreter?

lars h: well,

  1. every program should have an embedded Tcl interpreter. it's good for ya!
  2. in comparison to the full sexp syntax, Tcl lists are much easier to parse.
  3. even in comparison to the canonical form, which (I suspect) is highly geared towards being easy for C to parse, the Tcl list parser fares rather well. You need (if you're copying code from the Tcl sources) SetListFromAny, TclFindElement, and TclCopyAndCollapse, but that's about it.

Comparing Tcl lists and SEXPS may be instructive in explaining some fundamental differences between Tcl and Lisp. The following is a SEXP

(abc (de #6667#) "ghi jkl")

and this is the corresponding Tcl list

abc {de \x66\x67} "ghi jkl"

Some useful observations are:

  1. Both allow several equivalent ways of encoding the same information, e.g. the #6667# / \x66\x67 could alternatively have been written fg. SEXPS offers about twice as many forms as Tcl lists do, however. (This is typical. In comparison to the radical simplicity of Tcl, Lisp is a language suffering from severe featuritis.)
  2. In the SEXP, there are parentheses around the outer list, whereas there is no such thing in the Tcl list. This reflects the fact that a SEXP inherently has a type (the example is a list), whereas Tcl values are untyped (the example can be read as a list, but also as a string, and the same holds for the final list element; the type is in the beholder).
  3. ...

a Tcl-native encoding of a list of SEXPs as above could be as a list where even elements are types and the odd ones the corresponding values. Then the above example would be

list {"" abc list {"" de "" fg} "" {ghi jkl}}

if one writes "" for the empty type specifier. (The rfc-draft above also allows for every base string to carry a "display hint" prefix, which looks like "[image/gif]". That effectively means that one has to make room for a type tag for every non-list SEXP, even though it is normally empty.)

dcd is sceptical of Lars' scepticism. I'll offer these Tcl results:

% string range [split {a b c}] 0 1
% string  range [split {{a} {b} {c}}] 0 1

lars h: And what is that supposed to prove? That feeding lists into a command for extracting substrings may pick up a delimiter or two? Gee, that's "really" news ;<) And can you imagine, the exact same thing happens if you feed it SEXPs.

lv The surprise, to me is this:

% string range [split [list [list a] [list b] [list c]]] 0 1

which I would have expected to be the same as the previous example. Turns out that the list generated in my example doesn't have the list delimiters in it.

dcd (continued): That said, I chose tinytcl over SIOD for an embedded application because of it's untyped simplicity and the fact that it would require less CS background for any future maintainer. Aesthetically, though, Lisp and the SDSE SEXP's are far more appealing. in fact, in true Lisp form, the definition of the 'data structure' sexp is both a definition of the structure and the data it contains - reminiscent of the type-fields built into lisp-machine hardware architecture.

gjc: I love the reference to siod. Every program should have an embedded Scheme interpreter. but seriously, if you can find some old reference to Tcl/SIOD flame wars, perhaps from 15 years ago, there will be benchmarks that show SIOD taking considerably fewer page faults and operating system resources to be activated and print "hello world" than did Tcl implementations at the time, even though the general impression, the accepted wisdom, was that Tcl was vastly more compact and efficient than any Lisp implementation could possibly be. Perl also figured in these benchmarks, and an upshot was some non-trivial optimizations going from perl 4 to Perl 5.