# Class 33: Logic Programming (3)

Back to Logic Programming (2). On to Haskell (1).

Held: Friday, April 21, 2006

Summary: Today we explore some particular examples in Prolog.

Related Pages:

Due

Assignments

• Read the first five sections (Introduction; Values, Types, and Other Goodies; Functions; Case Expressions and Pattern Matching; Type Classes and Overloading) of A Gentle Introduction to Haskell.

Notes:

• Have a great weekend!

Overview:

• Detour: Notation.
• Numbers.
• List Operations.
• Polynomials.

## Detour: Notation

• Predicates, Functins, and Contants: Begin with lowercase
• Variables: Begin with Uppercase.
• List with car X and cdr Xs: `[X|Xs]`
• List with elements X0,X1,X2,X3: `[X0,X1,X2,X3]`
• Loading a file: `['filename'].`

## Numbers

• Suppose we represent n as a list of n 1's.
• How can we write predicates that do computation?
• Here's a start for addition. The `add` predicate takes three parameters: the first addend, the second addend, and the result.
```A1: add([],X,X).
```
• We can see how this works to confirm that 2 + 3 = 5.
```? add([1,1], [1,1,1], [1,1,1,1,1])
// use A2 with
//   Remaining0 = [1]
//   PartialResult0 = [1,1,1,1]
// use A2 with
//   Remaining0 = []
//   PartialResult0 = [1,1,1]
// use A1 with
//   X0 = [1,1,1]
? // nothing left to prove?
```
• We can use this to find out what number we add to 3 to get 5.
```? add(X, [1,1,1], [1,1,1,1,1]).
// use A2 with
//   X = [1|Remaining0]
//   Remaining0 undefined
//   PartialResult0 = [1,1,1,1]
// use A2 with
//   Remaining0 = [1|Remaining1]
//   Remaining1 undefined
//   PartialResult1 = [1,1,1]
// Note A1 and A2 match
// use A1 with
//   Remaining1 = []
//   X = [1,1,1]
? // Nothing left
//   X = [1|Remaining0]
//   Remaining0 = [1|Remaining1]
//   Remaining1 = []
// => [1,1]
```
• How would we write a less-than-or-equal-to (`le`) predicate?
• How would we write a `multiply` predicate?
• How would we write a `factorial` predicate?
• How would we write a predicate that can be used to idenfity the minimum element in a list of numbers?

## List Operations

• How would we write a predicate, `contains(L,X)`, that determines ifL contains X?
• How wuld we use `contains` to Write a predicate that determines whether a list is a permutation of the word "ingrate".
• How would we modify that so that it works for words that have repeated letters e.g. "prolog".

## Polynomails

• Suppose we build polynomials using the zero-ary function `x`, and the binary operations `plus` and `times`.
• For example, 3x2 + 5x + 4 would be represented as
`plus(plus(times(3,times(x,x)), times(5,x)), 4)`
• How would we write the predicate, `substitute(X, Exp, Result)`, that holds if `Result` is the result of substituting `X` for each `x` in `Exp`.
• How can we do more to simplify?

Back to Logic Programming (2). On to Haskell (1).

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Wed May 10 09:03:03 2006.
The source to the document was last modified on Thu Jan 12 09:00:38 2006.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS302/2006S/Outlines/outline.33.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu