Project 5: Prolog

CMSC 330, Fall 2017 (Due December 4th, 2017)

Ground Rules

This is NOTa pair project. You must work on this project alone.

1. 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).
2. 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.

Introduction

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.pldefines a module named ariththat exports the predicates gcd/3, factor/2, prime/1and partition/1. The use_module/1directive 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 : Don’t 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 swipland 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

1. Many library predicates, including member/2 , append/3 and length/2 can be “run backwards” or used as generators. The predicate between/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.
2. The predicates findall/3 , bagof/3 and setof/3 reason about all solutions to a goal. We suggest reading the documentation for setof/3 , because it behaves differently than findall/3 when the goal has no solutions or contains free variables. Use forall/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/1and partition/2. You have encountered factor/2under 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/3useful for this purpose. The predicate prime/1has a natural but inefficient implementation in terms of factor/2. Although you aren’t tested for efficiency, we challenge you to provide efficient implementations of factor/2and prime/1. If you have trouble implementing partition/2, consider returning after completing the list exercises.

• Predicate: factor(N,F)
• Description: F is a factor N .
• Assumptions: N and F are positive integers.
• Notes: F is a factor of N if N = K * F for some integer K .
• Usage: If N and F are positive integers, then factor(N,F) succeeds with all solutions for F .

?- 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 of A and B .
• Assumptions: A and B are nonnegative integers.
• Notes: Use the Euclidean algorithm to compute gcd(A,B,D) .
• Usage: If A and B are nonnegative integers, then gcd(A,B,D) succeeds with one solution for D .

?- 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 are 1 and N .
• Usage: If N is a nonnegative integer, then prime(N) succeeds iff N 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 of N into distinct primes.
• Assumptions: N is a positive integer and Part an ordered list of distinct positive integers.
• Notes: A partition of a positive integer N is a set S of positive integers such that S sums to N .
• Usage: If N is a positive integer, then partition(N,Part) succeeds with all solutions for Part .
• 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/2and powerset/2. We require that index/3work in a variety of modes and flat/2on heterogeneous lists.

• Predicate: product(List,Prod)
• Description: Prod is the product of every number in List .
• Assumptions: The product of the empty list is 1 .
• Usage: If List is a list of integers, then Product(List,Prod) succeeds with a unique solution for Prod .

?- 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 of Elem in List.
• Assumptions: Index is a nonnegative integer.
• Notes: In this case, order and uniqueness of solutions matters
• Usage: If List is a list, then index(List,Elem,Index) succeeds with all solutions for Elem and Index .
• 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)].

• Predicate: flat(NestedList,FlatList)
• Description: FlatList is the result of removing one level of nesting from NestedList .
• Usage: If NestedList is a list, then flat(NestedList,FlatList) succeeds with one solution for FlatList .

?- 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 is List with all duplicates removed.
• Notes : The order of elements in Unique is the order of elements in List .
• Usage: If List is a list, then nodups(List,Unique) succeeds with one solution for Unique .

?- 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 of Set
• Assumptions: Set and Pow are ordered lists without duplicates.
• Notes: The powerset of a set S is the set of all subsets of S .
• Usage: If Set is an ordered list without duplicates, then powerset(Set,Sub) succeeds with all solutions for Sub
• 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 isn’t obvious, consider reviewing the slides on operational semanticsand Prologbefore 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/3and eval_stmt/3. You are only required to interpret the fragment of SmallC for which type checking has been implementing. For reference, eval_expr/3must support

• integers, represented int(N) where N is an integer;
• booleans, represented bool(B) where B is true or false ;
• variables, represented id(X) where X is an atom;
• negation, represented not(E) where E is an expression;
• equality, represented eq(E1,E2) where E1 and E2 are expressions;
• inequality, represented lt(E1,E2) where E1 and E2 are expressions;
• disjunction, represented or(E1,E2) where E1 and E2 are expressions;
• addition, represented plus(E1,E2) where E1 and E2 are expressions; and
• multiplication, represented mult(E1,E2) where E1 and E2 are expressions.

Similarly, eval_stmt/3must support

• the empty statement, represented skip ;
• sequencing, represented seq(S1,S2) where S1 and S2 are statements;
• variable declaration, represented decl(T,X) where T is one of int or bool and X is an atom;
• variable assignment, represented assign(X,E) where X is an atom and E an expression;
• while loops, represented while(G,B) where G is an expression and B a statement; and
• conditionals, represented cond(G,T,E) where G is an expression and T and E statements.

Environments are represented as association lists. The elements of an association list are pairs of the form K-Vwhere Kis a key and Vthe value. By convention, we say that Kis bound to Vin an environment Envif Vis the leftmost binding for Kin Env. The examples below assume that assignment doesn’t overwrite variable bindings. Thus, your implementation may not match the examples exactly. The predicate lookup/3defined in opsem.plreturns the leftmost binding for a key in an association list.

The predicates interpret_expr/6and interpret_stmt/4can be used to test your implementation. You are referred to the documentation in opsem.plfor their full specification. To use interpret_expr/5and 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 value Value in environment Env .
• Usage: If Env is an environment and Expr a well-typed expression, then eval_expr(Env,Expr,Value) succeeds with one solution for Value .

?- 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 evaluating Stmt in environment Env
• Usage: If Env is an environment and Stmt a well-typed statement, then eval_stmt(Env,Stmt,NewEnv) succeeds with one solution for NewEnv .

?- 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 Mas a quintuple nfa(Q,A,D,S,F)where Qis a list of states, Athe alphabet, Dthe transition relation, Sthe start state, and Fthe final states of M. The transition relation is a list of triples (I,A,J)having the obvious meaning, The atom epsilonrepresents the empty string. You can assume that all NFAsare well-formed and no list contains duplicate entries. The following examples assume that Mis 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 Uto a final state, then accept/2can report success for each path. Similarly, if there are multiple paths from a state Ito a final state, then productive/2can 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 state To from state From on symbol A .
• Usage: If M is an NFA, then move(M,From,A,To) succeeds with all solutions for From , A and To .

?- 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 of From .
• Usage: If M is an NFA , then e_closure(M,From,To) succeeds with all solutions for From and To .

?- 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 by M .
• Usage: If M is an NFA and String a string, then accept(M,String) succeeds if M accepts String .

?- 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 in M .
• Usage: If M is an NFA, then productive(M,State) succeeds with all solutions for State .

?- 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 length Len accepted by the NFA.
• Usage: If M is an NFA, then enumerate(M,Len,String) succeeds with all solutions for Len and String .

?- 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]].