Logic

From CS 61A Wiki
Jump to: navigation, search

Logic is a declarative query programming language, in which the user imputes fact in order to solve a query. Logic is a complete implementation that depends upon the Scheme project as data records are expressed as Scheme lists, and queries are expressed as Scheme values.

Facts and queries

Logic works by accepting user-stated fact and logically deducing query statements from those facts. A fact statement in logic consists of one or more lists following the keyword fact. Each fact statement is a relation. For example, the first line states that the parent of barack is abraham.

logic> (fact (parent abraham barack))
logic> (fact (parent abraham clinton))
logic> (fact (parent delano herbert))
logic> (fact (parent fillmore abraham))
logic> (fact (parent fillmore delano))
logic> (fact (parent fillmore grover))
logic> (fact (parent eisenhower fillmore))
 
 
logic> (query (parent abraham ?child))
Success!
child: barack
child: clinton

Using the facts stated, we can easily find all the parent relations between one and another. Below, the query statement asks for all of the names that have abraham as its parent. If there exists such relationship, logic will output Success! followed all entries that satisfy the query.

Compound facts

(fact <conclusion> <hypothesis0> <hypothesis1> ... <hypothesisN>)

Compound facts are written beginning with a conclusion, followed by hypotheses. For the conclusion to be true, all of the hypotheses must be satisfied.

logic> (fact (child ?c ?p) (parent ?p ?c))
 
logic> (query (child ?child fillmore))
Success!
child: abraham
child: delano
child: grover

The fact can be read as "?c is the child of ?p, provided that ?p is the parent of ?c."

Recursion

Logic also supports recursion, that is, the conclusion of a fact may depend on a hypothesis that contains the same symbols.

logic> (fact (ancestor ?a ?y) (parent ?a ?y))
logic> (fact (ancestor ?a ?y) (parent ?a ?z) (ancestor ?z ?y))
 
logic> (query (ancestor ?a herbert))
Success!
a: delano
a: fillmore
a: eisenhower

Hierarchical facts

Fact and query lists can also contain lists, providing a way to represent hierarchical data. For example, we can assign colors to dog names.

logic> (fact (dog (name abraham) (color white)))
logic> (fact (dog (name barack) (color tan)))
logic> (fact (dog (name clinton) (color white)))
logic> (fact (dog (name delano) (color white)))
logic> (fact (dog (name eisenhower) (color tan)))
logic> (fact (dog (name fillmore) (color brown)))
logic> (fact (dog (name grover) (color tan)))
logic> (fact (dog (name herbert) (color brown)))
 
logic> (query (dog (name clinton) (color ?color)))
Success!
color: white
 
logic> (query (dog (name clinton) ?info))
Success!
info: (color white)

Sources