The cycle of eval and apply unwinds the means of combination and the means of abstraction in the language. This cycle is the basic structure of any interpreter. Once you have a basic idea of an interpreter, you can build any language.

Inventing a new language can be a method to gain control over complexity. Computer programming is primarily a way to express ideas, and only incidentally has to do with getting a computer to do something. To communicate new kinds of ideas, new modes of expression are required.

In this lecture, and the following one, we will build a very different language, which won't allow us to think about programming in terms of procedures.

Up next:

1. Show what the language looks like.

2. Show how the language is implemented.

Thirdly, we'll demonstrate a nice use of streams to avoid backtracking.

In the first set of lectures, we covered the distinction between the declarative knowledge of mathematics, and the imperative knowledge of computer science. Can this gap be bridged?

son-of adam abel
son-of adam cain
son-of cain enoch
son-of enoch irad

One fact son-of adam cain can be used to answer multiple different questions: what is the relationship between adam and cain? Who is the son of adam? Who is cain a son of?

One piece of declarative knowledge can be used as the basis of many different kinds of imperative knowledge; this is the essence of the power of this programming style.

Rules of inference.

if (son-of ?x ?y) and
   (son-of ?y ?z)
then (grandson ?x ?z)

Let's take a step back, and look at a procedure for merging two sorted lists.

(define (merge x y)
  (cond
   ((null? x) y)
   ((null? y) x)
   (else
    (let ((a (car x)) (b (car y)))
      (if (< a b)
          (cons a
                (merge (cdr x) y))
          (cons b
                (merge x (cdr y))))))))

Below is the specific bit of logic which allows the program to work.

(let ((a (car x)) (b (car y)))
  (if (< a b)
      (cons a (merge (cdr x) y))

A deduction is happening here.

if
    (cdr-x and y merge-toform z)
and
    a < (car y)
then
    ((cons a cdr-x) and y
     merge-to-form (cons a z))

The other clause is essentially identical.

if
    (x and cdr-y merge-to-form z)
and
    b < (car x)
then
    (x and (cons b dry-y)
     merge-to-form (cons b z))

And for completeness, we have these two basic statements.

For all x, (x and () merge-to-form x)
For all y, (() and y merge-to-form y)

The procedural approach could be visualised with merge as a black box, taking the inputs x and y, and outputting ans. The rule-based approach, in juxtaposition, would be visualised as a cloud containing merge-to-form, x, y and z.

With these fundamental rules of logic, it should be possible to ask:

(1 3 7) and (2 4 8) merge-to-form ?
(1 3 7) and ? merge-to-form (1 2 3 4 7 8)
?x and ?y merge-to-form (1 2 3 4 7 8)

There are two major differences to procedural programming which are immediately apparent.

1. Not computing functions (using relations instead).

2. Due to the use of relations, there's not necessarily one answer.

This style of programming is called logic programming. Use logic to express what is true, use logic to check if something is true, use logic to find out what is true.

An example of a logic programming languages is Prolog. We will implement a query language, which will contain the essence of Prolog, and roughly the same power and limitations.

Let's start building and begin with a collection of facts.

(job (Bitdiddle Ben) (computer wizard))
(salary (Bitdiddle Ben) 40000)
(supervisor (Bitdiddle Ben)
            (Warbucks Oliver))
(address (Bitdiddle Ben)
         (Slumerville (Ridge Road) 10))

(address (Hacker Alyssa P)
         (Cambridge (Mass Ave) 78))
(job (Hacker Alyssa P)
     (computer programmer))
(salary (Hacker Alyssa P) 35000)
(supervisor (Hacker Alyssa P)
            (Bitdiddle Ben))

(address (Tweakit Len E)
         (Boston (Bay State Road) 22))
(job (Tweakit Len E)
     (computer technician))
(salary (Tweakit Len E) 15000)
(supervisor (TweakitLen E)
            (Bitdiddle Ben))

(address (Reasoner Louis)
         (Slumerville (Pine Tree Road)
                      80))
(job (Reasoner Louis)
     (computer programmer trainee))
(salary (Reasoner Louis) 20000)
(supervisor (Reasoner Louis)
            (Hacker Alyssa P))

(job (Warbucks Oliver)
     (administation big wheel))
(salary (Warbucks Oliver) 100000)
(address (Warbucks Oliver)
         (Swellesley (The Manor)))

As with any language, there are three fundamental questions.

1. What are the primitives?

2. What are the means of combination?

3. What are the means of abstraction?

There is one primitive: query.

(job ?x (computer programmer))
results:
(job (Hacker Alyssa P)
     (computer programmer))

(job ?x (computer ?type))
results:
(job (Bitdiddle Ben) (computer wizard))
(job (Hacker Alyssa P) (computer programmer))
(job (Tweakit Len E) (computer technician))

However it doesn't match:

(job (Reasoner Louis) (computer programmer trainee))

as Louis' job description has three symbols.

The addition of a full stop rectifies the above issue.

(job ?x (computer . ?type))

List all people who work in the computer division, together with their supervisors.

(and (job ?x (computer . ?y))
     (supervisor ?x ?z))

List all people whose salary is greater than 30000.

(and (salary ?p ?a)
     (lisp-value > ?a 30000))

List all people who work in the computer division, who do not have a supervisor who works in the computer division.

(and
 (job ?x (computer . ?y))
 (not (and (supervisor (?x ?z)
                       (job ?z (computer . ?w))))))

The means of combination are logical operations: and, not, or and a hack, lisp-value.

Rules are the means of abstraction.

(rule
 (bigshot ?x ?dept) ; rule conclusion
 (and               ; rule body
  (job ?x (?dept . ?y))
  (not (and (supervisor ?x ?z)
            (job ?z (?dept . ?w))))))

Revisit merge in terms of rules.

(rule (merge-to-form () ?y ?y))
(rule (merge-to-form ?y () ?y))

A rule with no body is always true.

(rule
 (merge-to-form
  (?a . ?x) (?b . ?y) (?b . ?z))
 (and (merge-to-form (?a . ?x) ?y ?z)
      (lisp-value > ?a ?b)))
(rule
 (merge-to-form
  (?a . ?x) (?b . ?y) (?a . ?z))
 (and (merge-to-form ?x (?b . ?y) ?z)
      (lisp-value > ?b ?a)))

Now test.

(merge-to-form (1 3) (2 7) ?x)
results:
(merge-to-form (1 3) (2 7) (1 2 3 7))

(merge-to-form (2 ?a) ?x (1 2 3 4))
results:
(merge-to-form (2 3) (1 4) (1 2 3 4))
(merge-to-form (2 4) (1 3) (1 2 3 4))

(merge-to-form ?x ?y (1 2 3 4 5))

With the last query, the slowness is blatantly evident. This is partly due to the language being doubly interpreted, but also due to the algorithm for merges being doubly recursive.