Wednesday, November 16, 2011

Designing a Programming Language Can Be Fun

I recently stumbled upon a nice discussion started by Kanchi in the stacexchange forums. The discussion was if one were to design a programming language, how would one do it?

Such questions are too vague. Language features can't really be discussed until the purpose of the language is determined. Language design is a huge topic. If you're interested in designing a language, a good place to start is by thinking about what the deficiencies are in a language that you already know. Design decisions often arise from considering a design defect in another product.

Alternatively, consider a domain that you are interested in, and then design a domain-specific language (DSL) that specifies solutions to problems in that domain.

Once you have sketched out what you want your language to look like, try to write down precisely what the rules are for determining what is a legal and illegal program. Typically you'll want to do this at multiple levels:

  • A reason for creating a new language
  • A Philosophy
  • A Semantic Definition
  • A lexical description of your tokens
  • A Syntax Analysis definition

How will your language be different? What is its mission? Is it functional? Is it object orientated? Is it a meta-language? What are its unique features? What will it give the world that doesn't exist (or exists in an ugly way)? How do you want to change things? Is it compiled or interpreted? A DSL or general purpose language? This is your philosophy and dictates alot about your language's design.

Next, work on scratching out rough syntax and semantics on paper. This will be your semantic definition ... writing fake code is a great way to develop your thoughts.

You will then need to define your tokens and syntax in some way. Programs then process these into automata capable of reading in strings and processing the syntax. Yacc and Bison use Regular Expressions and a BNF style syntax for lexical and syntax analysis respectively. There are also Yacc and Bison like tools in for other languages.

You will also need a grounding in language theory/compilers to know what NOT to do. Examples include ambiguous grammars, AST generation and manipulation problems and generally how to make life simple for yourself. Knowing the theory is very important.

This is how my dream programming language would look like:
  • A powerful static type system with some support for dependent typing.
  • Optional dynamic typing.
  • Numeric Tower a la Lisp but statically typed.
  • Macros a la Lisp.
  • Primarily a Functional Programming language with basic support for imperative programming (like ML family).
  • Garbage collection.
  • Type inference.
  • Continuations.
  • Optional lazy semantics.
  • All the control constructs would be provided in the form of library functions. (This can be made possible using last two features.)
  • Minimal syntax (not as little as Lisps, but something of the sort of Ioke/Seph.)
Here are some good books that will help you out

Compilers: Principles, Techniques, and Tools
Modern Compiler Implementation in C


Anonymous said...

+1 on mentioning Ioke/Seph

Anonymous said...

Anonymous said...

I strongly disagree with recommending the Dragon Book. There is no need to do a survey of all the different parsing methods in detail in order to write a DSL or a language. I think that most books written on the topic of constructing a compiler, rather than surveying the field, would be far more useful.

Thomas Nadin said...

You mentioned loke/Seph as a idea of the syntax but you didn't post any scratching out of rough syntax and semantics on paper!

Post a Comment