Expert F# 3.0 by Don Syme & Adam Granicz & Antonio Cisternino

Author:Don Syme & Adam Granicz & Antonio Cisternino [Syme, Don & Granicz, Adam & Cisternino, Antonio]
Language: eng
Format: epub
ISBN: 9781430246503
Publisher: Apress
Published: 2012-10-30T04:00:00+00:00

Representing Propositional Formulae Efficiently Using BDDs

In practice, propositional formulae to describe hardware can be enormous, involving hundreds of thousands of nodes. As a result, hardware companies have an interest in smart algorithms to process these formulae and check them for correctness. The circuits in the computers you use from day to day have almost certainly been verified using advanced propositional logic techniques, often using a functional language as the means to drive and control the analysis of the circuits.

A major advance in the application of symbolic techniques to hardware design occurred in the late 1980s with the discovery of binary decision diagrams, a representation for propositional logic formulae that is compact for many common circuit designs. BDDs represent a propositional formula via the use of if ... then ... else conditionals alone, which you write as (variable => true-branch | false-branch). Special nodes are used for true and false at the leaves: you write these as T and F. Every BDD is constructed with respect to a global variable ordering, so x AND NOT y can be represented as (x => (y => F | T) | F) if x comes before y in this ordering and as (y => F | (x => T | F)) if y comes before x. The variable ordering can be critical for performance of the representation.

BDDs are efficient because they use some of the language representation techniques you saw in Chapter 9. In particular, they work by uniquely memoizing all BDD nodes that are identical, which works by representing a BDD as an integer index into a lookup table that stores the real information about the node. Furthermore, negative indexes are used to represent the negation of a particular BDD node without creating a separate entry for the negated node. Listing 12-3 shows an implementation of BDDs. Fully polished BDD packages are often implemented in C. It’s easy to access those packages from F# using the techniques described in Chapter 19. Here, you have a clear and simple implementation entirely in F# code.

Listing 12-3. Implementing Binary Decision Diagrams

open System.Collections.Generic

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.