###### Books / Programming Language Design / Chapter 19

# More Prolog

## Recursion

Prolog inference rules can be recursive. For example:

These rules establish that *X* is *Y*’s ancestor if

*X*is*Y*’s father or mother (first two rules, not recursive), or- there is some
*Z*such that*X*is*Z*’s father and*Z*is*Y*’s ancestor, or - there is some
*Z*such that*X*is*Z*’s mother and*Z*is*Y*’s ancestor

Example query (using the ground truths from the previous lecture:

| ?-ancestor(grandpa, bart).true ? yes | ?-ancestor(grandpa, homer).true ? yes | ?-ancestor(grandpa, marge).no

## Numbers

A prolog variable can have a numeric value (as opposed to a symbol). The **is** keyword binds a variable to an expression with a numeric value.

Example:

| ?-A is 2 + 3.A = 5 yes

## Tuples and Lists

A tuple is a sequence with a fixed number of values. A list is a sequence with an arbitrary number (zero or more) of values.

A tuple:

A list:

Lists have an alternate syntax:

[FirstElement|RestOfList]

The alternate syntax is very useful for writing inference rules that operate on lists.

As an example: finding the smallest number in a list of numbers.

First, we can define a **min** rule which, for a pair of numbers, specifies which is the minimum:

Read the first rule as “A is the minimum of A and B if A <= B”.

Examples:

| ?-min(What, 2, 3).What = 2 ? yes | ?-min(What, 3, 2).What = 2 yes

We can define two rules for finding the smallest number in a list of numbers:

The first rule specifies that in a list where *A* is the only element, it is the smallest element. This serves as a base case.

The second rule specifies that for a list where *A* is the first element and *B* is a list containing an unspecified number of elements, the minimum value *Min* is the minimum of *A* and *SB*, where *SB* is the smallest value in *B*.

Example:

| ?-smallest(What, [11, 86, 2, 69, 22, 39, 85, 57, 78, 76]).What = 2 ? yes

## Example: Sorting

Now that we’ve defined how to find the smallest item in a list, we define how to sort a list.

The base case is that sorting a list with no elements is the empty list:

The recursive case defines what it means to sort a list with at least one element:

This rule states that the sorted form of a list is a list containing at least one element is the list where the first element is the minimum value in the original list, and the subsequent values are the rest of the elements in the original list in sorted order.

To extract the minimum element from the list, we use the built-in **append** rule. The assertion

says that *C* is the result of concatenating the lists *A* and *B*. We use this rule twice. The first use,

states that *List* is the result of concatenating two lists. The first list is *BeforeMin*. The second list has *Min* (the minimum element of the overall list) as its first element, and *AfterMin* as the remaining elements. This effectively gives us lists *BeforeMin* and *AfterMin*, which are lists with the elements that precede and succeed *Min*.

The second use,

says that *RestUnsorted* is the list formed by concatenating *BeforeMin* and *AfterMin*. We use *RestUnsorted* to define *RestSorted*:

This is a recursive application of the **sorted** rule, which here says that *RestSorted* is the elements in *RestUnsorted* in sorted order.

Example use:

| ?-sorted(What, [11, 86, 2, 69, 22, 39, 85, 57, 78, 76]).What = [2,11,22,39,57,69,76,78,85,86] ? yes

### Is this an algorithm?

In a declarative language, it becomes difficult to say what algorithm is used to compute a result. In our definition of the **sorted** rule, the definition resembles a selection sort, where we building a sorted result by repeatedly selecting the minimum element.

A difficulty with declarative programming is because the programmer does not directly specify an algorithm, it is difficult to reason about the efficiency with which the computation will be carried out.

## Merge Sort

Here is merge sort in Prolog.

Recall that merge sort is a recursive sorting algorithm based on *merging* sorted lists to produce a single sorted list that contains all of the elements from the two input lists.

Here is how we can define the merge operation in Prolog. First, the base cases:

These rules state that the result of merging any sorted list with the empty list produces that list.

A pair of recursive rules define the more general case of merging two nonempty lists:

The first rule says that the if *MinList1*, the first element of the list [*MinList1* | *RestList1*] is smaller than *MinList2* (the first element of the list [*MinList2* | *RestList2* ]), then the result of merging the two lists is *MinList1*, followed by the result of merging the lists *RestList1* and [*FirstList2* | *RestList2*]. The second rule handles the symmetric case (where *MinList2* is less than *MinList1*).

Testing the merge rule:

| ?-merge(What, [1, 3, 5, 6], [2, 4, 7]).What = [1,2,3,4,5,6,7] ?

Now that we have a merge operation, we can define the **mergeSort** rule. First, the two base cases:

These rules state that sorting a list with no elements or exactly one element produces the same list as a result.

Next, the general (recursive) case:

A few things to note here:

- The
**length**predicate asserts that the length of the list called*List*is*N* - The
**div**function does integer division *FirstLength*and*SecondLength*are the lengths required to split the overall*List*into two equal parts: the**length**predicate is used to assert that*FirstUnsorted*and*SecondUnsorted*are lists with those lengths**append(FirstUnsorted, SecondUnsorted, List)**asserts that*List*is the result of concatenating*FirstList*and*SecondList*- The recursive applications of
**mergeSort**assert that*FirstSorted*and*SecondSorted*are the results of sorting*FirstUnsorted*and*SecondUnsorted*, respectively - The clause
**merge(Sorted, FirstSorted, SecondSorted)**asserts that the overall result,*Sorted*, is the result of merging*FirstSorted*and*SecondUnsorted*

Testing merge sort:

| ?-mergeSort(What, [11, 86, 2, 69, 22, 39, 85, 57, 78, 76]).What = [2,11,22,39,57,69,76,78,85,86] ?

### Is this an algorithm?

Again, with a declarative language, it’s hard to say.

It is worth noting that the definition of our rules is pretty close to how we might define merge sort in an imperative language.