It is a hard complicated python assignment, please if you want to accept it it should be guaranteed that it can be done. Thank you!
Important notes about grading: Programs that cannot be compiled will receive an automatic zero. If you are having trouble getting your assignment to compile, please visit recitation or office hours. The following lists the grade distribution: · Problem 1, Problem 2: 11.42% each · Problem 3, Problem 4: 31.43% each · Problem 5: 14.3% Pseudocode The pseudocode of Problem 3 and 4 is given in the lecture note Control in Prolog. Abstract Syntax Tree To implement the abstract interpreter, we will start with the definition of prolog terms (i.e. abstract syntax tree). OCaml Definition In [ ]: type term = | Constant of string (* Prolog constants, e.g., rickard, ned, robb, a, b, ... *) | Variable of string (* Prolog variables, e.g., X, Y, Z, ... *) | Function of string * term list (* Prolog functions, e.g., append(X, Y, Z), father(rickard, ned), ancestor(Z, Y), cons (H, T) abbreviated as [H|T] in SWI-Prolog, ... The first component of Function is the name of the function, the second component of Function is its parameters defined as a term list.*) A Prolog program consists of clauses and goals. A clause can be either a fact or a rule. A Prolog rule is in the shape of head :- body. For example, ancestor(X, Y) :- father(X, Z), ancestor(Z, Y). In the above rule (also called a clause), ancestor(X, Y) is the head of the rule, which is a Prolog Function defined in the type term above. The rule's body is a list of terms: father(X, Z) and ancestor(Z, Y). Both are Prolog Functions. A Prolog fact is simply a Function defined in the type term. For example, father(rickard, ned). In the above fact (also as a clause), we say rickard is ned's father. A Prolog goal (also called a query) is a list of Prolog Functions, which is typed as a list of terms, e.g., ?- ancestor(rickard, robb), ancestor(X, robb). In the above goal, we are interested in two queries: ancestor(rickard, robb) and ancestor(X, robb). In [ ]: type head = term (* The head of a rule is a Prolog Function *) type body = term list (* The body of a rule is a list of Prolog Functions *) type clause = Fact of head | Rule of head * body (* A rule is in the shape head :- body *) type program = clause list (* A program consists of a list of clauses in which we have either rules or facts. *) type goal = term list (* A goal is a query that consists of a few functions *) The following stringification functions should help you debug the interpreter. In [ ]: let rec string_of_f_list f tl = let _, s = List.fold_left (fun (first, s) t -> let prefix = if first then "" else s ^ ", " in false, prefix ^ (f t)) (true,"") tl in s (* This function converts a Prolog term (e.g. a constant, variable or function) to a string *) let rec string_of_term t = match t with | Constant c -> c | Variable v -> v | Function (f,tl) -> f ^ "(" ^ (string_of_f_list string_of_term tl) ^ ")" (* This function converts a list of Prolog terms, separated by commas, to a string *) let string_of_term_list fl = string_of_f_list string_of_term fl (* This function converts a Prolog goal (query) to a string *) let string_of_goal g = "?- " ^ (string_of_term_list g) (* This function converts a Prolog clause (e.g. a rule or a fact) to a string *) let string_of_clause c = match c with | Fact f -> string_of_term f ^ "." | Rule (h,b) -> string_of_term h ^ " :- " ^ (string_of_term_list b) ^ "." (* This function converts a Prolog program (a list of clauses), separated by \n, to a string *) let string_of_program p = let rec loop p acc = match p with | [] -> acc | [c] -> acc ^ (string_of_clause c) | c::t -> loop t (acc ^ (string_of_clause c) ^ "\n") in loop p "" Below are more helper functions for you to easily construct a Prolog program using the defined data types: In [ ]: let var v = Variable v (* helper function to construct a Prolog Variable *) let const c = Constant c (* helper function to construct a Prolog Constant *) let func f l = Function (f,l) (* helper function to construct a Prolog Function *) let fact f = Fact f (* helper function to construct a Prolog Fact *) let rule h b = Rule (h,b) (* helper function to construct a Prolog Rule *) Python Definition The idea is similar to the OCaml definition above. Prolog abstract syntax tree is defined in src/prolog_structures.py. Also see the comment below. Note that in the python implementation, a Rule class is used to construct both a rule and a fact. If the underlying instance is a fact, the body of the rule RuleBody owns an empty term list. In [ ]: (* Every clause in a prolog program is encoded as a rule A fact is a rule with empty body *) class Rule: (* head is a function *) (* body is a *list* of functions (see RuleBody) *) def __init__(self, head, body): assert isinstance(body, RuleBody) self.head = head self.body = body (* Rule body is a list of functions (terms). *) class RuleBody: def __init__(self, terms): assert isinstance(terms, list) self.terms = terms (* The super-class for all Prolog terms *) class Term: pass (* A function is, for example, father(rickard, ned). *) class Function(Term): def __init__(self, relation, terms): self.relation = relation (* function name, e.g. father *) self.terms = terms (* funcion parameters, e.g. rickard, ned *) (* Prolog Variables, e.g. X, Y, ... *) class Variable(Term): def __init__(self, value): self.value = value class Constant(Term): def __init__(self, value): self.value = value (* Prolog Atoms, e.g. rickard, ned, ... *) class Atom(Constant): def __init__(self, value): super().__init__(value) (* Prolog Numbers, e.g. 1, 2, ... *) class Number(Constant): def __init__(self, value): super().__init__(int(value)) Occurs_check In this example, we implement the function: occurs_check : term -> term -> bool occurs_check v t returns true if the Prolog Variable v occurs in t. Please see the lecture note Control in Prolog to revisit the concept of occurs-check. OCaml Implementation In [ ]: let rec occurs_check v t = (* BEGIN SOLUTION *) match t with | Variable _ -> t = v | Constant _ -> false | Function (_,l) -> List.fold_left (fun acc t' -> acc || occurs_check v t') false l (* END SOLUTION *) Note that in this implementation, when t is a variable, we don't need to use pattern matching to deconstruct v (type term) to compare the string value of v with that of t. We can compare two Variables via structural equality, e.g. Variable "s" = Variable "s". Therefore, if t is a variable, it suffices to use t = v for equality checking (one should use = rather than == for structural equality). Examples and test-cases. In [ ]: assert (occurs_check (var "X") (var "X")) assert (not (occurs_check (var "X") (var "Y"))) assert (occurs_check (var "X") (func "f" [var "X"])) assert (occurs_check (var "E") (func "cons" [const "a"; const "b"; var "E"])) The last test-case above was taken from the example we used to illustrate the occurs-check problem in the lecture note Control in Prolog. ?- append([], E, [a,b | E]). Here the occurs_check function asks whether the Variable E appears on the Function term func "cons" [const "a"; const "b"; var "E"]. The return value should be true. Python Implementation The idea is similar to the above OCaml implementation. In [ ]: def occurs_check (v : Variable, t : Term) -> bool: if isinstance(t, Variable): (* If t is a Variable instance *) return v == t elif isinstance(t, Function): (* If t is a Function instance *) for t in t.terms: if occurs_check(v, t): (* If v occurs in a function paramter *) return True return False return False (* Otherwise t is an instance of Atom or Number *) Problem 1 Implement the following functions which return the variables contained in a term or a clause. OCaml Implementation variables_of_term : term -> VarSet.t variables_of_clause : clause -> VarSet.t The result must be saved in a data structure of type VarSet that is instantiated from OCaml Set module. The type of each element (a Prolog Variable) in the set is term as defined above (VarSet.t = term). You may want to use VarSet.singleton t to return a singletion set containing only one element t, use VarSet.empty to construct an empty variable set, and use VarSet.union t1 t2 to merge two variable sets t1 and t2. In [ ]: module VarSet = Set.Make(struct type t = term let compare = Pervasives.compare end) (* API Docs for Set : https://caml.inria.fr/pub/docs/manual-ocaml/libref/Set.S.html *) let rec variables_of_term t = (* YOUR CODE HERE *) let variables_of_clause c = (* YOUR CODE HERE *) Examples and test-cases: In [ ]: (* The variables in a function f (X, Y, a) is [X; Y] *) assert (VarSet.equal (variables_of_term (func "f" [var "X"; var "Y"; const "a"])) (VarSet.of_list [var "X"; var "Y"])) (* The variables in a Prolog fact p (X, Y, a) is [X; Y] *) assert (VarSet.equal (variables_of_clause (fact (func "p" [var "X"; var "Y"; const "a"]))) (VarSet.of_list [var "X"; var "Y"])) (* The variables in a Prolog rule p (X, Y, a) :- q (a, b, a) is [X; Y] *) assert (VarSet.equal (variables_of_clause (rule (func "p" [var "X"; var "Y"; const "a"]) [func "q" [const "a"; const "b"; const "a"]])) (VarSet.of_list [var "X"; var "Y"])) Python Implementation The idea is similar to the OCaml implementation. def variables_of_term (t : Term) -> set : def variables_of_clause (c : Rule) -> set : The function should return the Variables contained in a term or a rule using Python set. The result must be saved in a Python set. The type of each element (a Prolog Variable) in the set is Variable. You may want to merge two python sets s1 and s2 by s1.union(s2), create a singleton set containing only one element t by set([t]), and construct an empty set by set(). Note that the union function returns a new set with elements from s_1 and s_2 and s_1 itself is unchanged. In [ ]: def variables_of_term (t : Term) -> set : (* YOUR CODE HERE *) def variables_of_clause (c : Rule) -> set : (* YOUR CODE HERE *) Problem 2 The goal of this problem is to implement substitution.