lambdas are anonymous functions. Macros are code transformers. Lisp code is not an AST.
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.
> 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
In an s-expression this is just
(if (> a b)
(setq a (- a b))
(setq b (- b a))
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)
BiwaScheme Interpreter version 0.6.4
Copyright (C) 2007-2014 Yutaka HARA and the BiwaScheme team
((lambda (x) (* x 10))
30)
=> 300
> 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.
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))
yep.
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.
Lisp existed already before Clojure and has a rich history, much of which is not in Clojure.
ClojureScript is interpreter, unless you run Closure compiler in compilation phase. Interpretation is done by default in repl. There is also Joker [0].
> no linked lists as base data structure
Not true. Linked lists are base data structure on the same level as vectors and hash maps. Unlike Scheme where hash maps are sometimes implemented as assoc-ed lists.
> no Lisp in Lisp
Check for CinC and derivatives [1] or Ferret [2].
> no Lisp runtime
What you define by "runtime"?
> no images
By this requirement, 90% Lisps out there would not be Lisp ;) Even some Common Lisp implementations (ABCL) doesn't have it. Or if you want another extreme, V8/nodejs can generate image/snapshot or you can dump JVM image via Criu [3].
> not the typical debugging tools like break loops
IntelliJ has it, CIDER has it, there is clj-debugger... It is not part of default implementation, just like Scheme doesn't have it.
I thought ClojureScript compiles to JavaScript?
> What you define by "runtime"?
For example the stuff the JVM provides: memory management, data layout, interrupt handling, threads, loading code, talking to the environment, ...
> By this requirement, 90% Lisps out there would not be Lisp
I'd think it's more like 70% use images... just a guess. The exceptions usually are Lisps using runtimes which can dump/load images (like probably every Lisp on the JVM) or which by choice don't do (like some Lisp to C compilers, ...).
> Even some Common Lisp implementations (ABCL) doesn't have it.
That's the same limitation of the JVM. There are a few more implementations which don't have it. But generally there is a rich choice of full language implementations with and without images.
According to [0], these days it is hard to distinguish between compilers/interpreters. However, it translates code to javascript and execute it immediately, just like python does (converting code to own bytecode, before execution). No translation to machine language.
> For example the stuff the JVM provides...
I still fail to see what (Common) Lisp runtime gives over JVM, except direct translation to machine language (Hotspot does that in runtime) and maybe restarts - there are few clojure libraries which implements this, but thing would be much better if is baked in language/jvm.
> I'd think it's more like 70% use images
If you count into that Scheme implementations, that number would be significantly different ;)
A Lisp interpreter runs directly the s-expressions. This is independent from the idea of evaluation. Evaluation could be implemented by an interpreter or by a compiler.
For example using an interpreter:
CL-USER 32 > (defun fak (n)
(if (zerop n)
1
(* n (fak (1- n)))))
FAK
CL-USER 33 > (trace (fak :break (eql (first *traced-arglist*) 0)))
(FAK)
CL-USER 34 > (fak 5)
0 FAK > ...
>> N : 5
1 FAK > ...
>> N : 4
2 FAK > ...
>> N : 3
3 FAK > ...
>> N : 2
4 FAK > ...
>> N : 1
5 FAK > ...
>> N : 0
Break on entry to FAK with *TRACED-ARGLIST* (0).
1 (continue) Return from break.
2 Continue with trace removed.
3 Continue traced with break removed.
4 Continue and break when this function returns.
5 (abort) Return to top loop level 0.
Type :b for backtrace or :c <option number> to proceed.
Type :bug-form "<subject>" for a bug report template or :? for other options.
CL-USER 35 : 1 > :bq
FAK <- FAK <- FAK <- FAK <- FAK <- EVAL <- CAPI::CAPI-TOP-LEVEL-FUNCTION <- CAPI::INTERACTIVE-PANE-TOP-LOOP
<- MP::PROCESS-SG-FUNCTION
CL-USER 36 : 1 > :n
Interpreted call to FAK
CL-USER 37 : 1 > :lambda
(LAMBDA (N) (DECLARE (SYSTEM::SOURCE-LEVEL #<EQ Hash Table{0} 41B01C37FB>))
(DECLARE (LAMBDA-NAME FAK))
(IF (ZEROP N) 1 (* N (FAK #))))
If we want, we could inspect, alter it with the usual Lisp functions and continue running.
CL-USER 39 : 1 > (fifth *)
(IF (ZEROP N) 1 (* N (FAK (1- N))))
CL-USER 40 : 1 > (setf (third *) 2)
2
CL-USER 41 : 1 > **
(IF (ZEROP N) 2 (* N (FAK (1- N))))
CL-USER 42 : 1 > :c 1
5 FAK < ...
<< VALUE-0 : 2
4 FAK < ...
<< VALUE-0 : 2
3 FAK < ...
<< VALUE-0 : 4
2 FAK < ...
<< VALUE-0 : 12
1 FAK < ...
<< VALUE-0 : 48
0 FAK < ...
<< VALUE-0 : 240
240
More efficient data representation, more efficient execution, saving and loading of images, tailored GCs, mixing compiled and interpreted (see above) Lisp code, deeper runtime inspection, resumeable exceptions, efficient stack traces, efficient function calls, fast startup times, etc etc.
Something like Lisp, which may have a bunch of very dynamic parts, is hard to implement efficiently on the JVM. Clojure is designed to map better to the JVM.