Glossary of Formal Languages and Compilation
An index of all technical terms used in this article series, sorted alphabetically.
A
$\lnot$ (negation)
logical connector “not”. $\lnot P$ is true if and only if $P$ is false.
→ See L8
$\Longrightarrow$ (implication)
logical connector “implies”. $P \Longrightarrow Q$ means “if $P$ is true, then $Q$ is true”.
→ See L8
$\omega$
exponent of matrix multiplication, $\le 2.371552$ (Williams et al. 2024). Bounds CFG parsing via Valiant.
→ See L17
$\wedge$ (conjunction)
logical connector “and”. $P \wedge Q$ is true if and only if both $P$ and $Q$ are true.
→ See L8
$T_{\text{gen}}$, $T_{\text{parse}}$
Time complexity functions for generation and recognition respectively, parameterized by Chomsky level $k$ and length $n$.
→ See L15
/N and \N
Primitive speed operators of BP3. /N multiplies speed by N (accelerates), \N divides it by N (slows down). N must be a positive integer. Inherited from BP1/BP2. In the C code: T0 with sub-type 11 (/) or 25 (\).
→ See B12
3-3-2 Pattern
Rhythmic grouping of 3+3+2 = 8 beats, typical of rumba, son cubano, and many popular music styles. The asymmetry creates a characteristic rhythmic tension between the groups of 3 and the final group of 2.
→ See M12
\N and \\*N
Scaling operators of BP3. *N multiplies scaling by N, **N divides it by N. N must be a positive integer. In the C code: T0 with sub-type 21 (*) or 24 (**).
→ See B12
_tempo()
Special function of BP3 (T43 in the C code) that modifies the local tempo by a rational factor x/y. Unifies /N (speed) and *N (scaling) into a single command: speed *= x, scaling *= y.
→ See B12
AC
Algorithmic Composition — an approach where software assists the composer with algorithms, without replacing their decisions. Lineage: Common Music → OpenMusic → PWGL → Opusmodus
→ See M7
Action (CCS)
an observable event that a process can perform. Three types: action $a$, co-action $\bar{a}$, internal action $\tau$.
→ See L12
Actor
A binding unit that links an alphabet, a scale, sounds, a transport, and an evaluator — the complete resolution context of a symbol
→ See S3, S9
ActorDirective
Node declaring an actor with its properties (alphabet, scale, sounds, transport…)
→ See S13
Adapter
A program that translates timestamped BPscript events into commands for a runtime
→ See S4
Adjunction
The central operation of TAGs. It consists of inserting an auxiliary tree at an internal node of an existing tree, by “cutting” the subtree and reattaching it to the foot node. This is what distinguishes TAGs from CFGs.
→ See L9
Aftertouch
pressure exerted on a key after the initial attack. Allows adding expression to sustained notes (vibrato, crescendo…).
→ See I4
Almost minimal finite automaton
A compact representation of a regular language built by QAVAID (separate Prolog II program) from examples. “Almost” minimal because exact minimization can over-generalize.
→ See B8
Alphabet
Ordered sequence of note names + available alterations — purely nominal
→ See S9
Alphabet (V or Σ)
Finite set of symbols usable in a grammar. Σ often denotes terminals alone, V the complete set.
→ See B2
Alter
Modification of a note’s pitch in MusicXML (sharp ♯ = +1, flat ♭ = -1, natural ♮ = 0).
→ See I5
Ambiguity (grammar)
Property of a grammar where the same string can be derived in several different ways (multiple possible syntax trees).
→ See B1
ANAL (mode)
BP3’s analytical mode — the grammar tests if a sequence belongs to the language. Uses template matching and wildcards. Corresponds to modus tollens.
→ See B8, L13
Analysis-by-synthesis
A paradigm where recognition uses generation as an internal subprocess. The receiver generates hypotheses and compares them to the received signal (cf. L13).
→ See B8, L13
Aroha/Avaroha
Ascending/descending scale of an Indian raga — can be different
→ See S9
Arpeggio
notes of a chord played successively rather than simultaneously
→ See M3
ARROW
Type of arrow in a BP3 rule (-->, <->, <--). Determines in which directions (PROD, ANAL) the rule is active.
→ See B10
Articulation
Indication of how a note should be played (staccato, accent, tenuto…).
→ See I5
Assertion
a logical property about the program state at a given point. Preconditions and postconditions are assertions.
→ See L8
AST
Abstract Syntax Tree — tree representation of a program after parsing
→ See B11, S13
Axiom
an inference rule without premises (conclusion always true). Example: $\langle n \rangle \Downarrow n$ is an axiom because a number always evaluates to itself.
→ See L6, L8
Ālāp
Slow introduction of a raga in Indian music, without a fixed pulsation, where the musician progressively explores the notes of the mode.
→ See B12, B4, B6, S5, S6
Āvart
A complete tāla cycle. A kayda can extend over several āvart before concluding with a tihāī.
→ See B4
B
Backtick
the ` “ character used in BPscript to delimit native code intended for a runtime
→ See S1, S4
Backtracking
Algorithmic technique of backtracking when a partial solution fails
→ See B13
Behaviorism
A school of psychology (early 20th century) that explains learning solely through stimulus-response, without reference to innate mental structures.
→ See M4
Best known algorithm bound
ceiling reached by the best algorithm published to date; can be improved.
→ See L17
Bidirectional
capable of generating and recognizing; see L13
→ See S1
Bidirectionality
Property of a grammatical formalism that can be used for both generation (producing strings) and recognition (analyzing strings) with the same grammar.
→ See L16
Big-step
semantics where a transition (denoted $\Downarrow$) completely evaluates an expression to its final value.
→ See L6
Binding
A link between a symbol and its actor — implicit (inferred) or explicit (dot notation)
→ See S3
Birman-Ullman (paradox)
The observation that transforming a parser into a generator is easy, while transforming a grammar into a parser is difficult — seemingly the inverse of asymmetry, but in reality its confirmation.
→ See L15
Bisimulation
a relation between two processes such that at each step, any action of one can be mimicked by the other, and vice versa. Finer than trace equivalence: it takes into account the branching structure.
→ See L11, L12
Bit
elementary unit of information (0 or 1). 7 bits = 128 possible values (0-127).
→ See I4
BNF (Backus-Naur Form)
notation for describing the syntax of a language. e ::= n | e + e means “e is either n, or e + e”.
→ See L6
BNF / EBNF (Backus-Naur Form / Extended BNF): notation for writing formal grammars. Used to specify the syntax of programming languages. See L3.
- Context-free
a type of grammar (Type 2) where each rule replaces a single symbol, independently of the context. Allows recursion and nesting. See L2.
→ See M1
Bol
Mnemonic syllable of the Indian tabla (e.g., dha, dhin, tin, ta). The “Bol” in “Bol Processor.”
→ See B1, B6, M5
Bol Processor (BP3)
a system of formal grammars for music, developed by Bernard Bel since 1989, initially for the North Indian tabla
→ See S1
Bol (बोल): Mnemonic syllable of the tabla (e.g., dha, dhin, tin, ta). The “Bol” in “Bol Processor”. Each bol corresponds to a specific stroke producing a distinct timbre.
- String (or word)
Finite sequence of symbols. Example: “abc” is a string of 3 symbols.
→ See B2
Bottom ($\bot$)
minimal element of a domain, representing absence of information or non-termination. Pronounced “bottom”. Example: an infinite loop has $\bot$ as its denotation.
→ See L7
Bottom-up
A parsing strategy that starts from the terminal symbols (the leaves of the tree) and ascends towards the axiom (the root). Examples: LR, CYK.
→ See L14
Bottom-up parser
A parser that starts from the text and ascends towards the start symbol by reducing groups of symbols.
→ See L1
BP3
Bol Processor 3 — musical grammar software developed by Bernard Bel (see I2)
→ See M3
BP3 (Bol Processor 3)
Musical grammar software developed by Bernard Bel (1990s), designed for Indian and African music.
→ See M4, M5
BPM
Beats Per Minute. Measure of tempo. 120 BPM = 120 quarter notes per minute.
→ See I4
Buffer
current events continue to play while the new sequence is being calculated
→ See S11
C
Cadence
A chord progression that punctuates the end of a musical phrase (e.g., $V \to I$ = dominant → tonic).
→ See M4, M6
Cartesian product
$A \times B$ = set of all pairs (a, b) with a in A and b in B.
→ See L6
Cascade
Priority system between layers — the most specific layer overrides the others
→ See S14
Catalan (numbers)
The sequence $C_n = \frac{1}{n+1}\binom{2n}{n}$ which counts the number of binary trees with $n$ nodes. Exponential growth $\sim 4^n / n^{3/2}\sqrt{\pi}$.
→ See L15
Catalan numbers
$C_n \sim 4^n/n^{3/2}\sqrt\pi$—count the derivation trees of an ambiguous CFG string.
→ See L17
Categorical (distribution)
Discrete probability distribution over a finite set of categories, each with its own weight. Generalizes the roll of a biased die to an arbitrary number of faces.
→ See B4
Causal (system)
In signal processing, a system whose output at time $t$ depends only on inputs at times $\leq t$. The generator is causal; a parser without lookahead is also.
→ See L15
CCG (Combinatory Categorial Grammar)
A grammatical formalism where each word carries a typed category (like $(S\backslash NP)/NP$ for a transitive verb) and words combine through operators (application, composition, type-raising).
→ See L9
CCS (Calculus of Communicating Systems): a process algebra introduced by Robin Milner (1980). Operators: prefix $a.P$, choice $P + Q$, parallel $P \mid Q$, restriction $P \setminus \{a\}$.
- Parallel composition
operator $P \mid Q$ (CCS) or $P \parallel_A Q$ (CSP) that executes two processes simultaneously.
→ See L12
CCS (Calculus of Communicating Systems): process algebra introduced by Robin Milner (1980). Operators: prefix (a.P), choice (P + Q), parallel (P | Q), restriction ((new a) P).
- Parallel composition
operator P | Q that executes P and Q simultaneously. Processes can synchronize on common actions.
→ See L11
Cents
Logarithmic unit — 1200 cents = 1 octave, 100 cents = 1 semitone in 12-TET
→ See S15, S9
CFG (Context-Free Grammar)
A grammar where each rule replaces a single non-terminal symbol, regardless of the surrounding context.
→ See B1
Chomsky hierarchy
classification of formal languages into 4 types (Type 3 → Type 0) according to the increasing expressive power of the necessary grammars. See L1.
→ See M1
Chomsky, Noam
American linguist (born 1928), founder of the theory of generative grammars.
→ See M4
Chomsky-Shannon-Morris Triptych
Three complementary theoretical frameworks for understanding BP3’s modes. Chomsky = structural complexity (hierarchy), Shannon = encoding/decoding (direction), Morris = cycle correctness (commutativity).
→ See B8
Circularity
a situation where the dependency graph contains a cycle, making evaluation impossible. Detecting whether an attribute grammar can produce circular dependencies is DEXPTIME-complete.
→ See L10
Class invariant
a property that must be true for any object of a class, at any observable time (between method calls).
→ See L8
Coarticulation
In phonetics, the modification of a sound by its adjacent sounds. By analogy, BP3’s time-setting modifies the phrasing of a sound-object based on its temporal context.
→ See B9
Combinator
A combination operation in CCGs. The main ones are application (forward/backward), composition (B), and type-raising (T). They originate from Curry’s combinatory logic.
→ See L9
Communicative efficiency
pressure shaping languages toward a speaker-effort / informativeness trade-off.
→ See L21
Compas
Rhythmic cycle in flamenco, structured by accents that define the identity of each palo (style). In rumba, the compas is a 4-beat cycle (or 8 eighth notes) with a 3-3-2 accent pattern.
→ See M12
Compiler correctness
property stating that compilation preserves meaning. Formally: Morris’s diagram commutes.
→ See L11
Compositional path
Sequence of flag states that defines a trajectory through the grammar — each state activates a different set of rules
→ See S6
Compositionality
property whereby the meaning of a composite expression depends only on the meaning of its components. Example: the meaning of “2 + 3” depends only on the meaning of “2”, “3”, and “+”.
→ See L5, L7
Compression rate ($R$)
number of signifiers (bits) per transmitted signified. Compressing = lowering $R$ = spending less energy $E(R)$.
→ See L21
Concatenation
joining strings end-to-end. Denoted · (middle dot). "abc" · "def" = "abcdef".
→ See L6
Configuration
complete state of a program at a given instant (expression to evaluate + environment + memory). Noted $\langle e, \sigma \rangle$ where $e$ is the expression and $\sigma$ is the state.
→ See L5, L6
Configuration (SOS)
Tuple representing the complete state of the system during derivation. For BP3 with flags and weights: $(\sigma, \varphi, t, w)$ — working string, flag environment, time, weight function.
→ See B4
Conjunct motion
Melodic movement by successive whole or half steps (C-D-E), as opposed to disjunct motion (leaps, like C-G).
→ See M6
Consonance/Dissonance
Consonance is the quality of a stable and “pleasant” sound (octave, fifth, major third). Dissonance is unstable and calls for resolution.
→ See M6
Constraint-satisfaction
Problem of finding values that satisfy a set of constraints
→ See B13
Context
a condition for rule application, based on neighboring symbols — positive (A B) or negative #(A B) — tested during derivation, never modified
→ See S8
Context marker
A BP3 construction that conditions the application of a rule on the presence of a symbol in the context.
→ See B6
Context-free
Property of a rule that applies regardless of the symbol’s environment. Replacing A with xyz does not depend on what precedes or follows A.
→ See B1, L1, M2
Context-free grammar (CFG)
A grammar where all rules are of the form $A \to \gamma$ (a single non-terminal on the left).
→ See L1
Context-sensitive
A property of a grammar where the replacement of a symbol depends on its environment. Corresponds to Type 1 of the Chomsky hierarchy.
→ See B6, S8
Continuous function
a function that preserves the limits of increasing chains. Necessary for the existence of fixed points.
→ See L7
Control
BP3 control written directly in the stream (vel(120), goto(2,1))
→ See S13
Control Change (CC)
message to modify continuous parameters (volume, pan, sustain…). Identified by a number (0-127) and a value (0-127).
→ See I4
controlTable
Table {CTn → parameters} — runtime () compiled into _script(CTn)
→ See S10
Convergence
Property of a process that tends towards a final state. Decremental weights converge to $0$, forcing termination.
→ See B4
Cross-references
Links between elements of a text where one element refers to another defined elsewhere (e.g., hyperlinks, footnotes).
→ See L1
Cross-rhythm
A rhythmic pattern where the accents of one voice systematically fall between those of another.
→ See M5
Cross-serial dependencies
A syntactic structure where two sequences of elements correspond element by element, like subjects and verbs in Dutch ($A_1\ A_2\ A_3\ B_1\ B_2\ B_3$ where $A_i$ depends on $B_i$).
→ See L9
Csound
Sound synthesis language created by Barry Vercoe (MIT, 1986). BP3 can generate Csound code as an alternative to MIDI, allowing arbitrarily complex grammar terminals.
→ See B9
CSP (Communicating Sequential Processes): a process algebra by Tony Hoare (1985). Synchronization by shared events, with three semantic models (traces, failures, failures-divergences).
- Downbeat
the first beat of a measure — the natural synchronization point between musical voices.
→ See L12
CSP (Communicating Sequential Processes): process algebra introduced by Tony Hoare (1985). Synchronization on shared events, with three semantic levels (traces, failures, failures-divergences).
- Commutative diagram
a diagram where all paths between two points yield the same result. For a compiler: interpret the source = compile then interpret the target.
→ See L11
CT (Control Table)
Point-in-time override via () — persists until the next ()
→ See S14
CV (Control Voltage)
Continuous modulation over a duration (ADSR, LFO, ramp) — declared as name(target, transport) = lib.type(args)
→ See S14, S3
CV engine
Downstream component that resolves CV objects (ADSR, LFO, ramp) into audio buses or CC messages
→ See S10
CVInstance
Declaration of a CV object at the top of the scene (envelope, LFO, ramp)
→ See S13
CYK (Cocke-Younger-Kasami): A bottom-up parsing algorithm using dynamic programming. Runs in $\mathcal{O}(n^3)$ for any CFG.
- Top-down
A strategy that starts from the axiom (the root) and descends towards the terminals (the leaves). This is the natural direction of generation. In parsing, this is the LL strategy.
→ See L14
D
· (double brackets)
standard notation for “the denotation function”. e reads as “the denotation of e” or “what e means mathematically”.
→ See L7
Data byte
a MIDI byte whose most significant bit is 0 (values 0-127). Carries message parameters (note, velocity, CC value…).
→ See M1
Dataflow
paradigm where computation is modeled as a graph of data flows between processing nodes
→ See M3, M7
DAW
Digital Audio Workstation. Music production software (Ableton, Logic, FL Studio…).
→ See I4, M3
DCG (Definite Clause Grammar): Grammatical extension of Prolog, inherently bidirectional thanks to unification, but with asymmetrical pathologies (different infinite recursions in each direction).
- Declarativity
Property of a grammar that separates what it says (linguistic content) from how it is processed (direction, traversal strategy). A prerequisite for bidirectionality according to Appelt.
→ See L16
Decrement
Decrease in a value. In <50-12>, the decrement is $12$: the weight loses $12$ with each use.
→ See B4
Decremental weight
Weight associated with a rule that decreases after each use of that rule. BP3 notation: <N-M> (initial weight $N$, decrement $M$).
→ See B4
Degree shift
changing the starting degree in the scale — produces a different mode
→ See S15
Denotation
the mathematical value (function, set, etc.) associated with an expression. Noted $\llbracket e \rrbracket$ for expression $e$.
→ See L7
Dependency graph
a directed graph whose nodes are attribute instances and whose edges represent dependencies between them. If it is acyclic, an evaluation order exists.
→ See L10
Derivation
Sequence of rule applications starting from the initial symbol (S) to a string containing only terminals.
→ See B1, B2, B3, L6, S1, S2
Derivation mode
In BP3, a sub-grammar strategy for choosing and applying rules (ORD, RND, LIN, SUB, SUB1, TEM, POSLONG).
→ See B3, S5
Derivation tree (syntax tree)
Visual representation of a derivation, with the start symbol at the root and terminals at the leaves.
→ See B1
DERIVATION_MODE
Traversal direction for an individual rule (LEFT, RIGHT, RND). Distinct from the block’s MODE.
→ See B10
Design by Contract
a programming methodology where functions are annotated with preconditions, postconditions, and invariants. Invented by Bertrand Meyer (Eiffel, 1986).
→ See L8
Desirable difficulty (desirable difficulties, R. & E. Bjork): observation that well-calibrated learning obstacles improve retention—the empirical idea of a non-trivial error optimum.
- Striatum / basal ganglia
brain structures (modulated by dopamine) that calculate effort cost and form habits.
→ See L21
Determined rest
Fixed-duration rest, noted as - in BP3. Corresponds to an explicit pause of one time unit.
→ See B2
Deterministic
a system that always produces the same result with the same inputs
→ See M3
Differential coupling
generation and recognition are sensitive to both axes (class × sub-problem), but with an inverted primary sensitivity.
→ See L17
Directive
an @… instruction that configures the entire scene, outside the temporal flow
→ See S2
Disjoint
Two sets are disjoint if they have no elements in common.
→ See B2
Distributed Composition
Architecture where multiple BPscript instances on different machines synchronize via triggers
→ See S7
Divisions
Number of subdivisions per quarter note, defines the file’s temporal resolution.
→ See I5
Djembe
A goblet-shaped drum originating from West Africa, played with the hands.
→ See M5
DOCTYPE
Declaration at the beginning of an XML file that indicates the schema (structure rules) used.
→ See I5
Domain
a mathematical structure with a partial order ($\sqsubseteq$) and completeness properties; serves as a “value space” for programs.
→ See L7
Domain theory
branch of mathematics providing the structures (ordered domains) necessary to define the semantics of loops and recursion.
→ See L5
Dominant
The 5th degree of the scale (e.g., G in C major), which creates tension calling for resolution to the tonic.
→ See M4
Dominant (V)
Fifth degree of the scale, a tension chord that calls for the tonic.
→ See M6
Downbeat
Strong beat, usually the first beat of a measure.
→ See M5
Dragon Book
Nickname for Compilers: Principles, Techniques, and Tools (Aho, Sethi & Ullman, 1986), the reference book in compiler design.
→ See L14
DSL
Domain-Specific Language — a programming language dedicated to a particular domain
→ See M3, M7
DTD (Document Type Definition): older XML validation format, corresponding to a local tree language. Superseded by XSD since MusicXML 4.0.
- Tree grammar
a grammar that operates on trees rather than character strings. XML schemas are tree grammars.
→ See M2
Dunun
Family of cylindrical double-headed drums (dununba, sangban, kenkeni) playing patterns in West Africa.
→ See M5
Dynamic Tonality
Parametric temperament whose generator can vary continuously
→ See S9
Dynamic weight
In BP3, a numerical weight associated with a rule that changes (usually decreases) after each use of that rule.
→ See B1
Dynamics
Indication of sound intensity on the score (pp, p, mp, mf, f, ff — from softest to loudest).
→ See I5
E
Earley
A hybrid (top-down-bottom-up) parsing algorithm capable of processing any CFG in $\mathcal{O}(n^3)$.
→ See L14
EBNF
Extended Backus-Naur Form — standard notation for syntax (ISO 14977)
→ See S12
EBNFdoc
Systematic documentation format for EBNF productions, inspired by API references (Javadoc, MDN). Each production is documented with its typed components, constraints, C source, and examples.
→ See B10
Ecological oracle
here, the non-formal oracle formed by interaction feedback (repair, alignment, desynchronization), primarily implicit.
→ See L21
Elaboration
A note or passage that “decorates” a structural note without changing its meaning.
→ See M6
Empty string (ε)
The string of length zero, containing no symbols. Noted as ε (epsilon) or λ (lambda).
→ See B2
Encoder
Step 3 — translates the AST into BP3 grammar + emits the terminalActorMap and prototypes
→ See S10
Encoder / Decoder
In Shannon’s model, the encoder transforms a message into a signal (generation), the decoder reconstructs the message from the signal (recognition). They are not symmetrical.
→ See L13
ENGINE_KEY
Reserved key for engine qualifiers []
→ See S12
Enharmonic equivalence
Equivalence between two notations of the same frequency (C# = Db) — only exists in equal temperament
→ See S15
Enharmony
in music, two notes of the same pitch but different spelling (C# = D♭). MIDI does not distinguish enharmonics.
→ See I4
Entrainment
synchronization of rhythmic behaviors between interacting individuals (here, in joint music).
→ See L21
Environment
a dictionary associating each variable with its value. Noted ρ (rho). Example: {x ↦ 5, y ↦ 10}.
→ See L7
Equal Temperament
tuning system dividing the octave into 12 equal semitones. Standard of modern Western music.
→ See I4
Error rate / distortion ($\varepsilon$)
proportion of what the receiver does not correctly reconstruct. Increases with compression $R$, decreases with shared knowledge $\kappa$.
→ See L21
Extracted learning ($G$)
knowledge gain $d\kappa$ derived from resolved errors. Function of $\varepsilon$ in an inverted U (neither too little nor too much) and the power of the oracle.
→ See L21
F
Fan-out
A parameter of MCFGs that measures the number of components a rule can manipulate simultaneously. Fan-out 1 = CFG, fan-out 2 = TAG.
→ See L9
Fifths
Number of alterations in the key signature, counted on the circle of fifths (positive = sharps ♯, negative = flats ♭).
→ See I5
Finite automaton
An abstract machine with a finite number of states, without external memory. Reads an input character by character and changes state according to transition rules.
→ See L1, M1
Fixed point
value $x$ such that $f(x) = x$. Example: $0$ is a fixed point of $f(x) = x^2$, because $f(0) = 0$. In semantics, used to define loops and recursion.
→ See L5, L7
Flag
Conditional variable attached to a rule (/name=value/). Controls activation and modifies the derivation state.
→ See B10, B4, S1, S2, S6
Flag environment ($\varphi$)
Function that associates each flag name with its current integer value. Notation: $\varphi(\text{avart}) = 4$.
→ See B4
Flat alphabet
Convention where terminals are opaque names prefixed with bol — BP3 does not know what they mean
→ See S10
Formal language
A set of symbol strings defined by precise rules.
→ See L1
Formal verification
the use of mathematical methods to prove that a system (software or hardware) satisfies its specification.
→ See L8
Frege, Gottlob
German logician (1848-1925), founder of modern logic, to whom the principle of compositionality is attributed.
→ See M4
FST (Finite-State Transducer): A finite-state automaton with input and output. The inverse of an FST is also an FST—a property that does not generalize to context-free grammars.
- GF (Grammatical Framework): Multilingual grammatical formalism by Ranta (2004, 2019) with abstract/concrete syntax separation, allowing parsing and generation in 40+ languages.
- Grammar Inversion
Strzalkowski’s technique for automatically transforming a parsing grammar into a generation grammar by inverting the control structure. Proves that direction is embedded in procedural grammars.
→ See L16
Function (gen) vs relation (parse)
Generation is a function (single-valued): its input — (grammar + derivation) — determines the output. This is not injectivity (two derivations can yield the same string). Parsing is a relation (one sentence → multiple trees) because its input — (grammar + string) — is less informative and underdetermines the tree.
→ See L15
Functional update
Operation that creates a new environment identical to the old one except for one variable. Notation: $\varphi[\text{avart} \mapsto 3]$ means “$\varphi$ with avart changed to $3$.”
→ See B4
G
Gate
A signal that remains active for a duration — in BPscript, a symbol that occupies time
→ See S3
General MIDI (GM)
standard defining 128 sounds numbered identically across all compatible devices.
→ See I4
Generation under semantic constraint
producing a string that additionally satisfies an external constraint. NP-complete from $k=2$ with features (Brew 1992).
→ See L17
Generative grammar
A set of formal rules capable of producing all valid structures of a language.
→ See M4
GPR (Grouping Preference Rule)
In GTTM, a preference rule for grouping notes into phrases.
→ See M4
GPR (Grouping Preference Rules)
Preference rules for grouping. Describe how we perceive boundaries between musical groups.
→ See M6
Graha bheda
Technique of raga transposition by shifting the fundamental note (Sa), causing a new raga to emerge. Formalizable as a BP3 homomorphism.
→ See B6
Grain
In granular synthesis, a micro-sound fragment (typically 1-100 ms) which, combined with thousands of others, forms complex textures and sounds.
→ See B9
Grammar
A set of rules for generating or recognizing a language. Defined by terminal symbols, non-terminal symbols, and production rules.
→ See L1, M1
grammar_section
Grammar block containing a mode, an optional preamble, and rules.
→ See B10
Grid shift
transposition by shifting N steps in the temperament grid — only works in equal temperament
→ See S15
Grouping structure
Hierarchical organization of musical events into units (motifs, phrases, sections).
→ See M4
GTTM
Generative Theory of Tonal Music — Lerdahl and Jackendoff’s theory modeling musical perception
→ See M3
GTTM (A Generative Theory of Tonal Music)
Lerdahl and Jackendoff’s theory (1983) formalizing the perception of tonal music.
→ See M4
GTTM (Generative Theory of Tonal Music)
Generative theory of tonal music, developed by Lerdahl and Jackendoff (1983).
→ See M6
Guaranteed termination
Property of a system that necessarily reaches a final state in a finite number of steps. Decremental weights guarantee at most $\lceil N/M \rceil + 1$ steps.
→ See B4
Guard
Condition that must be satisfied for a rule to apply. Flags in test mode (/avart/, /avart>2/) function as guards.
→ See B4, S2, S6
H
Head
The structurally most important note of a group. The other notes in the group are elaborations of the head.
→ See M6
Hemiola
Specific polymeter where 2 and 3 are superimposed (6 beats = 2×3 = 3×2).
→ See M5
Hierarchy
Organization in nested levels (tree), where each element belongs to a higher-level element.
→ See M4
Hoare logic
a formal system of triples $\{P\}\; C \;\{Q\}$ and inference rules for proving program correctness. Introduced by C.A.R. Hoare in 1969.
→ See L8
Hoare triple
notation $\{P\}\ C\ \{Q\}$ meaning “if $P$ is true before $C$, then $Q$ is true after”.
→ See L5, L8
HomoApply
Homomorphism node — MASTER (=X) defines, SLAVE (:X) replicates
→ See B11
Homomorphism
A function that transforms each symbol of a string according to a fixed mapping, preserving structure (morphism of free monoids).
→ See B6, L11, S8
Hot-swap
Hot-swapping — modifying code while the system is running, without stopping it
→ See S11
HTML
HyperText Markup Language — markup language for web pages, a cousin of XML.
→ See I5
HTSPN (Hierarchical Time Stream Petri Nets): a hierarchical extension of timed Petri nets, used for interactive scores (Senac 1995, Allombert 2007).
- Token
a marker in a place of a Petri net. Represents a resource, a state, or a position in the execution.
→ See L12
I
IDyOM (Information Dynamics of Music): A statistical model of musical prediction based on corpus entropy. Models the listener as an inference machine.
- Grammatical inference (grammar induction): The “third direction” — finding the grammar from examples of sentences. The inverse problem of formal language theory.
- Modus ponens / modus tollens
In logic, modus ponens goes from rule to consequence (if A then B, A, therefore B — generative direction). Modus tollens goes from observation to premise (if A then B, B observed, therefore A plausible — analytical direction).
→ See L13
IEEE 1599
multilayer standard for 6-layer synchronized XML musical representation
→ See M3
Implicit resolution
The compiler infers the actor of a symbol when there is no ambiguity
→ See S3
Incoming Trigger (<!)
Synchronization point — the derivation waits for an external signal
→ See S7
Increasing chain
a sequence of elements $x_0 \sqsubseteq x_1 \sqsubseteq x_2 \sqsubseteq \ldots$ where each element has “more information” than the previous one. Used to construct fixed points.
→ See L7
Indeterminate rest
Rest with a duration calculated by the context, noted as _ in BP3. Used in polymetric expressions.
→ See B2, S5
Inference rule
schema of the form “if these premises are true, then this conclusion is true”.
→ See L5, L6
Informant regime (vs. text): in Gold, learning with access to answers/counter-examples, more powerful than positive data alone.
- Superfinite class
class containing all finite languages and at least one infinite one; not identifiable from positives alone (Gold’s wall).
→ See L21
Information bottleneck
formal framework (Tishby) for the trade-off between compressing a variable and information retained about another—candidate for formalizing $\varepsilon^{*}$.
→ See L21
Inherited attribute
an attribute whose value is transmitted by the parent node or siblings to the left. Information flows top-down or left-to-right. Example: the declared type type_decl in a variable list.
→ See L10
Inherited attribute ($\downarrow$): Information that descends from parent to child in an attribute grammar. Top-down flow.
- Synthesized attribute ($\uparrow$): Information that ascends from child to parent in an attribute grammar. Bottom-up flow.
- Chart (parsing table)
A tabular data structure used by parsing algorithms (Earley, CYK, chart parsing) to store intermediate results. In parsing, indexed by positions in the input string. In generation, this indexing is impossible (the string does not yet exist), hence the need to be driven by semantic heads.
→ See L14
Initial algebra
an algebra from which there is a unique homomorphism to any other algebra of the same signature. A language’s AST is an initial algebra: there is only one way to interpret it in a given semantic domain.
→ See L11
Inline backtick
A backtick within a symbol call — the runtime is inferred from the symbol, no tag needed
→ See S4
Input object
A zero-duration time-object that waits for an external signal (MIDI note, mouse click) to synchronize real-time performance.
→ See B9
Interleaving
a concurrency model where “A and B in parallel” means “all possible sequences by alternating actions of A and B”. Used by CCS/CSP.
→ See L12
Intrinsic ambiguity
A property of a language (not a grammar) such that every grammar that generates it is ambiguous. Discovered by Parikh (1966).
→ See L15
Intrinsic bound
characterization of the difficulty of the problem itself ($\Theta(f)$ or complexity class), which no algorithm can beat unless a conjecture is overturned.
→ See L17
Invariant
property that remains true throughout execution.
→ See L5
Inverse Folding
In bioinformatics, the problem of designing an RNA sequence that folds into a target structure. NP-hard (Bonnet et al., 2020).
→ See L16
IR
Intermediate Representation — intermediate representation between source and target
→ See B11
J
Jhālā
Concluding phase of a raga, fast and virtuosic
→ See S6
JIT
Just-In-Time compilation — compilation of code at runtime. Extempore uses LLVM JIT to compile DSP live
→ See M7
Jor
Intermediate phase of a raga, progressively rhythmic
→ See S6
K
K-parameter
Interactive weight (<K1>, <K1=5>) allowing the user to dynamically control rule selection.
→ See B10
KAMP
Appelt’s system unifying planning and realization in NLG. Bidirectional but “computationally impracticable.”
→ See L16
Kathak
Classical dance of Northern India, linked to the tabla. Tabla player-dancer interactions are a founding case study for BP3.
→ See B6
Kayda
Tabla composition with a fixed theme (mukhra) and systematic variations. Uses complex grammatical structures (sub-grammars, templates), not simply SUB1 mode.
→ See B3, B4, B8
Khali
“Empty” section (without resonance) of an Indian tāla cycle, where dry bols (tin, ta) replace resonant bols (dha, dhin).
→ See B1, B3, M5
Kleene star (*)
Operation on a set that produces all possible strings formed with its elements, including the empty string. If T = {a}, then T* = {ε, a, b, aa, ab, ba, bb, aaa, …}.
→ See B2
Kleene’s theorem
guarantees that any continuous function on a domain has a least fixed point, obtained as the limit of successive approximations.
→ See L7
Knowledge gradient ($\kappa$)
amount of grammatical knowledge available, from 1 (known grammar, recognition) to 0 (nothing known, pure inference).
→ See L21
Kpress
Compression factor of the phase diagram in PolyMake(). Reduces temporal resolution when the grid exceeds memory limits.
→ See B12
L
L-attributed
a class of attribute grammars where inherited attributes depend only on the parent and left siblings. Evaluated in a single left-to-right pass, compatible with LL parsing.
→ See L10
Lambda
Empty production (ε) — the non-terminal disappears
→ See B11
Lambda (empty production)
A rule that rewrites a non-terminal as the empty string ($\varepsilon$). The symbol disappears without a trace.
→ See B6
Language
Set of all terminal strings derivable from the start symbol.
→ See B2
LCM
Least Common Multiple — in polymeter, the point where two cycles resynchronize (e.g., LCM of 2 and 3 = 6).
→ See M5, S5
Learning progress
speed at which one learns ($\approx d\kappa/dt$); models curiosity as intrinsic utility (Gottlieb & Oudeyer).
→ See L21
Left-corner
A hybrid parsing strategy that starts bottom-up (the first symbol) then continues top-down (prediction).
→ See L14
Leftmost (left derivation)
Strategy that always replaces the leftmost non-terminal.
→ See B3
Leftmost derivation
Derivation strategy that always rewrites the leftmost non-terminal in the work string. In BP3’s LIN mode, the choice among applicable rules at this position is random.
→ See B3
Legato
Connected playing style, where notes flow into each other without interruption. Indicated by a slur.
→ See I5
LHS (Left-Hand Side)
Left side of a rule — what is rewritten. Must contain at least one element.
→ See B10, B3
LIN (BP3 mode)
Linear mode — the candidate rule is chosen randomly from those that produce a leftmost derivation (the leftmost non-terminal is rewritten first).
→ See B3
Live coding
a performative programming practice where code is written and modified in real-time in front of an audience
→ See M3, M7, S11, S2
LL (Left-to-right, Leftmost derivation): Predictive top-down parsing. Mimics the direction of generation. Less powerful than LR.
- Lookahead
Number of lookahead symbols a parser consults to decide which rule to apply. Noted as $k$ in LL($k$) and LR($k$).
→ See L14
Loop invariant
a logical property true before the loop and preserved by each iteration. Key to correctness proofs for loops.
→ See L8
LTS (Labeled Transition System): a triplet $(S, \text{Act}, \to)$ — states, actions, transitions. The underlying model of CCS.
- Marking
the distribution of tokens in the places of a Petri net. Represents the global state of the system at a given time.
→ See L12
M
Macro
textual substitution — the compiler replaces the call with the macro’s body before any analysis
→ See S2
Markovian process (memoryless)
Stochastic process where the probability of a future event depends only on the present state, not on the history.
→ See B1
Mathematical function
relation that associates exactly one element from a starting set (domain) to each element of an arrival set (codomain). Example: $f(x) = x + 1$ associates each integer with its successor.
→ See L5
MCSL
Mildly Context-Sensitive Language — a class of languages between context-free (Type 2) and context-sensitive (Type 1)
→ See M7
MCSL (Mildly Context-Sensitive Languages)
Class of languages between Type 2 (context-free) and Type 1 (context-sensitive). Position of grammars written within BP3.
→ See B10
MDL (Minimum Description Length): criterion for choosing a model; the best one minimizes (model size) + (data encoded by it). Quantified Occam.
- CRC (cyclic redundancy check): redundant bits added to detect corruption. Removing them compresses but reduces robustness.
- Under-specification
omitting, in a message, what the receiver can reconstruct—compressing at the source.
→ See L21
Membership decision
determining if a string belongs to the language (yes/no)—the reference bound on the recognition side.
→ See L17
Membership test
The decision problem: “does this sequence belong to the language generated by this grammar?”. In BP3, solved by template matching in ANAL mode.
→ See B8
Meter
Regular organization of beats into groups with a hierarchy of accents (strong/weak beats).
→ See M5
Metric
Hierarchical organization of strong and weak beats, distinct from rhythm (note durations).
→ See M6
Metric properties
Characteristics of a sound-object related to its internal duration and how its timing adjusts to tempo.
→ See B9
Microsound
Curtis Roads’ term for the temporal scale of grains (below the note, above the sample).
→ See B9
MIDI
Musical Instrument Digital Communication — universal protocol (1983) for transmitting musical events between instruments and software. MIDI 2.0 (2020) extends resolution to 32 bits
→ See M7
MIDI Channel
logical subdivision (1-16) allowing different instruments to be addressed on the same cable. Like 16 independent phone lines.
→ See I4
Mildly context-sensitive
A class of languages satisfying Joshi’s criteria: contains CFLs, captures cross-serial dependencies, is semilinear, and allows polynomial parsing.
→ See L9
Mini-notation
TidalCycles’ compact syntax for describing rhythmic patterns within quotes
→ See M7
MODE
Derivation mode of a grammar block (ORD, RND, LIN, SUB, SUB1, TEM, POSLONG). Determines the rule selection strategy.
→ See B10
Model surprise (Bayesian)
magnitude of model change after an event = information gained about the grammar. In bits.
→ See L21
Modular power
BP3 is not fixed to a Chomsky class — depending on the activated mechanisms, it ranges from context-free (Type 2) to context-sensitive (Type 1), or even beyond; see B6
→ See S1
Modus ponens
Direct logical reasoning: “if A implies B, and A is true, then B is true”. In BP3: if the grammar has the rule S → A B, we can produce A B. Direction: PROD.
→ See B8
Modus tollens
Inverse logical reasoning: “if A implies B, and B is false, then A is false”. In BP3: if a sequence does not correspond to any derivation of the grammar, it is not grammatical. Direction: ANAL.
→ See B8
Monad
mathematical structure allowing the encapsulation of effects (state, randomness, errors) within a functional framework. Used to model programs with side effects in denotational semantics.
→ See L5, L7
Morris Diagram
Commutative diagram (Morris, 1973) that formalizes compiler correctness: the result must be the same whether one takes the “compile then execute” path or “interpret directly”. Applied to the PROD→ANAL→adjusted weights→re-PROD cycle.
→ See B8
MOS (Moment of Symmetry)
Scale generated by a single interval (generator) reduced within a period
→ See S9
MPE
MIDI Polyphonic Expression. Extension allowing one channel per note for individual expression.
→ See I4
MPR (Metrical Preference Rule)
In GTTM, a preference rule for metrical structure (strong/weak beats).
→ See M4
MPR (Metrical Preference Rules)
Preference rules for metrical structure. Describe how we infer the beat grid.
→ See M6
Music engraving
the process of laying out a score according to professional typographic conventions. LilyPond automates this process
→ See M7
Music Petri Net
an extension of Petri nets adapted for musical description (Barate, Haus, Ludovico, 2005).
→ See L12
MusicXML
standardized XML exchange format (W3C) for digital scores. Interoperability between Finale, Sibelius, MuseScore, LilyPond
→ See M7
Mutation
Modification of a flag via [flag=value], [flag+1] or [flag-1] at the end of the rule — applied when the rule is triggered (out-of-time), not at a point in the played flow
→ See S6
MWSCCS (Musical Weighted Synchronous CCS): an extension of SCCS with stochastic weights for musical composition (Ross, 1995).
- Place
a circular node in a Petri net, containing tokens. Represents a state or a condition.
→ See L12
N
Neighbor tone
An ornamental note adjacent to a main note, which moves away by one step and then returns to it (e.g., C-D-C).
→ See M4
Neighboring tone (embellishment)
Ornamental note that leaves a structural note by conjunct motion and returns to it. Example: C-D-C.
→ See M6
Nesting
a structural property of context-free languages — an element can contain other elements of the same type, to an arbitrary depth. This is the key to Type 2.
→ See M2
NLG / NLU (Natural Language Generation / Understanding): The two sub-domains of NLP (Natural Language Processing) that embody the generation/recognition duality.
- Incremental parsing
Syntactic analysis that processes input symbol by symbol, as it is received, without waiting for the end of the sentence. Necessary for real-time analysis. More difficult than offline parsing because the analyzer does not have access to the rest of the signal.
→ See L13
NLG (Natural Language Generation): Sub-field of NLP concerning text generation. The Reiter & Dale pipeline decomposes the process into document planning → microplanning → surface realization.
- NLG Pipeline
Three-stage architecture (Reiter & Dale, 2000): 1) document planning (what to say), 2) microplanning (how to say it), 3) surface realization (the sentence). Structurally top-down.
→ See L16
Non-terminal
Intermediate symbol (variable) that will be replaced during derivation. By convention, written in uppercase (S, NP, VP).
→ See B1, B2, L1, L6, S2
NonTerminal
A symbol that can be rewritten (starts with an uppercase letter in BP3)
→ See B11
Normalization
Adjustment of durations so that all voices have the same total duration
→ See B13, B1
Notation $\llbracket \cdot \rrbracket$
double brackets meaning “the denotation of” or “the mathematical meaning of”. $\llbracket e \rrbracket$ is read “the denotation of $e$“.
→ See L5
Note On/Off
messages indicating the start (Note On) and end (Note Off) of a note.
→ See I4
O
OAG (Ordered Attribute Grammar): an intermediate class between L-attributed and general AG, where a fixed evaluation order can be statically determined for each production. Introduced by Kastens (1980).
- Flag (BP3): a named global-scope counter that conditions and modifies the application of grammar rules. Combines the roles of guard (test) and effect (modification).
- Multi-pass evaluation
an evaluation strategy where the tree is traversed multiple times, each pass calculating a subset of attributes. Necessary when dependencies do not allow a single pass.
→ See L10
Octaves
Register naming convention (position, separator, low→high list)
→ See S9
on_fail
Failure management directive — what to do when no rule applies (skip, retry, fallback)
→ See S6
Optimal error rate ($\varepsilon^{*}$)
error rate that maximizes learning per unit of energy. Distinct from the communicative optimum (which minimizes error).
→ See L21
Oracle
In the context of grammatical inference, the expert (the musician) who validates or rejects generalizations proposed by the system.
→ See B8, L21
ORD (BP3 mode)
Ordered mode, where rules are applied in the sequential order of the file.
→ See B3
Orphan backtick
A backtick at the top of the scene, not attached to a symbol, executed at init — requires a runtime tag
→ See S4
OSI Model
Open Systems Interconnection — a 7-layer model structuring network protocols
→ See M3
Ostinato
A short musical motif stubbornly repeated throughout a passage or piece.
→ See B3
Out-time object<<...>> element played immediately, outside the normal temporal flow. Can be a MIDI note or a sound-object.
→ See B10, B9
Outgoing Trigger (!)
Signal sent to a runtime at the time of execution
→ See S7
OutTimeObject
Out-of-time object <<symbol>> — triggered without occupying duration
→ See B11
P
P-chain
psycholinguistic framework (Dell & Chang) where prediction links production, comprehension, and acquisition; prediction error drives learning.
→ See L21
Parser
A program that analyzes text according to a grammar and builds a structure (syntax tree).
→ See L1, S10
Parser (syntax analyzer)
Program that analyzes a string to determine its grammatical structure.
→ See B2
Parsing (syntactic analysis)
The process that, given a sentence and a grammar, determines whether the sentence belongs to the language and reconstructs its structure (derivation tree).
→ See L13
Part
A voice or instrument in the score.
→ See I5
Partial correctness
property $\{P\}\; C \;\{Q\}$ — if $C$ terminates, $Q$ is true. Says nothing about termination.
→ See L8
Partial order ($\sqsubseteq$)
relation “is less defined than” or “has less information than”. $\bot \sqsubseteq x$ for all $x$.
→ See L7
Partwise
File organization by instrument then by measure (most common).
→ See I5
Passing note
A note that connects two structural notes by stepwise motion (e.g., D between C and E).
→ See M4
Patch / Program / Preset
predefined instrument sound. Program 1 = piano in General MIDI.
→ See I4
Patching
Wiring of audio modules (filter → reverb → output) — managed by the runtime, not by BPscript
→ See S14
Pattern
in SuperCollider or TidalCycles, an object that generates sequences of values according to rules
→ See M3, M7
Pattern matching
A mechanism for matching motifs. BP3 wildcards capture portions of derived strings for reuse.
→ See B6
PCFG
Probabilistic Context-Free Grammar — context-free grammar enriched with probabilities (see B1)
→ See M3, M7
PCFG (Probabilistic CFG)
Context-free grammar where each production rule is associated with a probability.
→ See B1
Performance control
Special function (_name(args)) controlling sound rendering (pitch, velocity, timing, etc.). 68 functions defined in BP3.
→ See B10
Periodic notation
notation using . to divide a sequence into fragments of equal symbolic duration
→ See S5
Petri Net
a graphical formalism (places, transitions, arcs, tokens) for modeling concurrent systems. Invented by Carl Adam Petri (1962).
→ See L12
Phase diagram
Internal data structure of BP3 (Maxconc × Maxevent grid) representing the temporal placement of all events after polymetric expansion.
→ See B12
Pitch Bend
message that continuously varies the pitch of a note (glissando, vibrato).
→ See I4
Poly_ratio
A single-voice polymetric expression {n, seq} compressing or stretching a sequence into n time units. Here, {1, 6 notes} plays 6 notes in 1 beat — a micro-timing.
→ See M12
PolyMake()
C function in Polymetric.c that implements polymetric expansion. Not formally documented.
→ See B13
Polymeter
Superposition of several different meters (e.g., 3 against 4).
→ See M5
Polymetric expansion
Transformation of {v1, v2} into a sequence of timestamped events
→ See B13
Polymetric ratio
The N in {N, ...}. Defines how many beats the sequence occupies. It is not a tempo operator (no speed modification), it is a structural ratio with local scope. Accepts rationals ({3/2, ...}).
→ See B12, S5
Polymetry
superposition of different meters — for example, 3 notes against 2 in the same duration. In BP3, denoted $\{v_1, v_2\}$.
→ See L12, M7, S1, S2, S5
Polynomial parsing
A parsing algorithm whose execution time is bounded by a polynomial in the length of the input. For TAGs: $O(n^6)$. For CFGs (CYK algorithm, Cocke-Younger-Kasami): $O(n^3)$.
→ See L9
Polyphony
Superposition of several independent melodic lines. In MusicXML, managed by the <voice> element.
→ See I5
Polyrhythm
Term sometimes synonymous with polymeter, sometimes distinguished (polyrhythm = different accents on the same meter).
→ See M5
POSLONG (BP3 mode)
Position + Longest mode, a variant of SUB1 that selects the longest derivation among candidate rules at the leftmost position. Leftmost-longest match strategy.
→ See B3
Postcondition
property guaranteed after the execution of an instruction.
→ See L5, L8
PPQ
Pulses Per Quarter note. Temporal resolution of a MIDI file. 480 PPQ = 480 ticks per quarter note.
→ See I4
Precondition
property required before the execution of an instruction.
→ See L5, L8
Predictive coding / free energy
principle (Friston) according to which the brain minimizes surprise (prediction error).
→ See L21
Preference rule
In GTTM, a rule that indicates a tendency rather than a strict obligation.
→ See M4, M6
Premise
a condition required to apply a rule (above the horizontal bar).
→ See L6
Primary
The element before ! — must occupy time (gate, cv, or silence)
→ See S7
Prime
apostrophe (') indicating “the new value”. σ' = “sigma prime” = new state.
→ See L6
Probabilistic monad
a monad allowing the composition of probability distributions.
→ See L7
Probability distribution
a function associating each possible outcome with its probability. The sum of probabilities is 1.
→ See L7
Process
in process algebra, an entity that performs actions and can interact with other processes. A process is defined by its observable behavior.
→ See L11
Process with memory
Stochastic process where the probability of an event depends on the history. BP3 with dynamic weights is technically extended-state Markovian (counters are part of the state), but the observable behavior is memory-based.
→ See B1
Prod
LCM (least common multiple) of all duration ratios in a piece. Determines the resolution of the integer grid of the phase diagram.
→ See B12
PROD (mode)
BP3’s production mode — the grammar generates musical sequences by derivation. Corresponds to modus ponens.
→ See B8, L13
Production rule
Instruction of the form $A \to x$ indicating that A can be replaced by x.
→ See B1, B3, L1, M4
Progression (harmonic)
Movement from one chord to another that creates tension and a sense of direction.
→ See M6
Prolongation
Relationship where a musical event extends or elaborates another without creating a new harmonic direction.
→ See M6, S5
Prolonged rest (UndeterminedRest)
Silence of indefinite duration, noted as ... in BP3. Equivalent to a fermata.
→ See B2
Protocol
set of rules defining how two systems communicate.
→ See I4
PRPR (Prolongational Reduction Preference Rules)
Preference rules for prolongational reduction. Describe how we perceive tension/resolution relationships.
→ See M6
PSPACE-complete
A class of problems solvable in polynomial space but for which no polynomial-time algorithm is known. Parsing context-sensitive grammars is PSPACE-complete.
→ See L15, L17
Pumping lemma
A proof tool in language theory used to show that a language is not context-free.
→ See B6
Pushdown automaton
A finite automaton augmented with a stack (LIFO memory). Can push and pop symbols, allowing it to manage nesting.
→ See L1, M2
Q
QAVAID (Question Answer Validated Analytical Inference Device): Separate Prolog II program (1988-1990) for interactive grammatical inference, developed by Bel & Kippen. Never integrated into BP3, abandoned. The name also means “grammar” (قواعد) in Arabic/Urdu.
- Round-trip test
A validation test where sequences produced by an inferred grammar are submitted to the musician who provided the original examples. If accepted, the grammar has captured the tacit rules. Musical equivalent of Morris’s commutativity test.
→ See B8
Qualifier
Qualifier [] for the BP3 engine (speed, weight, tempo…)
→ See S13
Quantization
aligning changes to a time grid — the change takes effect at the next beat or cycle
→ See S11
R
Rasgueado
A flamenco guitar technique consisting of rapid string sweeps, typically alternating downward (down-strum) and upward (up-strum) movements.
→ See M12
Rate-distortion
theory (Shannon) of the minimum number of bits to transmit a message at a given fidelity. Tolerating a little loss allows for more compression.
→ See L21
raw_value
Raw value (any text up to , or ]) for engine keys
→ See S12
Recursion
Property of a rule that can apply to its own result, allowing for nested structures.
→ See M4
Reductional tree
Hierarchical structure where each level simplifies the lower level by keeping only the structurally important elements.
→ See M6
Referential semantics
The ability of language to talk about things in the world (the word “cat” refers to an animal).
→ See M4
Regular expression (regex)
A compact notation for describing text patterns. Equivalent in power to a finite automaton.
→ See L1
Regular language
a language recognizable by a finite automaton (Type 3). Individual MIDI messages form a regular language.
→ See M1
RELAX NG
an XML validation format more expressive than XSD, corresponding to a complete regular tree language. Used by MEI.
→ See M2
Renormalization
Recalculation of probabilities after weight modification. If weights change from $[50,\, 1]$ to $[38,\, 1]$, probabilities are recalculated from $[98\%,\, 2\%]$ to $[97.4\%,\, 2.6\%]$.
→ See B4
REPL
Read-Eval-Print Loop — an interactive console that maintains state between commands
→ See S4
Reserved Word
a word that the language reserves for itself — the user cannot redefine it or use it as a name
→ See S2
Resolver
Downstream component (1 per actor) that translates token → frequency via the 5 pitch layers
→ See S10, S3, S9
Reversible grammar
A grammar designed to be used in both directions (generation and parsing) without transformation. Examples: GF, unification grammars.
→ See L13
Reward prediction error
gap between expected and received reward, signaled by dopamine (Schultz); neural substrate of surprisal and update.
→ See L21
RHS (Right-Hand Side)
Right side of a rule — the result of rewriting. Can be empty (ε-production). 23 possible element types.
→ See B10, B3
RHSElement
Union type of the 19 node types that can appear on the right-hand side of a rule
→ See B11
Rightmost (right derivation)
Strategy that always replaces the rightmost non-terminal.
→ See B3
RND (BP3 mode)
Random mode, where rules are chosen randomly according to their weights.
→ See B3
rule_prefix
Unique identifier of a rule (gram#N[M]). N = block index, M = rule index within the block.
→ See B10
Running status
a MIDI optimization where the status byte can be omitted if it is identical to the previous one. Requires the parser to remember the last status.
→ See M1
Runtime
an execution environment that consumes the timestamped sequence produced by the engine (downstream layer)
→ See S1, S2, S4
RuntimeQualifier
Qualifier () for the runtime (vel, pan, wave…) — compiled into _script(CTn)
→ See S13
S
S-attributed
a class of attribute grammars containing only synthesized attributes. Evaluated in a single bottom-up pass, compatible with LR parsing.
→ See L10
Sam
First beat of the tāla cycle — the point of resolution for Indian cadences.
→ See B3, B6, M5
Saussure, Ferdinand de
Swiss linguist (1857-1913), founder of structural linguistics, known for the notion of the arbitrariness of the sign.
→ See M4
Scaling
Internal variable of PolyMake() which, combined with speed, determines the effective tempo (speed/scaling). Modified by *N, **N and the denominator of _tempo(x/y).
→ See B12
Scope
The visibility area of a variable — each runtime has its own, isolated from others
→ See S4
Secondary
The symbol after ! — triggers at the same instant as the primary
→ See S7
Semantic compositionality
Principle (attributed to Frege) according to which the meaning of an expression is constructed from the meaning of its parts (“big cat” = meaning(big) + meaning(cat)).
→ See M4
Semantic domain
mathematical set in which programs are interpreted (integers, functions, distributions…).
→ See L5, L7
Semantic rule
an equation or function that defines how to calculate the value of an attribute based on other attributes. Each grammar production is accompanied by its semantic rules.
→ See L10
Semantics
formal study of the meaning of programs.
→ See L5
Semilinearity
A property of a language whose Parikh vectors (counting the occurrences of each symbol) form a semilinear set. Intuitively, word lengths grow in a regular manner.
→ See L9
Session View
Ableton Live’s grid view where clips are launched freely, without a timeline
→ See S11
Shared derivation forest
A data structure that compactly represents (in $\mathcal{O}(n^3)$) an exponentially large number of derivation trees. Non-determinism is compressed, not eliminated.
→ See L15
Shuffle
A ternary rhythm in blues and rock, based on a triplet subdivision.
→ See M5
Sign reversal
for constrained generation, the asymmetry reverses—generating becomes harder than analyzing.
→ See L17
Simultaneous Group
a set of events attached to the same instant, often factorized into a macro
→ See S7
SimultaneousGroup
AST node for Sa!dha!spotlight (primary + secondary, temporal)
→ See S12
Small-step
semantics where each transition (denoted $\to$) represents a single step of execution.
→ See L6
SMF
Standard MIDI File. MIDI file format (.mid).
→ See I4
SMF (Standard MIDI File): MIDI file format (.mid). Chunk structure (header + tracks).
- Status byte
a MIDI byte whose most significant bit is 1 (values 128-255). Identifies the message type and channel.
→ See M1
Smooth time
Temporal mode of BP3 (_smooth) where durations are intrinsic properties of objects, without reference to a pulsation. Implements Boulez’s “smooth time”.
→ See B12, S5
SOS
Structural Operational Semantics — formal framework introduced by Plotkin in 1981 for defining programming languages.
→ See L6
Sound-object
Musical entity with metric and topological properties, more general than a note
→ See B13, B9
Spec
Permanent properties of a terminal (timbre, sample, decay) — resolved once at loading
→ See S14
SpecialFn
BP3 special function (_tempo, _smooth, _legato, etc.) — 30+ functions
→ See B11
Speed
Internal variable of PolyMake() representing the current speed of the stream. Modified by /N, \N and the numerator of _tempo(x/y).
→ See B12
SpeedRatio
Speed/scale operator (/2, *3, **3, \2)
→ See B11
Spines
in Humdrum, vertical columns of a \\kern file, each representing a voice or a musical dimension
→ See M7
Staccato
Detached playing style, where each note is played briefly. Indicated by a dot above or below the note.
→ See I5
Standalone backtick
A backtick in the flow of a rule, executed at the moment of derivation — requires a runtime tag
→ See S4
Start symbol
The initial non-terminal from which all derivation begins (often S for “Sentence” or “Start”).
→ See B2
State transformer
a function of type State → State. An imperative command is viewed as a state transformer.
→ See L7
Step
An elementary interval in the temperament grid
→ See S15
Stochastic
Involving a random element. A stochastic process is one whose evolution depends on chance.
→ See B1, L6, M3
Stochasticity
random or probabilistic nature of a process. A stochastic system can produce different results with each execution.
→ See L5
Strengthening
replacing a precondition with a stronger (more restrictive) condition. If we know that $\{x > 0\}\; C \;\{Q\}$, then $\{x = 5\}\; C \;\{Q\}$ is also valid because $x = 5$ implies $x > 0$.
→ See L8
Striated time
Concept from Boulez (1963) designating a temporal flow divided by regular reference points (pulsation, measure). Default mode of BP3 (_striated).
→ See B12, S5
Strongly-timed
ChucK’s paradigm where time is a native type of the language, manipulable like any other data
→ See M7
Structural ambiguity
A property of a sentence that allows multiple derivation trees for the same grammar. Frequent in recognition, absent in generation.
→ See L13
Structural Symbol
a character (or group of characters) with a fixed syntactic meaning
→ See S2
Strum
A rapid sweep across guitar strings. A down-strum (D) goes from low to high; an up-strum (U) goes from high to low.
→ See M12
SUB (BP3 mode)
Substitution mode — parallel derivation where all candidate rules apply simultaneously to the work string, as in L-systems.
→ See B3
SUB1 (BP3 mode)
Substitution 1 mode — a single pass of rewriting, leftmost, deterministic. Rules are tested in file order.
→ See B3
Substitution
A TAG operation that replaces a marked leaf node ($\downarrow$) with an initial tree of the corresponding type. Analogous to derivation in a CFG.
→ See L9
Substitution $Q[x/e]$
an operation that replaces each occurrence of variable $x$ with expression $e$ in formula $Q$. Example: $(x > 3)[x/(x + 1)] = (x + 1 > 3) = (x > 2)$.
→ See L8
Surprisal
$S(w_i) = -\log_2 P(w_i | w_1 \ldots w_{i-1})$. Measures the information contributed by a token in context. Zero for the generator, positive for the parser.
→ See L15
Surprisal (predictive surprise)
$-\log_2$ of the probability an event had under the current model. In bits. Measurable without knowing the true grammar.
→ See L21
Symbolic time
Representation of time in BP3 in the form of rational fractions (Q), independent of physical milliseconds.
→ See B12
SymbolWithTriggerIn
AST node for Sa<!sync (symbol + attached incoming trigger)
→ See S12, S13
Sync tag
Synchronization point <<WN>> between polymetric voices. Rendezvous mechanism.
→ See B10
Syntax tree
Tree-like representation of a derivation, with the start symbol at the root and terminals at the leaves.
→ See B3
SynthDef
in SuperCollider, a synthesizer definition as a graph of audio generators
→ See M3
Synthesized attribute
an attribute whose value is calculated from the attributes of child nodes. Information flows bottom-up in the tree. Example: the val of an arithmetic expression node.
→ See L10
Σ (capital sigma)
summation symbol. $\Sigma w_i = w_1 + w_2 + \ldots + w_n$.
→ See L6
T
Tag
XML syntax element enclosed by < and >, such as <note> or </note>.
→ See I5
TAG (Tree Adjoining Grammar)
A grammatical formalism that manipulates elementary trees (initial and auxiliary) via two operations: substitution and adjunction. Introduced by Joshi (1975).
→ See L9
Tala
Indian rhythmic cycle, structured in groups with specific strokes (e.g., Tintal = 16 beats).
→ See M5
TEM (BP3 mode)
Templates mode, which exhaustively derives a sub-grammar to generate a catalog of structural skeletons (TEMPLATES: section).
→ See B3
TEMP (mode)
BP3’s structural exploration mode — exhaustively enumerates all structural skeletons that the grammar can produce (ignoring weights). The resulting catalog can optionally be used by ANAL as an alternative recognition strategy. TEMP is not a prerequisite for ANAL. In Shannon’s terms: builds the decoder’s dictionary.
→ See B8
Temperament
Mathematical interval grid — division of frequency space into steps
→ See S9
Template
Structural skeleton pre-calculated by the TEMP direction. Stored in the TEMPLATES: block.
→ See B10
Template matching
The central mechanism of ANAL mode: superimposing a sequence to be analyzed onto the patterns defined by the grammar rules.
→ See B8
Terminal
Final symbol that appears in the output and cannot be rewritten. By convention, written in lowercase.
→ See B1, B2, L1, L6
terminalActorMap
Dictionary {BP3 terminal → actor} — allows the dispatcher to identify the actor
→ See S10, S13
Tetrachord/Jins
4-note fragment spanning a fourth — basic building block of Arabic and Turkish scales
→ See S9
Theka
Basic pattern of an Indian tāla, played as an ostinato by the tabla. A fixed sequence of bols that defines the character of the rhythmic cycle.
→ See B1, B2, B3
Tick
smallest unit of time in a MIDI file. The number of ticks per quarter note is defined by the PPQ.
→ See I4
Tihai
In Indian music, a final cadence where a motif is repeated three times, leading to the sam (the first beat of the rhythmic cycle, a point of convergence).
→ See M4, M5
Tihāī
Indian cadence where a motif is repeated exactly three times to land on sam. Corresponds to BP3’s SUB mode.
→ See B3, B4, B6
Time pattern
In BP3, a symbol (t1, t2…) defining a relative duration in smooth time. In striated mode, time patterns have zero duration.
→ See B12
Time-object
The elementary building block of BP3 — any sequence of messages possessing a duration. The generic term includes notes, Csound instructions, and any temporal event.
→ See B9
Time-setting
Temporal placement of sound-objects under constraints (Bel 1992)
→ See B13, B9
Timewise
File organization by measure then by instrument.
→ See I5
Tintāl
The most common tāla (rhythmic cycle) of North Indian classical music: 16 beats in 4 groups of 4.
→ See B1, B3
Token
Basic lexical unit (word, number, operator) recognized by a parser. Corresponds to the terminals of the grammar.
→ See B2
Tokenizer
Step 1 — breaks the source into tokens, reads alphabets and octaves
→ See S10
Tonic
The resting note or chord of a tonality (e.g., C in C major), the point of tension resolution.
→ See M4
Tonic (I)
First degree of the scale, a point of rest and harmonic stability.
→ See M6
Tonic shift
transposition by changing the reference note — preserves all ratios
→ See S15
Top-down parser
A parser that starts from the start symbol and tries to derive the text by applying the rules.
→ See L1
Topological properties
Characteristics of a sound-object related to its neighborhood relationships (truncation, overlap, adjacency).
→ See B9
Total correctness
property $[P]\; C \;[Q]$ — $C$ terminates AND $Q$ is true. Combines partial correctness and termination.
→ See L8
Trace
a sequence of observable events produced by a process. The set of traces of a process is the simplest semantic model in CSP.
→ See L11
Transducer
a machine that transforms an input into an output. An FST transforms strings; a tree transducer transforms trees (ASTs). Compilers are tree transducers.
→ See L11
Transition
a rectangular node in a Petri net. Represents an action. Fires when all its input places have enough tokens.
→ See L12, L5
Translational semantics
semantics that defines the meaning of a program by its translation into a target language. The meaning of P is the meaning of T(P) in the target language.
→ See L11
Transpile
to convert code from one language to another of the same level of abstraction
→ See M3
Transpiler
a program that converts source code from one language to another at the same level of abstraction
→ See M7, S1
Transport
Output protocol for timestamped data (Web Audio, MIDI, OSC)
→ See S10, S3
Tree (computer science)
Hierarchical data structure with a root, intermediate nodes, and leaves. Each node (except the root) has a unique parent.
→ See M6
Tree automaton
a machine that recognizes trees (rather than strings). Used for validating XML documents against a schema.
→ See M2
Trigger
An instantaneous pulse of zero duration
→ See S3
True concurrency
a concurrency model that distinguishes “A and B simultaneous” from “A then B” or “B then A”. Captured by Petri nets. – $\tau$ (tau): an internal action in CCS, invisible from the outside. Results from synchronization between an action and its co-action.
→ See L12
TSRPR (Time-Span Reduction Preference Rules)
Rules for identifying group heads in time-span reduction.
→ See M6
Tuning
Concrete scale = which steps of the temperament to use + reference frequency
→ See S9
Tuplet
In Western notation, a group of compressed notes (triplet = 3 notes in the time of 2).
→ See M5
Turing machine
A theoretical model of computation with an infinite tape, a read/write head, and transition rules. Can compute anything that is computable.
→ See L1
Tāla
Rhythmic cycle structuring Indian classical music (e.g., tintāl = 16 beats, jhaptāl = 10 beats).
→ See B2
U
Undetermined rest
Silence ... whose duration is calculated by PolyMake()
→ See B13
Union (∪)
Set operation that combines two sets. A ∪ B contains all elements of A and all elements of B.
→ See B2
Universal grammar
Chomsky’s hypothesis that all humans are born with innate linguistic principles.
→ See M4
Ursatz
Schenker’s term (German, “original structure”) referring to the fundamental harmonic and melodic skeleton of a tonal piece.
→ See M4
V
Variable
The |x| construction where the first occurrence sets a value and subsequent ones replicate it. Allows for the expression of exact repetition constraints impossible in CFGs.
→ See B6, S8
Variant (termination function)
a positive integer expression that strictly decreases at each iteration of a loop. Its existence proves termination.
→ See L8
Velocity
intensity of a note (0-127), corresponding to the “strike force.” Generally affects volume and/or timbre.
→ See I4, M3
Vibhāg
Section of a tāla. Tintāl has 4 vibhāgs of 4 beats each.
→ See B2, B3
Voice
Melodic line within a part (for polyphony on a staff).
→ See I5
VST
Virtual Studio Technology. Audio plugin format allowing virtual instruments and effects to be added to a DAW.
→ See I4
Vādi
Dominant note of a raga, the most frequent and important. Its regular presence can be modeled by a BP3 flag.
→ See B4
W
Weakening
replacing a postcondition with a weaker condition (less precise but still correct). If $x = 6$ is true, then $x > 0$ is also true: the postcondition has been weakened.
→ See L8
Weakest precondition (wp)
the least restrictive condition $P$ such that $\{P\}\; C \;\{Q\}$ is valid. Notation: $\text{wp}(C, Q)$. Introduced by Dijkstra (1975).
→ See L8
Weakly context-sensitive
a class of languages more expressive than context-free grammars, but still parsable in polynomial time (TAG, CCG); BP3’s flags touch upon it, its variables exceed it; see L9
→ See S1
WebAssembly (WASM)
a binary execution format that allows compiled code (here BP3, written in C) to run in a browser
→ See S1
Weight
Numerical value <N> or <N-M> controlling the probability of rule selection in RND mode.
→ See B10
Wildcard
The ?N construction that captures an arbitrary portion of the string. In PROD mode: capture on the left side, reinjection on the right side (context-sensitive rewriting between grammars). In ANAL mode: pattern matching for membership testing. Works in both directions—see B8.
→ See B6, S8
X
XML
eXtensible Markup Language — structured text format with nested tags.
→ See I5
XSLT
eXtensible Stylesheet Language Transformations — language for transforming XML into another format.
→ See I5
Ρ
ρ (rho)
Greek letter conventionally used to represent an environment (variable → value dictionary).
→ See L7
Σ
σ (sigma)
Greek letter conventionally used to represent a state (program memory).
→ See L7