What aren't S-Expressions?

Question

I'm confused as to what an S-Expression isn't?

In scheme/racket, would anything with define NOT be an S-Expression:

   (define a 2)
 

   (define (my-print x)
     (println x))

Or maybe it is just things that dont evaluate to "values"? Like imports and comments?:

#lang racket/base
; and comments?

I'm not sure I really understand what things don't qualify as s-expressions?

Just trying to better understand S-Expressions.

Answer 1

I suspect that you probably mean 'expression' not 's-expression', since the latter term really has no existence in Scheme at all. However.

S-expressions

In the traditional sense, an s-expression is either:

• an atom;
• or a cons written as (<car> . <cdr>) where <car> and <cdr> are s-expressions.

Obviously this depends heavily on the definition of 'an atom'. Atoms are generally anything that is not a cons, and they include at least:

• the special null object ();
• symbols which are just names really: foo, foo-bar etc;
• probably numbers.

Note this definition makes no reference to values: an s-expression is just a definition of a family of structures.

A traditional Lisp would then be defined by writing a reader, which turns written representations of s-expressions into s-expressions. This reader would define what atoms were, and also almost always would include some convenient syntactic shorthands: (a . (b . (c . ()))) has a shorthand which is (a b c) for instance. So the reader gives you s-expressions and you then write an evaluator which will evaluate a small subset of possible s-expressions as programs (note that there are a vast number of s-expressions which are not legal programs). And finally a printer which turns s-expressions back into a written form.

So traditional Lisps were defined by assigning a semantics (via the evaluator) to some subset of s-expressions. A Lisp program is simply a sequence of s-expressions which get evaluated, and everything in a Lisp program is an s-expression.

Expressions

The definition of 'an expression' seems to vary based on the Lisp: in particular the Common Lisp specification defines 'expression' in a way which is different than the definition I'm about to give (note I've been a CL programmer for a very long time, I'm not objecting to the spec here).

I think the most useful way of defining the term is to borrow the usual definition used by mathematicians who, after all, have been doing this stuff for a long time: an expression is something which has a value, or an expression is a formula which can occur on the right hand side of an assignment. So if you can write 'x = ...' then '...' is an expression.

This carries across directly to programming languages: if you can write, in Scheme, (set! x ...) or (define x ...) then ... is an expression: if you can't, it's not. Note that this also applies to other languages: if you can write 'x = ...;' in C then ... is an expression. For example you can't write x = if (y == 1) 3; else 2; in C because if statements are, well, statements, not expressions: you have to write x = (y == 1)? 3 : 2;.

(Note that this notion of 'expression' does not deal with multiple values at all: see note at the end.)

This is the definition of expression I will use below.

Expressions in traditional Lisp

Traditional Lisps are expression languages: this means that any s-expression to which the language assigns a semantics (which, again, is a tiny subset of s-expressions) is an expression with a value, although that value might be undefined. In particular it means that there are no kinds of thing in the language which do not have values: there are no statements or other magic things: if the language assigns a semantics to an s-expression then it is an expression. Here's a weird example in Common Lisp: an s-expression like (defun name arglist ...) defines a function, and is therefore one of the s-expressions to which the language assigns a semantics. So you can, for instance do this

(let ((x (defun foo (y) y)))
  (cons x x))

And the value of this expression will be (foo . foo) in fact. Seeing defun forms other than at top-level in a CL program is a serious code smell, but it's legal CL, because everything is an expression in CL.

Note that the s-expressions to which the language assigns semantics and which correspond, therefore, to expressions are often (almost always) structured things, and just because the s-expression as a whole corresponds to an expression does not mean all its parts do. For instance

(cond
 (<test> <expression> ...)
 ...)

is a valid expression, but in general the s-expressions (<test> <expression> ...) are not: they are only valid as part of a cond form. However <test> and all the <expresssion>s will be valid expressions.

S-expressions in Scheme

However Scheme is not defined the way traditional Lisps were: there is no mention of s-expressions in the R7RS (PDF link) at all, for instance. The closest thing is probably <datum> (section 7.1.2) which defines what read can parse: I think it would be safe to say that a <datum> is an s-expression in Scheme. But Scheme is not defined in terms of <datum>s: it's defined in terms of the written syntax of the language directly.

Expressions in Scheme

Scheme is not quite as much an expression language as traditional Lisps. it defines things which are expressions, which it calls <expression>s, and these are defined in 7.1.3 of R7RS. As with Lisp, some of the parts of the things which are <expression>s are not themselves <expression>s: Scheme doesn't talk about them as being merely s-expressions, but you could think of them that way (whether that's useful I am not sure).

However there are a number of things in Scheme which are not expressions. For instance the things that make up a <program> (7.1.6) are not expressions, and this means that, for instance (define ...) is not an expression: you can't say:

(let ((x (define y 1))) x)

In Scheme. You can say

(let ((x (λ ()
           (define y 1)
           y)))
  x)

but that's because (λ () (define y 1) y) is a valid expression, although just as with Lisp that doesn't mean (define y 1) is: it's only allowed there because the syntax of λ allows it there.

So in Scheme there are expressions, which, just as in Lisp, may contain parts which are not themselves expressions, but there are also some things (which I think only occur at top-level in a program?) which are not expressions: they're definitions and things like that.

---

Note that above I've talked about an expression as something which, when evaluated, has a value: of course, what this really means is that it has zero or more values: (values) is an expression, as is (values 1 2). A more precise definition would deal with this problem.

Note that I have avoided the term 'form': I think it's safe to say that a 'form' is an s-expression in a traditional Lisp but I am not actually sure, and it is almost certainly not safe to say this in Scheme.

Answer 2

It's a bit philosophical, really. See Are Lisp forms and Lisp expressions same thing? for some prior discussion.

Or maybe it is just things that dont evaluate to "values"?

That's as reasonable a definition as any. Not everyone will agree, but nobody will disagree too loudly. Any expression in Scheme is an S-expression (symbolic expression), because it doesn't have any other kind of expression. Things that aren't expressions, because they can't be evaluated, are fuzzier, but it's defensible to say they're not expressions and thus not S-expressions.