<p>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 <a href="https://github.com/bbrk24/Trilangle/blob/a0826901a05aa33693ddaa87e95c7fa393b48907/src/thread.cpp#L156" rel="noreferrer">undefined behavior</a> and <a href="https://codegolf.stackexchange.com/a/257836/106545">a difference between what the interpreter does vs what's part of the language</a>, I don't have a formal spec written. How could I go about writing up a formal spec for the language?</p>

<specification>
How do I write a spec for an existing language?
CC BY-SA 4.0
2023-05-31T15:43:59.867Z
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.
Bbrk24
<h1>The Formal Grammar</h1>
<p>As the question didn't limit itself to just semantics, I'll like to answer from a syntax point of view.</p>
<p><a href="https://en.wikipedia.org/wiki/Formal_grammar" rel="nofollow noreferrer">The formal grammar</a> 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 <a href="https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form" rel="nofollow noreferrer">Backus–Naur form
</a>, which can be thought of as a meta grammar for writing a formal grammar.</p>
<p>For an example of a real life formal grammar, the <a href="https://docs.python.org/3/reference/grammar.html" rel="nofollow noreferrer">Python full grammar specification</a> may prove useful, though it is pretty long.</p>
<p>Additionally, it may be helpful to have a syntax reference that explains just the syntax of the language.</p>

CC BY-SA 4.0
2023-05-31T16:51:23.350Z
2023-05-31T16:51:23.350Z
FireTheLost
CC BY-SA 4.0
2023-05-31T17:17:40.983Z
While this might be a good point in general, an esolang with single-character instructions is not exactly conducive to BNF-style grammars.
Bbrk24
CC BY-SA 4.0
2023-05-31T17:27:47.627Z
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.
FireTheLost
<h1>Frame Challenge: Do you need one?</h1>
<p>Lots of languages get by just fine without a formal spec. Raku is formally defined to be &quot;the semantics that pass the Raku test suite&quot;. There's no specification document; it's just code that checks conformance. Ruby is defined even less formally, as &quot;whatever the official MRI interpreter does at this moment&quot;. Especially if what you're writing is a hobby language, a good case could be made for defining the spec as &quot;what my interpreter does&quot;, or &quot;things that pass my tests&quot; if the tests are thorough enough.</p>
<p>As a side note: &quot;undefined behavior&quot; 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 &quot;panics&quot; rather than &quot;undefined behavior&quot;.</p>

CC BY-SA 4.0
2023-05-30T23:27:13.787Z
2023-05-30T23:27:13.787Z
Silvio Mayolo
CC BY-SA 4.0
2023-05-30T23:40:13.980Z
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.
Bbrk24
CC BY-SA 4.0
2023-05-31T00:19:42.847Z
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.
Pseudonym
<p><strong>tl;dr</strong>: Don't sweat it, but still do it.</p>
<p>As someone currently writing two(!) <a href="https://docs.yzena.com/yc/master/yao/spec.html" rel="nofollow noreferrer">language</a> <a href="https://docs.yzena.com/yc/master/yvm/spec.html" rel="nofollow noreferrer">specs</a> for languages that nobody will likely use, I agree with <a href="https://languagedesign.stackexchange.com/users/89/kaya3">@kaya3</a>: write the spec as a check for yourself.</p>
<p>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.</p>
<p><strong>As for how to get started</strong>: don't sweat it too much. Just document random things in a random order. Copy+paste will help you reorder things later.</p>
<p>This works especially well on things like specifications because one section that follows another does <em>not</em> have to be related to the previous section. The writing does not have to transition smoothly.</p>
<p>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.</p>
<p>I think you'll be thankful to just have those notes, no matter their quality.</p>

