CSE307
Spring 2009
Stony Brook 		Principles of Programming Languages
Annie Liu
Assignment 6 		Handout A6
Apr. 16, 2009
Due Apr. 30

Logic Programming --- Adding Power

This assignment has two goals: (1) practicing programming with logic, and (2) doing powerful analysis for the EHR policy.

Among the variety of tasks we have written programs for, the most complex one is the name analysis in Assignment 3. To do more powerful analysis, logic programming comes in handy. In particular, because the EHR policy is based on the notion of roles, we will analyze dependencies involving activation and deactivation of roles. The analysis is powerful because it handles transitive and even cyclic dependencies.

Doing powerful analysis

The EHR policy contains mostly rules that specify when various roles with 0 or more arguments can be activated and deactivated, by defining predicates canActivate and canDeactivate. For example, consider the first rule in file ra 

  (R1.1.1)
  canActivate(mgr, Register-RA-manager(mgr2)) <-
  hasActivated(mgr, RA-manager()),
  RA-manager-regs(n, mgr2),
  n=0
It specifies that a manager mgr can activate the role Register-RA-manager with argument mgr2 if
  1. mgr has activated the role RA-manager with no arguments,
  2. assertion RA-manager-regs(n, mgr2) holds, and
  3. n=0.
Thus there is an dependency of canActivate(mgr,Register-RA-manager(mgr2)) on hasActivated(mgr,RA-manager()).

Precisely, assertion canActivate(x,R(args)) denotes that entity x can activate his or her role R with arguments args, and assertion canDeactivate(y,x,R(args)) denotes that entity y can deactivate entity x's role R with arguments args.

Predicates hasActivated and isDactivated are used to implement the effects of activation and deactivation. Assertion hasActivated(x,R(args)) holds after canActivate(x,R(args)) holds and the role R(args) is activated. Therefore, there is an implicit dependency of hasActivated(x,R(args)) on canActivate(x,R(args)). Similarly, there is an implicit dependency of isDeactivated(x,R(args)) on canDeactivate(y,x,R(args)).

For simplicity, we will use canA, hasA, canD, and isD to abbreviate canActivate, hasActivated, canDeactivate, and isDeactivated, respectively.

Our analysis will consist of two tasks.

  1. Abstract policy rules to consider only the four predicates above that deal with role activation and deactivation, and consider only the names of roles. For example, the rule above will be abstracted as a dependency of (canA,Register-RA-manager) on (hasA,RA-manager).
  2. Given a pair (action,role), where action is one of canA, hasA, canD, and isD, and role is the name of one of the roles in the policy, find all pairs of actions and roles that the given pair depends on, transitively, following both explicit and implicit dependencies.

For task 1, we may write a method in Python to write out direct dependencies, both explicit and implicit ones, as facts of the form 

  edge(action1, role1, action2, role2).
For example, the dependency in the rule above will be written as 
  edge(canA, rRegister_RA_manager, hasA, rRA_manager).
Recall that constants must use lower-case initials, hence we added a lower-case r in front of all role names. Also, '-' in role names are replaced with '_'.

Note that, to do this task, we only need to consider top-level Atoms and RemoteAtoms in the policy rules, and ignore the locations and issuers in RemoteAtoms. For example, for the following rule in file ra 

  (R3.1.1)
  canActivate(cli, Workgroup-member(org, group, spcty)) <-
  hasActivated(x, NHS-health-org-cert(org, start, end)),
  org@org.hasActivated(x, Register-team-member(cli, group, spcty)),
  Current-time() in [start, end]
we will abstract out the following edges: 
  edge(canA, rWorkgroup_member, hasA, rNHS_health_org_cert).
  edge(canA, rWorkgroup_member, hasA, rRegister_team_member).

For task 2, we may write a program in XSB to compute reachability, as described below.

Programming with logic

For computing reachability, we may define two rules, one for the base case and one for the recursive case. For printing all solutions, another rule is needed. Finally, for efficient query evaluation, we need to declare the use of tabling, a.k.a., memoization. All these will be discussed in the next class.

To show that your program works as expected, show the result of querying all pairs that (canD,rConcealed-by-spine-clinician) depends on transitively.

Extra credit suggestions

Here are some ideas, and do try them, especially (1) and (4), and receive 10% extra credit each. (1) Find all pairs of actions and roles that are in cycles. (2) Print also the name of the rule used for each new pair reached. (3) Think of other interesting and/or useful things to analyze about the EHR policy, and do them. (4) Describe, in your README file, the changes you have to make to your program in assignment 5 to do task 1 of this assignment. Feel free to discuss any of these with me.

Yes, there is no extra credit for early submission. Take your time and do a good job for this last assignment.

Handins

Hand in everything electronically, using Blackboard, by 5pm on the due date. Your handin should include your README file, code, test data, and anything else you have to show your work.

Grading

This assignment will be graded based on 100 points, allocated in proportion to the estimated amount of work for each part. You may do this assignment in a team of two people; the two people will receive the same points. Exceptionally well thought-out and well written work will receive appropriate extra credit. Extra credit work will be graded based on the estimated amount of extra work.