MuLE/Scheme Warm-up Lab

SLic rename, unname, answer, writeanswer.

Assumptions

This lab assumes that one is familiar with the DrScheme environment and has seen MuLE and one of its associated languages. No understanding of how the SLic interpreter works is required.

 

Objective

After completing this lab, one should feel more comfortable with both the language scheme and the MuLE architecture.

 

Overview of SLic

SLic is a logic language that provides some of the basic features found in declarative languages like Prolog. The declarative/logic paradigm is a unique paradigm that has features not found in languages of other paradigms. Furthermore, logic is a basic concept that is important in many parts of the computer science curriculum.

In general, declarative programs describe properties of the solution as a collection of "facts" and "rules" (called the database), but do not specify how to compute the solution. Instead, the database engine derives the actual solution using predicate calculus to infer valid statements. For example, in a procedural language, when we need to sort a list of items, we write procedures to compare two items, to swap two items, and finally, an algorithm to specify when to compare items and when to swap them. In a declarative language, we simply state the current list as a "fact" and that a sorted list is a permutation of the order of the elements in the list such that for any two consecutive items in the list, a given relationship holds. The database engine will use inference rules to deduce the sorted list.

Interpreters for declarative languages also employ unique algorithms (resolution, backward or forward chaining, and unification) not found in other language paradigms. Although the interpreter still has a parser, instead of an "execute" component it has a database engine consisting of search, unification, inference, and output components (with auxiliary functions). (The parser in SLic has a less important function than the parsers of MuLE’s other languages, SLam, SPoc, and SOOP.) In operation, an expression is read by the interpreter and parsed to determine whether the expression is a fact (which describes an attribute), a goal or query (which is the question to be answered and which may contain variables), or a rule (which describes implications). Depending on the expression, the interpreter either extends the database (by a fact or a rule) or searches the database (under some constraints). Consequently, the SLic interpreter implementation shares the least code with MuLE’s other interpreters.

SLic searches with a back-chaining algorithm and relies on a unification function to identify unique matches. The following algorithm describes the basic iterative loop structure of the search engine of SLic.

for each sub-goal g' in the goal list g

for each set s' of variable assignments in s

for each item d in the database

sp = unify (g', d, s')

if sp = 'fail

remove s' from s

else

replace s’ with sp in s

The algorithm checks each database item against each sub-goal of the expression and finds all valid variable assignments satisfying the goal. The variable g represents the goal, and is created when the interpreter parses a goal expression into a list of sub-goals (conjuncts). The variable s represents the current list of potential variable assignments sets. As combinations of sub-goals and database items are examined, the set s will shrink when an invalid assignment is eliminated, or grow when a new, possibly valid assignment is found. Those that remain after the outer loop terminates represent the variable assignments that are valid for all database items across all sub-goals.

SLic implements the search algorithm via three recursive functions, back-chain(), prove(), and prover(), which each represent one level of the triple nested for loop in the algorithm. SLic also includes a parser function, a unification function, and a collection of auxiliary helper functions for variable substitution, time-stamping, pretty printing the answer sets and so forth. The functional decomposition of SLic makes it especially useful for programming within the context of an existing program since each function can be implemented independently if the interfaces between the functions is specified with sufficient care.

 

Overview of this Laboratory Assignment

This project requires some of the ancillary functions used by the SLic interpreter to be written. While understanding the overall architecture and flow of control of SLic is desired, it is not necessary to successfully complete this assignment.

The first task is to write a simple output function, printAnswer, to print the results of the database search. The second task is to write two functions, rename and unname, to rename variables before and after unification.

The printAnswer function takes a single argument which is either the token ‘fail or a list of items, each of which is itself a list of valid variable assignments with the following specification:

(printAnswer

(lambda (s)

....

))

printAnswer should output "fail" when given the ‘fail token, "true" when given the empty list (this is not exactly correct, but is explained in more detail later), and each list of variable assignments on a separate line for all other inputs. In the inference engine context, the empty list results from a successful search when no variables exist in the original query/goal.

