An exercise in Language Design

When I was doing my honours year in Computer Science (UNSW, 1986) I wanted to design a new programming language.  That would be a rather large project for an honours year and naturally it didn’t happen.  I have remained interested in languages, though for most of the time that interest has been idle.

I recently wrote some articles about languages for LWN and that has re-awoken my interest in language design.  While I had scribbled down (or typed out) various notes about different ideas in the past, this time I seem have have progressed much further than ever before.  It probably won’t ever amount to much but I’ve decided to try to continue with the project this time and create as concrete a design and implementation as I can … in my spare time.

As part of this effort I plan to write up some of my thoughts as blog entries, and publish some source code in a git tree somewhere.  This note is the first such entry and it presents the high level design philosophy that I bring.  Undoubtedly this philosophy will change somewhat as I progress, both in clarifying the ideas I present here and in distilling new ideas from all the reflection that will go into the design process.  I’ll probably come back and edit this article as that happens, but I’ll try to make such changes obvious.

Philosophy

I see two particular goals for a language.  This first is  allow the programmer to express their design and implementation ideas clearly and concisely.  So the language must be expressive.  The second is to prevent the programmer from expressing things that the didn’t mean to express, or which they have not thought through properly.  So the language must be safe.

There are a number of aspects to being expressive.  Firstly, useful abstractions must be supported so that the thinking of the programmer can be captured.  “useful” here is clearly a subjective metric and different abstractions might be useful to different people, depending on what they are familiar with.  Some might like “go to”, some might like “while/do”, others might like functions applied to infinite sequences which are evaluated lazily.  The language I produce will undoubtedly match my own personal view of “useful”, however I will try to be open minded.  So we need clear, useful abstractions.

The “what they are familiar with” is an important point.  We all feel more comfortable with familiar things, so building on past history is important.  Doing something in a different way just to be different is not a good idea.  Doing it differently because you see an advantage needs to be strongly defended. Only innovate where innovation is needed, and always defend innovation clearly.  When innovation is needed, try to embed it in familiar context and provide mnemonic help wherever possible.

Being expressive also means focussing on how the programmer thinks and what meets their needs.  The needs of the programmer are primary, the needs for the compiler are secondary.  Often it is easier to understand a program when the constructs it uses are easy to compile – as there is less guesswork for the programmer to understand what is really going on.  So the needs of the compiler often do not conflict with the needs of the programmer.  When they do it is probably a sign of poor language design which should be addressed.  If no means can be found to improve the design so it suits both programmer and compiler, then the needs of the programmer must come first.

A key element of simple design is uniformity.  If various features are provided uniformly then the programmer will not be forced to squeeze their design into a mismatched mould in order to use some feature – the feature will be available wherever it is needed.  The  most obvious consequence of this is that built-in types should not have access to any functionality that user-defined types do not have access to.  It should be possible to implement any built-in type in the language rather than having to have it known directly to the compiler.

The are probably limits to this.  “Boolean” is such a fundamental type that some aspects of it might need to be baked in to the language.  However wherever that sort of dependency can be reasonably avoided, it should be.

The second gaol is preventing mistakes, and there are many aspects to this too.  Mistakes can be simple typos, forgotten steps, or deep misunderstanding of the design and implementation.  Preventing all of these is impossible.  Preventing some of them is easy.  Maximising the number of preventable errors without unduly restricting expressiveness is the challenge.

An important part of reducing errors is making the code easy to read.  In any writing, the practice of writing a first draft and then reviewing and improving it is common.  This is (or should be) equally true for writing a computer program.  So when reading the program, the nature and purpose of the algorithm and data should stand out.  The compiler should be able to detect and reject anything that might look confusing or misleading.  When reading code that the compile accepts, it should be easy to follow and understand.

This leads to rules like “Different things should look different” and “similar things should look the same”.  The latter is hopefully obvious and common.  The former could benefit from some explanation.

