4 ms·

I'm not persuaded this is a better idea than, say, Racket's ability to configure the reader layer [1]. This lets you create, for example, an embedded Datalog im

I'm not persuaded this is a better idea than, say, Racket's ability to configure the reader layer [1]. This lets you create, for example, an embedded Datalog implementation [2] that uses Datalog syntax but interops with other Racket modules. (The underlying data model doesn't change.) This gives you the ability to metaprogram without being confined to S-expressions, but it does so in a high-level way. It is very neat to see this kind of syntax bootstrapping. I think there's some value (in a researchy-sense) to being able to do that. But I'm not sure if there's something fundamentally "better" about this approach over Racket's approach. Postscript: Lisp (and Scheme and Racket) macros typically operate on AST (typically because Lisp has reader macros and Racket has a full-bodied reader extension) but Rhombus [3] operates on a "shrubbery", which is like an AST but it defers some parsing decisions until later. This gives macros a little flexibility in extending the syntax of the language. Another interesting point in the design space! [1]: https://docs.racket-lang.org/guide/hash-reader.html https://docs.racket-lang.org/guide/hash-reader.html [2]: https://docs.racket-lang.org/datalog/datalog.html https://docs.racket-lang.org/datalog/datalog.html [3]: Flatt, Allred & Angle et al. (2023-10-16) Rhombus: A New Spin on Macros without All the Parentheses, Proceedings of the ACM on Programming Languages. https://doi.org/10.1145/3580417 https://doi.org/10.1145/3580417

aidenn0 2y ago
Heck, I'm not convinced that this is a better idea than Common Lisp readtable[1], and I think Racket's #lang is more ergonomic than the CL readtable. 1: Which is powerful enough to implement a C compiler in: https://github.com/vsedach/Vacietis https://github.com/vsedach/Vacietis
lispm 2y ago
> Lisp ... macros typically operate on AST In Lisp they don't. See Emacs Lisp, Common Lisp, ISLISP. A Lisp macro gets only passed some data and returns some data. There is nothing like an AST. If we define a macro foo-macro and we call it: (foo-macro ...) then ... can be any data. Example: (defmacro rev (&rest items) (reverse items)) Above macro REV gets data passed and reverses it. The &rest list of ITEMS gets reversed. ITEMS is the list of source arguments in the macro call. We can then write: (rev 1 2 3 4 +) (rev (rev 10 n -) (+ a 20 b) (rev 30 a *) list) Example: CL-USER 7 > (let ((n 4) (a 3) (b 2)) (rev (rev 10 n -) (+ a 20 b) (rev 30 a *) list)) (90 25 -6) There is no syntax tree. All the macro does, is to reverse the list of its source arguments. If I let the macro describe the thing it gets passed, then we get this: CL-USER 8 > (defmacro rev (&rest items) (DESCRIBE items) (reverse items)) REV CL-USER 9 > (rev 1 2 3 4 +) (1 2 3 4 +) is a LIST 0 1 1 2 2 3 3 4 4 + 10 As a side effect, we can see that the macro gets a simple list passed. A list of numbers and a symbol ("symbol" is also a data type). Not text. Not an AST. Also data which is possibly not read, but computed by other code. We can compute the arguments of the macro REV and pass the thing to EVAL. Works the same as above. CL-USER 10 > (eval (append '(rev) (loop for i from 1 to 4 collect i) '(+))) (1 2 3 4 +) is a LIST 0 1 1 2 2 3 3 4 4 + 10 The macro only gets that data and can do anything with it. There is no idea of Abstract Syntax Tree: it does not need to be a tree, it does not need to be valid Lisp code and it carries no syntactical information. Generally, it also does not need to return valid Lisp code. To be computed all we need is that the evaluator eventually sees valid Lisp code, not the individual macro. In Lisp the "reader" by default only parses a data layer: symbolic expressions. EVAL, macros and other Lisp functionality gets mostly data passed. EVAL has to figure out, what (a b c) actually is as a program. It can traverse it in an interpreter or compile it. A compiler may internally create AST representations -> but that free to the implementation. The Lisp language then typically is not defined over text syntax, but data syntax. A Lisp interpreter processes during execution not text, but s-expressions. It's a "List Processor", not a Text Processor. Lisp not Texp. ;-) The function COMPILE gets an s-expression passed, not text. Racket and Scheme have other macro systems.
- JonChesterfield 2y ago
  You are correct and the precision is appreciated. However your emphasis is somewhat misleading. In the lisp world, when data represents code, it's probably stored in a tree. Elsewhere, when data represents code, it's probably stored as an array of bytes. There code may not be recognised as being data at all. It's the difference between eval taking a byte string and taking a parse tree. Rather literally. This is only a convention. Lisp does it right, but as almost everything else thinks code is strings, confusion abounds.
  - kazinator 2y ago
    There is a "data AST" in Lisp. The data AST is source code to Lisp evaluation/compilation. Compilation may produce another AST, but typically this is something internal, and implementation-specific. The data AST is rich enough to for ergonomic, precise source-to-source manipulation. Even a pretty advanced Lisp compiler can be built which goes straight from the data AST to an intermediate representation, skipping the code AST stage. "Data AST" means that when we have (+ 1 2), this doesn't say "I'm an arithmetic expression", but rather something weaker: "I'm a list of three elements: a symbol object, and two integer objects". The list object is an abstract syntax tree for the printed list. It must be. It not a parse tree because a parse tree would preserve the representation of the parentheses: in a parse tree, every grammar symbol appears: the nodes of the tree are 1:1 to the grammar rules that they match. Since the parentheses, and whatnot, are gone, it must be abstract syntax. Most of Lisp syntax is designed such that its syntactic units correspond to nodes of the data AST. That makes source-to-source transformations ergonomic, because the data AST data structure is easy to manipulate.
