EXAMINING ROOM
A little known Smalltalk/V tool combines Smalltalk's object-oriented, class structured environment with Prolog's logical, declarative approach
Gregory L. Lazarev
Gregory L. Lazarev is president of Applied Logic Programming Inc. He can be reached at 262 Tomkenn Rd., Philadelphia, PA 19151; 215-649-4740.
Recently, there has been a lot of interest in multilanguage software environments which provide a variety of tools that can be applied to different kinds of problems. Despite the fact that many applications can be implemented using one language, it seems worthwhile to combine the strong features of different languages into one environment. The subject of this article is the Prolog/Smalltalk environment, which is particularly intriguing because of the two powerful paradigms involved: logic programming(such as with Prolog) and object-oriented programming (as with Smalltalk). The environment examined is Digitalk's Smalltalk/V, which has an embedded version of Prolog, Prolog/V.
Prolog
The power of the declarative programming language Prolog is well known. The source of this power is in describing knowledge rather than in prescribing a solution technique. A Prolog program consists of a set of non-ordered facts and rules (clauses) describing the knowledge required to solve a problem. Clauses are independent; each has its separate logical meaning. The "what" portion of the problem (that is, what is known and what is required) is expressed explicitly. Programming in Prolog is quite different from programming in conventional languages. Rather, it is closer to the development of a logical specification. The solutions are obtained primarily through the default inference mechanism that is a part of Prolog (the "how" portion is implicit).
This clear separation between logic and control results in many practical advantages of Prolog. The declarative style of programming is very natural, making the task of programming easier; programs are more concise and easier to maintain; Prolog provides an extension of the relational database technology; and the language is powerful and flexible enough to be used for all stages of software development, as well as for rapid prototyping.
These advantages of Prolog are supported by its features, many of which are unique to Prolog: both programs and data are represented by clauses; general pattern matching is available through unification; an automated inference mechanism with backtracking is provided; a non-deterministic style of programming is possible; use of recursive programs and structures can provide simplification; and many Prolog programs are invertible.
A problem usually can be presented as a set of declarative and procedural (imperative) tasks. Prolog is ideally suited for the declarative tasks. However, its applicability for procedural tasks based on side effects (such as I/O, windows manipulation, graphics interface, and so on) is more limited and less natural. Also, Prolog does not provide embedded facilities (classes, inheritance) for describing a problem's taxonomy and placing it within the existing environment. Therefore, the usability of Prolog can be substantially extended by merging it with other languages. These benefits work both ways: by extending the Prolog capabilities and by adding Prolog's inferential power to the other language. One example of such a mixed environment is the interface with the C language, supplied by most Prolog vendors. We consider here the Prolog/Smalltalk environment, which provides many features that cannot be found in other environments.
Object-Oriented Programming and Smalltalk
One problem with traditional software is the separation of data and procedures. Despite the fact that data and procedures are treated as independent, in reality they are not. Each procedure makes assumptions about the data it deals with. These assumptions are explicitly expressed in the procedure by using strong data types and through programming statements (such as the case statement). The separation of data and procedures often results in ad hoc, nonorganized programming practice. Moreover, it prevents reuse of the procedures. Each procedure is tightly bound to the environment (application) and to the specific data structures it uses. Therefore, it is very difficult, if not impossible, to make such procedures general enough to be useful under different circumstances
Object-oriented programming (OOP) resolves this problem by binding data and procedures, known as methods, together as objects. The object's internal structure (data and methods) is hidden from the outside, which makes objects reusable. Computation is performed by sending a message to the object, and only the object itself, through one of its methods, determines the response to the message. In this way the external interface (through messages) defines what should be done, and the internal structure of the object defines how it should be done.
Everything in OOP is based on objects communicating through messages. For example, control structures are invoked by sending messages with blocks as arguments (that is, ifFalse: aBlock, whileTrue: aBlock, and so on). Objects are grouped into classes. Classes form a hierarchy; within the hierarchy each class inherits variables and methods from its superclass. For systems that cannot (or should not) be described using the traditional method of functional decomposition, the object-oriented approach is very natural and allows an easier transition from conceptualization to implementation. Table 1, this page, provides a comparison of semantics and design methodologies for Prolog, Smalltalk, and conventional imperative languages, such as Fortran and C.
Table 1: Comparison of semantics and design methodologies for Prolog, Smalltalk, and conventioanl imperative languages.
Semantics Methodology
Prolog Declarative Functional decomposition
Smalltalk Procedural Object-oriented design
Imperative languages Procedural Functional decomposition
Smalltalk is the best-known example of OOP and is more than a language. It is an interactive, graphics-oriented programming environment based on a carefully chosen class organization. This window, menu-based environment integrates the language, the operating system, and such support tools as text editor, compiler, and debugger. In addition, the inspector lets you examine and edit objects, and browsers help you to navigate and manipulate within a maze of classes and methods.
Smalltalk/V includes numerous classes. Magnitude classes define objects that can be compared, measured, ordered, and counted (some examples of these classes are Number, Character, Date, and Time). Stream classes are used to access files, devices, and internal objects such as sequences of characters or other objects. Collections classes define arbitrary objects (examples include Bag, Set, Array, and String classes). Window classes include the Pane classes, used for the display in a designated area of the screen, and Dispatcher classes, used for processing keyboard and mouse inputs. The Dispatch Manager class schedules all the windows under its control. Graphic classes consist of four major classes: the Form class provides a two-dimensional view for a bitmap; the Point and Rectangle classes reference a point and a rectangular block contained in a Form; and the BitBlt (bit block transfer) class describes the basic bitmapped operation of moving a block of bits from one place to another. The latter also describes more complex operations such as conversion of characters into displayable bit patterns (class Character-Scanner), drawing lines from one place to another (class Pen), and animation (class Animation).
Object-oriented extensions are applied to several languages, including Prolog, but they are beyond the scope of this article.
Prolog/V
The emphasis in the implementation of Prolog/V is on the tight integration of Prolog and Smalltalk. Prolog/V is fully embedded into the Smalltalk environment, therefore Smalltalk features, such as inheritance, are available. The class is defined first, then the Prolog clauses belonging to this class are entered in a way very similar to entering the Smalltalk methods. The only difference is that it is done through a Logic Browser window rather than through a Class Hierarchy Browser window, as it is for Smalltalk methods. (The Logic Browser has a Prolog compiler, the Class Hierarchy Browser has a Smalltalk compiler.) All clauses with the same name, that is with the same predicate name in the clause head, are grouped together and compiled into one Smalltalk method with one argument. A class Logic (a subclass of Object) and its subclass Prolog provide the methods for Prolog execution and built-in predicates, respectively. Therefore, in order to inherit these properties, any Prolog program should be placed into one of the subclasses of the Prolog class.
You can call Prolog from Smalltalk and vice versa. From Smalltalk, you can invoke Prolog's question. The standard Prolog question ?- a1, a2,... aN is replaced in Prolog/V by the receiver:? a1, a2,... aN Here the receiver is an instance of some arbitrary class. The clauses matching the goals a1, a2,... aN may either belong to this class or be inherited from its superclasses. After calculating the answers, Prolog returns them as a Smalltalk array (or as a nil if there are no answers) that can be processed further by Smalltalk if necessary.
On the Prolog side, the predicate is used to send a Smalltalk message. It provides a convenient way to support side-effects in Prolog/V. The predicate is as in is (var, smalltalkExpr) unifies a Prolog variable varwith the Smalltalk expression smalltalkExpr. It replaces the standard is predicate in Prolog that unifies a variable with the Prolog expression. Therefore, in Prolog/V the arithmetic is performed by sending a Smalltalk message as in is(x,2 + 3 * 4).
Two other examples of using the is predicate are:
is( len, len0 value + 1)
and
is(_, pen
place: 5 @ 5;
goto: 35 @ 25)
In the first example len0 is a Prolog variable. The Prolog variable can be used in a Smalltalk expression, but the value message should be sent to such a variable first. In the second example, only the side-effect (drawing a line) is relevant.
Prolog/V syntax is quite close to the standard Edinburgh syntax. In addition to the two previously described differences (the question and the is predicate), there are other major differences. Prolog/V variables start either with a lower case letter (local variables) or with an upper case letter (global variables). Atoms are preceded with #, characters are preceded by $, strings must be surrounded by single quotes, and no underscore is allowed in names (the anonymous variable _ is an exception). All structures, even structures without arguments, must have a pair of parentheses as in pred1(x, y), pred2(). Some predicates are not implemented in Prolog/V; in particular, side-effect predicates (such as get, put see, seen, etc.) are supported through the Smalltalk messages. Others may have different semantics. For example, the consult predicate provides communication among parallel classes.
To demonstrate the advantages provided by the Prolog/Smalltalk integration, consider an example of a program for transferring blocks. The next section presents a core program written in standard Prolog (Arity/Prolog is used). The extensions provided by Prolog/V (multi-pane windows, synchronization among panes, customized menu, graphics interface) follow.
Blocks Example in Standard Prolog
The blocks example used here is taken from Lazarev. Consider a tabletop with a pile of blocks on it. Blocks may be directly on the table or on each other. The problem is to create a plan which moves the blocks from a given starting configuration to a given final configuration. Blocks are moved one at a time if the following conditions are satisfied: the top of a block to be moved must be clear; if a block is moved to the top of another block, then the top of the second block also must be clear.
The resulting program is shown in Listing One. It is based on the state-space search using the generic recursive procedure path. The move procedure is problem-specific.
The path has three arguments, the start state (State), the goal state (Goal), and the history of visited states (Hist). If the Goal is reached, then the solution is printed using the procedure printpath. Otherwise, in order to find a path from the State to the Goal, the following steps should be taken: find move from a State to an intermediate state Interm; check that Interm state is not on the list of already visited states, Hist; and find a path from Interm to a Goal with the list of visited states enlarged by In term. The top goal go calls path with [Start] as the initialized list of visited states, and the !predicate limits search to the first solution.
The blocks problem is represented using the list data structure:
[on( a,A), on( b,B) on( z,Z) ],
where a, b,... z are blocks, and A, B,..., Z are either blocks or the table t.
Two move clauses describe the transition from a State1 to a State2. The first clause chooses some block (using a member predicate), checks if it is clear, and places the chosen block on the table. The resulting State2 is formed by substituting t for the original block's position Y The move of a block already located on the table is forbidden. The second move clause is similar to the first but places the block on top of another block rather than on a table. The second block must be different from the first and clear. As a result, the list's element on(X, Y) is replaced by on(X,Z) where X is the block moved and Y and Z are its initial and final positions. The procedure clear specifies that a block X is clear if there is nothing on top of it.
For simplicity, let's limit ourselves to four blocks. The predicates blocks1 and blocks2 describe the three-block transfer; the predicate blocks3 describes the four-block transfer. For example, consider the three blocks transformation corresponding to the goal blocks2 (see Figure 1, this page).
The solution is presented as:
?- blocks2. [on(a,t), on(b,t), on(c,a) ] [on(a,t), on(b,t), on(c,t) ] [on(a,t), on(b,a), on(c,t) ] [on(a,t), on(b,c), on(c,t) ] [on(a,b), on(b,c), on(c,t) ].
Blocks Example in Prolog/V
The core of the blocks program written in Prolog/V is the standard Prolog program from the previous section. The difference is an advanced user interface provided by Prolog/V. An interface of this kind is difficult to implement in other environments.
The blocks example in Prolog/V is represented by the class Blocks and its subclass BlocksPro. Their position within the hierarchy of classes is shown in Figure 2, below.
Figure 2: Class hierarchy for the blocks example
Object
Logic
Prolog
Library
Blocks
BlockPro
The class Library (a subclass of the class Prolog), has many useful predicates (such as append, member, findall, etc.) that are not among the built-in predicates of the class Prolog. The class Library is not shown here. The class Blocks, with its Smalltalk methods, is shown in Listing Two. The class BlocksPro (Listing Three) is the subclass of Blocks. All of its methods are Prolog clauses. BlocksPro doesn't have its own instance variables; it inherits instance variables and methods from the class Block.
The program is invoked by sending the message:
BlocksPro new openOn
The openOn method, inherited from the class Blocks, creates a multi-pane window BLOCKS. There are four panes interacting with each other--instances of the class SubPane. The list pane at the screen's top left corner displays the list of choices. The text pane at the screen's top right corner provides a brief description of the application and has a customized menu with two options--do and help. The text pane in the middle of the screen displays help messages and the analytically represented output (the output stream, defined by the instance variable replyStream, is determined by sending the dispatcher message to the object associated with the temporary variable replyPane). The graph pane at the bottom of the screen provides a graphic drawing of the moving blocks.
The position and size of each pane relative to the whole window is defined by the message framingRatio:extent:.
A message name: is sent to the instance of the class SubPane. It initializes a pane when the window is first open. There are four initialization methods: choices, input, reply, and graph:. The method choices returns a list of available alternatives. The method input returns the text associated with the choice. The choice is defined by the instance variable selectedChoice. The method reply clears the output pane. Finally, the method graph: returns the white form of the specified size and initializes the global variables.
The class SubPane also provides the capability for synchronizing panes through the method change:. The message change: #choice: is sent to the instance of the class ListPane. The method choice: assigns the selectedChoice to the chosen alternative (i.e., blocks1, blocks2, or blocks3) and then broadcasts the value of selectedChoice to all panes. The broadcast is done by sending messages changed: to the controlling application (in our case, the instance of BlocksPro). The arguments of changed: messages are the names of the initialization methods described above. In this way, a list pane selection is synchronized with the contents of other panes. The initial screen display is shown in Figure 3, below. Figure 3: The initial screen
After the choice is made, the next step is to access the text pane menu through the method doBlocksMenu. This menu gives two options do and help, defined by the methods doBlocks and help, respectively. (Notice that all methods described so far are inherited by the class BlocksPro from its superclasses, particularly from the class Blocks.) The help method writes the text of the help message into the output stream. The doBlocks method provides the main program function. It invokes one of the Prolog goals (blocks 1(), blocks2(), or blocks3()), depending on the value of selectedChoice. All Prolog clauses belong to the class BlocksPro. Only new clauses or clauses different from the standard Prolog program ( Listing One) are described here.
The predicate go/2 consists of three subgoals init/1, path/3, and the trivial subgoal described by the method finish. The functions of init/1 predicate are to initialize the animation, to initialize the Smalltalk blocks data structure, and to draw the initial blocks configuration. The first two functions are described by the method initialize1. To invoke this method, as well as any other Smalltalk method from Prolog/V, a Smalltalk message should be sent using the predicate is, as in
is( _, self initialize1).
The method initAnimation adds four objects with different names and colors to the instance variable animator. Each object is represented by the array of forms simulating its continuous movement on the screen. When the object moves, the old image is erased, and the new image, taken from the array of forms, is displayed at the new position. The array of forms in the blocks application consists of one element only--the form White.
The existing Prolog blocks data structure is not adequate to support graphics of moving blocks. Therefore, the extra Smalltalk data structure, described by the instance variable position, is provided. (The other choice is to include the graphics extension within the existing Prolog data structure.) The variable position is represented as an array with the number of elements equal to the number of participating blocks. Each element is the instance of the class OrderedCollection; it is initialized by the method initPosition to an empty collection.
Finally, the initial drawing is handled through the recursive predicate initDraw/1. It describes either the placing of block x on the table (predicate addDraw( x)), or the placing of block x on top of block z(predicate addDraw (x, z)). The actual work is performed by the Smalltalk methods add:onTbl: (called from addDraw/1 and add:onBl: (called from addDraw/2). Because the initial drawing is done in specific order (from the table up), the predicate arrange/2 is introduced. It transforms the starting Prolog blocks data structure into the "drawing order" structure. For example, the structure [on(a,b), on(b,t), on(c,t), on(d,a) ] is transformed into the structure [on(c,t), on(b,t), on(a,b), on(d,a) ]. The screen display at the start of graphics simulation is shown in Figure 4, this page. Both menu options (do and help) were chosen.
Figure 4: The screen at the start of the graphics simulation
The main procedure path/3 is a modified version of the same procedure from the standard Prolog program. The first path clause is invoked when the goal is achieved. The text output pane is cleared, and all steps needed to transform the initial configuration into the final configuration are written into the output stream. The second path clause supports the graphics drawing by calling the procedure moveDrawInOut/3. The three parameters of the predicate moveDrawInOut describe the block's name, the place it is moving from, and the place it is moving to. (In order to obtain these parameters explicitly, the predicate move/2 from the standard Prolog program was converted into the predicate move/5.) The procedure moveDrawInOut/3 has two clauses. The first clause describes the move from placeFrom to placeTo. The second clause describes the reverse process--the move from placeTo to placeFrom. This clause is used on backtracking to undo the graphics effects from the last move. The procedure moveDraw/3 describes the same two cases as the move/5 procedure, i.e., placing a block on the table and placing a block on the top of the another block. It deals with updating the data structure position and also moves blocks on the screen from one place to another.
The actual work is done by the Smalltalk methods remove:, add:onTbl:, and add:onBl:. The method remove: block finds in the array position the ordered collection that includes block, and then removes block from there. There are no graphics involved. The methods add:block onTbl: col and add:block1 onBl: block2 add the block after the last entry in the ordered collection and then move the block on the screen by sending the message tell:place: to the animator object. The only difference between these two methods is the mechanism of finding the proper ordered collection in the array position.
Screen displays in the process of simulation and after program completion are shown in Figure 5, page 78, and Figure 6, this page.
Figure 5: Screen display during the simulation process
Figure 6: Screen display after simulation
Smalltalk Terminology Prolog Terminolog
Conclusions
Overall, the Prolog/Smalltalk environment and its excellent implementation by Digitalk provides an interesting example of multi-language systems. (The performance modeling tool based on Prolog/V is described in Pazirandeh and Becker.) Many existing Prolog programs can easily be incorporated into this environment. The blocks application, described here, is an example of such a program.
The technique discussed above may also have a strong impact on software engineering practice. Prolog/V combines the Smalltalk object-oriented, class structured environment with the logical, declarative approach in specifying objects' behavior. The declarative approach advocated by Prolog is often more suitable than the traditional, procedural approach used in "pure" Smalltalk.
References
1. Digitalk Smalltalk/V. Object-Oriented Programming System, (Los Angeles, CA: Digital Inc., 1987).
2. B. J. Cox, Object-Oriented Programming. An Evolutionary Approach, (Reading, MA: Addison-Wesley, 1986).
3. B. Meyer, "Reusability: The Case for Object-Oriented Design," IEEE Software, March 1987, 50-63.
4. E. P. Stabler, Jr., "Object-Oriented Programming in Prolog," AI Expert, Oct. 1986, 46-57.
5. W. F Clocksin and C. S. Mellish, Programming in Prolog, (Berlin: Springer-Verlag, 1984).
6. G. L. Lazarev, Why Prolog? Justifying Logic Programming for Practical Applications, (Englewood Cliffs, NJ: Prentice-Hall, 1989).
7. M. Pazirandeh and J. Becker, "Object Oriented Performance Models with Knowledge-based Diagnostics," Proceedings of the 1987 Winter Simulation Conference, (A. Thesen, H. Grant, W. David Kelton (eds.)), 1987.
I would like to thank Susan Bartley and Kenneth Krigelman for their valuable comments.
Everything in Smalltalk centers around objects. Objects belong to classes, which, by forming a hierarchy, define inheritance. Each class is characterized by name and has instance and class variables associated with it. Each variable refers to the object whose pointer it contains. Assignment expression assigns the object to the variable (as in array:-#(abc)). Instance variables (named and indexed) belong to the instance of the class and exist for the object's lifetime. Class variables are shared between all instances of the same class and exist until explicitly deleted. Class variables are a subset of shared variables that start with an upper case letter and are shared by many objects.
Computation is defined as a process of changing instances variables of existing objects, creating new objects or destroying them. All computations are performed by messages. The only way to access the object's data in Smalltalk is to send a message to the object. A message is composed of three parts: a receiver of the message, the message selector (specifying the action to be performed), and the message arguments. A message always returns a single object as its result. The receiver of the message can be any object, that is an instance of the class or a class itself. The mechanism of the message passing provides external interfaces in Smalltalk. It takes the place of a procedure call in conventional language.
There are three kinds of messages: unary messages, binary messages, and keyword messages. Unary messages are messages with no arguments. For example, Pen new 'this is a string' size. The first message with the selector new is the class message. It returns the new instance of the class Pen. The second message with, selector size is the message to the instance of the class String It returns the size of the string. Binary messages are messages with one argument and one or two special characters as selector. For example, 3 + 4 or 'abc', 'def'. The first message with the selector + returns the object 7, the second message concatenates two strings and returns the string 'abcdef'. Keyword messages are messages with one or more arguments. For example, #( a b c b d b a) occurrencesOf: #b or #(a b c) at:2 put:$d. The first message with the selector occurrencesOf: returns the number of b-occurrences in the array, i.e. 3. The second message with the selector at:put: returns $d, but it also replaces bin the array #(a b c) with $d.
Normally, these messages are combined together into expressions with predefined rules of precedence. For example, in the expression 3 factorial + 7, the unary message factorial is evaluated first, the binary message + follows. The result is 13.
In response to a message received by the object, a matching method is executed. Methods are procedures associated with the class. They keep the internals of the object implementation invisible from the outside. There are two kinds of methods: class methods, responding to messages sent to the class, and instance methods, responding to messages sent to instances of the class. A method consists of the message pattern (the selector and its arguments) that is matched with the invoking message, temporary internal variables, and a series of expressions separated by periods. The execution of these expressions defines the message result. Consider, for example, the instance method includes from the class Indexed-Collection.
It has the selector indudes: with one argument, and one temporary variable--index. The caret (^) symbol determines the value to be returned. Each element of the receiver is compared with anObject until either the match is found (the result is true) or not found (the result is false). This method is matched against the following messages
A class is characterized by its name, variables (class and instance), and methods (class and instance). Classes form a hierarchy with a class Object as the root. A class inherits from its superclasses instance and class variables and methods. This inheritance allows references to the variables and methods not defined within a class. Search for variables and methods starts within a receiver's class and, if it fails, the search continues in its superclass, the superclass of superclass, and so on.
The syntax of Prolog is simple and is based on the concept of objects (not to be confused with the Smalltalk objects) and their relations.
The lowest level building blocks for Prolog programs are "terms." There are three classes of terms: constants, variables, and structures. Constants are the names of defined objects or specific relationships between them. Two main categories of constants in Prolog are atoms which normally begin with a lowercase letter (for example, find_next) and numbers. A constant represents a defined object. A variable stands for a yet undefined object that will be substituted once by an object in the course of computation (a process known as "instantiation"). Variables start with capital letters or the underscore character (for example, XY, _Age) The third class of terms is known as structures. A structure is described as: f(t1, ..., tn) where f is called a functor and t1, ..., tn are called components of the structure. A functor is characterized by its name f, which is an atom, and by the number of components n--its arity. It is denoted as f/n. A functor in Prolog cannot be a variable. This reflects a limitation of the first-order logic on which Prolog is based. A component of a structure may be any term, i.e., a constant, variable, or another structure. This allows the existence of nested structures.
Structures are fundamental in Prolog. A structure may either describe a single complex object built from other objects, as in: person_birthday (Name, date (Month, Day, Year) ) or it may describe a predicate which expresses a relationship among objects, as in the predicate likes/2: likes(X, steve).
A Prolog program consists of clauses. Each clause is represented through predicates A, B1, ..., Bn in the form: A:-B1, ..., Bk, ..., Bn where A is the clause's head and B1, ..., Bk, ..., Bn constitute the, clause's body. Declaratively, the clause A:- B1, ..., Bn stands for: A is true if all Bi's are true.
The predicates A and Bi are also known as goals (or subgoals). As a predicate, a goal either an atom or a structure. There is only one predicate in the clause's head. Commas between goals stand for conjunction (i.e., logical AND), but disjunction (logical OR) is also supported by separating goals with semicolons. The symbol :- is understood as if. Only two possible values are associated with each predicate: true or false. All variables appearing in clauses are read as "for all," i.e., universally quantified. The scope of a variable is limited to the clause in which it appears.
Prolog programs are described by facts, rules, and questions. All of them are all specific cases of clauses. A fact is a clause without body (that is, no conditions); rules have both a head and a body; questions are clauses without a head. The following notation is used for questions ?- B1, B2, ..., Bn instead of the more formal :- B1, B2, ..., Bn.
The most fundamental feature of Prolog, which differentiates it from conventional languages, is its declarative character. Ideally, writing a program in Prolog means expressing what is known (that is, to represent facts and rules in the most natural way), as well as specifying a problem by formulating a question. Prolog will do the rest, i.e. it will produce answers by manipulating the supplied facts, rules, and question. The ability to support the computation process automatically is based on the fundamental principles of unification and resolution. Strictly speaking, the above scenario is valid for pure Prolog only. In real Prolog, augmented with many built-in predicates, it is approximately true.
Rules in Prolog have two interpretations. Besides the declarative interpretation, the rule A :- B1, B2, ..., Bk, ..., Bn has the following procedural interpretation: To satisfy goal A, first satisfy subgoal B1, then satisfy subgoal B2, ..., then satisfy subgoal Bk, ..., and last satisfy subgoal Bn.
This interpretation not only specifies which subgoals should be satisfied but also provides procedural information by answering how (i.e., in what order) the computation will be done. The procedural meaning of a program, in contrast to its declarative meaning, generally depends on the order of goals in the body of each clause as well as on the order of clauses within the program.
Computation in Prolog is based on a standard strategy augmented with backtracking. The standard strategy is defined as sequential, depth first processing with goals in the clause body invoked from left to right and each goal unified with the head of the matched clause chosen according to textual order within a procedure (a procedure is a set of clauses with the same head).
Unification is the process of finding a set of bindings for variables so that the terms match. It is responsible for the answer extraction. Two Prolog terms match if they are identical or if variables in those terms can be instantiated (i.e., bound) in such a way that they become identical.
If one of the goals fails, then the attempt to resatisfy the last satisfied goal takes place--a process known as "backtracking" All variables instantiated with the last satisfied goal are uninstantiated. This is the way the "undo" operation is performed in Prolog.
As an example, consider a program that defines whether a particular element is part of a list. (A list is an ordered sequence of elements with any length. Head is the first element of a list. Tail is the original list without its first element. The notation [H | 7] is used with H as a head, and T as a tail.) Declaratively, the program is described as: X is a member of a list if it is identical to the head of the list or X is a member of a list if it is a member of the tail of the list.
The program is written in Prolog using the predicate member (X, List).
Consider the goal ?- member(X,[a,b,c]). The three solutions are: X = a; X = b; or X = c. The first solution (X = a) is produced by unification of the goal with the first member clause. The system backtracks looking for other solutions. By unifying with the second member clause, the goal ?-member(X, [b,c]) is invoked. The process repeats itself (starting with the first member clause) and results in two more answers.
_PROLOG/V: PROLOG IN THE SMALLTALK ENVIRONMENT_
by
Gregory L. Lazarev
[LISTING ONE]Acknowledgment
Smalltalk Terminology
by Gregory Lazarev
includes: anObject
"Answer true if the receiver contains an element equal to anObject, else
answer false."
|index| index := self size + 1. [(index := index - 1) > 0] whileTrue: [
anObject = (self at: index) ifTrue: (^true]]. ^false
#(a b c)includes: #b (returns true)
#(a b c)includes: #d (returns false)
Prolog Terminology
member(X, [X|_|). member(X, [_|T|) :-member(X,T).
<a name="0201_0018">
/* blocks transfer program */
/* generic */
go( Start, Goal) :- path( Start, Goal, [Start]), !.
path( Goal, Goal, Hist) :- printpath( Hist).
path( State, Goal, Hist) :- move( State, Interm),
not( member( Interm, Hist) ),
path( Interm, Goal, [Interm|Hist]).
member( X, [X|_]).
member( X, [_|T]) :- member( X, T).
printpath( []).
printpath( [H|T] ) :- printpath( T), write( H), nl.
/* problem specific */
blocks1 :- go( [on(a,b), on(b,t), on(c,t)], [on(a,b), on(b,c), on(c,t)] ).
blocks2 :- go( [on(a,t), on(b,t), on(c,a)], [on(a,b), on(b,c), on(c,t)] ).
blocks3 :- go( [on(a,b), on(b,t), on(c,t),on(d,a)], [on(a,d), on(b,c), on(c,t),
on(d,b)] ).
move( State1, State2) :- member( on( X,Y), State1),
clear( X, State1),
not( table( Y)),
subst( on( X, Y), State1, on( X, t), State2).
move( State1, State2) :- member( on( X,Y), State1),
clear( X, State1),
member( on( Z, _), State1), X \= Z,
clear( Z, State1),
subst( on( X, Y), State1, on( X, Z), State2).
clear( X, State) :- not( member( on( _, X), State)).
subst( _, [], _, []).
subst( X, [X|L], A, [A|M]) :- !, subst( X, L, A, M).
subst( X, [Y|L], A, [Y|M]) :- subst( X, L, A, M).
table( t).
<a name="0201_0019"><a name="0201_0019">
<a name="0201_001a">[LISTING TWO]<a name="0201_001a">
Prolog variableSubclass: #Blocks
instanceVariableNames:
'position animator number between replyStream selectedChoice '
classVariableNames: ''
poolDictionaries: ''
Blocks class methods
Blocks methods
add: block1 onBl:block2
"add one block to the top of the other"
| ordColl index col size|
index := 1.
col := 0.
[index <= number
and: [col = 0] ]
whileTrue: [
( (position at: index) includes: block2 )
ifTrue: [ col := index].
index := index + 1].
ordColl := position at: col.
ordColl add: block1.
size := ordColl size.
position at: col
put: ordColl.
animator tell: block1
place: ( (between * col) - (between * (2/3) ) ) @
( (RectPict extent y - 5) - ( 60 * size * Aspect) truncated )
add: block onTbl: col
"(re)initialize column: add the first block to it"
| ordColl |
ordColl := position at: col.
ordColl add: block.
position at: col
put: ordColl.
animator tell: block
place: ( (between * col) - (between * (2/3) ) ) @
( (RectPict extent y - 5) - ( 60 * Aspect) truncated)
assign: size
"assign a variable number"
number := size
choice: aSymbol
"Private - Change to the selected choice type."
selectedChoice := aSymbol. " #blocks1, #blocks2 or #blocks3"
self
changed: #input;
changed: #reply;
changed: #graph:
choices
"Private - Answer an Array of choices"
^#( blocks1 blocks2 blocks3 )
doBlocks
"Actual call to Prolog"
CursorManager execute change.
selectedChoice == #blocks1
ifTrue: [self :? blocks1() ].
selectedChoice == #blocks2
ifTrue: [self :? blocks2() ].
selectedChoice == #blocks3
ifTrue: [self :? blocks3() ].
CursorManager normal change
doBlocksMenu
"Menu do\help"
enu
labels: 'do\help' withCrs
lines: #()
selectors: #(doBlocks help)
finish
Menu message: 'The solution is found'
graph: aRect
" initialize graph pane, assign global variables"
| aForm |
aForm := Form
width: aRect width
height: aRect height.
aForm displayAt: aRect origin. "background"
RectPict := aRect. "global vars"
White := ( Form
width: 60 height: ( 60 * Aspect) truncated ).
^aForm
help
"Provide help message"
selectedChoice == #blocks1
ifTrue: [replyStream nextPutAll:
'EXPLANATION: This is an animation of the 3 blocks problem'; cr ].
selectedChoice == #blocks2
ifTrue: [replyStream nextPutAll:
'EXPLANATION: This is an animation of the 3 blocks problem'; cr ].
selectedChoice == #blocks3
ifTrue: [replyStream nextPutAll:
'EXPLANATION: This is an animation of the 4 blocks problem'; cr ]
initAnimation
" initialize Animation"
| blockImages |
blockImages :=
Array with: White.
animator := Animation new
initialize: RectPict.
animator add: blockImages
name: 'Black'
color: #black.
animator add: blockImages
name: 'LightGray'
color: #lightGray.
animator add: blockImages
name: 'Gray'
color:#gray.
selectedChoice == #blocks3
ifTrue: [ animator add: blockImages
name: 'DarkGray'
color: #darkGray].
" set speed, shift, background"
animator
setBackground;
speed: 8;
shiftRate: 10
initialize1
"initialize Blocks"
| pen|
" draw bottom"
pen := Pen new.
pen defaultNib: 3 @ 2.
pen
place: (RectPict origin x + 5) @ (RectPict corner y - 5);
goto: (RectPict corner x - 5) @ (RectPict corner y - 5).
" assign between variable"
between := RectPict width // number.
"initialize animation and position"
self
initAnimation;
initPosition
initPosition
"Set the receiver's initial position"
position := Array new: number.
1 to: number do: [:index|
position at: index
put: OrderedCollection new]
input
"Private - Answer an input text for
the selected choice (blocks1, blocks2 or blocks3)."
| text1 text2 text3 text|
text1 := 'FROM: A on B, B on Table, C on Table
TO : A on B, B on C, C on Table
( COLORS: A- Black, B- LightGray, C- Gray)'.
text2 := 'FROM: A on Table, B on Table, C on A
TO : A on B, B on C, C on Table
( COLORS: A- Black, B- LightGray, C- Gray)'.
text3 := 'FROM: A on B, B on Table, C on Table, D on A
TO : A on D, B on C, C on Table, D on B
( COLORS: A- Black, B- LightGray, C- Gray, D- DarkGray)'.
selectedChoice == #blocks1
ifTrue: [text := text1].
selectedChoice == #blocks2
ifTrue: [text := text2].
selectedChoice == #blocks3
ifTrue: [text := text3].
^text
openOn
"Create a window on Blocks.
Define the type, behavior and relative
size of each pane and schedule the window."
| topPane replyPane|
topPane := TopPane new label: 'B L O C K S'.
topPane addSubpane:
(ListPane new
model: self;
name: #choices;
change: #choice:;
selection: 1;
framingRatio: ( 0 @ 0 extent: 1/4 @ (1/6) ) ).
selectedChoice := #blocks1.
topPane addSubpane:
(TextPane new
model: self;
name: #input;
menu: #doBlocksMenu;
framingRatio: ( 1/4 @ 0 extent: 3/4 @ (1/6) ) ).
topPane addSubpane:
(replyPane := TextPane new
model: self;
name: #reply;
framingRatio: ( 0 @ (1/6) extent: 1 @ (1/6) ) ).
topPane addSubpane:
(GraphPane new
model: self;
name: #graph:;
framingRatio: ( 0 @ (1/3) extent: 1 @ (2/3) ) ).
topPane reframe:
(Display boundingBox insetBy: 10@10).
replyStream := replyPane dispatcher.
topPane dispatcher openWindow scheduleWindow
remove: block
"remove block (from the data structure only)"
| ordColl index col|
index := 1.
col := 0.
[index <= number
and: [col = 0] ]
whileTrue: [
( (position at: index) includes: block )
ifTrue: [ col := index].
index := index + 1].
ordColl := position at: col.
ordColl removeLast.
position at: col
put: ordColl
reply
" Initiate reply pane with an empty String."
^ String new
<a name="0201_001b"><a name="0201_001b">
<a name="0201_001c">[LISTING THREE]<a name="0201_001c">
Blocks variableSubclass: #BlocksPro
instanceVariableNames: ''
classVariableNames: ''
poolDictionaries: ''
BlocksPro class methods
BlocksPro methods
"add on the Table"
addDraw( x) :-
name( x, name1), col( x, col1),
is( _, self add: name1 value onTbl: col1 value).
"add on the Block"
addDraw( x, z) :-
name(x, name1), name( z, name2),
is( _, self add: name1 value onBl: name2 value).
"arrange0 - the first part of arrange"
arrange0( len, _, _, accum, accum) :-
length( accum, accumLen),
eq( len, accumLen).
arrange0( len, master, prev, accum, ordered) :-
nextStep( master, prev, [], nextPrev),
append( nextPrev, accum, nextAccum),
arrange0( len, master, nextPrev, nextAccum, ordered).
"arrange1 - the second step of arrange"
arrange1( master, [#t], arrMaster, arrMaster).
arrange1( master, [h|t], interm, arrMaster) :-
member( on(h,x), master),
arrange1( master, t, [on(h,x)| interm], arrMaster).
"arrange ,i.e. [on(a,b),on(b,t),on(c,t),on(d,a)] -->
--> [d,a,b,c,t] --> [on(c,t), on(b,t), on(a,b), on(d,a)] "
arrange( master, arrMaster) :-
length( master, len0),
is( len, len0 value + 1),
arrange0( len, master, [#t], [#t], ordered),
arrange1( master, ordered, [], arrMaster),
!.
"blocks1"
blocks1():- go( [on(#a,#b), on(#b,#t), on(#c,#t)], [on(#a,#b),
on(#b,#c), on(#c,#t)] ).
"blocks2"
blocks2():- go( [on(#a,#t), on(#b,#t), on(#c,#a)], [on(#a,#b),
on(#b,#c), on(#c,#t)] ).
"blocks3"
blocks3():- go( [on(#a,#b), on(#b,#t), on(#c,#t), on(#d,#a)],
[on(#a,#d), on(#b,#c), on(#c,#t), on(#d,#b)] ).
"clear"
clear( x, state) :- not( member( on( _, x), state) ).
"column"
col( #a, 1).
col( #b, 2).
col( #c, 3).
col( #d, 4).
"go"
go( start, goal) :- init( start),
path( start, goal, [start]),
is( _, self finish),
!.
"initialize"
init( start) :- length( start, startSize),
is( _, self assign: startSize value),
is( _, self initialize1 ),
arrange( start, arrStart),
initDraw( arrStart),
is( _, Menu message: 'Press button to start'),
!.
"initial drawing"
initDraw( []).
initDraw( [on(x,#t)|tail]) :- addDraw( x),
initDraw( tail).
initDraw( [on(x,z)|tail]) :- addDraw( x,z),
initDraw( tail).
"move"
move(state1,state2,x,y,#t) :- member( on( x, y), state1),
clear( x, state1),
not( table( y) ),
subst( on( x, y), state1, on( x, #t), state2).
move(state1,state2,x,y,z) :- member( on( x, y), state1),
clear( x, state1),
member( on( z, _), state1), ne( x, z),
clear( z, state1),
subst( on( x, y), state1, on( x, z), state2).
"draw Block --> Table"
moveDraw( x, _, #t) :-
name( x, name1), col( x, col1),
is( _, self remove: name1 value),
is( _, self add: name1 value onTbl: col1 value).
"draw Table --> Block; Block --> Block"
moveDraw( x, _, z) :-
ne( z, #t),
name(x, name1), name( z, name2),
is( _, self remove: name1 value),
is( _, self add: name1 value onBl: name2 value).
"draw In and Out"
moveDrawInOut( block, placeFrom, placeTo) :-
moveDraw( block, placeFrom, placeTo).
moveDrawInOut( block, placeFrom, placeTo) :-
moveDraw( block, placeTo, placeFrom),
fail(). " reverse back"
"name"
name( #a, 'Black').
name( #b, 'LightGray').
name( #c, 'Gray').
name( #d, 'DarkGray').
"nextStep - called from arrange0"
nextStep( _, [], nextPrev, nextPrev).
nextStep( master, [h|t], current, nextPrev) :-
findall( x, member( on( x,h), master), interm),
append( interm, current, current1),
nextStep( master, t, current1, nextPrev).
"path"
path( goal, goal, hist) :- is( _, self changed: #reply),
printpath( hist).
path( state, goal, hist) :- move(state, interm, block, placeFrom, placeTo),
not( member( interm, hist) ),
moveDrawInOut( block, placeFrom, placeTo),
path( interm, goal, [interm| hist] ).
"printpath1"
printpath1( [h]) :- is( _, replyStream nextPutAll:
(h value printString) ).
printpath1( [h| t] ) :- is( _, replyStream nextPutAll:
( (h value printString), ', ' ) ),
printpath1( t).
"printpath - print list in the reverse order"
printpath( []).
printpath( [h| t] ) :- printpath( t),
is( _, replyStream nextPutAll: '['),
printpath1( h),
is( _, replyStream nextPutAll: ']'),
is( _, replyStream cr).
"substitute"
subst( _, [], _, []).
subst( x, [x| l], a, [a| m]) :- !,
subst( x, l, a, m).
subst( x, [y| l], a, [y| m]) :- subst( x, l, a, m).
"table"
table( #t).
