AAIS Prolog

Mary Elaine Califf

As someone who leads a double life as a Macintosh programmer and a student of artificial intelligence (especially natural language processing), I was delighted by the opportunity to review the latest version of Advanced A.I. Systems' Full Control Prolog.

"Prolog?" you ask. "What does Prolog have to do with FrameWorks? I thought I was reading about object-oriented programming."

Relax. You haven't picked up the wrong magazine. AAIS Prolog, although it can be used as a standard Edinburgh-style Prolog environment, has objects; in fact, they must be used in order to access the Macintosh toolbox or to manipulate the environment. AAIS Prolog is simply another OODL, this one different from those that have been discussed here previously because it uses logic programming.

For those who are not familiar with logic programming and Prolog, I'll begin with a brief explanation of the language, without reference to the addition of objects in this implementation. People who are familiar with Prolog will probably want to skip to the next section, AAIS Extensions to Prolog.

Prolog

Prolog is probably the best known programming language based on logic and Lisp's most serious competitor in the AI community. Its syntax, like Lisp's, is much simpler than that of languages such as C, C++, and Pascal. However to the average programmer, the syntax is probably a bit more familiar than Lisp's, since it is based on predicate calculus, something many of us have faced at some point in our education. Programming in Prolog consists of declaring facts, defining rules, and asking questions.

Facts are statements about objects and their relationships. They consist of a relationship followed by a comma-separated list of objects in parentheses and a period (or full stop). Example Prolog facts include:

loves(john,mary).  % usually interpreted "John loves Mary"
loves(joe,jane).    % "Joe loves Jane"
sort([],[]).        % a sorted empty list is the empty list
female(jane).       % "Jane is female"
+(0,Num,Num).       % "0 + any number = that number"

You probably immediately noticed that I didn't capitalize the proper names in my facts. In Prolog, symbols typically begin with either a lower case letter or an underscore. If symbols beginning with capital letters are desired, they must be enclosed in single quotes. Thus, I could have written

loves('John','Mary').

Names which begin with capital letters are interpreted as variables.

The number of objects in parentheses is the arity of the fact. The name of the relationship is called the functor. In matching rules and facts against questions, Prolog attempts to match both the functor and the arity. So you can define two different sorts both called 'sort' if they have different numbers of arguments.

To do anything with these facts, you need to be able to ask questions about them. Questions in Prolog take the form

?- loves(mary,john).

On seeing a question, Prolog will attempt to match it against the facts in its database. As soon as Prolog succeeds in matching a fact (or satisfying a rule), it stops and returns yes or the binding of the variables in the query for that match. If, after examining all facts and rules with the same functor and arity, it doesn't find a match, Prolog returns no. Assuming the above set of facts, here is an example set of queries to Prolog.

?- loves(john,mary).   
    yes
?- loves(mary,john).
    no
?- loves(X,Y).
    X = john,   Y = mary ; % first match is loves(john, mary).
    X = joe,    Y = jane ; % typing ;-return  makes Prolog search
                           % for another match
    no                     % there is no third match
    ?- +(0,5,Y).           % the first Num in +(0,Num,Num) gets bound
    Y = 5                  % to 5, so the second must also be 5

In programming, obviously facts by themselves aren't going to get you very far, so Prolog provides rules, which take the following form:

sister(X,Y) :-                 % X is a sister of Y if
    female(X),                  % X is female
    parents(X, Mother, Father), % this subgoal finds X's parents
    parents(Y, Mother, Father), % this subgoal tries to match X's
                                % parents to Y's parents
    X \= Y.                     % and X is not the same as Y

When it encounters a rule, Prolog takes the right hand side as a list of subgoals that must be proved in order to prove the left hand side. The goals are always satisfied from left to right. Conjunction is represented by a comma; disjunction is represented by a semi-colon. All of the facts and rules with the same functor and arity can be taken as a disjunction of rules, which Prolog will search through from the first to the last in trying to satisfy a goal (answer a question). Thus, the equivalent of writing a function will often consist of writing multiple Prolog facts and rules. This is especially true of recursive functions, which will typically have one or more rules for boundary conditions followed by the recursive rule(s). This collection of facts and rules is typically called a program.

Basic Prolog data structures consist of numbers, symbols, structures, and lists. Structures are essentially facts without periods used as data. Thus, you can build things like:

book(moby_dick,author(herman,melville)).

Lists are similar to Lisp lists internally, but are represented differently to the programmer. The syntax for a list is a comma-separated list of items enclosed in square brackets: [a,b,c]. The empty list is []. [A | B] is a convenient way to distinguish the head (or car) and the tail (or cdr) of a list: A would unify with the head and B with the list representing the remainder of the list. Thus, a program to test for membership in a list would look like this:

member(X,[X|_]).        % if X equals the head, then X is a member of
                        % the list,
                        %  _ is an anonymous variable that unifies
                        % with anything
member(X,[_|Y) :-       % otherwise, X is a member of the list
    member(X,Y).        % if X is a member of the tail of the list

That covers the basics of Prolog syntax, but there are a few things to be aware of in order to follow all of the examples. When a Prolog rule fails, or a user asks for another answer by typing semicolon after Prolog's response, the Prolog system tries to satisfy the current goal again by searching for additional facts or rules in the database that match the goal. This is called backtracking, and it is how multiple rules and facts become a disjunction constituting a single program (or function). However, for cases where backtracking is undesirable, Prolog provides the cut function, '!'. When Prolog reaches the cut, it prevents the system from backtracking from the current goal. An example may help clarify. This is a program to delete all occurrences of an item from a list. It works by examining each element of the list and leaving it out if it matches the item to be deleted.

delete(_,[],[]).           % deletion from an empty list returns an
                                empty list
delete(X,[X|L],L1) :-      % if the item to be deleted matches the
                                head of the list
!, delete(X,L,L1).         % cut and try to satisfy delete with the
                                remainder of the list
delete(X,[Y|L],[Y|L2]) :-  % otherwise, return the head of the list
                                plus the result
delete(X,L,L2).            % of delete with the remainder of the list

If the second rule is matched, the third rule is not appropriate. The cut in the second rule prevents backtracking (in this case only possible if the user requests another answer) and trying the third rule and coming up with an incorrect answer.

fail is another useful item. It simply causes the current goal to fail immediately. It is used to create loops for input and, in conjunction with the cut, to say "quit trying to satisfy this goal if you get to this point."

Prolog also has several input and output predicates. Most of these are clear in meaning, but you'll want to note that nl is newline.

This has been a very sketchy introduction to an interesting language. For more information, you should consult an introduction to Prolog, a few of which are listed at the end of the article.

AAIS Extensions to Prolog

Objects aside, AAIS's Prolog systems add several useful extensions to the Edinburgh Prolog dialect. (There is no real standard for Prolog, but Edinburgh Prolog is functions as a de facto standard.) The AAIS system operates in two modes: AAIS mode and Edinburgh mode, with the extensions available in AAIS mode only. Thus, you can use the system as a typical Edinburgh Prolog if you choose.

The most obvious extension is its treatment of characters and strings. Character constants are typed between two backquotes and may be up to four characters long. The four-byte character constant is the extension here. Strings in Prolog can be entered by enclosing the in double quotes, but they are typically immediately converted to lists of characters. In AAIS mode, AAIS Prolog handles strings as blocks of characters and provides a number of built-in string manipulation routines.

Other extensions are for I/O. One is the provision of C-style I/O streams, which can deal with the data fork of a file. AAIS Prolog also provides routines for coping with the Macintosh file system, including ask_for_input_file and ask_for_output_file which hide most of the details of the corresponding system routines.

Objects

The biggest difference between AAIS Full Control Prolog and most Prologs is the addition of objects. As you will probably have noticed, either from your own knowledge of Prolog or my quick overview, it not immediately obvious how to handle objects in Prolog. Just to make matters more interesting, the objects here are performing two functions, and the manual doesn't really distinguish between them.

The first purpose of these objects is simply to provide the equivalent of C structures or Pascal records. Thus, they are typed objects with strongly typed fields. The possible field types are boolean, signedbyte, char, word, long (or integer), single, double, extended float, ptr, handle,other object types, ptrs to a specified type, block (which reserves a block of memory of a specified size without typing), C strings, Pascal strings, and prolog_data (which point to regular Prolog objects). As you can see, you can build just about any record you might.

New types are defined in one of three ways. define_record takes a typename and a list of field declarations and creates a new type with base type ptr. The definition of fontinfo is

:- define_record(fontinfo, [ascent=word, descent=word, 
    widmax=word, leading=word].

define_handle_record is similar, but the parent type of records defined with it is handle. define_sub_record allows the specification of the parent type of a record, providing object inheritance. Only a single parent may be specified; so multiple inheritance is not supported. One thing to note about handle and ptr objects is the the former are allocated using NewHandle, while the latter are allocated by Prolog's internal memory management. It is possible to define fields for an object which overlap other fields, like C unions. Thus, rects can be treated as consisting of either four integers or two points.

Specific objects are created and destroyed using create and destroy. Create takes a type name, a variable which will refer to the new object, and 0 or more arguments for the initialization functions for that type. Destroy simply takes a reference to the object to be destroyed.

Access to an object's fields can be accomplished in a couple of ways. You can use get_field and set_field, specifying the object, the field name, and either the variable to store the value in or the new value. However, you can also use object^.field to reference a field and use is to get the value out or put a new value in.

?- create(rect,A), A^.top is 30, A^.bottom is A^.top + 250.
    A = <rect#10325148:[30, 0, 280, 0]>

The variable A is bound to the new rectangle object.

Types are themselves objects in this system. For greater control over new types, instead of using define_record, etc., one can use the create(basic_type,…) to define new types. This allows the specification of the functor and arity of an initialization function for the type and the functor of a clean up function. When a new object is created, its ancestor's initialization functions are executed, followed by its own. The arguments to the initialization functions are create's arguments 2 through 1 + the arity of the initialization function, i.e. the object being created plus as many subsequent arguments to create as needed. The only argument to the clean up function is the object to be destroyed. Thus, the initialization and clean up functions work a lot like C++'s constructors and destructors.

Methods

Thus far, we have objects which contain data, have parent types, and have associated initialization and clean up functions. However, a key piece of the puzzle is still missing. How are we to handle methods in the Prolog environment? What AAIS did was to provide a new kind of rule, called a method rule, which specifies the object type to which it is applicable. The syntax for method rules is

typename <-  functor(object, args) :- subgoals.

Method rules work as you would expect for an object-oriented environment. If a method rule is defined for a type, then objects of that type will use that rule. If Y is a subtype of X, objects of type Y will use X's method rules unless a method rule with that functor and arity has defined for Y. In cases where a default rule is desired, since there is no root object type which all others inherit from, you can use default as the type name. You cannot have standard Prolog rules and method rules with the same functor and arity.

The Environment

AAIS Full Control Prolog 3.1 comes on floppy disks with a 2 volume manual for version 3.0 plus a 3.1 update manual. Installation is a simple of matter of copying the floppies onto your hard disk. It runs on a Macintosh Plus or better running System 6 or 7. It does require at least 2 megabytes of memory, more for large projects. At the moment I have 2.5 megabytes allocated to it. I have run the system on a Macintosh II (Nope, no letters; we're talking the original here.) and on a PowerBook 165 with virtual memory turned on. In both cases, it has been a comfortable system to work with, though I prefer the PowerBook except for the small screen. You will almost invariably have a minimum of two windows open: the Query window and an edit window for the program you're working on, so screen size can become an issue, especially when you add a couple of windows created by the program you're working on. The Prolog takes up about 2.5 megabytes on disk. All in all, I find the memory and disk space requirements very reasonable in comparison to things like our dear friend MacApp + MPW + …. It also compare favorably to MCL 2.0 which uses about 6 megabytes of disk space and needs at least 3 megabytes of RAM to run comfortably in my experience. The speed of execution also compares well with MCL, which is the closest environment I'm aware of.

Using the System

Full Control Prolog takes about 20 seconds to start up on my PowerBook. At startup, it presents you with a Query window, which is similar in function to MCL's Listener. This is the window where you type questions. You can also open edit windows where you type facts and rules. The system has pretty standard search functionality with one useful addition. One menu item is Find definition…. You provide a functor and arity and get back a list of all of the facts and rules with that functor and arity. This works for anything that is currently in Prolog's in-memory database, in essence the current running program.

To get things into memory, you can use the Eval menu to consult a file (the only possiblity in most Prologs, of course), to consult the current window, or to consult the current selection. This last can be very useful for quick bug fixes, though I've never had a consult take long enough to be frustrating.

A major advantage of this system is the same one you've heard before about dynamic programming environments. You can easily build and fix programs incrementally. Although it's possible to wipe the slate clean and start over, it's actually easier to simply add a few new rules or replace some incorrect rules with correct ones and go on.

I do have a few caveats about the environment, generally coming from a lot of work with MCL in recent months. AAIS Full Control Prolog doesn't really have any online help, and I find that frustrating at times. After all, who wants to go digging in the manual? On the other hand, the manual is indexed and is sensibly divided into chapters, so I haven't had any real difficulties finding what I wanted.

A second pet peeve, which some would probably not mind at all, is that if you try to re-execute a question by putting the cursor on the first line of the question and pushing enter, it works, but it moves the entry point up to write underneath that question (just like the MPW shell). This means that your query window is no longer in chronological order. I prefer MCL's method, where the thing to be executed is copied to the bottom of the window and then executed.

Finally, when you consult a window or selection, there's no clear indication that the consult is happening (unless it produces warnings or errors) or when it is finished. Again, I'm spoiled by MCL and MPW's status messages. MCL also prints the result from the last function in the listener window.

Despite these problems, the environment is very usable. The error messages are usually clear. Debugging is fairly standard Prolog debugging, but that has been adequate so far.

But Can You Do Real Programming?

Of course, the real test of a system, for this audience at least, is whether or not it can be used for serious program development. The answer to that is, I think, a qualified yes. The qualification comes from two sources. First, distribution of programs requires the purchase of a separate runtime distribution system and license. Second, I have spent most of my time with the system so far doing pretty standard Prolog things. I hope to spend some more time working on "real program" type things and do a followup article in an upcoming issue.

The second, and significantly larger, volume of the AAIS Prolog manual is on Programming the Environment. The first part of the manual describes the objects and how they, and the rest goes on to tackle specific issues. I shall go through chapters 4 through 9 of the manual and discuss briefly what each of those chapters covers. Then I'll discuss the source code that comes with the system. This should give a good initial feel for the viability of the system. In one or more future articles, I plan to describe some other programs including implementations of some of the MacApp examples.

At the outset, one should understand that AAIS Full Control Prolog does not purport to provide an application framework as such. However, it does provide a number of pre-defined object types which are important for building user interfaces. These are covered in chapter 4-6, divided into windows, graphic objects, and menus.

Chapter 4 describes windows. There are a number of pre-defined window types. basic_window is the ancestor of all other window types. Two dialog types are provided: basic_dialog and no_interrupt_dialog which inherits from basic_dialog. There are two window types for handling text, text_entry_window which may be read only or editable, and file_edit_window, which adds file information to the text_entry_window type. There are also drawing window types which inherit from basic_drawing_window. The four subtypes of this are bitmap_window, bitmap_view_window, picture_window, and picture_view_window. The bitmap windows remember their pictures as bitmap for cut/copy/paste and redraw, while the picture windows remember the commands. The view windows are resizable and have scrollbars; the others are fixed size without scrollbars. The manual also dicusses how to define additional window types.

A number of functions for manipulating windows are provided. There are also a number of methods defined for windows which should be overridden by users to handle events.

Graphic objects in AAIS Prolog are similar to views in MacApp. They exist inside windows; controls are a type of graphic object, each graphic object has its own coordinate system, pen, text font, and clip region; and there is an active graphic object. Sound familiar? The provided graphic objects include icons (which are not controls), buttons, check boxes, radio buttons, select_one and select_any (which manage groups of radio buttons and check boxes, respectively), scrollbars, display lists, text and integer entry objects, and drawing objects for bitmaps and pictures. As with windows, there are a number of methods defined to manage the various graphic objects, and methods to be overridden to handle events. And, of course, you can create your own graphic object types. One caveat on graphic objects is that they must be created programmatically. There is no equivalent to ViewEdit or its more usable successors.

There are two menu-related objects. One is the menus themselves, with which the menu items are associated. These have methods to add and remove menu items, enable/disable the menu or its items, and to identify enablers for a menu item. These enablers make the menu item's status depend on the state of a window or graphic object. This is useful for handling the edit menu, since the state of the items typically depends in part on whether or not the active window has a selection in it. Each menu item has a goal associated with it to be satisfied whenever the menu item is selected. It is also possible to define a default goal for the menu, which can be used for things like the desk accessories in the Apple menu (and is used for that by the development environment code).

The second menu-related object is the menu list. Menu lists are associated with window types and define what menus should be available when a specific window type is active. Thus, if you have one window type for which a sort menu makes sense and another for which it doesn't, you define the menu lists for the two types accordingly and the system then ensures that the menubar will contain the correct menus for the active window.

Besides the provided user interface objects, we programmers typically worry about our access to the toolbox and our ability to access other code. So you'll be glad to hear that it is possible to define both ROM traps and foreign code functions. Most of the ROM traps from Inside Macintosh volumes 1-6 are provided with the system, along with a guide explaining what is and is not there by chapter. In addition, the manual explains how to define additional ROM traps using define_rom. It also describes how to access foreign code functions, providing examples for MPW C and Think C.

Besides a fairly good manual, the system comes with a fair amount of example code. Unfortunately, that doesn't include a full typical Macintosh application, but it does include a number of examples some of which do include window and graphic object code, and it includes a significant amount of the code for the programming environment. This includes examples of windows, graphic objects, menus, foreign functions, defining new types. One notable point about the examples is that they include working apple events.

Conclusion

"So," you ask, "should I run out and buy a copy?" Well, as usual, that depends. The development system costs $595, and you do have to plan to pay for the runtime system and license. Technical support is provided free via phone, US mail, and AppleLink. There isn't an application framework as such, but a lot of what you get from such a framework as far as event handling, etc., is already there in the system, and user interface objects are provided. You have an OODL in a dynamic environment. Prolog is very different from the object-oriented languages you may be accustomed to, but it is most difficult at the very beginning, when you're making the mind shifts to logic programming, and when you're reaching the expert level and working on performance issues. The language is well-suited for some kinds of applications, especially in artificial intelligence domains. To me, this system is valuable because it gives me Prolog plus the ability to create a Macintosh interface. If you're looking to do development in Prolog on the Mac, this is your choice. If you're looking for an OODL on the Mac, especially if your domains are likely to fit well with logic programming, the system is definitely worth consideration.

For information, contact
Advanced A.I. Systems
P.O. Box 39-0360
Mountain View, CA 94039-0360
(415) 948-8658
Fax: (415) 948-2486
AppleLink: AAIS

Books on Prolog

Clocksin and Mellish. Programming in Prolog. Springer-Verlag.
Bratko. Prolog Programming for Artificial Intelligence. Addison-Wesley.
Sterlin and Shapiro. The Art of Prolog. MIT Press.
Ross. Advanced Prolog, Techniques and Examples. Addison-Wesley.