The first time I used Logo, it felt like magic. I could type a short sequence of simple commands, and draw beautifully complex shapes on the screen. In this tutorial, I will show you how to parse and interpret a Logo-like language in just 70 lines of code, and use this example to make broader points on designing and implementing your own language. To do so, we'll use my parsing library, Lark, and Python's turtle module. Let's begin!

(You can skip straight to the finished program, and then come back to see how I wrote it.)

What is a DSL and why should you care

When writing a software project, you might encounter information that your language of choice isn't very good at expressing or representing. It could be data, configuration, a list of commands, etc. Some abstraction might be missing, the language might prove too verbose, or writing the code might be too error-prone because there's no appropriate validation. When that happens, you might benefit from creating your own language, that describes the information in a clean and concise manner. That's called a "Domain-Specific Language", or DSL.

DSLs tend to be small and concise. And like most things, they have both pros and cons.

DSL Pros:

• Complete freedom of expression (within computational bounds)
• Clean and concise code that's easier to read, write, and debug.
• Validation by design
• Dynamic - it can be evaluated in run-time
• Reuse: DSLs can be shared between different languages and platforms (for example: Regular expressions)

DSL Cons:

• Now there's another language to learn (but that's a lazy excuse)
• You won't have direct access to Python's features (or whatever is your host language)
• It's detached from your IDE
• It might be difficult to design and to code

(For a more detailed overview of DSLs pros and cons, visit here)

Overall, there are many great reasons to use DSLs, but many programmers choose to avoid it, rightfully fearing the DSL will add complexity and take a long time to write. But, it doesn't have to be this way...

I'm going to take you step-by-step as we write our own DSL, starting with a naive solution, until we reach a working program with a parser and an interpreter. Hopefully, by the end of it I will convince you that DSLs can be a viable and cost-effective choice for your projects.

Designing a language

In this tutorial, we're going to write a DSL for Python's Turtle module! For those who don't know it, it's a Logo-inspired module for drawing vector graphics using simple commands. The first step when designing a language is to learn about the problem we're trying to solve (the domain). So if you never used the Turtle module, it might be prudent to look at some code, browse the docs, or play around with it a little bit.

To summarize, the Turtle module is used via a series of instructions. We can move the "turtle" on the canvas with spatial instructions (left, right, forward, etc.), we can change the size & color of the turtle's pen, instruct it to move with or without drawing, or otherwise alter the state of the turtle and/or window.

The next step is to choose what your language is going to do: Which features or concepts it's going to support, and what you will leave out. To keep this tutorial short, we're going to support only a small subset of instructions:

1. Left, right, forward and backward
2. Color
3. Repeat  - since we can't use Python's "for" directly
4. Fill  - activates filling mode. Chosen to demonstate structure

Now that we know the contents of the language, we can move on to the third step: Choosing a syntax. This step is part common-sense, part art, and part subjective opinion. However, I do believe there are some guidelines that are innately true.

Guidelines to choosing syntax for a language:

• Use popular idioms, based on your target audience. By using structures, keywords and symbols everyone already knows, you cut the time it takes to learn your language.
• Brevity of expression should correlate to the size of the language. For small languages, it's okay to use a lot of shorthands (see: regexps), but when the language gets bigger, opt for clarity instead (aka don't be Perl).
• Design for innate correctness. Try to design the language so it will promote good practices, and discourage abuse.

For example, Python was aimed at C programmers (among others), so it borrowed C syntax like += for in-place addition ,  and keywords like break and continue.

For our Turtle DSL, I will borrow my idioms and syntax from Logo, but with a modern twist. We'll use {curly-braces} for code blocks. And since we'll be designing a very small, interpreted language, we can make our basic commands one-lettered.

Here's how a program looks in my imaginary Turtle Language:

c green blue    # fg & bg colors
fill { repeat 36 {
  f200 l170     # forward & left
}}

But it's not going to be imaginary for long! Let's move on to the practical side of things.

Writing the grammar

Step 1) EBNF

Now that we know what our language looks like, we can to write a formal grammar for it. Later, we will feed our grammar to the parser, so it will know how to parse free-form text written in our language into a structured parse-tree that's easy to work with programmatically.

The standard way to write grammars is in EBNF form, and that's what we'll do in this tutorial. EBNF grammars are basically a hierarchy of rules and strings of the form:

name: production

Where production is a list of names and values.

Or informally:

rule: rule1, "keyword", rule2, rule3, ..

Rules can be recursive, but it's better to describe loops with repetition-operators. For example, this is how I would define Python's dictionary syntax in EBNF:

dict: "{" dict_item* "}"
dict_item: name ":" value
...

This is enough to allow us to describe an instruction in Turtle Language:

instruction: "f" number
           | "b" number
           | "l" number
           | "r" number
           | "c" color [color] // bgcolor is optional
           | "fill" code_block
           | "repeat" number code_block

code_block: "{" instruction+ "}"  // one or more instructions

This is an accurate and fairly succinct description of our syntax. We could however make it a little shorter, by avoiding repetition.

instruction: ("f"|"b"|"l"|"r") number
           | "c" color [color]
           | "fill" code_block
           | "repeat" number code_block

code_block: "{" instruction+ "}"

This variation is equivalent to the first one, just a little shorter.

You may have noticed our grammar contains a recursion between "code_block" and "instruction". That's totally fine, this is what parsers live for.

We still haven't defined "number" and "color". We'll do that next.

Step 2) Lark

So far, everything we did was fairly agnostic of a specific parsing library. But now is a good time to introduce Lark.

Lark is an open-source parsing library I spent the last month writing. I know, there are dozens of other parsing libraries. Why introduce yet another one? Here's why:

Lark uses the Earley parsing algorithm, a dynamic parsing algorithm that can handle all context-free grammars, including ambiguous grammars. It also supports a scannerless mode, which means terminals (tokens) are resolved by Earley at parse-time. The end result is that when you write your grammar with Lark, you don't have to worry about restrictions or state-machines. All grammar structures are allowed. If your grammar makes logical sense, Lark can parse it.

Lark is the only library that can make this claim. It also accepts grammars in a convenient EBNF form. It supplies a library of common terminals (i.e. regexps), to save its users from re-inventing the wheel in every grammar. And it can build a parse-tree automatically for every grammar.

Here ends the sales pitch, although I could go on. Let's look at how our grammar will look like in Lark, and I will follow with a thorough explanation:

start: instruction+

instruction: ("f"|"b"|"l"|"r") NUMBER
           | "c" COLOR [COLOR]
           | "fill" code_block
           | "repeat" NUMBER code_block

code_block: "{" instruction+ "}"

COLOR: ("a".."z")+
NUMBER: ("0".."9")+
WHITESPACE: (" " | "\n")+
%ignore WHITESPACE

(If you are following this by trying the code, that's awesome! Don't forget to escape the '\n'.)

In the first line, we tell Lark that our program is basically a list of instructions.

The next part is literally a copy-paste of our EBNF definition from above, only we change "color" and "number" to their terminal form, and define them.

When names are written in uppercase in Lark, they are treated as terminals. Terminals are a little like rules: They also match input by combining smaller particles. But while rules match structure, terminals match strings. If we defined COLOR as a rule instead (lowercase color), the parser will create structure where it makes no sense (For example, Tree("r", "e", "d") instead of just the string "red").

Another thing about terminals is that they are greedy, which is just what we need in this case.

Then finally, the last line tells lark to ignore whitespace.

c blue f 20 // we omit bgcolor, and run forward(20)