CC BY-SA 4.0
2023-05-31T03:32:11.897Z
2023-05-31T03:32:11.897Z
Gavin D. Howard
<p>Broadly, there are two ways to specify a programming language:</p>
<ul>
<li><a href="https://en.wikipedia.org/wiki/Denotational_semantics" rel="noreferrer">Denotational semantics</a> which directly gives meaning to terms in the language and says what terms have the same meanings as what other terms;</li>
<li><a href="https://en.wikipedia.org/wiki/Operational_semantics" rel="noreferrer">Operational semantics</a> which define the behaviour of programs in terms of an execution model, i.e. how each term in the language should be executed on some <a href="https://en.wikipedia.org/wiki/Abstract_machine" rel="noreferrer">abstract machine</a> or formalised <a href="https://en.wikipedia.org/wiki/Virtual_machine" rel="noreferrer">virtual machine</a>.</li>
</ul>
<p>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.</p>
<p>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.</p>
<p>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 <code>a() + b()</code> and your interpreter consistently evaluates <code>a()</code> before <code>b()</code>:</p>
<ul>
<li>If this consistent order is supposed to be part of the language specification, write something like: <em>&quot;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.&quot;</em></li>
<li>If this order is supposed to just be an implementation detail, write something like: <em>&quot;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.&quot;</em></li>
<li>Or if even the fact that the operands <em>are</em> evaluated is an implementation detail (i.e. you don't care about side-effects, or there are none): <em>&quot;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.&quot;</em></li>
</ul>
<p>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 <em>more</em> words to specify less about how the program is executed, so you aren't necessarily wasting effort by specifying too precisely.</p>
<p>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 &quot;virtual machine&quot; described in your spec, only that when it executes programs they must have the same behaviour <em>as if</em> they were executed by such a machine. You don't need to keep saying the words &quot;as if&quot; 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.</p>
<hr />
<h2>Why have a spec?</h2>
<p>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.</p>
<p>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.</p>
<p>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 &quot;bugs&quot; 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.</p>
<p>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 <em>thought</em> the interpreter would do, so chances are, the spec is more accurate to your intent than the implementation is.</p>

CC BY-SA 4.0
2023-05-31T00:13:50.253Z
2023-05-31T00:26:43.227Z
2023-05-31T00:26:43.227Z
kaya3
# How do I write a spec for an existing language?
Posted by: username_0 on 2023-05-30
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](https://github.com/bbrk24/Trilangle/blob/a0826901a05aa33693ddaa87e95c7fa393b48907/src/thread.cpp#L156) and [a difference between what the interpreter does vs what's part of the language](https://codegolf.stackexchange.com/a/257836/106545), I don't have a formal spec written. How could I go about writing up a formal spec for the language?
**Tags:** specification
> **Comments:**
> **username_0**: 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.  
---
## 4 answers
### Answer by username_5 on 2023-05-31. Score: 7
Broadly, there are two ways to specify a programming language:

* [Denotational semantics](https://en.wikipedia.org/wiki/Denotational_semantics) which directly gives meaning to terms in the language and says what terms have the same meanings as what other terms;
* [Operational semantics](https://en.wikipedia.org/wiki/Operational_semantics) which define the behaviour of programs in terms of an execution model, i.e. how each term in the language should be executed on some [abstract machine](https://en.wikipedia.org/wiki/Abstract_machine) or formalised [virtual machine](https://en.wikipedia.org/wiki/Virtual_machine).

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.
---
### Answer by username_2 on 2023-05-30. Score: 4
# 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".
> **Comments:**
> **username_0** (2023-05-30): 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.  
> **username_3** (2023-05-31): 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.  
---
### Answer by username_4 on 2023-05-31. Score: 4
**tl;dr**: Don't sweat it, but still do it.

As someone currently writing two(!) [language](https://docs.yzena.com/yc/master/yao/spec.html) [specs](https://docs.yzena.com/yc/master/yvm/spec.html) for languages that nobody will likely use, I agree with [@kaya3](https://languagedesign.stackexchange.com/users/89/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.
---
### Answer by username_1 on 2023-05-31. Score: 2
# 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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_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](https://docs.python.org/3/reference/grammar.html) 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.
> **Comments:**
> **username_0** (2023-05-31): While this might be a good point in general, an esolang with single-character instructions is not exactly conducive to BNF-style grammars.  
> **username_1** (2023-05-31): 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.  
---
