In this chapter we discuss four algorithms for computing answer sets of ground AnsProlog* programs. The first three algorithms compute answer sets of ground AnsProlog programs while the fourth algorithm computes answer sets of ground AnsPrologor programs. In Chapter 8 we will discuss several implemented systems that compute answer sets and use algorithms from this chapter.

Recall that for ground AnsProlog and AnsPrologor programs π answer sets are finite sets of atoms and are subsets of HBMπ. In other words answer sets are particular (Herbrand) interpretations of π which satisfy additional properties. Intuitively, for an answer set A of π all atoms in A are viewed as true with respect to A, and all atoms not in A are viewed as false with respect to A. Most answer set computing algorithms – including the algorithms in this chapter – search in the space of partial interpretations, where in a partial interpretation some atoms have the truth value true, some others have the truth value false and the remaining are considered to be neither true nor false. In the first three algorithms in this chapter the partial interpretations are 3-valued and are referred to as 3-valued interpretations, while in the fourth algorithm the partial interpretation that is used is 4-valued. Recall that we introduced 3-valued interpretations in Section 6.6.9, and that in 3-valued interpretations the atoms which are neither true not false have the truth value unknown.

In this chapter we present several fundamental results that are useful in analyzing and step-by-step building of AnsProlog* Programs, viewed both as stand alone programs and as functions. To analyze AnsProlog* programs we define and describe several properties such as categoricity (presence of unique answer sets), coherence (presence of at least one answer set), computability (answer set computation being recursive), filter-abducibility (abductive assimilation of observations using filtering), language independence (independence between answer sets of a program and the language), language tolerance (preservation of the meaning of a program with respect to the original language when the language is enlarged), compilabity to first-order theory, amenabity to removal of or, and restricted monotonicity (exhibition of monotonicity with respect to a select set of literals).

We also define several subclasses of AnsProlog* programs such as stratified, locally stratified, acyclic, tight, signed, head cycle free and several conditions on AnsProlog* rules such as well-moded and state results about which AnsProlog* programs have what properties. We present several results that relate answer sets of an AnsProlog* program to its rules. We develop the notion of splitting and show how the notions of stratification, local stratification, and splitting can be used in step-by-step computation of answer sets.

For step-by-step building of AnsProlog* programs we develop the notion of conservative extension – where a program preserves its original meaning after additional rules are added to it, and present conditions for programs that exhibit this property.

Representing knowledge and reasoning with it are important components of an intelligent system, and are two important facets of Artificial Intelligence. Another important expectation from intelligent systems is their ability to accept high level requests – as opposed to detailed step-by-step instructions, and their knowledge and reasoning ability are used to figure out the detailed steps that need to be taken. To have this ability intelligent systems must have a declarative interface whose input language must be based on logic.

Thus the author considers the all-round development of a suitable declarative knowledge representation language to be a fundamental component of knowledge based intelligence, perhaps similar to the role of the language of calculus to mathematics, and physics. Taking the calculus analogy further, it is important that a large support structure is developed around the language, similar to the integration and derivation formulas and the various theorems around calculus.

Although several languages have been proposed for knowledge representation, the language of AnsProlog* – logic programming with the answer set semantics, stands out in terms of the size and variety of the support structure developed around it. The support structure includes both implementations and use of the implementations in developing applications, and theoretical results for both analyzing and step-by-step building of theories (or programs) in this language. The support structure and the desirable properties of the language are also a testimony to the appropriateness of the language for knowledge representation, reasoning, and declarative problem solving.

Chapters 2–11 have described the fundamental components of a good compiler: a front end, which does lexical analysis, parsing, construction of abstract syntax, type-checking, and translation to intermediate code; and a back end, which does instruction selection, dataflow analysis, and register allocation.

What lessons have we learned? We hope that the reader has learned about the algorithms used in different components of a compiler and the interfaces used to connect the components. But the authors have also learned quite a bit from the exercise.

