9 ms·

S-Expressions (1997)

125 points by panic 9y ago

mitchtbaum 9y ago
Is it impossible to improve on s-expression notation? https://srfi.schemers.org/srfi-110/srfi-110.html#cant-improve https://srfi.schemers.org/srfi-110/srfi-110.html#cant-improv...
- yogthos 9y ago
  The problem with these schemes is that they're at odds with metaprogramming. One huge advantage of s-expressions is that the code is expressed using data literals. You can take any piece of code transform it as you would any regular data and then run it. The biggest practical improvement that I've seen was Clojure notation that expands the number of data literals to include vectors, maps, and sets. I think this greatly helps with readability as it provides additional visual cues, while still preserving homoiconicity.
  - kmill 9y ago
    > The problem with these schemes is that they're at odds with metaprogramming. One huge advantage of s-expressions is that the code is expressed using data literals. I don't think it is necessary for there to be a single uniform syntax for code to be able to fully leverage metaprogramming. Take for instance Mathematica (barring complexities of the evaluator itself...) The underlying type for almost everything in the language is the "expression," essentially a tagged list. The front-end language, called "standard form," can be converted to and from expressions. Expressions can more-or-less be directly serialized as "full form," which looks like McCarthy's M-expressions, and standard form extends this notation with operators and precedence rules. (Technically, standard form is given in a 2d graphical notation that is parsed into expressions, and "input form" is linear text. All the forms are interconvertible.) Programming in Mathematica seems to amount to writing lots of transformation rules for expressions, and it usually works out just writing the code you want to match against, but with pattern variables as holes. You are also free to write in full form for patterns if it helps make intent more precise. I think many cases of code transformation involve a pattern to match against. A language with few syntax classes and with metavariables can support metaprogramming easily enough. There are a few examples I've seen, and, although I can't remember the names, I think MetaOCaml was one. I guess what I'm saying is, so long as you make it so there is a "code literal," no matter the purported "homoiconicity" properties, you're good for metaprogramming. > while still preserving homoiconicity I think Alan Kay using the word "homoiconic" for Lisp was a mistake. The syntax of Lisp really is not the same as the internal representation, unlike the Tcl (which I understand actually executes by manipulating strings). This is a reason structured editors for Lisp don't seem to work out. Here is a new word: autoiconic ("self representing"). A language is autoiconic if there are composable code literals. It is not necessary for an autoiconic language to have "eval," but it is necessary to be able to read in code and then write out equivalent code. Furthermore, the code literals must allow for metavariables and composability: replacing a metavariable with a code literal must result in syntactically valid code when written. This excludes Javascript even though it has template literals. It is questionable whether Clojure is actually homoiconic, but it is arguably autoiconic since it has quasiquotation. (However, the way the quasiquoter works, a read/write cycle will result in code with a bunch of list manipulation functions. The supposed code literal disappears!)
    - kazinator 9y ago
      The problem with "homoiconic" is that it is about a storage mechanism: it says that function definitions are input into the image in a textual format and are stored in more or less that format so that they can later be recalled and edited. "homoiconic" languages can regurgitate their definitions. E.g. the set command in the POSIX shell, or LIST in classic BASIC. Those features are helpful interactively in that they allow a human to transform the code right inside the image by recalling, changing and reinstalling definitions. In Lisp, a data structure can be regurgited, rather than definitions. That is helpful in interactively debugging automated, rather than manual transformations. Moreover, the data structure is not regurgitated from a homoiconic form. It is isomorphic to the text in some way so that the data structure can be visualized from the text easily and vice versa. The programmer writes transformations which manipulate the data. These transformations take place in pipeline-like successive steps, where it is useful to intercept the process at different stages. The programmer of a homoiconic language doesn't do this; the programmer manipulates only the text. A BASIC programmer never works with the internal tokenized lines, for instance, in which a word like PRINT is condensed down to one byte. There is no access to that representation via any API from the language. Homoiconic languages don't place any transformation between the programmer input of a definition and the definition's storage; to do so would mean not to be homoiconic! ANSI Lisp has a very vaguely defined support for homoiconicity: the function ed which is intended to recall a function definition and allow the programmer to edit it. This feature is not very prominent; it is not the basis of Lisp interactivity. Almost every aspect of the function is implementation-dependent. To support ed, an implementation's defun operator has to store the un-expanded form somewhere.
      - kmill 9y ago
        This is a reasonable characterization of homoiconicity. Interestingly, by this definition, v8's implementation of Javascript is homoiconic since functions can be converted to strings, recovering the actual source text for its definition. I once took advantage of this to make a Smalltalk-like source editor for Javascript: http://tmp.esoteri.casa/grip/ http://tmp.esoteri.casa/grip/ (things might no longer work since I last was using it four years ago; I lightly edited it tonight to get it to start up without a file server. Only tested in Chrome!) It's based on an class-based object system I made that can serialize all of its class definitions. This drives both the class browser and the code serializer/saver. (Right now it has two code browsers because I was in the process of making a nicer one. Somehow, I had the idea that I was going to program a whole webapp with this thing, but I lost motivation.)
  - cryptonector 9y ago
    Sweet-expressions are supposed to map easily onto lists, no? Anyways, there are other ways to do metaprogramming. Haskell manages without homoiconicity.
    - zimablue 9y ago
      As far as I know, Haskell's metaprogramming uses template haskell which works but isn't a super elegant/beautiful solution relative to lisp?
      - cryptonector 9y ago
        Metaprogramming is trivial when you have a) lazy evaluation, b) a very smart optimizing compiler. That said, I do love me the Lisp macro system, but homoiconicity alone is not that useful if the representation mechanism makes it difficult to denote lots of implied things (like type inferencing).
  - dwheeler 9y ago
    > The problem with these schemes is that they're at odds with metaprogramming. Sweet-expressions (SRFI-110) support metaprogramming just fine. Sweet-expressions are general and homoiconic (just like S-expressions are), and they're backwards-compatible with traditional S-expressions as they are normally used. You're right that many other "readable" notations don't support metaprogramming, and I completely agree that most schemes are failures because of it. But once you agree that generality and homoiconicity are necessary, it's quite possible to create improved notations. I also think backwards compatibility is a (practical) must, but that is possible too. For more, see: https://readable.sourceforge.io/ https://readable.sourceforge.io/
  - kbp 9y ago
    > The biggest practical improvement that I've seen was Clojure notation that expands the number of data literals to include vectors, maps, and sets. Common Lisp has literal syntax for vectors (and it wasn't the first Lisp to). Its standard representation of a set is just a list, but if someone were to add proper sets to the language they could add read syntax for them easily CL also has read syntax for maps (as has every Lisp) in the form of alists; it doesn't have literal hash tables, but those aren't terribly useful. Alists perform better for lookup for less than 20 or so keys (their writes are always constant-time), and they aren't going to be a bottleneck until you have at least several hundred keys, at which point you probably won't be writing those as literals in your source code. As well, alists have several other nice properties over hash tables, like not being tied to any equality predicate. Alists are a standard Lisp map with literal syntax that's been around since the beginning and are often preferable to hashes, but if you really did want hash literals specifically, it's a trivial read macro.
