(go back)

# Gottfried Leibniz

• "Thinking can be usefully understood as a computational process"
• rules of arithmetic can be used to deal with abstract numbers symbolically
• thus, similarly rules of logic can be used to deal with abstract ideas symbolically as well

# Knowledge Base Techniques

## Back-chaining

• Chains backward from the query to the atomic sentences in the KB

## Back-tracking

• When a failure is found in one path of the chain, but another path may be tested. Back-tracks back up and down another branch

# Prolog

## Basic Syntax

• predicate definition: predicate(arg1,arg2,arg3)
• conditional statements: predicate(args) :- anotherPredicate(args).
• boy(Name) :- male(Name), young(Name).
• term: like a data structure, can be used as an argument to a predicate

## Lists

• Equal if: same number of elements in same positions
• Vertical Bar notation: v-bar can be inserted between elements; the elements that follow the bar become elements of a new list. Eg:
• [ a, b, c ] == [ a | [ b, c ] ]
• the opposition operation can be done too -> remove a bar, merge the following list's elements into the current list
• General Rules:
• X can match anything -- a single value element, or a list of elements (but NOT free-form elements not contained in a list)
• [ X ] matches only a list with 1 element (that 1 element could be another list, remember!)
• [ X | Y ] matches only a list with 1 or more elements
• [ X , Y ] matches only a list with 2 elements

## Arithmetic

Arithmetic expressions made up of variables, integers, parentheses, and these operators:

• +
• -
• *
• // (integer division)
• / (regular decimal dividions)
• mod
• ^

## Comparison

Predicates for comparison: <, =<, >, >=

Predicate for equality of arith expression: =:=

## Assignment (is)

Usage: variable is arith_expression

• if variable is unassigned, assigns result of arith expression to the variable
• else, if variable is assigned, tests for equality between variable value and expression like =:=

## Common Functions

• member(X,List). // indicates if X is a member of List
• sum(+X, +Y, -Z). // indicates X,Y must be provided as inputs, Z is output

## Command-Line

1. go to /sw1/Eclipse/bin/i386_linux/eclipse
2. run: ./eclipse -b yourfilename.pl

# Recursion

## General Procedure:

1. Consider the Head and Tail of the list
3. Recursively Process the Tail

## Hints:

• In developing a recursive function, step through several iterations of successive values until a general pattern can be spotted

## Example functions developed in class (see notes 04):

• member( X, List ).
• append( List1, List2, ResultList ).
append( [ ], List2, List2 ).
append( [ X | List1 ], List2, [ X | Result ] ) :- append( List1, List2, Result ).
• sum( ListOfNumericElements, Sum ).
sum( [ ], 0 ).
sum( [ Head | Tail ], S ) :- sum ( Tail, Q ), S is Q + Head.
• length( List, LengthOfList ).
length( [ ], 0 ).
length( [ Head | Tail ], N ) :- length( Tail, M ), N is M + 1.
• writeList( List ).
writeList( [ ] ).
writeList( [ X | Tail ] ) :- write(X), nl, writeList(Tail).
• reverseWriteList( List ).
reverseWriteList( [ ] ).
reverseWriteList( [ X | Tail ] ) :- reverseWriteList(Tail), nl, write(X).

# Constraint Satisfaction Problems

examples:

• map colouring
Example: using "Generate & Test" pattern Constraints: 5 countries: A, B, C, D, E; 3 colours: red, blue, white

/* define the colours */
colour(red).
colour(blue).
colour(white).

/* solve; first Generate (values) */
solve( [ A, B, C, D, E ] ) :- colour(A), colour(B), colour(C),
colour(D), colour(E),
colour(D), colour(E),

/* then Test (constraints) */
not A = B, not A = C, not A = E, not A = D,
not B = C, not C = D, not E = D.

Note that this uses the simple Generate and Test approach which is highly inefficient. Prolog will generate all the values for A through E first, before testing any constraints. Prolog will assign all the same values the first time, then change the last variable through all combinations of possible values, before moving to the second last variable, etc. This results in many 'fails', which means a lot of back-tracking, and thus very slow to find any solution, if one exists. For best performance, interleave Tests with Generated values. Must always generate values though, even if they are known
• crypt-arithmetic problem solving
SEND
+ MORE
-----
MONEY
• scheduling

## Pattern for solving:

1. identify the domain values
2. choose a predicate (usually one, sometimes two) to generate values for variables
3. choose variables that will be set with the values of the particular domain
4. define the domain with actual constants via the predicate
5. implement the constraints one at a time; generate variable values just before testing for most efficient program
• implement additional helper predicates as needed
• may choose an optimal order for generating values by creating a dependency graph (start with the most 'independent')

# Natural Language Understanding

## Linguistics

• Morphology: roots of words, prefixes, suffixes
• Syntax: how are the words grouped
• Semantics: what do the words mean?
• Pragmatics: what are the words being used for?

## Lexicon

• Word categories of the language, and the vocabulary in each category
• Articles: a, the
• Proper nouns: Mary, John, Toronto
• Common nouns: boy, sweater, milk
• Transitive verbs: kick, love, throw
• Intransitive verbs: walk, sleep, die, listen
• Copula verbs: be, seem, ...
• Prepositions: in, on, from, beside, ...

## Grammar

• lexical (terminal) categories, like an article or transitive verb; written in lower case
• group (non-terminal) categories, like a phrase or a sentence; written in upper case
S    -> NP VP
VP   -> copula_verb Mods
VP   -> transitive_verb NP Mods
VP   -> intransitive_verb Mods
Mods -> []
Mods -> PP Mods
PP   -> preposition NP
NP   -> proper_noun
NP   -> article NP2