B6) Homomorphisms, Variables, and Context

When BP3 Goes Beyond Context-Free Grammars

Some BP3 constructions cannot be expressed in a classic context-free grammar. They introduce memory, context, and flow control.

Where does this article fit in?

After covering probabilities (B1), vocabulary (B2), derivation rules (B3) and dynamic control (B4), this article explores the advanced constructions of BP3 (Bol Processor 3, cf. I2): variables, homomorphisms, wildcards, and context markers. These mechanisms make BP3 a system far more powerful than a simple context-free grammar — they bring it closer to context-sensitive grammars (L1), or even Turing-complete languages. The details of the translation into SuperCollider code are covered in B7.

Why is this important?

A Context-Free Grammar (CFG) is an elegant but limited tool. It cannot express certain constraints that are nevertheless natural in music:

Repeating exactly the same motif: If a theme appears twice in a piece, a CFG cannot guarantee that the two occurrences are identical. Each derivation is independent.
Transforming a motif according to an external rule: Transposing a melody to minor, applying an inversion — these operations require a memory of what has been played.
Reacting to context: Playing a different motif depending on what precedes or follows it.

Let’s take an analogy with kathak, the classical dance of North India, intimately linked to the tabla and BP3. A CFG is a kathak choreographer who gives general instructions: “do a tatkar (rhythmic step), then a chakkar (pirouette)”. But they cannot say “repeat exactly the same tatkar as before” or “if the tablist played a dha (resonant bol), respond with a tin (dry bol)”. For this, memory and context sensitivity are needed — exactly what the constructions we are about to explore provide. This is no coincidence: Bernard Bel and James Kippen developed BP3 precisely to model these interactions between tabla and dance in the Lucknow tradition [BelKippen1992a].

The idea in one sentence

BP3 extends CFGs with variables (exact repetition), homomorphisms (motif transformation), wildcards (pattern matching), and context markers — constructions that make BP3 a context-sensitive language.

Let’s explain step by step

1. Variables: the tihāī and exact repetition

The problem

In Indian music, the tihāī (a cadence where a motif is repeated exactly three times to land on sam, the first beat of the tāla cycle — the rhythmic resolution point towards which all improvisation converges) requires that the three repetitions be identical. If I write:

gram#1[1] S --> A - A - A

In RND mode (Random — random derivation, cf. B3), each A is derived independently. The first A could yield dha tirakita dhin and the second tin ta ka. This is not a tihāī — these are three different motifs, and the cadence effect is lost.

The BP3 solution

BP3 introduces the variable with the notation |x| (identifier between pipes):

gram#1[1] S --> |x| - |x| - |x|

This rule reads: “derive something, call it x, then play x two more times — exactly the same thing, separated by silences”. The variable captures the result of the first derivation and replicates it wherever it appears. This is exactly the structure of a tihāī [BelKippen1992a].

Variable vs non-terminal

Do not confuse |x| (variable) with a non-terminal. A non-terminal is a category that will be derived independently at each occurrence. A variable is a binding: the first occurrence sets the value, subsequent ones reuse it.

Construction Behavior

Non-terminal A Each occurrence derived independently

Variable \|x\| First occurrence sets the value, subsequent ones replicate it

Construction	Behavior
Non-terminal `A`	Each occurrence derived independently
Variable `\\|x\\|`	First occurrence sets the value, subsequent ones replicate it

Complete example

gram#1[1] S --> |x| - |x| - |x|
gram#1[2] |x| --> dha tirakita dhin dhin
gram#1[3] |x| --> tin ta dha ge na

Possible result: dha tirakita dhin dhin - dha tirakita dhin dhin - dha tirakita dhin dhin — a perfect tihāī, where the same bol motif is played three times to land on sam (first beat of the cycle).

Why it’s context-sensitive

The link to Chomsky’s hierarchy (L1) is direct. The language { ww | w ∈ Σ* } — the set of all strings formed by a word w followed by its exact copy, where Σ* (sigma star) denotes the set of all possible words over the alphabet Σ (sigma) — is not context-free. This is a classic result: the pumping lemma (a proof tool that shows a language cannot be generated by a CFG) prohibits it. BP3 variables allow expressing exactly this type of constraint, which places BP3 at the context-sensitive (Type 1) level of the hierarchy.

