> that wording somehow implies that they somehow retain the semantics of the data passed to them
Since they can do arbitrary transformations, retaining semantics is not in focus. Since the input may not have any semantics defined, the semantics is actually provided via the macro implementation.
> S-Expressions are just a serialisation format for the m-expression AST.
S-expressions know nothing about 'syntax'. Thus they can't be an 'abstract syntax tree'. (3 4 +) is a valid s-expression, but carries no information about any syntax (what is the + ? in an s-expression it's just a symbol) and is also an invalid Lisp expression.
An abstract syntax tree would be the result of parsing a program according to some grammar and it would represent the syntactic categories. The parsing stage would already eliminate invalid programs of that programming language.
https://upload.wikimedia.org/wikipedia/commons/thumb/c/c7/Ab...
In Lisp it is important that the s-expression is NOT a syntax tree. Otherwise it would be difficult to write macros which violate Lisp syntax.
He made it far enough into the wikipedia article to find a graphic that pseudo supports his claim, but not far enough to actually read the definition of an Abstract Syntax Tree (the thing we talk about) vs Concrete Syntax Tree (the thing he talks about).
> This distinguishes abstract syntax trees from concrete syntax trees, traditionally designated parse trees, which are typically built by a parser during the source code translation and compiling process.
Check out the abstract syntax tree on the right:
https://en.wikipedia.org/wiki/Abstract_syntax_tree
It has a node which is a BRANCH and which has three relations CONDITION, IF-BODY, ELSE-BODY.In an s-expression this is just
(if (> a b)
(setq a (- a b))
(setq b (- b a))
Thus there is no representation that IF is a branching expression, there is no representation that A and B are variables. There is no representation that > is a compare op. And so on.The s-expressions are just nested lists of tokens without any idea what the tokens refers to or what language construct it stands for. All we know is what the tokens are and a hierarchy. A is a symbol, but what kind we don't know: it could be a data object, a variable name, a function name, a goto tag, a name of a class, a name of a type, ...). In the abstract syntax tree the > is identified as a compare op, IF is identified as a branch, A is identified as a variable identifier, ...
The Lisp reader also does not create that information. It just creates a data structure, which could be anything, any kind of data.
This is why explicitly said Lambdas. Name one use of lambdas not covered by functions that is not delayed evaluation. If you want to be pedantic please be so consistently.
> S-expressions know nothing about 'syntax'. Thus they can't be an AST.
You seem to be confusing what the CL Hyperspec calls syntax, which is actually the semantics of evaluating a certain expression list, with the actual parse tree that can be generated from M-Expressions. And you seem to confuse Abstract Syntax Trees which can contain pretty much anything with Concrete Syntax Trees generated by parsing (it's explained on the very wiki page you linked). And even IF they were the same, M-Exps themselves are so flexible that they can express everything as function calls and arguments, and since the original Lisp only had a single symbol type your (3 4 +) argument itself is flawed.
You're way to focused on how CL does things, maybe it's your CL background that actually causes you to miss the bigger picture of lisp, something you accuse the people of that come from Java.
A lambda is a function. There is nothing special about them. There is nothing which makes them less or more functional than other functions.
((lambda (x) (* x 10))
30)
FYI: above is valid Scheme code. BiwaScheme Interpreter version 0.6.4
Copyright (C) 2007-2014 Yutaka HARA and the BiwaScheme team
((lambda (x) (* x 10))
30)
=> 300
Above is lambda expression applied to an argument. There is nothing 'delaying' about it.> You seem to be confusing what the CL Hyperspec calls syntax,
No, I'm looking at the Racket documentation.
https://docs.racket-lang.org/reference/syntax-model.html
The reader in Racket reads expressions into syntax objects. In a second pass it then creates a complete parse.
In an Interpreter based Lisp one reads the s-expression into an internal representation of lists, symbols, numbers. The interpreter then has the syntax encoded into its code and walks these lists keeping track of functions, variables, built-in operators, bindings, ... etc.
That's pretty much what a Lisp interpreter did since the dawn of time. Two decades before CL even existed.
Clojure even doesn't use an interpreter.
> Lambdas/AF are used to delay evaluation but keep the default semantics.
You and lispm seem to agree that lambdas can be used to delay evaluation, e.g. `(lambda () (+ 1 2))`. They are also used to abstract/parameterise, e.g. `(lambda (x) (* x x))`.
These two ideas coincide in most languages, since it's often not clear how we would evaluate a parameterised expression (e.g. how might we evaluate the `(* x x)` above, whilst keeping `x` as a free parameter?). Hence most languages don't evaluate inside a parameterised expression (lambdas) until called, and hence we can use them to delay evaluation.
In fact, we can evaluate "under a lambda", which is what happens during inlining, constant folding, or more generally partial-evaluation and supercompilation. This shows that parameterising and delaying evaluation are two distinct ideas, but they're usually represented with one language construct (lambda). We could imagine a separate language construct, like `(delay foo)`, which prevents any form ofevaluation (including inlining, supercompilation, etc.) from being applied to its argument, until it's 'forced' (maybe with a 'force' construct, or maybe by overloading function call syntax).
As for whether Lisp code is a syntax tree I would say:
- If we're allowing the possibility of the reader being altered, then our code doesn't have to be a tree, but I personally wouldn't call it "Lisp code" if it differed that much from s-expressions, regardless of whether a Lisp implementation can read it or not. In that case it's more like we're repurposing a Lisp implementation to act on some non-Lisp language. For example, if we used reader macros to consume regular expressions, that doesn't mean that regular expressions are Lisp.
- To me "Lisp code" is a syntax tree, but it is concrete not abstract (for the reasons lispm says, e.g. `+` is just an opaque symbol rather than an arithmetic operator; we can interpret it in any way we like, using macros).
- I wouldn't say that Lisp code is s-expressions, since there are alternative representations (e.g. I-expressions, sweet-expressions, etc.). Yet as long as they're equivalent to s-expressions (which, in particular, requires that they're trees and that we can impose our own semantics using macros!), then I'm happy calling them Lisp.
We delay evaluation because it may be expensive (potentially non-terminating), or because it may involve side-effects.
Delayed evaluation allows us to create new semantics, like lazy data structures.
The steps of a procedural program which are have not yet executed are delayed evaluation. Sometimes that is important, because those steps require some external event to have taken place, so that their own effect takes place after that event, or because that event provides a needed input. Mechanisms like closures and continuations give us new useful ways to structure this.
Indeed, we must delay (full) evaluation if we want a function to be recursive. This is also why we can't inline every function call (even if we're prepared to accept the inevitable code bloat).
> or because it may involve side-effects.
> The steps of a procedural program which are have not yet executed are delayed evaluation. Sometimes that is important, because those steps require some external event to have taken place, so that their own effect takes place after that event, or because that event provides a needed input.
I didn't explicitly talk about side-effects, but I was making an implicit assumption that evaluating under a lambda would never move an effect from runtime to compile/expansion time, and would preserve the partial-order of runtime effects (i.e. the absolute order may change, if there's a race condition and our partial-evaluation manages to speed up one path more than the other, but those which are causally-linked like triggering an event handler or waiting for input would preserve their order). To me, these requirements are just part of what it means for the evaluation to be correct, just like a call to `foo` should run the code for `foo` rather than some arbitrary other function, etc.
A partial-evaluator/supercompiler/inliner/constant-folder/loop-unroller can partially-evaluate code by treating parameters as opaque symbols (since we don't know what their value will be), and they can likewise treat language primitives which have side-effects as opaque values. For example we can treat `(lambda () (print "hello world"))` as being in normal form (and hence we do no further evaluation), whilst still treating `(lambda () (print (concat "hello " "world")))` as not being in normal form, since we can go ahead and run the `concat` call.
> Delayed evaluation allows us to create new semantics, like lazy data structures.
> Mechanisms like closures and continuations give us new useful ways to structure this.
I agree, I was just pointing out we can (a) implement such things without `lambda` (e.g. using a separate `delay` construct) and that (b) we can implement `lambda` in a way which doesn't allow forms (e.g. by allowing evaluation under a lambda, by limiting what we count as a normal form).
I'm not saying it's practical or desirable to do so, just that it's important to know which properties are inherent to a feature (like `lambda`) and which are under our control to choose.
Right, and this is not different from any other function:
(define (foo) (+ 1 2))
(define bar (list foo (lambda () (+ 1 2)))) ; putting two functions in a list for later evaluation
((first bar))
((second bar))
> They are also used to abstract/parameterise, e.g. `(lambda (x) (* x x))`.yep.
Macros are more than simple code transformers, that wording somehow implies that they somehow retain the semantics of the data passed to them, which mighy be the case but is not required at all.
S-Expressions are just a serialisation format for the m-expression AST.