7 ms·

Not everything is an expression

spenczar5 12y ago
Recurse is really publishing some fantastic stuff. This entire second issue has been just great.
taeric 12y ago
While it is generally held that everything in lisp is an expression. Isn't the more pertinant fact that everything is a list? That is, I thought macros hinged on the fact that everything is a list, not that everything is an expression.
- arohner 12y ago
  Macros hinge on the idea that code is data. Macros are functions that run at "compile-time" [1], that take unevaluated code (i.e. data) and return any valid data, it just happens that returning a list is interpreted as a function call. But I can also define: (defmacro foo [x] :foo) which always returns a keyword. All lisps that I'm aware of only let macros dispatch on list evaluation, i.e. when you see (foo ...), call the function defined in (defmacro foo), but I'm not aware of any limitation preventing you from applying that to other types of data. [1] technically, they run at macro-expansion time, which is after reading the expression, and before evaluating.
  - taeric 12y ago
    Right, my point is that is less dependent on "everything is an expression" and more that "everything is a list." Right?
    - arohner 12y ago
      And my point is that everything isn't a list, but it is data. Macros are functions that take data, and return data. Their most common usage is that that they take lists and return lists, but that isn't required.
      - taeric 12y ago
        Makes sense. I was actually coming at it from the "everything is in a list" vantage. And can be destructured as such. (Restructured, as well, of course.)
- frou_dh 12y ago
  But everything isn't a list. The number 12 or the symbol x are expressions but not lists.
  - taeric 12y ago
    They are atoms. Of a list.
    - frou_dh 12y ago
      Often they are but not always, e.g. a value of type other than cell/list can be evaluated at the top-level. How the top-level itself works is an implementation detail. More fundamentally, being known to something else is not the direction "is a" works in.
      - taeric 12y ago
        Apologies for missing this earlier. At evaluation time, I agree things make a difference. Before that, though, things are merely items in a list. So, yeah, I said it poorly. It is less "everything is a list." And more "everything is in a list." At least at the reasoning level.
