10
$\begingroup$

I have a working interpreter for my language Trilangle, and I have a decent but informal grasp of the language's semantics. Though I've alluded to undefined behavior and a difference between what the interpreter does vs what's part of the language, I don't have a formal spec written. How could I go about writing up a formal spec for the language?

$\endgroup$
1
  • $\begingroup$ I feel like this isn’t a perfect duplicate of the other question: that one is asking about the format, while I was trying to ask about the process. “Do you need to?” isn’t an answer to the other one, for example. I’ll admit that the questions are similar, though. $\endgroup$
    – Bbrk24
    May 31, 2023 at 15:43

4 Answers 4

7
$\begingroup$

Broadly, there are two ways to specify a programming language:

Since you have an interpreter already, the implementation of the interpreter already describes a virtual machine that can execute programs in your language. The interpreter has some data structures representing the program's state (typically the evaluation context, plus values passed between functions in the interpreter), and for each type of AST node, it has instructions for how the program's state changes when that node is executed.

So, operational semantics are probably the way to go. You can go more or less formal, but a full specification for your language can consist of essentially translating the core of the interpreter into human language: describe what the program state consists of, and how each kind of statement or expression affects that program state.

If there is any part of that core which you don't want to be specified, simply don't include it in the spec. However, do write enough to specify the parts of the behaviour you do want to specify. For example, if your language has expressions like a() + b() and your interpreter consistently evaluates a() before b():

  • If this consistent order is supposed to be part of the language specification, write something like: "a binary operator expression evaluates its operands from left-to-right, then the value of the expression is computed by applying the operator to those values."
  • If this order is supposed to just be an implementation detail, write something like: "a binary operator expression evaluates its operands in an unspecified order, then the value of the expression is computed by applying the operator to those values."
  • Or if even the fact that the operands are evaluated is an implementation detail (i.e. you don't care about side-effects, or there are none): "the value of a binary operator expression is the result of applying the operator to the values of the operands. An implementation may optionally omit evaluating the operands, if it determines that their values are not needed for the computation."

It's fine to be overly specific, particularly in your first draft ─ it may be easier to start by just describing exactly how your interpreter works, and then modifying the spec later as you decide which parts of it are implementation details. You may notice from above that it often takes more words to specify less about how the program is executed, so you aren't necessarily wasting effort by specifying too precisely.

It's also worth adding that this kind of specification doesn't literally mean that an implementation of your language must be a direct translation of the "virtual machine" described in your spec, only that when it executes programs they must have the same behaviour as if they were executed by such a machine. You don't need to keep saying the words "as if" all the way through your specification, as this should be understood by readers; but it probably won't hurt to add one paragraph somewhere making this explicit.


Why have a spec?

Silvio Mayolo's answer argues that you may not need one. I would say it's a good idea to have a spec, even if your language has only one implementation and it's maintained by you alone.

A spec is a source of truth for what the correct behaviour of a program is. It makes clear to users of the language which behaviours of your interpreter they can rely on in future versions, and which they shouldn't.

It can also be used to judge whether a suspected bug in your interpreter is really a bug. If I have a program in your language which seems to be misbehaving, you probably don't want me to just always file a bug report on your issue tracker, because many such "bugs" are really caused by people like me thinking that the language should do something different to what you think it should do. But if you have a spec, then I can compare your interpreter's behaviour with the spec and make an objective judgement about whether the observed behaviour contradicts the spec.

If there is a difference between the observed and specified behaviour, then either the interpreter or the spec needs to be fixed. But the spec describes what you thought the interpreter would do, so chances are, the spec is more accurate to your intent than the implementation is.

$\endgroup$
4
$\begingroup$

Frame Challenge: Do you need one?

Lots of languages get by just fine without a formal spec. Raku is formally defined to be "the semantics that pass the Raku test suite". There's no specification document; it's just code that checks conformance. Ruby is defined even less formally, as "whatever the official MRI interpreter does at this moment". Especially if what you're writing is a hobby language, a good case could be made for defining the spec as "what my interpreter does", or "things that pass my tests" if the tests are thorough enough.

As a side note: "undefined behavior" is usually a term for things the interpreter does not or cannot catch and therefore is permitted to assume will not occur. Since you seem to be detecting those errors in your interpreter, I might be more inclined to call them "panics" rather than "undefined behavior".

$\endgroup$
2
  • $\begingroup$ I will point out that these warnings are all gated behind the -w flag. Some of these are substantially slower than not checking — most notably, checking for overflow on multiplication requires division, since C++ doesn’t have fullwidth/reporting-overflow operations the way e.g. Swift does. $\endgroup$
    – Bbrk24
    May 30, 2023 at 23:40
  • $\begingroup$ Counterpoint: Even if you don't write a full spec, attempting to define the semantics of a language formally often reveals things you didn't consider when implementing the language. Sometimes that's a bug in the implementation, and sometimes it's a general case of a feature that you didn't consider because it didn't occur to you. $\endgroup$
    – Pseudonym
    May 31, 2023 at 0:19
4
$\begingroup$

tl;dr: Don't sweat it, but still do it.

As someone currently writing two(!) language specs for languages that nobody will likely use, I agree with @kaya3: write the spec as a check for yourself.

I also want to add that there will be times when the implementation does something that the spec says nothing about. This is still useful because it shows you the blind spots in your language's design.

As for how to get started: don't sweat it too much. Just document random things in a random order. Copy+paste will help you reorder things later.

This works especially well on things like specifications because one section that follows another does not have to be related to the previous section. The writing does not have to transition smoothly.

In addition, the wordsmithing does not have to be great or even good. The spec can just be a bunch of notes you write to yourself that you clean up later if necessary.

I think you'll be thankful to just have those notes, no matter their quality.

$\endgroup$
2
$\begingroup$

The Formal Grammar

As the question didn't limit itself to just semantics, I'll like to answer from a syntax point of view.

The formal grammar is not related to the semantics of the language but is nevertheless an important aspect of a language specification. The formal grammar is the set of rules that explain how to get each possible, valid input code string for the specified language. A popular method of writing a formal grammar is the Backus–Naur form , which can be thought of as a meta grammar for writing a formal grammar.

For an example of a real life formal grammar, the Python full grammar specification may prove useful, though it is pretty long.

Additionally, it may be helpful to have a syntax reference that explains just the syntax of the language.

$\endgroup$
2
  • $\begingroup$ While this might be a good point in general, an esolang with single-character instructions is not exactly conducive to BNF-style grammars. $\endgroup$
    – Bbrk24
    May 31, 2023 at 17:17
  • $\begingroup$ True, I was thinking pretty generally when I answered. That said, I would really like to see a formal grammar for an esolang. That would be pretty neat. $\endgroup$ May 31, 2023 at 17:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .