Ling484 Notes

A. C. Brett acbrett@uvic.ca Department of Linguistics University of Victoria Clearihue C139

Procedures: Examples and Discussion

Agents and devices that are intended to perform procedures include any variety of mechanical, electrical, electronic, or living mechanism that is capable of being instructed or, in effect, "programmed". Such mechanisms include, among many others, clothes washers, microwave ovens, computers, and human beings.

Examples of procedures that are normally intended to be performed by computers, and which are of particular interest in computational linguistics, include procedures devised for the task or problem of determining whether or not a given string is a sentence in a particular language. Procedures for answering this question may consist of a finite sequence of instructions comprising a program in a language which is "comprehensible" to, and executable by, a particular computer. Thus, in this case, the computer program itself constitutes the procedure, and the individual statements of this program comprise its steps.

That a computer program constitutes a procedure is clearly evident if the programming language employed is procedural; that is, the statements in the programming language take the form of explicit instructions which the computer is expected to carry out. That a computer program constitutes a procedure may not be evident when the programming language is one of those which is described as descriptive or declarative. The statements of such languages take the form, for the most part, of assertions, declarations, or predications, together with statements which can be construed as questions, queries, or interrogations regarding facts or relationships established by the declarative statements. These declarations and interrogations, however, implicitly invoke procedures which are performed by the computer to establish and store the information contained in the declarations, and to answer the questions about this information posed by the interrogative statements.

Examples of procedures for tasks that human beings are intended to perform include cooking recipes, sewing and knitting instructions, and instructions for assembling furniture or toys purchased as kits or in partially assembled form. Of course, recipes and assembly instructions can be considered procedures only when they meet the conditions of a procedure; namely, that the instructions are in a language and form which is comprehensible to the cook or the person doing the assembling, and which describes completely, at an adequate level of detail, what is to be done at each stage of the task, that the instructions consist of a finite number of discrete steps in an order which is appropriate to the successful completion of the task, and that the instructions accommodate any eventuality that might arise in the course of the task.

Recipes generally meet the "discrete steps" condition, and invariably satisfy the "finite number of steps" condition; but, a recipe calling for a "pinch" of salt or a "warm" oven, or instructing the cook to bake something for "about" 15 minutes or "until brown" could be considered to violate the condition that each step be precisely described. Instructions which tell the assembler to put nut B on bolt A, and then say to put on the lock washer would violate the ordering of steps condition. If there were no nut B in the kit, but there is an extra wing nut C which could be used in place of nut B, and this possibility is not mentioned in the the instructions, then the condition that all eventualities be accommodated would be violated.

Examples of problem-solving procedures intended to be performed by people, but which are more closely related to the procedures encountered in computational linguistics and formal language theory than those cited immediately above, include the rules and operations for doing long division and for "parsing" simple sentences learned in elementary school, and the instructions for using an electronic calculator to add two numbers together. Although the collection of parsing rules learned in elementary school likely would not satisfy all the conditions for a procedure, the set of operations for long division and for using a calculator likely were described in a form which would satisfy these conditions.

For example, the instructions for adding two number together using a calculator might consist of the following, depending upon the particular calculator: 1) Press the keys for the first number; 2) Press the "+" key; 3) Press the keys for the second number; and, 4) Press the "=" key. This sequence of operations constitutes a procedure, and the four steps comprising it are sufficiently precisely described that most people would be able to perform them to achieve the goal of obtaining the sum of the two numbers on the calculator's display.

The steps of a procedure normally are the simplest, most basic operations which are consistent with the capabilities of the agent or device intended to perform the procedure. For example, the step in the procedure for adding two numbers using a calculator which consists of the instruction to "press the keys for the first number" should be sufficiently simple and basic for most people. If necessary, however, this instruction can be broken down into simpler, more basic operations. In this case, the first step of the procedure, as it was described above, might actually consist of the following more basic steps: 1a) Begin with the first digit of the number, and press the key corresponding to this digit; 1b) Go to the next number, and press the key corresponding to it; 1c) Repeat step (1b) until there are no more digits.