Our goal was to describe a good compiler that is, to use Einstein's phrase, “as simple as possible – but no simpler.” we will now discuss the thorny issues that arose in designing the MiniJava compiler.

Structured l-values. Java (and MiniJava) have no record or array variables, as C, C++, and Pascal do. Instead, all object and array values are really just pointers to heap-allocated data. Implementing structured l-values requires some care but not too many new insights.

Tree intermediate representation. The Tree language has a fundamental flaw: It does not describe procedure entry and exit. These are handled by opaque procedures inside the Frame module that generate Tree code. This means that a program translated to Trees using, for example, the Pentium- Frame version of Frame will be different from the same program translated using SparcFrame – the Tree representation is not completely machine-independent.

This book is intended as a textbook for a one- or two-semester course in compilers. Students will see the theory behind different components of a compiler, the programming techniques used to put the theory into practice, and the interfaces used to modularize the compiler. To make the interfaces and programming examples clear and concrete, we have written them in Java. Another edition of this book is available that uses the ML language.

Implementation project. The “student project compiler” that we have outlined is reasonably simple, but is organized to demonstrate some important techniques that are now in common use: abstract syntax trees to avoid tangling syntax and semantics, separation of instruction selection from register allocation, copy propagation to give flexibility to earlier phases of the compiler, and containment of target-machine dependencies. Unlike many “student compilers” found in other textbooks, this one has a simple but sophisticated back end, allowing good register allocation to be done after instruction selection.

This second edition of the book has a redesigned project compiler: It uses a subset of Java, called MiniJava, as the source language for the compiler project, it explains the use of the parser generators JavaCC and SableCC, and it promotes programming with the Visitor pattern. Students using this edition can implement a compiler for a language they're familiar with, using standard tools, in a more object-oriented style.

The mathematical notion of function is that if f(x) = a “this time,” then f(x) = a “next time”; there is no other value equal to f(x). This allows the use of equational reasoning familiar from algebra: If a = f(x), then g(f(x), f(x)) is equivalent to g(a, a). Pure functional programming languages encourage a kind of programming in which equational reasoning works, as it does in mathematics.

Imperative programming languages have similar syntax: a → f(x). But if we follow this by b → f(x), there is no guarantee that a = b; the function f can have side effects on global variables that make it return a different value each time. Furthermore, a program might assign into variable x between calls to f(x), so f(x) really means a different thing each time.

Higher-order functions. Functional programming languages also allow functions to be passed as arguments to other functions, or returned as results. Functions that take functional arguments are called higher-order functions.

Higher-order functions become particularly interesting if the language also supports nested functions with lexical scope (also called block structure). Lexical scope means that each function can refer to variables and parameters of any function in which it is nested. A higher-order functional language is one with nested scope and higher-order functions.

The semantic analysis phase of a compiler must translate abstract syntax into abstract machine code. It can do this after type-checking, or at the same time.

Though it is possible to translate directly to real machine code, this hinders portability and modularity. Suppose we want compilers for N different source languages, targeted to M different machines. In principle this is N · M compilers (Figure 7.1a), a large implementation task.

An intermediate representation (IR) is a kind of abstract machine language that can express the target-machine operations without committing to too much machine-specific detail. But it is also independent of the details of the source language. The front end of the compiler does lexical analysis, parsing, semantic analysis, and translation to intermediate representation. The back end does optimization of the intermediate representation and translation to machine language.

A portable compiler translates the source language into IR and then translates the IR into machine language, as illustrated in Figure 7.1b. Now only N front ends and M back ends are required. Such an implementation task is more reasonable.

Even when only one front end and one back end are being built, a good IR can modularize the task, so that the front end is not complicated with machine-specific details, and the back end is not bothered with information specific to one source language. Many different kinds of IR are used in compilers; for this compiler we have chosen simple expression trees.

A compiler must do more than recognize whether a sentence belongs to the language of a grammar – it must do something useful with that sentence. The semantic actions of a parser can do useful things with the phrases that are parsed.