- ndr 2y ago
  How is a list (of nested lists) not a tree?
  - lispm 2y ago
    It could theoretically be a graph. For example I can make a circular list being a part of the source and the macro may process it. Get the first two items from a list and add them: CL-USER 21 > (defmacro add-2 (a) (list '+ (first a) (second a))) ADD-2 Now we construct a circular list and use the macro: CL-USER 22 > (add-2 #1=(1 2 3 . #1#)) 3 The circular list is really a part of the source code: CL-USER 23 > '(add-2 #1=(1 2 3 . #1#)) (ADD-2 #1=(1 2 3 . #1#)) Another example: One could pass in a string and have the macro parse the string...
pjc50 2y ago
I'm not sure that something which uses brainfuck as its default example is intending you to take it seriously. Personally I burst out laughing at the introduction of "metacrank".

aidenn0 2y ago

Heck, I'm not convinced that this is a better idea than Common Lisp readtable[1], and I think Racket's #lang is more ergonomic than the CL readtable. 1: Which is powerful enough to implement a C compiler in: https://github.com/vsedach/Vacietis https://github.com/vsedach/Vacietis

lispm 2y ago

> Lisp ... macros typically operate on AST In Lisp they don't. See Emacs Lisp, Common Lisp, ISLISP. A Lisp macro gets only passed some data and returns some data. There is nothing like an AST. If we define a macro foo-macro and we call it: (foo-macro ...) then ... can be any data. Example: (defmacro rev (&rest items) (reverse items)) Above macro REV gets data passed and reverses it. The &rest list of ITEMS gets reversed. ITEMS is the list of source arguments in the macro call. We can then write: (rev 1 2 3 4 +) (rev (rev 10 n -) (+ a 20 b) (rev 30 a *) list) Example: CL-USER 7 > (let ((n 4) (a 3) (b 2)) (rev (rev 10 n -) (+ a 20 b) (rev 30 a *) list)) (90 25 -6) There is no syntax tree. All the macro does, is to reverse the list of its source arguments. If I let the macro describe the thing it gets passed, then we get this: CL-USER 8 > (defmacro rev (&rest items) (DESCRIBE items) (reverse items)) REV CL-USER 9 > (rev 1 2 3 4 +) (1 2 3 4 +) is a LIST 0 1 1 2 2 3 3 4 4 + 10 As a side effect, we can see that the macro gets a simple list passed. A list of numbers and a symbol ("symbol" is also a data type). Not text. Not an AST. Also data which is possibly not read, but computed by other code. We can compute the arguments of the macro REV and pass the thing to EVAL. Works the same as above. CL-USER 10 > (eval (append '(rev) (loop for i from 1 to 4 collect i) '(+))) (1 2 3 4 +) is a LIST 0 1 1 2 2 3 3 4 4 + 10 The macro only gets that data and can do anything with it. There is no idea of Abstract Syntax Tree: it does not need to be a tree, it does not need to be valid Lisp code and it carries no syntactical information. Generally, it also does not need to return valid Lisp code. To be computed all we need is that the evaluator eventually sees valid Lisp code, not the individual macro. In Lisp the "reader" by default only parses a data layer: symbolic expressions. EVAL, macros and other Lisp functionality gets mostly data passed. EVAL has to figure out, what (a b c) actually is as a program. It can traverse it in an interpreter or compile it. A compiler may internally create AST representations -> but that free to the implementation. The Lisp language then typically is not defined over text syntax, but data syntax. A Lisp interpreter processes during execution not text, but s-expressions. It's a "List Processor", not a Text Processor. Lisp not Texp. ;-) The function COMPILE gets an s-expression passed, not text. Racket and Scheme have other macro systems.

JonChesterfield 2y ago
You are correct and the precision is appreciated. However your emphasis is somewhat misleading. In the lisp world, when data represents code, it's probably stored in a tree. Elsewhere, when data represents code, it's probably stored as an array of bytes. There code may not be recognised as being data at all. It's the difference between eval taking a byte string and taking a parse tree. Rather literally. This is only a convention. Lisp does it right, but as almost everything else thinks code is strings, confusion abounds.
- kazinator 2y ago
  There is a "data AST" in Lisp. The data AST is source code to Lisp evaluation/compilation. Compilation may produce another AST, but typically this is something internal, and implementation-specific. The data AST is rich enough to for ergonomic, precise source-to-source manipulation. Even a pretty advanced Lisp compiler can be built which goes straight from the data AST to an intermediate representation, skipping the code AST stage. "Data AST" means that when we have (+ 1 2), this doesn't say "I'm an arithmetic expression", but rather something weaker: "I'm a list of three elements: a symbol object, and two integer objects". The list object is an abstract syntax tree for the printed list. It must be. It not a parse tree because a parse tree would preserve the representation of the parentheses: in a parse tree, every grammar symbol appears: the nodes of the tree are 1:1 to the grammar rules that they match. Since the parentheses, and whatnot, are gone, it must be abstract syntax. Most of Lisp syntax is designed such that its syntactic units correspond to nodes of the data AST. That makes source-to-source transformations ergonomic, because the data AST data structure is easy to manipulate.
ndr 2y ago
How is a list (of nested lists) not a tree?
- lispm 2y ago
  It could theoretically be a graph. For example I can make a circular list being a part of the source and the macro may process it. Get the first two items from a list and add them: CL-USER 21 > (defmacro add-2 (a) (list '+ (first a) (second a))) ADD-2 Now we construct a circular list and use the macro: CL-USER 22 > (add-2 #1=(1 2 3 . #1#)) 3 The circular list is really a part of the source code: CL-USER 23 > '(add-2 #1=(1 2 3 . #1#)) (ADD-2 #1=(1 2 3 . #1#)) Another example: One could pass in a string and have the macro parse the string...

pjc50 2y ago

I'm not sure that something which uses brainfuck as its default example is intending you to take it seriously. Personally I burst out laughing at the introduction of "metacrank".