- taeric 9y ago
  This is a weak argument. Practically all languages compound symbols made from multiple characters, such as >=; there is no shortage of symbols. Also, nearly all programming languages have a function-call notation, but only Lisp-based languages choose s-expressions to notate it, so saying “we need function call notation” do not excuse s-expressions. I'm ironically going to complain that this is a weak rebuttal. For one thing, I find it hilarious to see how well this predicted the explosion of silly operators in some of the current languages. (Haskel and Scala, I'm looking in your general directions...) Second, the point is that all function calls now look the same. Both in serialized form and in parsed form. That is, the homoiconic nature is the point, no? To treat that as a somewhat byproduct is somewhat odd. They then go on to posit the use of meaningful whitespace. Something that is quite disgusting to me. It is dreadfully easy to mistakenly read whitespace. To the point that I do think programs are textual art, and care should be used to structure them in a pleasant and easy to read way. However, I cannot bring myself to like meaningful whitespace. YAML has given me enough headaches in life in a scant year, that I am pretty firmly on the opposite side of that fence now.
  - dwheeler 9y ago
    > They then go on to posit the use of meaningful whitespace. Something that is quite disgusting to me. Clearly not everyone agrees with this viewpoint, since Python depends on it and is extremely popular. But if you don't want meaningful whitespace, that's fine. We actually devised three notations, each one a superset of the previous ones: * curly-infix-expressions (c-expressions) * Neoteric-expressions (n-expressions) * Sweet-expressions (t-expressions) Only the last one (sweet-expressions) is whitespace-sensitive. More info here: https://readable.sourceforge.io/ https://readable.sourceforge.io/
    - RoboTeddy 9y ago
      This looks really nice! Are there any largish examples written with sweet-expressions? (Seeing large chunks of code could help with forming a gestalt impression)' Edit: found one - https://sourceforge.net/p/readable/code/ci/master/tree/src/sweeten.sscm https://sourceforge.net/p/readable/code/ci/master/tree/src/s...
