Logic languages are also referred to as declarative languages, since programs written are essentially a series of declarations. This differs from other languages, in which programs are typically composed of a number of assignments and control flow statements. [Seb99, p.612] The user defines the program by developing a database of facts and rules. These constructs do not describe how the result is to be computed, but does describe the form of the result. 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. Because users concentrate on the form rather than the method, logic languages afford a great deal of freedom. For this reason, logic languages are very powerful, and useful.
Logic languages are made up of three kinds of statements, facts, rules, and goals. Facts define simple statements, such as John is a boy, or Jim is John’s father. Rules describe implications, typically based on existing database facts. For example, a rule could declare that someone is a Holy Cross freshman, if that person goes to Holy Cross and is a freshman. We see that we create rules, based on facts already in the database. Goals are used to query the database and obtain structured information. Goals are the start of theorem proving, and are used to both determine if something is true or false, or to return all items that fit a certain criteria. Thus, by using these three types of statements together we can create programs tailored to the logical needs of the programmer.
There are however limitations to the flexibility logic languages provide. If we look at the two rules and related query:
?- chicken { peepers } .
We see that the obvious question arises, which comes first? This is a problem, since the program does not know this question is unanswerable, it will continue to cycle until resources run out. Infinite loops are a major criticism of logic languages because cycles may be hidden within levels of inference. Although many researchers believe the answer to these cycles lies within parallel computing, no solution currently exists.
It is evident that there are both pros and cons to declarative/logic programming. Logic languages remain valuable for theorem proving, and other logical mathematical uses.
SLic is a logic language that provides some of the basic features found in declarative languages like Prolog. This unique paradigm has features not found in other languages. Furthermore, logic is a basic concept that is important in many parts of the computer science curriculum.
SLic is a simple logical language. The grammar and functionality is fundamentally simple, thus learning and understanding the language should come quickly. SLic’s interpreter is one of MuLE’s interpreters for multiple programming languages. It is important to realize that SLic does not have as much flexibility or functionality as other logic languages, it is designed to be simple. The grammar may be slightly limited for this reason.
A SLic window is created by executing the file "launcher.s" in DrScheme. In the MuLE interface window that appears, click on the "SLic - functional" button or select from the pull-down menu. This opens a SLic window by binding a variable to the result of a call to the procedure make-SLic. Once in the SLic environment, existing SLic database and query files can be opened and loaded into the simple editing window of the SLic interpreter by selecting the “open” button. The opened file will appear in the upper window and may be modified before executing with the SLic interpreter. Everything typed in the lower window will be interpreted as an expression by SLic.
The SLic interface is a double paned window. Both the upper definitions window and the lower interface window can be used to enter in databases, queries and programs, though it is recommended that the definitions window be used for this purpose. The interface window accepts one argument/statement at a time and executes it when the enter key is hit, whereas the definitions window allows for several arguments/statements on different lines to be entered at once. They will only be executed when the "execute" button is clicked. All of the output will appear in the interface window. Besides this benefit, the definitions window allows for the saving and retrieving of files, opposed to the interface window which does not. If the user wishes to alternate between the two, bear in mind the environment, or list, that has been created is used by, and thus is changed by, either window.
At the command level, SLic understands three meta-commands: list, help and clear. Each command is executed in SLic by entering the command, without parentheses, at the SLic prompt.
list A debugging instruction that will list all of the environment (current variable) bindings.
clear Clears the environment (current variable) bindings. This is especially useful between program executions to clear out a previously defined database.
help Displays the SLic grammar.
Simplistic comments are allowed in SLic programs. If the first two characters on a line of a SLic program are // then the line is ignored by the SLic interpreter. There can be no white space or other characters before the //, i.e. the // must be in columns one and two of the line.
|
<slic> |
::= |
<slic_command> |
|
<slic_command> |
::= |
clear |
|
<slic_command> |
::= |
help |
|
<slic_command> |
::= |
list |
|
<slic_command> |
::= |
<slic_stmt_list> |
|
<slic_stmt_list> |
::= |
<slic_stmt> <slic_stmt_list> |
|
<slic_stmt_list> |
::= |
|
|
<slic_stmt> |
::= |
<fact> . |
|
<slic_stmt> |
::= |
<goal> . |
|
<slic_stmt> |
::= |
<rule> . |
|
<fact> |
::= |
<item> |
|
<item> |
::= |
<id> { <id_list> } |
|
<id_list> |
::= |
<id> <id_list> |
|
<id_list> |
::= |
<id> |
|
<goal> |
::= |
?- <item_list> |
|
<item_list> |
::= |
<item> and <item_list> |
|
<item_list> |
::= |
<item> |
|
<rule> |
::= |
<item> if <item_list> |
The clear command, clears the current database. The list command lists the current state of the database.
An additional constraint not depicted in the grammar is that there must be at least one space between all symbols, items, identifiers, and delimiters. For example, the following SLic would not parse correctly due to the lack of spaces.
student{Benjamin}.
The following is formatted correctly.
student { Benjamin } .
As a reminder, each line must end with a period.
Facts are an integral part of defining the database in a logic-orientated language such as SLic. The inputted fact is stored as part of the database. This database is used for evaluating queries and forming rules.
The following simple fact is interpreted as Christian is a student.
A more complex type fact is one with two parameters inside the brackets:
This fact might be interpreted as “king teaches christian”. What is important is this syntax defines a relationship teaches, between king and christian. This relationship can be further manipulated by using rules and queries. The user determines the meanings of facts inputted. This aspect of logic-orientated languages allows the user a great deal of freedom and flexibility.
Make sure you do not create facts that conflict logically. That is, they are not technically wrong, but make no sense realistically. Thinking through facts and rules is important when creating a SLic database.
The facts and rules in the example database below depend on each other and are used to form new rules and queries. You may save a database you have created or modified to an external file by using the save button on the SLic window. To open a previously saved database use the open button. Every new SLic session starts with a new empty database. After either typing a new database or opening a file with a previously saved database, select the execute option.
The discussions in sections 3.6 on rules and 3.7 on queries and their expected results will refer to this database.
Facts in SLic allow definitions of identifiers in terms of existing facts. For example, the following rule occurs in the sample database of section 3.5.
This rule uses the facts in the database of the form teaches { X Y } . , to define a teacher as anyone who is included in a fact with an identifier of teaches and is the first member of the identifier list. Thus, according to the rule and database facts, king, barr, and christian are defined as teachers.
Complex rules involve more complicated item lists on the right hand side of the if. Such statements are comprised of items and item lists joined by the keyword and. The rule,
describes a chair as any identifier in the database that is the first element of the identifier list for teaches, and is also a professor. In other words, a chair is someone who both teaches, and is a professor. Thus, king and barr are both chairs, but christian is not since he is not a professor and coleman is not because he does not teach.
The rule,
defines a studentteacher as someone who fits the criteria teaches { X Y } as well as student { X } . Thus we see this rule would yield christian as a studentteacher, since teaches { X Y } yields christian, king, and barr for the X variable, and student { X } yields christian for the X variable. The only member of both sets is christian, so he is a studentteacher, according to the stated rule.
Rules may have several variables. The rule,
defines a groupwithmaleleader as any groupofthree { X Y Z } that also satisfies male { X } . There are two groupsofthree sets, but only one has an X variable that also satisfies male { X }. The only groupwithmaleleader would be (christian, matt, rachel).
If an identifier occurs on the left hand side of an if clause, then it must also occur on the right hand side.
Using specific variable names in facts, rules and queries is not necessary.
Queries are the heart of logic-oriented languages. In SLic a query is denoted by the two character symbol ?- proceeding the command. Queries can contain constants or variables and vary with complexity.
The simple query,
returns
This query asks if christian is a student. Since there is a fact in the database student { christian } . , the query returns true. The query,
returns fail since there is no fact in the database that says dan is a student.
Another type of query involves using variables to elicit lists of all solutions to the given query. For example, the following query asks for all students in the database,
and returns several lists of a list.
We see that each student listed is part of a fact in the database. Similarly, we can write the following query to list all of the people king teaches,
which returns several lists.
All of the matches between king and X in the database for the fact teaches are returned. Multiple variables in queries can be used to return all pairs in the database for the fact teaches,
which returns the following lists.
Queries involving rules can also be written,
?-
malestudent { X } .
which returns the following list with two identifying lists.
The database of facts and rules listed below provides an additional set of example queries. [Ger93]
Listed below a number of queries are constructed with the expected SLic response.
The above query returns all X that satisfy eats { X Y } . To see all of the things a bear eats construct the following query.
Queries using rules that reference other rules can also be constructed as below.
The above query asks for identifiers that satisfy the rule of omnivore { X } which asks for all X that satisfy meatfisheater { X} and planteater { X }.
This final nonsense database of facts and rules provides another opportunity for query examples.
a { x } .
a { y } .
a { z } .
b { x } .
b { y } .
b { w } .
s { X } if a { X } .
t { W } if s { W } .
r { X } if a { X } and b { X } .
p { X Y } if a { X } and b { Y } .
q { X } if a { X } and b { Y } .
foo { a b } .
foo { c d } .
bar { b a } .
bar { d c } .
foo { e f } .
bar { e f } .
foobar { P Q } if foo { P Q } and bar { Q P } .
A series of queries and return values are listed below.
?- a { X } .
((X x))
((X y))
((X z))
?- a { x } .
true
?- a { g } .
fail
?- foo { X Y} .
((X a) (Y b))
((X c) (Y d))
((X e) (Y f))
?- a { Q } and b { Q }.
((Q x))
((Q y))
?- s { Z } .
((Z x))
((Z y))
((Z z))
?- y { Z } .
((Z x))
((Z y))
((Z z))
?- r { X } .
((X x))
((X y))
?- p { W Z } .
((W x) (Z x))
((W x) (Z y))
((W x) (Z w))
((W y) (Z x))
((W y) (Z y))
((W y) (Z w))
((W z) (Z x))
((W z) (Z y))
((W z) (Z w))
?- p { Q y } .
((Q x))
((Q y))
((Q z))
?- p { x y } .
true
?- p { a n } .
fail
?- p { X X } .
((X x))
((X y))
?- foobar { X Y } .
((X a) (Y b))
((X c) (Y d))
Note: SLic is case sensitive and at least one blank space must occur between items.
A discussion of unification will appear in a future version of this manual.