array_proof_rules.h

Go to the documentation of this file.

/*****************************************************************************/
/*!
 * \file array_proof_rules.h
 * 
 * Author: Clark Barrett 5/29/2003
 * 
 * Created: May 29 19:16:33 GMT 2003
 *
 * <hr>
 * Copyright (C) 2003 by the Board of Trustees of Leland Stanford
 * Junior University and by New York University. 
 *
 * License to use, copy, modify, sell and/or distribute this software
 * and its documentation for any purpose is hereby granted without
 * royalty, subject to the terms and conditions defined in the \ref
 * LICENSE file provided with this distribution.  In particular:
 *
 * - The above copyright notice and this permission notice must appear
 * in all copies of the software and related documentation.
 *
 * - THE SOFTWARE IS PROVIDED "AS-IS", WITHOUT ANY WARRANTIES,
 * EXPRESSED OR IMPLIED.  USE IT AT YOUR OWN RISK.
 * 
 * <hr>
 * 
 * CLASS: ArrayProofRules
 * 
 * 
 * Description: Array proof rules.
 */
/*****************************************************************************/

#ifndef _cvcl__theory_array__array_proof_rules_h_
#define _cvcl__theory_array__array_proof_rules_h_

namespace CVCL {

  class Theorem;
  class Expr;
  
  class ArrayProofRules {
  public:
    // Destructor
    virtual ~ArrayProofRules() { }

    ////////////////////////////////////////////////////////////////////
    // Proof rules
    ////////////////////////////////////////////////////////////////////

    // ==>
    // write(store, index_0, v_0, index_1, v_1, ..., index_n, v_n) = store IFF
    //
    // read(store, index_n) = v_n &
    // index_{n-1} != index_n -> read(store, index_{n-1}) = v_{n-1} &
    // (index_{n-2} != index_{n-1} & index_{n-2} != index_n) -> read(store, index_{n-2}) = v_{n-2} &
    // ...
    // (index_1 != index_2 & ... & index_1 != index_n) -> read(store, index_1) = v_1
    // (index_0 != index_1 & index_0 != index_2 & ... & index_0 != index_n) -> read(store, index_0) = v_0
    virtual Theorem rewriteSameStore(const Expr& e, int n) = 0;

    // ==> write(store, index, value) = write(...) IFF
    //       store = write(write(...), index, read(store, index)) &
    //       value = read(write(...), index)
    virtual Theorem rewriteWriteWrite(const Expr& e) = 0;

    // ==> read(write(store, index1, value), index2) =
    //   ite(index1 = index2, value, read(store, index2))
    virtual Theorem rewriteReadWrite(const Expr& e) = 0;

    // value = read(store, index) ==>
    //   write(store, index, value) = store
    virtual Theorem rewriteRedundantWrite1(const Theorem& v_eq_r,
                                           const Expr& write) = 0;

    // ==>
    //   write(write(store, index, v1), index, v2) = write(store, index, v2)
    virtual Theorem rewriteRedundantWrite2(const Expr& e) = 0;

    // ==>
    //   write(write(store, index1, v1), index2, v2) =
    //   write(write(store, index2, v2), index1, ite(index1 = index2, v2, v1))
    virtual Theorem interchangeIndices(const Expr& e) = 0;
    //! Beta reduction of array literal: |- (array x. f(x))[arg] = f(arg)
    virtual Theorem readArrayLiteral(const Expr& e) = 0;

  }; // end of class ArrayProofRules

} // end of namespace CVCL

#endif

---