- shakna 9y ago
  I've written a bit of Scheme in production. What I've found is that S-Expressions are unambiguous, and easy to learn, but Scheme doesn't railroad you with them. There's other options as well. A more recent project used the traditional syntax for macro-files. We seperated those out, a bit like C-header files, because it was easier for a macro-traceback library we created. Most of the main files were in Wisp, which decreased the learning time for our Pythonistas. Finally our hot-paths tended to be Cish. That is, they were compiled C at release, but Scheme with a C reader macro at development. (Based around Racket's c-lang). Of all of these, I prefer Scheme's traditional syntax, maybe with the curly infix extension for dealing with OO when I have to (like interfacing with Java). I know a lot that swear by Wisp, however. Finally, a lot of people like Cs syntax. I think syntax is something that people look for familiarity in, just as much as useability. Reducing cognitive load is important, and background is highly influential. For me, I've yet to see something beat S-Expressions. But I don't expect that can be true of everyone. I wish pluggable syntax appeared in a wider range of languages.
- gkya 9y ago
  It's kinda perfect. Sexps are readable, very easily and quickly navigable and mobile (i.e. moving some expression(s) around in the program source) w/ something like paredit, very easy to partially evaluate, parse, and they are easy to write. The complexity of the program is almost entirely contained within the tree of function calls instead of partly in the syntactic representations of the operations and literals. It's very easy to teach: we have lists, they contain symbols (i.e. names), numbers, strings (i.e. text), and other lists; symbols stand for themselves when quoted, or treated as variable names if not and evaluate to the values they name; if we don't quote the lists, they are function calls, the initial item must then be a name of a function, and the rest are arguments to that function. The entire program is made up of function calls, some evaluated at compile time, some run time. That is a fairly complete definition of a Scheme and CL like syntax. Furthermore, I find the Polish notation way of writing down mathematical expressions (albeit I seldom use them) as sexps is superior to the infix notation because any possibility of ambiguity is effortlessly dealt with. Basically there's no reason to further complicate a simple and useful thing when the complexity added does not offer substantial benefits while keeping those that the simpler solution offers.
  - viperscape 9y ago
    > any possibility of ambiguity is effortlessly dealt with "(+ 1)" is rather ambiguous and evaluates to 1, compared to "1 + ", which is very straight forward-- it's an incomplete expression and no evaluation can be done.
    - taeric 9y ago
      I'm curious how it is ambiguous. What two meanings do you see?
      - xapata 9y ago
        Perhaps the complaint is that there's a sort of cold-start problem -- it's not obvious that we're starting from zero. With addition, it's hard to imagine what else to start from, but perhaps starting from 1 would make sense in some contexts, where `(+ 1)` could evaluate to `2`.
- Shoothe 9y ago
  Rebol/Red have more readable s-expressions as their syntax but the drawback is more complex evaluation rules.
chowes 9y ago
Looks awfully similar to Mark
- brians 9y ago
  Canonical forms seem a big win. And teeny parsers.
  - dwheeler 9y ago
    There's always a trade-off. These parsers aren't very large anyway, in part because they are general (sweet-expressions, like S-expressions, aren't tied to any particular semantic).
nfoz 9y ago
Seems like this definition is tied to US-ASCII and that we'd need another spec (even if trivial) for any S-expressions that would intend to allow raw Unicode.

125 points by panic 9y ago

Is it impossible to improve on s-expression notation? https://srfi.schemers.org/srfi-110/srfi-110.html#cant-improve https://srfi.schemers.org/srfi-110/srfi-110.html#cant-improv...

yogthos 9y ago
The problem with these schemes is that they're at odds with metaprogramming. One huge advantage of s-expressions is that the code is expressed using data literals. You can take any piece of code transform it as you would any regular data and then run it. The biggest practical improvement that I've seen was Clojure notation that expands the number of data literals to include vectors, maps, and sets. I think this greatly helps with readability as it provides additional visual cues, while still preserving homoiconicity.
- kmill 9y ago
  > The problem with these schemes is that they're at odds with metaprogramming. One huge advantage of s-expressions is that the code is expressed using data literals. I don't think it is necessary for there to be a single uniform syntax for code to be able to fully leverage metaprogramming. Take for instance Mathematica (barring complexities of the evaluator itself...) The underlying type for almost everything in the language is the "expression," essentially a tagged list. The front-end language, called "standard form," can be converted to and from expressions. Expressions can more-or-less be directly serialized as "full form," which looks like McCarthy's M-expressions, and standard form extends this notation with operators and precedence rules. (Technically, standard form is given in a 2d graphical notation that is parsed into expressions, and "input form" is linear text. All the forms are interconvertible.) Programming in Mathematica seems to amount to writing lots of transformation rules for expressions, and it usually works out just writing the code you want to match against, but with pattern variables as holes. You are also free to write in full form for patterns if it helps make intent more precise. I think many cases of code transformation involve a pattern to match against. A language with few syntax classes and with metavariables can support metaprogramming easily enough. There are a few examples I've seen, and, although I can't remember the names, I think MetaOCaml was one. I guess what I'm saying is, so long as you make it so there is a "code literal," no matter the purported "homoiconicity" properties, you're good for metaprogramming. > while still preserving homoiconicity I think Alan Kay using the word "homoiconic" for Lisp was a mistake. The syntax of Lisp really is not the same as the internal representation, unlike the Tcl (which I understand actually executes by manipulating strings). This is a reason structured editors for Lisp don't seem to work out. Here is a new word: autoiconic ("self representing"). A language is autoiconic if there are composable code literals. It is not necessary for an autoiconic language to have "eval," but it is necessary to be able to read in code and then write out equivalent code. Furthermore, the code literals must allow for metavariables and composability: replacing a metavariable with a code literal must result in syntactically valid code when written. This excludes Javascript even though it has template literals. It is questionable whether Clojure is actually homoiconic, but it is arguably autoiconic since it has quasiquotation. (However, the way the quasiquoter works, a read/write cycle will result in code with a bunch of list manipulation functions. The supposed code literal disappears!)
  - kazinator 9y ago
    The problem with "homoiconic" is that it is about a storage mechanism: it says that function definitions are input into the image in a textual format and are stored in more or less that format so that they can later be recalled and edited. "homoiconic" languages can regurgitate their definitions. E.g. the set command in the POSIX shell, or LIST in classic BASIC. Those features are helpful interactively in that they allow a human to transform the code right inside the image by recalling, changing and reinstalling definitions. In Lisp, a data structure can be regurgited, rather than definitions. That is helpful in interactively debugging automated, rather than manual transformations. Moreover, the data structure is not regurgitated from a homoiconic form. It is isomorphic to the text in some way so that the data structure can be visualized from the text easily and vice versa. The programmer writes transformations which manipulate the data. These transformations take place in pipeline-like successive steps, where it is useful to intercept the process at different stages. The programmer of a homoiconic language doesn't do this; the programmer manipulates only the text. A BASIC programmer never works with the internal tokenized lines, for instance, in which a word like PRINT is condensed down to one byte. There is no access to that representation via any API from the language. Homoiconic languages don't place any transformation between the programmer input of a definition and the definition's storage; to do so would mean not to be homoiconic! ANSI Lisp has a very vaguely defined support for homoiconicity: the function ed which is intended to recall a function definition and allow the programmer to edit it. This feature is not very prominent; it is not the basis of Lisp interactivity. Almost every aspect of the function is implementation-dependent. To support ed, an implementation's defun operator has to store the un-expanded form somewhere.
    - kmill 9y ago
      This is a reasonable characterization of homoiconicity. Interestingly, by this definition, v8's implementation of Javascript is homoiconic since functions can be converted to strings, recovering the actual source text for its definition. I once took advantage of this to make a Smalltalk-like source editor for Javascript: http://tmp.esoteri.casa/grip/ http://tmp.esoteri.casa/grip/ (things might no longer work since I last was using it four years ago; I lightly edited it tonight to get it to start up without a file server. Only tested in Chrome!) It's based on an class-based object system I made that can serialize all of its class definitions. This drives both the class browser and the code serializer/saver. (Right now it has two code browsers because I was in the process of making a nicer one. Somehow, I had the idea that I was going to program a whole webapp with this thing, but I lost motivation.)
- cryptonector 9y ago
  Sweet-expressions are supposed to map easily onto lists, no? Anyways, there are other ways to do metaprogramming. Haskell manages without homoiconicity.
  - zimablue 9y ago
    As far as I know, Haskell's metaprogramming uses template haskell which works but isn't a super elegant/beautiful solution relative to lisp?
    - cryptonector 9y ago
      Metaprogramming is trivial when you have a) lazy evaluation, b) a very smart optimizing compiler. That said, I do love me the Lisp macro system, but homoiconicity alone is not that useful if the representation mechanism makes it difficult to denote lots of implied things (like type inferencing).