The second part of the project is to implement some variable manipulation functions required by the unification function (i.e. these functions are necessary for unification to work properly but are not called by unif directly). When the same variables are used in multiple facts, rules, and queries, variable context is not clear within the database engine. Therefore prior to unification, the variables are renamed using different time stamps for each expression. The function rename inputs an expression and a timestamp and replaces all variables in the expression with a variable-timestamp pair according to the following specification.

(rename

(lambda (expr ts)

....

))

The return value is the expression, expr, in which all variables are renamed. For example, if rename were called with (eats X Y) and a time stamp of 0, the resulting expression would be (eats (X 0) (Y 0)). A boolean helper function, variable?, is available in SLic already to determine if an item is a variable or not.

After unification, a similar unname function must be written which takes an expression and replaces renamed variables with their original names. Another boolean helper function, var?, is provided and should be used to determine whether an item x is a renamed variable or not.

 

The Details

Part I. Answer Output: printAnswer

The output for a given query can either be "fail," "true," or a list of valid variable assignments. In this part of the project, you are to write code to output the appropriate answer based on the return value of back-chain.

To write to the output window, use

(send win writeln <x>)

<x> can be a string, a constant, or a list.

Part II. Variable Renaming: rename and unname

As motivation, consider the following simple SLic example:

father { X Y } if parent { X Y } and male { X } .

parent { john jane } .

male { john } .

Now, consider the goal (note, the variables are in the opposite order):

?- father { Y X } .

Without variable renaming, the result of this query would be ‘fail. Upon matching the goal and the left hand side of the rule, the database engine would conclude that only if X = Y do these terms unify. From our implied mean of this example, that could only occur if someone was his own father which makes no sense from a genealogical standpoint.

Each time a goal matches with a rule, we begin a new search through the database. This means that the variables on the right hand side of the rule (which become the new goal) must be unique from those of the database. For this reason, a time-dependent naming convention is used for variable renaming.

Before we begin matching goals with facts and rules, we rename the variables in the goal using a time stamp. Then, each database item is renamed using a new time stamp. If the LHS of a rule unifies with the goal, we use yet another time stamp to rename the RHS which becomes the new goal. The result of a successful unification is a list of valid variable assignments with each variable renamed. However, this list is not a valid solution until it successfully unifies with each conjunct of the goal. For convenience, the list is not unnamed until just before the final result is output.

For this part of the project, two functions must be written.

The remainder of this section describes the form of the expression referred to above and then gives sample parameters and return values for each of the functions written.

Facts, rules, and goals are all made up of terms. In SLic, a term has the form,

<functor> ( <p1> <p2> ... <pn> )

where <p1> through <pn> are the parameters for the function.

Using terms, we have the following form for facts, rules and goals:

fact: <term>

rule: <term> if <term1> ... <termm>

goal: <term1> ... <termm>

Note the relationship between the left-hand-side (LHS) of a rule and a fact and also between the right-hand-side (RHS) of a rule and a goal. These directly related to the predicate calculus which is the basis for all logic languages.

A term has the following form in the database.

(<functor> <p1> <p2> ... <pn>)

That is, a list, where the first element is the functor name and the remaining elements are the parameters.

To represent a fact, rule, or goal, we simply make a list of terms. Therefore:

fact: (<term>)

rule: (<term> <term1> ... <termm>)

goal: (<term1> ... <termm>)

Thus, if we enter the following:

f { x y z } .

g { X } if f { X Y Z } .

our database will have the following form:

( ( ( f x y z ) ) ( ( g X ) ( f X Y Z ) ) )

Sample parameter and return values

So, for example if rename is passed

((carnivore X) (animal X) (eatsmeat X))

it should return

((carnivore (X 0)) (animal (X 0)) (eatsmeat (X 0)))

Furthermore, if unname is passed

((((X 0) bear)) (((X 0) wolf)))

it should return

 
(((X bear)) ((X wolf)))

If printAnswer is passed

((((X 0) bear) ((Y 0) fish))  (((X 0) wolf) ((Y 0) rabbit)))

then writeAnswer is passed

(((X bear) (Y fish)) ((X wolf) (Y rabbit)))

 

Part III. What to Turn in

The faculty member using this lab should fill in the details for project submission and perhaps grading details.