IKS in Computational Systems Notes | B.Sc. (Computer Science) Semester 5 | Mumbai University | munotes

Ayurvedic classification is not a validated classifier. It is a structured diagnostic vocabulary. Treating it as a tested medical model is a claim nobody in this book makes.

What "computational thinking" means here

MU's first course objective asks you to see śāstra as a knowledge system "aligned with computational thinking". That phrase has four ordinary parts, and you will use all four in this paper.

Decomposition. Break a problem into parts that can be solved separately. Piṅgala breaks "list every metre" into "list every metre of one syllable" plus a rule for growing the list.

Pattern recognition. Notice that two different problems have the same shape. The count of metres with exactly three long syllables and the count of ways to choose three items from a set are the same number, and the Meru-prastāra computes both.

Abstraction. Throw away what does not matter. A syllable has a sound, a meaning and a length; Piṅgala keeps only the length, and that is why his rules are arithmetic.

Algorithm design. State the steps so exactly that someone who does not understand the problem can still carry them out. This is the test that separates a description from an algorithm, and chapter seventeen applies it to Piṅgala's own words.

Worked example, before anything else

Here is the smallest complete instance of the whole paper, so that the rest of the book has something to attach to.

The problem. A Sanskrit metre of three syllables. Each syllable is either short (laghu, written L) or long (guru, written G). List every possible metre.

The classical rule, from Piṅgala's Chandaḥśāstra with Halāyudha's commentary: write a row of all long syllables. Then, to get each next row, find the first long syllable from the left, make it short, make everything to its left long, and leave everything to its right alone. Stop when the row is all short.

Carried out by hand:

The observation that makes this a computer science paper. Write 1 for L and 0 for G, and read each row with the leftmost syllable as the units place: 000, 100, 010, 110, 001, 101, 011, 111. Those are 0, 1, 2, 3, 4, 5, 6, 7 in binary. The rule is counting in base two, and it is written down centuries before the positional notation it depends on reached Europe.

That claim is checked, not asserted. The program in chapter nineteen verifies it for every row of every metre up to fourteen syllables.

How to use this book

Read it in order. The chapters follow MU's printed module order exactly, so you can lay the syllabus page beside the contents and tick off labels.

Each module's last chapters are practice. They carry worked answers of the length the examination actually wants, which is five marks.

Do the code. Twenty of the fifty marks on this paper are one program you write, run and defend out loud. Every listing in this book has been run, and you should run them too.

Quick revision

• MU's course description calls these traditions "structured, rule-based, and algorithmic" and "analogous" to modern computer science concepts. Analogous is a testable claim.
• Five real correspondences: binary encoding, enumeration, index retrieval, binary exponentiation, and rule-based generation with conflict resolution.
• Three honest limits: no machine, no cipher in the Arthaśāstra, no validated classifier in Ayurveda.
• Computational thinking has four parts: decomposition, pattern recognition, abstraction, algorithm design.
• Laghu and guru, two values in one position, is the hinge of Module I.

Test yourself

1. MU's description uses one word that makes this paper falsifiable rather than decorative. Which word, and why does it matter?

"Analogous." An analogy asserts that two things do the same work. That can be shown or refuted, so every chapter has to argue its case instead of asserting a resemblance.

2. Give one correspondence between a classical Indian text and a modern computer science concept, and one place where the correspondence fails.

Piṅgala's prastāra enumerates every pattern of n two-valued symbols in the order of binary counting, which is exhaustive enumeration over an n-bit space. It fails as an account of computing because nothing executes it but a person: there is an algorithm and no machine.

3. Name the four parts of computational thinking and give the Piṅgala example of one.

Decomposition, pattern recognition, abstraction, algorithm design. Abstraction: a syllable's sound and meaning are discarded and only its length is kept, which is what allows the rules to be arithmetic.

4. Why does this book refuse to say the Arthaśāstra contains a cipher?

Because the text names cipher-writing and never states a method. Naming a requirement is not supplying an algorithm, and the difference is the whole distinction between a specification and an implementation.

The eight topics she prints

You may choose another relevant IKS topic, but these eight are the ones she names, and every one of them is built in full somewhere in this book.

The eight headings the submission must carry

She prints these too, and in this order. A submission that is missing one of them is missing marks that were free.

1. Title, in the form "IKS Concept as CS Concept"
2. Problem Statement
3. Conceptual Mapping Table
4. Algorithm Specification (Pseudo-code)
5. Working Code
6. Minimum 10 Test Cases
7. Complexity and Limitations
8. Conclusion

[The Internal Assessment: Building and Presenting the Implementation] is a complete worked submission under all eight headings, so you have a model and not a description.

What this means for how the book is written

Every algorithm in this book has been run. Not proof-read, run. The tables you will read are the output of programs, and the programs are printed beside them, because you are going to be marked on code that works.

Definitions are set out to be found. A five-mark answer opens with a definition and a viva opens with one. So each chapter's first section is a definition twice over: once in plain words and once in the wording you can write down.

Each module closes on practice. [Practice for Module I] and [Practice for Module II] carry worked answers at five-mark length, and the book's last chapter does the same for the cross-module question.

What it does NOT mean

It does not mean skipping the reading to write code. Her first required item is a problem statement in the form "IKS concept as CS concept", and her third submission heading is a conceptual mapping table. Both of those are marks for understanding the classical side, and a demo without them is half an answer.

It does not mean the paper is easy because it is two credits. Thirty hours of teaching and fifty marks, with individual components that each have to be passed, is the same structure as any other paper. The internal is harder than a class test, not easier.

Quick revision

• 50 marks: 20 internal, 30 external.
• External: 1 hour, Q.1 on Module 1, Q.2 on Module 2, Q.3 on both, each any 2 of 4 for 10 marks. An answer is worth 5 marks.
• Internal: ONE implementation, alone or in a pair, with a problem statement, a formal specification, working code, at least 10 test cases, and a correctness and limitations analysis, shown by a live demo and a viva.
• Eight topics are named and eight submission headings are required.
• This internal scheme is named as being for this course and not for the others.

Test yourself

1. How many marks does one written answer on this paper carry, and how do you know?

Five. Each of the three questions is worth 10 marks and asks for any 2 of 4 alternatives, so each attempted alternative carries 5.

2. What is different about this paper's internal assessment, and where is that stated?

It is an implementation project rather than class tests and assignments. The evaluation scheme in the syllabus circular splits its own list into "For Courses other than IKS in Computational Systems" and "For IKS in Computational Systems course", and only this paper gets the project.

3. Name the five things the implementation must include.

A problem statement in the form "IKS concept as CS concept"; a formal specification of the rules or algorithm; working code; at least ten test cases; and a short analysis of correctness and limitations.

4. Why is the last chapter of this book about cross-module answers?

Because Q.3 is set on Modules 1 and 2 together, so ten of the thirty external marks require you to relate a topic from one module to a topic from the other.

The third stage is the one that is usually missing from a bad set of notes, and it is the one that makes a definition trustworthy. A definition nobody has attacked is a guess.

The four layers a śāstra is published in

This is the structural fact that makes the classical literature navigable, and it is almost never explained to a student before they meet their first Sanskrit citation.

The sūtra text. Aphorisms, as short as two words, arranged in a fixed order and numbered. Piṅgala's Chandaḥśāstra and Pāṇini's Aṣṭādhyāyī are both sūtra texts. A sūtra is unreadable without the next layer, and that is a deliberate design choice, not a failure.

The vṛtti. A running gloss that supplies the words the sūtra left out and shows one worked instance of each rule. It is the reference implementation: it tells you what the rule actually does.

The bhāṣya. A full commentary that argues about the rule, considers objections, and states why the rule is worded as it is rather than some other way. Halāyudha's Mṛtasañjīvanī on Piṅgala is this layer, and most of what this book quotes from Piṅgala is quoted from it.

The vārttika. A critical layer on the commentary, noting where it is wrong, incomplete or over-general. It is the errata list, and its existence tells you the tradition expected its own commentaries to be checked.

Worked example: the same idea in both notations

The classical form. Piṅgala's sūtra for the one-syllable table is two words, "dvikau glau". Halāyudha's commentary expands it: write a ga above and a la below, and because the sūtra says "two", place two such pairs. Without the commentary the sūtra is undecipherable; with it, the operation is exact.

The modern form. A specification might read: for a metre of one syllable, the table of patterns is the ordered list (G, L). A documentation comment then explains that G stands for a heavy syllable and L for a light one and gives the table for n equal to two as an illustration.

The point of the comparison. Both have a terse normative core and a longer explanatory layer, and in both the normative core alone is insufficient to act on. The classical tradition made the separation explicit and gave each layer a name. Most modern codebases do not.

What a śāstra is NOT

It is not simply an old book. A hymn, a story and a chronicle are not śāstra, because none of them defines its terms or states rules for deriving new claims.

It is not necessarily correct. Formal and true are different properties. Ayurvedic classification is highly formalised and that says nothing about whether any particular classification is clinically right. A formal system can be rigorously wrong, and saying so is part of answering MU's "critically assess".

It is not a program. There is no machine. A śāstra is executed by a trained human reader, and the tradition invests heavily in training that reader, which is what the four layers are for.

Limits of the comparison

Two limits should be stated before the enthusiastic chapters begin.

The rules are not typed. Nothing in a sūtra text says what kind of object a rule takes. A modern specification can be checked mechanically for that; a sūtra is checked by a reader who already knows.

There is no separation between the system and its meta-system. Pāṇini's meta-rules are written in the same language and the same numbering as his ordinary rules. That is economical and it is also why the tradition needed the four layers: the distinctions live in the commentary, not in the notation.

Quick revision

• Śāstra: a systematised, rule-governed discipline with defined terms, ordered rules and a declared theory of evidence.
• Every śāstra declares three things: its terms, its rules and how they interact, and its admissible means of knowledge.
• The teaching order is enunciation, definition, critical examination, and the third stage is what makes a definition trustworthy.
• The four publication layers: sūtra, vṛtti, bhāṣya, vārttika, which are specification, reference implementation, commentary and errata.
• Formal is not the same as true, and formal is not the same as executable.

Test yourself

1. Define śāstra in one sentence fit for an examination.

A systematised body of rule-governed knowledge with defined terms, rules whose interaction is itself governed by stated principles, and a declared account of the admissible means of knowledge, transmitted as aphorisms with their own commentary.

2. Name the four layers a śāstra is published in and give the modern counterpart of each.

Sūtra, the specification; vṛtti, the reference implementation; bhāṣya, the explanatory commentary; vārttika, the errata. Halāyudha's Mṛtasañjīvanī is a bhāṣya on Piṅgala.

3. A student says "the Arthaśāstra is a śāstra, so what it says about taxation must be right." What is wrong with that?

It confuses being formal with being true. Formality is a property of how a system states and derives its claims; correctness is a property of the claims. A formal system can derive false conclusions perfectly.

4. Why is a sūtra deliberately incomplete on its own?

Because it was built for oral transmission, where the cost of a word is high and a trained teacher is assumed. The missing material is supplied by the vṛtti and bhāṣya, so the incompleteness is a division of labour between layers rather than a defect.

Worked example: two words that generate a table

Piṅgala's rule for the shortest metre is two words: dvikau glau.

What is in the text. "Two" and "ga and la", where ga names the heavy syllable and la the light one. Four syllables of Sanskrit.

What Halāyudha's commentary supplies. Write a ga, and below it write a la. Because the sūtra says "two", these are the two forms a one-syllable metre can take. He then reads the word "two" again in the next sūtra to build the two-syllable table, and so on.

What a modern statement of the same rule would need. An ordered list of the two symbols, a statement that a one-syllable metre has exactly two forms, a statement of which comes first, and a note on what the symbols mean. Perhaps twenty-five words.

The compression ratio, honestly. Four syllables against twenty-five words looks like a factor of ten. It is not, because the commentary is part of the system and the commentary on those four syllables runs to a paragraph. What the compression buys is not total size, it is the size of the part that must be memorised exactly.

The three costs, stated plainly

This is the section that separates an answer from an advertisement.

No random access. Because words carry over from earlier sūtras, you cannot read sūtra 8.24 without knowing what is in force from the sūtras before it. The text is a stream, not an array. A modern equivalent is a compressed file you must decompress from the beginning to read the middle of.

No redundancy. Every syllable is load-bearing, so nothing survives damage. Lose a word and the rule is not merely less clear, it is a different rule.

No error detection. A recited text has no checksum. The tradition's answer was social rather than technical: multiple lineages of reciters, and the vārttika layer whose job is to notice that a rule as received cannot be right.

What it does NOT mean

It does not mean the sūtra style is obscure on purpose. It is terse on purpose, which is a different thing. Every device listed above has a stated function, and the tradition documents all of them.

It does not mean a shorter sūtra is a better one. The measure the tradition actually applies is that a rule should state what is needed and nothing else. A rule that has been shortened past that point is criticised in the commentary, not admired.

It does not mean compression is free. The three costs above are real, and the whole four-layer publication scheme of the previous chapter exists to pay them.

Limits and the modern parallel

The honest parallel is not to source code, which is read by a machine that will not guess. It is to a wire format: a representation chosen to be small, whose meaning lives in a separate schema, which is unreadable without that schema, and which is brittle if a byte is lost.

Where the parallel breaks is that a wire format has a decoder that is itself mechanical and exact. A sūtra's decoder is a human being with years of training, and two trained readers can disagree. The commentaries are full of such disagreements, and this book records the ones that matter to its own claims.

Quick revision

• The sūtra method is compression driven by an oral medium: syllables, ambiguity and corrections are expensive; the reader's training is free.
• Four techniques: technical terms, single-letter markers, class names for sets, and carrying words over from earlier rules.
• "Dvikau glau", four syllables, generates the one-syllable table, with the commentary supplying the procedure.
• Three costs: no random access, no redundancy, no error detection.
• The modern parallel is a wire format with an external schema, not source code.

Test yourself

1. Why is a sūtra short? Give the reason in terms of the medium rather than of style.

Because the text lives in human memory and is transmitted by voice, so its size is its entire cost of ownership, while the reader's years of training cost the text nothing. The rational design pushes everything possible out of the text and into training and commentary.

2. Name the four compression techniques and say what each replaces.

Technical terms replace descriptions; single-letter markers replace statements about how a form may be treated; class names replace lists of elements; carrying words over replaces restating conditions in every rule.

3. State one cost of the sūtra method and give its modern analogue.

Words carry over from earlier sūtras, so there is no random access into the middle of the text. The analogue is a compressed stream that must be decoded from the start to read any part of it.

4. Is "shorter is better" the tradition's own standard? Justify your answer.

No. The standard is that a rule should state what is needed and nothing more; commentaries criticise rules that have been shortened past the point of stating their own conditions.

Among all these three means of knowledge, the knowledge derived from the instructions of the inspired comes first. After this, comes examination, with the aid of Observation and Inference.

Three separate claims are in those lines and all three are worth having.

Use all three. A diagnosis reached from one channel is not faultless, and he says so.

No single channel is complete. This is the strongest statement of the three and the most modern. It is the classical form of what an engineer means by not trusting a single sensor.

Testimony comes first in time. Not first in authority: first in order of use. You read the literature before you examine the patient, because without the literature you do not know what to look for. Charaka puts the argument as a question: what would one who has not been instructed succeed in knowing by examining with observation and inference?

Worked example: the same three in a modern system

Take a monitoring system that decides whether a web service is unhealthy.

Pratyakṣa. It measures response time directly from a probe. That is perception: contact with the object, reporting a particular fact.

Anumāna. It sees the error rate rising and the queue depth growing, and concludes the database connection pool is exhausted, which it cannot observe. That is inference, and it depends on a general connection between exhausted pools and those two symptoms. If the connection does not hold, the inference is wrong however good the measurements were.

Āgama. It consults a runbook written by the team that built the service, which says that this combination of symptoms in this service means the pool. That is testimony, and its reliability is exactly the reliability of the team that wrote it.

Now apply Charaka's three claims. A system using only the probe cannot say why. A system using only the runbook cannot notice something new. And the runbook has to be read before the probe is useful, because it tells you which numbers matter. His ordering is not piety; it is the right order.

What pramāṇa theory does NOT say

It does not say testimony outranks observation. Charaka's word is that instruction comes first, and his own explanation is that it comes first in sequence because it tells you what to examine. Nothing in the passage makes it the strongest evidence.

It does not make the list obviously three. Different schools close the list at different places, and Nyāya Sūtra 1.1.3's commentary enumerates them: the Cārvākas admit only perception; the Vaiśeṣikas and Bauddhas two; the Sāṃkhyas three; the Naiyāyikas four, adding comparison; and later schools add presumption, non-existence, probability and rumour. MU's three are the Sāṃkhya and Āyurvedic set. [The Four Pramāṇas of Nyāya, and Why Charaka Has Three] deals with the difference.

It does not settle what perception is. Nyāya Sūtra 1.1.4 imposes four conditions on perception precisely because "I saw it" is not a definition. The next chapter is about that.

Limits

The scheme has one structural weakness that a modern reader should see at once. It has no mechanism for revising the list. A pramāṇa is admitted or not, and a debate about whether comparison is an independent means of knowledge is conducted by argument, not by measurement. There is nothing in the apparatus resembling a calibration experiment.

The strength is the other side of the same coin: because the list is closed and public, an argument can be checked against it by anyone, which is what makes the debate rules of Module II enforceable.

Quick revision

• Pramāṇa: an admitted means of knowledge. MU names three: pratyakṣa, anumāna, āgama.
• Declaring them first is what makes fallacy detectable: a bad argument appeals to something off the list or fails a stated condition.
• Charaka: use all three; no single one suffices; instruction comes first in order of use.
• "By only one of these means of knowledge, knowledge does not arise of everything that should be known."
• Schools close the list at one, two, three, four, six or eight. Three is the Sāṃkhya and Āyurvedic set; Nyāya has four.

Test yourself

1. Define pramāṇa and name the three the syllabus prints.

A pramāṇa is an admitted valid means of coming to know something. The three printed are pratyakṣa (perception), anumāna (inference) and āgama or śabda (authoritative verbal testimony).

2. Quote or paraphrase Charaka's reason for using all three, and explain its modern form.

He says that with all three one should first fully examine a disease and the diagnosis then becomes faultless, and that by only one of them knowledge does not arise of everything that should be known. The modern form is that no single source of evidence is sufficient, so a reliable system combines direct measurement, inference and documented prior knowledge.

3. Why does Charaka put testimony first, and what does that ordering not mean?

First in order of use, because without prior instruction one does not know what to observe or what to infer. It does not mean testimony is the strongest evidence or that it overrides observation.

4. Give one weakness of pramāṇa theory as a theory of evidence.

It has no procedure for revising its own list. Whether a candidate means of knowledge is independent is settled by argument rather than by any measurement, so the set of admitted channels is fixed by dispute rather than by test.

A monitoring system has both: a number arriving from a probe, and the judgement that the number means the service is slow. The classical scheme is right that these are different things and that errors enter at the second step.

Worked example: four failures, one for each condition

A student is asked to record what is in a laboratory. Four of their entries are not perception, and each fails a different condition.

"There is a soldering iron in the next room, because I can smell hot flux." Fails contact. No sense has touched the iron. This is inference, and it belongs to anumāna.

"There is something on the far bench, but I cannot tell what." Fails determinate. The impression has not resolved.

"There is an oscilloscope, because the label on the trolley says so." Fails unnameable. The knowledge came through a word, not through the thing. This is testimony.

"There is water on the corridor floor," when the floor is dry and polished under a bright light. Fails non-erratic. A regular optical effect has produced a regular mistake.

Every one of the four is a real way a system goes wrong, and the value of the definition is that it names them apart.

Charaka's complication: the mind as a sixth sense

Kaviratna's note on the same topic records something the Nyāya definition leaves implicit:

As ordinarily understood, "pratyaksha" implies all that is acquired by the senses. As the mind, however, is regarded in Hindu philosophy as the sixth sense, that which is acquired by the mind is included within the word.

And Charaka's own line is that observation is "the result of observation which one acquires by one's own senses and mind."

This matters for the classification chapters of Module II. If the mind is a sense, then noticing that two symptoms usually occur together is itself a kind of perception rather than an inference, and the boundary between the first two pramāṇas moves. The honest thing to say in an answer is that the boundary is drawn differently in the two traditions and to name which one you are using.

What it does NOT mean

It does not mean perception is infallible. The four conditions are a filter, not a guarantee. An observation can satisfy all four and still be of a badly made instrument.

It does not mean naming is bad. The unnameable condition says only that the naming is not part of the perceiving. The classification that follows is essential; it is just a different step, with its own failure modes.

It does not mean indeterminate awareness is worthless. It is the raw material. What the sūtra denies is that it is already knowledge.

Limits

The scheme has no notion of measurement error as a quantity. A perception either satisfies the conditions or it does not; there is no confidence attached to it. Modern practice attaches a number, and that number is the main thing a classical epistemology has no slot for.

It also has no account of instrumented perception. A reading taken through a microscope is perception of what, exactly? The tradition did not need the question; a computer science student does, because every sensor is an instrument.

Quick revision

• Nyāya Sūtra 1.1.4: perception is knowledge arising from the contact of a sense with its object, and determinate, unnameable and non-erratic.
• Contact excludes inference; determinate excludes unresolved impressions; unnameable excludes knowledge got through words; non-erratic excludes systematic illusion, and the mirage is the Sūtra's own example.
• An alternative reading allows indeterminate perception, "this is something", as well as determinate, "this is a Brahmaṇa".
• Charaka's translator records the mind as a sixth sense, so what the mind acquires falls inside pratyakṣa for him.
• The scheme has no quantity of error and no account of instruments.

Test yourself

1. State Nyāya Sūtra 1.1.4 and say what each of its three epithets excludes.

Perception is knowledge arising from the contact of a sense with its object and which is determinate, unnameable and non-erratic. Determinate excludes unresolved impressions such as not knowing whether a distant plume is smoke or dust; unnameable excludes knowledge that comes by way of the thing's name; non-erratic excludes systematic illusion, such as taking a mirage for water.

2. "I know the server is overloaded because the queue is long." Which pramāṇa is this, and why not perception?

Anumāna. No sense has contacted the overload itself; the conclusion is drawn from an observed sign by way of a general connection, which fails the contact condition of 1.1.4.

3. What does Charaka's tradition add to the definition, and what does it change?

That the mind counts as a sixth sense, so what the mind acquires is included in pratyakṣa. It moves the boundary between perception and inference, so an answer should say which tradition's boundary it is using.

4. Give one thing the classical account of perception has no room for.

A quantified error or confidence. A perception either meets the four conditions or does not; there is no number attached to how reliable it is.

Effect to cause is diagnosis. You have the symptom and you want the fault. It is unreliable in a different way: several causes can produce the same effect. A swollen river may mean rain upstream, or a dam release.

Correlation is the one that looks safest and is not. Horns and tails go together in the animals you have seen. Nothing makes them go together. The connection is a summary of observation, not a mechanism, and it fails the first time you meet an animal outside the sample.

That third one is the classical statement of the standard modern warning, and it is stated in the Sūtra's own terms: the reason is erratic when there is no universal connection between it and what you concluded. [Hetvābhāsa: The Five Fallacies of the Reason] works that out.

Worked example

A student's laptop will not boot. Three inferences follow, one of each kind.

A priori. "The battery is at two per cent and the charger is not plugged in, so it is going to shut down." Cause to effect. Blockable: someone may plug it in.

A posteriori. "It powers on, the fan spins, and nothing appears on the screen, so the display or its cable has failed." Effect to cause. Several causes fit, so the inference narrows rather than settles.

Commonly seen. "Every laptop of this model I have seen with this fault had a failed cable, so this one has a failed cable." Correlation. It carries no mechanism and no guarantee that the sample was representative.

The three conclusions are not equally good, and knowing which kind you are making is how you know how much weight to put on it.

What it does NOT mean

It does not mean inference is second class. It is a pramāṇa in its own right, on every school's list including the shortest ones after the Cārvākas'.

It does not mean an inference is a guess. An inference whose general connection is sound is knowledge. The classical machinery exists precisely to check the connection, which is what [Anumāna: Vyāpti, and the Three Kinds of Inference] is about.

It does not mean "preceded by perception" makes it about the past. The perception that precedes it may be of the sign now; what is prior is the observation of the connection.

Where Module II takes this

Everything else about inference is there, and none of it is repeated here.

• The structure of an inference in five stated members, in [The Five-Member Syllogism].
• The invariable connection itself, vyāpti, and the vocabulary of subject, mark, positive and negative instance, in [Anumāna: Vyāpti, and the Three Kinds of Inference].
• The five ways the reason can be bad, in [Hetvābhāsa: The Five Fallacies of the Reason].
• Writing the whole thing in logical notation, in [The Five Members Written in Logical Notation].

Quick revision

• Nyāya Sūtra 1.1.5: inference is knowledge preceded by perception, of three kinds: a priori, a posteriori, commonly seen.
• Ingredients: a subject, a mark observed in it, and a previously established general connection.
• A priori is cause to effect, prediction; a posteriori is effect to cause, diagnosis; commonly seen is correlation.
• Vātsyāyana reads the third kind as "not commonly seen", reaching what can never be perceived, which is the opposite of a correlation.
• Correlation is the kind that looks safest and is weakest, because it carries no mechanism.

Test yourself

1. Define anumāna and give its three kinds with one example each.

Knowledge preceded by perception, drawn from an observed mark by way of a general connection. A priori: clouds, so rain. A posteriori: a swollen river, so there was rain. Commonly seen: a horned beast, so it has a tail.

2. Why does the definition insist that inference is "preceded by perception"?

Because two prior observations are needed: the mark must have been perceived now, and the general connection between mark and conclusion must have been observed earlier.

3. Which of the three kinds is a correlation, and what is its characteristic weakness?

"Commonly seen." It summarises past observation without supplying a mechanism, so it fails as soon as a case outside the sample appears.

4. What does Vātsyāyana do to the third kind, and why does it matter which reading you use?

He reads it as "not commonly seen", inference to something never perceptible at all, such as the soul from its qualities. It matters because on one reading the third kind is the weakest form of inference and on the other it is the boldest.

The Sūtra's own worked example

Suppose a young man coming to the side of a river cannot ascertain whether the river is fordable or not, and immediately an old experienced man of the locality, who has no enmity against him, comes and tells him that the river is easily fordable: the word of the old man is to be accepted as a means of right knowledge called verbal testimony.

Every element of the policy is in that sentence. The young man cannot perceive the riverbed and has no general connection to infer from, so the other two channels are closed. The old man is local, which is the scope of his expertise; experienced, which is its depth; and has no enmity, which is the absence of a motive to mislead.

The two kinds, and what they cost to check

The distinction is the useful one. A claim of the first kind puts its source at risk, because it can be falsified. A claim of the second kind does not, so it rests entirely on the source's standing. Any answer on āgama should make that point, because it is where the channel is weakest.

Worked example: the same policy in software

A team decides which sources its incident response may rely on.

Admitted, matter that is seen. The database vendor's documented maximum connection limit. The vendor is expert in that matter, states it as instruction, and has no interest in the team being wrong. The claim is verifiable, so the source is at risk if it is untrue.

Admitted with care, matter not seen. A retired colleague's account of why a design decision was taken five years ago. Expert, candid, no enmity, but nothing can now verify it. It is usable and it is not checkable, and the team should record which it is.

Not admitted, scope. The same vendor's opinion about which cloud provider is cheapest. Expertise does not extend there.

Not admitted, motive. A benchmark published by a product's own vendor comparing it with a competitor. The enmity condition is failed in its mirror image: an interest in your believing something.

That last case is worth dwelling on. The classical condition is stated as absence of enmity toward the hearer, which is narrower than absence of interest. A modern policy has to widen it, and saying so is a fair criticism of the classical rule rather than a defect in your answer.

What it does NOT mean

It does not mean tradition is self-certifying. The warrant is expertise and candour in a named matter, and the gloss deliberately refuses to make identity or standing part of the test.

It does not mean testimony outranks observation. Charaka's ordering puts instruction first in sequence, not first in authority.

It does not mean unverifiable testimony is worthless. Vidyabhusana says the second kind can somehow be reached by inference. It means that such a claim rests on the source alone, and you should know when you are in that position.

Limits

Three, and all three matter for the Module II chapters on expert systems.

No degrees. A source is reliable or it is not. There is no weighting, and no procedure for combining two sources that disagree.

No account of chains. Almost all real testimony is a chain: A told B who wrote it down and C read it. Every link can fail and the classical scheme addresses only the first.

Interest is under-specified. Absence of enmity is not absence of incentive, and the difference is most of modern source criticism.

Quick revision