- dwheeler 9y ago
  > The problem with these schemes is that they're at odds with metaprogramming. Sweet-expressions (SRFI-110) support metaprogramming just fine. Sweet-expressions are general and homoiconic (just like S-expressions are), and they're backwards-compatible with traditional S-expressions as they are normally used. You're right that many other "readable" notations don't support metaprogramming, and I completely agree that most schemes are failures because of it. But once you agree that generality and homoiconicity are necessary, it's quite possible to create improved notations. I also think backwards compatibility is a (practical) must, but that is possible too. For more, see: https://readable.sourceforge.io/ https://readable.sourceforge.io/
- kbp 9y ago
  > The biggest practical improvement that I've seen was Clojure notation that expands the number of data literals to include vectors, maps, and sets. Common Lisp has literal syntax for vectors (and it wasn't the first Lisp to). Its standard representation of a set is just a list, but if someone were to add proper sets to the language they could add read syntax for them easily CL also has read syntax for maps (as has every Lisp) in the form of alists; it doesn't have literal hash tables, but those aren't terribly useful. Alists perform better for lookup for less than 20 or so keys (their writes are always constant-time), and they aren't going to be a bottleneck until you have at least several hundred keys, at which point you probably won't be writing those as literals in your source code. As well, alists have several other nice properties over hash tables, like not being tied to any equality predicate. Alists are a standard Lisp map with literal syntax that's been around since the beginning and are often preferable to hashes, but if you really did want hash literals specifically, it's a trivial read macro.