While the level of detail concerning the operations comprising the steps of a procedure must be consistent with the capabilities of the device or agent performing the procedure, it is unnecessary to provide more detail than that which is minimally required. Thus, it is not necessary to provide any information whatsoever about how the device being operated, such as the calculator, actually executes the operations. It is sufficient for the operator of the calculator to be informed about the basic operations entailed in using it, such as what keys to press, and in what order. The person does not need to know how the calculator "reads" the keys which are pressed, how it stores the first number, and how it performs the addition of the first number to the second. Similarly, a person employing one of the high-level programming languages to prepare a procedure for a computer need not know, nor need he describe, how the machine "reads" the data upon which it is to work: it is sufficient to specify the statement which is interpreted by the computer as an instruction to "read" data.

The calculator example illustrates an important attribute of procedures; namely, that they may contain loops consisting of one or more steps or instructions which are performed one or more times. The repetition or iteration of a sequence of steps is effected by a branch or go to instruction which causes a specified step, different from the one immediately following in the procedure, to be performed next. The repetition of the sequence of steps within the loop is stopped by means of a test or condition. In the calculator example, the pressing of keys to enter digits is stopped when the condition that there are no more digits is met.

Cooking recipes also frequently contain loops, in conjunction with tests, which may not be readily recognised as such. For example, the instruction to "stir until mixed" consists of a step in a procedure, where the step in this case may be viewed as one turn of a spoon about a bowl, together with the test "until mixed", which suggests that after each turn of the spoon, the contents of the bowl be tested to determine if they are mixed (the vagueness of the term "mixed" notwithstanding). If they are not yet mixed, another turn is made, that is, the stirring loop is continued. When the condition of the test is satisfied, namely that the contents of the bowl are mixed, then the stirring loop is discontinued.

Branching to another step, different from the next one in the sequence of steps in the procedure, need not necessarily be associated with a loop. Branching on the basis of a condition met by the data, or intermediate results derived from the data, may cause different sequences of steps to be performed. Consequently, those steps of a procedure actually performed may depend upon the data for a particular problem, and the sequence in which the steps of a particular procedure are performed may vary from problem to problem.

For example, cooking recipes contain branches which cause some steps to be performed only under certain circumstances. A recipe for jam may contain the instruction to add pectin if the fruit is not ripe enough, or to add sugar if the jam is not thick enough after heating for a prescribed time at a particular temperature. If the fruit is not sufficiently ripe, the steps involved in adding pectin will be performed, while if it is ripe, the pectin adding steps will be skipped.

The sequence of steps for entering a number digit by digit into a calculator could be used for both the first and second of the two numbers to be added. Thus, this sequence could appear twice in the procedure, or it might be included once, with branch instructions being used to direct the person using the calculator to follow them whenever a number is to be entered. The last step of the digit-entering sequence then might consist of an instruction to return to that step of the procedure immediately following the one consisting of the instruction to go to the digit-entering sequence. In this case, the digit-entering sequence represents an example of what may be called a subprocedure.

A subprocedure is a sequence of steps which form part of a procedure, but which can be distinguished or separated from the other steps, and which can be, in effect, branched to, or used, by any step in the procedure. A subprocedure meets all the criteria for a procedure, with the exception that it is not intended to be performed independently of the procedure of which it is a part. To facilitate the branching to the sequence of steps comprising it, a subprocedure usually is named or identified in some way. The instruction to perform a subprocedure then might be effected implicitly merely by citing its name, or by "calling" the subprocedure by name when its steps are to be performed. The word "call" is often used to describe the branching to a subprocedure, and the subprocedure is thought of as being invoked to perform a specific subtask, or to solve a particular subproblem.

