Search code examples
recursionbinary-treesmlsmlnj

Recursing Binary Decision Diagrams in SML

In one of my classes at university, we are learning functional programming through SML/NJ.

I have been given an assignment which requires us to perform a number of operations on Binary Decision Diagrams. (conjunction, disjunction, not, etc.)

Based on this truth table

table

I have the following function defined

fun IfThenElse(p,q,r) = 
  if p then q else r;

Then, we have the BDD (ROBDD) datatype declared as such

datatype ROBDD = true
               | false
               | IfThenElse of string * ROBDD * ROBDD;

So far this is all fairly straightforward. I'm getting lost on actually operating on BDD's, for instance, creating an ROBDD which represents the conjunction of two ROBDD's.

My function declaration so far looks like this

infix bddAnd;
fun op bddAnd(first:ROBDD,second:ROBDD) = 
   ...

It will be called with two ROBDD's, something like this

val conjunction = IfThenElse("p", true, false) bddAnd IfThenElse("q", true, false);

From here, I'm not really sure where to start. My professor has given us this hint:

Of course, True bddAnd anyROBDD will be just anyROBDD. To get the ordering: If you’re asked to compute (IfThenElse(p, ϕ, ψ) bddAnd IfThenElse(q, χ, θ)) the proposition letter at the root of the resultant ROBDD will be either p or q – whichever is less. So you’ll need 3 cases: p < q, p = q, and p > q. Having determined the root, you recurse down the branches

The first part makes sense, but I'm left with two questions.

1. How do I determine the root of any ROBDD?

If it's just true or false, it doesn't have one, right? So there should be a special case for just being given a boolean? If we are given a more fleshed out ROBDD, like IfThenElse("p", true, false), how do I gain access to p, in the ROBDD structure? Note that the first argument of an IfThenElse will always be a letter.

2. How do I recurse through the ROBDD's?

I understand the basics of recursive functions in SML, but I'm confused on how to do it within the ROBDD structure, compared to say, lists. I'm guessing I need to build some sort of curried functions that operate on each argument in the ROBDD, but I'm really not sure how to structure it.

Apologies for the long winded question, but I'm really having a hard time understanding how to operate on the ROBDD structure. Any explanation would be very helpful, thank you!

EDIT:

After some syntax and renaming, my bddAnd function now looks like this

infix bddAnd;
fun op bddAnd (true, second) = second
  | op bddAnd (first, true) = first
  | op bddAnd (false, _) = false
  | op bddAnd (_, false) = false
  | op bddAnd ((left as (IfThenElse (prop1, true1, else1))), (right as (IfThenElse (prop2, true2, else2)))) = 
        if prop1 < prop2 then 
          IfThenElse (prop1, true1 bddAnd right, else1 bddAnd right)
        else if prop1 > prop2 then
          IfThenElse (prop2, true2 bddAnd left, else2 bddAnd left)
        else
          IfThenElse (prop1, true1 bddAnd right, else1 bddAnd left);
Solution

  • Pattern matching is usually a good starting point.

    The cases involving True and False are simple:

    fun op bddAnd (True, second) = second
     | bddAnd (first, True) = first
     | bddAnd (False, _) = False
     | bddAnd (_, False) = False

    the last one is more interesting:

     | bddAnd (IfThenElse (v1, t1, e1)) (IfThenElse (v2, t2, e2)) = ... what? ...

    As your professor hinted, you need to consider three cases for v1 and v2:

    if v1 < v2 then ...
else if v1 > v2 then ...
else ...

    Looking at the first one, v1 < v2, we should pick v1 as the "root".

    It's not very difficult to convince yourself that

    (IfThenElse p T1 E1) bddAnd (IfThenElse q T2 E2)

    is equivalent to

    IfThenElse p (T1 bddAnd (IfThenElse q T2 E2)) (E1 bddAnd (IfThenElse q T2 E2))

    that is, you create one "tree" from two by recursing into both branches of the IfThenElse you chose, bringing the other tree along.
    The recursion will terminate since bddAnd is applied to smaller and smaller arguments, and the result will be ordered as long as the input was ordered (which I assume we are allowed to assume).

    Matching the code above,

     | bddAnd (left as (IfThenElse (v1, t1, e1))) (right as (IfThenElse (v2, t2, e2))) = 
        if v1 < v2 then IfThenElse (v1, t1 bddAnd right, e1 bddAnd right)
        else ...

    (Using as-patterns to make it easier to refer to the parameters as wholes.)

    The remaining two cases left as an exercise.