Control abstraction --- Writing queries

This assignment has three goals: (1) writing queries using comprehensions, (2) writing queries using recursive functions, and (3) generating logic program code for a portion of the EHR policy rules. Both (1) and (2) are exercises for programming with control abstraction. We will continue to use the EHR policy rules and the Python programs for reading in these rules from Assignment 2, but please use the updated files: spine, pds, hospital, ra, and ehrparse.py; they contain small fixes and/or improvements that should not affect programs for previous assignments.

Writing queries using comprehensions

Most of you used a lot of loops to do Assignments 2 and 3, but one could write programs for the same tasks using comprehensions instead of loops, and the resulting programs are usually simpler and clearer. For example, for the five tasks in Assignment 2, below is my complete program written using comprehensions:

import ehrparse

def a2():
    rules = ehrparse.parse()
    facts = [r for r in rules if r.hypos == []]
    conclpreds = set(r.concl.name for r in rules)
    hypospreds = set(h.name for r in rules for h in r.hypos
		     if isinstance(h,ehrparse.Atom))
    remoteatoms = [h for r in rules for h in r.hypos
		   if isinstance(h,ehrparse.RemoteAtom)]

    print 'rules', len(rules)
    print 'facts', len(facts)
    print 'conclpreds', len(conclpreds)
    print 'hypospreds', len(hypospreds)
    print 'remoteatoms', len(remoteatoms)

Writing queries using recursive functions

Another way to program the analysis in Assignments 2 and 3 is to use recursive functions instead of loops. Specifically, to process lists, you can only call the following functions on lists, not using any other built-in functions:

def null(l):   #true iff list l is empty
    return l==[]
def car(l):    #head of l, i.e., first element of l
    return l[0]
def cdr(l):    #tail of l, i.e., all elements except the first element of l
    return l[1:]
def nil():     #an empty list
    return []
def cons(h,t): #a list whose head is h and whose tail is t
    l=[h]
    l[1:1]=t
    return l

def facts1(rules):
    if null(rules): return nil()
    elif null(car(rules).hypos):
        return cons(car(rules),facts1(cdr(rules)))
    else: return facts1(cdr(rules))

def facts2(rules):
    return (
        nil() if null(rules)
        else cons(car(rules),facts2(cdr(rules))) if null(car(rules).hypos)
        else facts2(cdr(rules))
        )

def facts2(rules):
    if null(rules): return nil()
    t = facts2(cdr(rules))
    if null(car(rules).hypos): return cons(car(rules),t)
    else: return t

Generating logic program code

The third task is to generate logic program code for EHR policy rules that do not use constraints or aggregates. We just need to add explicit location and issuer arguments to each Atom object and remove all RemoteAtom objects; and to flatten any RemoteAtom object in an argument of an Atom object into multiple arguments of the Atom object.

Specifically, we will
1. find all the rules that do not use constraints or aggregates;
2. for each rule found in 1, and for each conclusion or hypothesis of the rule that is an Atom object or a RemoteAtom object:
2.1. if it is an Atom object, of form p(a1,...,ak),
produce from it a new Atom object, of form p(Local,Local,a1,...,ak), where "Local" is a constant;
2.2. if it is a RemoteAtom object, of form loc@iss.p(a1,...,ak),
produce from it an Atom object, of form p(loc,iss,a1,...,ak);
if location loc is missing, i.e., has value None, use "Local" instead;
2.3. consider the resulting Atom object, say of form p(a1,...,ak), from 2.1 or 2.2:
if an argument of it, say ai, is a RemoteAtom object, of form loc@iss.q(b1,...bj),
flatten ai to become new arguments of p, i.e.,
produce from p(a1,...,ai,...,ak) a new Atom object p(a1,...,q,loc,iss,b1,...,bj,...,ak), where "q" is a constant; again, if location loc is missing, i.e., has value None, use "Local" instead.

For example, for the EHR policy rule:

(S1.4.6)
canReqCred(ag, "Spine".canActivate(ag, Agent(pat))) <- 
hasActivated(ag, Agent(pat))

canReqCred("Local","Local",ag,"canActivate","Local","Spine",ag,Agent(pat)) <-
hasActivated("Local","Local",ag,Agent(pat))

The generated logic program rules should be constructed from the parts of the policy rules and returned as results of functions. To finally produce the logic program code, you need to (1) replace "<-" with ":-", (2) add "." at the end of each rule, (3) make all variables upper-case initial, and (4) make all constants and constructors lower-case initial. For example, for the new rule produced above, the following actual code should be generated:

canReqCred(local,local,Ag,canActivate,local,spine,Ag,agent(Pat)) :-
hasActivated(local,local,Ag,agent(Pat)).

Extra credit suggestions

Here are some ideas. (1) Finish this assignment by Thursday March 26, and receive 10% extra credit. (2) Write recursive functions for the same items in analysis of predicates as in Assignment 3. (3) Think of ways to analyze the types of the arguments of predicates, and do them; partial information about types counts too, such as some argument of some predicate always being a structure of some constructor. (4) Think of other interesting and/or useful things to analyze about the EHR policy, and do them. Feel free to discuss any of these with me.

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.