When a procedure is intended to be performed by a computer, and is described using a procedural programming language, the subprocedures usually are referred to as subprograms or subroutines, or as function subprograms. It is often the case that subprograms or subroutines are invoked explicitly using the word call, followed by the subprocedure name, while subprocedures of the function subprogram type are invoked implicitly by referring to their name in a step of a procedure.

The information required while a subprocedure is being performed might be shared in common with the whole procedure of which the subprocedure is a part. Such information is said to be global. Information used only by the subprocedure, typically consisting of intermediate quantities not needed by other parts of the procedure, are described as local.

For example, consider the digit-entering subprocedure of the procedure for using a calculator, and assume that the digits of a number to be added are removed from the number as each digit is entered. This process would leave fragments of the original number which become smaller as each digit is removed and entered. These fragments then could be viewed as local quantities because they are not required elsewhere in the procedure.

Some information which is required while a subprocedure is being performed can be provided or passed to it by means of arguments. The number to be entered into a calculator, for example, might be viewed as being passed as an argument of the digit-entering subprocedure. Some subprocedures, such as the subprograms of a computer program which are explicitly "called", also return information to the "calling" steps of the procedure by means of arguments. Other subprocedures, typically the function subprograms which are used merely by citing their name, return information to the step containing their name in the location occupied by their name.

The passing of information to, and the return of information from, a subprocedure can be illustrated with the following procedure for determining whether or not a given string a is a sentence in the language L(G) generated by a grammar G. The productions of G might be applied by a subprocedure. The string a could be provided or passed to this subprocedure as an argument. When the subprocedure is performed, the productions might be tested one at a time against the string, employing the right-hand side as the condition. If a match is obtained, the matching substring could be replaced by the left-hand side of the production, and the resulting modified string returned to the "calling" step of the procedure.

The procedure "calling" the production-applying subprocedure might contain a loop which causes this subprocedure to be "called" repeatedly. At each iteration of this loop, the string modified in the previous "call", by replacing the substring which matches the right-hand side of a production by the left-hand side of the production, might be passed to the subprocedure. The loop might include a step in which the modified string returned from the subprocedure is tested to determine if it consists only of the root symbol of the grammar. If it does, then a is recognised as a sentence in L(G). If this test fails, then another iteration of the loop is performed. If no more productions can be applied by the subprocedure, and the modified string is not the root symbol of the grammar, then a is not recognised as a sentence in L(G).

While subprograms are employed often in procedures intended to be performed by computers, subprocedures also occur in procedures intended for human beings. Cooking recipes, for example, frequently use subprocedures to describe the preparation of components such as sauces and dressings which are common to a number of different dishes. Rather than including a description of how to make a gravy in every recipe requiring a gravy, the procedure for this task might be included separately in a cook book, and be referred to or "called" in other recipes throughout the book which require a gravy. Such components might have, and be referred to, by a unique name, such as Hollandaise Sauce, for example.

In the foregoing example of sauce recipe, the stock or drippings from the boiling or roasting of meat according to one recipe may be viewed as analogous to the "data" which, in this case, might be passed to a sauce-making subrecipe. This subrecipe, if it is regarded as a function-type subprocedure, may be viewed as returning the sauce as its "value".

The iteration or repetition of a sequence of steps in a procedure usually is effected by means of branch or go to instructions. Another device whereby steps may be repeated makes use of a subprocedure. Ordinarily, the steps comprising a subprocedure are repeated by repeatedly "calling" the subprocedure within a loop. A repetition of the steps comprising a subprocedure also may be effected, however, by having the subprocedure "call" itself. The "calling" of a subprocedure by itself is described as recursion.

The subprocedure which is "called" in this fashion might be thought of as another copy of the "calling" subprocedure. Although recursion can in fact be performed employing multiple copies of the one procedure, it is more normally the case that only one copy is used, and this copy is "re-entered". Before the "re-entry" occurs, however, all the information currently being used in the subprocedure is saved by pushing it onto a stack. On "re-entry", the subprocedure starts anew with whatever information might be provided in its arguments. On return, the information previously stored is recovered by popping it from the stack in which it was saved.

