Strategies, tips and tutorials on designing programming languages

Discovering The Arcane World Of Esoteric Programming Languages

/in , /by

An esoteric programming language is a programming language designed to challenge the norms of language design. It is a language designed to make a point. The point could be anything: the challenge itself of creating something unusual, making an elaborate joke, creating a language as an artistic expression, testing promising ideas for programming, etc.

This should make clear that there is not an easy way to properly categorize or organize all the different esoteric programming languages, since by definition they defy the rules. But we could use some concepts and organizing principles to get a better sense of the community around them. So that we could understand what the people use them for, or to use this information as an inspiration to create your own esoteric language.

Download the guide with 68 resources on Creating Programming Languages

68resources

Receive the guide to your inbox to read it on all your devices when you have time

Powered by ConvertKit

Some Useful Concepts

Turing Tarpit

A Turing tarpit is a programming language that is Turing-complete, but practically unusable. A Turing-complete language can simulate any Turing-machine. In practical terms, you can write any program with it. So in theory all such languages are equally powerful, but the ones that are also a Turing Tarpit make incredibly difficult to write any kind of program. A common way to do that is to reduce the number of available symbols: try writing even an Hello World program with only 8 characters.

Quine

A quine is a program that produces as output a copy of its source code. The program cannot be the empty program, even if the empty program is a valid program in the specific language. Reading the source code from disk or memory is also considered cheating. The name “quine” was coined by Douglas Hofstadter, in his book Gödel, Escher, Bach: An Eternal Golden Braid, in the honor of philosopher Willard Van Orman Quine. So the concept of quine is not unique to esoteric programming languages, but nonetheless is a typical first challenge to overcome when writing one.

Code Golf

A code golf is a type of competition in which the objective is to write the shortest possible program that implement a certain algorithm. In this context, shortest means having the shortest source code. It does not mean having the smaller size of the binary executable code. Playing code golf is called “golf scripting”. There are also all other kinds of competitions related to programming, which, given the audience, frequently encourage creative cheating. Generally speaking a challenge is a motivating factor for many esoteric programming languages.

Obfuscation

The concept of obfuscation, that is to say to hide the real meaning of a message, is obviously not exclusive to esoteric programming languages or even programming in general. But it has a great relevance in many esoteric programming languages. Especially if you intend it in the larger general sense of misleading or confusing the recipient. You are not hiding the message because the message itself is important, but because the hidden form is, in itself, the objective. A typical way to achieve this is by minimizing the number of symbols of the language, but you can also camouflage a programming language in what looks like normal text or an image.

Non-Determinism

In this larger meaning of misleading, or confusing the audience, non-determinism can also be used to achieve the same objective. A non-deterministic language is one for which, given the current state of a program, the next state cannot always be predicted. The concept has some use in normal programming languages, essentially due to unpredictable conditions at run time. But it is taken to the extreme by certain esoteric programming languages, by randomizing variables or even randomizing the instructions themselves.

Groups Of Esoteric Programming Languages

As we have already said we cannot provide an exhaustive way of organizing all the esoteric programming languages. And even if somebody could find it, soon somebody else would invent a new esoteric programming languages just to make it invalid. So what we are trying to do is simply to offer some groups, or categories, to better understand and explore the world of esoteric programming languages.

  • Languages with an objective value, although this value is not necessarily an extrinsic or typical one. A basic example is a language designed to win a code golf competition: its value can be measured, but it has no meaning outside of the community of esoteric programming languages. But the more useful kind are the ones designed to achieve a non typical object, such as to bypass security measures (see JSFuck) or to define Type-0 languages of the Chomsky hierarchy (see Thue).
  • Unusable languages. These are languages that are very challenging to use. This can be an explicit objective of the designer or simply an accident of the design itself. The user may even found the fun to use them for some time. A typical way to achieve an unusable language, both by design and by accident, is with minimalism (see Brainfuck). But if you want something almost impossible to use you need something like a language that use a ternary system and purposefully self-alter itself, among other things (see Malbolge).
  • Languages for testing an idea or proving something. These are languages that may not do something useful, but they are good testing ground for a new concept or to prove something. For instance a language in which programs are arranged in a two-dimensional grid (see Befunge) or an almost pure functional language (see Unlambda)
  • Artistic languages. These are languages that are designed with the idea of having some artistic value. You could argue that they are effectively part either of the group of the testing languages or the ones with an objective value. We put them in a different category, because they don’t look like programming, but they the tend to look interesting, even if you may not want to use them. For instance they look like abstract art (see Piet) or like a Shakesperean play (see Shakespeare).
  • Jokes languages. These are languages invented with people with a weird sense of humour. Like a person that says: «do you want to hear a joke? – then it reads War And Peace, before concluding – Our whole lives are a joke!». An example is a satirical language, where even the reference manual is a joke (see INTERCAL)

Some Notable Esoteric Languages

Of course this is not an exhaustive list of notable esoteric programming languages, but more modestly a list of a few notable for their success or peculiarity.

Befunge

The main esoteric feature of Befunge is that programs are arranged in a two-dimensional grid. It is also a stack based and a reflective language, so it allows a program to alter itself. The main objective was to design a language for which it was as hard as possible to create a compiler.

The original version, now called Befunge-93, it is not Turing complete, because it puts a limit of 80×25 to the grid size. But a new version, called Befunge-98, removes this limit and it should be Turing complete. Befunge has spawned a whole class of multidimensional languages, called Fungeoid.

Befunge has commands that control the direction up, down, left, right and thus can also create a cycle, together with more traditional commands for output, binary operations, etc.

An Hello Word program looks like this.

Brainfuck

Probably the most famous of all esoteric programming languages, it is notable for his extreme minimalism. Both in the number of commands available and also in having a very small compiler. In fact the second condition is the reason for the first, because the author wanted to create a language with the smallest possible compiler.  The author created a compiler that used only 240 bytes and sometimes later somebody created one with just 100 bytes. A natural consequence of this objective is that the language is hard to use, although it is Turing complete. In short, it is a Turing tarpit.

It is sometimes referred to with a censored spelling, such as Brainf*ck or many other variations.

