Project 5: Prolog
CMSC 330, Fall 2017 (Due December 4th, 2017)
Ground Rules
This is NOT a pair project. You must work on this project alone.
- You can use any built-in arithmetic or list predicate, in addition to any predicate defined
library(lists)
. Do not use additional libraries or syntactic extensions (unless given permission by an instructor, which is unlikely). - If asked to generate multiple solutions, the order and uniqueness of solutions is irrelevant unless specified otherwise. If a predicate should succeed deterministically, you are not required to prune redundant choice points provided that no distinct solutions are generated on backtracking. Your code is tested by inspecting sets of solutions using extra-logical predicates.
Welcome to Prolog! This project contains five sections: arithmetic, lists, binary trees, operational semantics and finite automata. Each section begins with familiar exercises, mostly drawn from previous projects, so that solutions can be adapted and compared between OCaml and Prolog. The exercises in each section are arranged in roughly increasing difficulty. Tests are independent between sections, so you can skip between them without worrying about dependencies.
This project is organized into five modules , which are collections of predicated satisfying an interface. The module/2
directive occurring at the beginning of each source file declares the module name and interface. For example, the file arith.pl
defines a module named arith
that exports the predicates gcd/3
, factor/2
, prime/1
and partition/1
. The use_module/1 directive imports all predicates defined by a module, making them available in the current module or toplevel session.
Project Files
To begin this project, you will need to commit any uncommitted changes to your local branch and pull updates from the git repository. Click here for directions on working with the Git repository. The following are the relevant files:
- Prolog files (you should edit)
- arith.pl : This file is the place you will implement part 1, the arithmetic module.
- list.pl : This file is the place you will implement part 2, the list module.
- opsem.pl : This file is the place you will implement part 3, the operational semantics module.
- nfa.pl : This file is the place you will implement part 4, the finite automata module.
- Provided Prolog files (no need to edit, changes will be overwritten!)
- lexer.pl : This file implements the SmallC lexer.
- parser.pl : This file implements the SmallC parser.
- public.pl : The public test driver file.
- Submission Scripts and Other Files
- submit.rb : Execute this script to submit your project to the submit server.
- submit.jar and .submit : Dont worry about these files, but make sure you have them.
- pack_submission.sh : Execute this script to zip your project for web submission.
Tests and Running
The public tests can be run by executing swipl -f public.pl -t run_tests
.
You can test any module from the Prolog toplevel. Run swipl
and load any of your modules. For example, to load the arithmetic module execute [arith].
. Assuming no errors, you will now be able to use any of your predicates.
General Advice
- Many library predicates, including
member/2
,append/3
andlength/2
can be run backwards or used as generators. The predicatebetween/3
generates all integers in a possibly infinite range when its third argument is uninstantiated (i.e., a variable). Understanding the behavior of these predicates will be immensely helpful in completing this project. - The predicates
findall/3
,bagof/3
andsetof/3
reason about all solutions to a goal. We suggest reading the documentation forsetof/3
, because it behaves differently thanfindall/3
when the goal has no solutions or contains free variables. Useforall/2
to determine whether a goal succeeds for every instantiation of its free variables.
Part 1: Arithmetic (arith.pl)
In this section, you will implement four predicates: factor/2
, gcd/3
, prime/1
and partition/2
. You have encountered factor/2
under the name mult_of_y
in Project 2(a). Here, you must not only determine whether one number is a factor of another, but generate all factors of a number. You will find the predicate between/3
useful for this purpose. The predicate prime/1
has a natural but inefficient implementation in terms of factor/2
. Although you arent tested for efficiency, we challenge you to provide efficient implementations of factor/2
and prime/1
. If you have trouble implementing partition/2
, consider returning after completing the list exercises.
- Predicate:
factor(N,F)
- Description:
F
is a factorN
. - Assumptions:
N
andF
are positive integers. - Notes:
F
is a factor ofN
ifN = K * F
for some integerK
. - Usage: If
N
andF
are positive integers, thenfactor(N,F)
succeeds with all solutions forF
.
?- factor(68,17).true.?- factor(17,68).false.?- setof(F,factor(68,F),Factors).Factors = [1, 2, 4, 17, 34, 68].
- Predicate:
gcd(A,B,D)
- Description:
D
is the greatest common divisor ofA
andB
. - Assumptions:
A
andB
are nonnegative integers. - Notes: Use the Euclidean algorithm to compute
gcd(A,B,D)
. - Usage: If
A
andB
are nonnegative integers, thengcd(A,B,D)
succeeds with one solution forD
.
?- gcd(8,0,D).D = 8.?- gcd(8,9,D).D = 1.?- gcd(12,15,D).D = 3.
- Predicate:
prime(N)
- Description:
N
is prime. - Assumptions:
N
is a nonnegative integer. - Notes:
N
is prime iff its only positive factors are1
andN
. - Usage: If
N
is a nonnegative integer, thenprime(N)
succeeds iffN
is prime.
?- prime(0).false.?- prime(7).true.?- setof(P,(between(0,10,P),prime(P)),Primes).Primes = [2, 3, 5, 7]
- Predicate:
partition(N,Part)
- Description:
Part
is a partition ofN
into distinct primes. - Assumptions:
N
is a positive integer andPart
an ordered list of distinct positive integers. - Notes: A partition of a positive integer
N
is a setS
of positive integers such thatS
sums toN
. - Usage: If
N
is a positive integer, thenpartition(N,Part)
succeeds with all solutions forPart
. - Hints: Compare your solution against OEIS A000586 for a quick sanity check.
?- partition(4,Part).false.?- partition(8,Part).Part = [3, 5].?- setof(Part,partition(7,Part),Parts).Parts = [[2, 5], [7]].
Part 2: Lists (list.pl)
In this section, you will implement five predicates: product/2
, index/3
, flat/2
, nodups/2
and powerset/2
. We require that index/3
work in a variety of modes and flat/2
on heterogeneous lists.
- Predicate:
product(List,Prod)
- Description:
Prod
is the product of every number inList
. - Assumptions: The product of the empty list is
1
. - Usage: If
List
is a list of integers, thenProduct(List,Prod)
succeeds with a unique solution forProd
.
?- product([],Prod).Prod = 1.?- product([1,2,3],Prod).Prod = 6.?- product([5,5,4],Prod).Prod =100.
- Predicate:
index(List,Elem,Index)
- Description:
Index
is the index ofElem
in List. - Assumptions:
Index
is a nonnegative integer. - Notes: In this case, order and uniqueness of solutions matters
- Usage: If
List
is a list, thenindex(List,Elem,Index)
succeeds with all solutions forElem
andIndex
. - Hints: Define a tail-recursive helper predicate.
?- index([],Elem,Index).false.?- findall(Index,index([1,2,1,2],2,Index),Indices).Indices = [1, 3].?- findall((Elem,Index),index([1,2,1,2],Elem,Index),Pairs).Pairs = [(1, 0),(2, 1),(1, 2),(2, 3)].
<! MWH: Explain the use X-Y here? Not something we normally cover, and it comes up again below. > <! Changed to (X,Y) > <! MWH: General question, what if List is not a list? We dont say how errors are handled. Perhaps emphasize we wont test that? >
- Predicate:
flat(NestedList,FlatList)
- Description:
FlatList
is the result of removing one level of nesting fromNestedList
. - Usage: If
NestedList
is a list, thenflat(NestedList,FlatList)
succeeds with one solution forFlatList
.
?- flat([],FlatList).FlatList = [].?- flat([1,[3]],FlatList).FlatList = [1, 3].?- flat([1,[[2],3],[4,[]]],FlatList).FlatList = [1, [2], 3, 4, []].
- Predicate:
nodups(List,Unique)
- Description:
Unique
isList
with all duplicates removed. - Notes : The order of elements in
Unique
is the order of elements inList
. - Usage: If
List
is a list, thennodups(List,Unique)
succeeds with one solution forUnique
.
?- nodups([],Unique).Unique = [].?- nodups([2,3,2],Unique).Unique = [2, 3].?- nodups([3,2,3],Unique).Unique =[3, 2].
- Predicate:
powerset(Set,Sub)
- Description:
Sub
is an element of the powerset ofSet
- Assumptions:
Set
andPow
are ordered lists without duplicates. - Notes: The powerset of a set
S
is the set of all subsets ofS
. - Usage: If
Set
is an ordered list without duplicates, thenpowerset(Set,Sub)
succeeds with all solutions forSub
- Hints: Give a recursive definition of the powerset operation. There is one binary choice in the recursive case.
?- powerset([],Sub).Sub = [].?- setof(Sub,powerset([1],Sub),Subs).Subs = [[], [1]].?- setof(Sub,powerset([1,2],Sub),Subs).Subs = [[], [1], [1, 2], [2]].
Part 3: Operational Semantics (opsem.pl)
In this section, you will implement an interpreter for a fragment of SmallC. The key observation is that the semantics for SmallC are given by natural deduction rules, which are identical in structure to Prolog clauses. If this isnt obvious, consider reviewing the slides on operational semantics and Prolog before beginning this section. Once you understand the relationship between the operational semantics and Prolog clauses, implementing the interpreter should be an exercise in translation.
We have provided a parser, type checker and driver to make testing your interpreter easier. The parser and type checker perform no error reporting. Thus, you can assume that all expressions and statements are well-typed with respect to the environment when implementing eval_expr/3
and eval_stmt/3
. You are only required to interpret the fragment of SmallC for which type checking has been implementing. For reference, eval_expr/3
must support
- integers, represented
int(N)
whereN
is an integer; - booleans, represented
bool(B)
whereB
istrue
orfalse
; - variables, represented
id(X)
whereX
is an atom; - negation, represented
not(E)
whereE
is an expression; - equality, represented
eq(E1,E2)
whereE1
andE2
are expressions; - inequality, represented
lt(E1,E2)
whereE1
andE2
are expressions; - disjunction, represented
or(E1,E2)
whereE1
andE2
are expressions; - addition, represented
plus(E1,E2)
whereE1
andE2
are expressions; and - multiplication, represented
mult(E1,E2)
whereE1
andE2
are expressions.
Similarly, eval_stmt/3
must support
- the empty statement, represented
skip
; - sequencing, represented
seq(S1,S2)
whereS1
andS2
are statements; - variable declaration, represented
decl(T,X)
whereT
is one ofint
orbool
andX
is an atom; - variable assignment, represented
assign(X,E)
whereX
is an atom andE
an expression; - while loops, represented
while(G,B)
whereG
is an expression andB
a statement; and - conditionals, represented
cond(G,T,E)
whereG
is an expression andT
andE
statements.
Environments are represented as association lists. The elements of an association list are pairs of the form K-V
where K
is a key and V
the value. By convention, we say that K
is bound to V
in an environment Env
if V
is the leftmost binding for K
in Env
. The examples below assume that assignment doesnt overwrite variable bindings. Thus, your implementation may not match the examples exactly. The predicate lookup/3
defined in opsem.pl
returns the leftmost binding for a key in an association list.
The predicates interpret_expr/6
and interpret_stmt/4
can be used to test your implementation. You are referred to the documentation in opsem.pl
for their full specification. To use interpret_expr/5
and interpret_stmt/4
, you must provide a string representation of an expression, a typing environment, and initial values for all free variables in the expression or statement. The string must be syntactically correct, the expression or statement well-typed in the typing environment, and the initial values consistent with the typing environment. As mentioned above, your interpreter operations under these assumptions; no error checking is required.
- Predicate:
eval_expr(Env,Expr,Value)
- Description:
Expr
evaluates to valueValue
in environmentEnv
. - Usage: If
Env
is an environment andExpr
a well-typed expression, theneval_expr(Env,Expr,Value)
succeeds with one solution forValue
.
?- interpret_expr("x + 1",[x-int],[x-2],Type,Value).Type = int,Value = 3.?- interpret_expr("!p || p",[p-bool],[p-false],Type,Value).Type = bool,Value = true.?- interpret_expr("x + 1 < 3 == p",[x-int,p-bool],[x-1,p-false],Type,Value).Type = bool,Value = false.
- Predicate:
eval_stmt(Env,Stmt,NewEnv)
- Description:
NewEnv
is the result of evaluatingStmt
in environmentEnv
- Usage: If
Env
is an environment andStmt
a well-typed statement, theneval_stmt(Env,Stmt,NewEnv)
succeeds with one solution forNewEnv
.
?- interpret_stmt("int x; x = 1;",[],[],Env).Env = [x-1, x-0].?- interpret_stmt("int x; bool p; if (x < 3) {x = x + 1; p = !p;}",[],[],Env).Env = [p-true, x-1, p-false, x-0]?- interpret_stmt("int f; f = 1; while (0 < n) {f = f * n; n = n + (-1);}",[n-int],[n-4],Env).Env = [n-0, f-24, n-1, f-24, n-2, f-12, n-3, f-4, f-1, f-0, n-4].
Part 4: Finite Automata (nfa.pl)
In this section, you will enumerate the strings of a regular language given an NFA for that language. You should find the implementation more natural in Prolog than OCaml, because Prolog executes queries by performing depth-first search with backtracking. Thus, explicit data structures required to simulate nondeterminism in OCaml are largely implicit in Prolog. The only complication arises when dealing with epsilon-closures, because cycles in the transition graph may cause nontermination.
We adhere to the mathematical definition and represent an NFA M
as a quintuple nfa(Q,A,D,S,F)
where Q
is a list of states, A
the alphabet, D
the transition relation, S
the start state, and F
the final states of M
. The transition relation is a list of triples (I,A,J)
having the obvious meaning, The atom epsilon
represents the empty string. You can assume that all NFAs
are well-formed and no list contains duplicate entries. The following examples assume that M
is bound to the following NFA, which accepts the set of all strings over [a,b]
ending in a
.
nfa([0,1,2,3],[a,b],[(0,a,1),(0,b,1),(0,epsilon,1),(1,epsilon,0),(1,b,3),(1,a,2)],0,[2]),
Note that redundant choice points are acceptable, provided that no distinct solutions are obtained on backtracking. In particular, if there are multiple paths through an NFA on input U
to a final state, then accept/2
can report success for each path. Similarly, if there are multiple paths from a state I
to a final state, then productive/2
can succeed with redundant solutions for I
. You can avoid duplicate solutions using cut or breadth-first search.
- Predicate:
move(M,From,A,To)
- Description:
M
can transition to stateTo
from stateFrom
on symbolA
. - Usage: If
M
is an NFA, thenmove(M,From,A,To)
succeeds with all solutions forFrom
,A
andTo
.
?- move(M,1,a,2).true.?- move(M,1,b,2).false.?- setof((I,A,J),move(M,I,A,J),Moves).Moves = [(0, a, 1),(0, b, 1),(1, a, 2),(1, b, 3)].
- Predicate:
e_closure(M,From,To)
- Description:
To
is an element of the epsilon-closure ofFrom
. - Usage: If
M
is anNFA
, thene_closure(M,From,To)
succeeds with all solutions forFrom
andTo
.
?- e_closure(M,0,2).false.?- e_closure(M,0,1).true.?- setof(I-J,e_closure(M,I,J),Closure).Closure = [0-0, 0-1, 1-0, 1-1, 2-2, 3-3].
- Predicate:
accept(M,String)
- Description:
String
is accepted byM
. - Usage: If
M
is an NFA andString
a string, thenaccept(M,String)
succeeds ifM
acceptsString
.
?- accept(M,[]).false.?- accept(M,[a,a]).true.?- accept(M,[a,b]).false.
- Predicate:
productive(M,State)
- Description: There is a final state reachable from
State
inM
. - Usage: If
M
is an NFA, thenproductive(M,State)
succeeds with all solutions forState
.
?- productive(M,3).false.?- productive(M,0).true.?- nfa:nfa_suffix(M), setof(I,productive(M,I),Productive).Productive = [0, 1, 2].
- Predicate:
enumerate(M,Len,String)
- Description:
String
is a string of lengthLen
accepted by the NFA. - Usage: If
M
is an NFA, thenenumerate(M,Len,String)
succeeds with all solutions forLen
andString
.
?- enumerate(M,0,U).false.?- setof(U,enumerate(M,2,U),Strings).Strings = [[a, a], [b, a]].?- setof(U,enumerate(M,3,U),Strings).Strings = [[a, a, a], [a, b, a], [b, a, a], [b, b, a]].
Project Submission and Grading
Be sure to follow the project description exactly! Your solution will be graded automatically, so any deviation from the specification will result in lost points.
You can submit your project in two ways:
- Submit your files directly to the submit serveras a zip file by clicking on the submit link in the column web submission. Then, use the submit dialog to submit your zip file containing all of your source files directly. Select your file using the Browse button, then press the Submit project! button. You will need to put it in a zip file since there are several component files. We provide a script
pack_submission.sh
which you can run to make a zip file containing all of the necessary files. - Submit directly by executing a the submission script on a computer with Java and network access. Included in this project are the submission scripts and related files listed under Project Files . These files should be in the directory containing your project. From there you can either execute submit.rb or run the command
java -jar submit.jar
directly (this is all submit.rb does).
No matter how you choose to submit your project, make sure that your submission is received by checking the submit server after submitting.
Academic Integrity
Please carefully read the academic honesty section of the course syllabus. Any evidence of impermissible cooperation on projects, use of disallowed materials or resources, or unauthorized use of computer accounts, will be submitted to the Student Honor Council, which could result in an XF for the course, or suspension or expulsion from the University. Be sure you understand what you are and what you are not permitted to do in regards to academic integrity when it comes to project assignments. These policies apply to all students, and the Student Honor Council does not consider lack of knowledge of the policies to be a defense for violating them. Full information is found in the course syllabus, which you should review before starting.
Reviews
There are no reviews yet.