2. Homomorphisms: transforming a motif

The idea

A homomorphism in mathematics is a function that preserves structure. In music, it is a transformation applied note by note: transposition, inversion, retrograde. BP3 integrates this concept directly into its syntax.

Homomorphism in music

Think of an Instagram filter for music. The “sepia” filter doesn’t change the composition of the photo; it transforms each pixel. Similarly, a musical homomorphism doesn’t change the structure of the melody; it transforms each note: moving up a third, switching to minor, inverting intervals.

BP3 Syntax

BP3 uses three markers:

Marker	Syntax	Role
Master	`(= ...)`	Defines the reference motif
Slave	`(: ...)`	Replicates the motif with transformation
Ref	identifier	References an external homomorphism file (`-ho.*`)

Example:

gram#1[1] S --> (= Sa Re Ga Ma) (: minor) (: retrograde)

The master defines the motif Sa Re Ga Ma. The first slave applies the “minor” homomorphism. The second applies “retrograde”. Result: three versions of the same motif — the original, its minor version, and its retrograde version.

Formally, a BP3 homomorphism is a morphism of free monoids (a transformation that preserves the concatenation operation of words). Let’s break it down:

h is the transformation function — the mapping table (for example: Sa → Re, Re → Ga, Ga → Ma, etc.)
Σ* (sigma star, already encountered above) denotes the set of all possible words over the musical alphabet
h : Σ* → Σ* means that h takes a musical word and returns another musical word
The fundamental property is h(αβ) = h(α)h(β), where α (alpha) and β (beta) are any two musical fragments: transforming the sequence αβ (alpha followed by beta) is equivalent to transforming α and β separately and then concatenating the results

In plain terms: each note is transformed independently, and the order is preserved. If h transposes by a whole tone and the phrase is Sa Re, then h(Sa Re) = h(Sa) · h(Re) = Re Ga [Bel1998].

Graha bheda — raga transposition as homomorphism

