For a while I have been trying to design a nice Lisp-based syntax for Hel, trying to fit things like type information and default arguments in function definitions, devising a good syntax for object properties, etc., but never being satisfied with what I come up with. So a few days ago I decided to try something else entirely: to devise a non-Lisp syntax while maintaining a similar level of flexibility to define new language constructs. And I think I have come up with something quite palatable, though there are a few open problems to solve.
The idea is not entirely new. I know of at least Elixir, which is homoiconic but has more variety/flexibility in its syntax, though it has a bunch of hardcoded reserved words; and Dylan, which seems to have a pretty complex macro system, though maybe a little more complex than I'd wish. My non-Lisp Hel syntax has a bunch of hardcoded symbols (( ) [ ] { } , ; and newline), and the syntax for numbers and identifiers is hardcoded too (but that is hardcoded even in Lisp, though Common Lisp has reader macros to overcome this problem to an extent), but there are no reserved keywords, and I find it easier to read and analyze than Dylan. I hope you like it too (though feel free to comment in any case).
if x > 0 {
print("foo")
return x*2
} else {
print("bar")
return x*3
}
That looks like a pretty regular language, but the magic here is that none of the "keywords" is hardcoded. This is interpreted as a command if with the four arguments x > 0, the first block, else, and the second block. It is up to the operator/macro bound to the variable if to decide what to do with these arguments.
There are some caveats here, the most notable one being that the else must appear in the same line as the closing brace of the first block, otherwise it would be interpreted as an independent command rather than a part of the if command. I think this is an acceptable price to pay for the flexibility of not having a limited, hardcoded set of commands.
The central component of the syntax is the command, or perhaps more precisely the phrase, since "command" gives the impression of a separation between statements and expressions which does not really exist in the syntax. A phrase is a sequence of space-separated constituents. A constituent is one of:
The arguments of a function call, indexing operation, parenthesized expression, and the elements of tuples and arrays are themselves phrases (i.e., you can have an if inside a function call).
Parsing of constituents is greedy. When looking at a series of tokens such as if x > 0 { ... } and trying to determine where a consituent ends and the next one starts, the parser will consider each consituent to be the longest sequence of tokens from left to right that can be validly interpreted as a constituent. In this example:
Phrases are separated by newlines or semicolons. To avoid the effect of a newline, a \ can be used at the end of the line (as in Python). Within parentheses or brackets, newlines are ignored (also as in Python).
That's pretty much all there is to it, in general lines. Except...
An operator is any sequence of one or more of the characters ! @ $ % ^ & * - + = : . < > / ? | ~. So + and * are operators, but so are ++ and |> and @.@.
One open problem with this syntax is how to handle operator precedence in a general way. In my current prototype, I have hardcoded the precedence of the arithmetic operators, but I need to have sane precedence rules for user-defined operators.
One way is to allow the user to specify the precedence for custom operators (like the infixl and infixr declarations in Haskell). The problem is that this means a program cannot be parsed without interpreting the fixity declarations, which I find annoying, especially given that operators can be imported from other modules, and being unable to parse (read in Lisp parlance) a program without compiling the dependencies is deeply annoying from a Lisp perspective. Another problem is that it is not only hard to parse for the parser, it's hard to parse for the human too.
Another way is to have a fixed rule to assign each operator a precedence. I remember seeing a language once which gave each operator a precedence based on its first character (so, for example, *.* would have the same precedence as *). [Update: I don't remember which language it was, but it turns out that Scala does the same.] I like this solution a lot because it's easy for the human to know the precedence of an operator they've never seen before. The problem is reconciling this with the natural precedences expected from some operators (for instance, = and == usually have different precedences). I still have to think about this. Suggestions are welcome.
[Update: Maybe it makes more sense for the last character to determine precedence, since we want things like += to have the same precedence as =. On the other hand, an operator like => makes more sense as having the same precedence as = than >. Don't = and > have the same precedence anyway, though, since == and > do?]
The consituent parsing rules may cause some surprises. Consider the following example:
let answer = if x > 0 { 23 } else { 42 }
In principle, this looks like assigning the result of the if to the variable answer. However, the parsing rules as stated above will lead to this being parsed as the sequence of constituents:
which is not quite what was intended. To use the if expression (which is a whole phrase, not a constituent) as the right-hand side of =, one would have to surround it with parentheses.
The arguments of a function call are phrases, not constituents, so an if expression can appear as the argument of a function call without having to surround it with an extra pair of parentheses on the top of those already required by the function call. But function arguments are delimited by commas, so, to avoid ambiguity, commas are not allowed to appear outside parentheses. For example, you cannot have a command like:
for x, y in items { ... }
because in a function call like:
f(for x, y in items { ... })
it would be ambiguous whether this is a single argument or two. The solution is to require:
for (x, y) in items { ... }
instead.
This also means that import foo, bar must be import (foo, bar) instead, though this limitation might be lifted outside parentheses.
A space cannot appear between a function and its argument list. The reason is that we don't want for (x, y) in list to be interpreted as containing a function call for(x, y), nor do we want for x in (1, 2, 3) to be interpreted as containing a call in(1, 2, 3). I don't typically write spaces between a function and its arguments anyway, but I feel ambivalent about this space sensitivity. Perhaps the most important thing here (and in the above gotchas as well) is to have good error messages and (optional, on by default) warnings when things go wrong. For example, upon seeing something that might be a function call with a spurious space inside:
foo.hel:13: error: `foo` is not a command foo.hel:13: hint: don't put spaces between a function and its argument list 13 foo (x, y)
This might be harder for the macros (e.g., for identifying that the call in(1, 2, 3) it received as argument was meant to be two separate constituents), but I think it can be done, especially for rule-based macros (as opposed to procedural ones).
A different solution is to get rid of tuples entirely and use for [x, y] instead, except this does not really solve the problem because this is ambiguous with the indexing operation.
I already have a prototype parser, but it's pretty rough, and I still have to work on the interpreter, so I have not published it yet. If you have comments, suggestions, constructive criticism, or two cents to give, feel free to comment.
2019 might just be the year of Hel on the desktop. I mean, not really, but I would like to talk a bit about my prospects for Hel going forward.
For those who don't know, Hel (huangho's Experimental Language/Lisp) is my playground for experimenting with programming language design and implementation ideas. The Hel 0.1 compiler was a very crude translator from a simple Lisp-like language to C, similar in spirit to lows. Hel 0.2 was a bit of an improvement, in that it at least had the rudiments of an intermediate representation. The goal for Hel 0.2 was to be a superset of a subset of R5RS Scheme (i.e., Hel and R5RS would have a common subset), and the compiler itself would be written mostly in this subset; the idea was to eventually be able to compile the Hel compiler with either a Scheme implementation or with the Hel compiler itself, thus bootstrapping the language (i.e., being able to compile the compiler with itself).
My goals have changed a bit, though. First of all, I'm now interested in exploring more the language side rather than the implementation side of the project. I think an interpreter might serve my goals better than a compiler, since it is easier to change and test ideas. The compiler can come later.
Second, I'm not so keen anymore in having a large common subset with Scheme. Multi-shot continuations (call/cc) have always been out of the subset, but as of late I'm willing to question things as basic as cons cells. I may not get that far away from Scheme, but when exploring design options I definitely don't want to be constrained by compatibility. So bootstrappability can come later too.
Third, because I want to write an interpreter, but I don't want it to be terribly slow, I'll probably be switching implementation platform. So far I had been doing development on GNU Guile, but I'll probably switch to either Chez Scheme (a pretty fast R6RS Scheme implementation), or SBCL (a pretty fast Common Lisp implementation). SBCL has the advantage of having more libraries available (and Common Lisp itself is a larger language than that provided by Chez), while Chez has the advantage of being (in principle) closer to Hel (although that's kind of moot if bootstrapping is not an immediate goal anymore). I thought SBCL would also be faster than Chez, but in my highly scientific benchmark (running (fib 45) on each implementation), Chez is actually faster out of the box, though SBCL is faster if type declarations are provided.
So what are my goals for Hel 0.3? Well:
Implementation-wise, one of my major goals is debuggability. I want to have a Lisp which can give proper stack traces, with proper line numbers, in the presence of macros, and show function arguments in the stack trace.
Language-wise, I want:
Optional types, with a lightweight syntax for type declarations;
Explicit indication of mutability, with more things immutable by default (strings, lists). Mutability is an always-present part of APIs in Scheme and Common Lisp (both language standards are very explicit in describing data sharing between function arguments and results, which values can or cannot be mutated, etc.); I think this really ought to be more explicit in the data types themselves. I have described a proposal for handling mutability before, but nowadays I'm more inclined to simply have mutable and immutable variants of lists, dictionaries and such; it's less elegant but easier to implement and use efficiently. We'll see how this goes. The important thing is to make mutability explicit in the data types (and their printed representation).
A concise notation for declaring and using new data types, reading and printing them, doing pattern matching, reflection, etc., to reduce the temptation to Use Lists For Everything™.
There are other things (some of which I intend to write about in the future), but I think these are the most important ones.
Wish everyone a happy new year, and may our living-dead open source projects thrive in 2019.
Copyright © 2010-2024 Vítor De Araújo
O conteúdo deste blog, a menos que de outra forma especificado, pode ser utilizado segundo os termos da licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International.
Powered by Blognir.