In a recursive-descent parser, semantic action code is interspersed with the control flow of the parsing actions. In a parser specified in JavaCC, semantic actions are fragments of Java program code attached to grammar productions. SableCC, on the other hand, automatically generates syntax trees as it parses.

SEMANTIC ACTIONS

Each terminal and nonterminal may be associated with its own type of semantic value. For example, in a simple calculator using Grammar 3.37, the type associated with exp and INT might be int; the other tokens would not need to carry a value. The type associated with a token must, of course, match the type that the lexer returns with that token.

For a rule A → B C D, the semantic action must return a value whose type is the one associated with the nonterminal A. But it can build this value from the values associated with the matched terminals and nonterminals B, C, D.

RECURSIVE DESCENT

In a recursive-descent parser, the semantic actions are the values returned by parsing functions, or the side effects of those functions, or both.

A simple computer can process one instruction at a time. First it fetches the instruction, then decodes it into opcode and operand specifiers, then reads the operands from the register bank (or memory), then performs the arithmetic denoted by the opcode, then writes the result back to the register back (or memory), and then fetches the next instruction.

Modern computers can execute parts of many different instructions at the same time. At the same time the processor is writing results of two instructions back to registers, it may be doing arithmetic for three other instructions, reading operands for two more instructions, decoding four others, and fetching yet another four. Meanwhile, there may be five instructions delayed, awaiting the results of memory-fetches.

Such a processor usually fetches instructions from a single flow of control; it's not that several programs are running in parallel, but the adjacent instructions of a single program are decoded and executed simultaneously. This is called instruction-level parallelism (ILP), and is the basis for much of the astounding advance in processor speed in the last decade of the twentieth century.

A pipelined machine performs the write-back of one instruction in the same cycle as the arithmetic “execute” of the next instruction and the operand-read of the previous one, and so on. A very-long-instruction-word (VLIW) issues several instructions in the same processor cycle; the compiler must ensure that they are not data-dependent on each other.

An idealized random access memory (RAM) has N words indexed by integers such that any word can be fetched or stored – using its integer address – equally quickly. Hardware designers can make a big slow memory, or a small fast memory, but a big fast memory is prohibitively expensive. Also, one thing that speeds up access to memory is its nearness to the processor, and a big memory must have some parts far from the processor no matter how much money might be thrown at the problem.

Almost as good as a big fast memory is the combination of a small fast cache memory and a big slow main memory; the program keeps its frequently used data in cache and the rarely used data in main memory, and when it enters a phase in which datum x will be frequently used it may move x from the slow memory to the fast memory.

It's inconvenient for the programmer to manage multiple memories, so the hardware does it automatically. Whenever the processor wants the datum at address x, it looks first in the cache, and – we hope – usually finds it there. If there is a cache miss – x is not in the cache – then the processor fetches x from main memory and places a copy of x in the cache so that the next reference to x will be a cache hit.

The trees generated by the semantic analysis phase must be translated into assembly or machine language. The operators of the Tree language are chosen carefully to match the capabilities of most machines. However, there are certain aspects of the tree language that do not correspond exactly with machine languages, and some aspects of the Tree language interfere with compile-time optimization analyses.

For example, it's useful to be able to evaluate the subexpressions of an expression in any order. But the subexpressions of Tree.exp can contain side effects – ESEQ and CALL nodes that contain assignment statements and perform input/output. If tree expressions did not contain ESEQ and CALL nodes, then the order of evaluation would not matter.

Some of the mismatches between Trees and machine-language programs are

• The cjump instruction can jump to either of two labels, but real machines' conditional jump instructions fall through to the next instruction if the condition is false.

• eseq nodes within expressions are inconvenient, because they make different orders of evaluating subtrees yield different results.

• call nodes within expressions cause the same problem.

• call nodes within the argument-expressions of other call nodes will cause problems when trying to put arguments into a fixed set of formal-parameter registers.

Why does the Tree language allow eseq and two-way cjump, if they are so troublesome? Because they make it much more convenient for the Translate (translation to intermediate code) phase of the compiler.