The language consist in eight different commands that manipulate a data pointer and two stream of bytes for input and output. It also supports loops. Other characters, besides the ones representing the commands, are considered comments and ignored by the compiler.

This is an example of how the language works (taken from the Esolangs wiki).

An Hello World program looks like this.

If you want to find out more you can see on the corresponding Wikipedia page or Esolangs page.

INTERCAL

INTERCAL may have not been the first esoteric programming language, but it is certainly the first famous one. How old is it? It was created in 1972 and the first implementation was made with punched cards. The language was intended as a parody, but also to make something completely new, an alien to the programming world. The name is not an acronym, according to the authors:

The full name of the compiler is “Compiler Language With No Pronounceable Acronym,” which is, for obvious reasons, abbreviated “INTERCAL.”

The rest of the INTERCAL Reference Manual (PS format) is also full of nonsensical or humorous statements. This is both for the language they describe and for how they do it. For instance this is a section on Variables

INTERCAL allows only 2 different types of variables, the 16-bit integer and the 32-bit integer. These
are represented by a spot ( . ) or two-spot ( : ), respectively, followed by any number between 1 and 65535,
inclusive. These variables may contain only non-negative numbers; thus they have the respective ranges of
values: 0 to 65535 and 0 to 4294967295. Note: .123 and :123 are two distinct variables. On the other hand,
.1 and .0001 are identical. Furthermore, the latter may not be written as 1E-3 .

The language also allows the use of a modifier PLEASE. However it also requires the use of the proper quantity of this keyword. It cannot be used too little or too much, that is to say you need to show the proper amount of politeness. The really unfunny part is that it was an undocumented feature in the original manual. A joke manual for a joke manual may be okay, but one that it is incomplete is unacceptable.

This is an Hello World in a version of INTERCAL implemented with C: C-INTERCAL.

In short, INTERCAL is a very elaborate joke. The kind of joke that may lead you to admire its creator for its perseverance or to doubt its sanity, or maybe both.

JSFuck

The success of Brainfuck are spurred the creation of many derivatives languages, too many to mention them all. But the most notable one is JSFuck.

JSFuck is not a proper language, but it is more of an esoteric programming style of Javascript that requires of using only 6 characters. The resulting programs are valid JavaScript programs and in fact it was invented to bypass security techniques like malware detection. Its properties made it also useful for code obfuscation.

It works because you can evaluate any expression in Javascript as any type. So [] represents and empty array, but by prepending it with a + you can force it to evaluate as the number 0. To obtain a letter like a you can manipulate the value false, etc. The end result is an extremely verbose language: the equivalent of alert("Hello World!") is 22948 characters long.

Malbolge

Malbolge is a language specifically designed to be almost impossible to use: «via a counter-intuitive ‘crazy operation’, base-three arithmetic, and self-altering code», in the words of its own creator. In fact even the author never wrote a working program with it. The first program was generated by another program  that implemented an heuristic search algorithm. The language is not Turing complete and it is also based on a misspelling of Malebolge, the eight circle of hell in Dante Alighieri’s Inferno. So it really does not have any redeeming quality.

I will not attempt to describe it because the whole thing is explicitly an exercise in frustration. However there is a notable “crazy operation” that is worth mentioning: encryption. The language is supposed to work on an ternary virtual machine and has three registers, one of which contain a pointer to the current instruction and is called [c]. After the instruction is executed the modulo 94 of the value in [c] replaces whatever is in [c] then the result is encrypted according to an encryption table. Welcome to hell, indeed.

Some brave soul has created an Hello World program.

Piet

Piet is a language in which programs are represented as abstract art paintings, in the style of Piet Mondrian. It is stack based and Turing complete.

There are 18 colors ordered according to hue and brightness, plus black and white. These last two have special meaning and are used for control flow. The program execution relies on two “pointers”: a Direction Pointer and a Color Block Chooser. The DP may point up, down, left and right, while CC can only point left and right. The combination of these two pointers govern the execution of the program: basically which block of color is executed next. The size of a block of color represent an integer. When the program transition between different blocks of color, their difference in hue and brightness determines the kind of command that is executed. The commands are the usual one, like output a value, multiply, etc.

The Hello World program has a certain beauty.

Hello World in Piet by Thomas Schoch

Shakespeare

Shakespeare is a language designed to have: «beautiful source code that resembled Shakespeare plays». The language has few commands and it is functionally similar to assembly language, but it is unsurprisingly quite verbose.

The variables must be declared in an initial section and their names must be valid Shakespearean characters, such as Romeo or Juliet. These variables are stacks on which later will be executed operations like pop, push and input/output. The name of acts and scenes works as goto labels and the destination of certain conditional statements. Characters, that is to say variables, must be called on stage to be manipulated and there can be only two at a time on the stage.

The lines usually represents numerical constants: some nouns and adjective are converted in numerical values.

Special words, like “Remember”, or combinations thereof, like “Speak your mind”, perform commands. These are normal commands such as pushing values on the stack-character, outputting the value of the current variable or the corresponding ASCII character.

A conditional statement is represented by a question from one character and an answer from the other character which determines where to go, if the condition of the question evaluate to true.

The Hello World is as long and productive as a Shakespearean play.

Thue

Thue is a programming language based upon a string rewriting system, called semi-Thue system. It is non-deterministic and follows the constraint programming paradigm. Which means that the variables are defined in terms of constraint (ex. something is true or false). It is a Turing tarpit.

In the case of Thue the costraints are represented by a list of substitution rules in the form:

Special formats of this form represent input, output or the ending of the list of rules.

The non-deterministic nature of the language can be shown by indicating two possible replacement for the same string. For example:

  • you write a rule that says that the string a can be replaced with stupid
  • you also write a rule that says that the string a can be replaced with you are

When a program is executed the string a could be replaced by either of the two options.

The list of rules is followed by a string that represents the initial state.

While writing a useful program can be hard, the typical Hello World is quite easy and understandable, at least by the standard of esoteric programming languages.

Unlambda