taeric 9y ago
This is a weak argument. Practically all languages compound symbols made from multiple characters, such as >=; there is no shortage of symbols. Also, nearly all programming languages have a function-call notation, but only Lisp-based languages choose s-expressions to notate it, so saying “we need function call notation” do not excuse s-expressions. I'm ironically going to complain that this is a weak rebuttal. For one thing, I find it hilarious to see how well this predicted the explosion of silly operators in some of the current languages. (Haskel and Scala, I'm looking in your general directions...) Second, the point is that all function calls now look the same. Both in serialized form and in parsed form. That is, the homoiconic nature is the point, no? To treat that as a somewhat byproduct is somewhat odd. They then go on to posit the use of meaningful whitespace. Something that is quite disgusting to me. It is dreadfully easy to mistakenly read whitespace. To the point that I do think programs are textual art, and care should be used to structure them in a pleasant and easy to read way. However, I cannot bring myself to like meaningful whitespace. YAML has given me enough headaches in life in a scant year, that I am pretty firmly on the opposite side of that fence now.
- dwheeler 9y ago
  > They then go on to posit the use of meaningful whitespace. Something that is quite disgusting to me. Clearly not everyone agrees with this viewpoint, since Python depends on it and is extremely popular. But if you don't want meaningful whitespace, that's fine. We actually devised three notations, each one a superset of the previous ones: * curly-infix-expressions (c-expressions) * Neoteric-expressions (n-expressions) * Sweet-expressions (t-expressions) Only the last one (sweet-expressions) is whitespace-sensitive. More info here: https://readable.sourceforge.io/ https://readable.sourceforge.io/
  - RoboTeddy 9y ago
    This looks really nice! Are there any largish examples written with sweet-expressions? (Seeing large chunks of code could help with forming a gestalt impression)' Edit: found one - https://sourceforge.net/p/readable/code/ci/master/tree/src/sweeten.sscm https://sourceforge.net/p/readable/code/ci/master/tree/src/s...