• Āgama or śabda: the instructive assertion of a reliable person, Nyāya Sūtra 1.1.7.
• A reliable person is an expert in the matter, willing to communicate their own experience, and, from the river example, without enmity toward the hearer. Identity is expressly not a condition: ṛṣi, Ārya or mleccha alike.
• Two kinds, 1.1.8: matter seen, which is verifiable, and matter not seen, which is not.
• The river ford is the Sūtra's own worked example and contains the whole policy.
• Weaknesses: no degrees of trust, no account of chains of transmission, and absence of enmity is narrower than absence of interest.

Test yourself

1. State the definition of āgama and the three conditions on a reliable person.

The instructive assertion of a reliable person. The person must be an expert in the matter concerned, must be willing to communicate their own experience of it, and, on the Sūtra's own example, must have no enmity against the hearer.

2. Which condition does the classical gloss expressly refuse to impose, and why is that notable?

Identity or social standing: the reliable person may be a ṛṣi, an Ārya or a mleccha. It is notable because it makes the test turn on expertise and candour alone, which is the correct rule.

3. Distinguish the two kinds of testimony and say which is the weaker warrant.

Testimony about matter that is seen can be verified, so a false source is exposed. Testimony about matter that is not seen cannot, so it rests entirely on the source's standing, and is the weaker warrant.

4. Give one way in which a modern trust policy has to go beyond the classical conditions.

It must exclude sources with an interest in the hearer believing a particular thing, not merely sources hostile to the hearer. A vendor's own comparative benchmark passes the enmity test and fails the interest test.

That is exactly why a compiler checks that a file parses before it checks types, and checks types before it warns about unreachable code. Each stage assumes the previous one passed.

Worked example: one claim through all three stages

The claim. A student says: this sorting function is correct, because I ran it on my own test file and the output was sorted.

Stage one, admissibility. The premise is an observation of one run. That is pratyakṣa, and it is admissible. Nothing is rejected here.

Stage two, form. Reconstruct the five members and the gap appears.

• Proposition: this function is correct.
• Reason: because it sorted my test file.
• Example: whatever sorts a file is correct, as ... and here the student has nothing to put. There is no general connection between sorting one file and being correct.
• Application: cannot be stated.
• Conclusion: cannot be drawn.

The argument fails at the third member, and it fails visibly, which is the whole value of the form. A vague objection ("that is not enough testing") becomes a precise one: the example member cannot be supplied.

Stage three, defects. Even if a general connection were offered, it would be erratic in the Sūtra's sense, because the same reason supports the opposite conclusion: an incorrect function can also sort one particular file. Nyāya Sūtra 1.2.5 defines the erratic reason as one that leads to more conclusions than one, and the Sūtra's own illustration has exactly this shape.

Charaka's validation rule, which is different and complementary

The Nyāya machinery validates an argument. Charaka validates an investigation, and his rule is one sentence:

Truly, by only one of these means of knowledge, knowledge does not arise of everything that should be known.

That is a rule about coverage rather than about form. An investigation that used only one channel is incomplete even if every step in it is faultless. A modern reviewer applies both rules and would recognise the second as asking whether the evidence is sufficient, not merely whether the reasoning is valid.

What structured reasoning does NOT give you

It does not give you truth. An argument can pass all three stages and be false, because a general connection believed on good evidence can still be wrong. The apparatus improves the odds and does not settle the matter.

It does not give you discovery. Nothing in it tells you what to claim. It assesses claims that are already made, which is why the five extra members some schools add, beginning with jijñāsā, the inquiry, are attempts to bolt a discovery stage onto the front.

It does not remove judgement. Deciding whether a general connection really holds is itself a judgement, and the tradition knows it: the whole debate literature exists to argue about exactly that.

Limits

The scheme is binary at every stage. Evidence is admissible or not, form is complete or not, a defect is present or not. There is no slot for a weak but real argument, and no way to aggregate three weak arguments into a strong one. Modern practice does that constantly, and the classical apparatus has no notation for it.

It is also adversarial by design. It assumes an opponent whose job is to find the defect. That is a strength when there is one and a weakness when there is not, because nothing in the machinery checks itself.

Quick revision

• Structured reasoning: named steps, so that a bad argument can be shown bad by a third party who was not present.
• Three stages in order: admissibility of evidence, completeness of form, absence of the named defects.
• The stages correspond to input validation, a required template, and a static analyser, and the order is forced for the same reason a compiler parses before it type-checks.
• Charaka adds a coverage rule: one channel of evidence is never enough.
• Limits: everything is binary, nothing aggregates weak arguments, and the whole apparatus needs an opponent to run it.

Test yourself

1. Name the three stages of validation and what each one catches.

Admissibility, which catches an appeal to something not accepted as evidence; form, which catches an assertion presented as an argument; and defects of the reason, which catch an argument that is well formed and still worthless.

2. Why is the order of the stages not arbitrary?

Each stage assumes the previous one passed. Examining the quality of a reason that rests on inadmissible evidence, or looking for defects in something not stated as an argument, is wasted work. A compiler parses before type-checking for the same reason.

3. Reconstruct "it works on my test file, so it is correct" in the five members and say where it fails.

Proposition: the function is correct. Reason: it sorted my test file. The example member cannot be supplied, because there is no general connection between sorting one file and being correct, so application and conclusion cannot follow. It fails at the third member.

4. Give one thing the classical validation scheme cannot express.

Degree. Every stage is pass or fail, so there is no way to record a weak but genuine argument, and no way to combine several weak arguments into a stronger case.

Cheap: defaults and inheritance, so rama need not repeat may borrow. Expensive: exceptions, which have to be handled by overriding a slot and then explaining why.

Rules. IF conditions THEN conclusion, with an engine that applies them.

Cheap: adding a new piece of knowledge without touching the rest. Expensive: understanding what the system will do overall, because the behaviour is spread across the rules.

The comparison a five-mark answer needs

Worked example: the same fact, and the question that separates the notations

The fact: most students return books on time.

In logic, this cannot be said at all without extending the notation. for all X: student(X) implies returnsOnTime(X) is false, and there is no standard way in plain first-order logic to say "most".

In a semantic network, you can draw an edge labelled "usually returns on time", and now the notation's semantics have quietly become whatever the reader thinks that label means.

In a frame, it is natural: the student frame gets a slot returns with default on time, and an individual frame may override it.

As a rule, it is natural in a different way: a rule concluding returnsOnTime(X) from student(X), plus a second rule that retracts it for a named individual.

The lesson is not that frames and rules are better. It is that the fact was easy to state in two notations and not statable in a third, and you cannot know that until you try. Pick the notation after you know the questions, not before.

What knowledge representation is NOT

It is not a database schema. A schema fixes syntax and, loosely, semantics. It has no inference procedure, so nothing is derived that was not stored.

It is not the same as storing text. A page of prose contains knowledge and supports no inference at all. Turning prose into a representation is the work, and it is the work every chapter of this paper's Module II asks you to do on a classical text.

It is not free of commitments. Every notation says something about what exists. Choosing one is choosing an ontology whether or not you notice.

The classical connection, stated carefully

The claim MU's syllabus makes is that śāstra method is knowledge representation, and the honest version of that claim is specific.

What matches. A śāstra fixes its syntax, its semantics and its inference, which are three of the four requirements above, and Vaiśeṣika's padārtha scheme is an explicit ontological commitment, which is the fourth.

What does not. None of it is machine readable, and none of it was meant to be. The inference procedure is a trained reader. So the correspondence is at the level of design, not of implementation, and an answer that says so is stronger than one that does not.

Quick revision

• Knowledge representation: encoding what is known so that new facts can be derived.
• Four requirements: syntax, semantics, inference procedure, ontological commitment.
• Four families: logic, semantic networks, frames, rules, each cheap at some questions and expensive at others.
• A representation is a bet about which questions will be asked.
• The classical correspondence is at the level of design: a śāstra fixes all four, but its inference procedure is a person.

Test yourself

1. Name the four things a knowledge representation must fix, and say what goes wrong if the second is missing.

Syntax, semantics, an inference procedure, and an ontological commitment. Without semantics, two readers can take the same expression two ways, so nothing derived from it can be relied on: an unlabelled arrow between two boxes is the standard example.

2. Why is a database schema not a knowledge representation?

It has no inference procedure, so it stores facts and derives none. A representation must support working out something the system was not told.

3. Take the fact "most students return books on time" and say which of the four families states it naturally and which cannot.

Frames state it as a default on a slot, and rules state it as a rule with an override. Plain first-order logic cannot state it at all, since the universal is false and there is no standard quantifier for "most". A semantic network can draw the label but loses precise semantics in doing so.

4. State the correspondence between śāstra method and knowledge representation, with its limit.

A śāstra fixes terms, rules and admissible evidence, and a scheme such as padārtha is an explicit ontology, so all four requirements are addressed. The limit is that nothing is machine readable and the inference procedure is a trained human reader, so the correspondence is one of design, not implementation.

The row that makes the comparison worth drawing is the fourth. Ordinary specifications are notoriously silent about conflicts between their own clauses, and a reader has to guess. Pāṇini wrote the conflict rule down. [Vipratiṣedha: When Two Rules Collide, the Later Wins] is that rule.

Worked example: a sūtra read as a specification

Pāṇini 7.3.84, in Vasu's translation: "when a sārvadhātuka or an ārdhadhātuka affix follows there is guṇa of the base."

As a specification.

Three features of that are worth naming. The rule does not say how to perform the substitution, only what the result is. Its second precondition is supplied by another rule, which is what a meta-rule is for. And its exception is declared elsewhere and has priority, which is a stated conflict policy.

What a formal specification is NOT

It is not an implementation. It says what, not how. A specification that fixes the algorithm has over-specified and has forbidden better implementations.

It is not a guarantee of correctness. It can be wrong about what was wanted. Formality moves the argument from "does the code do this?" to "is this what we wanted?", which is progress and not a solution.

It is not necessarily mathematical notation. A precise subset of English with defined terms can be a specification. What matters is that the terms are fixed and the conditions are complete, which is exactly what a śāstra does.

Limits of the classical comparison

Two honest limits, both of which belong in a critical answer.

A sūtra's preconditions are not all written down. Some are carried over from earlier sūtras by anuvṛtti, and which ones are in force at a given rule is decided by the commentary. A modern specification that relied on an editor to say which preconditions applied would be rejected.

Nothing checks a sūtra mechanically. There is no machine that can confirm the rules are consistent, and in fact the tradition disputes the consistency of particular rules at length. A formal specification in the modern sense is one a tool can check; a sūtra is one only a trained reader can check.

Quick revision

• A formal specification states required behaviour in a notation whose syntax and semantics are fixed, so satisfaction is checkable rather than arguable.
• It fixes three things: what must hold, under what assumptions, and what is left free. Anything not forbidden is permitted.
• "Every student has a supervisor" has three readings; a formula has one.
• The śāstra parallel is strong on definitions, conditions, conflict policy, tests and errata.
• It is weak on two counts: preconditions carried over rather than written, and no mechanical checking.

Test yourself

1. Define a formal specification and name the three things it fixes.

A description of required behaviour in a notation with fixed syntax and semantics, so that satisfaction can be proved or checked mechanically. It fixes what must hold, the assumptions under which it must hold, and what is left free.

2. Give a requirement with more than one reading and show how a formal notation removes the ambiguity.

"Every student has a supervisor" may mean each has some supervisor, or there is one supervisor for all, or each has exactly one. Writing "for all S: student(S) implies (exists T: supervises(T, S))" commits to the first and to nothing else.

3. Why is it a mistake to think a specification only constrains?

Because it also licenses: whatever it does not forbid is permitted. A sort specification that does not require stability permits an unstable implementation, and a caller who assumed stability has misread the licence.

4. Name one respect in which a sūtra falls short of a modern formal specification.

Its preconditions are not all written at the rule; some are carried over from earlier rules and which are in force is settled by the commentary. Relatedly, no tool can check a sūtra set for consistency, so the checking is done by a trained reader.

Abstraction

The habit. Throw away everything that does not bear on the question, and keep a name for what is left.

In a śāstra. A Sanskrit syllable has a sound, a meaning, a pitch and a length. Piṅgala keeps the length and throws away the rest, and reduces it to two values, light or heavy. Once a syllable is one of two things, counting metres becomes arithmetic. That single decision is what makes the whole of Module I possible.

In a program. Here is the same abstraction, run.

# A metre, abstracted to nothing but the weight of each syllable.
LINES = [
    ("a ga na tri pa da", [1, 1, 1, 1, 1, 1]),
    ("ma dhu ra ya ti", [1, 1, 1, 2, 1]),
    ("so ma pa la", [2, 1, 1, 1]),
]

for text, weights in LINES:
    pattern = "".join("G" if w == 2 else "L" for w in weights)
    print("%-22s %-8s syllables %d, heavy %d"
          % (text, pattern, len(pattern), pattern.count("G")))

a ga na tri pa da      LLLLLL   syllables 6, heavy 0
ma dhu ra ya ti        LLLGL    syllables 5, heavy 1
so ma pa la            GLLL     syllables 4, heavy 1

The words have gone. What is left is a string over two symbols, which is a thing a rule can be stated about.

The cost. An abstraction is a decision to be blind to something. Piṅgala's abstraction cannot express which syllables rhyme, because rhyme is part of what was discarded.

Algorithm design

The habit. State the steps so exactly that someone who does not understand the problem can carry them out and get the right answer.

In a śāstra. Halāyudha's own words on the prastāra rule are a procedure: write a row of all heavy syllables; then find the first heavy syllable, make it light, make what precedes it heavy, leave what follows alone; repeat until the row is all light. Nothing in that requires you to know what a metre is.

In a program. The same three sentences, in Python, in [Prastāra in Code].

The test. Give the steps to somebody outside the subject. If they need to ask you a question, the steps are a description and not an algorithm. [The Prastāra Rule Read as an Algorithm] applies that test properly, against the five standard properties.

The four habits as a table

What computational thinking is NOT

It is not programming. No machine appears in any of the four habits. A student who thinks the phrase means writing code will misread MU's objective.

It is not a claim that everything is computable. Deciding whether a general connection holds, which is the load-bearing step of every inference in Module II, is not made mechanical by any of the four.

It is not modern. This is the claim MU's syllabus is actually making, and it is the one you should be able to argue in five marks: the habits are habits of anyone who must transmit an exact procedure without being present to explain it.

Quick revision

• Four habits: decomposition, pattern recognition, abstraction, algorithm design. MU's CO 1 names computational thinking.
• Decomposition: Piṅgala solves one syllable plus a growth rule. Test: can you check one part alone?
• Pattern recognition: metres by weight are combinations. Trap: a pattern is a hypothesis.
• Abstraction: a syllable becomes one of two symbols, and that one decision makes Module I arithmetic. Cost: blindness to what was discarded.
• Algorithm design: steps a person outside the subject can follow. Test: do they have to ask a question?

Test yourself

1. Name the four habits and give Piṅgala's instance of abstraction.

Decomposition, pattern recognition, abstraction, algorithm design. Abstraction: a syllable's sound, meaning and pitch are discarded and only its weight is kept, reduced to two values, so that a metre becomes a string over two symbols.

2. What is the test of whether you have really decomposed a problem?

Whether one part can be checked without running the others. If it cannot, the text has been divided but the problem has not.

3. Give the cost of abstraction, with an example from this paper.

You become blind to what you discarded. Piṅgala's scheme cannot say anything about rhyme or meaning, because both were thrown away when the syllable was reduced to its weight.

4. Why is it wrong to read MU's "computational thinking" as meaning programming?

Because none of the four habits mentions a machine. They are habits of stating a problem and a procedure exactly, which is why a tradition transmitting a discipline through memory develops them without any computer at all.

Editions of the eighth chapter do not number it alike. The same sūtra, "rūpe śūnyam", is numbered 26 in one of this book's witnesses and 28 in another. There is no error in either: the chapter's sūtra divisions are themselves an editorial judgement, and different editors divide differently.

Worked. So this book prints a number only where two of its three witnesses agree. Where they do, the number is given with the edition named. Where they do not, the sūtra is named by its opening words and its place in the sequence, and the disagreement is stated.

The numbers that are secure, agreeing across witnesses in the Asiatic Society edition's numbering, are these, and they are the ones this book uses.

The saṅkhyā group, which computes the number of patterns without listing them, follows immediately after 8.27 in the same chapter. Its numbering is where the witnesses diverge, so [Saṅkhyā: Counting the Rows Without Writing Them] names those sūtras by their opening words.

The six pratyayas, and what Halāyudha says about the sixth

A pratyaya is an operation on the set of metrical patterns. Halāyudha treats them as a group and closes the chapter by saying the group is complete.

1. Prastāra, laying out every pattern in order.
2. Naṣṭa, recovering a pattern that has been lost, from its row number.
3. Uddiṣṭa, finding the row number of a pattern pointed at.
4. Lagakriyā, how many patterns have a given number of light syllables.
5. Saṅkhyā, how many patterns there are altogether.
6. Adhvayoga, how much space the written table takes.

On the sixth he records, in effect, that some count it and that it is omitted here because it is very slight. [Lagakriyā and Adhvayoga: The Rest of the Pratyayas] gives both, because a question may name one MU's own labels do not.

What this book claims about the text, and what it does not

Claimed. The eighth chapter states the operations listed above; Halāyudha works them; the arithmetic they describe is exactly the arithmetic this book prints, because every one of them has been implemented and run.

Not claimed. That Piṅgala had the idea of a number base. That he wrote the operations as a mathematician would. That anything in the text is a program. The operations are algorithms and there is no machine, and the distinction is kept throughout.

Not claimed, and worth saying twice. That this book's readings settle disputed questions in Sanskrit prosody. Where the tradition disagrees, the disagreement is reported.

Quick revision

• The Chandaḥśāstra, attributed to Piṅgala, is a sūtra text on Sanskrit metre in eight chapters. Chapter 8 carries the pratyayas.
• The commentary quoted is Halāyudha's Mṛtasañjīvanī, named in the chapter's own colophon. The sūtra gives the rule; the commentary gives the procedure.
• The edition quoted is the Bibliotheca Indica text, ed. Visvanātha Śāstrī, Asiatic Society of Bengal, Calcutta, 1874.
• Editions number chapter 8 differently: "rūpe śūnyam" is 26 in one witness and 28 in another. Numbers are printed only where witnesses agree.
• Six pratyayas: prastāra, naṣṭa, uddiṣṭa, lagakriyā, saṅkhyā, adhvayoga. Halāyudha says the sixth is usually omitted as slight.

Test yourself

1. What is the Chandaḥśāstra about, and why does a computer science paper use its eighth chapter?

It is a treatise on Sanskrit metre. Its eighth chapter reduces metre to strings over two symbols and states operations on the whole set of such strings, so the questions it answers are combinatorial and algorithmic.

2. Name the commentary this book quotes and say why a commentary is needed at all.

Halāyudha's Mṛtasañjīvanī. A sūtra of two or three words states a rule in outline and omits the procedure, so the procedure has to be read from the commentary.

3. Why does this book sometimes name a sūtra by its opening words instead of by a number?

Because editions divide the eighth chapter differently and so number it differently. "Rūpe śūnyam" is numbered 26 in one witness and 28 in another, so a bare number would be a claim the sources do not support.

4. List the six pratyayas and say which one Halāyudha treats as optional.

Prastāra, naṣṭa, uddiṣṭa, lagakriyā, saṅkhyā, adhvayoga. He records that some count the sixth, adhvayoga, and that it is left out as very slight.

Worked example: three lines scanned

The lines below are transliterated syllable by syllable and marked. What is being demonstrated is only the procedure, and nothing turns on the choice of lines.

Two things to notice. Two lines of different syllable counts can have the same total duration, which is why the tradition has a second family of metres counted by mātrā rather than by syllable. And the pattern column is a string over two symbols, which is the only thing the rest of Module I will use.

The seven metre classes

The tradition names classes of metre by the number of syllables in a line. Halāyudha's own commentary on the saṅkhyā rule runs through seven of them, and this book quotes his figures in [Saṅkhyā: Counting the Rows Without Writing Them].

Every figure in the third column is a power of two, and every one of them is stated in the commentary rather than calculated by this book. That is a fact worth pausing on: a prosodist writing on metre has produced, in the course of his subject, a table of powers of two from 64 to 4096.

What a metre is, formally

Putting the vocabulary together gives a definition a computer science student can work with.

A metre of n syllables is a string of length n over the alphabet {L, G}. The set of all such strings is what the next several chapters enumerate, index and count. Nothing about Sanskrit is needed after this point, which is the payoff of the abstraction.

What this does NOT mean

It does not mean every string is a real metre. Most of the 4096 twelve-syllable patterns have no name and were never used. The tradition's interest is in which ones are named; Piṅgala's chapter eight is about the whole space anyway, and that is precisely why it becomes mathematics.

It does not mean quantity is the whole of Sanskrit prosody. There are metres counted by total mātrā rather than by syllable count, and there are rules about pauses. Neither is on this syllabus.

It does not mean the scansion is mechanical in every case. There are conventional licences, and editors disagree about particular lines. None of that affects the combinatorics.

Quick revision

• Sanskrit metre is quantitative: it counts duration, not stress.
• Laghu, light, L: a short vowel, not closed. Guru, heavy, G: long vowel, diphthong, or short vowel closed by a consonant. One mātrā against two.
• A syllable's weight can depend on what follows it, so a metre is a sequence and not a bag.
• A pāda is a line; four pādas make a stanza; a vṛtta is a metre defined by syllable count.
• Seven classes from gāyatrī at 6 syllables to jagatī at 12, with 64 to 4096 patterns, all powers of two, all stated in Halāyudha's commentary.
• Formally: a metre of n syllables is a string of length n over {L, G}.

Test yourself

1. Define laghu and guru, and give the rule that makes a short vowel heavy.

Laghu is a light syllable, one mātrā: a short vowel not closed by a consonant. Guru is heavy, two mātrās: a long vowel, a diphthong, or a short vowel closed by a consonant. The closing consonant is what makes a short vowel heavy.

2. Why does the weight of a syllable sometimes depend on the next syllable?

Because a consonant that closes the syllable adds duration, and whether a syllable is closed depends on what follows it. So scansion is done over the line, not syllable by syllable in isolation.

3. Why is quantitative metre easier to formalise than stress metre?

Because weight is decidable by a stated rule, while stress is a matter of degree and of dialect. A property decidable by rule can be encoded as a symbol, and symbols can be counted.

4. Give the formal definition of a metre of n syllables, and say how many there are for the anuṣṭubh.

A string of length n over the alphabet of two symbols, light and heavy. The anuṣṭubh has eight syllables, so there are 256 patterns, which is the figure Halāyudha's commentary itself gives.

pattern  value  back
GGG          0  0
LGG          1  1
GLG          2  2
LLG          3  3
GGL          4  4
LGL          5  5
GLL          6  6
LLL          7  7

distinct patterns of 3 syllables: 8
bits carried by a 3 syllable line: 3

The mapping is a bijection: every pattern has one value, every value has one pattern, and the eight patterns are the eight numbers.

What "n bits" buys you

This is the part that makes the abstraction useful rather than decorative.

Counting becomes arithmetic. You do not have to write the table to know how big it is. [Saṅkhyā: Counting the Rows Without Writing Them] is exactly this.

Addressing becomes arithmetic. You do not have to write the table to find its fiftieth row. [Naṣṭa: From a Row Number Back to the Pattern] is exactly this, and it is the most striking of Piṅgala's rules for a computing student, because it is random access into a structure that was never built.