There seems to be a tendency among programmers and mathematicians to find simple models that effectively cover a wide range of cases.  In mathematics, group theory is a perfect example.  Many many different mathematical structures can be described as “groups”.  This is very useful for drawing parallels and for understanding relationships and deep structure.  However when it is carried across from mathematics to language design it does not work out so well.

For me, the main take away from my article – linked above – “Go and Rust – objects without class”, is that “everything is an object” and the implied “inheritance is all you need” is a bad idea.  It blends together different concepts it a way that is ultimately unhelpful.  When a programmer reads code and sees inheritance being used it may not be clear which of the several possible uses of inheritance is paramount.  Worse: when a programmer creates a design they might use inheritance and not have a clear idea of exactly “why”  they are using it.  This can lead to muddy thinking and muddy code.

So:  if things are different, they should look different.  Occam’s razor suggests that “entities must not be multiplied beyond necessity”.   This is valuable guidance, but leaves open the interpretation of “necessity”.  I believe that in a programming language it is necessary to have sufficient entities that different terminology may be used to express different concepts. This ensures that the reader need not be left in doubt as to what is intended.

Finally, good error prevention requires even greater richness of abstractions than clarity of  expression requires.  For the language/compiler to be able to catch errors, it must have some degree of understanding as to what is going on.  This requires that the programmer be able to describe at a rich level what is intended.  And this requires rich concepts.  It also requires complete coverage.  If a programmer uses clear abstractions most of the time and drops into less clear expression occasionally, then it doesn’t greatly harm the ability of another programmer to read the code – they just need to concentrate a bit more on the vague bits.  However that does make it a lot harder for the compiler to check.  Those lapses from clarity, brief though they may be, are the most important parts to check.

Unfortunately complete coverage isn’t really a possibility.  That was one of the points in my “A Taste of Rust” article.  It is unrealistic to expect any formal language to be very expressive and still completely safe.  That isn’t an excuse not to try though.  While the language cannot be expected to “understand” everything, careful choices of rich abstractions should be able to cover many common cases.  There will still need to be times when the programmer escapes from strict language control and does “unsafe” things.  These need to be carefully documented, and need to be able to “tell” the language what they have done, so the language can still check the way that these  “unsafe” features are used.  This refers back to the previous point about built-in types not being special and all features being available to user-defined types.  In the same way, safety features need to be available in such a way that the programmer can make safety assertions about unsafe code.

As the language design progresses, each decision will need to be measured against these two key principles:

  • Does it aid clarity of expressions?
  • Does it help minimise errors?

These encompass many things so extra guidance will help.  So far we have collected:

  • Are the abstractions clear and useful?
  • Are we using familiar constructs as much as possible?
  • Have we thoroughly and convincingly defended any novelty?
  • Does this benefit the programmer rather than the compiler?
  • Is this design uniform?  Can the idea apply everywhere?  Can we make it apply anywhere else?
  • Can this feature be used equally well be user-defined types and functions?
  • Does this enhance readability? Can the language enforce anything to make this more readable when correct?
  • Are we ensuring that similar things look similar?
  • Are there different aspects to this that should look different?
  • Can we help the compiler ‘understand’ what is going on in this construct?
  • Is this “safety check” feature directly available for the programmer to assert in “unsafe” code.

Not all of these guides will apply to each decision, but some will.  And the two over-riding principles really must be considered at every step.

So there is my philosophy.  I have some idea where it leads, but I fully expect that as I try to justify my design against the philosophy I’ll be surprised occasionally.  For you my dear reader I’m afraid you’ll have to wait a little while until next installment.  Maybe a week or so.

This entry was posted in Language Design. Bookmark the permalink.

Leave a Reply

Your email address will not be published.

ERROR: si-captcha.php plugin says GD image support not detected in PHP!

Contact your web host and ask them why GD image support is not enabled for PHP.

ERROR: si-captcha.php plugin says imagepng function not detected in PHP!

Contact your web host and ask them why imagepng function is not enabled for PHP.