I've been active on my "Ocean" programming language design project again and have created another point release which I am calling "Cataract Creek". It contains a number of changes but the most significant are functions and references (aka pointers) so that is what I'll discuss here.
I found as I was working on some of the design that these two really need to come together, or at least I needed some understanding of references before I could do anything useful with functions. This is because functions need some form of "by-reference" parameter to be really useful, and that means there must be some concept of references.
Yes, here it is over a year and a half since the last time I wrote about this, and I'm still working on it. Or maybe working on it again. But I really think I've got a much better solution this time. It certainly seems to be easier to work with.
I don't clearly remember the problems that I had with the previous design, but I do know that it seemed fragile and there was particularly some issue with not having a token that clearly closed a list of statements - like a '}' in C or "end" in Pascal. In any case I now have a new approach which is much simpler
It has been some years since I last wrote about about parsing with indents and line-breaks. Some of that time I've been distracted by other things, some of it has involved working on other areas of language design, but some of it has seen me struggling with line breaks again.
In my last note I had made significant progress over my original design, and there is much in that note that is still valuable. But some of it I got wrong too.
Most particularly, the idea that NEWLINES should be separators rather than terminators was mostly wrong. I now believe they must be mostly thought of as terminators, though there is one area where we must blur our definitions a little.
While I was writing test code for my first toy language I particularly noticed the lack of interesting data structures: to write interesting loops you can do a lot more if you can build data structures while doing it. So my second toy will begin to introduce data types. It won't be until a later iteration before we get structures though.
The first step to this is knowing how to declare variables, or local bindings. Then I'll have something to attach types of data structures too. So this installment is about local variables and their scope.
I started writing this 3 years ago and am only publishing it now. Sometimes life works like that. I had to wait until the code worked and I managed to lose interest for a while and get distracted by other things. At the recent linux.conf.au I went to a talk about the language "Pony". While I'm not thrilled with pony (I don't currently think that expressions and statements are interchangeable), the talk inspired me to get back to ocean... So what can we say about scopes?
Now that I have my general parsing worked out and understand how I want to use indents and line breaks to give a two dimensional structure to my language, I need to think about the details of some of the elements of the language. The part of a language that we use the most is the part which does stuff: statements and expressions. So that is where I will start, though particularly with statements.
In my earlier note about LR parsing I observed that many simple grammars will only ever have at most one REDUCE action in any given state. This means that there is no need for an "action table" to list which of several productions to reduce based on different look-ahead symbols. I even went so far as to say:
I personally cannot see why you would ever want a grammar which had two completed items in the same state. It means that some sequence of input tokens could be treated as one thing or as another depending only on what comes next. That sounds a like a design mistake to me. Maybe I'll eat my words later, but for now this means I cannot find a useful example - sorry.
I have since found some examples which shed valuable light on this issue and give me a chance to see how my words taste
In two previous articles I explored an approach to enhancing an LR parser to work with indents and line breaks. While I discovered some useful ideas and produced some code that seemed to work, I've subsequently discovered some serious flaws in the reasoning.
For indents, my reasoning about exactly when to REDUCE in the face of an OUT token was flawed and didn't properly address all cases. I've made a few updates to that article to highlight this failing. For linebreaks, I only talked about when they should be ignored and didn't cover the other important question of their role in terminating things. I hadn't at the time seen how important that was.
So now I want to rectify these problems and present a more complete solution. As I have explored around these problems I've seen other smaller issues and made a number of changes to my approach. The big picture is still much the same but some of the details are different in important ways. I also think I understand it all much better and so will try to explain things more clearly.
My previous note introduced the problem of parsing a two-dimensional language and the need to pay attention to indenting and line breaks and use them to guide the parsing of the language, both to enhance error detection, and to resolve ambiguity. The key intuitive insight which guides this investigation is that indents imply continuation while line breaks terminate things - sometimes.
That first note only looked in detail at indents. It provided rules by which a reduction in indent level can force the end of a syntactic unit by triggering a REDUCE operation in the LR parser. This note completes the solution by exploring and describing how line breaks can be interpreted when parsing a sentence in a two-dimensional language.
Many programming languages are essentially one dimensional. The parser treats them simply as a linear sequence of tokens. A program could all be written on a single line, or with each token on a separate line and the parser or compiler wouldn't notice the difference This set of languages includes Algol, Pascal, C, Rust and many others.
Some languages are 2-dimensional in a bad way. FORTRAN is probably the best example, though BASIC is similar. These (at least in their early forms) had strict requirements as to what can go on one line and what needs to go on a separate line.
A few languages are exploring the middle ground. Go will treat Newlines like semi-colons in certain cases which can result in a 2-dimensional feel, but brings with it some rather ad-hoc rules. Python probably makes the best attempt at 2-dimensional parsing of the languages that I have looked at. It allows newlines to terminate statements and also uses indents to indicate the grouping of some language elements, particularly statement groups.
While I find a lot to like in Python, it seems imperfect. I particularly dislike using a backslash to indicate line continuation. You can avoid this in Python by putting brackets around things as a newline inside brackets is ignored. But this feels like a weakness to me.
The recognition of a line-break as being distinct from other kinds of white space seems to be a clear recognition that the two dimensional appearance of the code has relevance for parsing it. It is therefore a little surprising that we don't see the line indent playing a bigger role in interpretation of code.
This note is the first part of a report on my attempt to translate my intuition about parsing the two dimensional layout into some clear rules and concrete code. This note deals with indents. A subsequent note will look at non-indenting line breaks.
It is time for another diversion, but it is leading towards the language design - honest.
LR grammars are a tool for specifying the grammar for a language, and it is fairly easy to automatically generate a parsing tool from a grammar. So they have often been used for this purpose.
There seems to be some suggestion that LR is no longer to tool of choice (see wikipedia - since redacted), apparently because it is hard to do good error reporting. The gcc compilers converted from an LR grammar to a recursive descent LL grammar, apparently for this reason.
However I like LR grammars and I don't see the problem. So I plan to start out with an LR grammar approach. Either it will work well, or I will start the see the problem, and either outcome in positive in my view. So I cannot lose.