Unlambda is an (almost) pure functional language designed to show a purely functional language (and probably how impractical that would be). It is based on combinatory logic. It is Turing complete and the first functional Turing tarpit. It relies on a few functions, an apply operator ` (the backquote character) and it also support input/output. Technically it works only on functions with a single argument, but multi-argument functions can be translated into a sequence of functions.

An Hello World program almost looks readable.

Other Interesting Esoteric Languages

Fugue is a language that uses MIDI files as source code. The intervals between each note is translated to specific traditional commands, such as input/output or addition.

Beatnik is a stack based language which consists in a series of English words; whitespace and punctuation are ignored. The words are converted in traditional commands according to their value in the game Scrabble.

Whitespace is a joke language in which only whitespace characters, such as tabs and spaces, are valid and any other character is ignored. This is, of course, the inverse of the usual behaviour of compilers that ignore whitespace. Given these characteristic it can be used in a Polyglot program, that is to say a program that is valid for more than one language. As long as the other language is not Python, or any language where whitespace matters.

GolfScript is a concatenative programming language designed to win code-golf competitions that is also Turing complete.

Snowflake is a reversible self-modifying language in which both the interpreter and the program are modified at each run.

FRACTRAN is a language in which programs are a list of fractions and an initial number. I am not sure what it does, but it does something, since it has a Wikipedia page.

Iota and Jot are two formal languages, each one designed to be the simplest formal system. By their nature they can also be considered  equally minimalist, Turing tarpit, programming languages. Both use only two symbols and perform two operations. A successor, called Zot, supports also input/output.

Entropy is a very aptly named programming language designed to accept the idea of giving up control. Any output of the program will be approximated and each time the data is accessed it is randomly modified. The language does not modify the original program, so each time is run the output will be different, but the initial state will be preserved. A curious side effect of the randomization of data is Drunk Eliza, a web version of the classic Eliza program in which the therapist seems to be drunk.

Monicelli is a joke language based on the comedy film My Friends. A typical program looks like a series of nonsensical Italian phrases. Surprisingly this makes sense since the film used as inspiration also feature nonsensical phrases. It is the circle of madness.

Summary

The world of esoteric programming language is as exciting as it is maddening: there are no rules, but a lot of interesting things. I hope to have given you a slightly sane window on what you could expect.

If you want to know more or to participate in this community I suggest looking at Esolangs. That website, together with Wikipedia, is the source of most examples shown in this article. There you can also find some inspiration in a list of ideas for an esoteric programming language.

You may also find interesting the blog of Marc C. Chu-Carroll in its many incarnations during the years. As the name Good Math, Bad Math implies, it is mainly dedicated to mathematics. Nonetheless it has also many analyses of esoteric programming languages in a series called Pathological Programming (Language). You can see, for instance, one dedicated to the smallest programming language.

68 Resources To Help You To Create Programming Languages

/in , /by

Here it is a new guide, to collect and organize all the knowledge that you need to create your programming language from scratch.

Creating a programming language is one of the most fascinating challenge you can dream of as a developer.

The problem is that there are a lot of moving parts, a lot of things to do right and it is difficult to find a well detailed map, to show you the way. Sure, you can find a tutorial on writing half a parser there, an half-baked list of advices on language design, an example of a naive interpreter. To find those things you will need to spend hours navigating forums and following links.

We thought it was the case to save you some time by collecting relevant resources, evaluate them and organize them. So you can spend time using good resources, not looking for them.

We organized the resources around the three stages in the creation of a programming language: design, parsing, and execution.

Download the guide with 68 resources on Creating Programming Languages

68resources

Receive the guide to your inbox to read it on all your devices when you have time

Powered by ConvertKit

Table of contents

Section 1:

Designing the Language

When creating a programming language you need to take ideas and transform them in decisions. This is what you do during the design phase.

Before You Start…

Some good resources to beef up your culture on language design.

Articles

Books

  • Design Concepts in Programming Languages, if you want to make deliberate choices in the creation of your programming language, this is the book you need. Otherwise, if you don’t already have the necessary theoretical background, you risk doing things the way everybody else does them. It’s also useful to develop a general framework to understand how the different programming languages behave and why.
  • Practical Foundations for Programming Languages, this is, for the most part, a book about studying and classifying programming languages. But by understanding the different options available it can also be used to guide the implementation of your programming language.
  • Programming Language Pragmatics, 4th Edition, this is the most comprehensive book to understand contemporary programming languages. It discusses different aspects, of everything from C# to OCaml, and even the different kinds of programming languages such as functional and logical ones. It also covers the several steps and parts of the implementation, such as an intermediate language, linking, virtual machines, etc.
  • Structure and Interpretation of Computer Programs, Second Edition, an introduction to computer science for people that already have a degree in it. A book widely praised by programmers, including Paul Graham directly on the Amazon Page, that helps you developing a new way to think about programming language. It’s quite abstract and examples are proposed in Scheme. It also covers many different aspect of programming languages including advanced topics like garbage collection.

Type Systems

Long discussions and infinite disputes are fought around type systems. Whatever choices you end up making it make sense to know the different positions.

Articles

  • These are two good introductory articles on the subject of type systems. The first discuss the dichotomy Static/Dynamic and the second one dive into Introspection.
  • What To Know Before Debating Type Systems, if you already know the basics of type systems this article is for you. It will permit you to understand them better by going into definitions and details.
  • Type Systems (PDF), a paper on the formalization of type systems that also introduces more precise definitions of the different type systems.

Books

  • Types and Programming Languages, a comprehensive book on understanding type systems. It will impact your ability to design programming languages and compilers. It has a strong theoretical support, but it also explains the practical importance of individual concepts.
  • Functional programming and type systems, an interesting university course on type systems for functional programming. It is used in a well known French university. There are also notes and presentation material available. It is as advanced as you would expect.
  • Type Systems for Programming Language, is a simpler course on type system for (functional) programming languages.

Section 2:

Parsing

Parsing transforms the concrete syntax in a form that is more easily manageable by computers. This usually means transforming text written by humans in a more useful representation of the source code, an Abstract Syntax Tree.

An abstract syntax tree for the Euclidean algorithm

There are usually two components in parsing: a lexical analyzer and the proper parser. Lexers, which are also known as tokenizers or scanners, transform the individual characters in tokens, the atom of meaning. Parsers instead organize the tokens in the proper Abstract Syntax Tree for the program. But since they are usually meant to work together you may use a single tool that does both the tasks.

Tools

  • Flex, as a lexer generator and (Berkeley) Yacc or Bison, for the generation of the proper parser, are the venerable choices to generate a complete parser. They are a few decades old and they are still maintained as open source software. They are written in and thought for C/C++. They still works, but they have limitations in features and support for other languages.
  • ANTLR, is both a lexer and a parser generator. It’s also more actively developed as open source software. It is written in Java, but it can generate both the lexer and the parser in languages as varied as C#, C++, Python, Javascript, Go, etc.
  • Your own lexer and parser. If you need the best performance and you can create your own parser. You just need to have the necessary computer science knowledge.

Tutorials

  • Flex and Bison tutorial, a good introduction to the two tools with bonus tips.
  • Lex and Yacc Tutorial, at 40 pages this is the ideal starting point to learn how to put together lex and yacc in a few hours.
  • Video Tutorial on lex/yacc in two parts, in an hour of video you can learn the basics of using lex and yacc.
  • ANTLR Mega Tutorial, the renown and beloved tutorial that explains everything you need to know about ANTLR, with bonus tips and tricks and even resources to know more.

Books

  • lex & yacc, despite being a book written in 1992 it’s still the most recommended book on the subject. Some people say because the lack of competition, others because it is good enough.
  • flex & bison: Text Processing Tools, the best book on the subject written in this millennium.
  • The Definitive ANTLR 4 Reference, written by the main author of the tool this is really the definitive book on ANTLR 4. It explains all of its secrets and it’s also a good introduction about how the whole parsing thing works.
  • Parsing Techniques, 2nd edition, a comprehensive, advanced and costly book to know more than you possibly need about parsing.

Section 3:

Execution

To implement your programming language, that is to say to actually making something happens, you can build one of two things: a compiler or an interpreter. You could also build both of them if you want. Here you can find a good overview if you need it: Compiled and Interpreted Languages.

The resources here are dedicated to explaining how compilers and/or interpreters are built, but for practical reasons often they also explain the basics of creating lexers and parsers.

Compilers

A compiler transforms the original code into something else, usually machine code, but it could also be simply any lower level language, such as C. In the latter case some people prefer to use the term transpiler.

Tools

  • LLVM, a collection of modular and reusable compiler and toolchain technologies used to create compilers.
  • CLR, is the virtual machine part of the .NET technologies, that permits to execute different languages transformed in a common intermediate language.
  • JVM, the Java Virtual Machine that powers the Java execution.
  • Babel, a JavaScript compiler. It has a very modern structure, based upon plugins, which means that it can be easily adapted, but it doesn’t do anything by default, really, that is what the documentation says. Its creators present it as a tool to support new featuers of JavaScript in old environment, but it can do much more. For instance, you can use to create JavaScript-based languages, such as LightScript.

Articles & Tutorials

  • Building Domain Specific Languages on the CLR, an article on how to build internal DSL on the CLR. It’s slightly outdated, since it’s from 2008, but it’s still a good presentation on the subject.
  • The digital issue of MSDN Magazine for February 2008 (CHM format), contains an article on how to Create a Language Compiler for the .NET Framework. It’s still a competent overview of the whole process.
  • Create a working compiler with the LLVM framework, Part 1 and Part 2, a two-part series of articles on creating a custom compiler by IBM, from 2012 and thus slightly outdated.
  • A few series of tutorials froms the LLVM Documentation, this is three great linked series of tutorial on how to implement a language, called Kaleidoscope, with LLVM. The only problem is that some parts are not always up-to-date.
  • My First LLVM Compiler, a short and gentle introduction to the topic of building a compiler with LLVM.
  • Creating an LLVM Backend for the Cpu0 Architecture, a whopping 600-pages tutorial to learn how to create a LLVM backend, also available in PDF or ePub. The content is great, but the English is lacking. On the positive side, if you are a student, they feel your pain of transforming theoretical knowledge into practical applications, and the book was made for you.
  • A Nanopass Framework for Compiler Education, a paper that present a framework to teach the creation of a compiler in a simpler way, transforming the traditional monolithic approach in a long series of simple transformations. It’s an interesting read if you already have some theoretical background in computer science.
  • An Incremental Approach to Compiler Construction (PDF), a paper that it’s also a tutorial that develops a basic Scheme compiler with an easier to learn approach.
  • The Super Tiny Compiler!: “This is an ultra-simplified example of all the major pieces of a modern compiler written in easy to read JavaScript” (and using Babel). There is a short introduction, but this is more of a walkthrough of the code than a proper tutorial. This may be a good or a bad thing, depending on your preference.

Books

  • Compilers: Principles, Techniques, and Tools, 2nd Edition, this is the widely known Dragon book (because of the cover) in the 2nd edition (purple dragon). There is a paperback edition, which probably costs less but it has no dragon on it, so you cannot buy that. It is a theoretical book, so don’t expect the techniques to actually include a lot of reusable code.
  • Modern Compiler Implementation in ML, this is known as a the Tiger book and a competitor of the Dragon book. It is a book that teaches the structure and the elements of a compiler in detail. It’s a theoretical book, although it explains the concept with code. There are other versions of the same book written using Java and C, but it’s widely agreed that the ML one is the best.
  • Engineering a Compiler, 2nd edition, it is another compiler book with a theoretical approach, but that it covers a more modern approach and it is more readable. It’s also more dedicated to the optimization of the compiler. So if you need a theoretical foundation and an engineering approach this is the best book to get.

Interpreters

An interpreter directly executes the language without transforming it in another form.

Articles & Tutorials

Books

  • Writing An Interpreter In Go, despite the title it actually shows everything from parsing to creating an interpreter. It’s contemporary book both in the sense that is recent (a few months old), and it is a short one with a learn-by-doing attitude full of code, testing and without 3-rd party libraries. We have interviewed the author, Thorsten Ball.
  • Crafting Interpreters, a work-in-progress and free book that already has good reviews. It is focused on making interpreters that works well, and in fact it will builds two of them. It plan to have just the right amount of theory to be able to fit in at a party of programming language creators.

Section 4:

General

This are resources that cover a wide range of the process of creating a programming language. They may be comprehensive or just give the general overview.

Tools

In this section we include tools that cover the whole spectrum of building a programming language and that are usually used as standalone tools.

  • Xtext, is a framework part of several related technologies to develop programming languages and especially Domain Specific Languages. It allows you to build everything from the parser, to the editor, to validation rules. You can use it to build great IDE support for your language. It simplifies the whole language building process by reusing and linking existing technologies under the hood, such as the ANTLR parser generator.
  • JetBrains MPS, is a projectional language workbench. Projectional means that the Abstract Syntax Tree is saved on disk and a projection is presented to the user. The projection could be text-like, or be a table or diagram or anything else you can imagine. One side effect of this is that you will not need to do any parsing, because it is not necessary. The term Language Workbench indicates that Jetbrains MPS is a whole system of technologies created to help you create your own programming language: everything from the language itself to IDE and supporting tools designed for your language. You can use it to build every kind of language, but the possibility and need to create everything makes it ideal to create Domain Specific Languages that are used for specific purposes, by specific audiences.
  • Racket, is described by its authors as “a general-purpose programming language as well as the world’s first ecosystem for developing and deploying new languages”. It’s a pedagogical tool developed with practical ambitions that has even a manifesto. It is a language made to create other languages that has everything: from libraries to develop GUI applications to an IDE and the tools to develop logic languages. It’s part of the Lisp family of languages, and this tells everything you need to know: it’s all or nothing and always the Lisp-way.

Articles

Tutorials

Books

  • How to create pragmatic, lightweight languages, the focus here is on making a language that works in practice. It explains how to generate bytecode, target the LLVM, build an editor for your language. Once you read the book you should know everything you need to make a usable, productive language. Incidentally, we have written this book.
  • How To Create Your Own Freaking Awesome Programming Language, it’s a 100-page PDF and a screencast that teach how to create a programming language using Ruby or the JVM. If you like the quick-and-dirty approach this book will get you started in little time.
  • Writing Compilers and Interpreters: A Software Engineering Approach, 3rd edition, it’s a pragmatic book that still teaches the proper approach to compilers/interpreters. Only that instead of an academic focus, it has an engineering one. This means that it’s full of Java code and there is also UML sprinkled here and there. Both the techniques and the code are slightly outdated, but this is still the best book if you are a software engineer and you need to actually do something that works correctly right now, that is to say in a few months after the proper review process has completed.
  • Language Implementation Patterns, this is a book from the author of ANTLR, which is also a computer science professor. So it’s a book with a mix of theory and practice, that guides you from start to finish, from parsing to compilers and interpreters. As the name implies, it focuses on explaining the known working patterns that are used in building this kind of software, more than directly explaining all the theory followed by a practical application. It’s the book to get if you need something that really works right now. It’s even recommended by Guido van Rossum, the designer of Python.
  • Build Your Own Lisp, it’s a very peculiar book meant to teach you how to use the C language and how to build you own programming language, using a mini-Lisp as the main example. You can read it for free online or buy it. It’s meant you to teach about C, but you have to be already familiar with programming. There is even a picture of Mike Tyson (because… lisp): it’s all so weird, but fascinating.
  • Beautiful Racket: how to make your own programming languages with Racket, it’s a good and continually updated online book on how to use Racket to build a programming language. The book is composed of a series of tutorials and parts of explanation and reference. It’s the kind of book that is technically free, but you should pay for it if you use it.
  • Programming Languages: Application and Interpretation, an interesting book that explains how to create a programming language from scratch using Racket. The author is a teacher, but of the good and understandable kind. In fact, there is also a series of recordings of the companion lectures, that sometimes have questionable audio. There is an updated version of the book and of the recordings, but the new book has a different focus, because it want also to teach about programming language. It also doesn’t uses Racket. If you don’t know any programming at all you may want to read the new version, if you are an experienced one you may prefer the old one.
  • Implementing Domain-Specific Languages with Xtext and Xtend, 2nd edition, is a great book for people that want to learn with examples and using a test-driven approach. It covers all levels of designing a DSL, from the design of the type system, to parsing and building a compiler.
  • Implementing Programming Languages, is an introduction to building compilers and interpreters with the JVM as the main target. There are related materials (presentations, source code, etc.) in a dedicated webpage. It has a good balance of theory and practice, but it’s explicitly meant as a textbook. So don’t expect much reusable code. It’s the typical textbook also in the sense that it can be a great and productive read if you already have the necessary background (or a teacher), otherwise you risk ending up confused.
  • Implementing functional languages: a tutorial, a free book that explains how to create a simple functional programming language from the parsing to the interpreter and compiler. On the other hand: “this book gives a practical approach to understanding implementations of non-strict functional languages using lazy graph reduction”. Also, expect a lot of math.
  • DSL Engineering, a great book that explains the theory and practice of building DSLs using language workbenches, such as MPS and Xtext. This means that other than traditional design aspects, such as parsing and interpreters, it covers things like how to create an IDE or how to test your DSL. It’s especially useful to software engineers, because it also discusses software engineering and business related aspects of DSLs. That is to say it talks about why a company should build a DSL.
  • Lisp in Small Pieces, an interesting book that explain in details how to design and implement a language of the Lisp family. It describes “11 interpreters and 2 compilers” and many advanced implementation details such as the optimization of the compiler. It’s obviously most useful to people interested in creating a Lisp-related language, but it can be an interesting reading for everybody.

Section 5:

Summary

Here you have the most complete collection of high-quality resources on creating programming languages. You have just to decide what you are going to read first.

At this point we have two advices for you:

  1. Get started. It does not matter how many amazing resources we will send you, if you do not take the time to practice, trying and learning from your mistake you will never create a programming language
  2. If you are interested in building programming languages you should subscribe to our newsletter. You will receive updates on new articles, more resources, ideas, advices and ultimately become part of a community that share your interests on building languages

You should have all you need to get started. If you have questions, advices or ideas to share feel free to write at federico@tomassetti.me. We read and answer every email.

Our thanks to Krishna and the people on Hacker News for a few good suggestions.

Building a language: tool support

/0 Comments/in , /by

When building a language there is one aspect which is absolutely crucial: that is tool support.
Tool support will determine if your language is usable at all, it will influence the reception from user and the usability.
In this video I explain why and how you can build great tool support with a limited effort.

Tool support is what makes a real language. This is also one of the reasons why I am against the whole concept of internal DSLs: they are nice but they are not really languages. They cannot be compared in any way to external DSLs (a.k.a. real DSLs).

And it is nice that experts agree on this:

Building a compiler for your own language: validation

/2 Comments/in , /by

validation_for_your_own_programming_language

So you have parsed your code and built a clean AST for it. Now it is time to check if what the user has expressed make sense at all. We should perform validation, identifying semantical errors, to communicate together with lexical and syntactical errors (provided by the parser).

This post is the part of a series. The goal of the series is to describe how to create a useful language and all the supporting tools.

  1. Building a lexer
  2. Building a parser
  3. Creating an editor with syntax highlighting
  4. Build an editor with autocompletion
  5. Mapping the parse tree to the abstract syntax tree
  6. Model to model transformations
  7. Validation
  8. Generating bytecode

After writing this series of posts I refined my method, expanded it, and clarified into this book titled
How to create pragmatic, lightweight languages

 

Code

Code is available on GitHub under the tag 07_validation

Implement semantic checks

In the previous post we have seen how to implement the function process to execute an action on all the nodes of our AST. A typical case is that we want to execute certain operation only on certain nodes. We want still to use process to navigate the tree. We can do that by creating this function named specificProcess.

Let’s see how to use specificProcess to:

  • find all the VariableDeclarations and check they are not re-declaring a variable already declared
  • find all the VarReferences and verify they are not referring to a variable that has been not declared or has been declared after the VarReference
  • perform the same check done on VarReferences also for Assignments

Ok, so invoking validate on the root of the AST will return all possible semantic errors.

Getting all errors: lexical, syntactic, and semantic

We first need to invoke the ANTLR parser and get:

  • the parse tree
  • the list of lexical and syntactic error

Then we map the parse tree to the AST and perform the semantic validation. Finally we return the AST and all the errors combined.

In the rest of the system we will simply call the SandyParserFacade without the need to invoke the ANTLR parser directly.

Test validation

Will it fly? Let’s verify that.

Conclusions

This is all nice and well: with a simple call we can get a list of all errors we have. For each of them we have a description and the position. This is enough for our compiler but we would now need to show these errors in the editor. We will do that in out of the future posts.

 

Related articles across the web

Getting started with ANTLR: building a simple expression language

/20 Comments/in , , , /by
This post is the part of a series. The goal of the series is to describe how to create a useful language and all the supporting tools.

  1. Building a lexer
  2. Building a parser
  3. Creating an editor with syntax highlighting
  4. Build an editor with autocompletion
  5. Mapping the parse tree to the abstract syntax tree
  6. Model to model transformations
  7. Validation
  8. Generating bytecode

After writing this series of posts I refined my method, expanded it, and clarified into this book titled
How to create pragmatic, lightweight languages

In this post we will start working on a very simple expression language. We will build it in our language sandbox and therefore we will call the language Sandy.

I think that tool support is vital for a language: for this reason we will start with an extremely simple language but we will build rich tool support for it. To benefit from a language we need a parser, interpreters and compilers, editors and more. It seems to me that there is a lot of material on building simple parsers but very few material on building the rest of the infrastructure needed to make using a language practical and effective.

I would like to focus on exactly these aspects, making a language small but fully useful. Then you will be able to grow your language organically.

The code is available on GitHub: https://github.com/ftomassetti/LangSandbox. The code presented in this article corresponds to the tag 01_lexer.

The language

The language will permit to define variables and expressions. We will support:

  • integer and decimal literals
  • variable definition and assignment
  • the basic mathematical operations (addition, subtraction, multiplication, division)
  • the usage of parenthesis

Examples of a valid file:

The tools we will use

We will use:

  • ANTLR to generate the lexer and the parser
  • use Gradle as our build system
  • write the code in Kotlin. It will be very basic Kotlin, given I just started learning it.

Setup the project

Our build.gradle file will look like this

We can run:

  • ./gradlew idea to generate the IDEA project files
  • ./gradlew generateGrammarSource to generate the ANTLR lexer and parser

Implementing the lexer

We will build the lexer and the parser in two separate files. This is the lexer:

Now we can simply run ./gradlew generateGrammarSource and the lexer will be generated for us from the previous definition.

Testing the lexer

Testing is always important but while building languages it is absolutely critical: if the tools supporting your language are not correct this could affect all possible programs you will build for them. So let’s start testing the lexer: we will just verify that the sequence of tokens the lexer produces is the one we aspect.

Conclusions and next steps

We started with the first small step: we setup the project and built the lexer.

There is a long way in front of us before making the language usable in practice but we started. We will next work on the parser with the same approach: building something simple that we can test and compile through the command line.

What if sketching on a whiteboard was a form of programming?

/4 Comments/in , /by

There are different possible notations for languages: textual and graphical are the two larger families.

We can define graphical notations for formal languages. For example we can define a graphical notation to define state machines.

A Domain Specific Language for state machines can be defined using JetBrains MPS. However the user would have to edit the state machine inside MPS.

I wonder if we could instead specify a state machine just by sketching something on a whiteboard. Consider this example:

sm1

We have a start state (the white circle on top) which leads us to the state A without needing any event. Then from state A we can go to state B when an event of type b occurs. Or we can go to state C if an event of type a occurs. From C we need a state of type c to move to D.

Note that I did not represent the direction of transitions, we could assume that they always lead from the higher state to the lower.

I think that at this point we should just make a picture to this sketch and obtain a program which would permit to run this state machine.

To do that we should recognize the different shape, the text present and assign everything to a corresponding concept in our DSL.

The first step would be to recognize rectangles. I guess there are already libraries to do that. I tried OpenCV but I really do not like the way C++ dependencies are handled. I started playing with BoofCV instead, which is written in Java. I first used functions to recognize segments and I got something like this:

Screenshot from 2016-03-28 19-12-53

Then I wrote some functions to merge segments which have endpoints very close and similar slope, to reduce the number of segments. That did not work particularly well.

Screenshot from 2016-03-28 19-13-03

I realized I should probably use some pre-processing: first a Gaussian blur and then calculate the derivatives over the X and Y axis. I got something like this. The colors depends on the values present in the derivates X and Y images. I should use those values to recognize horizontal and vertical lines with common endpoints and so get rectangles.

Screenshot from 2016-03-29 18-49-46

This is not as easy as I hoped but I would love to spend more time on it in the future.

Conclusions

I do not have experience in image recognition so I cannot say if we can get something usable enough with the current state of the art. However I love the idea of lowering the barriers to make easier for people to formalize their thoughts. By working on DSLs we lower the conceptual barriers, so that instead of using GPLs (like Java or C++) users can adopt languages which are more familiar to them. The next step is to remove the tool barrier, making programming as easy as sketching.

Still, people will need some ability to formalize their thoughts but we can definitely remove some of the incidental barriers due to languages, notations and tools.

Related articles across the web

Raising the level of abstraction: what if we tried to do that bottom up?

/1 Comment/in , /by

It is clear that software development is going in the direction of raising the level of abstraction since it was born.

The reason is simple: we can juggle with so many concepts in our mind. If we are busy thinking about what we stored in the EAX register it is difficult to think about the bigger picture. As we raise the level of abstraction we start using bigger bricks and we can see farther.  Once we think in terms of objects the OOP design patterns can emerge, because they build on combinations of a few concepts at our current level of abstraction.

How are we moving to higher levels of abstractions? By hiding the details. We hide how we use registers, how we allocate memory, how pointers are handled, how polymorphism is implemented.

There are several way we can achieve that: normally we build new languages from which we generate or compile to some lower level abstraction. For example many C++ compilers at the beginning were just spitting out some C. Also compilers for Eiffel were using the same strategy. One thing that instead was not tried was to evolve languages adding new concepts as they emerge. In this case I am thinking about a gradual process which would target micro-patterns. Things like getters or setters in Java. Or things like this one:

What we are doing here? we are just returning self.data[code]. If it was not initialized we would set it to a default value ({}). Ok, lazy initialization: this is a concept common and comprehensible per se. What if we could add this concept and see if it is then used to build up new patterns?

This would be trivial to do using a tool like Jetbrains MPS.

I plan to play a little bit with this idea in next week and see where it leads me.

Related articles across the web

Getting started with Jetbrains MPS: how to define a simple language (screencast)

/in , , /by

I am blessed (or cursed) with having many different interests in software development. However my deepest love is with language engineering. There are different tools and techniques but Jetbrains MPS is particularly fascinating.

To help people getting started or just get the feeling of how it is to develop with Jetbrains MPS I recorded this short screencast.

 

 

If you are not familiar with this tool here there are the basic ideas.

Jetbrains MPS is a projectional editor: that means that it internally stores the information contained in the different nodes.

If you create a model, then change how certain nodes should look, and you reopen the model it will be automatically using the new “look & feel” that you just. This is simply because what is stored is the pure information, while the appearance is recreated each time you open a model. In other words when you open a model it is projected in a form that you defined and that should be easy to understand for a human being.

This is very different from what happens with text language: suppose you create your language and then decide to replace braces with brackets. You have now to manually go over all your existing source files and modify them, because in that case what is saved is not the pure information, the abstract syntax tree, but its representation: the textual form.

In Jetbrains MPS you work on the different concerns of your language separately: you first define the single concept and the information they contain, then you work on the other aspects. There are several like typesystem, generation, dataflow, etc. In this short screencast we just look at the concept definition and the editor aspect.

One of the advantages of a projectional editor is that you can change the appearance of your nodes without invalidating your existing models. That is great to incrementally improve the appearance of the single nodes and the way they can be edited. In the screencast we start with the default representation of the concept we defined, as provided by default by Jetbrains MPS. Then we refine the editors in a couple of steps until we have a representation which is good enough.

At the end of the screencast we have a language we can use to define very simple todo lists. The possibility to improve it are endless:

  • we could add more concepts: like priority, deadlines and tags for each single task
  • we could add the possibility to mark a task as done and add a nice shortcut to do so
  • we could integrate the language with some other tool: what if we could synchronize our models with Trello or with workflowy?
  • we could support subtasks

Question: have you ever thought of creating your own language, either a general purpose language or a domain specific language? If so did you actually get started?

 

Dynamic, static, optional, structural typing and engineering challenges

/0 Comments/in /by

How an engineer should NOT look at technical matters

Dynamic versus static typing is one of those confrontations that seams to attracts zealots. It really sadden me to see how people tend to defend vehemently their side simply because they are not able to understand the other position. In my opinion if you do not get why both static and dynamic typing are great in certain situations you are an incomplete software developer. You have chosen to look at just a portion of the picture.

An engineer should be open-minded: it is ok to have your opinions but when you keep bashing ideas that made millions of developers very productive, chances are that you are missing something. Try being humble, you could end up learning something.

Ok, so what?

I had very good experiences using Java or Haskell (from the static side) or Python and Ruby (from the dynamic field). There is no way you can obtain the succintness of Ruby code, the amazing possibilities given by its metaprogramming features with statically typed languages. On the other end I really end up missing static typing when I have to refactor large chunks of code. Tests help (when they are there) but it is often not enough.

Now, there are approaches to try getting the best of whole worlds. One solution is to combine languages for different parts of the system: perhaps you could write the infrastructure of your platform using Java and the business logic using JRuby. Why not?

However that means that you have still some challenges at the language boundaries. You need to master several tools and learn the best practices for the different languages and so on. Therefore it would be interesting to get the advantages of both worlds in one single language.

A compromise?

A very partial solution is to use static typing with type inference: it does not give you the same power you get with dynamically types languages but you get some of the succintness. Not a giant leap but it helps closing the gap. Types are still calculated at compile time, and that means that you could have to streamline your solution, so that also the compiler can understand it. However you would not have to type yourself all the types. Also, when refactoring you have to change types in less places.

Type inference sounds as a great idea but it has its drawbacks: try writing some Haskell code, pretty soon you will start being puzzled about the type derived from the compiler for a value. In practice I need to add some annotations to make some of the types explicit otherwise I get lost pretty soon.

Another approach to combine static and dynamic typing is to start from a dynamic language and try to make it more static-like. There are two options for that: optional typing and structural typing.

Basically optional typing means that you can add some type annotations in certain parts of your dynamic language, so that a part of it can be statically checked, while the rest will keep being dynamic. This can be helpful both to catch errors and to improve performances because it enable the compiler to optimize some calls. Look at Typed Clojure and PEP -0484: Type hints for python.

Structural typing means to have duck-types: your type is the list of the operations that it supports. Basically you can look at the code of your method and look which operations perform on the parameters. Does it invoke the method foo on the parameter bar? Cool, that means that when this method is invoked I should ensure that bar has some type that has the method foo. It does not matter the name of the class, what it matters is its structure (i.e., the fields and methods it has). In principle a good idea but imho it can get confusing quite soon.

It is supported in Scala, where you can write this:

However it seems verbose, doesn’t it? With structural type inference perhaps we could avoid the verbose type declaration and have some safety at compilation time. At this time I am not aware of any language that get this exactly right. Any suggestion?

Can’t I just have Ruby with a super smart compiler catching my stupid errors?

No, so far you can’t.

People tried to do that: think about the Crystal language, which aims to be a statically typed version of Ruby or Mirah which tried to be a statically typed version of JRuby. It is tempting to think that you can have a nice language as Ruby, just add a little bit of static-typing and get the best of both worlds. The problem is that it does not just work in that way, like the authors of Crystal figured out. Eventually that particular feature ends up having an impact on other aspects of the language and force you to rethink it globally.

I think this is often the case in engineering project: a customer think you can just squeeze another feature in and he does not get the impact on other aspects such security or architectural integrity. We as engineers have to juggle many balls and take decisions considering all of them. Adding one other ball could force us to rethink our strategy or cause all the balls to fall on the ground.

Alternatives to global variables and passing the same value over a long chain of calls

/1 Comment/in , /by

The old, good global variables are the wrong solution to a real problem: you want some information to be available in a large context. In Object-Oriented languages like Java we often do not have something we call a global variable. We instead lie to ourself using public static variables or singletons and denying they are exactly the same thing. No, we are too much object-oriented and too good developers to be using global variables.

Passing a value to all single method call: much better?

Ok, so you repent and decide to give up global variables. What do you do? You pass a value explicitely. Cool. And then you pass it to another method and to another and the same value is propogate over and over until it is available in many places of your application. Much better, eh? You have polluted the signatures of far too many methods and should you ever decide to change the type of the value passed, that would require a lot of work.

fire-bucket-brigade

You have a bunch of methods just passing around the information. Many of them do absolutely nothing with that value, but still need to receive it to be able to pass it along the chain.

Consider a concrete example: I was working on tool for analyzing Java code and some objects required an instance of a TypeResolver: an object that given a name (such as java.lang.String or my.shiny.Class) would provide for them representations of types. Good.

Let’s call the classes using directly a TypeResolver typeResolverUsers. Now, whoever was using the typeResolverUsers (let’s call them the usersOfTypeResolverUsers) needed a TypeResolver to pass it to the typeResolverUsers it was invoking. So each usersOfTypeResolverUsers asked for a TypeResolver at construction time and store it, to later pass it to classes which actually needed it. So now whoever was instantiating one of the usersOfTypeResolverUsers needed to have a TypeResolver  reference. And so on, until far too many classes were aware of the existence of the TypeResolver class.

That is not nice to refactor and it pollutes your methods. I solved this particular case using a Registry. It was not flawless and not so straightforward so I was wondering: is there a better solution?

Another example: Position and WorldSize

Let’s think about another example: we want to represent a Position on a world map (think about my beloved world generator: WorldEngine). Now the Position is of course defined by two values: x and y. However given it is a world map we want to be able to wrap left-right. So to perform certain operations we need to access the world size: if we know that the world is 500 cells wide, when we move from a Position with x=499 to the right we end up having x=0.

In this scenario we could:

  • use a global variable: it means that in our program there is one possible world size. It is stored in some place accessible from the whole application. That works if this assumption holds. If we instead are working on several worlds at the same time we need an alternative.
  • we could store the world size in the Position instance. That means that in every occasion in which we want to create a Position we need a reference to a world size. Given the application deals all the time with Position instances that means that many methods (perhaps most methods) will get a WorldSize instance and pass it down the chain.

I am not happy with neither of these alternatives. I would like to have something that is almost like a global variables but somehow having a limited and controlled scope. Or if you want, I would like to implicitly pass some contextual information without polluting the signature of all methods.

I think that a Position is really defined only by x and y. It needs to know the WorldSize to perform certain tasks, but this is a contextual information, not something that is controlled or owned by Position.

Contextual information: what the heck is that?

For this reason I am working on the concept of contextual information. For now I have implemented it like this:

  • we can declare that certain values could be context dependant: we would specify a name and a type for each of them
  • we could assign values for a certain context-dependant variable according to a dynamic scope: it means that we would make the value available not only in a certain block of statements but also to all the functions and methods invoked in that block, recursively
  • the value would be accessible only in a given thread (yes, ThreadLocal to the rescue)

Examples

This is the current syntax as implemented in my programming language, Turin:

Alternative solutions

There are many ways to make values available to your application without using explicitly global variables. One way it to use a Singleton, another is to declare static variables.

Another solution is the RegistryPattern:

A registry is a global association from keys to objects, allowing the objects to be reached from anywhere. It involves two methods: one that takes a key and an object and add objects to the registry and one that takes a key and returns the object for the key

Pros & Cons

With respect to a global variable we are able to limit the scope of a value, to a context which is not static but dynamic, anyway totally unrelated pieces of code could not mess up with the same global variables we are using.

The main issue with that solution is that we cannot statically determine if a value is available or not in a given context. However we return an Optional leaving the responsibility to the user to verify if the value is present or not.

With respect to the ContextObject pattern we offer type checking: we declared the type of a context value so we can verify that only compatible values are ever assigned to it.