diff options
Diffstat (limited to 'Source/AIFramework/Expr.ssc')
| -rw-r--r-- | Source/AIFramework/Expr.ssc | 447 |
1 files changed, 447 insertions, 0 deletions
diff --git a/Source/AIFramework/Expr.ssc b/Source/AIFramework/Expr.ssc new file mode 100644 index 00000000..94dc4dc7 --- /dev/null +++ b/Source/AIFramework/Expr.ssc @@ -0,0 +1,447 @@ +//-----------------------------------------------------------------------------
+//
+// Copyright (C) Microsoft Corporation. All Rights Reserved.
+//
+//-----------------------------------------------------------------------------
+// This file specifies the expression language used by the Abstract
+// Interpretation Framework.
+//
+// expressions e ::= x variables
+// | f(e1,...,en) uninterpreted functions
+// | \x:t.e lambda expressions
+//
+// types t ::= b user-defined/built-in base types
+// | t1 * ... * tn -> t' function type
+
+namespace Microsoft.AbstractInterpretationFramework
+{
+ using System.Collections;
+ using Microsoft.Contracts;
+
+ //----------------------------- Expressions -----------------------------
+
+ /// <summary>
+ /// An interface for expressions. This expression language is specified
+ /// by interfaces to allow the client to be able to use their existing
+ /// AST nodes as AIF expressions.
+ ///
+ /// This only serves as a place for operations on expressions. Clients
+ /// should implement directly either IVariable or IFunApp.
+ /// </summary>
+ public interface IExpr
+ {
+ /// <summary>
+ /// Execute a visit over the expression.
+ /// </summary>
+ /// <param name="visitor">The expression visitor.</param>
+ /// <returns>The result of the visit.</returns>
+ [Pure][Reads(ReadsAttribute.Reads.Owned)] object DoVisit(ExprVisitor! visitor);
+
+ // TODO: Type checking of the expressions.
+ }
+
+ /// <summary>
+ /// An interface for variables.
+ ///
+ /// This interface should be implemented by the client.
+ /// </summary>
+ public interface IVariable : IExpr
+ {
+ string! Name { get; } // Each client must define the name for variables
+ }
+
+ /// <summary>
+ /// An interface for function applications.
+ ///
+ /// This interface should be implemented by the client.
+ /// </summary>
+ public interface IFunApp : IExpr
+ {
+ IFunctionSymbol! FunctionSymbol { [Pure][Reads(ReadsAttribute.Reads.Owned)] get; }
+ IList/*<IExpr!>*/! Arguments
+ {
+ [Pure][Reads(ReadsAttribute.Reads.Owned)][Rep] get
+ ensures result.IsReadOnly;
+ ;
+ }
+
+ /// <summary>
+ /// Provides a method to create a new uninterpreted function
+ /// with the same function symbol but with the arguments with
+ /// args.
+ /// </summary>
+ /// <param name="args">The new arguments.</param>
+ /// <returns>A copy of the function with the new arguments.</returns>
+ IFunApp! CloneWithArguments(IList/*<IExpr!>*/! args)
+ //TODO requires this.Arguments.Count == args.Count;
+ ;
+ }
+
+ /// <summary>
+ /// An interface for anonymous functions (i.e., lambda expressions)
+ /// </summary>
+ public interface IFunction : IExpr
+ {
+ IVariable! Param { [Pure][Reads(ReadsAttribute.Reads.Owned)] get; }
+ AIType! ParamType { [Pure][Reads(ReadsAttribute.Reads.Owned)] get; }
+ IExpr! Body { [Pure][Reads(ReadsAttribute.Reads.Owned)] get; }
+
+ IFunction! CloneWithBody(IExpr! body);
+ }
+
+ /// <summary>
+ /// An abstract class that provides an interface for expression visitors.
+ /// </summary>
+ public abstract class ExprVisitor
+ {
+ public abstract object Default(IExpr! expr);
+
+ public virtual object VisitVariable(IVariable! var)
+ {
+ return Default(var);
+ }
+
+ public virtual object VisitFunApp(IFunApp! funapp)
+ {
+ return Default(funapp);
+ }
+
+ public virtual object VisitFunction(IFunction! fun)
+ {
+ return Default(fun);
+ }
+ }
+
+ /// <summary>
+ /// A utility class for dealing with expressions.
+ /// </summary>
+ public sealed class ExprUtil
+ {
+ /// <summary>
+ /// Yield an expression that is 'inexpr' with 'var' replaced by 'subst'.
+ /// </summary>
+ /// <param name="subst">The expression to substitute.</param>
+ /// <param name="var">The variable to substitute for.</param>
+ /// <param name="inexpr">The expression to substitute into.</param>
+ public static IExpr! Substitute(IExpr! subst, IVariable! var, IExpr! inexpr)
+ {
+ IExpr result = null;
+
+ if (inexpr is IVariable)
+ {
+ result = inexpr.Equals(var) ? subst : inexpr;
+ }
+ else if (inexpr is IFunApp)
+ {
+ IFunApp! funapp = (IFunApp!)inexpr;
+ IList newargs = null;
+ newargs = new ArrayList{ IExpr! arg in funapp.Arguments; Substitute(subst, var, arg) };
+ result = funapp.CloneWithArguments(newargs);
+ }
+ else if (inexpr is IFunction)
+ {
+ IFunction! fun = (IFunction!)inexpr;
+
+ if (fun.Param.Equals(var))
+ result = fun;
+ else
+ result = fun.CloneWithBody(Substitute(subst, var, fun.Body));
+ }
+ else
+ {
+ assert false;
+ }
+
+ return result;
+ }
+
+
+ //
+ // Poor man's pattern matching.
+ //
+ // The methods below implement pattern matching for AI expressions.
+ //
+ // Example Usage:
+ // Match(e, Prop.Imp,
+ // (Matcher)delegate (IExpr e) { return Match(e, Prop.And, out x, out y); }
+ // out z)
+ // which sees if 'e' matches Prop.Imp(Prop.And(x,y),z) binding x,y,z to the subtrees.
+ //
+ public delegate bool Matcher(IExpr! expr);
+
+ private static IFunApp/*?*/ MatchFunctionSymbol(IExpr! expr, IFunctionSymbol! f)
+ {
+ IFunApp app = expr as IFunApp;
+ if (app != null)
+ {
+ if (app.FunctionSymbol.Equals(f))
+ return app;
+ else
+ return null;
+ }
+ else
+ return null;
+ }
+
+ public static bool Match(IExpr! expr, IFunctionSymbol! f, params Matcher[]! subs)
+ {
+ IFunApp app = MatchFunctionSymbol(expr,f);
+ if (app != null)
+ {
+ int i = 0; // Note ***0***
+ foreach (Matcher! s in subs)
+ {
+ if (!s((IExpr!)app.Arguments[i])) { return false; }
+ i++;
+ }
+ return true;
+ }
+ else { return false; }
+ }
+
+ // Unary Binding
+ public static bool Match(IExpr! expr, IFunctionSymbol! f, out IExpr arg0, params Matcher[]! subs)
+ {
+ arg0 = null;
+
+ IFunApp app = MatchFunctionSymbol(expr,f);
+ if (app != null)
+ {
+ arg0 = (IExpr!)app.Arguments[0];
+
+ int i = 1; // Note ***1***
+ foreach (Matcher! s in subs)
+ {
+ if (!s((IExpr!)app.Arguments[i])) { return false; }
+ i++;
+ }
+ return true;
+ }
+ else { return false; }
+ }
+
+ // Binary Binding
+ public static bool Match(IExpr! expr, IFunctionSymbol! f, Matcher! sub0, out IExpr arg1, params Matcher[]! subs)
+ {
+ arg1 = null;
+
+ IFunApp app = MatchFunctionSymbol(expr,f);
+ if (app != null)
+ {
+ if (!sub0((IExpr!)app.Arguments[0])) { return false; }
+
+ arg1 = (IExpr!)app.Arguments[1];
+
+ int i = 2; // Note ***2***
+ foreach (Matcher! s in subs)
+ {
+ if (!s((IExpr!)app.Arguments[i])) { return false; }
+ i++;
+ }
+ return true;
+ }
+ else { return false; }
+ }
+
+ public static bool Match(IExpr! expr, IFunctionSymbol! f, out IExpr arg0, out IExpr arg1, params Matcher[]! subs)
+ {
+ arg0 = null;
+ arg1 = null;
+
+ IFunApp app = MatchFunctionSymbol(expr,f);
+ if (app != null)
+ {
+ arg0 = (IExpr!)app.Arguments[0];
+ arg1 = (IExpr!)app.Arguments[1];
+
+ int i = 2; // Note ***2***
+ foreach (Matcher! s in subs)
+ {
+ if (!s((IExpr!)app.Arguments[i])) { return false; }
+ i++;
+ }
+ return true;
+ }
+ else { return false; }
+ }
+
+ // Ternary Binding
+ public static bool Match(IExpr! expr, IFunctionSymbol! f, out IExpr arg0, out IExpr arg1, out IExpr arg2, params Matcher[]! subs)
+ {
+ arg0 = null;
+ arg1 = null;
+ arg2 = null;
+
+ IFunApp app = MatchFunctionSymbol(expr,f);
+ if (app != null)
+ {
+ arg0 = (IExpr!)app.Arguments[0];
+ arg1 = (IExpr!)app.Arguments[1];
+ arg2 = (IExpr!)app.Arguments[2];
+
+ int i = 3; // Note ***3***
+ foreach (Matcher! s in subs)
+ {
+ if (!s((IExpr!)app.Arguments[i])) { return false; }
+ i++;
+ }
+ return true;
+ }
+ else { return false; }
+ }
+
+ /// <summary>
+ /// Not intended to be instantiated.
+ /// </summary>
+ private ExprUtil() { }
+ }
+
+ //------------------------------ Symbols --------------------------------
+
+ /// <summary>
+ /// An interface for function symbols. Constants are represented by
+ /// 0-ary function symbols.
+ ///
+ /// This interface should be implemented by abstract domains, but client
+ /// expressions need keep track of function symbols.
+ /// </summary>
+ public interface IFunctionSymbol
+ {
+ AIType! AIType { [Pure][Reads(ReadsAttribute.Reads.Owned)][Rep][ResultNotNewlyAllocated]
+ get; }
+ }
+
+ /// <summary>
+ /// The type of the arguments to ExprUtil.Match, a poor man's pattern
+ /// matching.
+ /// </summary>
+ public interface IMatchable
+ {
+ }
+
+ //-------------------------------- Types --------------------------------
+
+ /// <summary>
+ /// Types.
+ /// </summary>
+ public interface AIType
+ {
+ }
+
+ /// <summary>
+ /// Function type constructor.
+ /// </summary>
+ public sealed class FunctionType : AIType
+ {
+ /*[Own]*/ private readonly IList/*<Type!>*/! argTypes;
+ /*[Own]*/ private readonly AIType! retType;
+
+ public FunctionType(params AIType[]! types)
+ requires types.Length >= 2;
+ {
+ AIType type = types[types.Length-1];
+ assume type != null;
+ this.retType = type;
+ ArrayList argTypes = new ArrayList();
+ for (int i = 0; i < types.Length-1; i++)
+ {
+ type = types[i];
+ assume type != null;
+ argTypes.Add(types);
+ }
+ this.argTypes = ArrayList.ReadOnly(argTypes);
+ }
+
+ public IList/*<AIType!>*/! Arguments
+ {
+ [Pure][Reads(ReadsAttribute.Reads.Owned)][Rep]
+ get
+ ensures result.IsReadOnly;
+ {
+ return argTypes;
+ }
+ }
+
+ public int Arity
+ {
+ [Pure][Reads(ReadsAttribute.Reads.Owned)] get { return argTypes.Count; }
+ }
+
+ public AIType! ReturnType
+ {
+ [Pure][Reads(ReadsAttribute.Reads.Owned)] get { return retType; }
+ }
+
+ /* TODO Do we have the invariant that two functions are equal iff they're the same object.
+ public override bool Equals(object o)
+ {
+ if (o != null && o is FunctionType)
+ {
+ FunctionType other = (FunctionType) o;
+
+ if (Arity == other.Arity
+ && ReturnType.Equals(other.ReturnType))
+ {
+ for (int i = 0; i < Arity; i++)
+ {
+ if (!argTypes[i].Equals(other.argTypes[i]))
+ return false;
+ }
+ return true;
+ }
+ else
+ return false;
+ }
+ else
+ return false;
+ }
+ */
+ }
+
+ //------------------------------ Queries -------------------------------
+
+ public enum Answer { Yes, No, Maybe };
+
+ /// <summary>
+ /// An interface that specifies a queryable object that can answer
+ /// whether a predicate holds.
+ /// </summary>
+ public interface IQueryable
+ {
+ /// <summary>
+ /// Answers the query whether the given predicate holds.
+ /// </summary>
+ /// <param name="pred">The given predicate.</param>
+ /// <returns>Yes, No, or Maybe.</returns>
+ Answer CheckPredicate(IExpr! pred);
+
+ /// <summary>
+ /// A simplified interface for disequalities. One can always
+ /// implement this by calling CheckPredicate, but it may be
+ /// more efficient with this method.
+ /// </summary>
+ Answer CheckVariableDisequality(IVariable! var1, IVariable! var2);
+ }
+
+ public static class QueryUtil
+ {
+ public static Answer Negate(Answer ans)
+ {
+ switch (ans)
+ {
+ case Answer.Yes:
+ return Answer.No;
+ case Answer.No:
+ return Answer.Yes;
+ default:
+ return Answer.Maybe;
+ }
+ }
+ }
+
+ //----------------------------- Exceptions -----------------------------
+
+ public class TypeError : CheckedException
+ {
+ }
+}
|