Sub-counting becomes combinatorics. How many of the patterns have exactly three light syllables is a question about bit counts, and it has a closed-form answer. [Meru-Prastāra: Halāyudha's Staircase] is that answer.

What it does NOT license

Four overclaims are made about Piṅgala regularly, and all four should be refused in an answer that is asked to assess critically.

"Piṅgala invented binary." No. He set up a two-valued encoding and stated operations on it. There is no statement in the text of a positional number system with base two, no arithmetic on such numbers, and no notion of a base at all.

"Piṅgala invented the bit." No. A bit is a measure of information, defined in the twentieth century. What is true is that his encoding carries one bit per syllable, which is a fact about his encoding and not a claim about his intent.

"The prastāra is a binary counter." Almost. Its order is the order of binary counting, and that is proved later. It is not described as counting, and it is not used to do arithmetic.

"This makes the Chandaḥśāstra a work of computer science." No. It makes the Chandaḥśāstra a work in which several problems of a kind computer science later made central are posed and solved, which is a more interesting claim because it is true.

The honest summary

What Piṅgala did is more specific and more impressive than the overclaims. He chose an encoding in which the questions of his subject became decidable by arithmetic, and then stated the arithmetic. Choosing a representation so that the problems become tractable is the whole of what [Knowledge Representation: The Modern Name For It] is about, and it is the highest praise available.

Quick revision

• A bit is a choice between two alternatives. A syllable, abstracted, is such a choice.
• A line of n syllables carries n bits, so there are 2 to the power n lines.
• With laghu as one, guru as zero, and the leftmost syllable as the units place, patterns and numbers correspond one to one.
• Both of those choices are conventions; what the text fixes is the ORDER of the table.
• What follows: counting, addressing and sub-counting all become arithmetic.
• What is not licensed: that Piṅgala invented binary, the bit, or a counter. What is true: he chose an encoding that made his questions arithmetical.

Test yourself

1. Show in four steps why a metre of n syllables has 2 to the power n forms.

A syllable has two possible values; a choice between two is one bit; a line of n syllables is n independent choices, so n bits; n independent binary choices give 2 multiplied by itself n times distinct results.

2. Which two choices in the standard mapping are conventions rather than facts about the text?

Assigning one to laghu rather than to guru, and treating the leftmost syllable as the units place. The text fixes the order of the table, not the arithmetic reading of it.

3. What is unusual about the position of the units place in Piṅgala's order, and does it matter?

The fastest-changing symbol is on the left, the opposite of ordinary numeral notation. It is a difference in presentation only: the order is still the order of counting.

4. A classmate says Piṅgala invented binary numbers. Correct them in two sentences.

He set up a two-valued encoding of syllables and stated operations that enumerate, index and count the resulting patterns. He nowhere states a positional number system with base two, performs arithmetic on such numbers, or uses the notion of a base at all.

1. Write a first row of n heavy syllables.
2. Look along the current row from the left and find the first heavy syllable.
3. If there is none, stop: the table is complete.
4. Otherwise make that syllable light, make every syllable to its left heavy, and leave every syllable to its right exactly as it is.
5. Write the result as the next row and go back to step 2.

Step 4 is the whole rule and it has three clauses. Students who get the table wrong have almost always dropped the middle clause, which resets the left-hand part.

The three-syllable table

This is the program's own output, from the file printed in [Prastāra in Code].

Worked. Trace the rule once to see it working. Row 4 is L L G. The first heavy syllable is the third. Make it light, make the first two heavy, leave nothing to the right: G G L, which is row 5. That is the step where the reset matters, and where a careless reader would write L L L.

The same table the other way: Halāyudha's recursion

The rule above walks the table one row at a time. Sūtra 8.22 as Halāyudha explains it gives a second construction, and it is the one a programmer will find natural.

To build the table for n syllables: write the table for n minus 1 syllables twice, one copy under the other; then in the new syllable's column, put heavy against every row of the first copy and light against every row of the second.

Check it for n equal to 2. The one-syllable table is G, L. Write it twice: G, L, G, L. Fill the second column with G, G then L, L. The result is GG, LG, GL, LL, which is the four rows the commentary says the two-syllable prastāra has.

The new syllable goes on the right. This is the one detail that is easy to get backwards, and getting it backwards produces a table of the right size in the wrong order. The program in [Prastāra in Code] builds the table both ways and asserts they are identical, which is how that mistake was caught.

Why the two constructions agree

They agree because the rule in step 4 changes the rightmost part of the row least often. The first syllable alternates every row; the second changes every two rows; the k-th changes every 2 to the power k minus 1 rows. So the table splits exactly in half on the last syllable, which is what the recursive construction assumes.

That observation is also the whole content of [Binary Number Systems, and Exactly Where Piṅgala's Order Agrees], stated ahead of time.

What the prastāra is NOT

It is not a list of metres in use. Most of its rows are patterns no poet ever wrote. Its subject is the whole space, which is exactly why it becomes mathematics.

It is not a table that has to be stored. The rule is the table. A scribe with the rule and a row can produce the next row, and the retrieval rules can produce any row from its number.

It is not the only possible order. Other orders exist and one of them, the reverse, appears in later prosodic literature. Piṅgala's is the one his retrieval rules are built for, and mixing two orders is the commonest way to get a naṣṭa answer wrong.

Quick revision

• Prastāra: every pattern of n syllables, in one fixed order, from all-heavy to all-light, 2 to the power n rows, no repeats.
• 8.20 dvikau glau gives the one-syllable table; 8.21 miśrau ca the two-syllable; 8.22 pṛthaglā miśrāḥ generalises by repetition; 8.23 vasavas trikāḥ states eight for three syllables.
• The rule: find the first heavy syllable from the left, make it light, make everything to its left heavy, leave everything to its right alone.
• The recursion: write the shorter table twice, and fill the new column, which is on the RIGHT, with heavy against the first copy and light against the second.
• The commentary's own figures: 8, 16, 32, 64 for three to six syllables.

Test yourself

1. State the prastāra rule in your own words and apply it to L L G.

Find the first heavy syllable from the left, make it light, make everything to its left heavy, and leave everything to its right unchanged. In L L G the first heavy syllable is the third, so it becomes light and the first two are reset to heavy, giving G G L.

2. Which clause of the rule do students drop, and what goes wrong?

The clause that resets everything to the left of the changed syllable to heavy. Dropping it turns L L G into L L L instead of G G L, and the table then repeats rows and misses others.

3. Give Halāyudha's recursive construction and say where the new syllable goes.

Write the table for one fewer syllable twice, one copy beneath the other, then fill the new column with heavy against the first copy and light against the second. The new column is at the right-hand end of the row.

4. Why is an order more useful than a list?

Because it is reproducible, so a row number names one thing; it is addressable, so a row can be asked for by number; and it lets the table be generated from a rule instead of stored.

Read each row as a number with light counting one and heavy counting zero, the leftmost syllable being the units place. Then one step of the rule does this: the first heavy syllable, at position k, becomes light, adding 2 to the power k minus 1; and every light syllable to its left becomes heavy, subtracting 1 plus 2 plus 4 and so on up to 2 to the power k minus 2, which totals 2 to the power k minus 1 minus 1.

So the net change is exactly plus one. Each step increases the row's value by one, the value starts at 0 and can never exceed 2 to the power n minus 1, so the rule stops after exactly 2 to the power n minus 1 steps.

Verdict: satisfied, and provably. Notice what this argument gives you beyond termination: it gives the exact number of steps, and it is the reason the order is the order of counting.

Effectiveness

The property. Every step is basic enough to be carried out exactly, in finite time, with the means available.

The rule. The operations are: scan a row left to right; overwrite one symbol; overwrite a prefix. A scribe with a palm leaf can do all three. No step requires arithmetic, and none requires knowing anything about metre.

Verdict: satisfied. And worth noticing: the rule is effective for a human executor with no mathematics, which is exactly what it was designed for.

Output

The property. It produces the intended result.

The rule. It produces every pattern of n syllables, once each, in a fixed order. That is a claim about correctness and it is not obvious from the rule.

The finiteness argument above supplies the proof. If each step adds exactly one to the row's value, and the first row is 0, then the rows take the values 0, 1, 2 and so on up to 2 to the power n minus 1, each exactly once. Since the mapping between patterns and values is one to one, every pattern appears exactly once.

Verdict: satisfied, and proved by the same argument as finiteness. The program in [Prastāra in Code] also checks it by brute force up to fourteen syllables, which is a different kind of assurance.

The five properties as a table

What this does NOT establish

It does not make the Chandaḥśāstra a program. An algorithm is a procedure; a program is an algorithm expressed for a machine. There is no machine, and saying so is part of the answer.

It does not mean Piṅgala thought in these terms. The five properties are a modern test. What has been shown is that his rule passes it, which is a fact about the rule.

It does not mean every rule in the text passes. [Lagakriyā and Adhvayoga: The Rest of the Pratyayas] discusses one that is stated so briefly that its definiteness depends on the commentary, and the honest verdict there is different.

Limits

One limit is worth naming because it recurs. The rule has no stated complexity. Nothing in the text says how long producing the table takes, or notices that it takes time proportional to n times 2 to the power n. The saṅkhyā rule shows that Piṅgala cared about avoiding work, so the absence is interesting rather than damning, but it is an absence. [Algorithmic Generation: What Piṅgala Actually Achieved] gives the costs.

Quick revision

• The five properties: input, definiteness, finiteness, effectiveness, output.
• Definiteness is the classical rule's strongest property: no step requires a choice.
• Finiteness is proved, not observed: each step raises the row's value by exactly one, so the rule halts after 2 to the power n minus 1 steps.
• The same argument proves correctness: the rows take every value from 0 upward exactly once.
• Effectiveness: scan, overwrite one symbol, overwrite a prefix. A scribe can do all three with no arithmetic.
• What is missing from the text: any statement of cost.

Test yourself

1. Name the five properties of an algorithm.

Input, definiteness, finiteness, effectiveness, output.

2. Prove that the prastāra rule terminates, and say how many steps it takes.

Read a row as a number with light as one and the leftmost syllable as the units place. One step turns the first heavy syllable light, adding 2 to the power k minus 1, and resets the lighter syllables to its left, subtracting 2 to the power k minus 1 minus 1. The net change is plus one. Starting from 0 and bounded by 2 to the power n minus 1, the rule halts after exactly 2 to the power n minus 1 steps.

3. How does the same argument prove the table is complete and has no repeats?

Because the rows take the values 0, 1, 2 and so on consecutively, and patterns correspond one to one with values, every pattern appears exactly once.

4. Which property is a rule like "begin at a convenient point" failing, and why does it matter?

Definiteness. A reader has to make a choice, so two readers can produce different results, and the procedure is a description rather than an algorithm.

 1  G G G
 2  L G G
 3  G L G
 4  L L G
 5  G G L
 6  L G L
 7  G L L
 8  L L L

Line by line, because a viva will ask. row.index(GURU) is step two of the rule, finding the first heavy syllable from the left. The three pieces of the next line are the three clauses of step four. The while condition is step three, and it is checked before each pass, which is why an all-light row ends the table instead of being processed.

Test cases

Heading six. She asks for a minimum of ten. Here they are as two groups: five that check the size of the output, and five that check its shape over every n from one to twelve.

GURU, LAGHU = "G", "L"

def prastara(n):
    row = [GURU] * n
    rows = ["".join(row)]
    while GURU in row:
        k = row.index(GURU)
        row = [GURU] * k + [LAGHU] + row[k + 1:]
        rows.append("".join(row))
    return rows

def prastara_recursive(n):
    """Halayudha on 8.22: the shorter table twice, new column on the right."""
    if n == 1:
        return [GURU, LAGHU]
    prev = prastara_recursive(n - 1)
    return [r + GURU for r in prev] + [r + LAGHU for r in prev]

TESTS = [
    ("one syllable gives two rows",        1, 2),
    ("two syllables give four rows",       2, 4),
    ("three syllables give eight rows",    3, 8),
    ("the gayatri gives sixty four rows",  6, 64),
    ("the jagati gives 4096 rows",        12, 4096),
]

print("%-40s %-8s %-8s %s" % ("test", "rows", "expected", "result"))
for name, n, expected in TESTS:
    rows = prastara(n)
    ok = len(rows) == expected
    print("%-40s %-8d %-8d %s" % (name, len(rows), expected, "pass" if ok else "FAIL"))

print()
CHECKS = [
    ("the first row is all guru",          lambda n: prastara(n)[0] == "G" * n),
    ("the last row is all laghu",          lambda n: prastara(n)[-1] == "L" * n),
    ("no row repeats",                     lambda n: len(set(prastara(n))) == 2 ** n),
    ("every row has n syllables",          lambda n: all(len(r) == n for r in prastara(n))),
    ("the recursion gives the same table", lambda n: prastara(n) == prastara_recursive(n)),
]
for name, check in CHECKS:
    results = [check(n) for n in range(1, 13)]
    print("%-40s %s for n = 1 to 12" % (name, "pass" if all(results) else "FAIL"))

test                                     rows     expected result
one syllable gives two rows              2        2        pass
two syllables give four rows             4        4        pass
three syllables give eight rows          8        8        pass
the gayatri gives sixty four rows        64       64       pass
the jagati gives 4096 rows               4096     4096     pass

the first row is all guru                pass for n = 1 to 12
the last row is all laghu                pass for n = 1 to 12
no row repeats                           pass for n = 1 to 12
every row has n syllables                pass for n = 1 to 12
the recursion gives the same table       pass for n = 1 to 12

The first four expected values, 2, 4, 8 and 64, are Halāyudha's own figures from his commentary on 8.23. The test is therefore against the text and not against our own arithmetic, which is the strongest form the test can take.

The bug the last test caught

The final check compares the iterative table with the recursive one, and it is there for a reason.

The first version of prastara_recursive in this book's own program file wrote GURU + r instead of r + GURU, putting the new syllable at the left-hand end of the row. That version produced a table of exactly the right size, with no repeats, beginning all-heavy and ending all-light. Every test except the comparison passed. The order was wrong, and nothing but the comparison would have noticed.

The lesson for an internal assessment is general: a test that only checks the size of the output cannot see a wrong order. Say that in your limitations section and you have said something real.

Complexity and limitations

Heading seven.

Time. The loop runs 2 to the power n minus 1 times, and each pass copies a row of n symbols, so the work is proportional to n times 2 to the power n. There is no faster way, because the output itself is that big.

Space. As written, the whole table is held in memory: again n times 2 to the power n. For n equal to twelve that is about 49,000 symbols, which is nothing; for n equal to thirty it would be about thirty-two gigabytes. If you only need one row at a time, do not build the list, and if you need one particular row, do not build the table at all. [Naṣṭa: From a Row Number Back to the Pattern] is the alternative.

The recursive version. It builds every intermediate table, so it does about twice the work of the iterative one and uses recursion depth n. It is in the book to be compared with, not to be preferred.

Limitation. Neither version can produce row 5,000,000 of a thirty-syllable metre without producing everything before it. That is not a flaw in the code; it is a property of enumeration, and it is exactly the gap Piṅgala's retrieval rules fill.

Quick revision

• Iterative implementation: start all-heavy, find the first heavy from the left, make it light, reset its left, keep its right, until all-light.
• Recursive implementation, from 8.22: the shorter table twice, the new column appended on the RIGHT.
• Time and space are both proportional to n times 2 to the power n; that is the size of the output, so it cannot be beaten.
• MU's five submission headings used here: problem statement, conceptual mapping, pseudo-code, working code, test cases.
• A test that checks only the size of the output cannot detect a wrong order. Compare two independent constructions.

Test yourself

1. Write the prastāra rule as pseudo-code in five lines.

Set row to n copies of guru and start the list with it. While the row contains a guru: let k be the position of the first guru; replace the row by k minus one gurus, then a laghu, then the rest of the row unchanged; append it. Return the list.

2. Give the time complexity and say why it cannot be improved.

Proportional to n times 2 to the power n, because there are 2 to the power n rows of n symbols each. No algorithm that prints the whole table can do less work than the size of the table.

3. A classmate's prastāra function returns the right number of rows, all distinct, starting all-heavy and ending all-light, but the order is wrong. Which test would catch it?

A comparison against an independently written implementation, such as the recursive construction from 8.22. Size, distinctness and endpoint tests all pass on a wrongly ordered table.

4. Why is it wrong to use this program to answer "what is row 3000 of the twelve-syllable metre?"

Because it must generate the 2999 rows before it. The retrieval rule naṣṭa computes that row directly from its number, in work proportional to the number of syllables.

n      rows   row number equals binary value   first mismatch
1      2      yes                              none
2      4      yes                              none
3      8      yes                              none
4      16     yes                              none
5      32     yes                              none
6      64     yes                              none
7      128    yes                              none
8      256    yes                              none
9      512    yes                              none
10     1024   yes                              none
11     2048   yes                              none
12     4096   yes                              none
13     8192   yes                              none
14     16384  yes                              none

the ordinary binary numerals of 3 bits, for comparison
0  000   reversed 000
1  001   reversed 100
2  010   reversed 010
3  011   reversed 110
4  100   reversed 001
5  101   reversed 101
6  110   reversed 011
7  111   reversed 111

Fourteen syllable counts, 32,766 rows in total, and no mismatch anywhere.

Where the agreement comes from

The proof is the one already given in [The Prastāra Rule Read as an Algorithm], and it is worth restating in the language of this chapter because in that language it is a single observation.

The prastāra rule finds the first guru from the left, makes it laghu, and resets the laghus to its left to guru. Under the reading above, that is: find the first 0, make it 1, and make all the 1s below it 0.

That is exactly the rule for adding one to a binary number, written for a number whose low-order digit is on the left. Since the first row is all guru, which is zero, the rows are 0, 1, 2 and so on.

Where it differs: the direction

Only one thing differs, and it is a matter of writing rather than of arithmetic.

Look at the last two rows of the output table above. The numeral for four is 100 and Piṅgala's pattern for four is GGL, which is 001 in digits. They are reverses of each other, and that is the whole difference.

Is the difference significant? For counting, no. The order of the rows is identical; only the direction the symbols are written in differs, which is a convention about layout. For arithmetic, it would matter, because addition algorithms are written for one direction. But Piṅgala never adds two patterns, so the question never arises in the text.

Worked example: row 41 of the gāyatrī

The gāyatrī has six syllables and 64 rows. Find row 41.

As arithmetic. Rows are numbered from one in the tradition, so row 41 has value 40. In base two, 40 is 32 plus 8, so the sixth and fourth places hold 1: reading the leftmost syllable as the units place, positions 4 and 6 are laghu.

As a pattern. G G G L G L.

Checked by the rule. [Naṣṭa: From a Row Number Back to the Pattern] does exactly this with Piṅgala's own halving rule and gets the same answer, and the program in [Index Retrieval, and Proving Two Rules Are Inverses] verifies the two methods agree on every row of every metre up to sixteen syllables.

What this does NOT show

It does not show Piṅgala had a base. There is no statement anywhere in the text that a pattern has a numerical value, and no arithmetic is performed on a pattern.

It does not show he had positional notation. Positional notation is about writing numbers. He is writing metres, and the correspondence is something we can see and he did not need.

It does not make the prastāra a counter. A counter's purpose is to count. The prastāra's purpose is to enumerate patterns. They coincide, and coinciding is not the same as being the same thing.

The thing it does show is stronger than any of those: the order he chose, for reasons internal to prosody, is the unique order in which his two retrieval rules become simple arithmetic. That is a design decision paying off, and it is what a computer science student should admire.

Quick revision

• Base two: digits 0 and 1, places worth 1, 2, 4, 8. Adding one flips the low run of 1s to 0 and the next 0 to 1.
• The claim, checked for every row up to fourteen syllables: row r, counted from zero, is the pattern whose value is r with laghu as 1 and the leftmost syllable in the units place.
• The reason: the prastāra rule is the add-one rule written with the low-order digit on the left.
• The only difference from numeral notation is the direction, which is layout and not arithmetic, and it never bites because the text never adds two patterns.
• Not shown: that Piṅgala had a base, positional notation, or a counter.

Test yourself

1. State the correspondence between a prastāra row and a binary number exactly.

With laghu read as 1, guru as 0, and the leftmost syllable as the units place, the pattern in row r of the prastāra, counting rows from zero, has value r.

2. Explain in one sentence why the prastāra rule produces that order.

Because finding the first guru, making it laghu and resetting the laghus to its left is precisely the rule for adding one to a binary number written with its units digit on the left.

3. What is the single difference between a prastāra row and a binary numeral, and does it affect the order?

The units place is at the left-hand end instead of the right, so the symbols are written in the reverse direction. It does not affect the order of the rows at all.

4. Find row 17 of the four-syllable prastāra by arithmetic, and say what goes wrong.

Nothing can be found: the four-syllable prastāra has 16 rows, numbered 1 to 16, so there is no row 17. A four-syllable pattern carries four bits and covers the values 0 to 15 only.

So: 1, double to 2, square to 4, double to 8, square to 64. Four operations, and the answer is 64.

The figures his commentary then states

Having done the gāyatrī, he runs through the rest, and this is the part worth quoting in an answer, because the numbers are in the text.

Seven figures, seven exact powers of two, in a commentary on prosody.

The method, run

def marks(n):
    """Pingala's halving: S where the number was halved, D where one came off."""
    out = []
    x = n
    while x > 0:
        if x % 2 == 0:
            out.append("S")
            x //= 2
        else:
            out.append("D")
            x -= 1
    return "".join(reversed(out))

def sankhya(n):
    """Start at one; square at an S, double at a D."""
    v = 1
    for m in marks(n):
        v = v * v if m == "S" else v * 2
    return v

NAMED = [("gayatri", 6), ("usnih", 7), ("anustubh", 8), ("brhati", 9),
         ("pankti", 10), ("tristubh", 11), ("jagati", 12)]

print("%-10s %-4s %-8s %-6s %-6s %s" % ("metre", "n", "marks", "ops", "2**n", "sankhya"))
for name, n in NAMED:
    print("%-10s %-4d %-8s %-6d %-6d %d" % (name, n, marks(n), len(marks(n)), 2 ** n, sankhya(n)))

print()
bad = [n for n in range(1, 200) if sankhya(n) != 2 ** n]
print("values of n from 1 to 199 where the rule disagrees with 2**n:", bad)
print("operations for n = 100:", len(marks(100)), "against 100 multiplications")

metre      n    marks    ops    2**n   sankhya
gayatri    6    DSDS     4      64     64
usnih      7    DSDSD    5      128    128
anustubh   8    DSSS     4      256    256
brhati     9    DSSSD    5      512    512
pankti     10   DSSDS    5      1024   1024
tristubh   11   DSSDSD   6      2048   2048
jagati     12   DSDSS    5      4096   4096

values of n from 1 to 199 where the rule disagrees with 2**n: []
operations for n = 100: 9 against 100 multiplications

The mark string is printed in the order the operations are applied, so DSDS for the gāyatrī reads: double, square, double, square, which is Halāyudha's own sequence.

Why it works

Squaring doubles the exponent and doubling adds one to it. So if you can build n out of doublings and additions of one, you can build 2 to the power n out of squarings and doublings.

And building n that way is exactly the halving procedure read backwards: n is either twice something, or one more than something. That is the whole justification, and it is two sentences.

The running total

The last sūtra of the group answers a different question: how many metres are there altogether, from one syllable up to n? Halāyudha's gloss is to double the number of forms and reduce by two.

Check it. For the gāyatrī, double 64 is 128, less two is 126, and 2 plus 4 plus 8 plus 16 plus 32 plus 64 is 126. The formula is 2 to the power n plus one, minus two, and it is right.

What it does NOT mean

It does not mean Piṅgala had logarithms. Nothing counts operations, and nothing in the text says the method is faster than multiplying out. The saving is real and it is not remarked upon.

It does not mean the method is stated as general exponentiation. It is stated for powers of two, because that is what the subject needs. Squaring and doubling generalises immediately to any base, and the text does not generalise it.

It does not mean 2 to the power n was understood as a function. The commentary computes seven values. It does not write a formula.

Limits

The honest limit is that the method is presented as a recipe, not as an economy. Nobody in the text says "this is quicker". A modern reader supplies the observation that it takes about log n operations, and that observation, not the recipe, is what makes it a landmark. Saying so is better than pretending the text claims what it does not.

Quick revision

• Saṅkhyā: the number of patterns, without listing them.
• Going down: halve if even, subtract one if odd, marking which. Coming back up: start at one, square at a halving, double at a subtraction.
• Halāyudha's gāyatrī: 1, double 2, square 4, double 8, square 64. Four operations.
• His commentary states 64, 128, 256, 512, 1024, 2048, 4096 for six to twelve syllables, all exact powers of two.
• Why it works: squaring doubles the exponent, doubling adds one, and every number is twice something or one more than something.
• The running total sūtra: double the count and subtract two, which gives 126 for the gāyatrī.
• What is absent: any statement that the method is cheaper.

Test yourself

1. Compute 2 to the power 10 by Piṅgala's method, showing the marks and the operations.

Ten is even, halve to five, mark halved; five is odd, subtract one to four, mark reduced; four halves to two, mark halved; two halves to one, mark halved; one reduces to zero, mark reduced. Read back: start 1, double to 2, square to 4, square to 16, double to 32, square to 1024. Five operations.

2. Why does squaring correspond to halving, and doubling to subtracting one?

Because squaring a power of two doubles its exponent and doubling adds one to it, so the operations on the answer mirror, in reverse, the halvings and subtractions applied to the exponent.

3. Which figures from Halāyudha's commentary support the claim that his method is about powers of two?

Sixty-four for six syllables, and then 128, 256, 512, 1024, 2048 and 4096 for seven to twelve, each stated in Sanskrit numerals and each exactly a power of two.

4. What does the text NOT say about this method, and why does that matter to an honest answer?

It nowhere says that the method is faster than repeated multiplication, and it never counts operations. The economy is real but it is our observation, not the text's claim, and an answer that attributes it to the text overstates the evidence.

Worked. For n equal to 1000, b is 10. So at most 18 multiplications against 999. For n equal to a million, b is 20, so at most 38 against nearly a million.

And the lower bound. You cannot do better than about log n, because each multiplication at best doubles the largest exponent you hold, so after k multiplications the highest exponent reachable is 2 to the power k.

Piṅgala's version against the general one

The only mathematical difference is the fixed base. The doubling in his ascent is multiplication by the base, and his base happens to be two.

Why it still matters: modular exponentiation

This is the sentence to remember, because it links Module I to Module II.

Public-key cryptography rests on computing a to the power e modulo m where e and m are hundreds of digits long. With repeated multiplication that is impossible: there is not enough time in the universe. With square and multiply it is a few thousand multiplications, each of them on numbers of a few hundred digits, which is a fraction of a second.

Two details make it practical, and both are worth naming.

Reduce modulo m at every step. Otherwise the intermediate numbers grow to astronomical size. Squaring a number of d digits gives 2d digits, so after twenty squarings you would have a million digits.

The bits of the exponent are secret. Because the algorithm does an extra multiplication exactly when a bit is one, an attacker who can measure the time or the power consumption can read the exponent off. Real implementations therefore do the same work whichever the bit is. That is a whole field, and [Symmetric Encryption] and [Cipher Algorithms, Classical to Modern] return to the general point that an algorithm's timing can leak its secrets.

What it does NOT mean

It does not mean Piṅgala invented the algorithm for a general base. His base is two throughout and no generalisation appears.

It does not mean the method is always best. For a small n, repeated multiplication is simpler and the difference is nothing. The method earns its keep when n is large.

It does not mean the cost is exactly log n. It is between log n and 2 log n depending on how many ones the exponent has, and an answer that says "about log n" is right while one that says "log n" is imprecise.

Quick revision

• Binary exponentiation: square at each bit, multiply by the base where the bit is one. At most 2 log n multiplications.
• Top down, from the most significant bit: result starts at a, then square and conditionally multiply.
• Bottom up: while n is positive, multiply into the result if n is odd, square the base, halve n.
• Piṅgala's saṅkhyā is the same algorithm with the base fixed at two, and his doubling is multiplication by that base.
• The lower bound is about log n, because each multiplication at best doubles the largest exponent held.
• It is what makes public-key cryptography possible; reduce modulo m at every step, and beware that the timing leaks the exponent.

Test yourself

1. Compute a to the power 13 by squaring, listing the exponents reached.

Write 13 as 1101. Start at a, exponent 1. Square and multiply by a: 3. Square: 6. Square and multiply by a: 13. Five multiplications.

2. Give the cost of the method and the reason it cannot be improved much.

At most 2 log n multiplications, since there are about log n bits and each contributes a squaring and possibly one multiplication. It cannot be improved beyond about log n because each multiplication at best doubles the largest exponent held, so k multiplications reach at most 2 to the power k.

3. What is the one mathematical difference between Piṅgala's saṅkhyā and binary exponentiation?

Piṅgala's base is fixed at two, so his "multiply by the base" step appears as doubling. Otherwise the descent and the ascent are identical.

4. Why must a modular exponentiation reduce at every step, and what does the algorithm leak if written naively?

Without reducing, the intermediate values double in length at each squaring and become unmanageable. Written naively it performs an extra multiplication exactly when an exponent bit is one, so its running time or power draw reveals the exponent.

Worked by hand: G G G L G L

Row forty-one, which is the row [Binary Number Systems, and Exactly Where Piṅgala's Order Agrees] reached by arithmetic. The two methods agree.

Why the rule is right

Write the row number, counted from one, as one plus the pattern's binary value with laghu as 1 and the leftmost syllable in the units place. Then the rule is Horner's method for evaluating that expression from the high-order end, which for this direction of writing means from the right.

Let y stand for the running number after some syllables have been taken. The step "double, and subtract one at a guru" is the same as "double, and add one at a laghu, then subtract one". Which is to say: it evaluates twice the previous value, plus the current bit, minus one. Unrolled from a start of one, that is exactly one plus the binary value.

The short version, which is the one to write in an examination: the rule is Horner's evaluation of the pattern as a binary number, shifted by one because rows are counted from one and numbers from zero.

The rule, run

def uddista(pattern):
    """8.26 pratilomagunam dvirladyam, with 8.27 tato'pyekam jahyat.

    Take the syllables from the LAST to the first. Start at one. At each
    syllable double; and if that syllable is a guru, subtract one.
    """
    y = 1
    for ch in reversed(pattern):
        y *= 2
        if ch == "G":
            y -= 1
    return y

for p in ("GGGGGG", "LGLGGG", "GGGLGL", "LLLLLL", "GGG", "LLL"):
    print("%-8s row %d" % (p, uddista(p)))

GGGGGG   row 1
LGLGGG   row 6
GGGLGL   row 41
LLLLLL   row 64
GGG      row 1
LLL      row 8

Four lines of code for a rule stated in two sūtras. The whole content is y = 2*y with a conditional y -= 1.

The cost

One pass over the pattern, one doubling and at most one subtraction per syllable. So the work is proportional to n, the number of syllables, and does not depend on how large the row number is.

Compare the alternative: generating the table and searching it costs n times 2 to the power n. For the jagatī that is 49,152 symbol operations against 12. This is the same improvement in kind that an index gives over a scan, and it is worth saying in exactly those words, because that is what MU's phrase "index retrieval mechanisms" is pointing at.

What it does NOT mean

It does not mean the pattern is validated. Give the rule a pattern of the wrong length and it will cheerfully return a number. Nothing in the text checks the input, and a program should.

It does not mean rows are counted from zero. They are counted from one throughout the tradition, which is why the rule starts at one rather than at zero. Mixing the conventions is the commonest arithmetic mistake in this topic.

It does not work for another order. Later prosodists use the reverse order, and uddiṣṭa for that order is a different rule. Applying this one to a table built the other way gives a wrong answer silently.

Quick revision

• Uddiṣṭa: from a pattern to its row number.
• 8.26 pratilomaguṇaṃ dvirlādyam, reverse order, doubling; 8.27 tato'pyekaṃ jahyāt, and subtract one, which Halāyudha applies at a guru.
• The rule: start at one, take syllables from last to first, double each time, subtract one at a heavy syllable.
• Worked: L G L G G G is row 6; G G G L G L is row 41.
• It is Horner's evaluation of the pattern as a binary number, offset by one because rows count from one.
• Cost proportional to n, against n times 2 to the power n for generate and search.

Test yourself

1. Find the row number of G L L G by the rule, showing the running value.

Syllables from the last: G, L, L, G. Start 1. G: double to 2, subtract one, 1. L: double to 2. L: double to 4. G: double to 8, subtract one, 7. Row seven.

2. Why do trailing heavy syllables leave the running number unchanged?

Because doubling one and subtracting one gives one again. In the binary reading they are leading zeros, which contribute nothing to a number's value.

3. State the modern description of the rule in one sentence.

It is Horner's method for evaluating the pattern as a binary number with laghu as one and the leftmost syllable in the units place, offset by one because rows are counted from one.

4. Give the cost of uddiṣṭa and of the obvious alternative, for a twelve-syllable metre.

Uddiṣṭa is twelve doublings, one per syllable. Generating the table and searching it is 4096 rows of twelve symbols, about 49,000 symbol operations.

Reading the syllable column downward gives L G L G G G, and that is row six.

Check it against the other rule: [Uddiṣṭa: From a Pattern to Its Row Number] takes L G L G G G and returns six. The two rules agree, and they must, because they are inverses.

Worked by hand: row 41 of the gāyatrī

G G G L G L, which is the pattern [Binary Number Systems, and Exactly Where Piṅgala's Order Agrees] reached by arithmetic and which uddiṣṭa returns forty-one for.

Why the rule is right

In the binary reading, the row number minus one is the pattern's value with laghu as one and the leftmost syllable in the units place. So the first syllable is laghu exactly when the units bit of the row number minus one is one, that is, exactly when the row number minus one is odd, that is, exactly when the row number is even.

That is step two. And halving the even row number r gives r over two, whose parity decides the next syllable in the same way.

For the odd case, r minus one is even, so the bit is zero and the syllable is guru; and the next number needed is r minus one over two plus one, which is r plus one over two. That is step three, with the plus one before the halving doing exactly that arithmetic.

So: "add one before halving at an odd number" is the correction that keeps the count on a one-based scale. That single detail is what makes the rule work on row numbers rather than on values, and it is the detail a student who reinvents the rule always gets wrong.

The rule, run, with both directions checked

def nasta(n, r):
    """8.24 lardhe and 8.25 saike g.

    Halve the row number; if it was even write a laghu, and if it was odd add
    one before halving and write a guru. Do this n times, writing from the left.
    """
    out = []
    x = r
    for _ in range(n):
        if x % 2 == 0:
            out.append("L")
            x //= 2
        else:
            out.append("G")
            x = (x + 1) // 2
    return "".join(out)

def uddista(pattern):
    y = 1
    for ch in reversed(pattern):
        y *= 2
        if ch == "G":
            y -= 1
    return y

print("the six syllable metre, Halayudha's own example is row 6")
for r in (1, 6, 41, 64):
    p = nasta(6, r)
    print("  row %-3d nasta gives %-8s uddista gives it back as %d" % (r, p, uddista(p)))

the six syllable metre, Halayudha's own example is row 6
  row 1   nasta gives GGGGGG   uddista gives it back as 1
  row 6   nasta gives LGLGGG   uddista gives it back as 6
  row 41  nasta gives GGGLGL   uddista gives it back as 41
  row 64  nasta gives LLLLLL   uddista gives it back as 64

The cost

One halving and at most one addition per syllable, so the work is proportional to n and independent of how large the row number is. Finding row 4000 of a twelve-syllable metre costs the same twelve steps as finding row 1.

What it does NOT mean

It does not check the row exists. Ask for row 100 of a three-syllable metre and the rule returns a pattern. There are only eight rows. Nothing in the text validates the input and a program must.

It does not stop when the number reaches one. It stops when the syllable count is reached. A reader who stops early produces a short pattern, and this is the commonest mistake in working the rule by hand.

It does not depend on the table existing. That is the point of it. The pattern is computed, not looked up, and the table never has to be written at all.

Quick revision

• Naṣṭa: from a row number to the pattern in that row.
• 8.24 lardhe: halve, and write L. 8.25 saike g: if odd, add one, halve, and write G.
• Write syllables left to right, one per step, and stop when the syllable count is reached, not when the number reaches one.
• Halāyudha's own example: row 6 of the gāyatrī is L G L G G G.
• Row 41 of the gāyatrī is G G G L G L.
• Cost proportional to the number of syllables, independent of the row number.
• The "add one before halving" is the correction for rows being counted from one.

Test yourself

1. Find row 11 of the four-syllable metre by the rule.

11 is odd: add one, halve to 6, write G. 6 is even: halve to 3, write L. 3 is odd: add one, halve to 2, write G. 2 is even: halve to 1, write L. The pattern is G L G L.

2. Why is one added before halving when the number is odd?

Because rows are counted from one and values from zero. For an odd row number r, the value r minus one is even, so the syllable is guru, and the next number required is r minus one over two plus one, which equals r plus one over two.

3. When does the rule stop, and what happens if a student stops too early?

It stops when as many syllables have been written as the metre has. Stopping when the number reaches one produces a pattern that is too short, which is the commonest error in working it by hand.

4. How much work does naṣṭa do for row 4000 of a twelve-syllable metre, and how much does generating the table do?

Naṣṭa does twelve halvings. Generating the table and counting to row 4000 does about 4000 rows of twelve symbols, roughly 48,000 symbol operations.

n      rows     inverses   first failure
1      2        yes        none
2      4        yes        none
3      8        yes        none
4      16       yes        none
5      32       yes        none
6      64       yes        none
7      128      yes        none
8      256      yes        none
9      512      yes        none
10     1024     yes        none
11     2048     yes        none
12     4096     yes        none
13     8192     yes        none
14     16384    yes        none
15     32768    yes        none
16     65536    yes        none

Sixteen syllable counts, 131,070 rows in total, every one checked in both directions.

Why exhaustive checking is worth something here, and where it stops

What it establishes. For every metre up to sixteen syllables, the two rules are exactly inverse. No case within that range can be wrong.

What it does not establish. That they are inverse for every n. A test over a finite range is a test, not a proof.

The proof, for the record, is the argument given in the two previous chapters: both rules compute the same correspondence between row numbers and binary values, one in each direction, and a bijection's inverse is unique. State the argument and offer the check as evidence, never the check alone. That is the difference between a program that passes and a claim that is justified, and it is the distinction MU's "analysis of correctness" is asking for.

Worked example: the other direction, and the round trip

Take the jagatī, twelve syllables, and row 2731.

Naṣṭa. 2731 is odd, so add one and halve to 1366, writing G. 1366 halves to 683, writing L. 683 is odd, so 342, writing G. 342 halves to 171, L. 171 odd, 86, G. 86 halves to 43, L. 43 odd, 22, G. 22 halves to 11, L. 11 odd, 6, G. 6 halves to 3, L. 3 odd, 2, G. 2 halves to 1, L. The pattern is G L G L G L G L G L G L.

Uddiṣṭa on that pattern. From the last syllable, which is L: 1 doubles to 2. G: 4 less one, 3. L: 6. G: 12 less one, 11. L: 22. G: 44 less one, 43. L: 86. G: 172 less one, 171. L: 342. G: 684 less one, 683. L: 1366. G: 2732 less one, 2731.

The round trip closes, and the alternating pattern is worth noticing: the row numbers of alternating patterns are the numbers whose binary form alternates, which for twelve places is 2730 as a value and 2731 as a row.

What this does NOT give you

It does not give you search. Neither rule answers "which rows have exactly four laghus?". That is lagakriyā, and it is a different pratyaya with a different answer, in [Meru-Prastāra: Halāyudha's Staircase].

It does not give you a sorted order other than its own. The index is the index of Piṅgala's order. A question about a different order needs different rules.

It does not validate anything. Neither rule checks that the row exists or that the pattern has the right length. A program that exposes them to a user must.

Quick revision

• Index retrieval: reaching an element by its position, and a position by its element, in time independent of the collection's size.
• Naṣṭa is number to pattern; uddiṣṭa is pattern to number. Each costs one step per syllable and needs no table.
• The modern analogue is a computed address, as in an array index or a hash function.
• The pair is exactly inverse; checked over 131,070 rows up to sixteen syllables, and proved by the binary correspondence.
• An exhaustive check over a range is evidence, not a proof. Give the argument and offer the check.
• Neither rule searches, validates, or works for a different ordering.

Test yourself

1. What does it mean to call naṣṭa and uddiṣṭa index retrieval mechanisms?

They give access to a row by its position and to a position by its row, in time proportional to the syllable count and independent of the number of rows, without the collection being stored.

2. Compare the three ways of answering "what is row 4000 of the jagatī?" by cost.

Scanning costs about 4000 rows of work. Storing the table costs 4096 rows of space to build and hold, then one lookup. Computing by naṣṭa costs twelve steps and no space.

3. Why is the exhaustive check in this chapter not a proof, and what is the proof?

Because it covers only n up to sixteen. The proof is that both rules compute the same bijection between row numbers and binary values, one in each direction, and the inverse of a bijection is unique.

4. Which question do these two rules NOT answer, and which pratyaya does?

They do not answer how many patterns have a given number of light syllables. That is lagakriyā, answered by the Meru-prastāra.

The new column is at the right-hand end. Put it at the left and you get sixteen distinct rows in the wrong order, and every test that counts rows will pass. [Prastāra in Code] records that this book's own program made exactly that mistake and how it was caught.

The call tree

The recursion for n equal to three makes one call for n equal to two, which makes one call for n equal to one, which returns. So the calls are a chain of length n, not a branching tree, and the depth of the recursion is n.

That is worth stating because it is the resource that runs out first. Each pending call occupies space, so a recursion of depth n uses space proportional to n even if it returns nothing. A recursion of depth one million will exhaust the stack of most languages, and Python's default limit is a thousand.

Recursion against iteration, on the same problem

Both are in the text, in the sense that the same sūtra supports both readings. Neither is better in the abstract. The iterative form is what you want if you are producing one row at a time; the recursive form is what you want if you are proving something about the table, because an induction on n follows the recursion exactly.

Proof by induction, which is the recursion's real payoff

Claim: the prastāra for n syllables has 2 to the power n rows.

Base case. For n equal to one the table has two rows, and 2 to the power 1 is 2.

Inductive step. Suppose the table for n minus one has 2 to the power n minus one rows. The rule writes it twice, so the new table has twice that many, which is 2 to the power n.

Therefore the claim holds for every n by induction.

That proof is three lines and it is available only because the definition is recursive. The iterative rule gives the same fact by the counting argument in [The Prastāra Rule Read as an Algorithm], which is longer. A recursive definition makes induction easy, and that is the strongest reason to have one.

What recursion is NOT

It is not the same as a loop that calls itself. The distinguishing feature is the base case. A procedure that calls itself with no base case is not recursion, it is a fault.

It is not always slower. The overhead is a function call, which is small. Where recursion is expensive here is in space, because every intermediate table is retained.

It is not restricted to one recursive call. Halāyudha's rule uses the smaller table twice, but it calls for it once and copies it. A definition that made two separate calls for the same thing would do the work twice, which is the problem [Meru-Prastāra as a Dynamic Programming Model] is about.

Quick revision

• A recursive definition has a base case, a recursive case, and progress toward the base case.
• Sūtra 8.20 is the base case, one syllable, two rows. Sūtra 8.22 is the recursive case: the shorter table twice, new column on the right.
• Halāyudha states the stopping condition himself: "again and again, until the desired prastāra".
• The recursion's depth is n, and depth costs space even when nothing is returned.
• Iterative: one row held, no nesting. Recursive: every intermediate table held, depth n.
• The payoff of recursion is induction: the 2 to the power n count is a three-line proof.

Test yourself

1. Name the three things a recursive definition needs, and give Piṅgala's instance of each.

A base case: the one-syllable table, from 8.20. A recursive case: the table for n minus one written twice with the new column filled, from 8.22. Progress toward the base case: each step reduces n by one, bounded below by one.

2. Build the three-syllable prastāra from the two-syllable one.

The two-syllable table is GG, LG, GL, LL. Written twice with a third column of heavy then light: GGG, LGG, GLG, LLG, then GGL, LGL, GLL, LLL.

3. Prove by induction that the prastāra for n syllables has 2 to the power n rows.

For n equal to one there are two rows. If the table for n minus one has 2 to the power n minus one rows, the rule writes it twice, giving twice as many, which is 2 to the power n. The claim follows for all n.

4. Which resource does recursion consume that iteration does not, and why?

Space for the pending calls, proportional to the depth, because each call that has not yet returned must be remembered. For this rule the depth is n, and in addition every intermediate table is retained.

The tree, drawn by a program

def uddista(pattern):
    y = 1
    for ch in reversed(pattern):
        y *= 2
        if ch == "G":
            y -= 1
    return y

def draw(n, prefix="", depth=0):
    """The prastara as a binary tree. Every leaf is one pattern."""
    if depth == n:
        print("%s    pattern %s, prastara row %d" % ("    " * depth, prefix, uddista(prefix)))
        return
    for symbol in ("G", "L"):
        print("%s+-- %s" % ("    " * depth, symbol))
        draw(n, prefix + symbol, depth + 1)

print("root, no syllables chosen yet")
draw(3)
print()
print("leaves: 2**3 =", 2 ** 3, "   depth:", 3, "   internal nodes:", 2 ** 3 - 1)

root, no syllables chosen yet
+-- G
    +-- G
        +-- G
                pattern GGG, prastara row 1
        +-- L
                pattern GGL, prastara row 5
    +-- L
        +-- G
                pattern GLG, prastara row 3
        +-- L
                pattern GLL, prastara row 7
+-- L
    +-- G
        +-- G
                pattern LGG, prastara row 2
        +-- L
                pattern LGL, prastara row 6
    +-- L
        +-- G
                pattern LLG, prastara row 4
        +-- L
                pattern LLL, prastara row 8

leaves: 2**3 = 8    depth: 3    internal nodes: 7

The complication, which is the point of the chapter

Read the leaves top to bottom: rows 1, 5, 3, 7, 2, 6, 4, 8. That is not the prastāra order.

The reason is exact and it is worth being able to state. The tree's natural traversal fixes the FIRST syllable at the top and varies the LAST one fastest. The prastāra varies the FIRST syllable fastest. So the two orders differ, and they differ by reversing the significance of the positions.

Three ways to put it, all the same fact.

In tree terms. A depth-first traversal that chooses the first syllable at the root is a big-endian traversal, and the prastāra is little-endian.

In binary terms. The traversal enumerates 000, 001, 010, 011, 100, 101, 110, 111 with the first symbol as the most significant bit. The prastāra enumerates the same strings with the first symbol as the least significant.

In practical terms. If you want the tree's traversal to produce the prastāra, put the LAST syllable at the root. Then each level down fixes an earlier syllable, and the leaves come out in Piṅgala's order.

This is not a defect in either structure. It is the thing to be careful about, and a student who can say why the orders differ understands both.

What the tree is good for, and what it is not

Good for: reasoning about the count. The 2 to the power n leaves and the 2 to the power n plus one minus two edges both fall out of the picture in a line.

Good for: pruning. If you only want patterns with no two adjacent heavy syllables, you can abandon a subtree the moment the condition fails, and never visit its leaves. That is a saving the flat table cannot express, and it is how a search problem is usually attacked.

Not good for: storage. Holding the tree costs more than holding the table, because the internal nodes are stored too. The tree is a way of thinking, and the table is the answer.

Not good for: random access. There is no way to jump to the forty-first leaf of a tree without walking. That is what naṣṭa is for, and it is the one thing the tree makes harder rather than easier.

Quick revision

• Tree vocabulary: node, edge, root, parent, child, leaf, depth, height, path. Binary tree: at most two children. Complete binary tree of depth n: 2 to the power n leaves.
• The prastāra is the tree of n two-way choices; a pattern is a path from the root to a leaf.
• Leaves: 2 to the power n. Edges: 2 to the power n plus one, minus two, which is the running total sūtra's figure.
• The tree's natural traversal is big-endian and the prastāra is little-endian, so the leaf order is NOT the prastāra order. Put the last syllable at the root to fix it.
• The tree is good for counting and for pruning, bad for storage and for random access.

Test yourself

1. Define leaf, depth and complete binary tree, and say how many leaves a complete binary tree of depth 6 has.

A leaf is a node with no children. The depth of a node is the number of edges from the root to it. A complete binary tree of depth n has two children at every node above depth n and all its leaves at depth n. At depth 6 it has 64 leaves.

2. Why is the prastāra a binary tree, and what does a path represent?

Because a pattern is built by n successive two-way choices of syllable, so the set of patterns is the set of root-to-leaf paths in a complete binary tree of depth n. A path spells the pattern.

3. The tree's leaves come out as rows 1, 5, 3, 7, 2, 6, 4, 8. Explain why, and say how to fix it.

The traversal fixes the first syllable at the root, so the last syllable varies fastest, which makes the first syllable the most significant. The prastāra makes the first syllable the least significant. Putting the last syllable at the root makes the traversal produce Piṅgala's order.

4. Name one thing the tree makes easier than the flat table and one thing it makes harder.

Easier: pruning, since a subtree whose patterns cannot satisfy a condition can be abandoned without visiting its leaves. Harder: random access, since there is no way to jump to the forty-first leaf without walking, which is exactly what naṣṭa does arithmetically.

What he then reads off the rows

This is the part that settles what the array is for, and he states it directly.

Row two. In the two-celled row is the arrangement of one syllable: there one is guru and one is laghu.

Row three. In the third row is the prastāra of two syllables: there one is all-guru, two have one laghu, one is all-laghu, and these are the forms in the order of the cells.

Row four. In the fourth row is the prastāra of three syllables: there one is all-guru, three have one laghu, three have two laghus, one is all-laghu.

So the rows he reads are 1 1, then 1 2 1, then 1 3 3 1. In a commentary on Sanskrit metre.

The array, drawn by the rule

def meru(rows):
    """Halayudha's staircase: one at the top; an end cell takes the one above it,
    an inner cell takes the two cells above it, combined."""
    tri = [[1]]
    for _ in range(rows - 1):
        prev = tri[-1]
        tri.append([1] + [prev[i] + prev[i + 1] for i in range(len(prev) - 1)] + [1])
    return tri

WIDTH = 5
tri = meru(8)
for i, row in enumerate(tri):
    pad = " " * (WIDTH * (len(tri) - 1 - i) // 2)
    print("%s%s" % (pad, "".join("%*d" % (WIDTH, x) for x in row)))

                     1
                   1    1
                1    2    1
              1    3    3    1
           1    4    6    4    1
         1    5   10   10    5    1
      1    6   15   20   15    6    1
    1    7   21   35   35   21    7    1

The staggering in the output is the staggering the commentary describes: each row is offset by half a cell so that every interior cell sits beneath two.

How to read a row

Take the row beginning 1 6 15 20. Counting the top cell as row zero, this is row six, so it is about metres of six syllables, the gāyatrī.

Add them: 1 plus 6 plus 15 plus 20 plus 15 plus 6 plus 1 is 64, which is the saṅkhyā for the gāyatrī and the figure Halāyudha states. Every row sums to the number of patterns, which is a check you can run on any row by eye.

Why the addition rule is right

Take a pattern of n syllables with exactly k light ones. Look at its last syllable.

If the last syllable is heavy, the first n minus one syllables form a pattern of n minus one syllables with exactly k light ones.

If the last syllable is light, the first n minus one syllables form a pattern of n minus one syllables with exactly k minus one light ones.

Every pattern falls into exactly one of those two cases, and nothing is counted twice. So the count for n and k is the count for n minus one and k, plus the count for n minus one and k minus one.

Those two counts are the two cells above. That is the rule, and the argument is four lines.

The end cells

An end cell is 1 because there is exactly one way to have no light syllables, namely all heavy, and exactly one way to have all of them light. Halāyudha's instruction to place one in each end cell is not an exception to the rule; it is the rule applied where one of the two cells above is missing and counts as nothing.

What the Meru is NOT

It is not the prastāra. The prastāra lists patterns; the Meru counts them by a property. Confusing the two is the commonest error in this topic.

It is not indexed by the row number of a pattern. Cell three of row six does not mean row three. It means the count of patterns with three light syllables.

It is not a table of powers. Its rows sum to powers of two, which is a fact about it, not what it holds.

Quick revision

• Meru-prastāra: one at the top, ones at the ends, every interior cell the sum of the two above.
• Halāyudha describes the staggered cells, sets one in the first cell, and glosses "full" as the two above combined.
• He reads the rows off: 1 1 for one syllable, 1 2 1 for two, 1 3 3 1 for three.
• Row n, cell k, counting both from zero, is the number of patterns of n syllables with exactly k light syllables.
• Every row sums to 2 to the power n, which is the saṅkhyā.
• Why: split the patterns on the last syllable, heavy or light, and the two cases are the two cells above.

Test yourself

1. State the construction rule of the Meru-prastāra in one sentence.

Place one in the topmost cell and one in each end cell of every row, and in every interior cell place the sum of the two cells immediately above it.

2. What does cell 2 of row 5 mean, and what is its value?

The number of patterns of five syllables with exactly two light syllables, which is 10.

3. Prove the addition rule.

Classify the patterns of n syllables with k light ones by their last syllable. If it is heavy, the rest is a pattern of n minus one syllables with k light ones; if it is light, the rest has k minus one light ones. The two cases are exclusive and exhaustive, so the count is the sum of those two counts, which are the two cells above.

4. Why is every end cell a one, and why is that not an exception to the rule?

There is exactly one all-heavy pattern and exactly one all-light pattern. It is not an exception because one of the two cells above an end cell does not exist and counts as nothing, so the sum is just the single cell above, which is one.

n    counted off the table      Meru row n                 sum    2**n
1    [1, 1]                     [1, 1]                     2      2
2    [1, 2, 1]                  [1, 2, 1]                  4      4
3    [1, 3, 3, 1]               [1, 3, 3, 1]               8      8
4    [1, 4, 6, 4, 1]            [1, 4, 6, 4, 1]            16     16
5    [1, 5, 10, 10, 5, 1]       [1, 5, 10, 10, 5, 1]       32     32
6    [1, 6, 15, 20, 15, 6, 1]   [1, 6, 15, 20, 15, 6, 1]   64     64
7    [1, 7, 21, 35, 35, 21, 7, 1] [1, 7, 21, 35, 35, 21, 7, 1] 128    128
8    [1, 8, 28, 56, 70, 56, 28, 8, 1] [1, 8, 28, 56, 70, 56, 28, 8, 1] 256    256

and the same figures from the binomial coefficient, n = 6
  k:         0    1    2    3    4    5    6
  C(6,k):    1    6   15   20   15    6    1
  Meru:      1    6   15   20   15    6    1

Three independent routes: counting the patterns one at a time, adding cells in the staircase, and the closed form. They agree at every value printed, and the first two agree at every n from one to eight, which is 510 patterns counted by hand by the machine.

The identities worth knowing

Each of these is a fact about the triangle that a five-mark question can ask for, and each has a one-line reason.

Symmetry: C(n, k) equals C(n, n minus k). Choosing which k are light is the same as choosing which n minus k are heavy. That is why every row reads the same backwards.

Row sum: the row for n adds to 2 to the power n. Every pattern has some number of light syllables, so summing over all k counts every pattern once. This is the link between the lagakriyā and the saṅkhyā, and it is Halāyudha's own 64 for the gāyatrī.

The ends are one. Exactly one all-heavy pattern and one all-light one.

The second entry is n. There are n positions in which the single light syllable can stand.

The addition rule. Proved in [Meru-Prastāra: Halāyudha's Staircase] by splitting on the last syllable.

Worked example: a real prosodic question

How many six-syllable patterns have more heavy syllables than light ones?

By the row. More heavy than light means fewer than three light, so k is 0, 1 or 2. The row for six is 1, 6, 15, 20, 15, 6, 1. So 1 plus 6 plus 15, which is 22.

Checked another way. By symmetry, the number with more light than heavy is also 22, and the number with exactly three of each is 20. Now 22 plus 22 plus 20 is 64, which is the whole table. The two answers are consistent.

That second calculation is worth doing every time. A row of the Meru gives you a free check on any counting answer, because the parts must add to the row sum.

What this is NOT

It is not a claim of priority over Pascal. The claim this book makes is that the array and its construction rule are in Halāyudha's commentary, which is a statement about a text. Questions of who first wrote down what, in which century, in which tradition, are a matter for historians of mathematics and the literature on them is large. An answer should say the array is in the commentary and leave the rest.

It is not the same object as the prastāra. Both are called prastāra in Sanskrit, and they are different things: one lists, the other counts.

It is not limited to two symbols. With three symbols the analogous array is the trinomial triangle, and the prosodic tradition that counts by mātrā rather than by syllable meets a related problem.

Quick revision

• The lagakriyā and the count of k-subsets of n are the same problem: choosing which syllables are light is choosing which positions.
• C(n, k) is n factorial over k factorial times n minus k factorial, but compute it by alternating multiplication and division.
• Identities: symmetry, so rows read the same backwards; row sum 2 to the power n; ends are one; second entry is n; and the addition rule.
• Three routes agree: counting off the prastāra, the Meru's additions, the closed form.
• A row gives a free check on any counting answer, since the parts must add to the row sum.

Test yourself

1. Explain in one sentence why the lagakriyā is a binomial coefficient.

Because choosing which k of the n syllables are light is exactly choosing a subset of k positions from n, and the pattern is then determined, so patterns and subsets correspond one to one.

2. Compute C(7, 3) without factorials, showing the steps.

7 over 1 is 7; times 6 over 2 is 21; times 5 over 3 is 35. So C(7, 3) is 35, which is the fourth entry of row seven.

3. How many eight-syllable patterns have exactly three light syllables, and how do you check your answer?

Row eight is 1, 8, 28, 56, 70, 56, 28, 8, 1, so the answer is 56. Check it by symmetry against the count with five light syllables, which is also 56, and by the row sum, which is 256.

4. State carefully what this book claims about the Meru-prastāra and Pascal's triangle.

That the array, its construction by adding the two cells above, and the reading of its rows as counts of patterns by number of light syllables are all present in Halāyudha's commentary on Piṅgala. It makes no claim about priority, which is a historical question with its own literature.

n      k      C(n,k)   naive calls  memo calls   table cells
6      3      20       39           19           27
10     5      252      503          51           65
14     7      3432     6863         99           119
18     9      48620    97239        163          189
22     11     705432   1410863      243          275

Read the last row. The answer is 705,432 and the naive recursion makes 1,410,863 calls to find it, which is twice the answer minus one. The memoised version makes 243. The naive cost is proportional to the answer itself, which is the worst possible behaviour, and the reason is visible: with no memory the recursion effectively counts the subsets one at a time.

The costs, stated

The last row is worth noticing: for a single value, the multiplicative formula of [Pascal Triangle and Combinatorics] beats all three, and dynamic programming is not always the answer even when it applies.

Where Halāyudha's instruction sits in this

His rule is the tabulated form, exactly. He says to draw the cells, put one at the top, and fill each row from the row above. That is bottom-up dynamic programming in the ordinary sense: no subproblem is solved twice because the order of filling guarantees the dependencies are already present.

What is not in his text. No statement that the alternative is slow, no count of operations, and no notion of a subproblem. The structure is there and the analysis is ours. Saying so is the honest form of the claim, and it is the form MU's "critically assess" wants.

Worked example: MU's implementation topic

Her topic 6 asks for the Meru-prastāra as a Pascal triangle and dynamic programming model. A submission that scores well answers four questions and the chapter has now given all four.

What is the IKS concept? Halāyudha's staircase, constructed by adding the two cells above, and read as the count of patterns by number of light syllables.

What is the CS concept? Bottom-up dynamic programming over the binomial addition rule.

What is the mapping? A cell is a subproblem; the addition rule is the recurrence; filling row by row is the tabulation order; the end cells are the base cases.

What is the evidence? The call counts above. A submission that states them has measured its claim, which is what her "analysis of correctness and limitations" asks for.

What dynamic programming is NOT

It is not recursion with a cache, in general. Memoisation is one of its two forms. Tabulation involves no recursion at all.

It is not applicable to every recursive problem. Without overlapping subproblems there is nothing to save. The prastāra's own recursion has none.

It is not free. Memoisation costs space proportional to the number of distinct subproblems, and for a large n times k that can be the binding constraint. Tabulation over one row at a time avoids it, which is why the bottom-up form is often preferred.

Quick revision

• Two conditions: optimal substructure and overlapping subproblems. Both hold for the binomial addition rule.
• Three forms: naive recursion, memoisation top down, tabulation bottom up.
• Measured: C(22, 11) is 705,432 and the naive recursion takes 1,410,863 calls; memoisation takes 243.
• Naive time is proportional to the answer; memoisation to n times k; tabulation to n squared with space for one row; the closed form to k with constant space.
• Halāyudha's instruction is the tabulated form. The structure is his; the analysis is ours.

Test yourself

1. State the two conditions for dynamic programming and show that the binomial addition rule meets both.

Optimal substructure: C(n, k) is the sum of C(n minus 1, k) and C(n minus 1, k minus 1). Overlapping subproblems: C(n minus 1, k minus 1) is reached from both C(n, k) and C(n, k minus 1), and the overlap grows with n.

2. Why is the naive recursion's cost proportional to the answer?

Because with no memory the recursion bottoms out at a base case once for every subset being counted, so the number of leaf calls is the value of C(n, k) itself.

3. Distinguish memoisation from tabulation and give one advantage of each.

Memoisation is top down: apply the recurrence but look up and store each answer. Tabulation is bottom up: fill the array in an order that guarantees dependencies are present. Memoisation computes only the cells actually needed; tabulation needs no recursion and can keep only one row at a time.

4. Which form does Halāyudha's instruction correspond to, and what is absent from his text?

Tabulation, since he fills each row from the row above. Absent are any statement that an alternative would be slow, any count of operations, and any notion of a subproblem.

Adhvayoga, and Halāyudha's own refusal

At the close of the eighth chapter he records that some count a sixth pratyaya, which he calls the measuring of the extent, and says it is not stated here because it is very slight, adding that it varies with the metre. Then: thus the group of pratyayas is complete.

Two things worth taking from that.

The set is a set. He treats the pratyayas as a closed group and says so, which is why "name the six pratyayas" is a fair question.

He gives a reason for an omission. That is a habit of a formal tradition: a gap is declared rather than left.

The arithmetic, stated as the obvious reading

Since the commentary declines to give the rule, this book gives the arithmetic and labels it as the obvious reading rather than as the text's own.

Worked. What is being measured. A written prastāra of n syllables has 2 to the power n rows, each n symbols wide, and a gap between consecutive rows.

So the extent, counted in symbol widths, is n times 2 to the power n for the symbols, plus 2 to the power n minus 1 for the gaps.

What makes this a genuine pratyaya rather than a triviality is that, like saṅkhyā, it is answered without drawing the table. And the modern point is exactly the one a programmer meets: the SPACE a computation needs is a resource to be estimated in advance, separately from the time. A tradition that lists "how much room will this take" beside "how many are there" is thinking about both.

Where Halāyudha is right that it is slight

He is right, and it is worth saying so rather than inflating the sixth pratyaya's importance.

It is derivable from saṅkhyā in one step. Once you know there are 2 to the power n rows, multiplying by the width is not a new idea.

It depends on the writing surface. How wide a symbol is, and whether rows are spaced, is a matter of the palm leaf and not of the mathematics. That is presumably what he means by saying it varies.

Nothing else depends on it. No other pratyaya uses its result.

Quick revision

• Six pratyayas: prastāra, naṣṭa, uddiṣṭa, lagakriyā, saṅkhyā, adhvayoga.
• Lagakriyā is the question "how many have k light syllables"; the Meru-prastāra is the instrument that answers it. Halāyudha says the Meru is shown for the sake of the lagakriyā.
• Adhvayoga measures the written extent. Halāyudha records that some count it and leaves it out as very slight and as varying with the metre.
• Its arithmetic: n times 2 to the power n symbol widths, plus 2 to the power n minus 1 gaps. Six syllables gives 447.
• Every pratyaya after the first avoids building the table.
• He declares the omission rather than leaving a gap, which is a habit of a formal tradition.

Test yourself

1. Name the six pratyayas and the question each answers.

Prastāra, all the patterns; naṣṭa, the pattern in a given row; uddiṣṭa, the row of a given pattern; lagakriyā, how many patterns have a given number of light syllables; saṅkhyā, how many there are; adhvayoga, how much space the written table takes.

2. What is the difference between the lagakriyā and the Meru-prastāra?

The lagakriyā is the operation, the counting of patterns by their number of light syllables. The Meru-prastāra is the array that performs it, which Halāyudha says he sets out for the sake of the lagakriyā.

3. Why does Halāyudha omit adhvayoga, and is he right?

Because it is very slight and varies with the metre. He is right: it follows from saṅkhyā in one multiplication, it depends on the writing surface rather than on the mathematics, and nothing else uses its result.

4. Compute the written extent of the three-syllable prastāra in symbol widths, with gaps.

Eight rows of three symbols is 24, plus seven gaps, which is 31.

No machine. Every rule is executed by a trained person. The gap between an algorithm and a machine that runs it is most of the history of computing, and none of it is here.

No notion of cost. Not one of the six rules is accompanied by a statement that it is cheaper than the alternative. The saṅkhyā saving is real and unremarked. The costs in the table above are ours.

No base, and no arithmetic on patterns. The order agrees with binary counting, which is proved in [Binary Number Systems, and Exactly Where Piṅgala's Order Agrees], and the text nowhere treats a pattern as a number or adds two of them.

No generalisation. Saṅkhyā computes powers of two, not powers. The Meru counts light syllables in a two-symbol alphabet, not selections in general. The generalisations are immediate and the text does not make them.

No validation. No rule checks its input. Naṣṭa will return a pattern for a row that does not exist.

The claim this book does make

Stated once, carefully, because it is the sentence a good answer needs.

Piṅgala chose a representation in which the questions of his subject became decidable by arithmetic, and then stated the arithmetic as procedures. The representation is the two-valued syllable. The questions are enumeration, addressing and counting. The procedures are the six pratyayas. Every part of that sentence is a fact about the text, and the whole of it is what a computer scientist means by good design.

Worked example: the answer to a cross-module question

Q.3 of MU's paper draws on both modules. Here is the shape of an answer that uses this chapter, written at the length five marks allows.

Question. Relate Piṅgala's treatment of metre to the idea of a formal system as it appears elsewhere in this course.

Answer. Both Piṅgala and Pāṇini fix a finite alphabet, state rules over it, and provide for the case where a result is needed that has not been written out. Piṅgala's alphabet has two members and his rules generate and address the whole set of strings; Pāṇini's alphabet is the sounds of Sanskrit and his rules derive particular strings on demand. The difference is the interesting part: Piṅgala's space is complete and uniform, so arithmetic suffices to navigate it, whereas Pāṇini's target language is a proper subset of the strings his alphabet admits, so his system needs conditions, exceptions and a conflict policy that Piṅgala's has no occasion for. Nyāya, in Module II, supplies the third case, in which the rules are about admitting a claim rather than producing a string, and the enforcement is social rather than arithmetical.

That answer is four sentences and it touches three of the six syllabus areas. That is the register Q.3 is asking for.

Quick revision

• Six rules: prastāra generates; naṣṭa and uddiṣṭa index; saṅkhyā counts; lagakriyā counts by a property; adhvayoga measures.
• Five of the six never build the table. For the jagatī that is twelve operations against about 49,000.
• All six are definite and effective; the finiteness of each has a short argument; adhvayoga is the weakest because its rule is not stated in full.
• Not achieved: no machine, no statement of cost, no base or arithmetic on patterns, no generalisation, no validation.
• The claim that is true: he chose a representation that made his questions arithmetical, and then stated the arithmetic.

Test yourself

1. Which of the six pratyayas builds the table, and what follows for the rest?

Only the prastāra. The other five answer their questions without materialising the set, so they behave like an interface to a structure that is never stored.

2. Give the cost of each of naṣṭa, saṅkhyā and prastāra, for a twelve-syllable metre.

Naṣṭa is twelve steps. Saṅkhyā is five operations for n equal to twelve. The prastāra is 4096 rows of twelve symbols, about 49,000 symbol operations.

3. Name three things the text does not do, that a careless account of Piṅgala claims.

It never states that any rule is cheaper than an alternative; it never treats a pattern as a number or performs arithmetic on one; and it never generalises saṅkhyā beyond powers of two or the Meru beyond a two-symbol alphabet.

4. State the claim this book makes about Piṅgala in one sentence.

He chose a representation, the two-valued syllable, in which the questions of his subject became decidable by arithmetic, and then stated that arithmetic as a set of effective procedures.

The Gaṇapāṭha, lists of words grouped so that a rule can name a whole group by its first member.

The Uṇādisūtras, a supplementary set for words the main grammar does not derive.

The point for this paper is architectural. The rules are separated from the data they operate on, and the data is itself annotated. That is a separation a modern system makes too, and it is the reason the grammar can be as small as it is.

The translation this book quotes

Every Pāṇini quotation in this book comes from Srisa Chandra Vasu's English translation, published from Allahabad between 1891 and 1898, one volume per book of the grammar. Vasu died in 1918, so the translation is out of copyright and may be quoted with attribution.

What makes it the right source for this paper, rather than a modern study, is that it gives each sūtra in translation with a note on its type and its cross-references, which is exactly the material a chapter on rule architecture needs.

What the tradition means by correctness

This is worth stating because it is unusual and it bears on the comparison with formal grammars.

A form is correct if the rules derive it. Not if it is attested, and not if it sounds right. The grammar is the authority, which is why the tradition argues so hard about the rules themselves.

So the grammar is a specification of a language, in the strict sense. The set of strings it derives is the language. That is exactly the modern definition of a language generated by a grammar, and it is the basis of the comparison in [Context-Free Grammar, and Whether Pāṇini Wrote One].

And it has a boundary problem the modern definition also has. If the grammar derives a form nobody uses, is the grammar wrong or the usage incomplete? The commentaries take both positions in different places, and a modern grammar engineer meets the same question every week.

What this book does not claim about the text

Not a date. The estimates in the scholarly literature span several centuries and nothing here depends on one.

Not completeness. Whether the Aṣṭādhyāyī derives every form of the Sanskrit its author knew is a scholarly question with a long literature. This book quotes rules and does not adjudicate.

Not that the tradition's own analysis is superseded. The four precedence principles this book sets out are the tradition's, not ours. Where the tradition disputes a rule's reading, the dispute is reported.

Why MU's "Topics:" row is claimed here

MU's printed page leaves the bare word "Topics:" on a line of its own immediately above the four Pāṇini labels, as an artefact of her layout. It carries no subject matter. It is recorded in this book's contract so that the completeness check examines every row she printed rather than skipping one, and it is claimed here because this is the chapter that opens the block it introduces.

Quick revision

• Aṣṭādhyāyī: eight books, four quarters each, close to four thousand rules. A citation is book, quarter, position, as in 7.3.84.
• It is generative: the rules produce forms, and a form is correct if and only if the rules derive it.
• Three accompanying lists: the Dhātupāṭha of roots, the Gaṇapāṭha of word groups, the Uṇādisūtras. Roots in the Dhātupāṭha carry markers that change which rules apply.
• Rules are separated from annotated data, which is why the grammar is small.
• Quoted here from Srisa Chandra Vasu's English translation, Allahabad, 1891 to 1898, out of copyright.
• Correctness is derivability, which makes the grammar a specification of a language in the modern sense.

Test yourself

1. What does it mean to call the Aṣṭādhyāyī generative rather than descriptive?

It states rules that produce forms from roots and affixes, rather than cataloguing forms already collected. A form counts as correct if and only if the rules derive it.

2. Read the citation 6.1.77 and say what each number means.

The seventy-seventh sūtra of the first quarter of the sixth book. A citation is always book, then pāda, then position within the pāda.

3. Name the three lists that accompany the grammar and say why the separation matters.

The Dhātupāṭha of verbal roots, the Gaṇapāṭha of word groups, and the Uṇādisūtras. Separating annotated data from rules is what allows a rule to name a whole class in a few syllables, which is why the grammar can be as small as it is.

4. State the tradition's criterion of correctness, and one problem it creates.

A form is correct if the rules derive it. The problem is the boundary case: if the rules derive a form nobody uses, it is not settled whether the rules are wrong or the record of usage is incomplete, and the commentaries take both positions.

vidhi. Sūtra 7.3.84, in Vasu's translation: "when a sārvadhātuka or an ārdhadhātuka affix follows there is guṇa of the base." An operation with a condition and a result.

niyama. Vasu's own note on 7.3.84 is the clearest illustration available: the sūtra does not say what is gunated, "and to complete the sense, the word ikaḥ must be read into the sūtra", which restricts the operation to the ik vowels. The restriction is supplied by a paribhāṣā and has the effect of a niyama on the vidhi's scope.

adhikāra. Vasu's translation records governing rules by their effect: for instance a rule declaring that in the sūtras up to a stated one, a certain word is to be understood. From that point every following rule inherits the word without repeating it. The inheritance is cancelled where the range ends.

atideśa. A rule saying that a substitute is to be treated as the original for the purposes of other rules. Vasu discusses this at length under the term sthānivat, and it is exactly a case of extension by analogy: what is true of the original is asserted of its replacement.

Why a typed rule system is the interesting thing here

This is the argument to make in an answer, and it is stronger than any comparison with a particular modern formalism.

An untyped rule set cannot state a policy. If every rule is just "rewrite this as that", there is no way to say "a definition may never conflict with an operation", because nothing distinguishes the two.

A typed rule set can. Once rules have kinds, the tradition can and does say things like: a special rule sets aside a general one. That statement is about kinds, and it is the apavāda principle of [Rule Precedence: The Four Principles].

And the types are declared, not inferred. Vasu's list is given before the grammar starts. A reader knows what sort of thing each rule is, and the commentary says which for a rule that is disputed.

Worked example: five rules, one form

Deriving a single verb form touches five of the six kinds, which is why the classification is worth having.

The task. From the root meaning "to be", with a present-tense third person singular ending, produce the stem with the correct vowel.

saṃjñā. 1.1.1 and its neighbours give meanings to vṛddhi and guṇa, so that later rules can name the operation in one word.

adhikāra. A governing rule establishes the range of sūtras within which the operation being discussed is understood, so 7.3.84 need not restate it.

vidhi. 7.3.84 fires: a sārvadhātuka affix follows, so there is guṇa of the base.

paribhāṣā. 1.1.3 supplies the missing word: guṇa of the ik vowels of the base, not of anything else.

niṣedha, the prohibition, which the tradition treats as a species of niyama. 1.1.5 would block the operation if the affix carried an indicatory marker. Here it does not, so the operation stands.

Result. The stem's vowel is replaced by its guṇa. [Rule-Based Generative Structure] carries the derivation through, and [Pāṇini's Aṣṭādhyāyī as a Rule-Based Grammar Engine] implements exactly this chain.

What this classification is NOT

It is not Pāṇini's own list. The six kinds are the tradition's analysis of his rules, reported by Vasu. The sūtras themselves do not carry a label saying which kind they are, and for some rules the tradition disagrees.

It is not exhaustive in practice. The tradition uses further terms, niṣedha for a prohibition among them, and different commentators draw the lines differently.

It is not the same as a modern type system. Nothing checks the types. A rule that behaves like two kinds at once is handled by argument, not by a tool.

Quick revision

• Six kinds, from Vasu: saṃjñā a definition, paribhāṣā a key to interpretation, vidhi a general rule, niyama a restrictive rule, adhikāra a governing rule, atideśa extension by analogy.
• Only vidhi performs an operation. Five of the six manage rules.
• Modern counterparts: type declaration, meta-rule, production, constraint, lexical scope, inheritance.
• Instances read in Vasu: 1.1.1 saṃjñā; 1.1.3 paribhāṣā, and he says so; 7.3.84 vidhi; the sthānivat discussion for atideśa.
• The value of types: they let a policy be stated about rules, which is what the precedence principles are.
• The classification is the tradition's, not the text's; nothing checks it; commentators disagree on particular rules.

Test yourself

1. Name the six kinds of sūtra with a one-line gloss each.

Saṃjñā, a definition; paribhāṣā, a rule about how rules are read; vidhi, a general operation; niyama, a restriction on a rule's scope; adhikāra, a governing rule understood in those that follow; atideśa, the extension of a rule to an uncovered case by analogy.

2. Which kind performs an operation, and why does the answer matter?

Only vidhi. It matters because it shows that five of the six kinds exist to manage rules rather than to change forms, which is what a large rule system actually spends itself on.

3. Give a modern counterpart for adhikāra and for atideśa, and justify each.

Adhikāra is a lexical scope or an inherited attribute: something stated once is understood in every rule within a range until cancelled. Atideśa is inheritance or macro expansion: a case not covered is treated as if it were a covered one, so the covered rule's behaviour is reused.

4. Whose classification is this, and what follows for how you should cite it?

It is the tradition's analysis of Pāṇini's rules, reported in Vasu's introduction. So it should be cited as the tradition's classification, not as something the sūtras themselves declare, and an answer should note that commentators disagree about particular rules.

So: take a sound, take a marker that appears later, and the name denotes everything from that sound up to but not including that marker.

The two examples Vasu gives

Two characters each. "All the vowels" and "all the consonants", the two commonest conditions in any phonological rule, cost one syllable apiece.

And Vasu states the total: though numerous pratyāhāras could be formed, practically there are only 42 in use.

Worked example: building and decoding a name

Building. You want to say "any vowel other than a, i or u". Those three are aphorism 1, closed by the marker N. So the sounds you want begin after that marker, at r in aphorism 2, and run to the end of the vowels, which is closed by C at the end of aphorism 4. The name is therefore the first sound you want plus that marker: r plus C.

Decoding. Given a name, find its first character in the sequence and its second character among the markers; the name is everything between them. Given ik, the first sound is i in aphorism 1, and the marker K closes aphorism 2. So ik denotes i, u, r and l, which is exactly the set Vasu says sūtra 1.1.3 restricts guṇa and vṛddhi to: "the ik vowels only, i, u, ri, and li long and short".

That is the payoff. [Meta-Rules: Paribhāṣā, and Rules About Rules] is about a rule whose whole content is the two-character name ik, and now you can read it.

Why this is a compression scheme with a purpose

Three properties are worth naming, because each is a property a computer scientist would look for.

The name carries its own definition. No lookup table. Decoding requires only the ordered sequence, which is memorised once.

The ORDER is the design. Any set that is not a contiguous span cannot be named this way, so the order has to be chosen so that the needed sets are spans. That is the hard part, and it is what makes the fourteen aphorisms an achievement rather than a list.

The cost is paid once and the saving is paid out thousands of times. Fourteen aphorisms to memorise, against two characters instead of a list in each of thousands of rules.

The honest limits

Not every set is a span. Sets the grammar needs but cannot express as a span are handled by other means, and the tradition discusses them.

A marker used twice creates an ambiguity. Vasu notes exactly this: the same letter serves as marker in two of the aphorisms, so a name using it could denote two different spans, and the tradition has to say which.

The scheme says nothing about phonetics. The order is chosen for the grammar's convenience, not to reflect how sounds are made, and where the two pull apart the grammar wins.

And the transliteration in this book is not the sounds. The fourteen are printed above in plain letters so that a reader without Devanagari can follow the mechanism. The sounds themselves are Sanskrit phonemes and the printed forms are approximations; nothing in this paper depends on the phonetic detail.

Quick revision

• Fourteen aphorisms, called the Śivasūtras or Pratyāhāra Sūtras, order the sounds of Sanskrit. Vasu states the number.
• Each ends in a marker consonant that is not one of the sounds.
• Sūtra 1.1.71 ādir antyena sahetā: a name is the first sound plus a later marker, and denotes everything between them.
• Vasu's examples: ac is all the vowels, hal is all the consonants. He states that 42 pratyāhāras are in practical use.
• ik denotes i, u, r and l, which is the set sūtra 1.1.3 restricts guṇa and vṛddhi to.
• The design is the ORDER: a set can be named only if it is a contiguous span.
• Limits: not every set is a span; a marker reused creates an ambiguity Vasu notes; the order serves the grammar, not phonetics.

Test yourself

1. What is a pratyāhāra, and which sūtra states how one is formed?

A two-character abbreviation denoting a contiguous span of the ordered list of sounds, formed from the first sound of the span plus the marker consonant that closes it. Sūtra 1.1.71, ādir antyena sahetā.

2. Decode ac and hal, and say why they are the two most useful names in the grammar.

Ac runs from a to the marker C, so it is all the vowels. Hal runs from ha to the marker L, so it is all the consonants. Conditions of the form "before a vowel" and "after a consonant" are the commonest in any phonological rule, and each now costs two characters.

3. Why is the ORDER of the fourteen aphorisms the real achievement?

Because a set can be named only if its members are contiguous in the order. Choosing an order in which every set the grammar needs happens to be a span is the difficult part; naming a span is trivial once it is.

4. Give one limitation of the scheme that the tradition itself notes.

The same marker letter serves in two different aphorisms, so a name formed with it could denote either of two spans, and the tradition has to state which is meant.

So the marker is invisible in the output and decisive in the derivation. That is a type annotation. The affix has a type, the rule is guarded on the type, and the type is erased before anything is produced.

The rule that reads the marker

Sūtra 1.1.5, whose number is confirmed in both of this book's witnesses. Its effect, as Vasu states it, is the one quoted above: a marked affix causes neither guṇa nor vṛddhi.

Two things about that rule are worth noticing.

It is a prohibition, not an operation. It changes nothing; it prevents something. In the six-kind classification of [The Six Kinds of Sūtra, in Vasu's Own Words] that is a niṣedha, which the tradition treats as a species of restrictive rule.

It is stated once for all marked affixes. Not once per affix. That is the saving, and it is the reason the annotation exists.

The comparison, stated as a table

The row that matters most is the third. Both are erased. An annotation that survived into the output would be part of the thing annotated, and neither is.

Worked example, worked twice

Take a root ending in a light vowel, and two affixes that are identical in their letters but differ in their markers.

Affix without a marker. 7.3.84's condition is met. 1.1.3 says the operation applies to the root's ik vowel. The vowel is replaced by its guṇa. The form changes.

Affix with a marker. 7.3.84's condition is met just as before. 1.1.5 prohibits the operation. The vowel is untouched. The form does not change.

Same rule, same root, same visible affix, two results. The only difference is a letter that never appears. [Pāṇini's Aṣṭādhyāyī as a Rule-Based Grammar Engine] implements exactly this pair, and its test cases include both.

What an anubandha is NOT

It is not a sound. It is not pronounced and it is not part of the phonetics.

It is not arbitrary. Vasu's translation records which markers carry which effects, and the tradition documents the system. A marker is a name in a fixed vocabulary.

It is not the same as an affix's meaning. Two affixes with the same meaning may carry different markers because they behave differently under other rules. The marker is about rule applicability, not about semantics.

It is not checked. Nothing verifies that a root's markers are right. If a list is wrong the grammar derives wrong forms, and the only way to notice is that the output is wrong. That is the honest difference from a type system, which rejects the program.

Quick revision

• An anubandha or it is an indicatory letter on a root, affix or substitute, deleted before the form is used, which controls which rules apply.
• Vasu's example: an affix that satisfies 7.3.84's condition still does not cause guṇa, because of its marker, and he gives "the real terminations" without it.
• The rule that reads the marker is 1.1.5, a prohibition rather than an operation, stated once for all marked affixes.
• It is a type annotation: attached to data, read by rules, erased before output.
• Unlike a type system, nothing checks it. A wrong marker gives a wrong word and no error.

Test yourself

1. Define anubandha and give the three stages of its life.

An indicatory letter attached to a form in the grammar's lists. It is placed on the form in the list, read as a condition by rules, and deleted before the form appears in a word.

2. Reconstruct Vasu's example of a marker blocking a rule.

A past participle termination is an ārdhadhātuka affix, so the general rule 7.3.84 would cause guṇa of the base. Because the termination carries an indicatory letter, 1.1.5 prohibits the operation, and the root's ik vowel is not gunated. The real termination, Vasu says, is the form without the marker.

3. In what precise sense is an anubandha a type annotation?

It is attached to data rather than to an operation, it is consulted to decide which operations are permitted, and it is erased before anything is produced.

4. Give the one important respect in which it is weaker than a type system.

Nothing checks it. A wrongly marked root produces a wrong word silently, whereas a type checker rejects an ill-typed program before it runs.

Say this plainly, because it matters. The engine in [Pāṇini's Aṣṭādhyāyī as a Rule-Based Grammar Engine] carries the derivation as far as the guṇa substitution and stops. The remaining step is a real rule in the grammar and the book cites it by number; it is not implemented, and calling the engine's output a Sanskrit word would be false. What the engine demonstrates is rule-based derivation with conditions, meta-rules and precedence, which is what the syllabus asks for.

The same derivation as a table

A second derivation, in which a rule does not fire

The value of a rule system is visible when a rule declines.

The task. The same root with a past participle termination.

Stage one and two. The root bhu, and a termination that is ārdhadhātuka.

Stage three, the rule that would fire. 7.3.84's condition is satisfied: an ārdhadhātuka affix follows.

Stage four, the rule that stops it. The termination carries an indicatory marker, and by 1.1.5 a marked affix causes neither guṇa nor vṛddhi. So the root's vowel is untouched.

The form. The root's vowel stays as it is, and the derivation continues with other rules.

Two derivations, the same general rule, opposite outcomes, and the deciding factor is a letter that never appears in either word. That is what [Anubandha: The Marker Letter as a Type Tag] is about, and this is the derivation it produces.

What makes this generative rather than descriptive

Three properties, and all three are testable claims about the grammar.

The output is produced, not selected. No list of verb forms exists anywhere in the system. The forms are what the rules make.

The rules are general. 7.3.84 is one rule and it applies to every root ending in an ik vowel before every affix of the two named kinds. A descriptive grammar would have a paradigm per root.

The exceptions are rules too. 1.1.5 is not a footnote; it is a rule of the same kind, in the same numbering, and it interacts with the others by the same precedence principles. [Rule Precedence: The Four Principles] is about those principles.

What a derivation is NOT

It is not a sequence you may reorder. Which rule fires when is decided by the precedence principles, not by the writer's convenience. Reordering can produce a different and wrong form.

It is not a proof that the form is attested. The tradition's criterion is derivability, as [Pāṇini's Aṣṭādhyāyī, and the Text We Are Reading] says. A derivation shows the grammar produces the form; whether anybody says it is a separate question.

It is not unique. Two different chains of rules can reach the same form, and the tradition argues about which is correct. That is not a defect peculiar to Sanskrit: any rewrite system with overlapping rules has the same property, and [Rewrite Systems] treats it under the name confluence.

Quick revision

• Five stages: root from the Dhātupāṭha, affix from the meaning, class sign, operations, finished form.
• The worked derivation: bhu plus ti, class sign by 3.1.68, guṇa by 7.3.84 scoped by 1.1.3 giving bho, then 6.1.78 giving bhavati.
• This book's engine performs the guṇa step and stops. 6.1.78 is cited and not implemented, and the book says so.
• The same rule declines on a marked affix, by 1.1.5, so two derivations with the same general rule end differently.
• Generative means: output produced not selected, rules general, exceptions stated as rules of the same kind.
• A derivation is not reorderable at will, not evidence of usage, and not necessarily unique.

Test yourself

1. Give the five stages of a derivation in the Aṣṭādhyāyī.

The root from the Dhātupāṭha; the affix the meaning requires; any class sign those affixes bring; the operations that the form's condition now triggers; and the finished form when no rule applies.

2. Work the guṇa step for the root bhu with a third person singular present ending, citing the rules.

Sūtra 3.1.68 supplies the class sign. Sūtra 7.3.84 provides that a sārvadhātuka affix causes guṇa of the base, and 1.1.3 restricts the operation to the ik vowels, so the root's u becomes o, giving bho plus the following elements.

3. Which rule finishes the derivation, and why does this book not implement it?

Sūtra 6.1.78, which turns the vowel class o belongs to into a semivowel sequence before a vowel, giving bhavati. The book's engine stops at the guṇa step and cites 6.1.78 rather than implementing it, so that nothing claims to produce a finished Sanskrit word that it does not produce.

4. Show how the same general rule can give two different outcomes.

With an unmarked ārdhadhātuka affix, 7.3.84 fires and the root's ik vowel takes guṇa. With an affix carrying an indicatory marker, the condition of 7.3.84 is still met but 1.1.5 prohibits the operation, so the vowel is untouched.

The result is a complete rule. And the completion is not a guess; it is the effect of a rule whose whole job is to complete such rules.

So 7.3.84 is not an incomplete rule. It is a complete rule read together with its meta-rule, and the grammar is designed to be read that way.

The modern counterparts

The last row is the one worth dwelling on, because it is the most sophisticated. 1.1.3's own wording makes it yield to a special rule. A default that knows it can be overridden is a designed default, not an accident.

Three paribhāṣā this book uses

Each is cited elsewhere in the book and collected here so the kind is visible as a kind.

1.1.3, iko guṇavṛddhī. Supplies the missing argument to every rule enjoining guṇa or vṛddhi. Used in [Rule-Based Generative Structure] and implemented in [Pāṇini's Aṣṭādhyāyī as a Rule-Based Grammar Engine].

1.4.2, vipratiṣedhe paraṃ kāryam. When two rules of equal standing conflict, the later prevails. [Vipratiṣedha: When Two Rules Collide, the Later Wins].

8.2.1, pūrvatrāsiddham. Everything in the last three quarters of book eight is treated as not having taken effect, so far as the earlier rules are concerned. [Asiddhatva and the Tripādī: Ordering by Blocking].

Notice what the three have in common. None of them mentions a sound, a root or an affix. They are entirely about rules, and the grammar would not work without them.

Worked example: the effect of removing a meta-rule

This is the best way to see what a meta-rule is doing: take it away.

With 1.1.3 in force. 7.3.84 gunates the ik vowel of the base. A base ending in a is untouched, because a is not an ik vowel.

Without 1.1.3. 7.3.84 says guṇa of the base and nothing restricts what. The rule would have to be read as gunating something unspecified, which is either meaningless or would have to be filled by guesswork, and the tradition's whole objection to that is why the paribhāṣā exists.

What would have to change if the meta-rule did not exist. Every rule enjoining guṇa or vṛddhi would have to name the ik vowels itself. Vasu notes that guṇa is enjoined in rules like 7.3.82 as well as 7.3.84, and there are many more. One meta-rule against a phrase repeated in dozens of rules is the trade, and it is the same trade a programmer makes with a default.

What a paribhāṣā is NOT

It is not a comment. It is a rule, numbered in the same sequence, and its effects are part of the grammar's output.

It is not always in book one. Paribhāṣā are scattered, and 8.2.1 is at the head of the last three quarters. Their position matters because some of them have scope limited by position.

It is not beyond dispute. Which rules are paribhāṣā, and exactly how far each reaches, is argued in the commentary literature. Vasu labels 1.1.3 and the tradition agrees about that one; others are contested.

Quick revision

• A paribhāṣā is a rule about rules. It performs no operation on a form.
• 1.1.3 is labelled a paribhāṣā by Vasu himself, and it supplies the missing word ikaḥ to every rule enjoining guṇa or vṛddhi.
• Vasu shows it completing 7.3.84: "to complete the sense, the word ikaḥ must be read into the sūtra."
• Its wording is defeasible: "in the absence of any special rule", which is a precedence statement inside a meta-rule.
• Three used in this book: 1.1.3 supplying an argument, 1.4.2 resolving a conflict, 8.2.1 imposing an order.
• None of the three mentions a sound, a root or an affix.
• Modern counterparts: default arguments, the semantics section of a language definition, a precedence table, an overridable default.

Test yourself

1. Define paribhāṣā and say how it differs from a vidhi rule.

A paribhāṣā is an interpretive rule governing how other rules are read or applied. A vidhi states an operation on a form. The paribhāṣā changes nothing in a word; it changes what the vidhi rules mean.

2. Quote or paraphrase Vasu's demonstration of 1.1.3 completing 7.3.84.

He says that 7.3.84 declares guṇa of the base when a sārvadhātuka or ārdhadhātuka affix follows, that the expression to be gunated is not specified, and that to complete the sense the word ikaḥ must be read into the sūtra, giving guṇa of the ik vowels of the base.

3. What does "in the absence of any special rule" in 1.1.3 tell you about the grammar's design?

That the default is deliberately overridable: a meta-rule states its own defeasibility, so a special rule can displace it without the grammar becoming inconsistent.

4. Name three paribhāṣā and what each governs.

1.1.3, which supplies the unstated argument to rules enjoining guṇa or vṛddhi; 1.4.2, which makes the later of two conflicting rules prevail; and 8.2.1, which makes the last three quarters of book eight non-existent for the rules before them.

The maxim, in Vasu's own words, and it appears in two of his volumes in the same wording:

That which is bahiraṅga is regarded as not having taken effect, or as not existing, when that which is antaraṅga is to take effect.

Notice the form of the statement. It does not say the inner rule is applied first. It says the outer rule is treated as not having happened while the inner rule is under consideration. That is stronger and it is more useful, because it makes the inner rule's condition evaluate against the form as it was.

Modern counterpart. Evaluating the inner expression before the outer, and more precisely, a scoping rule: what is visible to the inner rule is the state before the outer one ran.

Four: paratva, the later rule wins

If none of the three above separates them, the rule that stands later in the text prevails. This is sūtra 1.4.2, vipratiṣedhe paraṃ kāryam, and it is the subject of [Vipratiṣedha: When Two Rules Collide, the Later Wins].

Why it comes last. It is arbitrary. Position in the text is not a reason in the way specificity and scope are; it is a tie-break, and a tie-break is for when reasons run out.

The order, as a table

Worked example: the four tested in turn

Take two applicable rules, A and B, and walk the principles.

Is either special? If A's condition is "before any affix of kind K" and B's is "before affixes of kind K that carry marker M", then B is special and B wins. Stop.

If neither is special, is either nitya? If A would still apply after B had operated, but B would not still apply after A, then A can wait and B cannot, so B goes first. Stop.

If neither, is either inner? If A's condition involves only the root and B's involves the ending as well, A is antaraṅga and B is treated as not having taken effect. A wins. Stop.

If neither, compare positions. By 1.4.2 the later rule prevails.

The program in [Śāstra Rule Precedence as a Deterministic Finite Rewrite System] implements exactly this cascade and reports which principle decided, and its test cases include one for each of the four.

What the four principles do NOT give you

They do not always agree with each other. Two principles can point different ways, which is precisely why the order exists. The order is the tradition's answer, and the commentaries argue about particular cases.

They do not make the system provably consistent. Nothing shows that every possible conflict is resolved, or that the resolutions never produce a wrong form. The tradition's evidence is that the grammar derives the right forms, which is testing rather than proof.

They are not all in the text. Only paratva is a sūtra. Apavāda, nitya and antaraṅga are maxims of the tradition, transmitted as paribhāṣā in separate collections, and Vasu quotes the antaraṅga one as a maxim rather than as a numbered rule. An answer should say which are sūtras and which are maxims.

Quick revision

• Four principles, in order: apavāda, nitya, antaraṅga, paratva.
• Apavāda first because a special rule exists only to displace the general one.
• Nitya second because a rule that would still apply later can wait.
• Antaraṅga third, and its maxim treats the outer rule as not having taken effect, not merely as later.
• Paratva last, sūtra 1.4.2, because position in the text is arbitrary and a tie-break is for when reasons run out.
• Only paratva is a numbered sūtra; the other three are maxims of the tradition.

Test yourself

1. Name the four precedence principles in order and give the test for each.

Apavāda: is one rule's condition a subset of the other's? Nitya: would one still apply after the other, but not conversely? Antaraṅga: are one rule's conditions closer to the stem? Paratva: which rule stands later in the text?

2. Why is 1.4.2 applied last rather than first?

Because position in the text is arbitrary. Specificity, unconditional applicability and scope are reasons; position is only a tie-break, so it is used when the reasons run out.

3. Quote the antaraṅga maxim and say what is unusual about its wording.

That which is bahiraṅga is regarded as not having taken effect, or as not existing, when that which is antaraṅga is to take effect. It does not merely order the two rules: it makes the outer rule count as not having happened, so the inner rule's condition is evaluated against the earlier state.

4. Which of the four is a numbered sūtra, and why does the distinction matter?

Only paratva, sūtra 1.4.2. The distinction matters because the other three are maxims transmitted by the tradition rather than rules of the text, so their authority and their exact scope are matters the commentaries argue about.

A tool for the author. Because position decides, the author can express a preference by placing a rule later. That converts an editorial act into a semantic one, and Pāṇini uses it: a rule placed later is a rule intended to win.

What it costs

It makes position semantic. You can no longer move a rule for the sake of tidiness. Every rule's position is part of its meaning, and reorganising the grammar would change what it derives.

It makes insertion dangerous. Adding a rule changes its relation to every rule after it. The commentaries' anxiety about interpolated rules is exactly this.

It hides the reason. When a special rule wins, you know why: it is special. When the later rule wins, the only reason available is "it is later", which tells a reader nothing about the grammar's intent.

Modern parallel. A stylesheet in which later declarations win, or a configuration system in which the last file read overrides the earlier ones. Both are total and cheap, both make file order semantic, and both are notorious for the same two problems: you cannot reorder safely and you cannot tell from a rule why it lost.

Worked example: two rules, resolved twice

The pair. Two sandhi rules in the same quarter of book six, one at position 77 and one at position 78, which prescribe different treatments of the same vowel before a following vowel.

Applying 1.4.2 directly. 6.1.78 is later, so 6.1.78 prevails.

But check the earlier principles first. Is either special? If one applies to vowels of a class that is a subset of the other's, it is special, and it wins whichever position it holds. Vasu's discussion of exactly this neighbourhood turns on such considerations, and the honest report is that the pair's resolution is argued in the commentary rather than settled by position alone.

The lesson. 1.4.2 gives an answer whenever it is reached. The work is in knowing whether it has been reached, and a student who applies it first will be confidently wrong.

What 1.4.2 is NOT

It is not a general principle that later beats earlier. It applies to conflicts, and only to conflicts the other three principles do not resolve.

It is not about which rule was composed later. It is about position in the text as transmitted.

It does not govern the tripādī. There, 8.2.1's asiddhatva applies, and within the tripādī a later rule is treated as not having taken effect for an earlier one, which is the reverse of 1.4.2's effect.

It is not a claim about the grammar's consistency. It resolves conflicts; it does not show that resolving them always gives the right form.

Quick revision

• 1.4.2 vipratiṣedhe paraṃ kāryam: in a conflict, the later rule's operation is performed.
• A conflict means both apply, they prescribe different results, and none of the other three principles separates them.
• Later means later by book, quarter, position.
• It buys totality, cheapness, and a way for the author to express a preference by placement.
• It costs: position becomes semantic, insertion becomes dangerous, and the reason a rule lost is uninformative.
• Modern parallel: last declaration wins, as in a stylesheet or a layered configuration.
• It does not govern the tripādī, where 8.2.1's asiddhatva reverses the effect.

Test yourself

1. State 1.4.2 and the three conditions under which it is reached.

In a conflict, the operation of the later rule is performed. It is reached when both rules apply to the same form, they prescribe different results, and neither speciality, nor nitya status, nor scope separates them.

2. Give one advantage and one disadvantage of a positional tie-break.

Advantage: it is total and cheap, since any two rules have an order, so every conflict has an answer reached by comparing two addresses. Disadvantage: position becomes part of a rule's meaning, so the grammar cannot be reorganised or extended safely.

3. Order these by 1.4.2: 6.4.22, 7.3.84, 6.1.78.

6.1.78, then 6.4.22, then 7.3.84. Later quarter beats earlier quarter within a book, and a later book beats an earlier one.

4. Why is applying 1.4.2 first a mistake?

Because three principles precede it, and each of them can point the other way. A special, nitya or antaraṅga rule wins regardless of its position, so a student who compares positions first will reach the wrong result whenever one of those applies.

Worked example: reading a rule's context

Take 7.3.84, whose translation Vasu gives as: when a sārvadhātuka or an ārdhadhātuka affix follows there is guṇa of the base.

The affix is named in the locative. So by 1.1.66 the operation applies to what precedes the affix, which is the base. That is where the words "of the base" in Vasu's English come from: they are the effect of the case ending plus the meta-rule.

Guṇa is the operation, and what it replaces is supplied by 1.1.3, as [Meta-Rules: Paribhāṣā, and Rules About Rules] shows.

So the rule's four parts are: operand, the base's ik vowel; result, its guṇa; context, a following affix of two named kinds; and the context's direction, given by a case ending read through a meta-rule.

Nothing in the rule says the word "before" or "after". The case ending says it. That is the economy.

The formal meaning of context-sensitive

The phrase has a precise meaning in formal language theory and it is not the same as the informal one. It is worth having both.

A context-free rule has exactly one symbol on its left-hand side. It says: wherever you see this one symbol, you may replace it, no matter what surrounds it.

A context-sensitive rule has more than one symbol on its left-hand side, so the surroundings are part of what must match.

Here A becomes b, but only between x and y, and the x and y are unchanged. The rule cannot be split into a context-free one without losing the condition.

The consequence, which is the important part. Context-sensitive grammars generate strictly more languages than context-free ones. So the question "is the Aṣṭādhyāyī context-free?" is a real question with real stakes, and [Context-Free Grammar, and Whether Pāṇini Wrote One] answers it.

Where the Aṣṭādhyāyī is context-free and where it is not

Some rules are context-free in the formal sense. A rule that introduces an affix because the meaning requires it names no environment; it just adds material.

Most operational rules are not. 7.3.84 requires a following affix of a particular kind, which is context. Written as a rewrite rule its left-hand side has to mention both the vowel and the affix, so it has more than one symbol.

And some rules are worse than context-sensitive in the formal sense. A rule whose condition refers to a marker that has already been deleted, or to whether another rule has fired, is not a rewrite rule over strings at all. The asiddhatva mechanism of [Asiddhatva and the Tripādī: Ordering by Blocking] is exactly that, and it is why the formal classification of the whole grammar is not a simple matter.

The honest summary. The Aṣṭādhyāyī is a rule system with contexts, and the formal hierarchy is a tool for comparing it with modern grammars rather than a box it fits into. An answer that says so is better than one that picks a class.

What context-sensitivity is NOT

It is not the same as having exceptions. An exception is another rule. A context is a condition inside one rule.

It is not the same as ambiguity. A context makes a rule narrower, and narrower rules make a grammar more determinate, not less.

It is not expensive by itself. Checking a context costs a look at the neighbours. What is expensive is deciding which of several context-sensitive rules applies, which is why the precedence principles exist.

Quick revision

• Nearly every rule is a triple: what is changed, what it becomes, and where.
• Pāṇini states the "where" with a case ending. 1.1.66: a locative means the operation applies to what precedes. 1.1.67: an ablative means it applies to what follows.
• 1.1.49 ṣaṣṭhī sthāneyogā: a genitive means "in the place of", so "of X" is a substitution for X.
• Formally, a context-free rule has one symbol on its left; a context-sensitive rule has more, so the surroundings must match and are preserved.
• Context-sensitive grammars generate strictly more languages than context-free ones.
• The Aṣṭādhyāyī has context-free rules, many context-sensitive ones, and mechanisms that are not string rewriting at all.

Test yourself

1. How does a rule of the Aṣṭādhyāyī say where an operation applies?

By the case ending of the word naming the neighbouring item. By 1.1.66 a locative means the operation applies to what precedes it; by 1.1.67 an ablative means it applies to what follows.

2. What does a genitive in a rule mean, and which sūtra says so?

It means "in the place of", so the item named in the genitive is what is replaced. Sūtra 1.1.49, ṣaṣṭhī sthāneyogā.

3. Give the formal definition of a context-sensitive rule and one example.

A rule whose left-hand side has more than one symbol, so that the surrounding material must match and is preserved. For example x A y rewrites to x b y, which replaces A by b only between x and y.

4. Why is "is the Aṣṭādhyāyī context-free?" a question with stakes?

Because context-sensitive grammars generate strictly more languages than context-free ones, so the answer says something about what kind of system the grammar is, and about whether a context-free formalism could express it.

8.2.1 removes the question. Phase-one rules always see the form before any phase-two rule has touched it. Their conditions are therefore stable, and a reader can reason about phase one without knowing anything about phase two.

That is a real engineering benefit and it has a modern name.

The modern name: phase ordering

A multi-pass compiler makes exactly this choice. Constant folding does not need to know what the register allocator will do, because the allocator runs later and the folder is finished. The benefit is the same: each pass can be reasoned about in isolation.

Worked example, from Vasu's own discussion

He gives the mechanism at work, and the example is worth following because it shows why the rule is needed rather than merely stating it.

He is discussing a case in which a final consonant could be elided by either of two rules of the tripādī, at 8.2.7 and at 8.2.23. His report is that the form could not have had its final elided by 8.2.7 if the elision by 8.2.23 had taken effect, and that therefore, because within the last three quarters a subsequent rule is as if it had not taken effect so far as a preceding rule is concerned, 8.2.23 is treated as not having operated and 8.2.7 finds its scope.

Read what that does. The earlier rule of the tripādī gets to operate on the form as it stands, without having to know that a later rule of the tripādī would have changed the very thing its condition depends on. The blocking is what makes the earlier rule usable.

The one that is not 8.2.1: the ābhīya section

The grammar has a second, narrower asiddhatva, and a complete answer mentions it.

Sūtra 6.4.22, confirmed in the digital sūtrapāṭha, establishes a section within which, as Vasu puts it, when one of the rules of the section is to be brought into operation having the same place of operation as another of the section which has already taken effect, the one that has taken effect is regarded as not having taken effect.

So the same device is used twice, at two scales. Once for the whole tripādī, and once for a smaller neighbourhood within book six. That is a designed mechanism rather than a one-off patch, and pointing that out is the strongest form of the claim.

What asiddhatva is NOT

It is not deletion. The later rule does still operate. It is invisible to the earlier rules, not absent.

It is not the same as the antaraṅga maxim. That maxim also uses the words "not having taken effect", and Vasu quotes it that way, but it compares two rules by the closeness of their conditions, not by their section. Two mechanisms, similar wording, different tests.

It is not a general principle of the grammar. It is declared for two specific sections. Outside them, 1.4.2 and the other precedence principles apply.

It is not a proof of consistency. It makes the phases independent; it does not show that the resulting derivations are all correct.

Quick revision

• 8.2.1 pūrvatrāsiddham: the last three quarters of book eight, the tripādī, are asiddha for every preceding rule, and inside the tripādī a later rule is asiddha for an earlier one.
• Asiddha means treated as not having taken effect; Vasu glosses it as not-accomplished.
• Effect: two phases, with phase one blind to phase two, so phase-one conditions are stable.
• The modern counterpart is a compiler pass boundary, declared rather than inferred.
• Inside the tripādī the internal rule reverses 1.4.2's effect, which is a different mechanism for a different section.
• A second, narrower asiddhatva is established by 6.4.22 for a section of book six.
• It is not deletion, not the antaraṅga maxim, and not a general principle.

Test yourself

1. State 8.2.1 and both of its provisions.

The rules of the last three quarters of book eight are treated as not having taken effect with respect to all preceding rules; and within those three quarters a later rule is treated as not having taken effect with respect to an earlier one.

2. Why does a grammar benefit from making one section invisible to another?

Because a rule's condition then does not depend on whether a rule from the other section has already run. The conditions of the earlier section are stable, so it can be reasoned about without knowing anything about the later one.

3. Give the modern counterpart of asiddhatva and one property they share.

A compiler pass boundary. Both make each pass or phase operate only on what the previous one produced, so each can be reasoned about in isolation, and in both the boundary is declared rather than discovered.

4. How does the tripādī's internal rule relate to 1.4.2, and why is that not a contradiction?

Under 1.4.2 the later of two conflicting rules prevails. Inside the tripādī an earlier rule proceeds as though the later one had not taken effect, which is the opposite effect. It is not a contradiction because 8.2.1 declares a different mechanism for that section, and 1.4.2 governs elsewhere.

What each mechanism costs

An answer asked to assess should be able to say what the price of each is.

Apavāda requires knowing that one condition is a subset of the other, which is a judgement about content. Two rules can each look narrower in a different respect, and the commentaries argue about such cases.

Nitya requires reasoning about counterfactuals: would this rule still apply after the other had operated? That is harder than it sounds and the tradition disputes particular instances.

Antaraṅga requires a notion of "closer to the stem" that the grammar does not define formally. It is applied by trained judgement.

Paratva requires only a comparison of addresses, and costs nothing. Its price is paid elsewhere: position becomes semantic, as [Vipratiṣedha: When Two Rules Collide, the Later Wins] sets out.

Niṣedha costs nothing to apply and costs a rule to state. Each prohibition is another rule to transmit.

Asiddhatva costs nothing to apply and costs expressiveness: a phase-one rule cannot make use of a phase-two result even when it would be convenient.

The pattern is worth naming. The cheap mechanisms are the arbitrary ones, and the principled mechanisms are the expensive ones. That is true of modern conflict resolution too: a specificity rule is more informative and harder to compute than a "last one wins" rule.

Worked example: a conflict resolved at each level

The same pair of candidate operations, resolved four different ways depending on what is true of them.

If a prohibition applies. One operation is forbidden outright. One candidate remains. No conflict.

If the two rules are in different phases. The earlier rule operates on the form as it stands, blind to the later one. No conflict.

If one is special. The special rule operates and the general one does not apply here at all.

If none of that holds. Compare positions. The later rule operates, and the only reason available is its position.

What is NOT a conflict resolution mechanism

Two rules that do compatible things. If one lengthens a vowel and the other adds an affix, both happen. There is no conflict and no mechanism is needed.

An exception stated in the same rule. A rule with a clause excluding a case has narrowed its own condition. Nothing has to be resolved.

The commentaries' arguments. Where the tradition disputes which principle applies, that is a disagreement about the mechanisms, not a further mechanism.

Quick revision

• Six mechanisms, three kinds: decide between the rules, forbid one of them, or arrange that they never meet.
• Precedence, in order: apavāda, nitya, antaraṅga, paratva.
• Prohibition: niṣedha rules such as 1.1.5, which remove a candidate.
• Phase ordering: asiddhatva, sūtras 8.2.1 and 6.4.22, which makes one section invisible to another.
• Checked first: asiddhatva structurally, then prohibition, then the four principles in order.
• Only paratva, 1.4.2, and the prohibitions are numbered sūtras. Apavāda, nitya and antaraṅga are maxims.
• Cheap mechanisms are arbitrary; principled ones are expensive. That trade is not peculiar to Sanskrit.

Test yourself

1. Name the six conflict resolution mechanisms and group them by kind.

Precedence: apavāda, nitya, antaraṅga, paratva. Prohibition: niṣedha. Phase ordering: asiddhatva. The first four decide between rules, the fifth removes a candidate, the sixth prevents the conflict arising.

2. In what order are they tried, and why is asiddhatva first?

Asiddhatva, then prohibition, then the four principles in their own order. Asiddhatva is first because it is structural: if the two rules are in different phases, the earlier one cannot see the later one's result, so there is no conflict to resolve.

3. Which of the mechanisms are numbered sūtras?

Paratva, which is 1.4.2; the prohibitions, such as 1.1.5; and asiddhatva, which is 8.2.1 and 6.4.22. Apavāda, nitya and antaraṅga are maxims of the tradition rather than rules of the text.

4. Explain the trade-off between apavāda and paratva.

Apavāda is principled but expensive: it needs a judgement about whether one condition is a subset of another, and the commentaries dispute such judgements. Paratva is cheap but arbitrary: it needs only a comparison of two addresses, and it tells you nothing about why a rule lost.

derivations found: 20
distinct strings : 20
by arithmetic    : 2 subjects x 2 verbs x (1 + 2 + 2) = 20

  rama calls
  rama calls rama
  rama calls rama quickly
  rama calls sita
  rama calls sita quickly
  rama sees
  rama sees rama
  rama sees rama quickly
  rama sees sita
  rama sees sita quickly
  sita calls
  sita calls rama
  sita calls rama quickly
  sita calls sita
  sita calls sita quickly
  sita sees
  sita sees rama
  sita sees rama quickly
  sita sees sita
  sita sees sita quickly

Reading the three numbers the program prints

They are three independent statements about the same grammar, and the chapter prints all three because agreement between independent routes is the only evidence worth having.

Derivations found: 20. The enumeration walked every alternative of every rule and produced twenty results.

Distinct strings: 20. No two derivations produced the same string, so this grammar is unambiguous over its own output. A grammar in which those two numbers differed would be ambiguous, and that is a property worth being able to detect rather than assume.

By arithmetic: 20. Two choices of subject, two of verb, and five shapes of verb phrase, namely the bare verb, verb with either object, and verb with either object plus the adverb.

Three routes, one answer. If the arithmetic had disagreed with the count, the arithmetic would be the thing to doubt, and saying so is a habit worth having before you write the internal assessment.

The vocabulary a question will use

What a formal grammar is NOT

It is not a description of meaning. Nothing in the four parts says what a string means. "Sita calls rama quickly" is in the language and so is any other combination the rules allow, whether or not it makes sense.

It is not a parser. The grammar says which strings are in the language. Finding out whether a given string is, and how, is parsing, and [Parsing Algorithms] is about that.

It is not unique to its language. Many different grammars generate the same set of strings, and they can differ enormously in how easy they are to parse.

Quick revision

• Four parts: terminals, non-terminals, productions, start symbol.
• The language generated is the set of terminal strings derivable from the start symbol, and derivability is the whole criterion.
• A derivation is a sequence of sentential forms from the start symbol to a string of terminals.
• The small grammar above generates 20 strings by three independent routes: the enumeration's length, the count of distinct results, and the arithmetic. Equal counts of derivations and of distinct strings means the grammar is unambiguous over its output.
• Grammar is not meaning, not a parser, and not unique to the language it generates.

Test yourself

1. Give the four components of a formal grammar and say what makes a string a member of its language.

A finite set of terminals, a disjoint finite set of non-terminals, a finite set of productions each with at least one non-terminal on the left, and a start symbol. A terminal string is in the language if and only if there is a finite derivation of it from the start symbol.

2. How many strings does the grammar above generate, and how do you know?

Twenty. Three independent routes agree: the enumeration produced twenty derivations, those derivations gave twenty distinct strings, and the arithmetic is two subjects times two verbs times five verb-phrase shapes.

3. What is the difference between a grammar and a parser?

The grammar defines which strings are in the language. A parser decides, for a given string, whether it is in the language and by what derivation.

4. Why can two grammars be different and yet define the same language?

Because membership depends only on which terminal strings are derivable, not on the route. Different sets of productions can make the same set of strings derivable while differing in structure and in how easily they can be parsed.

A context-free production cannot express that at all. Its condition is a symbol; it has no way to say "provided rule R has not fired". This is not a matter of degree: the mechanism is outside the formalism.

Three: the objects are not non-terminals

A context-free grammar rewrites category names. Pāṇini's rules operate on sounds, on roots, on affixes and on markers, and the markers are deleted before the output. There is no level at which a Pāṇinian rule expands a category into its parts in the way "VP rewrites to V NP" does.

What Pāṇini has instead is a derivation that starts from a root and an affix and transforms them. That is a rewriting system over strings with side conditions, which is a different kind of object from a phrase-structure grammar.

The comparison, as a table

What Pāṇini's system IS, said positively

Refusing a classification is only half an answer. The positive statement is this.

It is a rewriting system with a fixed application strategy. Rules transform strings; the strategy is the precedence order; the strategy is what makes the system deterministic. [Rewrite Systems] gives the vocabulary and [Śāstra Rule Precedence as a Deterministic Finite Rewrite System] builds one.

Its nearest modern relatives are not phrase-structure grammars. They are two-level morphology and finite-state transducers, which likewise transform a form into a form with contexts and ordered rules, and which are the standard tools in computational morphology. [Foundations of NLP, and What Pāṇinian Grammar Contributed] takes that up.

What MU's own outcome asks, and how to answer it

Her OC 3 is: model and compare Pāṇini's generative grammar with modern formal grammars and parsing systems. A five-mark answer has four moves and they fit in about a hundred and thirty words.

Answer. Both are generative: a finite rule set defines the well-formed strings, and a form is correct if and only if the rules derive it. They differ in three respects. A context-free production has one non-terminal on its left and may be applied wherever that symbol occurs; Pāṇini's operative rules state a surrounding condition, for which sūtras 1.1.66 and 1.1.67 supply a general notation, so they are context-sensitive. A context-free derivation's result does not depend on the order of application; Pāṇini's does, and four precedence principles decide it. And a context-free rule cannot refer to whether another rule has applied, whereas asiddhatva under 8.2.1 does exactly that. So the Aṣṭādhyāyī is better modelled as an ordered string rewriting system, whose nearest modern relatives are finite-state transducers in computational morphology rather than phrase-structure grammars.

What this chapter does NOT say

It does not say the Aṣṭādhyāyī is more powerful than a context-free grammar in the formal sense. Power in that sense is about which sets of strings can be generated, and settling that for the whole Aṣṭādhyāyī would require a formalisation of it that this paper does not attempt. What is claimed is that it is not context-free, which follows from its mechanisms.

It does not say the comparison is worthless. The comparison is how you find out what each system is for, and the differences are more informative than the similarities.

It does not say Pāṇini anticipated Chomsky. Nothing here is a claim about influence. [Foundations of NLP, and What Pāṇinian Grammar Contributed] separates the claims about influence from the evidence for them.

Quick revision

• Context-free: exactly one non-terminal on the left, so a rule applies wherever its symbol occurs and a derivation has a parse tree.
• The Aṣṭādhyāyī is not context-free, for three reasons: its rules state contexts, with 1.1.66 and 1.1.67 as the general notation; its mechanisms refer to whether other rules have applied, by 8.2.1 and 6.4.22; and its rules operate on sounds and markers, not on categories.
• Order of application is irrelevant in a context-free grammar and decisive in Pāṇini's.
• Positively: it is an ordered string rewriting system, closer to a finite-state transducer than to a phrase-structure grammar.
• Not claimed: a formal result about generative power, or any claim about influence.

Test yourself

1. Define a context-free grammar and say what property of derivations follows.

One in which every production has exactly one non-terminal on its left-hand side. It follows that every derivation can be drawn as a parse tree, since each step expands one node into its children.

2. Give three reasons the Aṣṭādhyāyī is not context-free, each with a sūtra.

Its operative rules state contexts, with 1.1.66 and 1.1.67 providing the general notation by case ending. Its mechanisms refer to whether other rules have applied, by 8.2.1 and 6.4.22. And its rules operate on sounds, stems, affixes and markers rather than on non-terminal categories.

3. What is Pāṇini's system, stated positively?

An ordered string rewriting system with a fixed application strategy supplied by the four precedence principles, whose nearest modern relatives are the finite-state transducers used in computational morphology.

4. Why does this chapter refuse to make a claim about generative power?

Because generative power is a statement about which sets of strings a formalism can produce, and establishing it for the Aṣṭādhyāyī would require a formalisation of the whole grammar that this paper does not attempt. That it is not context-free follows from its mechanisms without any such formalisation.

The lesson a language designer takes from this is that expressiveness is not free, and the useful levels are the bottom two. Programming languages are deliberately kept context-free or very nearly so, because a parser for them then exists and is fast.

The placement question, and why this book refuses it

"Where does the Aṣṭādhyāyī sit in the hierarchy?" is asked often and this book does not answer it. The refusal has a reason and the reason is the answer worth writing.

The hierarchy classifies grammars in a fixed formalism. A production is a pair of strings over a fixed alphabet of terminals and non-terminals. To place a system in the hierarchy you must first express it in that formalism.

The Aṣṭādhyāyī is not in that formalism. Its rules refer to markers that are deleted, to whether other rules have operated, and to positions in the text. [Context-Free Grammar, and Whether Pāṇini Wrote One] lists these.

So a placement would be a claim about a formalisation, not about the text. Different formalisations of the same grammar can land in different classes, and the choice of formalisation is where all the content is. A paper that states a class without stating its formalisation has not said anything checkable.

What can be said, and is. Individual mechanisms can be placed, and this book places them.

The last two rows are the interesting ones. A strategy for choosing which rule to apply is not part of a grammar in the Chomsky sense at all: a grammar defines a set of strings and says nothing about how they are produced. Pāṇini's system is as much a procedure as a grammar, and the hierarchy has no axis for that.

Worked example: why a strategy is not a grammar

Take two productions that both apply to the same string.

In a context-free grammar this is not a problem and not a choice. Both derivations exist, both results are in the language, and if they produce different structures for the same string the grammar is ambiguous.

In Pāṇini's system it is a problem with a stated answer. Exactly one of the two rules is to apply, the precedence principles say which, and the other result is not a Sanskrit word.

So the two systems differ in what a rule set is for. A Chomsky grammar defines a set. Pāṇini's defines a function, from a root and a meaning to one form. A system that defines a function needs a strategy and a system that defines a set does not, and that is why the hierarchy does not have a place for the strategy.

Quick revision

• Four types: 3 regular, 2 context-free, 1 context-sensitive, 0 unrestricted, each properly contained in the next.
• Machines: finite automaton, pushdown automaton, linear bounded automaton, Turing machine.
• Regular cannot count or match brackets; context-free can match one nesting but not compare two counts; context-sensitive can; unrestricted makes membership undecidable.
• Costs rise with expressiveness, which is why programming languages are kept at type 2 or below.
• This book does not place the Aṣṭādhyāyī in a class, because a placement is a claim about a formalisation and no formalisation of the whole grammar is offered.
• It does place mechanisms: pratyāhāra is regular, a context-free rule is type 2, 7.3.84 is type 1, and asiddhatva and the precedence principles are outside the hierarchy.
• A Chomsky grammar defines a set of strings; Pāṇini's defines a function to one form, which is why it needs a strategy.

Test yourself

1. Name the four types with their production shapes and their machines.

Type 3 regular, a non-terminal rewriting to a terminal or a terminal and a non-terminal, recognised by a finite automaton. Type 2 context-free, one non-terminal on the left, a pushdown automaton. Type 1 context-sensitive, any left side with a right side no shorter, a linear bounded automaton. Type 0 unrestricted, any production, a Turing machine.

2. Give one language each type cannot generate that the next can.

Regular cannot generate balanced brackets, which is context-free. Context-free cannot generate strings with three equal counts, which is context-sensitive. Context-sensitive cannot generate every computably enumerable language, which type 0 can.

3. Why does this book refuse to place the Aṣṭādhyāyī in the hierarchy?

Because the hierarchy classifies grammars already expressed in one fixed formalism, and the Aṣṭādhyāyī is not in it: its rules refer to deleted markers, to whether other rules have applied, and to positions in the text. A placement would therefore be a claim about a chosen formalisation, and different formalisations land differently.

4. Why are the precedence principles outside the hierarchy altogether?

Because a Chomsky grammar defines a set of strings and says nothing about how a derivation is chosen. Pāṇini's system defines a single correct form, so it needs a strategy for choosing among applicable rules, and the hierarchy has no axis for a strategy.

Reading the two rule sets

Rule set A does not terminate, and the reason is visible in the trail: the two rules undo each other. A rewrite system can loop, and nothing in the notation prevents it.

Rule set B terminates, and it sorts. Every normal form has its a's before its b's. The termination argument is a good one to know: each application of the rule moves one a one place to the left, and the total of the positions of the a's is a whole number that strictly decreases and cannot go below zero. Exhibiting a quantity that strictly decreases is how termination is proved.

Rule set B is also confluent. Whatever order the rewrites are done in, the result is the same string: all the a's, then all the b's. So it is convergent, and it computes a function.

The Aṣṭādhyāyī as a rewrite system

This is the positive characterisation [Context-Free Grammar, and Whether Pāṇini Wrote One] promised.

The strings are forms under derivation. A root plus affixes, with markers.

The rules are the vidhi rules. Each replaces one element by another in a stated context.

A normal form is a finished word. No further rule applies.

And there is a strategy. This is the part that makes it different from rule set B above, and it is the important part.

Why a strategy changes everything

Rule set B is confluent, so it needs no strategy: any order gives the same answer. Most interesting rewrite systems are not confluent, and then the order decides the result.

Pāṇini's system is not confluent. Two rules can apply and give different words, and only one of them is Sanskrit. So a strategy is not an optimisation; it is part of the specification.

The strategy is the precedence order. Apavāda, nitya, antaraṅga, paratva, as [Rule Precedence: The Four Principles] sets out, with prohibitions and asiddhatva outside the queue.

A rewrite system plus a deterministic strategy computes a function. Given a root and a meaning, exactly one sequence of rewrites is licensed, so exactly one form results. That is what the grammar is for, and it is why the tradition invested so heavily in the precedence rules rather than in making the rules non-overlapping.

Termination, and the honest gap

The last row is a real gap and it should be stated.

Nothing in the tradition proves the grammar terminates. No argument is offered that a derivation cannot loop. The evidence is that derivations in practice finish, which is the same evidence rule set A appeared to have until somebody tried "ab".

The asiddhatva mechanism helps. By making phase two invisible to phase one, 8.2.1 prevents a class of loops in which a phase-one rule keeps re-firing because a phase-two rule keeps undoing its work. That is a structural reason to expect termination, and it is the nearest thing to an argument the system provides.

But it is not a proof, and a chapter that claimed otherwise would be overstating. What can be said is that the mechanism exists and that it forecloses the obvious failure mode.

What a rewrite system is NOT

It is not a grammar in the Chomsky sense. It has no start symbol and no non-terminals, and it need not define a set of strings. A grammar generates; a rewrite system transforms.

It is not deterministic by itself. Which occurrence of which rule to rewrite is a choice, and the notation does not make it.

It is not guaranteed to do anything. Termination and confluence are properties to be established, not features of the notation.

Quick revision

• A string rewriting system is an alphabet plus rules replacing one string by another. A step applies one rule at one occurrence.
• Normal form: no rule applies. Termination: every string reaches one. Confluence: different orders can be brought back together. Convergent: both.
• Rule set A, ab to ba and ba to ab, loops. Rule set B, ba to ab only, terminates and sorts, and the termination proof exhibits a strictly decreasing quantity.
• The Aṣṭādhyāyī is a rewrite system over forms, and it is NOT confluent, so its strategy is part of its correctness and not an optimisation.
• The strategy is the four precedence principles, with prohibition and asiddhatva outside the queue.
• Termination is not proved by the tradition. Asiddhatva forecloses the obvious loop and is not a proof.

Test yourself

1. Define normal form, termination and confluence.

A normal form is a string to which no rule applies. A system terminates if every string reaches a normal form in finitely many steps. It is confluent if whenever two different rewrites are possible from a string, the two results can be continued to a common string.

2. Prove that the rule "ba rewrites to ab" terminates.

Each application moves one a one position to the left, so the sum of the positions of the a's strictly decreases with every step. It is a non-negative whole number, so it cannot decrease for ever, and the system must halt.

3. Why is Pāṇini's strategy part of his specification rather than an optimisation?

Because his rule set is not confluent: two applicable rules can yield different forms and only one is correct. So the order of application determines the answer, and the precedence principles are what fix the answer.

4. What does asiddhatva contribute to termination, and what does it not?

By making the later phase invisible to the earlier one, it prevents a loop in which an earlier rule re-fires because a later rule keeps undoing its work. It does not amount to a proof that no derivation loops, and the tradition offers none.

traces
           q0   accept
  L        q0 q0   accept
  G        q0 q1   accept
  GL       q0 q1 q0   accept
  GG       q0 q1 qX   reject
  GLG      q0 q1 q0 q1   accept
  GGL      q0 q1 qX qX   reject
  LGLG     q0 q0 q1 q0 q1   accept

n    patterns accepted   Fibonacci check
1    2        2          matches
2    4        3          matches
3    8        5          matches
4    16       8          matches
5    32       13         matches
6    64       21         matches
7    128      34         matches
8    256      55         matches
9    512      89         matches
10   1024     144        matches
11   2048     233        matches
12   4096     377        matches

What that second table shows

The accepted counts are 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377. Each is the sum of the two before it, which is the Fibonacci recurrence, and the program checks it for every n from one to twelve.

The reason is a two-line argument. Count the acceptable patterns of n syllables by their last syllable. If it is light, the first n minus one syllables may be any acceptable pattern. If it is heavy, the syllable before it must be light, so the first n minus two may be any acceptable pattern. So the count for n is the count for n minus one plus the count for n minus two.

That is the same kind of argument as the Meru's addition rule, in [Meru-Prastāra: Halāyudha's Staircase]: split on the last syllable and add the cases. The technique transfers, which is what makes it worth learning.

And no historical claim is made. This is a fact about the machine defined above, established by running it. Nothing in this chapter says that any classical text states it, because this book has not verified that in a source it has read.

Why the machine is finite, and what that costs

Three states are enough for this condition because deciding it needs one bit of memory: was the previous syllable heavy?

Some conditions need more, and some need infinitely many. "Equally many light and heavy syllables" cannot be decided by any finite automaton, because the machine would have to remember the running difference, which is unbounded. That is the limitation [The Chomsky Hierarchy, and Where the Aṣṭādhyāyī Sits] records as "regular cannot count".

So the test for whether a DFA can do a job is: can the decision be made with a bounded amount of memory about what has been read? If yes, a DFA exists. If no, it does not.

Why this matters for the next chapter

The precedence cascade of [Rule Precedence: The Four Principles] is a decision procedure over a fixed, finite set of considerations, taken in a fixed order, with exactly one outcome at each step. That is a deterministic machine, and [Śāstra Rule Precedence as a Deterministic Finite Rewrite System] builds it as one.

The vocabulary this chapter supplies for that is: a state is the situation of the decision so far, a transition is the consideration being applied, and determinism is the property that exactly one outcome follows.

What a DFA is NOT

It is not a parser. It says yes or no. It produces no structure.

It is not more powerful with more states. Adding states extends what a particular machine can do; no number of states makes a DFA able to count without bound.

It is not non-deterministic. A machine with a choice at some state is a different object, and for every such machine there is a deterministic one accepting the same language, possibly with many more states.

Quick revision

• Five parts: states, alphabet, transition function, start state, accepting states. Deterministic means exactly one next state for each state and symbol.
• A DFA recognises exactly the regular languages, and its whole memory is which state it is in.
• The three-state machine above accepts the patterns with no two adjacent heavy syllables. qX is a trap state.
• The accepted counts follow the Fibonacci recurrence, and the reason is the split on the last syllable, as in the Meru's addition rule. No historical claim is made about that.
• The test for whether a DFA can do a job: is bounded memory about what has been read enough?
• A DFA gives a yes or no, produces no structure, and cannot count without bound however many states it has.

Test yourself

1. Give the five components of a DFA and say what "deterministic" means.

A finite set of states, an input alphabet, a transition function, a start state, and a set of accepting states. Deterministic means the transition function gives exactly one next state for every state and input symbol, so the machine never has a choice.

2. Design a DFA over L and G that accepts patterns ending in a light syllable.

Two states. In the start state, reading L goes to the accepting state and reading G stays; in the accepting state, reading L stays and reading G returns to the start. Accept only the second state, so the empty pattern is rejected.

3. Why do the accepted counts in the table follow the Fibonacci recurrence?

Classify the acceptable patterns of n syllables by the last syllable. If it is light, the first n minus one may be any acceptable pattern; if it is heavy, the one before must be light, so the first n minus two may be any acceptable pattern. The count for n is therefore the sum of the counts for n minus one and n minus two.

4. Give a condition on patterns that no DFA can decide, and say why.

Whether a pattern has equally many light and heavy syllables. The machine would have to remember the running difference between the two counts, which is unbounded, and a DFA has only finitely many states.

Working code

"""Sastra rule precedence as a deterministic finite rewrite system.

Every rule strictly SHORTENS the string, so termination is guaranteed.
The four precedence principles are declared on the rules, as the tradition
declares them, and the resolver applies them in the tradition's order.
"""

#      address  special nitya  inner  phase  left    right
RULES = {
    "R1": ("2.1.1", False, False, False, 1, "aa",  "a"),
    "R2": ("2.1.2", True,  False, False, 1, "aab", "ab"),
    "R3": ("3.1.1", False, True,  False, 1, "bb",  "b"),
    "R4": ("3.1.2", False, False, True,  1, "ba",  "a"),
    "R5": ("4.1.1", False, False, False, 1, "aaa", "aa"),
    "R6": ("5.1.1", False, False, False, 1, "aaa", "a"),
    "R7": ("6.1.1", False, False, False, 1, "aa",  ""),
    "R8": ("8.2.5", False, False, False, 2, "b",   ""),
}
ORDER = ["R1", "R2", "R3", "R4", "R5", "R6", "R7", "R8"]
SPECIAL, NITYA, INNER = 1, 2, 3


def address(name):
    return tuple(int(x) for x in RULES[name][0].split("."))


def candidates(word, phase):
    return [n for n in ORDER
            if RULES[n][4] == phase and RULES[n][5] in word]


def resolve(names):
    """The cascade, in the tradition's order. Returns winner and principle."""
    if len(names) == 1:
        return names[0], "only one applies"
    for flag, principle in ((SPECIAL, "apavada"), (NITYA, "nitya"), (INNER, "antaranga")):
        marked = [n for n in names if RULES[n][flag]]
        if len(marked) == 1:
            return marked[0], principle
        if len(marked) > 1:
            names = marked
    return max(names, key=address), "1.4.2 paratva"


def apply_once(word, name):
    left, right = RULES[name][5], RULES[name][6]
    i = word.index(left)
    return word[:i] + right + word[i + len(left):]


def derive(word):
    trail = []
    for phase in (1, 2):
        while True:
            names = candidates(word, phase)
            if not names:
                break
            winner, why = resolve(names)
            nxt = apply_once(word, winner)
            assert len(nxt) < len(word), "a rule that does not shorten breaks termination"
            trail.append((phase, word, names, winner, why, nxt))
            word = nxt
    return word, trail


def any_order(word, phase, depth=0):
    """Every normal form reachable by applying rules of this phase in ANY order."""
    names = candidates(word, phase)
    if not names or depth > 20:
        return {word}
    out = set()
    for n in names:
        out |= any_order(apply_once(word, n), phase, depth + 1)
    return out


CASES = ["aab", "bba", "baa", "aaba", "aaa", "aa", "bb", "ba", "b", "abba", "aabb", "a", ""]

print("%-8s %-12s %-6s %s" % ("input", "normal form", "steps", "principles used"))
for case in CASES:
    out, trail = derive(case)
    used = ", ".join(sorted({t[4] for t in trail})) or "none"
    print("%-8s %-12s %-6d %s" % (case or "(empty)", out or "(empty)", len(trail), used))

print()
print("each of the four principles decides at least once")
seen = {}
for case in CASES:
    for t in derive(case)[1]:
        seen.setdefault(t[4], (case, t[1], "/".join(t[2]), t[3]))
for principle in ("apavada", "nitya", "antaranga", "1.4.2 paratva"):
    if principle in seen:
        case, before, names, winner = seen[principle]
        print("  %-14s on input %-6s at %-5s among %-14s -> %s"
              % (principle, case, before, names, winner))
    else:
        print("  %-14s NEVER EXERCISED by these cases" % principle)

print()
print("one derivation traced: baa")
out, trail = derive("baa")
for phase, before, names, winner, why, after in trail:
    print("  phase %d  %-5s applicable %-14s -> %-3s by %-16s gives %s"
          % (phase, before, "/".join(names), winner, why, after or "(empty)"))
print("  normal form:", out or "(empty)")

print()
print("termination: every rule shortens the string, so no derivation can loop")
print("confluence:  checked below, input by input")
print("%-8s %-12s %s" % ("input", "strategy", "normal forms reachable in any order"))
for case in CASES:
    strat, _ = derive(case)
    forms = set()
    for f in any_order(case, 1):
        forms |= any_order(f, 2)
    tag = "confluent" if len(forms) == 1 else "not confluent"
    print("%-8s %-12s %-22s %s"
          % (case or "(empty)", strat or "(empty)",
             ", ".join(sorted(x or "(empty)" for x in forms)), tag))

input    normal form  steps  principles used
aab      a            2      apavada, only one applies
bba      a            2      nitya, only one applies
baa      (empty)      2      1.4.2 paratva, antaranga
aaba     (empty)      3      1.4.2 paratva, apavada, only one applies
aaa      a            1      1.4.2 paratva
aa       (empty)      1      1.4.2 paratva
bb       (empty)      2      only one applies
ba       a            1      only one applies
b        (empty)      1      only one applies
abba     (empty)      3      1.4.2 paratva, nitya, only one applies
aabb     a            3      apavada, only one applies
a        a            0      none
(empty)  (empty)      0      none

each of the four principles decides at least once
  apavada        on input aab    at aab   among R1/R2/R7       -> R2
  nitya          on input bba    at bba   among R3/R4          -> R3
  antaranga      on input baa    at baa   among R1/R4/R7       -> R4
  1.4.2 paratva  on input baa    at aa    among R1/R7          -> R7

one derivation traced: baa
  phase 1  baa   applicable R1/R4/R7       -> R4  by antaranga        gives aa
  phase 1  aa    applicable R1/R7          -> R7  by 1.4.2 paratva    gives (empty)
  normal form: (empty)

termination: every rule shortens the string, so no derivation can loop
confluence:  checked below, input by input
input    strategy     normal forms reachable in any order
aab      a            (empty), a             not confluent
bba      a            a                      confluent
baa      (empty)      (empty), a             not confluent
aaba     (empty)      (empty), a             not confluent
aaa      a            (empty), a             not confluent
aa       (empty)      (empty), a             not confluent
bb       (empty)      (empty)                confluent
ba       a            a                      confluent
b        (empty)      (empty)                confluent
abba     (empty)      (empty), a             not confluent
aabb     a            (empty), a             not confluent
a        a            a                      confluent
(empty)  (empty)      (empty)                confluent

Reading the output, in four parts

All four principles decide at least once

The second block of the output exists because of a specific failure mode. An engine can implement four branches and exercise two, and then two of its branches have never run. A test set that leaves a branch unexercised has not tested it, and this program reports which principle decided in each derivation so that the gap is visible rather than assumed away. Here each of the four decides at least once, and the block names the input and the competing rules for each.

Termination is proved, not observed

Every rule's right side is shorter than its left side, so every application strictly reduces the length of the string. Length is a non-negative whole number, so it cannot decrease for ever.

The program asserts it at every step. If a rule were added that did not shorten, the assertion would fire on the first derivation that used it, rather than the program looping until somebody noticed.

That is the standard shape of a termination argument, and it is the one [Rewrite Systems] gives for the sorting rule: exhibit a quantity that strictly decreases and is bounded below.

Confluence fails, and that is the finding

The last block computes, for each input, every normal form reachable by applying the rules of each phase in any order, and compares that set with what the strategy produces.

For seven of the thirteen inputs the set has two members. So the rule set is not confluent: different orders reach different answers.

And the strategy picks one of them. That is what makes the system a function. Without the strategy the system would be a relation, associating some inputs with two outputs, and a grammar that associated one root with two words would be useless.

This is the precise sense in which Pāṇini's precedence rules are part of his specification rather than an optimisation, and it is the claim [Rewrite Systems] makes and this program demonstrates.

The phase boundary earns its place

The rule that deletes a b is in phase two. Run it in phase one and it would delete b's that phase-one rules still need to see: the rule whose left side is a b followed by an a could no longer fire, because there would be no b.

So the boundary is not decoration. It preserves the conditions that the earlier rules depend on, which is exactly what sūtra 8.2.1 does for the tripādī, as [Asiddhatva and the Tripādī: Ordering by Blocking] sets out.

Complexity and limitations

Time. Each step scans the rule set once, which is proportional to the number of rules, and then searches the string for one occurrence. The number of steps is bounded by the length of the input, since each step shortens it. So a derivation costs at most the length of the input times the size of the rule base.

Space. One string and the trail. The trail is the same length as the number of steps.

Limitation: the flags are declared, not derived. The tradition decides whether a rule is special, nitya or antaraṅga by argument about its content. This program takes the flags as given. A fuller implementation would compute specialness by comparing conditions, and would then have to face the cases where neither condition is a subset of the other, which the commentaries argue about.

Limitation: the leftmost occurrence is always chosen. Where a rule's left side occurs twice, the tradition's own treatment of which occurrence is operated on is a separate matter, and this program's choice is a simplification it declares.

Limitation: it is not Sanskrit. The alphabet is two letters and the rules are invented to exercise the four principles. What is demonstrated is the architecture, and the architecture is the thing MU's topic 8 names.

Quick revision

• A deterministic finite rewrite system is a rule set plus a strategy that always chooses exactly one rule.
• The strategy here is the tradition's cascade: apavāda, nitya, antaraṅga, paratva, with the set narrowed rather than abandoned when several rules share a flag.
• Termination is proved by exhibiting a strictly decreasing bounded quantity, here the string's length, and asserted at every step.
• The rule set is NOT confluent: seven of thirteen inputs reach two normal forms under free choice of order.
• So the strategy is what makes the system compute a function, which is the sense in which Pāṇini's precedence rules are part of his specification.
• The phase boundary preserves conditions the earlier rules depend on, as 8.2.1 does.
• Limitations: flags declared not derived, leftmost occurrence always chosen, and the alphabet is not Sanskrit.

Test yourself

1. What makes a rewrite system deterministic, and why is that not the same as confluent?

A strategy that selects exactly one applicable rule for every string. Confluence is a property of the rule set, that different orders reach the same answer. A non-confluent set with a total strategy is still deterministic, and the strategy then decides the answer.

2. Prove that the system in this chapter terminates.

Every rule's right side is shorter than its left, so each application strictly reduces the length of the string. Length is a non-negative whole number and cannot decrease for ever, so every derivation halts.

3. Why does the program report which principle decided each step?

Because an engine can implement four branches and exercise only two, leaving two untested. Reporting the deciding principle makes an unexercised branch visible, and the output block shows that all four decide at least once.

4. What would go wrong if the deleting rule were moved into phase one?

It would delete the symbol that another phase-one rule needs in its condition, so that rule could no longer fire. The phase boundary preserves the conditions the earlier rules depend on, which is the function sūtra 8.2.1 performs for the tripādī.

input                        verdict
rama sees                    accepted
rama sees sita               accepted
rama sees sita quickly       accepted
sita calls rama              accepted
sees rama                    rejected: expected NP   at position 0, found sees
rama sita                    rejected: expected V    at position 1, found sita
rama sees quickly            rejected: trailing words left over at position 2
rama sees sita sita          rejected: trailing words left over at position 3
rama                         rejected: expected V    at position 1, found None
(empty)                      rejected: expected NP   at position 0, found None

the parse tree for: rama sees sita quickly
S
    NP
        rama
    VP
        V
            sees
        NP
            sita
        ADV
            quickly

the trace for a rejection: rama sees quickly
  enter S
  matched rama      as NP
  enter VP
  matched sees      as V
  trailing words left over at position 2

Reading the output

Four accepted, six rejected, and each rejection carries the reason and the position.

The error messages are the advantage of top-down parsing. "Expected V at position 1, found sita" is possible because the procedure that failed knew what it was looking for. A bottom-up parser at the same point knows only that its stack cannot be reduced.

The parse tree is the point of parsing. The tree for "rama sees sita quickly" says that "sees sita quickly" groups together as a verb phrase and "rama" stands outside it. Nothing in the string says so. Recovering that grouping is what a parser is for, and it is why a compiler parses before it does anything else.

And the trace shows the parser giving up honestly. On "rama sees quickly" it matched the subject and the verb, then found a word left over that no production could account for, and said so. It did not guess.

Ambiguity

A grammar is ambiguous if some string has two different parse trees.

Why it matters. Two trees mean two groupings, and two groupings can mean two things. In a programming language that is a disaster: an expression would compile two ways.

How it shows up. The classic case is an operator with no stated precedence, so that a sum of three terms can group either way. In natural language it is everywhere, which is one reason natural language parsing is hard in a way programming language parsing is not.

The grammar in this chapter is unambiguous, and the evidence is in [Formal Grammars: Alphabet, Rule, Derivation, Language]: its enumeration produced exactly as many derivations as distinct strings. Equal counts mean no string was reached twice, so no string has two derivations.

Why the Aṣṭādhyāyī is hard to parse with

Three reasons, all of which follow from earlier chapters.

It derives, and derivation is not reversible. A rule that replaces a vowel by its guṇa loses information: several different vowels have the same guṇa. Running the rule backwards gives several candidates and no way to choose among them from the output alone.

Markers are deleted. An anubandha decided which rules applied, and it is not in the finished word. So the analyser cannot see the information the derivation used.

The strategy is part of the meaning. To know which rule produced a given step you must know which rule the precedence principles would have selected, which depends on the state of the form before the step, which is what you are trying to recover.

The consequence, stated plainly. Using Pāṇini's grammar to analyse Sanskrit is not a matter of running it backwards. It requires search: propose an underlying form, derive it forwards, and see whether the result matches. That is how computational systems built on Pāṇinian principles actually work, and [Foundations of NLP, and What Pāṇinian Grammar Contributed] returns to it.

What parsing is NOT

It is not the same as validating. A parser can accept a string and the string can still be meaningless, as "sita calls rama quickly" being accepted shows. Syntax is not semantics.

It is not always necessary. If you only need to know whether a string matches a pattern, a finite automaton will do and produces no tree. [Automata Theory Foundations: The Finite Automaton] is the cheaper tool.

It is not unique to the grammar. Many parsers exist for one grammar, and they differ in speed, in error messages and in which grammars they can handle at all.

Quick revision

• Generating makes strings from rules; parsing recovers the rules from a string.
• Top down starts from the start symbol, is easy to hand-write, gives good error messages, and cannot handle left recursion.
• Bottom up starts from the input, uses a stack, handles left recursion, and gives poorer messages.
• The parse tree is the point: it records groupings the string does not state.
• Ambiguity is two trees for one string, and it matters because two groupings can mean two things.
• The Aṣṭādhyāyī is hard to parse with because derivation loses information, markers are deleted, and the strategy depends on the state you are trying to recover. Analysis therefore needs search, not reversal.

Test yourself

1. Distinguish parsing from generating, and say which the Aṣṭādhyāyī does.

Generating produces strings by applying rules; parsing takes a given string and determines whether the rules could have produced it and by what structure. The Aṣṭādhyāyī generates: it derives a form from a root and a meaning.

2. Give two differences between top-down and bottom-up parsing.

Top down starts from the start symbol and bottom up from the input. Top down cannot handle a left-recursive production, since parsing an A begins by parsing an A, whereas bottom up can; and top down gives better error messages, because the failing procedure knows what it expected.

3. Why is a parse tree worth having when a yes or no would do?

Because the tree records which parts of the string group together, and the grouping is what the meaning depends on. A yes or no from a finite automaton gives no structure at all.

4. Give one reason the Aṣṭādhyāyī cannot simply be run backwards to analyse a word.

Its rules lose information: several vowels share one guṇa, and the markers that decided which rules applied are deleted before the word appears. So a backward step has several candidates and no way to choose, and analysis must instead propose an underlying form and derive forwards to check it.

Why that invertibility matters. One machine serves both analysis and generation. Write the rules once and you get both directions, which is the property a plain rewrite system does not have.

And this is the honest comparison with Pāṇini. His rules are a mapping from an underlying form to a surface form, stated with contexts and applied in an order. That is what a cascade of transducers is. The differences are real: a transducer is invertible and his rules are not, and a transducer has no precedence cascade.

The claims about influence, sorted

This is the section that matters for honesty, and it is organised by what kind of claim each statement is.

Attributable to the text, and this book has read the evidence

The Aṣṭādhyāyī states rules with contexts, in a fixed order, with a declared policy for conflicts, and separates rules from annotated data. Every part of that is in earlier chapters with the sūtra that supports it.

It treats a language as defined by the strings its rules derive. That is the tradition's criterion of correctness, and it is the modern definition of a language generated by a grammar.

A resemblance, worth stating as a resemblance

Pāṇini's architecture resembles a cascade of finite-state transducers more than it resembles a phrase-structure grammar. That is a judgement about similarity, supported by the table above, and it is not a historical claim.

The six kinds of sūtra resemble a typed rule system. Also a resemblance, and a useful one, as [The Six Kinds of Sūtra, in Vasu's Own Words] sets out.

Claims this book does not make, and why

That Pāṇini influenced the development of formal language theory. This is asserted often. It is a historical claim about what particular twentieth-century researchers read and when, and it requires evidence this book has not examined. So it is not made here.

That a named modern formalism was derived from Pāṇini. Same reason.

That Pāṇini anticipated the Chomsky hierarchy. [The Chomsky Hierarchy, and Where the Aṣṭādhyāyī Sits] explains why even placing the Aṣṭādhyāyī in the hierarchy would be a claim about a formalisation rather than about the text.

What to write in an examination. If a question invites you to discuss Pāṇini's contribution to NLP, the strong answer describes the architecture, names the modern object it resembles, and says which claims are about the text and which are about influence. An answer that separates the two is better than one that asserts the larger claim.

Worked example: what a Pāṇinian analyser actually does

Because "run the grammar backwards" is not available, systems built on these principles work in the other direction.

Step one. Take the surface form. Propose a set of candidate underlying forms: a root from the root list, plus affixes that could plausibly be present.

Step two. For each candidate, derive forwards using the rules, with the precedence cascade deciding at each conflict.

Step three. Keep the candidates whose derivation produces the surface form exactly.

Step four. If more than one candidate survives, the form is ambiguous, and something outside the morphology has to choose.

This is generate and test, and it is the standard shape of a solution when a transformation is not invertible. Notice that it uses the grammar exactly as written, in its own direction, which is why a faithful implementation of the rules is worth having even though the task is analysis.

Quick revision

• Layers: tokenisation, morphology, syntax, semantics, pragmatics. They are not independent, and Sanskrit proves it, since tokenising requires undoing sandhi.
• A finite-state transducer reads and writes, so it maps strings to strings, and it is invertible, which is why it serves analysis and generation from one description.
• Pāṇini's rules resemble a cascade of transducers more than a phrase-structure grammar: contexts, ordering, one direction.
• Differences: a transducer is invertible and his rules lose information; a transducer has no precedence cascade.
• Attributable to the text: rules with contexts, in an order, with a conflict policy, and rules separated from annotated data.
• Not claimed here: any historical influence on formal language theory, because that needs evidence this book has not examined.
• A Pāṇinian analyser works by generate and test, not by reversal.

Test yourself

1. Name the layers of NLP and give one case where two of them cannot be separated.

Tokenisation, morphology, syntax, semantics, pragmatics. Tokenising Sanskrit cannot be separated from morphology, because adjacent words are joined by sandhi and the boundaries can be found only by undoing rules that belong to morphology.

2. What is a finite-state transducer and why is it the standard tool for morphology?

A finite automaton that writes an output symbol at each transition, so it maps one string to another. It is the standard tool because a morphological rule is such a mapping and because a transducer is invertible, so one description serves both analysis and generation.

3. Give two respects in which Pāṇini's rules differ from a transducer cascade.

His rules are not invertible, since operations such as guṇa lose information and markers are deleted. And they carry a precedence cascade for resolving conflicts, which a transducer cascade handles instead by the order in which the machines are composed.

4. A question asks you to assess Pāṇini's contribution to natural language processing. What should your answer separate, and why?

It should separate what is attributable to the text, namely rules with stated contexts applied in a stated order with a declared conflict policy over annotated data, from resemblances to modern formalisms, from historical claims about influence. The last require evidence about what particular researchers read, which is a different kind of claim and needs a different kind of support.

Working code

IK = ["i", "ii", "u", "uu", "ri", "rii", "li"]
GUNA = {"i": "e", "ii": "e", "u": "o", "uu": "o", "ri": "ar", "rii": "ar", "li": "al"}

RULES = [
    # sutra, kind, specific?, nitya?, inner?, phase, what it does
    ("1.1.5",  "nisedha", True,  False, True,  1, "block guna when the affix carries a marker"),
    ("7.3.84", "vidhi",   False, True,  True,  1, "guna of the stem's ik vowel"),
    ("8.2.1",  "boundary", False, False, False, 2, "phase two: invisible to phase one"),
]

def applicable(stem, affix_kind, markers):
    out = []
    if affix_kind in ("sarvadhatuka", "ardhadhatuka"):
        if any(stem.endswith(v) for v in IK):
            out.append("7.3.84")
        if markers:
            out.append("1.1.5")
    return out

def resolve(candidates):
    """The four principles, in order, returning the winner and the reason."""
    if len(candidates) == 1:
        return candidates[0], "only one rule applies"
    info = {r[0]: r for r in RULES}
    specific = [c for c in candidates if info[c][2]]
    if len(specific) == 1:
        return specific[0], "apavada: a special rule sets aside the general one"
    nitya = [c for c in candidates if info[c][3]]
    if len(nitya) == 1:
        return nitya[0], "nitya: the rule that would apply either way goes first"
    inner = [c for c in candidates if info[c][4]]
    if len(inner) == 1:
        return inner[0], "antaranga: the inner rule prevails"
    later = max(candidates, key=lambda s: tuple(int(x) for x in s.split(".")))
    return later, "1.4.2 vipratisedha: the later rule prevails"

def derive(stem, affix, affix_kind, markers=()):
    cands = applicable(stem, affix_kind, markers)
    if not cands:
        return stem + affix, "no rule applies", "none"
    winner, why = resolve(cands)
    if winner == "1.1.5":
        return stem + affix, why, winner
    for v in sorted(IK, key=len, reverse=True):
        if stem.endswith(v):
            return stem[:-len(v)] + GUNA[v] + affix, why, winner
    return stem + affix, why, winner

CASES = [
    ("bhu",   "ti",  "sarvadhatuka", (),     "bhoti"),
    ("ji",    "ti",  "sarvadhatuka", (),     "jeti"),
    ("kri",   "ti",  "sarvadhatuka", (),     "karti"),
    ("bhuu",  "ti",  "sarvadhatuka", (),     "bhoti"),
    ("patha", "ti",  "sarvadhatuka", (),     "pathati"),
    ("ji",    "ta",  "ardhadhatuka", ("k",), "jita"),
    ("bhu",   "ta",  "ardhadhatuka", ("ng",),"bhuta"),
    ("ji",    "tum", "ardhadhatuka", (),     "jetum"),
    ("ji",    "sya", "other",        (),     "jisya"),
    ("ji",    "",    "other",        (),     "ji"),
]

print("%-8s %-6s %-14s %-8s %-9s %-7s %s" % ("stem", "affix", "affix kind", "markers", "result", "expect", "decided by"))
ok = 0
for stem, affix, kind, markers, expect in CASES:
    got, why, winner = derive(stem, affix, kind, markers)
    ok += got == expect
    print("%-8s %-6s %-14s %-8s %-9s %-7s %s"
          % (stem, affix or "(none)", kind, ",".join(markers) or "(none)", got, expect,
             winner if winner != "none" else "-"))
print()
print("%d of %d cases give the expected result" % (ok, len(CASES)))
print()
print("the reason, for the two cases where two rules applied")
for stem, affix, kind, markers, expect in CASES:
    cands = applicable(stem, kind, markers)
    if len(cands) > 1:
        w, why = resolve(cands)
        print("  %s + %s: %s applied against %s, and %s won by %s"
              % (stem, affix, cands[0], cands[1], w, why.split(":")[0]))

stem     affix  affix kind     markers  result    expect  decided by
bhu      ti     sarvadhatuka   (none)   bhoti     bhoti   7.3.84
ji       ti     sarvadhatuka   (none)   jeti      jeti    7.3.84
kri      ti     sarvadhatuka   (none)   karti     karti   7.3.84
bhuu     ti     sarvadhatuka   (none)   bhoti     bhoti   7.3.84
patha    ti     sarvadhatuka   (none)   pathati   pathati -
ji       ta     ardhadhatuka   k        jita      jita    1.1.5
bhu      ta     ardhadhatuka   ng       bhuta     bhuta   1.1.5
ji       tum    ardhadhatuka   (none)   jetum     jetum   7.3.84
ji       sya    other          (none)   jisya     jisya   -
ji       (none) other          (none)   ji        ji      -

10 of 10 cases give the expected result

the reason, for the two cases where two rules applied
  ji + ta: 7.3.84 applied against 1.1.5, and 1.1.5 won by apavada
  bhu + ta: 7.3.84 applied against 1.1.5, and 1.1.5 won by apavada

Reading the output

Ten cases, ten expected results. Five where guṇa applies, two where the prohibition blocks it, and three where no rule applies at all.

The "decided by" column is the part that matters. For the two blocked cases, two rules were applicable at once: 7.3.84, which would gunate, and 1.1.5, which forbids it. The resolver reports that 1.1.5 won by apavāda, because its condition, an affix carrying a marker, is narrower than 7.3.84's condition, an affix of two named kinds.

And the last block prints the conflict explicitly. An engine that resolves a conflict silently is an engine you cannot debug, and an internal assessment that cannot show why it produced an answer will not survive a viva.

The limits of this engine, stated

This is MU's heading seven, and it is the heading that separates a good submission from a demonstration.

It stops before the word is finished. The guṇa substitution gives a stem, and the Sanskrit word needs one more rule, 6.1.78, which is cited and not implemented. The engine's output for the root bhu with a present ending is a stage in a derivation, not a word.

The rule base is three rules out of about four thousand. It is chosen to exhibit the architecture: a vidhi, a paribhāṣā scoping it, a niṣedha blocking it, and the phase boundary. It is not a grammar of Sanskrit and nothing here suggests it is.

The markers are given as input. In the grammar they come from the Dhātupāṭha and from the affix lists. A fuller implementation would read them from a data file, which is exactly the separation of rules from annotated data that [Pāṇini's Aṣṭādhyāyī, and the Text We Are Reading] describes.

Two of the four principles are never exercised by these ten cases. Nitya and antaraṅga are implemented and no case reaches them, because with three rules no pair is separated by those tests. The resolver in [Śāstra Rule Precedence as a Deterministic Finite Rewrite System] has cases for all four, and an honest submission says which of its branches its tests actually cover.

Transliteration is plain ASCII. The engine works on strings like "bhu" and "ji", not on Devanagari, so nothing in it depends on a script.

Complexity

Per derivation: the rule base is scanned once to collect candidates, so the work is proportional to the number of rules; the resolver then makes at most four passes over the candidates. With a rule base of four thousand, a real implementation would index the rules by their trigger conditions rather than scanning, which turns the scan into a lookup.

The resolver is constant time in the number of rules and linear in the number of candidates, which is small.

Quick revision

• Four parts of a rule-based engine: a rule base as data, candidate selection, conflict resolution, application, repeated.
• The Aṣṭādhyāyī supplies all four: its rules, its rule types, its four precedence principles, its phase boundary.
• The resolver is a cascade of single-winner tests in the tradition's order; reversing the order changes answers.
• A prohibition returns the form unchanged; a blocked operation is a normal outcome.
• The ten cases: five guṇa, two blocked by 1.1.5 winning on apavāda, three with no applicable rule.
• Limits: it stops before 6.1.78; three rules of four thousand; markers supplied as input; nitya and antaraṅga implemented but not exercised.

Test yourself

1. Give the four parts of a rule-based engine and the classical element each corresponds to.

A rule base as data, corresponding to the sūtras; candidate selection, corresponding to a rule's stated conditions; conflict resolution, corresponding to the four precedence principles; and application, corresponding to the vidhi operation.

2. Why is the resolver written as a cascade rather than as a score?

Because the tradition's principles are applied in a fixed order and each is decisive when it separates the candidates. A score would allow a lower principle to outweigh a higher one, which would give wrong answers whenever a special rule met a later one.

3. Explain why 1.1.5 beats 7.3.84 in the engine's output.

Both rules apply, so the cascade is entered. 1.1.5's condition, an affix carrying an indicatory marker, is a subset of 7.3.84's condition, an affix of two named kinds, so 1.1.5 is special and wins by apavāda before any other test is reached.

4. Name two limitations of this engine that belong in its own limitations section.

It stops at the guṇa substitution and does not apply 6.1.78, so its output is a stage in a derivation rather than a Sanskrit word. And two of the four precedence branches, nitya and antaraṅga, are implemented but are not exercised by any of its ten test cases.

2. Why is the sūtra method so brief, and what does the brevity cost?

The medium is human memory and recitation, so every syllable is a permanent cost, every ambiguity is a permanent risk, and a correction cannot be circulated; the reader's years of training, by contrast, cost the text nothing. The rational design pushes everything possible out of the text and into the commentary and the reader. The costs are three: no random access, because words carry over from earlier sūtras; no redundancy, so damage changes the rule rather than obscuring it; and no error detection, which the tradition answered socially, by parallel lineages and by the vārttika layer.

3. State the three pramāṇas and Charaka's rule about using them.

Pratyakṣa, perception; anumāna, inference; āgama or śabda, the instructive assertion of a reliable person. Charaka's rule is that all three should be used in examining a disease, and that the diagnosis then becomes faultless, because, in his own words, by only one of these means of knowledge, knowledge does not arise of everything that should be known. Testimony comes first in order of use, not in authority, because without prior instruction one does not know what to observe or what to infer.

4. Explain the prastāra rule and apply it to L L G.

Begin with a row of all heavy syllables. From any row, find the first heavy syllable from the left, make it light, make every syllable to its left heavy, and leave every syllable to its right unchanged; stop when the row is all light. In L L G the first heavy syllable is the third, so it becomes light and the two to its left are reset to heavy, giving G G L. The clause students drop is the reset, which turns L L G into L L L and breaks the table.

5. In what sense is the prastāra binary, and in what sense is it not?

Read laghu as one, guru as zero, and the leftmost syllable as the units place; then row r of the table, counting from zero, is the pattern whose value is r, and the next-row rule is exactly the rule for adding one to a binary number. That has been checked for every row of every metre up to fourteen syllables. What it is not: the text nowhere states a positional number system, nowhere treats a pattern as a number, and nowhere performs arithmetic on one. The order agrees with binary counting; the notion of a base does not appear.

6. State naṣṭa and uddiṣṭa and say what makes them index retrieval mechanisms.

Naṣṭa: halve the row number, writing a light syllable; if the number is odd, add one before halving and write a heavy syllable; write from the left and stop when the syllable count is reached. Uddiṣṭa: start at one, take the syllables from the last to the first, doubling each time, and subtract one at every heavy syllable. Each costs one step per syllable and neither needs the table, so they give access to a row by its number and to a number by its row in time independent of the size of the table. They are exact inverses, checked over every row up to sixteen syllables.

7. Explain Piṅgala's saṅkhyā rule and compute the number of forms of the gāyatrī.

Halve the syllable count repeatedly, recording a halving where it was exact and a subtraction where one had to come off first; then, reading the record forwards, start at one and square at a halving, double at a subtraction. For six syllables: six halves to three, three reduces to two, two halves to one, one reduces to zero, so the marks are double, square, double, square. Start at one: two, four, eight, sixty-four. Four operations instead of six multiplications, and Halāyudha's own commentary states the figure as sixty-four and then gives 128, 256, 512, 1024, 2048 and 4096 for seven to twelve syllables.

8. Describe the Meru-prastāra and state what its rows mean.

One is placed in the topmost cell; each end cell of every row takes the single cell above it; each interior cell takes the two cells above it, combined. Row n, counting the top as row zero, gives the number of patterns of n syllables with exactly k light syllables, for k from zero to n. Halāyudha reads the rows off as 1 1, then 1 2 1, then 1 3 3 1. The proof of the addition rule splits the patterns on the last syllable: if it is light the rest has one fewer light syllable, if heavy the rest has the same number, and the two cases are exclusive and exhaustive.

9. Name the six kinds of sūtra and say which of them changes a form.

Saṃjñā, a definition; paribhāṣā, a rule about how rules are read; vidhi, a general operation; niyama, a restriction on a rule's scope; adhikāra, a governing rule understood in those that follow; and atideśa, extension to an uncovered case by analogy. Only vidhi performs an operation on a form. Five of the six manage rules rather than changing words, which is the ratio worth noticing: a rule system large enough to be interesting spends most of its rules on the management of rules.

10. Explain the pratyāhāra device and decode two examples.

The fourteen Śivasūtras list the sounds of Sanskrit in a fixed order, each ending in a marker consonant that is not one of the sounds. By sūtra 1.1.71 a name is formed from the first sound of a span together with the marker that closes it, and denotes everything between them. So ac, from a to the marker closing the fourth aphorism, is all the vowels; hal, from ha to the final marker, is all the consonants. Vasu states that only forty-two such names are in practical use. The achievement is the order: a set can be named only if its members are contiguous in it.

11. Set out the conflict resolution mechanisms of the Aṣṭādhyāyī.

Three kinds. Structurally, asiddhatva: sūtra 8.2.1 makes the last three quarters of book eight non-existent for all earlier rules, so certain conflicts cannot arise. By prohibition: rules such as 1.1.5 forbid an operation outright, removing one candidate. And by precedence, in a fixed order of four: apavāda, a special rule sets aside a general one; nitya, a rule that would apply either way goes first; antaraṅga, a rule whose conditions lie closer to the stem prevails and the outer rule is treated as not having taken effect; and last, paratva, sūtra 1.4.2, under which the later rule prevails. Only paratva and the prohibitions are numbered sūtras; the other three principles are maxims of the tradition.

12. Is the Aṣṭādhyāyī a context-free grammar? Justify your answer.

No, for three reasons. Its operative rules state conditions on surrounding material, and sūtras 1.1.66 and 1.1.67 exist precisely to let any rule express a left or right context by a case ending, so the rules are context-sensitive in the strict sense. Its mechanisms refer to whether other rules have applied, which no context-free production can express: 8.2.1 and 6.4.22 do exactly that. And its rules operate on sounds, stems, affixes and deleted markers rather than on non-terminal categories, so there is no level at which a category is expanded into its parts. Positively, it is an ordered string rewriting system with a fixed application strategy, and its nearest modern relatives are the finite-state transducers of computational morphology.

The one-line facts a viva asks for

• Chandaḥśāstra: eight chapters; chapter 8 carries the pratyayas; the commentary quoted is Halāyudha's Mṛtasañjīvanī.
• Six pratyayas: prastāra, naṣṭa, uddiṣṭa, lagakriyā, saṅkhyā, adhvayoga.
• Aṣṭādhyāyī: eight books of four quarters; a citation is book, quarter, position.
• Fourteen Śivasūtras; forty-two pratyāhāras in practical use.
• 1.1.1 defines vṛddhi. 1.1.3 is the paribhāṣā restricting guṇa and vṛddhi to the ik vowels. 1.1.5 is the prohibition. 1.1.71 forms a pratyāhāra. 1.4.2 is vipratiṣedha. 7.3.84 causes guṇa. 8.2.1 is pūrvatrāsiddham.
• Vasu's translation, Allahabad, 1891 to 1898, is the source quoted, and it is out of copyright.
• 2 to the power n patterns of n syllables; row sums of the Meru are those same powers; the running total is 2 to the power n plus one, minus two.
• Gāyatrī 6 syllables and 64 forms, up to jagatī 12 syllables and 4096 forms, all stated in the commentary.

Quick revision

• Q.1 sets four alternatives on Module 1 and asks for two, so an answer is worth five marks: a definition, the mechanism, one example, one limit.
• The mapping table at the head of this chapter is the one to carry into the hall, because every cross-module answer begins by pairing a classical element with a modern concept.
• The three costs a complexity question is likeliest to want: the prastāra is proportional to n times 2 to the power n; naṣṭa and uddiṣṭa are proportional to n; saṅkhyā by squaring is proportional to log n.
• The sūtra numbers to know: 1.1.1, 1.1.3, 1.1.5, 1.1.71, 1.4.2, 7.3.84, 8.2.1 for Pāṇini, and 8.20 to 8.27 for Piṅgala.
• The figures Halāyudha's commentary itself states: 64, 128, 256, 512, 1024, 2048, 4096 for six to twelve syllables.

Test yourself

1. A question offers four alternatives and asks for two. What does that tell you about how much to write?

Each alternative is worth five marks in a one-hour paper, so a complete answer is a definition, the mechanism, one worked example and one limit, in roughly the length of the twelve answers above. It is not an essay, and it is not a list of headings either.

2. Which single table would you take into the hall, and why?

The mapping table at the head of this chapter, because Q.3 is set across both modules and every cross-module answer begins by pairing a classical element with the modern concept it corresponds to.

3. Give the three costs a complexity question is most likely to ask for.

The prastāra is proportional to n times 2 to the power n, which is the size of its output and therefore cannot be improved. Naṣṭa and uddiṣṭa are proportional to n and independent of the row number. Saṅkhyā by squaring is proportional to log n.

Seven of the sixteen are about failure. That proportion is the most informative thing about the list, and it is worth saying in an answer: a system that spends nearly half its vocabulary on how reasoning goes wrong is a system built for use against an opponent, not for private contemplation.

The commentary's own account of the structure

Vidyabhusana records, on the same sūtra, that knowledge of the sixteen categories means true knowledge of their enunciation, definition and critical examination, and that Book I treats of enunciation and definition while the remaining four books are reserved for critical examination.

So the text's own architecture is: name them, define them, then attack the definitions. That is the three-stage order [Śāstra: What Makes a Body of Knowledge Formal] identifies as the mark of a formal discipline, stated by the text about itself.

Worked example: where each group appears in a real dispute

Take a dispute about whether a piece of code is correct.

Doubt. The reviewer is not sure. That is saṃśaya, and it is what makes the enquiry worth having: nobody debates what nobody doubts.

Purpose. The reason for settling it: the release is tomorrow. That is prayojana.

Established tenet. What both parties already accept: the language's semantics, the test framework's behaviour. That is siddhānta, and a dispute in which nothing is shared cannot be conducted at all.

Familiar instance. A case both parties agree about, used to anchor a general claim. That is dṛṣṭānta, and it becomes the example member of the argument.

Members. The argument itself, in five parts. [The Five-Member Syllogism].

Failures. The reviewer's reason turns out to support the opposite conclusion too, which is the erratic fallacy; or one party wins by taking a word in a sense the other did not mean, which is quibble. [Hetvābhāsa: The Five Fallacies of the Reason] and [Chala, Jāti and Nigrahasthāna: How a Debate Is Lost].

What Nyāya is NOT

It is not a system of formal logic in the modern sense. There is no symbolic notation, no calculus, and no proof of soundness or completeness. What it has is a fixed form for an argument and a catalogue of ways an argument fails.

It is not only about debate. The first two categories are epistemology and the eighth is a method of reasoning. Debate is the setting, not the whole subject.

It is not the same as Vaiśeṣika. Vaiśeṣika is the sister school, concerned with the categories of what exists rather than with the means of knowing. Nyāya's category two, prameya, and Vaiśeṣika's padārtha overlap, and the traditions eventually merged, but they are two enumerations and [Padārtha: The Categories of What Exists] keeps them apart.

It is not committed to the religious frame of its first sūtra. The sūtra says the knowledge conduces to supreme felicity. Nothing in the logical machinery depends on that, and the machinery is what this paper examines.

Quick revision

• Nyāya: the Indian school of logic and debate. Its text is the Nyāya Sūtra of Gotama, five books of two chapters each.
• Sūtra 1.1.1 lists sixteen categories, and this book quotes Vidyabhusana's 1913 translation throughout.
• The sixteen in four groups: what knowledge is; what starts an enquiry; how an argument is made; how arguments are conducted and lost.
• Seven of the sixteen concern failure, which tells you the system is built for use against an opponent.
• The text's own order is enunciation, definition, critical examination; Book I does the first two and Books II to V the third.
• Not a symbolic logic, not only about debate, and not the same enumeration as Vaiśeṣika's padārtha.

Test yourself

1. What are the sixteen categories for, and which sūtra states them?

They are the subject matter of Nyāya: the means and objects of knowledge, the circumstances that start an enquiry, the parts of an argument, and the kinds of dispute and of failure. Nyāya Sūtra 1.1.1 enumerates them.

2. Group the sixteen and say what each group does.

Pramāṇa and prameya, what knowledge is and what it is of. Saṃśaya, prayojana, dṛṣṭānta and siddhānta, what starts and anchors an enquiry. Avayava, tarka and nirṇaya, how an argument is made and settled. Vāda, jalpa, vitaṇḍā, hetvābhāsa, chala, jāti and nigrahasthāna, how disputes are conducted and lost.

3. What does it tell you that seven of the sixteen categories concern failure?

That the system is designed for argument against an opponent rather than for private reasoning: nearly half its vocabulary exists so that a bad move can be named and the debate decided.

4. State the text's own three-stage order and where each stage is carried out.

Enunciation, definition, critical examination. Book I gives the enunciation and the definitions, and the remaining four books are reserved for the critical examination of them.

1. He receives a statement of similarity: this unknown animal resembles a known one.
2. He later perceives an animal resembling the known one.
3. He recalls the statement.
4. He concludes that the name in the statement applies to the animal in front of him.

The knowledge acquired is the application of a NAME. Not that the animal exists, which was perception; not a general fact, which would be inference. It is the linking of a word to a thing by way of a similarity.

Vidyabhusana records that some hold comparison is not an independent means, which is exactly the dispute above.

Why it matters to a computer science student

The four pramāṇas map onto four ways a system can acquire a fact, and the fourth is the one usually missing from the map.

The fourth row is nearest-neighbour classification, and it is a real and distinct operation. A system that matches a new record to the most similar known record and adopts its label is doing neither measurement nor rule-based derivation nor import. It is doing what the forester's listener did.

The comparison holds and it should not be pushed. The classical account is about applying a name on the strength of a stated similarity; a classifier is about assigning a label on the strength of a computed distance. The resemblance is in the structure, not in the mechanism, and [Multi-Class Classification, and How It Is Scored] treats the modern side on its own terms.

Which list does this paper use?

MU prints three in Module 1 and Nyāya's four belong to Module 2. So an answer should say which it is using.

For Module 1's pramāṇa question, use the three: pratyakṣa, anumāna, āgama. That is the Sāṃkhya and Āyurvedic set and it is what her label prints.

For a Module 2 question on Nyāya, use the four, and name the extra one as upamāna.

For a Q.3 cross-module question, the difference between the two lists IS an answer: the same paper prints one school's list in one module and another school's in the other, and being able to say which is which and why they differ is precisely the kind of comparison Q.3 asks for.

What the disagreement is NOT

It is not a disagreement about the facts. Every school agrees that people learn from testimony and from comparison. The question is whether those are separate channels or special cases.

It is not settled by counting. More means of knowledge is not a better epistemology. The Cārvāka position, that only perception counts, is a serious one and its consequence is that no general claim can be established at all.

It is not merely scholastic. The number of admitted channels determines what can be proved, and therefore what a debate can be won with. [Debate Methodology as a Validation Protocol] is where that bites.

Quick revision

• Nyāya Sūtra 1.1.3: perception, inference, comparison, verbal testimony. Four.
• Charaka and Sāṃkhya admit three, omitting comparison, and MU's Module 1 list is that three.
• Vidyabhusana enumerates schools admitting one, two, three, four, five, six and eight, and each list is a prefix of the next, so the dispute is about independence, not existence.
• Upamāna, 1.1.6: knowledge of a thing through its similarity to something previously well known. The bos gavaeus example: a statement of similarity, a later perception, a recollection, and the application of a name.
• The modern analogue of upamāna is labelling by similarity to a known instance, which is a distinct operation from measurement, derivation and import.
• Say which list you are using: three for Module 1, four for Nyāya, and the difference itself is a Q.3 answer.

Test yourself

1. Name the four pramāṇas of Nyāya and the one that Charaka omits.

Pratyakṣa, anumāna, upamāna and śabda. Charaka omits upamāna, comparison, and admits three.

2. Define upamāna and give the Sūtra's own example.

Knowledge of a thing through its similarity to another thing previously well known. A man is told by a forester that a bos gavaeus resembles a cow; later he sees such an animal, recalls what he was told, and concludes that the name applies to it.

3. What exactly are the schools disagreeing about when they admit different numbers?

Not whether people acquire knowledge in those ways, which all agree on, but whether each way is independent or reduces to one already admitted. A Vaiśeṣika treats testimony as a species of inference; a Naiyāyika denies that the required general connection has been established.

4. Give the modern counterpart of each of the four, and say where the comparison should stop.

Measurement, derivation from rules, import from a trusted source, and labelling a new instance by similarity to a known one. The comparison should stop at the mechanism: upamāna applies a name on a stated similarity, while a classifier assigns a label on a computed distance.

In modern terms: confirming cases and disconfirming cases, and the disconfirming ones are the informative ones. A rule that survives a search for counterexamples is worth more than a rule with many confirming instances, and the Nyāya apparatus has a slot for both.

The three kinds of inference

Nyāya Sūtra 1.1.5 gives them, with Vidyabhusana's own examples.