The digit-entering subprocedure of the calculator procedure can be described in such a way as to employ recursion. When the subprocedure is "called" to enter a number, the number can be passed as an argument. The subprocedure removes the left-most digit and enters it into the calculator. The subprocedure then can "call" itself, passing the number, with the left-most digit removed, as the argument. The subprocedure is restarted or re-entered, and the left-most of the remaining digits of the number is removed and entered into the calculator. The subprocedure "calls" itself again, passing the remaining fragment of the number.

The digit-removal step of the subprocedure can include a test to determine if any digits remain. The subprocedure "calls" itself only if a digit can be removed; otherwise, it returns to the "calling" procedure, or subprocedure. Furthermore, the last step of the subprocedure, following the "call" to itself, consists of an instruction to return to the procedure which "called" it.

Thus, if the number to be entered consists of only one digit, the subprocedure will remove that one digit, enter it into the calculator, and "call" itself, passing a number with no digits. The "copy" of the subprocedure which is "called" will determine that a digit cannot be removed, and will return to the "copy" of the subprocedure which "called" it. Since the step in the subprocedure following the "call" step is a return instruction, the subprocedure returns to the procedure which "called" it initially. The same sequence of steps will be performed if the number consists of more digits, the only difference being that more "copies" of the subprocedure will be "called", the number of such "copies" being equal to the number of digits in the number to be entered in the calculator, plus the "copy" which determines that there are no more digits.

Both iteration or recursion represent methods for effecting the repetition of a sequence of steps in a procedure. For many problems, the two are equally efficacious and either method may be employed to obtain the solutions to these problems, and in such cases, the decision whether to use iteration or to use recursion may be simply a matter of preference on the part of the author of the procedure. In other cases, however, depending perhaps upon the agent or device intended to perform the procedure, iteration and recursion may not be equally efficacious, and for some problems, one method may be more appropriate than the other.

An example wherein recursion could be considered more appropriate than iteration might be found in a procedure for determining if a given string a is a sentence in the language L(G). While either iteration or recursion might be employed to effect the repeated application of the productions of G to a and the sentential forms derived from it, recursion might be preferred because recursive subprocedures save the information they are working on before they "call" themselves, and then restore this information in its previous form when they return. Thus, information is unchanged by whatever other processing might have been performed in subsequent "calls".

A recognition procedure might taken advantage of this automatic saving and restoring of information in the following way. A recursive subprocedure might apply one production, then "call" itself to apply another, and so on, until a is recognised, or rejected, as a sentence. The information saved before the subprocedure "calls" itself can consist of the sentential form produced by applying one of the productions. When the subprocedure returns, this sentential form, as it was before the the next production was applied, is restored. Thus, if more than one production can be applied to a sentential form, and the one first applied at a particular stage leads to a not being recognised as a sentence, then the restoring of the sentential form as it was before the inappropriate production was applied enables the recognition procedure to apply another production which could result in a being recognised as a sentence.

Thus, the use of recursion in a recognition procedure enables the recogniser to back up, in effect, and try alternative paths, if these are available, which may lead to recognition of a string as a sentence. The action of backing up to try alternatives often is referred to as backtracking. Backtracking can be effected by a procedure which employs iteration rather than recursion; however, more effort is required on the part of the author of the procedure to prepare instructions for saving and restoring information, actions which are automatically performed by recursive subprocedures. Recursion may also be more efficacious then iteration, depending upon the device performing the procedure, which is normally a computer, and the programming languages employed.

Recursion might also be employed in the specification of the productions of a grammar, both to avoid prolixity, but also, and more importantly, to avoid the imposition of inappropriate limitations. For example, consider the following productions from a context free grammar:

NP ® Det N
NP ® NP PP
PP ® P NP

As it stands, this production describes a relationship among the constituents of a sentence, according to the grammar of which it is a part. In a sense, however, this production also may be viewed, from a procedural rather than a descriptive perspective, as a subprocedure which "calls" itself. In fact, its application in a recognition procedure can be performed by a recursive subprocedure.

To simplify matters somewhat, we consider an example in which the three foregoing productions are applied by a subprocedure named NP, which is part of a top-down recognition procedure. Note that boldface type is used here to denote a procedure name while the corresponding syntactic category label is represented with italic or "slanted" type. The procedure NP might "call" other subprocedures named Det, N, and P to test the data string for determiners, nouns, and prepositions, respectively. Initially, NP might be called by another subprocedure named VP, which applies a production such as VP ® V NP.

On being "called" by VP, NP "calls" Det to determine if the current data symbol is a determiner. If Det fails, then in this example the data string is not recognised as a sentence. If Det succeeds, NP "calls" N to determine if the next symbol is a noun. If N fails, then the string is not recognised as a sentence. If it succeeds, NP then "calls" P to determine if the third data symbol is a preposition. If P fails, then NP has recognised a noun phrase such as, for example, "the cat".

If the "call" to P succeeds, a preposition has been identified. NP then "calls" itself to repeat the process described above. In this case, if the "calls" to Det and N succeed; but, the "call" to P fails, then NP has recognised a noun phrase such as, for example, "the cat with the kittens". If, however, the "call" to P succeeds on this second entry into NP, then NP "calls" itself a second time, and the process described above will be repeated. As a consequence, the noun phrase complement of the preposition found previously might be identified; but, another preposition might not be identified. In this case, the NP subprocedure might have recognised a phrase such as "the cat with the kittens in the field", then returned to itself twice, and finally returned to the VP subprocedure which "called" it initially.

A third preposition, however, might have been identified, and in this event, NP will "call" itself again to identify the complement, and hence, recognise a third prepositional phrase. This recursion of NP, as performed by the NP subprocedure, might continue until a phrase such as "the cat with the kittens in the field by the road to the barn near the pond at the bottom of the hill" is finally recognised.

While the NP recursion will terminate in practice after relatively few prepositional phrases have been recognised, and the subprocedure NP fails to identify another preposition, there is in principle no limitation on the number of such phrases, provided that there are a finite number of them. It is this absence of limitation, together with the capability to accommodate an indefinite number of constituents such as the prepositional phrase used in this example, which both justifies and motivates the use of recursion in the productions of a grammar. Any other device either would impose unrealistic limitations, or would be pleonastic.

A procedure, by definition, can consist of only a finite number of steps. As a consequence of iteration and recursion, however, some sequences of steps many be performed a large number of times, perhaps even infinitely many, depending upon the procedure itself, and whether or not it contains iterated steps or recursive subprocedures, but also upon the particular problem or task.

For example, a procedure which employs iteration or a recursive subprocedure to list or enumerate positive integers or the sentences of a language might consist of relatively few steps. If, however, this procedure were used to enumerate "all" the positive integers, or the sentences of an infinite language, that is, a language with infinitely many different sentences, then the steps in the loop or in the recursive subprocedure would be performed infinitely many times. Only when this procedure is used to enumerate just the first n positive integers, or the sentences in a finite language, would a finite number of steps be performed.

A semi-algorithm is a procedure for solving a problem or performing a task which, if the problem has a solution or the task has an attainable goal, yields a solution or attains the goal after a finite number of steps have been performed.

In the context of formal language theory, if a string a over the vocabulary V_T is a sentence in a particular language L(V_T), then a procedure which confirms this fact in at most finitely many steps is a semi-algorithm. If, however, a is not a sentence in L(V_T), then a semi-algorithm will not necessarily confirm this fact in a finite number of steps.

The concept of the semi-algorithm is introduced because it is inherent in the nature of some problems and tasks that, although they possess a solution or an attainable goal, any procedure will require infinitely many steps to yield a solution or goal. For such problems and tasks there is no procedure which is a semi-algorithm, and hence, while these problems and tasks may indeed have solutions, they are intractable in practice. The enumeration of all the sentences in an infinite language is an example of such a task or problem.

