Language engineering 101

Language engineering is part of computer science. It has always been. Unfortunately it is not part of the standard curriculum when it comes to software engineering. You are often taught how to write code in a specific language. How to organize your code. How to use/build executables and libraries on top of a language. How to distribute them. You get familiar with the syntax, the OOP stuff, various abstractions etc. but you never go deeper. You never learn how programming languages actually work. Your knowledge stays mostly high level.

On the other hand working in the robotics domain often requires extensive knowledge in the language engineering domain. In robotics it is all about languages. We model the behavior of a robot with a language. We commission it, we simulate it, we build applications on top of it, we sell it, we make our career on top of it. And all this is possible only because some people have once learned how to design and implement a programming language. These guys are the true heroes of the industry!

The first step in this direction is to define the language. This means: defining the syntax (keywords and punctuation) for statements, expressions, functions and programs. The language design also includes the underlying meaning (semantics) behind each language construct.

You start with examples that illustrate the important features of the language. Then you provide variations of the examples. All this allows you to find inconsistencies in your initial idea. This is how you come up with patterns that eventually become the rules behind the language grammar.

There are two types of rules:

lexical rules - define the keywords, operators, identifiers, literals

syntax rules - define how keywords, operators, identifiers and literals can be combined to form statements, expressions, functions or programs.

Once you have an example for everything you want to do, write a language specification describing the rules, the operator precedence and associativity following the principle of least surprise. This will make your language attractive.

Next you define the control flow - how the code is executed from one statement to the next. Here you should follow the established principles again and only emphasize on the domain-specific portion of your design. Do not reinvent the wheel for common conditional and repetitive statements. Define the syntax for a function (subroutine) call, statements and expressions. How to tell the difference between statements and expressions? Simple. All expressions produce a result.

Next define the data types:

built in - these are immutable types with a fixed meaning (bool, int, float, string).

composite types - combine multiple values in a single type (array, struct)

domain specific types - help you support the target domain (3D vector, 4x4 matrix)

Program structure is equally important - where the program execution starts? How is the code compiled or interpreted? How are different modules loaded? How do you declare variables? How to define data types? How values are expressed? What is the nesting level?

These are some of the problems related to language design. It is better to solve them before the actual implementation starts.

Once all this is clear we can start recognizing the syntax.

What does this mean?

It means reading the characters from the input stream and figuring out how they are grouped together. Groups of characters can form keywords, identifiers, operators or literals. Usually some pattern matching is used at this level. The goal is to identify all possible lexemes (adjacent characters that form a single entity). The lexeme + the bundle of information (category, offset from the beginning, length, line number, column number etc.) related to it is known as a token. The token is a structure that contains all this data. The component that recognizes all the lexemes and delivers the list of tokens is known as a lexer.

Once the tokens are built the parser kicks in.

It recognizes the larger constructs in the programming language. Essentially it builds a structure containing the tokens and sub structures for every language construct. For every construct there is a different structure. A different type. The collection of all structures eventually forms a tree. This tree is known as a parse tree.

The parse tree is the fundamental data model that allows computers to work with languages.

Hints:

Syntax errors are reported at the level of the lexer and the parser.

Semantic errors are reported by a semantic analyzer once the parse tree is built.

Text highlighting relies on the category of the tokens.

Code completion works by finding the next possible token at the caret position.

This is a pretty simplified overview but it gives you the overall idea.

Armed with all this knowledge, lets see how languages are actually implemented from this point on.

Once the language is defined and you can parse source files you have a number of options to implement it:

1. pure interpreter - transforms the parse tree to an abstract syntax tree (AST) to run the code. ASTs tend to be shallower so they are faster to traverse. Running the code means visiting each and every node of the AST and executing the instructions inside. These interpreters are relatively easy to build but are known for their bad performance.

2. byte code compiler/interpreter - the compiler transforms the parse tree to an AST. Then uses the AST to lower the code to bytecode instructions. The bytecode is abstract (not specific to any CPU). The interpreter simply runs the bytecode instructions one by one. These interpreters offer moderate performance but are far more complex to build.

3. native compiler - transforms the parse tree to an AST. Then uses it to lower the code to machine instructions specific to a particular CPU. The compiled code has the best performance but a compiler is extremely complex to build.

4. transpiler - transforms the parse tree to an AST. Then uses the AST to generate code written in another language. These are relatively easy to build. Performance is usually not a concern.

In Process Simulate SCL is implemented as a pure interpreter. So by definition you should not expect great performance from it. Especially with long loops or large function blocks. Still it offers decent performance for well scoped daily tasks. I tried to put SCL into context with other well known languages on the picture below:

Nowadays SCL is more similar to shell scripts.

If I have to compare the performance, a bytecode interpreter can be up to 40 times faster than a pure interpreter. Native code can be up to 100 times faster than a bytecode interpreter.

But Java, .Net, Python are not that slow actually?!? Everybody uses them. How do they achieve the performance that they offer?

Well. There is also the concept of Just-In-Time compilation (JIT compiler)

This is the process of converting the bytecode instructions to native instructions at runtime - while the code runs. Usually this is done for code that runs very frequently (hot paths)

A quality compiler / interpreter can take years to develop. I believe this is not a surprise to anybody. With SCL we are just touching the top of the iceberg. Imagine having a bytecode interpreter instead. It will solve the performance bottlenecks that we currently have. Now with AI this might be more achievable than expected ...