Summary

• The type of a term can be tested by the following predicates:

  • var(X) X is a (non-instantiated) variable
  • nonvar(X) X is not a variable
  • atom(X) X is an atom
  • integer(X) X is an integer
  • atomic(X) X is either an atom or an integer

• Terms can be constructed or decomposed:

  Term = .. [Functor | ArgumentList]

  functor( Term, Functor, Arity)

  arg(N, Term, Argument)

  name(Atom, CharacterCodes)

• A prolog program can be viewed as a relational database that can be updated by the following procedures:

  assert(Clause) add Clause to the program

  asserta(Clause) add at the beginning

  assertz(Clause) add at the end

  retract(Clause) remove a clause that matches Clause

• All the objects that satisfy a given condition can be collected into a list by the predicates:

  bagof(X, P, L) L is the list of all X that satisfy condition P

  setof(X, P, L) L is the sorted list of all X that satisfy condition P

  findall(X, P, L) similar to bagof

• repeat is a control facility that generates an unlimited number of alternatives for backtracking

Propositional Logic

Summary

• Input and output is done using built-in procedures.

• Files are sequential. There are two types of streams:

  • There is the current input stream and the current output stream.
  • The user terminal is treated as a file called user.

• Switching between streams is done by:

  • see(File) File becomes the current input stream
  • tell(File) File becomes the current output stream
  • seen close the current input stream
  • told close the current output stream

• Files are read and written in two ways:

  • as sequences of characters

  • as sequences of terms

  • Built-in procedures for reading and writing characters and terms are:

    • read(Term) input next term
    • write(Term) output Term
    • put(CharCode) output character with the given ASCII code
    • get0(CharCode) input next character
    • get(CharCode) input next ‘printable’ character

• Two procedures help formatting:

  • nl output new line
  • tab(N) output N blanks

• The procedure name(Atom, CodeList) decomposes and constructs atoms.

  • CodeList is the list of ASCII codes of the characters in Atom.

1. Goldbach’s conjecture says that every positive even number greater than 2 is the sum of two prime numbers. Write a predicate goldbach(N, L) that returns L as a list of the two prime numbers that sum up to the given N (which must be even).

   Read more »

Summary

• Languages generally have a small set of closed class words that are highly frequent, ambiguous, and act as function words, and open-class words like nouns, verbs, adjectives. Various part-of-speech tagsets exist, of between 40 and 200 tags.
• Part-of-speech tagging is the process of assigning a part-of-speech label to each of a sequence of words.
• Two common approaches to sequence modeling:
  • a generative approach, HMM tagging
    • The probabilities in HMM taggers are estimated by maximum likelihood estimation on tag-labeled training corpora
    • The Viterbi algorithm is used for decoding, finding the most likely tag sequence
    • Beam search is a variant of Viterbi decoding that maintains only a fraction of high scoring states rather than all states during decoding
  • a discriminative approach, MEMM (Maximum Entropy Markov Model)tagging
    • This tagger train logistic regression models to pick the best tag given an observation word and its context and the previous tags, and then use Viterbi to choose the best sequence of tags.
• Modern taggers are generally run bidirectionally

Regular Expression, Text Normalization, Edit Distance

Summary

How to perform basic text normalization tasks?

• word segmentation
• normalization
• sentence segmentation
• stemming

Problem

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Examples

1
2
3

Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.

1
2
3

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

Problem

Goal: Pack knapsack so as to maximize total value.

• There are n items: item i provides value vi > 0 and weights wi > 0
• Knapsack has weight capacity of W

Assumption: All input values are integral

Negation as failure

‘Mary likes all animals but snakes’. How can we say this in Prolog? It is easy to express one part of this statement: Mary likes any X is X is an animal. This is in Prolog: likes(mary, X) :- animal(X).

But we have to exclude snakes. This can be done by using a different formulation:

If X is a snakes then Mary likes X is not true.

Otherwise if X is an animal then Mary likes X.

That something is not true can be said in Prolog by using a special goal, fail, which always fails, thus forcing the parent goal to fail. The above formulation is translated into Prolog, using fail, as follows:

1
2
3
4

likes(mary, X) :-
    snakes(X), !, fail.
likes(mary, X) :-
    animal(X).

or

1
2
3

likes(mary, X) :-
    snakes(X), !, fail;
    animal(X).