The concept of the semi-algorithm is also important because it is possible that there be a number of different procedures for solving one given problem, or for achieving the goal of one given task. While some of these may yield a solution or goal in finitely many steps, and hence be designated semi-algorithms, others may require infinitely many. Thus, the semi-algorithms comprise that subset of the procedures for a given task or problem which are feasible in principle, with the caveat in principle being attached because, although semi-algorithms yield a solution or goal in finitely many steps, the actual number of steps performed may be quite large.

A semi-algorithm for a problem or task is a procedure which is guaranteed to yield a solution or a goal only if the problem has a solution or the task an attainable goal. If, however, the problem has no solution or the task no attainable goal, then a finite number of steps may be sufficient to discover this fact, or infinitely many steps may be required.

An algorithm is a procedure for a problem or task which determines in a finite number of steps whether or not the problem is solvable or the goal attainable and, if a solution or attainable goal exists, yields a solution or goal in a finite number of steps. Thus, an algorithm is a semi-algorithm, but with the additional condition attached that it also indicates when a problem is insolvable or a goal is unattainable.

An algorithm is a procedure which, if a string a over an vocabulary V_T is a sentence in the language L(V_T), will recognise a as a sentence in a finite number of steps; but which also, if a is not a sentence in L(V_T), that is, a Î L^c(V_T), will determine this fact in finitely many steps.

It may be inherent in the in the nature of some tasks or problems that no mechanism can be devised whereby a procedure might detect that the problem is insolvable or that the goal is unattainable. Hence, infinitely many steps of a procedure may be performed without there being any indication that the problem is insolvable or the goal unattainable. For such tasks and problems, there is no procedure which is an algorithm. (In connection with tasks and problems of this nature, note that the condition on a procedure that it take into account all possible circumstances which might arise while it is being performed means only that the procedure can be carried out automatically, and does not mean that the procedure necessarily can determine when a problem is insolvable or a goal is unattainable.)

An example of a problem in formal language theory for which there is no procedure which is an algorithm can be found in the languages generated by the Chomsky Type 0 grammars, that is, the grammars with unrestricted productions. For any Type 0 language, a semi-algorithm can be devised which will recognise a string if it is a sentence in the language. There exist Type 0 languages, however, such that if a string is not a sentence, there is no procedure which will determine this fact in finitely many steps. Hence, for some Type 0 languages there is no algorithm for determining whether or not a particular string is a sentence.

Some problems or tasks, such as those for deciding whether of not a given string is a sentence in a particular language, require only a "yes" or "no" solution or result. A procedure for such a problem or task, the objective of which is to yield the "yes" or "no" result, is called a decision procedure. Thus, a recogniser for a language is an example of a decision procedure.

A procedure which halts, that is, yields the result "yes" in a finite number of steps when the string is a sentence, but which does not necessarily halt when the data string is not a sentence, is called a decision semi-algorithm. A procedure for the problem which halts regardless whether or not the string is a sentence, that is, it yields the result "yes" in finitely many steps when the data string is a sentence, but yields the result "no" in a finite number of steps when it is not, is called a decision algorithm.

A problem requiring only a "yes" or "no" result, such as the problem of determining whether or not a string is sentence, is described as algorithmically decidable if, and only if, there exists a procedure for solving it which is a decision algorithm. A language is described as decidable or recursively decidable or recursive if, and only if, there exists a decision algorithm for determining whether or not an arbitrary string is a sentence in the language.

Since there are Type 0 languages for which there exists no decision algorithm, these languages are, in general, undecidable. It is known, however, that for any language generated by a Chomsky Type 1, 2, or 3 grammar there exist decision algorithms. Therefore, the Type 1, 2, and 3 languages, that is, the context sensitive, the context free, and the finite or regular languages, respectively, are decidable.

Linguistics 484

Notes Index

Top of Page