In Indian music, graha bheda (graha = starting note, bheda = change) is a technique where the fundamental note (Sa) of a raga is shifted to another degree, giving rise to a new raga. For example, raga Kalyāṇ (Sa Re Ga Ma# Pa Dha Ni) becomes raga Bilaval (Sa Re Ga Ma Pa Dha Ni) by lowering the Ma# by a semitone.

This is exactly a homomorphism in the BP3 sense: the master is the original phrase in one raga, the slave applies a note-by-note mapping that produces a phrase in another raga. The melodic structure is preserved, only the pitches change — the very definition of a morphism [Bel1998].

3. Wildcards: capturing and transforming without defining

Wildcards (jokers) — denoted ? (anonymous), ?1, ?2 (named) — introduce pattern matching into grammar rules. They are analogous to capture groups in regular expressions (regex): on the left side of a rule, ?1 captures an arbitrary portion of the string; on the right side, ?1 re-injects it.

Contrary to what one might think, wildcards are not reserved for BP3’s analytical mode. They function fully in both directions — PROD (production) and ANAL (analysis) — with complementary semantics.

In PROD mode: context-sensitive rewriting

Imagine a two-stage grammar. The first grammar (GRAM#1) generates a sequence with markers:

gram#1[1] S --> R1 dha tirakita dhin dhin R2

The second grammar (GRAM#2) uses wildcards to transform this sequence:

gram#2[1] R1 ?1 R2 --> ?1 ?1

This rule reads: “find the pattern R1…R2, capture everything between the two markers (here dha tirakita dhin dhin), and replace the whole thing with two copies of this captured content”. Result:

dha tirakita dhin dhin dha tirakita dhin dhin

The wildcard ?1 captured the content between the markers (left side) then re-injected it twice (right side) — without ever knowing what that content was. This is context-sensitive rewriting: the rule depends on the context (markers R1 and R2) and operates on content it does not define.

Manipulating objects without defining them

This is the fundamental insight of wildcards in PROD mode: they allow manipulating structures without naming them. The rule R1 ?1 R2 --> ?1 ?1 doesn’t know if ?1 contains tabla bols, sitar notes, or robot commands — it only knows that there is “something” between two boundaries, and it duplicates it.

Here we touch upon a primitive form of the notion of object in programming: an entity manipulable by its interfaces (the markers) rather than by its internal structure. This is also what makes wildcards so powerful — and so different from variables.

Wildcards vs variables: two copying mechanisms

Both capture and replicate, but at different levels:

Variable `\\|x\\|`	Wildcard `?1`
Scope	Within the same rule
Captures what	The result of a derivation
When	During derivation
Musical analogy	“Play this theme, then play it again identically” (tihāī)

Variables create repetition (the tihāī). Wildcards create transformation (extracting a motif and recontextualizing it).

In ANAL mode: the membership test

In analytical mode, wildcards revert to their classic role of pattern matching. The rule:

gram#1[1] ?1 - ?1 - ?1 --> #

means: “verify that the sequence to be analyzed is a tihāī — three repetitions of the same motif separated by silences”. If the sequence dha tirakita dhin - dha tirakita dhin - dha tirakita dhin is submitted as input, the wildcard ?1 captures dha tirakita dhin and verifies that the three occurrences are identical.

This is the dual of PROD mode: in production, the wildcard transforms; in analysis, it recognizes. Two sides of the same coin — a topic developed in B8.

4. Context markers: the grammar looks around itself

The problem with CFGs

In a CFG, when A is replaced by x y z, the decision never depends on what surrounds A. This is the very definition of “context-free”. But in music, context is fundamental: you don’t play the same thing after a crescendo as after a silence.

BP3 markers

BP3 introduces context markers that make rules sensitive to their environment. The most important is the distant marker:

gram#1[1] |Resolution| --> (|sam|) dha tirakita dhin dhin

This rule plays the motif dha tirakita dhin dhin only if the marker sam is present somewhere in the current string — exactly like a tablist “aims” for sam to conclude an improvisation [BelKippen1992a].

A rule that says “replace A with xyz only if B is present somewhere” cannot be expressed in a CFG. It is a context-sensitive rule (Type 1):

In CFG (Type 2) :  A --> xyz         (always applicable)
In CSG (Type 1) :  B A --> B xyz     (only if B precedes A)

BP3 generalizes this principle with its markers, allowing distant conditions, not just on immediate neighbors.

The ālāp — the textbook case for context markers

The ālāp is the opening of a raga where notes are introduced one by one: first Sa alone, then Sa-Re, then Sa-Re-Ga, and so on. This structure of progressive accumulation is impossible to express properly with the 5 derivation modes (B3) or even flags (B4), which would require a rule for each step (see the ālāp note in B4).

Context markers offer an elegant solution:
gram#1[1]                    |Phrase| --> Sa |Ornement_Sa|
gram#1[2] (|Re_introduit|)  |Phrase| --> Re |Ornement_Re| |Phrase|
gram#1[3] (|Ga_introduit|)  |Phrase| --> Ga |Ornement_Ga| |Phrase|

Rule 2 is applicable only if the Re_introduit marker is present in the context — meaning Re has already been “unlocked” in a previous phrase. The grammar gradually accumulates its note vocabulary, exactly as a musician explores a raga.

This is a strong argument for explaining why Bel added context-sensitive extensions to BP3: the combinatorial structures of tabla (kayda, tihāī) are well expressed with modes and flags, but the accumulative structures of raga (ālāp, barhat) require context sensitivity. The two traditions — tabla and raga — demand different extensions.

5. Flow control and empty productions

Two additional constructions complete the arsenal:

_goto(gram, rule) — arbitrary jump. This instruction jumps to a specific rule in a specific grammar, like a goto in programming. It is a flow control mechanism that goes far beyond CFGs — it allows loops and arbitrary branching.

_lambda() — empty production. The non-terminal simply disappears, leaving no trace. In formal theory, we write A → ε (epsilon, the empty string). This is useful for optional structures: “there might be an ornament here, or nothing at all”.

The price of power

The more expressive a language is, the harder it is to analyze automatically. CFGs (Type 2) can be parsed in polynomial time. CSGs (Type 1) are decidable but potentially exponential. BP3’s context-sensitive constructions provide remarkable compositional power, but at the cost of complexity: some (wildcards, context markers, goto) cannot be resolved by a static transpiler — they require a full derivation engine (see B7).

Position in Chomsky’s hierarchy

Let’s place these constructions in the hierarchy (L1):

Level	Type	BP3 Constructions
Type 3	Regular	Simple sequences of notes
Type 2	Context-free	Non-terminals, derivation rules, modes (B1-B3)
Type 2+	Mildly context-sensitive	Bounded flags (B4) — same area as TAG, CCG
Type 1	Context-sensitive	Variables, context markers, wildcards
Type 0	Recursively enumerable	`_goto` (arbitrary jump), unbounded flags

Articles B1-B3 cover the context-free core. B4 (flags) pushes towards mildly context-sensitive. This article shows how advanced constructions propel BP3 up to the context-sensitive level, and even beyond. It is this parameterizable gradation — from Type 2 to Type 0 depending on the activated mechanisms — that makes BP3 formally original.

Key takeaways

Variables (|x|) allow repeating exactly the same derived motif — the tihāī is its perfect application. This capability is impossible in pure CFGs.
Homomorphisms ((= ...), (: ...)) transform motifs according to note-by-note mappings — graha bheda (raga transposition) is the natural musical example.
Wildcards (?1, ?2) capture and re-inject string fragments — in PROD mode for transformation (context-sensitive rewriting), in ANAL mode for recognition (membership test). They allow manipulating structures without defining them.
Context markers make rules sensitive to their environment — the ālāp (progressive introduction of notes) is the textbook case.
Flow control (_goto) and empty productions (_lambda) complete the arsenal beyond classic grammars.
BP3 is a parameterizable formalism: depending on the constructions used, it ranges from Type 2 (CFG) to Type 0 (Turing-complete).

Glossary

Ālāp: Opening of a raga where notes are introduced progressively. Its accumulative structure requires context markers — flags alone (B4) are not sufficient.
Bol: Mnemonic syllable of the tabla (e.g., dha, dhin, tin, ta). The “Bol” in “Bol Processor”.
Context-sensitive: Property of a grammar where the replacement of a symbol depends on its environment. Corresponds to Type 1 of Chomsky’s hierarchy.
Graha bheda: Technique of raga transposition by shifting the fundamental note (Sa), giving rise to a new raga. Formalizable as a BP3 homomorphism.
Homomorphism: Function that transforms each symbol in a string according to a fixed mapping, preserving the structure (morphism of free monoids).
Kathak: Classical dance of North India, linked to the tabla. Tablist-dancer interactions are a foundational case study for BP3.
Lambda (empty production): Rule that rewrites a non-terminal to the empty string (ε). The symbol disappears without a trace.
Context marker: BP3 construction that conditions the application of a rule on the presence of a symbol in the context.
Pattern matching: Mechanism for matching patterns. BP3 wildcards capture portions of derived strings for reuse.
Pumping lemma: A proof tool in language theory that demonstrates a language is not context-free.
Sam: First beat of the tāla cycle — the point of resolution towards which tihāī converge.
Tihāī: Indian cadence where a motif is repeated three times to land on sam. Formalizable in BP3 via variables: |x| - |x| - |x|.
Variable: |x| construction whose first occurrence sets a value and subsequent ones replicate it. Allows expressing exact repetition constraints impossible in CFGs.
Wildcard (joker): ?N construction that captures an arbitrary portion of the string. In PROD mode: capture on the left side, re-injection on the right side (context-sensitive rewriting between grammars). In ANAL mode: pattern matching to test membership. Works in both directions — see B8.

Prerequisites: L1, B2, B3
Reading time: 14 min
Tags: #homomorphisms #variables #context #BP3 #context-sensitive