The "oracle" program Abdullah Mohd Zin Eric Foxley Department of Computer Science University of Nottingham NOTTINGHAM NG7 2RD, UK email: amz, ef @ cs.nott.ac.uk ====================================================================== Note: Revision 3.2 October 23, 1996 ====================================================================== 1. Introduction A program which recognises whether a given piece of text contains a particular required meaning is called an "ora- cle".[3] This type of activity is vital in several areas of CEILIDH. It is used in CEILIDH to check that the output from the dynamic tests of a program represent "correct" out- put,[1] that program sources do or do not contain particular features, and that the answers to multiple choice questions contain appropriate valid words.[2] 2. Implementation The implementation uses the UNIX concept of a Regular Expression or "RE". REs are involved in many UNIX commands, text editors, the "sed" stream editor, the "grep" family of commands, and "awk". To check program output, the teacher provides a number of regular expressions which will be searched for in the text. These REs will be given one-per-line in a file whose name is supplied as the first argument in a call of the "oracle" program. The implementation of the "oracle" program uses "awk" to detect the REs, so exact details of the RE formats are to be found in "awk" documentation. The program "oracle" reads from its first argument a file of regular expressions (REs), to act as an oracle. They are converted to selection strings for an "awk" program, which then reads the text to be analysed from its standard input. The output of the "awk" program is of the form Score 93 which is a percentage of the mark awarded out of the max possible mark depending which REs were found. The REs must be awk-type REs, see "awk" documentation for exact details. Each line of the file of REs is of the form RE default 10 marks awarded if RE found at least once, no marks awarded of not found. Examples 127 the string "127" 127.3 the string "127" followed by any one character, followed by a "3" 127\.3 the string "127.3" cat|dog the string "cat" or the string "dog" [Ff]e*t the string "Ft", "ft", "Feet" or "feet" ^cat a line starting with the string "cat" cat$ a line ending with the string "cat" ^cat$ a line consisting of exactly the string "cat" 3. Extensions to the REs The RE may be preceded by colon separated fields such as 5:RE 5 marks awarded if RE found. The default is 10 marks. 15:>5:RE 15 marks awarded if > 5 occurrences found, zero marks if <= 5. 10:>=5:RE 10 marks awarded if >= 5 occurrences found, zero marks if < 5. <5:RE Default marks awarded if < 5 occurrences found, zero marks if >= 5. <=5:RE Default marks awarded if <= 5 occurrences found, zero marks if > 5. ==1:RE Default marks awarded if exactly 1 occurrence found. !=1:RE Default marks awarded if more or less than 1 occurrence. >=4-10:RE Default marks if >=10, zero marks if <=4, interpolated marks if between 4 and 10. +:RE This RE must occur AFTER the previous RE. -:RE The previous RE must NOT have been found before this one. ~10:RE If the RE is found, 10 marks are taken away. The 10 marks are not included in the maximum total out of which the mark gained is scaled as a percentage. Marks will never go negative. Any colon required in the RE must be escaped. The maximum mark (out of which the awarded percentage is calculated) is the total of all the positive possible marks, default 10 per RE unless otherwise specified. If there is a line such as :50,20;80,40;90,60 in the oracle file (starting with a colon, consisting of pairs of integers) the percentage will be piecewise linear scaled, so that 0 goes to 0 50 goes to 20 80 goes to 40 90 goes to 60 100 goes to 100 with linear interpolation between these points. If there are 10 REs consisting of error messages which must be absent such as ==0:delivers a random you may wish to scale the marks so that the presence of any one of them immediately reduces the mark to, say 50%. Any prime "'" in an RE is currently converted to a dot "." to avoid shell script problems driving the "awk" program. We should be more clever and escape it properly. 4. Flags to the oracle program Flag "-v1" causes the "awk" program to print subtotals. Flag "-v2" prints the actual REs it is searching for, and then for each one tabulates the required minimum and maximum number of occurrences demanded by the oracle file, the actual number of occurrences found, the awarded score, the maximum score (out of), and the accumulated score so far, and the marks lost on this RE. Flag "-v3" prints the "awk" program which has been generated to the screen. A numeric first non-flag argument such as oracle 20 RE_FILE sets the default mark per RE to 20. 5. SUID facility The program will normally be SUID to enable the file of REs (which is opened from within the program) to be kept hidden from the user. The files of REs will generally have no pub- lic read permission. 6. The use of oracles in CEILIDH Oracles are used in four separate areas of CEILIDH as a con- venient means of checking general text. 6.1. Dynamic test output The program's output must be examined to see if the student has solved the given problem correctly. The more precisely the question specifies the output format, the easier the oracle. Generating flexible REs to allow flexible output formats requires thought and experience. To avoid problems, you may choose to specify the output format very exactly, or to give the necessary print commands to the student in the program skeleton. For "Convert feet and inches to centimetres" I have several dynamic tests. The oracle for the first test looks simply for the correct numeric output value, the RE is perhaps 134\.57 (but beware of rounding errors and numbers of decimal places, so perhaps the RE should be 134\.(6|57)|135 Later tests look additionally for the text "cms" or "centimetres" which any civilised output should con- tain. Later tests check that the input values have been printed as in the output, as in 12 feet 3.4 inches converts to 12345.67 cms so checks also for the input values and text such as "fe*t". We may also wish to check for error messages in appropriate cases: 20:[Ee]rror and to ensure their absence in outher cases: ==0:[Ee]rror to ensure that the student does not always print "Error"! The standard and error outputs are currently combined for the oracle. Flexibility causes the teacher more trouble, but is educa- tionally much better. 6.2. Program features For particular programs, the program features oracle will check that, for example, constants such as 2.54 (convert centimetres to inches) occur exactly once in the source, using the RE line ==1:2\.54 (where the "==1:" prefix requires exactly one occurrence) in the "model.ft" oracle. This oracle is set by the "sf" teacher option, and should represent any features which the lecturer would look for "by eye" in hand marking. The contents of comments and strings are NOT passed to this oracle. 6.3. Program structure In the structure marking feature, the C programs are run through the "lint" checker, and the output searched by an oracle for particular warning messages. For C++ we use the "g++ -Wall" option. A typical oracle would be ==0:Undefined symbol.*referenced from text segment ==0:undeclared ==0:redeclared as different kind of symbol ==0:assignment of integer from pointer lacks a cast ==0:comparison is always 1 due to limited range of data type ==0:data definition lacks type or storage class ==0:defined but not used ==0:float or double assigned to integer data type ==0:previous declaration of ==0:statement with no effect ==0:unused variable ==0:value computed is not used :90,40;100,100 to give 100 marks for no warnings, 40 marks if there is 1 warning, less if there are more. The particular messages depend, of course, on your program analyser. 6.4. Multi-choice questions The script for a multi-choice problem include the text displayed to the student, followed after each "page" displayed by an oracle line to recognise the output. If the text says "Type a, b, c or d:" then you should recog- nise the answer "b" using the RE ^b$ rather than simply b to ensure that the student cannot type the reply abcd Most student answers are one-line replies. If the multi- line option is used, the complete text is put onto one line before the oracle is applied. If you are looking for a given word, give all possible alternatives, such as (ferrous|iron) *oxide Other oracles are available for the question-answer system, see its document for details. References 1. Steve Benford, Edmund Burke, and Eric Foxley, Teacher's Guide to the Ceilidh System 2.4, 1995. LTR Report, Computer Science Dept, Nottingham University 2. Eric Foxley, Question/answer exercises in Ceilidh, 1993. LTR Report, Computer Science Dept, Nottingham University 3. E. W. Weyuker, "On Testing non-testable program," The Computer Journal, vol. 25, no. 4, pp. 465-470, Nov 1982.