ICWiener 12y ago
Macros will expand into lisp forms, not only expressions. Whether a form is an expression, a declaration or a pattern depends on the surrounding context. I would say that declarations, ... are not syntax but semantic classes. Too bad the conclusion does not offer a glimpse of what would the extension mechanism look like. Still, nice article.
- dgreensp 12y ago
  Yes, critically speaking, the author seemed on track to implementing an extensible pattern matching system based on macros, before stopping to end with the point that it wasn't the obvious, idiomatic, built-in thing to do. And in this system, patterns are expressions. So "everything is an expression" isn't exactly wrong in this case. In Scala, you are given full control over both how a name "applies" (i.e. what Foo(...) does when called as a sort of constructor or factory method) and how it matches, in the form of an "unapply" static method that you implement. It seems like a "match" macro in a LISP could desugar a pattern into a program that matches that pattern, the same way the Scala compiler generates code that calls "unapply".
  - rntz 12y ago
    Author here. I have created a language, called moxy (https://www.github.com/rntz/moxy https://www.github.com/rntz/moxy), which supports not just extensible pattern-matching but defining extensible extensions in general (of which pattern matching is one example, LINQ might be another, and so on and so forth). However, it wasn't a lisp, because I also wanted to see whether I could support syntactic extensibility in a non-lisp language. The really important point, that moxy explored and that I think I didn't make clear in the article, is that patterns are just one example of where you want extensibility of a non-expression syntax class. Really you want to be able to define your own syntax classes and be able to extend them! I only mentioned moxy in a footnote in the article because it's "research-quality" at the moment - it's not well documented and I'm still having second thoughts about its design. I've moved on to other thing and am busy with work, so I don't imagine I'll be working on it in the immediate future.
- rntz 12y ago
endlessvoid94 12y ago
If you haven't had the chance to read "The Art of the Metaobject Protocol" [0], I highly recommend it. It deserves to be mentioned anytime something like OMeta is mentioned. [0] http://www.amazon.com/Art-Metaobject-Protocol-Gregor-Kiczales/dp/0262610744/ref=sr_1_1?ie=UTF8&qid=1427490532&sr=8-1&keywords=the+art+of+the+metaobject+protocol http://www.amazon.com/Art-Metaobject-Protocol-Gregor-Kiczale...
ThatGeoGuy 12y ago
I don't mean to be a pedant, but the author mentions a "syntax for patterns", basically claiming that Lisp doesn't have one. But, isn't syntax-rules (a la scheme) already a form for matching / macro-ing patterns? From my understanding the author seems to want macros that can be specialized for new forms. I may be confused about what the exact claim is here, but I don't see how this has anything to do with whether or not something is an expression. I don't quite understand how having "not everything is an expression" helps solve this problem.
- rntz 12y ago
  Author here! syntax-rules is a form of pattern matching (mentioned in footnote 2). But it's only for matching on syntax, not on ordinary values. I can't write the fibonacci function using syntax-rules. The idea behind "not everything is an expression" is that ordinary macros only extend the expressions in a language. But languages have more than expressions to them - they also have patterns, and possibly other syntax classes (loop formats, LINQ, monadic do-syntax). I think those syntax classes ought to be macro-extensible as well. That's what I mean when I say that ordinary macros don't acknowledge that not everything is an expression. It's rather a roundabout way to say it, I guess.
  - malisper 12y ago
    Well iterate[0], which is a lispy version of loop, is actually extendable through macros[1]. So what you are looking for is just a generic way to enable that for all macros? Iterate does it by having a code walker go over the code and macroexpand the extendable parts. It shouldn't be too hard to apply that method to new DSLs by specifying the syntax of the DSL to the code walker. [0] https://common-lisp.net/project/iterate/ https://common-lisp.net/project/iterate/ [1] https://common-lisp.net/project/iterate/doc/Rolling-Your-Own.html#Rolling-Your-Own https://common-lisp.net/project/iterate/doc/Rolling-Your-Own...
    - rntz 12y ago
      Yup, I pretty much want it to be trivially easy for define macros that are themselves macro-extensible. It's definitely possible to do this in Lisp, but: (a) it's not a well-known technique (b) it's not in the standard library of any Lisp I know of (c) there are interesting open design questions to be answered in the implementation of such a system I hope this article will get folks thinking about these issues. For example, walking the AST and calling macroexpand will work, but then you can't have a macro that expands differently in different contexts - when interpreted as an expression versus as a pattern, for example. I think this is an important feature.
kerkeslager 12y ago
This is an interesting approach. I'm working on a Lisp variant that recognizes the difference between expressions and... non-expressions? But taking the opposite approach: I found a way to make it so that everything is an expression while allowing one to do everything you would do with a non-expression via expressions. To achieve this, there are two kinds of expression: mutations and functions. There are two things to understand about this: 1. All expressions take in the environment. Most functions don't use it, while most mutations do. 2. All expressions run inside a trampoline that evaluates them. The difference between a mutation and a function is that when the trampoline evaluates a function, it places its result into the return register (where it can be picked up by something else). In contrast, when the trampoline evaluates a mutation, it replaces the environment with the result. This is why mutations typically use the environment--rather than destroying the environment, you usually want to build the new environment with most of the old environment. Some examples: ((mut () env (assoc env :foo 1))) ; equivalent to (define foo 1) ((mut () env (assoc env :my-define (mut (dest src) env (assoc env dest src))))) ; this is actually how `define` is defined ((mut () env (map))) ((+ 1 1)) ; throws exception "undefined symbol +" because previous line emptied the environment The "everything takes env" bit is inspired by J. Shutt's paper on his Kernel programming language: https://www.wpi.edu/Pubs/ETD/Available/etd-090110-124904/unrestricted/jshutt.pdf https://www.wpi.edu/Pubs/ETD/Available/etd-090110-124904/unr... and a lot of what I'm working on is built on his work.
- agumonkey 12y ago
  LiSP had a chapter on first class env http://pagesperso-systeme.lip6.fr/Christian.Queinnec/WWW/LiSP.html http://pagesperso-systeme.lip6.fr/Christian.Queinnec/WWW/LiS...
  - kerkeslager 12y ago
    Coincidentally, I just started reading that book. Hopefully it doesn't make my research redundant. :)
    - agumonkey 12y ago
ggchappell 12y ago
Interesting article. A few thoughts: The fact that Lisp does not distinguish between statements and declarations is closely tied to the fact that Lisp is very much a dynamic language (in particular, it is dynamically typed). The article uses the example of Python declaration vs. statement; but actually Python declarations are statements, too. This is typical of dynamic languages. On the other hand, in a statically typed language there is necessarily a distinction between code that is executed at runtime and (although we often don't talk about it this way) code that is executed at compile time. Declarations happen at compile time. Expressions and statements happen at runtime. The two categories almost always use very different syntax. Among statically typed languages, Haskell is particularly interesting, because, while it necessarily makes a strong distinction between expressions and declarations, it has erased the distinction between expression and statement: the latter is represented by an expression that returns a list of side effects. Another interesting take on this issue can be found in Daan Leijen's Koka programming language[1]. In Koka, whether a function has side effects is part of its type. So effect inference can be done. The result, if I understand things correctly, is that the expression-or-statement issue becomes more than just a yes/no thing. I think these ideas are worth further exploration. Lastly: an extensible pattern set. My goodness, yes. That's the big lack I feel in Haskell; I want to define new kinds of patterns. I've read that F# has good support for this, but I know nothing about it; can anyone comment? [1] http://research.microsoft.com/en-us/projects/koka/ http://research.microsoft.com/en-us/projects/koka/
- rntz 12y ago
  Yes, my discussion of the notion of syntax-classes is definitely a brief gloss, not an in-depth examination. I deliberately ignored the fact that Python merges statements & declarations in order to be able to demonstrate all four syntax classes in a single small example. I'm not sure it's appropriate to say that declarations are "executed at" compile time in a statically-typed language. In SML, for example, there's a notion of "phase separation" by which you can split the meaning of a program into its compile-phase and its run-phase meanings. Many declarations end up having both compile- and run-time components. In Haskell you might say that declarations are executed at compile time, but this means nothing more than that name-resolution and type-checking happen at compile time.
- 12y ago
zem 12y ago
minor nitpick - even if "OCaml has no equivalent of Haskell's Ordering or SML's order types" there is Pervasives.compare. it returns {0,-1,+1} rather than {EQ, LT, GT}, but you can still say match compare x v with | 0 -> ... | 1 -> ... | _ -> ... with the minor wart that since compare returns an int, you need to match the last case with a default to prevent the compiler from warning you about possibly not matching other int values.
yawaramin 12y ago
Sure, not everything is an expression; but an expressive language provides an expression that can contain other syntax classes and confine all their effects within the bounds of the expression. E.g., SML's 'let' expression. In a language that doesn't allow that, we end up having to do some really weird things (https://github.com/yawaramin/lambdak https://github.com/yawaramin/lambdak).
siscia 12y ago
I don't really get what the author is claiming... I would have code his `if-mathch` in a simpler way in clojure: (case (f data-structure) 0 (do-something) 1 (do-something-else) (do-default)) Where `f` can be a function defined in a protocol or a multimethod, so you can actually implement your own `f` for any data structure you like. Now, what I am missing ?
weavejester 12y ago
I've read through the article twice, and I still have no idea what the author is getting at. The author suggests that "the obvious way to implement a DSL as a macro, as we saw with if-match, hard-codes the form of the new syntax class". I disagree. That's not what I'd consider the obvious way at all. I'd consider the most obvious approach would be to pass the macro onto a polymorphic function of some description: (defmulti if-match* (fn [pat _ _ _] (if (list? pat) (first pat) (type pat))) (defmacro if-match [pat expr then else] (if-match* pat expr then else)) Macros have all the same capabilities for extensibility as regular functions. In Clojure at least, macros are just functions with some metadata attached.
- rntz 12y ago
  That's a very clever use of defmulti that I hadn't considered --- consider that you may know more about writing extensible macros than the average lisper :P. My article was also aimed at being language-agnostic, so a Clojure-specific feature like defmulti wouldn't have been appropriate to introduce. (Although of course CLOS does have multimethods as well, but that's an even more complicated subject!) However: 1. The code you give still isn't smart enough. It dispatches on the symbol at the head of the list, but that doesn't account for namespacing. So your pattern-macros will all end up in one giant namespace. You could probably invent something clever to account for this but... 2. My overall point[1] was that writing a macro-extensible macro shouldn't require cleverness or new code - it should be in the standard library! Indeed, ideally defining a "pattern-macro" should be accomplished via the same mechanism as defining an "expression-macro"; you shouldn't need separate, custom macro-defining-macros for each syntax class. I'd settle for it just being easy to define an extensible syntax class along with a macro-defining-macro for it, though. [1] Admittedly, this point could have been far clearer.
  - ICWiener 12y ago
    Regarding 1., I don't think it follows that the pattern-macro will end up in one giant namespace. I'd love to understand why you think so. And for 2, even though what you say seems desirable on the surface, you still approaches the problem in a way that is too fuzzy, or abstract. Just as saying "we should write more secure code" and then failing to attack the problem directly. No offense, but even though you may have a nice idea, your explanation is a little too handwavy.
gumby 12y ago
Not sure why it's a surprise that languages inherently require metasyntactic operations. This has been clear since Church and Gödel. There's lot of good work on programming languages that allow metasyntactic runtime extensions, going back to Brian Smith's work at PARC.
robgibbons 12y ago
It seems to me that it's possible to define most statements in an expressive syntax, at least in any language which allows for both constructs. For instance, in JavaScript one can use ternary syntax in place of an if-statement. Is a ternary condition actually an expression? It seems more of an expression than a statement, but one could argue it's just a simplified syntax of a conditional statement.
IshKebab 12y ago
Totally off-topic, but I was curious if the recursive Rust `sum` function is actually optimised correctly. Code: fn sum(l: &[i64]) -> i64 { match l { [] => 0, [x, xs..] => x + sum(xs) } } Assembly: _ZN3sum20hf66fc5855a7cf5fc3aaE: .cfi_startproc cmpq %fs:112, %rsp ja .LBB2_2 movabsq $24, %r10 movabsq $0, %r11 callq __morestack retq .LBB2_2: pushq %rbx .Ltmp10: .cfi_def_cfa_offset 16 subq $16, %rsp .Ltmp11: .cfi_def_cfa_offset 32 .Ltmp12: .cfi_offset %rbx, -16 movq 8(%rdi), %rcx xorl %eax, %eax testq %rcx, %rcx je .LBB2_4 movq (%rdi), %rax decq %rcx movq (%rax), %rbx addq $8, %rax movq %rax, (%rsp) movq %rcx, 8(%rsp) leaq (%rsp), %rdi callq _ZN3sum20hf66fc5855a7cf5fc3aaE addq %rbx, %rax .LBB2_4: addq $16, %rsp popq %rbx retq So... no.
- dbpatterson 12y ago
  You might get better optimizations if you make it tail recursive (LLVM probably gets some of these). ie: fn sum_tail(v : i64, l: &[i64]) -> i64 { match l { [] => v, [x, xs..] => sum(v + x, xs) } }
lispm 12y ago
If you look at the literature there are numerous examples of extensible macros. Often this is done for rule-based systems, which also involves matching or unification. Typically one wants to define these rules individually, update them individually, etc. One needs a registry, an interning function and a driving function. Below is just an example: (defvar *patterns* (make-hash-table)) (defparameter *pattern-names* nil) (defun intern-pattern (name if-pattern then-pattern) (setf *pattern-names* (append *pattern-names* (list name))) (setf (gethash name *patterns*) (list (compile nil `(lambda (pat) ,if-pattern)) (compile nil `(lambda (pat expr then else) (declare (ignorable pat expr then else)) ,then-pattern)))) name) (defmacro if-match (pat expr then else) (loop for name in *pattern-names* for (if-part then-part) = (gethash name *patterns*) when (funcall if-part pat) do (return (funcall then-part pat expr then else)))) (intern-pattern 'variable '(and pat (symbolp pat)) '`(let ((,pat ,expr)) ,then)) (intern-pattern 'literal-atom '(atom pat) '`(if (equalp ',pat ,expr) ,then ,else)) (intern-pattern 'cons '(eq 'cons (car pat)) '(destructuring-bind (_ p-car p-cdr) pat (declare (ignore _)) (let ((tmp (gensym))) `(let ((,tmp ,expr)) (if (consp ,tmp) (if-match ,p-car (car ,tmp) (if-match ,p-cdr (cdr ,tmp) ,then ,else) ,else) ,else))))) Writing the macro DEFPATTERN is then trivial... I help maintain an old Lisp-based web server, which was written in the mid-90s on the Symbolics Lisp Machine. It literally has zillions of these registry/intern/machinery/defining-macro combinations... It's just: one has to program those. But it has been done many many many times.
escherize 12y ago
I'm pretty confused by the author's definition of statements. FTA: "Statements are executed to take some action. Variable assignments, loops, conditionals, and raising exceptions are examples of statements." With respect to variable assignments or raising exceptions (though examples exist of the others...) aren't these by the author's definition statements? (def a "apple") or (throw (Exception. "my exception message"))

Recurse is really publishing some fantastic stuff. This entire second issue has been just great.

While it is generally held that everything in lisp is an expression. Isn't the more pertinant fact that everything is a list? That is, I thought macros hinged on the fact that everything is a list, not that everything is an expression.

arohner 12y ago
Macros hinge on the idea that code is data. Macros are functions that run at "compile-time" [1], that take unevaluated code (i.e. data) and return any valid data, it just happens that returning a list is interpreted as a function call. But I can also define: (defmacro foo [x] :foo) which always returns a keyword. All lisps that I'm aware of only let macros dispatch on list evaluation, i.e. when you see (foo ...), call the function defined in (defmacro foo), but I'm not aware of any limitation preventing you from applying that to other types of data. [1] technically, they run at macro-expansion time, which is after reading the expression, and before evaluating.
- taeric 12y ago
  Right, my point is that is less dependent on "everything is an expression" and more that "everything is a list." Right?
  - arohner 12y ago
    And my point is that everything isn't a list, but it is data. Macros are functions that take data, and return data. Their most common usage is that that they take lists and return lists, but that isn't required.
    - taeric 12y ago
      Makes sense. I was actually coming at it from the "everything is in a list" vantage. And can be destructured as such. (Restructured, as well, of course.)
frou_dh 12y ago
But everything isn't a list. The number 12 or the symbol x are expressions but not lists.
- taeric 12y ago
  They are atoms. Of a list.
  - frou_dh 12y ago
    Often they are but not always, e.g. a value of type other than cell/list can be evaluated at the top-level. How the top-level itself works is an implementation detail. More fundamentally, being known to something else is not the direction "is a" works in.
    - taeric 12y ago
      Apologies for missing this earlier. At evaluation time, I agree things make a difference. Before that, though, things are merely items in a list. So, yeah, I said it poorly. It is less "everything is a list." And more "everything is in a list." At least at the reasoning level.

ICWiener 12y ago

Macros will expand into lisp forms, not only expressions. Whether a form is an expression, a declaration or a pattern depends on the surrounding context. I would say that declarations, ... are not syntax but semantic classes. Too bad the conclusion does not offer a glimpse of what would the extension mechanism look like. Still, nice article.

dgreensp 12y ago
Yes, critically speaking, the author seemed on track to implementing an extensible pattern matching system based on macros, before stopping to end with the point that it wasn't the obvious, idiomatic, built-in thing to do. And in this system, patterns are expressions. So "everything is an expression" isn't exactly wrong in this case. In Scala, you are given full control over both how a name "applies" (i.e. what Foo(...) does when called as a sort of constructor or factory method) and how it matches, in the form of an "unapply" static method that you implement. It seems like a "match" macro in a LISP could desugar a pattern into a program that matches that pattern, the same way the Scala compiler generates code that calls "unapply".
- rntz 12y ago
  Author here. I have created a language, called moxy (https://www.github.com/rntz/moxy https://www.github.com/rntz/moxy), which supports not just extensible pattern-matching but defining extensible extensions in general (of which pattern matching is one example, LINQ might be another, and so on and so forth). However, it wasn't a lisp, because I also wanted to see whether I could support syntactic extensibility in a non-lisp language. The really important point, that moxy explored and that I think I didn't make clear in the article, is that patterns are just one example of where you want extensibility of a non-expression syntax class. Really you want to be able to define your own syntax classes and be able to extend them! I only mentioned moxy in a footnote in the article because it's "research-quality" at the moment - it's not well documented and I'm still having second thoughts about its design. I've moved on to other thing and am busy with work, so I don't imagine I'll be working on it in the immediate future.
rntz 12y ago

endlessvoid94 12y ago

If you haven't had the chance to read "The Art of the Metaobject Protocol" [0], I highly recommend it. It deserves to be mentioned anytime something like OMeta is mentioned. [0] http://www.amazon.com/Art-Metaobject-Protocol-Gregor-Kiczales/dp/0262610744/ref=sr_1_1?ie=UTF8&qid=1427490532&sr=8-1&keywords=the+art+of+the+metaobject+protocol http://www.amazon.com/Art-Metaobject-Protocol-Gregor-Kiczale...

ThatGeoGuy 12y ago

I don't mean to be a pedant, but the author mentions a "syntax for patterns", basically claiming that Lisp doesn't have one. But, isn't syntax-rules (a la scheme) already a form for matching / macro-ing patterns? From my understanding the author seems to want macros that can be specialized for new forms. I may be confused about what the exact claim is here, but I don't see how this has anything to do with whether or not something is an expression. I don't quite understand how having "not everything is an expression" helps solve this problem.

rntz 12y ago
Author here! syntax-rules is a form of pattern matching (mentioned in footnote 2). But it's only for matching on syntax, not on ordinary values. I can't write the fibonacci function using syntax-rules. The idea behind "not everything is an expression" is that ordinary macros only extend the expressions in a language. But languages have more than expressions to them - they also have patterns, and possibly other syntax classes (loop formats, LINQ, monadic do-syntax). I think those syntax classes ought to be macro-extensible as well. That's what I mean when I say that ordinary macros don't acknowledge that not everything is an expression. It's rather a roundabout way to say it, I guess.
- malisper 12y ago
  Well iterate[0], which is a lispy version of loop, is actually extendable through macros[1]. So what you are looking for is just a generic way to enable that for all macros? Iterate does it by having a code walker go over the code and macroexpand the extendable parts. It shouldn't be too hard to apply that method to new DSLs by specifying the syntax of the DSL to the code walker. [0] https://common-lisp.net/project/iterate/ https://common-lisp.net/project/iterate/ [1] https://common-lisp.net/project/iterate/doc/Rolling-Your-Own.html#Rolling-Your-Own https://common-lisp.net/project/iterate/doc/Rolling-Your-Own...
  - rntz 12y ago
    Yup, I pretty much want it to be trivially easy for define macros that are themselves macro-extensible. It's definitely possible to do this in Lisp, but: (a) it's not a well-known technique (b) it's not in the standard library of any Lisp I know of (c) there are interesting open design questions to be answered in the implementation of such a system I hope this article will get folks thinking about these issues. For example, walking the AST and calling macroexpand will work, but then you can't have a macro that expands differently in different contexts - when interpreted as an expression versus as a pattern, for example. I think this is an important feature.

kerkeslager 12y ago

This is an interesting approach. I'm working on a Lisp variant that recognizes the difference between expressions and... non-expressions? But taking the opposite approach: I found a way to make it so that everything is an expression while allowing one to do everything you would do with a non-expression via expressions. To achieve this, there are two kinds of expression: mutations and functions. There are two things to understand about this: 1. All expressions take in the environment. Most functions don't use it, while most mutations do. 2. All expressions run inside a trampoline that evaluates them. The difference between a mutation and a function is that when the trampoline evaluates a function, it places its result into the return register (where it can be picked up by something else). In contrast, when the trampoline evaluates a mutation, it replaces the environment with the result. This is why mutations typically use the environment--rather than destroying the environment, you usually want to build the new environment with most of the old environment. Some examples: ((mut () env (assoc env :foo 1))) ; equivalent to (define foo 1) ((mut () env (assoc env :my-define (mut (dest src) env (assoc env dest src))))) ; this is actually how `define` is defined ((mut () env (map))) ((+ 1 1)) ; throws exception "undefined symbol +" because previous line emptied the environment The "everything takes env" bit is inspired by J. Shutt's paper on his Kernel programming language: https://www.wpi.edu/Pubs/ETD/Available/etd-090110-124904/unrestricted/jshutt.pdf https://www.wpi.edu/Pubs/ETD/Available/etd-090110-124904/unr... and a lot of what I'm working on is built on his work.

agumonkey 12y ago
LiSP had a chapter on first class env http://pagesperso-systeme.lip6.fr/Christian.Queinnec/WWW/LiSP.html http://pagesperso-systeme.lip6.fr/Christian.Queinnec/WWW/LiS...
- kerkeslager 12y ago
  Coincidentally, I just started reading that book. Hopefully it doesn't make my research redundant. :)
  - agumonkey 12y ago

ggchappell 12y ago

Interesting article. A few thoughts: The fact that Lisp does not distinguish between statements and declarations is closely tied to the fact that Lisp is very much a dynamic language (in particular, it is dynamically typed). The article uses the example of Python declaration vs. statement; but actually Python declarations are statements, too. This is typical of dynamic languages. On the other hand, in a statically typed language there is necessarily a distinction between code that is executed at runtime and (although we often don't talk about it this way) code that is executed at compile time. Declarations happen at compile time. Expressions and statements happen at runtime. The two categories almost always use very different syntax. Among statically typed languages, Haskell is particularly interesting, because, while it necessarily makes a strong distinction between expressions and declarations, it has erased the distinction between expression and statement: the latter is represented by an expression that returns a list of side effects. Another interesting take on this issue can be found in Daan Leijen's Koka programming language[1]. In Koka, whether a function has side effects is part of its type. So effect inference can be done. The result, if I understand things correctly, is that the expression-or-statement issue becomes more than just a yes/no thing. I think these ideas are worth further exploration. Lastly: an extensible pattern set. My goodness, yes. That's the big lack I feel in Haskell; I want to define new kinds of patterns. I've read that F# has good support for this, but I know nothing about it; can anyone comment? [1] http://research.microsoft.com/en-us/projects/koka/ http://research.microsoft.com/en-us/projects/koka/

rntz 12y ago
Yes, my discussion of the notion of syntax-classes is definitely a brief gloss, not an in-depth examination. I deliberately ignored the fact that Python merges statements & declarations in order to be able to demonstrate all four syntax classes in a single small example. I'm not sure it's appropriate to say that declarations are "executed at" compile time in a statically-typed language. In SML, for example, there's a notion of "phase separation" by which you can split the meaning of a program into its compile-phase and its run-phase meanings. Many declarations end up having both compile- and run-time components. In Haskell you might say that declarations are executed at compile time, but this means nothing more than that name-resolution and type-checking happen at compile time.
12y ago

zem 12y ago

minor nitpick - even if "OCaml has no equivalent of Haskell's Ordering or SML's order types" there is Pervasives.compare. it returns {0,-1,+1} rather than {EQ, LT, GT}, but you can still say match compare x v with | 0 -> ... | 1 -> ... | _ -> ... with the minor wart that since compare returns an int, you need to match the last case with a default to prevent the compiler from warning you about possibly not matching other int values.

yawaramin 12y ago

Sure, not everything is an expression; but an expressive language provides an expression that can contain other syntax classes and confine all their effects within the bounds of the expression. E.g., SML's 'let' expression. In a language that doesn't allow that, we end up having to do some really weird things (https://github.com/yawaramin/lambdak https://github.com/yawaramin/lambdak).

siscia 12y ago

I don't really get what the author is claiming... I would have code his `if-mathch` in a simpler way in clojure: (case (f data-structure) 0 (do-something) 1 (do-something-else) (do-default)) Where `f` can be a function defined in a protocol or a multimethod, so you can actually implement your own `f` for any data structure you like. Now, what I am missing ?

weavejester 12y ago

I've read through the article twice, and I still have no idea what the author is getting at. The author suggests that "the obvious way to implement a DSL as a macro, as we saw with if-match, hard-codes the form of the new syntax class". I disagree. That's not what I'd consider the obvious way at all. I'd consider the most obvious approach would be to pass the macro onto a polymorphic function of some description: (defmulti if-match* (fn [pat _ _ _] (if (list? pat) (first pat) (type pat))) (defmacro if-match [pat expr then else] (if-match* pat expr then else)) Macros have all the same capabilities for extensibility as regular functions. In Clojure at least, macros are just functions with some metadata attached.

rntz 12y ago
That's a very clever use of defmulti that I hadn't considered --- consider that you may know more about writing extensible macros than the average lisper :P. My article was also aimed at being language-agnostic, so a Clojure-specific feature like defmulti wouldn't have been appropriate to introduce. (Although of course CLOS does have multimethods as well, but that's an even more complicated subject!) However: 1. The code you give still isn't smart enough. It dispatches on the symbol at the head of the list, but that doesn't account for namespacing. So your pattern-macros will all end up in one giant namespace. You could probably invent something clever to account for this but... 2. My overall point[1] was that writing a macro-extensible macro shouldn't require cleverness or new code - it should be in the standard library! Indeed, ideally defining a "pattern-macro" should be accomplished via the same mechanism as defining an "expression-macro"; you shouldn't need separate, custom macro-defining-macros for each syntax class. I'd settle for it just being easy to define an extensible syntax class along with a macro-defining-macro for it, though. [1] Admittedly, this point could have been far clearer.
- ICWiener 12y ago
  Regarding 1., I don't think it follows that the pattern-macro will end up in one giant namespace. I'd love to understand why you think so. And for 2, even though what you say seems desirable on the surface, you still approaches the problem in a way that is too fuzzy, or abstract. Just as saying "we should write more secure code" and then failing to attack the problem directly. No offense, but even though you may have a nice idea, your explanation is a little too handwavy.

gumby 12y ago

Not sure why it's a surprise that languages inherently require metasyntactic operations. This has been clear since Church and Gödel. There's lot of good work on programming languages that allow metasyntactic runtime extensions, going back to Brian Smith's work at PARC.

robgibbons 12y ago

It seems to me that it's possible to define most statements in an expressive syntax, at least in any language which allows for both constructs. For instance, in JavaScript one can use ternary syntax in place of an if-statement. Is a ternary condition actually an expression? It seems more of an expression than a statement, but one could argue it's just a simplified syntax of a conditional statement.

IshKebab 12y ago

Totally off-topic, but I was curious if the recursive Rust `sum` function is actually optimised correctly. Code: fn sum(l: &[i64]) -> i64 { match l { [] => 0, [x, xs..] => x + sum(xs) } } Assembly: _ZN3sum20hf66fc5855a7cf5fc3aaE: .cfi_startproc cmpq %fs:112, %rsp ja .LBB2_2 movabsq $24, %r10 movabsq $0, %r11 callq __morestack retq .LBB2_2: pushq %rbx .Ltmp10: .cfi_def_cfa_offset 16 subq $16, %rsp .Ltmp11: .cfi_def_cfa_offset 32 .Ltmp12: .cfi_offset %rbx, -16 movq 8(%rdi), %rcx xorl %eax, %eax testq %rcx, %rcx je .LBB2_4 movq (%rdi), %rax decq %rcx movq (%rax), %rbx addq $8, %rax movq %rax, (%rsp) movq %rcx, 8(%rsp) leaq (%rsp), %rdi callq _ZN3sum20hf66fc5855a7cf5fc3aaE addq %rbx, %rax .LBB2_4: addq $16, %rsp popq %rbx retq So... no.

dbpatterson 12y ago
You might get better optimizations if you make it tail recursive (LLVM probably gets some of these). ie: fn sum_tail(v : i64, l: &[i64]) -> i64 { match l { [] => v, [x, xs..] => sum(v + x, xs) } }

lispm 12y ago

If you look at the literature there are numerous examples of extensible macros. Often this is done for rule-based systems, which also involves matching or unification. Typically one wants to define these rules individually, update them individually, etc. One needs a registry, an interning function and a driving function. Below is just an example: (defvar *patterns* (make-hash-table)) (defparameter *pattern-names* nil) (defun intern-pattern (name if-pattern then-pattern) (setf *pattern-names* (append *pattern-names* (list name))) (setf (gethash name *patterns*) (list (compile nil `(lambda (pat) ,if-pattern)) (compile nil `(lambda (pat expr then else) (declare (ignorable pat expr then else)) ,then-pattern)))) name) (defmacro if-match (pat expr then else) (loop for name in *pattern-names* for (if-part then-part) = (gethash name *patterns*) when (funcall if-part pat) do (return (funcall then-part pat expr then else)))) (intern-pattern 'variable '(and pat (symbolp pat)) '`(let ((,pat ,expr)) ,then)) (intern-pattern 'literal-atom '(atom pat) '`(if (equalp ',pat ,expr) ,then ,else)) (intern-pattern 'cons '(eq 'cons (car pat)) '(destructuring-bind (_ p-car p-cdr) pat (declare (ignore _)) (let ((tmp (gensym))) `(let ((,tmp ,expr)) (if (consp ,tmp) (if-match ,p-car (car ,tmp) (if-match ,p-cdr (cdr ,tmp) ,then ,else) ,else) ,else))))) Writing the macro DEFPATTERN is then trivial... I help maintain an old Lisp-based web server, which was written in the mid-90s on the Symbolics Lisp Machine. It literally has zillions of these registry/intern/machinery/defining-macro combinations... It's just: one has to program those. But it has been done many many many times.

escherize 12y ago

I'm pretty confused by the author's definition of statements. FTA: "Statements are executed to take some action. Variable assignments, loops, conditionals, and raising exceptions are examples of statements." With respect to variable assignments or raising exceptions (though examples exist of the others...) aren't these by the author's definition statements? (def a "apple") or (throw (Exception. "my exception message"))