Csc 4330/6330, Programming Language Concepts (Spring 2022)

Homework 2 (Due: 10 February (Thursday))

1. Free Variables in First-Order Logic: A well-formed formula (wff) in first-order logic is defined as follows:
   • An atomic formula, p(a1,...,an), is a wff, where p is a predicate symbol (ID token) and a1,...,an (n > 0) are arguments that can be numbers (NUMBER token), or strings enclosed within single quotation marks (STRING token), or variables (ID token). We shall assume that the ID token begins with a lower-case letter and is followed zero or more letters or digits. Even though the variables are made up of lower and upper-case letters, these should be considered case-insensitive. For example, value1, vALUE1, vAlue1, etc all should be treated as the same variable. For simplicity, we may assume that the STRING tokens are made up of letters and digits.
   • If F1 and F2 are wffs, then F1 and F2, F1 or F2, and not F1 are wffs. (Note that we do not enforce parentheses!)
   • If F is a wff and x1,...,xn are variables (n > 0), then (exists x1,...,xn)(F), (forall x1,...,xn)(F), and (F) are wffs. (Note that here we enforce parentheses!)
   Since we do not enforce parentheses while using "and", "or", and "not", we will assume that "and" and "or" have lower precedence compared to "not". So, in a formula such as:

   A and B or not C and D
   

   the "not" will be applied to C and then the "and"s and "or"s will be applied with left associativity. Some examples of wffs are:

   employee('John','B','Smith',t,u,v,w,x,y,z)
   
   projects(h,20,'Stafford',k)
   
   (exists t,w,x,y,z)( employee('John','B','Smith',t,u,v,w,x,y,z) )
   
   (exists r,t,u,v,w,x,y,z)( employee(q,r,s,t,u,v,w,x,y,z) and not ((exists m,n,o,p)(dependent(t,m,n,o,p)) ) )
   

   Recall the definition of "free variables" in wffs from your Discrete Math (CSC 2510/MATH 2420) class.

   Write a CFG for wffs as defined above. Make sure to enforce precedence rules and left associativity on the logical operators. Then, using PLY define the tokens in WFFLexer.py and the parser specfication in WFFParser.py. Using p[0] assignment statements construct an expression tree data structure similar to homework 1. Then, in the main program write a function, free_variables(tree), that computes the list of free variables in the expression denoted by tree. A sample run is shown below:

   Mac-mini:wff raj$  python3 WFF.py 
   WFF: p(x,20,'aa');
   OPEN WFF with Free Variables:  ['X']
   WFF: (exists x,y)(p(x,u) and not q(y,v));
   OPEN WFF with Free Variables:  ['U', 'V']
   WFF: (exists x,y)(p(x,y));
   CLOSED WFF
   WFF: employee('John','B','Smith',t,u,v,w,x,y,z);
   OPEN WFF with Free Variables:  ['T', 'U', 'V', 'W', 'X', 'Y', 'Z']
   WFF: projects(h,20,'Stafford',k);
   OPEN WFF with Free Variables:  ['H', 'K']
   WFF: (exists t,w,x,y,z)( employee('John','B','Smith',t,u,v,w,x,y,z) );
   OPEN WFF with Free Variables:  ['U', 'V']
   WFF: (exists r,t,u,v,w,x,y,z)( employee(q,r,s,t,u,v,w,x,y,z) and not ((exists m,n,o,p)(dependent(t,m,n,o,p)) ) );
   OPEN WFF with Free Variables:  ['Q', 'S']
   WFF: exit;
   

   Note: A wff is OPEN if it contains a non-empty set of free variables and CLOSED otherwise.

2. Safe Datalog Rule: A Datalog rule is of the form:

   p :- q1, ..., qn.
   

   where n>0 and p is a positive atomic formula and q1, ..., and qn are positive or negative atomic formulas. A positive atomic formula is of the form:

   r(x1, ..., xm)
   

   and a negative atomic formulas of the form:

   not r(x1, ..., xm)
   

   where m>0 and r is a relation name and x1 , ..., xm are either numbers or variables. Relation names and variables are made up of alphabetic letters or digits and start with a lower-case alphabetic letter. Even though the variables are made up of lower and upper-case letters, these should be considered case-insensitive. For example, cno, CNO, cNO, etc all should be treated as the same variable.

   Some examples of Datalog rules are given below:

   ancestor(x1, y1) :- parent(x1, y1).
   teaches(tno,cno) :- faculty(tno), course(cno), assigned(tno,cno).
   p(x,y) :- q(2,x), r(u,45,z), s(a,b,22).
   p(x,y,z) :- q(x), not r(y,20), s(x,z).
   

   A Datalog rule is considered “Safe” if all variables that appear to the left of :- also appear to its right in positive atoms. For example in rule 2 above, the variables that appear to the left of :- are tno and cno. Both these variables appear to the right of :- in positive atomic formulas as well. So, this rule is “Safe”. However, rule 3 above is not “Safe” because the variable y appearing to the left of :- does not appear to the right of :-. Similarly, rule 4 is also not "Safe" because even though x, y, and z appear on the right hand side, unfortunately y appears only in a negative atomic formula, thereby rendering the rule "Unsafe".

   Using PLY, implement an Attribute Grammar that checks for "Safe" Datalog rules. In the first rule, return a Boolean value indicating whether the rule is safe (True) or unsafe (False). The main program, DLOG.py, can be used as a driver program. Here is a sample run:

   Mac-mini:dlog raj$ python3 DLOG.py
   Enter Datalog rule: ancestor(x1, y1) :- parent(x1, y1).
   SAFE Datalog Rule
   Enter Datalog rule: teaches(tno,cno) :- faculty(tno), course(cno), assigned(tno,cno).
   SAFE Datalog Rule
   Enter Datalog rule: p(x,y) :- q(2,x), r(u,45,z), s(a,b,22).
   UNSAFE Datalog Rule
   Enter Datalog rule: p(x,y,z) :- q(x), not r(y,20), s(x,z).
   UNSAFE Datalog Rule
   Enter Datalog rule: exit
   Mac-mini:dlog raj$