Also, read http://this-plt-life.tumblr.com/ and don't take yourself too seriously. Stand on the shoulders of giants and continue reaching for the sky. Languages are super fun.
A programming language is the semantics and without a strong notion of those semantics and the interactions you end up with confusion and difficulty. For an example one need look no further than Ruby's "implementation as specification" crazyness.
I won't go as far as to say that all language creators should adopt operational semantics when building a language, but if you're serious about it then you should at least investigate the process.
https://github.com/D-Programming-Language/dmd/blob/master/sr...
https://github.com/D-Programming-Language/dmd/blob/master/sr...
There's a lot of detail there, but the operation of both is straightforward.
With some work anyone can learn the material. It's not as simple as reading a blog post unfortunately, but you'll have a much deeper understanding of what it means to build a programming language.
I'm also reading the more recent Practical Foundations for Programming Languages by Robert Harper. It's written for a similar audience.
I would recommend both.
One reason I think that is because syntax helps develop conventions and make them obvious. If everything is an s-expr and you can do absolutely anything with macros anywhere, then two programmers might not really be able to communicate even if they are technically using the same language.
Macros are pretty much like Classes, Gotos/Loops, Exceptions, Functions, etc in this respect, the communities have mostly agreed on conventions _when_ and _how_ to use them.
I think the argument that macros will make a codebase unreadable to other programmers is largely an exaggeration to turn a pro-Lisp argument against Lisp. Its a pattern I have heard a little too often:
"C++ is powerful" -> "C++ is too powerful"
"Macros let you express ..." -> "Macros can do just too much"
So next time when you criticize macros, talk about something that is worth debating, like the fact that they can be unsafe (hygiene), they are not intuitively writable like functions, they might make debugging harder, etc.
Macros in the hands of an intermediate-to-experienced programmer are powerful tools. They remove patterns from your code. They allow you to modify the compiler to efficiently run your program. And all sorts of good things.
People arguing that X "is too powerful" are saying that nobody needs a combine harvester when a team of farmers with scythes will do.
Who is arguing that?
I wasn't criticizing macros; I claimed that they don't give you much guidance to any particular convention because you can do anything.
A language without conventions is incomplete, so you need to do something active to bring the conventions about. In other words, the designers of lisp leave conventions as an exercise for the reader and really offer no guidance from the language itself.
Clojure and racket are trying to address that, which is good. I've played around with them a bit, generally found them pleasant, and I hope they succeed (though I did not find anything that would compel me to actually use them for the kinds of things I work on).
It's interesting that you bring up C++. I wonder what your feelings are about people who prefer C over C++?
Guidance in a language is a hard thing to do right. I think the only reasonable way of guidance is to make good coding practice simple, limiting guidance is often quite bad [1], because while in a lot of cases it makes things easier, there are those cases where you then have to work around the limitations and this is when you get those "bug ridden incomplete implementations" of that "liberal" language.
Which good guidances from which programming languages are you fond of?
[1] now that I think about it, I do like immutability in functional programming languages - a not-so-liberal thing..
d = {}
d[key] = value
(set! d (make-hash-table))
(hash-table-put! d key value)easier to read than d = {} d[key1] = value1 d[key2] = value2 d[key3] = value3
So syntax matters, but it's not obvious which syntax is best.
Parsers are far from harmless pieces of logic you can just throw together. And not just because they take time to write - parsers are physically dangerous. Compiler writers develop incipient carpal tunnel syndrome trying to write parsers.
When you finish writing a parser as a language designer the problem of writing a parser for the language doesn't go away. The programming language users might want to apply transformations to source code written in the language -- which now means they need to write brand new parsers from scratch to do these transformations.
What s-exprs give you instead is the option to write a "parser" in one function call: using the read function. It doesn't get shorter than that.
Now, that's a parser that's easy to write.
edit: rewording
If you understand abstract languages, writing a recursive descent parser is a simple, paper and pencil exercise.
If you don't understand abstract languages, you should not be designing a language till you stop and learn them and you should STFU about what people designing languages should do until then.
Have you ever written a recursive descent parser for C?
I realize now what was inaccurate about what I wrote. It's that the things you have to do after you parse might be the more harmful parts. Processing the parse tree you get back.
edit: rewording
Instead, when you create a recursive descent parser, you create a series of functions called whenever a syntax element is discover. In these functions, you construct whatever your final data structures are going to be.
Of course, you still can create and return a full abstract syntax tree but one nice thing about recursive descent is that if you are only going to do a few things, you can just have those few operations in your parser and be done with it.
Even that might be overkill, though: a generic operator parser for unary, binary, ternary, n-ary, and so on will take about 50 lines of code. You can encode a surprisingly large number of control structures with a cleverly crafted precedence parser.
http://tratt.net/laurie/blog/entries/parsing_the_solved_prob... ltu discussion http://lambda-the-ultimate.org/node/4489
Really, they are easy. They are literally insignificant when you factor in all the hours you'll work on a language.
I wrote another one recently for a small side project. It took more time to write the unit tests for it. The parser practically wrote itself.
I'm egalitarian inasmuch as I believe every serious programmer ought to implement some sort of toy language at some point, but I'm not so stupid as to think that this is a good idea at all phases of a programmer's development. Beginners should concentrate on other basic tasks, even low-intermediate really should too. I wouldn't reserve this task for "experts" though, because this is one of the big steps in moving from intermediate to expert. (Anyone who has assembled the skill set to implement a toy-but-nontrivial language has assembled the skill set to accomplish a very wide variety of programming tasks. If I were interviewing someone and they could demonstrate this, I would almost entirely cease to care what actual languages or frameworks they may have worked in.)
Right, but if you just hand-write a recursive descent parser, you won't have to deal with shift-reduce conflicts. Dangling elses are trivial to solve. The nice thing about hand-writing a parser is that it lets you learn one new thing (how to implement a parser for a grammar) while taking advantage of what you already know (how to write, run, test, and debug code in some existing language).
Throwing a parser generator at someone means they end up learning the weird vagaries of that generator instead of focusing on their own language. Meanwhile, the resulting generated code is nigh-unreadable, so all of those debugging skills and nice IDE they have go to waste.
Do you know of any strategies for error reporting, or of tools that implement? I'm always on the lookout for cleaner approaches to this.
Not really.
Seriously, if you're going to get bogged down trying to get the lexer/parser to work, you're not ready to work on a full blown language/compiler. Lexing/parsing is the EASY part, as in a minute, insignificant part of the time you'll invest in the project. I really do mean that.
I'm genuinely interested by your comment. If I'm interpreting it correctly, you seem to be claiming that ensuring corner cases are handled correctly, testing, and maintaining a parser require a trivially small amount of work. What do you use to build your parsers?
I use a text editor.
Using a coverage analyzer is adequate for evaluating the thoroughness of the tests.
Yes, it all is a trivially small amount of work compared to the rest of a language project (and even compared with the rest of the compiler). You'll spend much more time just trying to figure out how to convert floating point values to strings.
I should hope not, since the source code to printf() should have pretty much the complete answer to that!
And yes, I did have to do my own float => string implementation.
One is that there is a big difference between writing a parser for a language you are inventing and writing a parser that is attempting to implement an existing language. Languages have lots of corner cases; if you are inventing the language then every quirk of your parser is correct by definition. You might not even be aware of some of the subtle choices that your hand-written parser is making.
As an example, of this, it was not discovered that ALGOL 60 had a "dangling else" ambiguity in its grammar until it after had been implemented, used extensively, and even published in a technical report. It was essentially an accident of the implementation that it resolved the ambiguity in the way that it did. So while it might not be too much work to "get the lexer/parser to work", it doesn't follow that all of the issues around parsing are trivial. There is still a lot of complexity and subtlety around parsing if you're trying to design something that could reasonably have multiple interoperating implementations.
Secondly, there is a very very seriously wide variation of lexical/syntactic complexity between languages. You can pretty easily write a 100% correct JSON parser in an hour or less (possibly much less, depending on what language you choose to write it in). On the other hand, it takes man-years to write a 100% correct C++ parser (not least because C++ tightly couples parsing and semantic analysis). Now I know this article is more talking about designing your own language, and no language will start out as syntactically complicated as C++, but empirically most of the languages we actually use have a fair bit of complexity to them, so delivering the lesson that lexers/parsers are easy in general is, I think, the wrong message to be sending.
Thirdly, there are a lot of practical considerations that can make parsing more complex. For example, take Steve Yegge's attempt to do some incremental parsing (from http://steve-yegge.blogspot.com/2008/03/js2-mode-new-javascr...):
I had two options: incremental parsing, or asynchrous
parsing. Clearly, since I'm a badass programmer who can't
recognize my own incompetence, I chose to do incremental
parsing. I mentioned this plan a few months ago to Brendan
Eich, who said: "Let me know how the incremental parsing
goes." Brendan is an amazingly polite guy, so at the time I
didn't realize this was a code-phrase for: "Let me know when
you give up on it, loser."
The basic idea behind incremental parsing (at least, my
version of it) was that I already have these little
functions that know how to parse functions, statements,
try-statements, for-statements, expressions,
plus-expressions, and so on down the line. That's how a
recursive-descent parser works. So I figured I'd use
heuristics to back up to some coarse level of granularity —
say, the current enclosing function – and parse exactly one
function. Then I'd splice the generated syntax tree fragment
into my main AST, and go through all the function's siblings
and update their start-positions.
Seems easy enough, right? Especially since I wasn't doing
full-blown incremental parsing: I was just doing it at the
function level. Well, it's not easy. It's "nontrivial", a
word they use in academia whenever they're talking about the
Halting Problem or problems of equivalent decidability.
Actually it's quite doable, but it's a huge amount of work
that I finally gave up on after a couple of weeks of effort.
There are just too many edge-cases to worry about. And I had
this nagging fear that even if I got it working, it would
totally break down if you had a 5,000 line function, so I
was kinda wasting my time anyway.
So, hand-created parsers may not flag ambiguous grammars and automatically generated parsers might (I've only done hand created parsers so I don't know).
And Steve Yegge quote just shows how much abstract languages are something you need to learn rather than something you can power your way through. And plenty of good programmers can power their way through almost any other kind of programming challenge so someone who seems very smart doing a very dumb thing in parsing doesn't surprise me (I've tried that myself).
> delivering the lesson that lexers/parsers are easy in general is, I think, the wrong message to be sending.
I stand by the message :-) in the sense that if a person finds lexing/parsing to be hard, they're likely to find the semantic/optimization/codegen parts of the compiler to be insurmountable.
I've written compilers for numerous languages, including C++, including 2 languages I invented, and lexing & parsing is just not that hard relative to the rest of a compiler.
The ones coming out of the parser aren't that hard to do.
Offhand, I'm not aware of any real-world language with lots of users that has a generated parser.
The programming language users might want to apply transformations
to source code written in the language -- which now means they need to
write brand new parsers from scratch to do these transformations.
I use Haskell and Clojure happily.
Sounds like petty nonsense to me.
While using s-expressions is obviously the right thing to do if you are writing your compiler in some dialect of Lisp, it may not be the best choice if using another language.
In particular, I have past experience from writing several toy programming language interpreter and compiler prototypes in Haskell. Representing the abstract syntax tree with a tree structure and sum types is easy and convenient and writing the actual parser (using e.g. Parsec) is trivial and doing a pretty printer isn't hard either (using Hughes-PJ pretty printers).
If you have not tried it, I recommend doing a small programming language prototype in Haskell. It's a very good exercise and really fun.
But your argument about this having to do with what compiler one is using doesn't make sense to me. S-expressions are easily parseable in virtually any language. S-expressions are always going to be one short-cut around the problem of deciding what syntax your language should have (my object is this short-cut may not help your language in the end - your S-expression language will be considered less-than-understandable by the same reasonably large group of people who consider LISP less-than-understandable).
For example, Google give this complete lisp interpreter in c:
http://www.umcs.maine.edu/~chaitin/lisp.c
Haskell may have facilities that make parsing any language reasonably easy, sure. But I have news, parsing language is easy once you learn a bit anyway.
Representing tree structures like abstract syntax trees is really easy and convenient in Haskell. The traditional example, curried λ-calculus with integers looks something like this:
data Expr =
Constant Int |
Identifier String |
Application Expr Expr |
Lambda String Expr
It is also easier to write a parser and pretty printer (using Parsec and Pretty combinators) to convert that tree structure to/from human readable/writable strings (ie. program source code) than it is to convert s-expressions to such a tree structure.
So while using s-expressions is certainly possible, in a nicely typed language like Haskell, it will be nicer to have a proper syntax tree data structure and the advantages of s-expressions are not really there unless you are writing an interpreter for a homoiconic language like Lisp or Prolog.
The way I usually start a programming language project (I do lots of those) is writing "programs" by specifying syntax trees for test cases in Haskell using literals and then running them through the interpreter/compiler/type checker. Only when I have something that actually works (and developing and debugging by writing the tree structures becomes unwieldy), I start thinking about the syntax and write the parser and pretty printer.
So if you're using a host language other than Lisp to implement your compiler/interpreter and your source language isn't homoiconic, using s-expressions as your internal program representation might end up being unwieldy. The syntax of your source language is pretty much irrelevant in this discussion, but writing a proper parser to produce tree structure might make sense rather than reading s-expressions.
Does my explanation make sense to you? If you have any questions, don't hesitate to ask.
Here's a few of my toy language projects for your enjoyment, you'll find examples of the things discussed above there:
https://github.com/rikusalminen/funfun LLVM compiler for a toy functional programming language (with type inference!)
https://github.com/rikusalminen/slolog Prolog-esque logic programming language
Well, parsing S-expressions is easy in most language. Unless somehow parsing an S-expression is hard in Haskell, it doesn't matter whether parsing easier. Normally, it just means both S-expressions and generic parsing is easy.
Your overall argument could better be written "S-expressions aren't part of the particular syntax transformation method I use." OK, sure.
An S-expression based interpreter is still pretty darned easy to write (unless Haskell has weird barriers that other language don't have, if so, it doesn't reflect well on Haskell).
> An S-expression based interpreter is still pretty darned easy to write (unless Haskell has weird barriers that other language don't have, if so, it doesn't reflect well on Haskell).
Oh, I knew I was too Haskell-centric in my answer because you missed my point entirely.
You can write an S-expression parser in Haskell, it's just as easy as writing it in any other language. But this wasn't the point at all.
Using S-expressions as the program internal representation just doesn't make sense in Haskell. You can do it and you should do it if implementing a Lisp dialect or other homoiconic language, but in general, it's a lot better to build a proper tree structure. The major advantage of s-expressions in the Lisp world is not really the syntax, but it is an universal tree structure.
Same thing applies if your host language isn't Lisp and you have a proper abstract syntax tree structure (either enums + unions or a class hierarchy or whatever). You can parse s-expressions but you need an extra step to get into the tree structure you're going to be using internally.
Your impression that S-expressions are hard in Haskell is just incorrect, my point was that there are better facilities for tree structures and parsing than S-expressions are.
As I said first thing in the earlier post... my argument isn't really about syntax, it's about the internal program representation.
And if you really want to dive down that rabbit hole I think you have to establish that prefix is better than suffix as well. I'm somewhat dubious of even this claim, since I find suffix easier to reason about. But maybe that's just me.
I think looking at pros and cons (in the abstract and in people's heads) of prefix vs. suffix could be interesting. What I like about suffix is that you can treat it as a stack. What I like about prefix is that I know what kind of node I'm building as I consider the arguments. I've not done enough of either to have much opinion on which matters more (some lisp, some rpn calculators, but not enough). I certainly wasn't agitating for prefix (in particular) above.
Note that English itself is an infix language: "Bob likes Clara" (SVO, infix), rather than "Likes Bob Clara" (VSO, prefix) or "Bob Clara likes" (SOV, suffix). A cursory search tells me SVO and SOV cover 75% of all languages. It would be interesting to see if people speaking SOV languages would prefer suffix notation. I would expect common patterns in (unrelated) world languages to loosely mirror natural dispositions towards syntax. In practice, that's probably a hodge podge of prefix, suffix and infix depending on whether you're dealing with verbs, connectives, prepositions, etc.
Of course, usually there's an implicit subject (receiver): this or self. In a language like ruby, which is very very object oriented, and has a similar thing where you always have a receiver to any function call, every instance has a certain set of stuff (the Kernel module) mixed into it that allows for general tasks to be treated as an implicit receiver. It works pretty well for solving this problem on the other side.
Take for example a common prefix notation: (< a b c d) this stands for "are all increasing?"
Since none are really the subject, most Java-like languages (if they had this at all) would have to invent a subject Integer.areIncreasing(myList). No longer does this give you a valuable subject, just a made up subject.
Certainly some operations (mostly arithmetic) are easier on the eyes since we've had a lot of practice with it.
Whenever I do arithmetic, I use threading macros to make it easier to read. Suddenly, it reads like infix, but with more flexibility.
(+ 4 (- 1 (/ 4 2))) ;; what?!
becomes
(_> 4 (/ _ 2) (- 1 _) (+ 4)) ;; ah
In infix, it would be:
(1 - (4 / 2)) + 4
The threading macro isn't quite as nice as the default infix, but it allows for both notations.
I think the second reads very well all things considered, start with 4, divide by 2, subtract from 1, add 4. (_ is the placeholder).
Re your example with <, the 'natural' object oriented way to do this to me would be to treat the list itself as the subject. [a,b,c,d].isOrdered() say. To the fact that doing it this way in java would be incredibly ugly, I'll only say that I'm not even remotely a fan of java or, for that matter, C++/Java/C#-style static-typed object-orientation.
As to the are increasing, yes, I suppose the list itself would be a more natural subject.
This is why I love macros, not really infix or prefix specifically, because a macro makes it trivial to just have this:
(. [1 2 3 4].isOrdered)
turn into this:
(isOrdered [1 2 3 4])
That way both the human and the compiler get their preferred view.
When you're dealing with human interfaces, existing convention counts enormously.
There is a reason we don't program in English, and keep inventing new programming languages. English is poor and ill suited for the problem, even though it has enormous existing convention.
Wait, if you say "just don't do it, learn LISP instead and just customize your stuff", well that is good advice, OK.
Still, learning real language construction tools is a cool thing. It's mainly cool in the long, miserable, thankless journey way the article describes yes. But beautiful still. Nice syntax the way human like to read has had a long, successful history. But LISP has had it's moments too...
This also means that there can be multiple concrete syntaxes for a language: e.g. for Python, you can use the standard syntax, but you could also use s-expressions, without changing the semantics one bit.
I wouldn't call it jumping through hoops though. Rather, for me, it's a natural consequence of separation of concerns. I try to build parsers that only know about concrete syntax. A later pass over the CST is responsible for building the AST, which prevents coupling of the parser to the abstract syntax.
YMMV. There's more than one way to skin this cat.
s-Expressions are not the same as LISP sure but I don't think you can say they are orthogonal either. They are a key aspect.
Sure, you can have a non-LISP s-expression language but the boundary between this and a subdialect of LISP is going to be porous.
The strengths and the weaknesses of LISP, as far I can see, come because it is so easy to just create a mini-language, a sub-dialectic to do this and that.
I'll assume people know the strengths (and I'm the one say them most eloquently), I'd mention simplicity, flexibility, recursion, homoiconity, etc.
I'd say the weaknesses "easy wheel reinventing", which has resulted in many half-formed wheels and few canonical wheels.
So to get back to syntax, what's nice about a "strong clear" syntax like infix math or c-style function declarations is that they make purposes clear and make boundaries clear. The useful of designing a "real language" is doing that. You can do everything with s-Expression but if it just your new language for doing X, you'll putting forward your purpose in a loose, flabby way. If you expression-language isn't going to be just rolled into LISP, it will just have all the weaknesses and of the strengths of LISP.