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 layers of the series — and above all, it shows why BP3 needs each of them.

The Overview: Four Layers

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

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

    subgraph E3["🚀 Layer 3 — EXTENSIONS"]
        direction LR
        L9["L9<br/>MCSL"]
        L10["L10<br/>Attribute<br/>Grammars"]
    end

    subgraph E4["🔄 Layer 4 — TRANSLATION & CONCURRENCY"]
        direction LR
        _sp[" "]:::spacer
        classDef spacer fill:transparent,stroke:transparent,color:transparent;
        L11["L11<br/>Advanced<br/>Semantics"]
        L12["L12<br/>Petri / CCS"]
    end

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

Each layer poses a fundamental question:

Layer	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

Layer 1 — Syntax: What is Valid?

The first question to ask when faced with a language — be it programming, musical, or natural — 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 (CFG) 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 (syntactic analyzer) 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<br/>(EBNF)"| P["Parser"]
    P -->|"Syntactic<br/>analysis"| AST["AST<br/>(25 nodes)"]
    AST -->|"Transpiler<br/>BP2SC"| SC["SuperCollider<br/>Code"]

Layer 2 — Semantics: What Does It Mean?

Having valid syntax is not enough. The phrase “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<br/>P"]
    OP["🔧 Operational<br/>'How does it execute?'<br/>→ Transition rules"]
    DN["📐 Denotational<br/>'What function does it compute?'<br/>→ Mathematical domains"]
    AX["✅ Axiomatic<br/>'What can be proven?'<br/>→ 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 to describe BP3’s five derivation modes (ORD, RND, LIN, SUB, SUB1) — each defines 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 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 from an initial symbol, applies rules, and progressively obtains a musical sequence. Each rewriting step is a transition — exactly what SOS formalizes. Article L6 constructs the rules that make this intuition rigorous.

Layer 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<br/>Regular<br/>(MIDI)"]
    T2["Type 2<br/>Context-free<br/>(MusicXML, BP3 base)"]
    MCSL["MCSL<br/>Mildly CS<br/>(BP3 + bounded flags)"]
    T1["Type 1<br/>Context-sensitive<br/>(BP3 + multi-LHS)"]
    T0["Type 0<br/>Turing-complete<br/>(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.

Layer 4 — Translation and Concurrency: The Final Pieces

The fourth layer 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<br/>Program"]
    IR["Intermediate<br/>Representation<br/>(AST)"]
    TGT["SuperCollider<br/>Code"]

    SRC -->|"Analysis<br/>(front-end)"| IR
    IR -->|"Generation<br/>(back-end)"| TGT
    SRC -.->|"Translational<br/>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 streams.
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 streams 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 Semantics	What does “translate to SC” mean?	L11	BP2SC = translational semantics
Process Semantics	How to formalize polymetry?	L11	Stream superposition = 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<br/>Grammar"] -->|"L2, L3"| P["Parsing"]
    P -->|"L4"| AST["AST"]
    AST -->|"L6"| SEM["Operational<br/>Semantics"]
    SEM -->|"L11"| TR["Transpilation<br/>(BP2SC)"]
    TR -->|"L12"| SON["Sound<br/>(polymetry)"]

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

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 to 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
Glossary — The 60+ terms of the complete corpus

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

← Back to index