proglang-11-14-19.md

Prolog II - Programming Languages - Nov 14th, 2019

Table of Contents

• Unification
• Backtracking
• Lists
  • Head & Tail
  • printallin(X)
  • memberoflist(X)
• Math
• Exercises
  • length
  • fibonacci
  • mystery1
  • mystery2

Unification

Trying to match two values

• Atoms and Values will unify to themselves
  • foo = foo
  • 3 = 3
• Predicates match if their their parameters match
  • foo(a) = foo(a)
  • foo(a) ≠ foo(b)
• Variables will match with anything if they are not already set
  • X = a
  • foo(a) = foo(X)

Backtracking

Once Prolog finds an answer to a query, it will go back and try to find any other answers avaiable. It continues searching after you press semicolon in the console.

Lists

?- X = [1,2,3].
?- X = [a, b, c, 9].

Head & Tail

?- [H|T] = [1,2,3,4,5].

printallin(X)

in(parkslope, brooklyn).
in(tandon, brooklyn).
in(brooklynbridge, brooklyn).

printallin(X) :- in(Y, X), writeln(["It's here", Y]), fail.

Output of printallin(brooklyn):

[It's here, parkslope]
[It's here, tandon]
[It's here, brooklynbridge]

memberoflist(X)

memberoflist(X, [X|_]).
memberoflist(X, [_|T]) :- (memberoflist(X, T)).

Query:

memberoflist(X, [1,2,3])

Output:

1 ;
2 ;
3 ;
false.

Query:

X = [1,Y,3], memberoflist(4, X)

Output:

X = [1,4,3],
Y = 4 ;
false.

---

Query:

memberoflist(4, X)

The above query will enumerate all possible lists with 4 inside it.

• _610 is the way prolog refers to some place in memory (in this case it probably refers to an empty list)

X = [4, _610] ;
...goes on forever...

Math

X is 1+5.

If you use the equal sign, it will treat 1+5 as atom

?- 1+5 = 2+4

false.

Exercises

length

Takes two parameters:

• The list
• A variable for the length of the list

% alternative:
% len([], Len) :- Len=0
len([], 0)
len((H|T), Len) :- len(Tail, Y), X is 1+Y.

fibonacci

There's a trick here because Prolog's pattern matching is different from Haskell’s. In Prolog, all the matching predicates get called. To make sure that fib(X, Fib) does not get called when we run fib(0,X) or fib(1, X),we have to add a constraint of N > 1.

fib(0,0).
fib(1,1).
fib(N, X) :- N>1,
				Last is N-1, Lastlast is N-2,
				fib(Last, Y),
				fib(Lastlast, Z),
				X is Y+Z.

mystery1

mystery1([X|Y], Z, [X|W]) :- mystery1(Y,Z,W).
mystery1([],X,X).
% mystery1([a,b,c], [green, blue, red], X).

What does mystery1 do?

It appends one list to another list.

You can also use it to find the difference between two lists.

mystery1([a,b,c], X, [a,b,c,d,e,f])

Output: 
[d, e, f]

mystery2

mystery2([],[]).
mystery2([H|T], [H|Ts]) :- mystery2(T, Ts).
mystery2([H|T], Ts) :- mystery2(T, Ts)
% mystery2([a,b,c], X).

What does mystery2 do?

It returns the all subsets of a list (Power Set).

#school/f19/proglang-f19