shakna 9y ago
I've written a bit of Scheme in production. What I've found is that S-Expressions are unambiguous, and easy to learn, but Scheme doesn't railroad you with them. There's other options as well. A more recent project used the traditional syntax for macro-files. We seperated those out, a bit like C-header files, because it was easier for a macro-traceback library we created. Most of the main files were in Wisp, which decreased the learning time for our Pythonistas. Finally our hot-paths tended to be Cish. That is, they were compiled C at release, but Scheme with a C reader macro at development. (Based around Racket's c-lang). Of all of these, I prefer Scheme's traditional syntax, maybe with the curly infix extension for dealing with OO when I have to (like interfacing with Java). I know a lot that swear by Wisp, however. Finally, a lot of people like Cs syntax. I think syntax is something that people look for familiarity in, just as much as useability. Reducing cognitive load is important, and background is highly influential. For me, I've yet to see something beat S-Expressions. But I don't expect that can be true of everyone. I wish pluggable syntax appeared in a wider range of languages.
gkya 9y ago
It's kinda perfect. Sexps are readable, very easily and quickly navigable and mobile (i.e. moving some expression(s) around in the program source) w/ something like paredit, very easy to partially evaluate, parse, and they are easy to write. The complexity of the program is almost entirely contained within the tree of function calls instead of partly in the syntactic representations of the operations and literals. It's very easy to teach: we have lists, they contain symbols (i.e. names), numbers, strings (i.e. text), and other lists; symbols stand for themselves when quoted, or treated as variable names if not and evaluate to the values they name; if we don't quote the lists, they are function calls, the initial item must then be a name of a function, and the rest are arguments to that function. The entire program is made up of function calls, some evaluated at compile time, some run time. That is a fairly complete definition of a Scheme and CL like syntax. Furthermore, I find the Polish notation way of writing down mathematical expressions (albeit I seldom use them) as sexps is superior to the infix notation because any possibility of ambiguity is effortlessly dealt with. Basically there's no reason to further complicate a simple and useful thing when the complexity added does not offer substantial benefits while keeping those that the simpler solution offers.
- viperscape 9y ago
  > any possibility of ambiguity is effortlessly dealt with "(+ 1)" is rather ambiguous and evaluates to 1, compared to "1 + ", which is very straight forward-- it's an incomplete expression and no evaluation can be done.
  - taeric 9y ago
    I'm curious how it is ambiguous. What two meanings do you see?
    - xapata 9y ago
      Perhaps the complaint is that there's a sort of cold-start problem -- it's not obvious that we're starting from zero. With addition, it's hard to imagine what else to start from, but perhaps starting from 1 would make sense in some contexts, where `(+ 1)` could evaluate to `2`.
Shoothe 9y ago
Rebol/Red have more readable s-expressions as their syntax but the drawback is more complex evaluation rules.

chowes 9y ago

Looks awfully similar to Mark

brians 9y ago
Canonical forms seem a big win. And teeny parsers.
- dwheeler 9y ago
  There's always a trade-off. These parsers aren't very large anyway, in part because they are general (sweet-expressions, like S-expressions, aren't tied to any particular semantic).

nfoz 9y ago

Seems like this definition is tied to US-ASCII and that we'd need another spec (even if trivial) for any S-expressions that would intend to allow raw Unicode.