L0) The Map of Formalisms

How the Tools of Language Theory Fit Together

The L series consists of twelve articles on formal languages. Twelve islands in an archipelago. Each island is a formalism — a mathematical tool for thinking about languages. Some describe syntax (what is valid?), others semantics (what does it mean?), and still others translation or concurrency. Between the islands, there are bridges: each formalism builds upon, extends, and completes the previous ones. This article is the map — to be read before the journey.

Why a Map?

A composer writing for I2 manipulates a grammar: rules that generate music. But behind this grammar lie dozens of formal concepts — Chomsky’s hierarchy, Abstract Syntax Trees (ASTs), operational semantics, mildly context-sensitive languages…

The L series explores them one by one. But without an overview, one risks getting lost. Which article should be read first? Why is it necessary to understand context-free grammars before semantics? Why does polymetry require concurrency models?

This map answers these questions. It shows the four levels of the series — and above all, it shows why BP3 needs each of them.

The Overview: Four Levels

 

flowchart TD
    subgraph E1["🧩 Level 1 — SYNTAX"]
        direction LR
        L1["L1
Chomsky
Hierarchy"]
        L2["L2
Context-Free
Grammars"]
        L3["L3
EBNF"]
        L4["L4
AST"]
        L1 --> L2 --> L3 --> L4
    end

    subgraph E2["🔍 Level 2 — SEMANTICS"]
        direction LR
        L5["L5
Three
Semantics"]
        L6["L6
SOS"]
        L7["L7
Denotational"]
        L8["L8
Axiomatic"]
        L5 --> L6
        L5 --> L7
        L5 --> L8
    end

    subgraph E3["🚀 Level 3 — EXTENSIONS"]
        direction LR
        L9["L9
MCSL"]
        L10["L10
Attribute
Grammars"]
    end

    subgraph E4["🔄 Level 4 — TRANSLATION & CONCURRENCY"]
        direction LR
        L11["L11
Advanced
Semantics"]
        L12["L12
Petri / CCS"]
    end

    E1 --> E2
    E1 --> E3
    E2 --> E4
    E3 --> E4

 

Each level poses a fundamental question:

Level Question Articles
1 — Syntax “What is valid?” L1, L2, L3, L4
2 — Semantics “What does it mean?” L5, L6, L7, L8
3 — Extensions “How to go beyond?” L9, L10
4 — Translation & Concurrency “How to translate and parallelize?” L11, L12

Level 1 — Syntax: What is valid?

The first question to ask when faced with a language — whether it’s a programming, musical, or natural language — is: which sequences of symbols are valid? The first four articles build the tools to answer this.

L1 lays out the fundamental framework. Noam Chomsky classified all possible languages into four types, from the simplest (Type 3, regular languages — think regular expressions) to the most complex (Type 0, recursively enumerable languages — as powerful as a Turing machine). Each type corresponds to a machine capable of recognizing it: finite automaton, pushdown automaton, linearly bounded automaton, Turing machine. This is the cadastre of languages.

L2 zooms in on Type 2, the core of almost everything. Context-Free Grammars (CFGs) allow for nesting: parentheses within parentheses, structures within structures. This is what enables BP3 to nest sub-grammars within grammars, and what makes music more than just a flat sequence of notes.

L3 provides the notation for writing these grammars. EBNF (Extended Backus-Naur Form) is to grammar what musical notation is to music: a language for writing a language. It is in EBNF that the formal specification of BP3 is written.

L4 shows what remains after parsing. When a parser reads a BP3 text, it produces an AST — a tree that captures the structure without the syntactic noise. It is this tree that the BP2SC transpiler will traverse to produce SuperCollider code.

Application to Music

Chomsky’s hierarchy directly illuminates the limitations of each musical format:

  • MIDI is essentially a Type 3 (regular) language — a sequence of events without nesting. This is what makes it simple but expressive only for flat sequences.
  • MusicXML is a Type 2 language — its XSD schema describes a nested tree structure. This is what allows it to represent musical notation with its measures, voices, and dynamics.
  • BP3 is a Type 2+ language — context-free at its base, but with mechanisms (flags, variables) that push it beyond.

 

flowchart LR
    T["BP3 Text"] -->|"Grammar
(EBNF)"| P["Parser"]
    P -->|"Syntactic
Analysis"| AST["AST
(25 nodes)"]
    AST -->|"Transpiler
BP2SC"| SC["SuperCollider
Code"]

 

Level 2 — Semantics: What does it mean?

Having valid syntax is not enough. The sentence “the note plays the silence” is syntactically correct but semantically absurd. The following four articles address the question of meaning.

L5 presents the three fundamental approaches. Since the 1960s, computer science has developed three ways to give meaning to programs:

  • Operational: one describes how the program executes, step by step. “To evaluate 2 + 3, one adds and obtains 5.”
  • Denotational: one describes what the program computes, like a mathematical function. “2 + 3 denotes the value 5.”
  • Axiomatic: one describes what can be proven about the program. “If x > 0 before, then x + 1 > 1 after.”

Three perspectives on the same object — like an architect (plan), a mason (construction), and an inspector (verification) looking at the same building.

 

flowchart TD
    Q["A program
P"]
    OP["🔧 Operational
'How does it execute?'
→ Transition rules"]
    DN["📐 Denotational
'What function does it compute?'
→ Mathematical domains"]
    AX["✅ Axiomatic
'What can be proven?'
→ Pre/post-conditions"]

    Q --> OP
    Q --> DN
    Q --> AX

 

L6 develops Plotkin’s operational approach. Structural Operational Semantics (SOS) formalizes program execution through inference rules. It is the ideal tool for describing BP3’s five derivation modes (ORD, RND, LIN, SUB, SUB1) — each defining how a grammar generates musical sequences.

L7 models programs as mathematical functions. Elegant, but it runs into a problem: stochasticity. BP3 uses random draws (RND mode, decremental weights) — a BP3 program does not compute one sequence but a set of possible sequences. Classical denotational semantics struggles to capture this probabilistic nature.

L8 allows for proving properties. Hoare logic states: “If this condition is true before execution, then this other condition will be true after.” For BP3, this is useful for proving invariants — for example, that a grammar with certain flags always produces sequences of bounded length. But limitations quickly appear when faced with non-determinism.

Why BP3 Needs SOS

Of the three approaches, operational semantics is the most suitable for BP3. Why? Because BP3 is a rewriting system: one starts with an initial symbol, applies rules, and gradually obtains a musical sequence. Each rewriting step is a transition — exactly what SOS formalizes. Article L6 constructs the rules that make this intuition rigorous.

Level 3 — Beyond Chomsky: When Type 2 Is No Longer Enough

Context-free grammars (Type 2) are powerful, but they have limitations. Two articles explore what happens when more is needed.

L9 explores the area located between Type 2 and Type 1: mildly context-sensitive languages (MCSL). This area hosts formalisms invented for natural language — TAG (Tree-Adjoining Grammars), CCG (Combinatory Categorial Grammars), MCFG (Multiple Context-Free Grammars) — but which apply remarkably well to music. Steedman (1984) used CCGs to formalize jazz improvisation. And BP3, when its flags are bounded, is precisely located in this mildly context-sensitive zone.

L10 enrich syntactic trees with computed properties. Invented by Knuth in 1968, they allow attaching information (type, value, constraint) to each node of the tree. BP3’s flags function exactly like “global inherited attributes”: they carry information across the derivation tree, modifying the behavior of the rules. Understanding attribute grammars means understanding why flags allow BP3 to go beyond Type 2.

 

flowchart LR
    T3["Type 3
Regular
(MIDI)"]
    T2["Type 2
Context-free
(MusicXML, BP3 base)"]
    MCSL["MCSL
Mildly CS
(BP3 + bounded flags)"]
    T1["Type 1
Context-sensitive
(BP3 + multi-LHS)"]
    T0["Type 0
Turing-complete
(BP3 + unbounded flags)"]

    T3 --> T2 --> MCSL --> T1 --> T0

    style MCSL fill:#e8f5e9,stroke:#2e7d32,stroke-width:3px

 

BP3’s Position

The key result (demonstrated in R1):

  • Without flags: BP3 is context-free (Type 2) — Theorem 4.1
  • With bounded flags: BP3 is mildly context-sensitive — Theorem 4.2
  • With multi-symbol LHS: BP3 reaches Type 1 — Proposition 4.1
  • With unbounded flags: BP3 is probably Turing-complete — Conjecture 4.1

This is an elegant result: the same mechanisms that make BP3 musically expressive (the flags) are those that elevate it in Chomsky’s hierarchy.

Level 4 — Translation and Concurrency: The Final Pieces

The fourth level covers two problems that classical syntax and semantics are not sufficient to address: translating one language into another, and executing multiple processes in parallel.

L11 presents three additional semantics:

  • Translational semantics defines the meaning of a program by its translation into another language. This is exactly what BP2SC does: the meaning of a BP3 program is given by the SuperCollider code it produces. Morris’s diagram (1969) captures this idea:

 

flowchart LR
    SRC["BP3
Program"]
    IR["Intermediate
Representation
(AST)"]
    TGT["SuperCollider
Code"]

    SRC -->|"Analysis
(front-end)"| IR
    IR -->|"Generation
(back-end)"| TGT
    SRC -.->|"Translational
Semantics"| TGT

 

  • Process semantics models systems that communicate and execute in parallel. This is the formal basis for polymetry — when BP3 superimposes several independent temporal flows.
  • Algebraic semantics defines operations on programs as an algebraic structure (monoid, group). Useful for musical transformations (transposition, inversion).

L12 provides the concrete tools for concurrency. Petri nets model systems with shared resources through tokens circulating in a graph. Process algebras (Milner’s CCS, Hoare’s CSP) formalize communication between parallel processes via bisimulation — two processes are “equivalent” if they cannot be distinguished from the outside.

Polymetry as a Concurrency Problem

BP3’s polymetry — the ability to superimpose temporal flows at different ratios (3 against 4, 5 against 7) — is formally a problem of parallel composition. Article L12 shows how the tools of concurrency theory (CCS’s | operator, Petri net synchronization) precisely capture this superposition.

The Synthesis: Why BP3 Needs All This

Each formalism in the L series illuminates a different aspect of BP3. The following table summarizes these connections:

Formalism Question Article BP3 Application
Chomsky’s Hierarchy Where is BP3 located? L1 Position in the hierarchy (Type 2 → MCSL → Turing)
Context-Free Grammars What is BP3’s basis? L2 Rewriting rules, recursion
EBNF How to write the grammar? L3 Formal specification of BP3
AST What tree does the parser produce? L4 25 node types, transpiler pipeline
Operational Semantics How do the rules execute? L6 5 formalized derivation modes
Denotational Semantics What distribution does BP3 compute? L7 Limitations with stochasticity
Axiomatic Semantics What can be proven about BP3? L8 Termination, bounded length
MCSL (TAG, CCG) Why does BP3 go beyond Type 2? L9 Bounded flags → mildly CS
Attribute Grammars What are flags formally? L10 Flags ≈ global inherited attributes
Translational Sem. What does “translate to SC” mean? L11 BP2SC = translational semantics
Process Sem. How to formalize polymetry? L11 Superposition of flows = parallel composition
Petri Nets / CCS What model for parallelism? L12 Polymetry as a temporal Petri net

The final diagram shows the complete cycle — from BP3 grammar to sound:

 

flowchart LR
    G["BP3
Grammar"] -->|"L2, L3"| P["Parsing"]
    P -->|"L4"| AST["AST"]
    AST -->|"L6"| SEM["Operational
Semantics"]
    SEM -->|"L11"| TR["Transpilation
(BP2SC)"]
    TR -->|"L12"| SON["Sound
(polymetry)"]

    style G fill:#fff3e0,stroke:#e65100
    style SON fill:#e8f5e9,stroke:#2e7d32

 

Recommended Reading Paths

The Index offers several thematic paths. Here is an additional one, specific to the L series:

Minimalist Path (the bare essentials for understanding BP3)

L1 → L2 → L4 → L5 → L6

Five articles. With these, you understand the syntactic basis (L1-L2), the data structure of the transpiler (L4), and the formalization of execution (L5-L6).

Complete Path (the entire series)

L1 → L2 → L3 → L4 → L5 → L6 / L7 / L8 → L9 → L10 → L11 → L12

The three semantics (L6, L7, L8) can be read independently after L5. The extensions (L9, L10) complete the syntax. L11 and L12 close the loop with translation and concurrency.

“BP3 in the Hierarchy” Path

L1 → L2 → L9 → L10

Four articles to understand where BP3 is located and why flags elevate it in the hierarchy.

Compact Glossary

Term Definition Article
AST (Abstract Syntax Tree) Tree representing the structure of a program, without syntactic noise L4
CFG (Context-Free Grammar) Grammar whose rules replace a symbol independently of context L2
CCS (Calculus of Communicating Systems) Process algebra for modeling concurrency L12
EBNF (Extended Backus-Naur Form) Standardized notation for writing grammars L3
Flag Global variable in BP3 that modifies the behavior of rules B4
MCSL (Mildly Context-Sensitive Language) Language between Type 2 and Type 1 — area of TAG, CCG, and BP3+flags L9
Parsing Syntactic analysis: transforming text into a tree (AST) L4
Petri Net Model of a concurrent system using tokens and transitions L12
Operational Semantics Giving meaning to a program by describing its execution L6
SOS (Structural Operational Semantics) Structural variant of operational semantics (Plotkin, 1981) L6
TAG (Tree-Adjoining Grammar) Grammar that operates by tree adjoining — mildly context-sensitive L9
Transpiler Program that translates source code into another source language B7

To Go Further

  • Series Index — Complete navigation through the entire corpus
  • I2 — The BP3 system in detail
  • M1 — MIDI analyzed with the tools of the L series
  • M2 — MusicXML formally analyzed
  • Glossaire — The 60+ terms of the complete corpus

Tags : #formal-languages #map #navigation #BP3 #overview