package scala_par_am
- Alphabetic
- Public
- All
Type Members
-
abstract
class
AbstractMachine[Exp, Abs, Addr, Time] extends AnyRef
The interface of the abstract machine itself.
The interface of the abstract machine itself. Abstract class that should be implemented by an abstract machine. Abstract machines that implement that in Scala-Par-AM are AAM*.scala and ParAAM*.scala.
The abstract machine is parameterized by abstract values, addresses and expressions. Look into AAM.scala for an example of how to define these parameters.
-
abstract
class
Action[Exp, Abs, Addr] extends MemoHashCode
The different kinds of actions that can be taken by the abstract machine
-
case class
ActionError[Exp, Abs, Addr](error: SemanticError)(implicit evidence$37: Expression[Exp], evidence$38: JoinLattice[Abs], evidence$39: Address[Addr]) extends Action[Exp, Abs, Addr] with Product with Serializable
An error has been reached
-
case class
ActionEval[Exp, Abs, Addr](e: Exp, env: Environment[Addr], store: Store[Addr, Abs], effects: Set[Effect[Addr]] = Set[Effect[Addr]]())(implicit evidence$31: Expression[Exp], evidence$32: JoinLattice[Abs], evidence$33: Address[Addr]) extends Action[Exp, Abs, Addr] with Product with Serializable
Evaluation continues with expression e in environment env
- class ActionHelpers[Exp, Abs, Addr] extends AnyRef
-
case class
ActionPush[Exp, Abs, Addr](frame: Frame, e: Exp, env: Environment[Addr], store: Store[Addr, Abs], effects: Set[Effect[Addr]] = Set[Effect[Addr]]())(implicit evidence$28: Expression[Exp], evidence$29: JoinLattice[Abs], evidence$30: Address[Addr]) extends Action[Exp, Abs, Addr] with Product with Serializable
A frame needs to be pushed on the stack, and the interpretation continues by evaluating expression e in environment env
-
case class
ActionReachedValue[Exp, Abs, Addr](v: Abs, store: Store[Addr, Abs], effects: Set[Effect[Addr]] = Set[Effect[Addr]]())(implicit evidence$25: Expression[Exp], evidence$26: JoinLattice[Abs], evidence$27: Address[Addr]) extends Action[Exp, Abs, Addr] with Product with Serializable
A value is reached by the interpreter.
A value is reached by the interpreter. As a result, a continuation will be popped with the given reached value.
-
case class
ActionStepIn[Exp, Abs, Addr](fexp: Exp, clo: (Exp, Environment[Addr]), e: Exp, env: Environment[Addr], store: Store[Addr, Abs], argsv: List[(Exp, Abs)], effects: Set[Effect[Addr]] = Set[Effect[Addr]]())(implicit evidence$34: Expression[Exp], evidence$35: JoinLattice[Abs], evidence$36: Address[Addr]) extends Action[Exp, Abs, Addr] with Product with Serializable
Similar to ActionEval, but only used when stepping inside a function's body (clo is therefore the function stepped into).
Similar to ActionEval, but only used when stepping inside a function's body (clo is therefore the function stepped into). The expressions and values of the arguments should also be provided, as they can be needed by the abstract machine.
- trait Address[A] extends AnyRef
- trait AddressWrapper extends AnyRef
- case class ArityError(name: String, expected: Int, got: Int) extends SemanticError with Product with Serializable
-
class
BaseSchemeSemantics[V, Addr, Time] extends Semantics[SchemeExp, V, Addr, Time]
Basic Scheme semantics, without any optimization
-
case class
BasicEnvironment[Addr](content: Map[String, Addr])(implicit evidence$2: Address[Addr]) extends Environment[Addr] with Product with Serializable
Basic mapping from names to addresses
- case class BasicKontStore[KontAddr](content: Map[KontAddr, Set[Kont[KontAddr]]])(implicit evidence$3: KontAddress[KontAddr]) extends KontStore[KontAddr] with Product with Serializable
-
case class
BasicStore[Addr, Abs](content: Map[Addr, Abs])(implicit evidence$3: Address[Addr], evidence$4: JoinLattice[Abs]) extends Store[Addr, Abs] with Product with Serializable
Basic store with no fancy feature, just a map from addresses to values
-
trait
BoolLattice[B] extends LatticeElement[B]
A lattice for booleans
- class BoundedInteger extends AnyRef
- case class CannotAccessCar(v: String) extends SemanticError with MemoHashCode with Product with Serializable
- case class CannotAccessCdr(v: String) extends SemanticError with MemoHashCode with Product with Serializable
- case class CannotAccessVector(vector: String) extends SemanticError with MemoHashCode with Product with Serializable
-
sealed
trait
Cardinality extends MemoHashCode
Cardinality represents how much information a lattice value represents
- case class CardinalityNumber(n: Int) extends Cardinality with Product with Serializable
-
trait
CharLattice[C] extends LatticeElement[C]
A lattice for characters
- case class Color(hex: String) extends MemoHashCode with Product with Serializable
- trait Count extends MemoHashCode
- case class CountingStore[Addr, Abs](content: Map[Addr, (Count, Abs)])(implicit evidence$5: Address[Addr], evidence$6: JoinLattice[Abs]) extends Store[Addr, Abs] with Product with Serializable
- abstract class Effect[Addr] extends MemoHashCode
- case class EffectAcquire[Addr](target: Addr)(implicit evidence$17: Address[Addr]) extends Effect[Addr] with Product with Serializable
-
trait
EffectKind extends MemoHashCode
The different kinds of effects that can be generated by the semantics
- case class EffectReadConsCar[Addr](target: Addr)(implicit evidence$10: Address[Addr]) extends Effect[Addr] with Product with Serializable
- case class EffectReadConsCdr[Addr](target: Addr)(implicit evidence$11: Address[Addr]) extends Effect[Addr] with Product with Serializable
- case class EffectReadVariable[Addr](target: Addr)(implicit evidence$9: Address[Addr]) extends Effect[Addr] with Product with Serializable
- case class EffectReadVector[Addr](target: Addr)(implicit evidence$12: Address[Addr]) extends Effect[Addr] with Product with Serializable
- case class EffectRelease[Addr](target: Addr)(implicit evidence$18: Address[Addr]) extends Effect[Addr] with Product with Serializable
- case class EffectWriteConsCar[Addr](target: Addr)(implicit evidence$14: Address[Addr]) extends Effect[Addr] with Product with Serializable
- case class EffectWriteConsCdr[Addr](target: Addr)(implicit evidence$15: Address[Addr]) extends Effect[Addr] with Product with Serializable
- case class EffectWriteVariable[Addr](target: Addr)(implicit evidence$13: Address[Addr]) extends Effect[Addr] with Product with Serializable
- case class EffectWriteVector[Addr](target: Addr)(implicit evidence$16: Address[Addr]) extends Effect[Addr] with Product with Serializable
- abstract class Environment[Addr] extends MemoHashCode
-
abstract
class
EvalKontMachine[Exp, Abs, Addr, Time] extends AbstractMachine[Exp, Abs, Addr, Time]
Abstract machine with a control component that works in an eval-kont way: it can either be evaluating something, or have reached a value and will pop a continuation.
- trait Expression[E] extends AnyRef
- trait Frame extends MemoHashCode
-
class
Graph[N] extends AnyRef
Represents an immutable directed graph where nodes are elements of N: (source node) -> (id of source node, set of neighbors)
-
class
GraphInfo extends AnyRef
Several information about a graph.
- trait GraphOutput extends AnyRef
- trait GraphOutputNode[N] extends AnyRef
-
case class
Identifier(name: String, pos: Position) extends MemoHashCode with Product with Serializable
An identifier has a name and a position
-
trait
IntLattice[I] extends LatticeElement[I]
A lattice for integers
-
trait
IsSchemeLattice[L] extends JoinLattice[L]
A lattice for Scheme should support the following operations
-
trait
JoinLattice[L] extends Monoid[L] with PartialOrdering[L]
A (join semi-)lattice L should support the following operations
- case class Kont[KontAddr](frame: Frame, next: KontAddr)(implicit evidence$1: KontAddress[KontAddr]) extends MemoHashCode with Product with Serializable
- trait KontAddress[A] extends AnyRef
- abstract class KontStore[KontAddr] extends MemoHashCode
-
trait
LatticeElement[L] extends Order[L] with Monoid[L] with Show[L]
We define here some domains that can will be useful to build a lattice for most languages.
- class MakeSchemeLattice[S, B, I, F, C, Sym] extends SchemeLattice
- sealed trait MayFail[L] extends MemoHashCode
- case class MayFailBoth[L](l: L, errs: List[SemanticError]) extends MayFail[L] with Product with Serializable
- case class MayFailError[L](errs: List[SemanticError]) extends MayFail[L] with Product with Serializable
- case class MayFailSuccess[L](l: L) extends MayFail[L] with Product with Serializable
-
trait
MemoHashCode extends Product
Memoize the default hash code method.
Memoize the default hash code method. That can be improve use of all immutable object.
- case class NotSupported(reason: String) extends SemanticError with Product with Serializable
- case class OperatorNotApplicable(name: String, arguments: List[String]) extends SemanticError with Product with Serializable
-
class
ParAAMCHybrid[Exp, Abs, Addr, Time] extends ParAAMCState[Exp, Abs, Addr, Time]
ParAAMCHybrid: similar than ParAAMCPart and ParAAMCSet when the number of sets in the worklist if greater or equal to the number of available actors.
ParAAMCHybrid: similar than ParAAMCPart and ParAAMCSet when the number of sets in the worklist if greater or equal to the number of available actors.
The worklist is implemented by an immutable list of set of states.
The main method eval() just send the initial state to the first ActorEval.
Each actor ActorEval evaluates a set of states, updates data, and sends equal part of the worklist to each actor ActorEval available, until to the worklist becomes empty.
-
class
ParAAMCHybridH[Exp, Abs, Addr, Time] extends ParAAMCState[Exp, Abs, Addr, Time]
ParAAMCHybridH: ParAAMCHybrid with direct identification of Halted states
ParAAMCHybridH: ParAAMCHybrid with direct identification of Halted states
Version of ParAAMCHybrid that includes to the worklist only the not halted states. Halted states are directly identified in the set of successors.
The worklist is implemented by an immutable list of set of states.
The main method eval() just send the initial state to the first ActorEval.
Each actor ActorEval evaluates a set of states, updates data, and sends equal part of the worklist to each actor ActorEval available, until to the worklist becomes empty.
-
class
ParAAMCPart[Exp, Abs, Addr, Time] extends ParAAMCState[Exp, Abs, Addr, Time]
ParAAMCPart: ParAAM-C-set for Parallel AAM - Concurrent - set
ParAAMCPart: ParAAM-C-set for Parallel AAM - Concurrent - set
Similar to ParAAMCState but sends equal part instead state, and there is NO global worklist.
The local worklist (named newStates) is implemented by an immutable list of set of states.
The main method eval() just send the initial state to the first ActorEval.
Each actor ActorEval evaluates a set of states, updates data, and sends equal part of its local worklist to each actor ActorEval available, until there is no more state to evaluate.
-
class
ParAAMCPartH[Exp, Abs, Addr, Time] extends ParAAMCState[Exp, Abs, Addr, Time]
ParAAMCPartH: ParAAMCPart with direct identification of Halted states
ParAAMCPartH: ParAAMCPart with direct identification of Halted states
Version of ParAAMCPart that includes to the worklist only the not halted states. Halted states are directly identified in the set of successors.
The worklist is implemented by an immutable list of set of states.
The main method eval() just send the initial state to the first ActorEval.
Each actor ActorEval evaluates a set of states, updates data, and sends equal part of the worklist to each actor ActorEval available, until to the worklist becomes empty.
-
class
ParAAMCSPart[Exp, Abs, Addr, Time] extends ParAAMCSState[Exp, Abs, Addr, Time]
ParAAMCSPart: ParAAM-C-S-part for Parallel AAM - Concurrent - Sender - part
ParAAMCSPart: ParAAM-C-S-part for Parallel AAM - Concurrent - Sender - part
Similar to ParAAMCSState but sends equal part of the worklist instead state.
The worklist is implemented by an immutable list of sets of states.
The main method eval() just starts the unique actor ActorSender. This actor sends the initial state to the first actor ActorEval.
Each actor ActorEval evaluates a set of states, updates data, and sends that it is now available to the actor ActorSender.
Each time that the ActorSender receives a message from an actor ActorEval, it sends equal part of the worklist to each actor ActorEval available, until to the worklist becomes empty.
-
class
ParAAMCSSet[Exp, Abs, Addr, Time] extends ParAAMCSState[Exp, Abs, Addr, Time]
ParAAMCSSet: ParAAM-C-S-set for Parallel AAM - Concurrent - Sender - set
ParAAMCSSet: ParAAM-C-S-set for Parallel AAM - Concurrent - Sender - set
Similar to ParAAMCSState but sends set of states instead state.
The worklist is implemented by an immutable list of sets of states.
The main method eval() just starts the unique actor ActorSender. This actor sends the initial state to the first actor ActorEval.
Each actor ActorEval evaluates a set of states, updates data, and sends that it is now available to the actor ActorSender.
Each time that the ActorSender receives a message from an actor ActorEval, it sends one set of states of the worklist to each actor ActorEval available, until to the worklist becomes empty.
-
class
ParAAMCSState[Exp, Abs, Addr, Time] extends ParAAMLSAState[Exp, Abs, Addr, Time]
ParAAMCSState: ParAAM-C-S-state for Parallel AAM - Concurrent - Sender - state
ParAAMCSState: ParAAM-C-S-state for Parallel AAM - Concurrent - Sender - state
The worklist is implemented by an immutable list of sets of states.
The main method eval() just starts the unique actor ActorSender. This actor sends the initial state to the first actor ActorEval.
Each actor ActorEval evaluates a state, updates data, and sends that it is now available to the actor ActorSender.
Each time that the ActorSender receives a message from an actor ActorEval, it sends one state of the worklist to each actor ActorEval available, until to the worklist becomes empty.
Extend ParAAMLSAState class to reuse common code.
-
class
ParAAMCSet[Exp, Abs, Addr, Time] extends ParAAMCState[Exp, Abs, Addr, Time]
ParAAMCSet: ParAAM-C-set for Parallel AAM - Concurrent - set
ParAAMCSet: ParAAM-C-set for Parallel AAM - Concurrent - set
Similar to ParAAMCState but sends set of states instead state.
The worklist is implemented by an immutable list of sets of states.
The main method eval() just sends the initial state to the first ActorEval.
Each actor ActorEval evaluates a set of states, updates data, and sends one set of states of the worklist to each actor ActorEval available, until to the worklist becomes empty.
-
class
ParAAMCSetH[Exp, Abs, Addr, Time] extends ParAAMCState[Exp, Abs, Addr, Time]
ParAAMCSetH: ParAAMCSet with direct identification of Halted states
ParAAMCSetH: ParAAMCSet with direct identification of Halted states
Version of ParAAMCSet that includes to the worklist only the not halted states. Halted states are directly identified in the set of successors.
The worklist is implemented by an immutable list of sets of states.
The main method eval() just sends the initial state to the first ActorEval.
Each actor ActorEval evaluates a set of states, updates data, and sends one set of states of the worklist to each actor ActorEval available, until to the worklist becomes empty.
-
class
ParAAMCState[Exp, Abs, Addr, Time] extends ParAAMCSState[Exp, Abs, Addr, Time]
ParAAMCState: ParAAM-C-state for Parallel AAM - Concurrent - state
ParAAMCState: ParAAM-C-state for Parallel AAM - Concurrent - state
The worklist is implemented by an immutable list of sets of states.
The main method eval() just sends the initial state to the first ActorEval.
Each actor ActorEval evaluates a state, updates data, and sends one state of the worklist to each actor ActorEval available, until to the worklist becomes empty.
Extend ParAAMCSState class to reuse common code.
-
class
ParAAMLSAPart[Exp, Abs, Addr, Time] extends ParAAMLSAState[Exp, Abs, Addr, Time]
ParAAMLSAPart: ParAAM-L-SA-part for Parallel AAM - Loop - SenderAggregator - part
ParAAMLSAPart: ParAAM-L-SA-part for Parallel AAM - Loop - SenderAggregator - part
Similar to ParAAMLSAState but sends successively equal part of the worklist instead state.
The worklist is implemented by an immutable list of sets of states.
The main method eval() loops until the worklist is empty. An unique actor ActorSenderAggregator sends successively equal part of the worklist to actors ActorEval and then collects each of these results.
-
class
ParAAMLSASet[Exp, Abs, Addr, Time] extends ParAAMLSAState[Exp, Abs, Addr, Time]
ParAAMLSASet: ParAAM-L-SA-set for Parallel AAM - Loop - SenderAggregator - set
ParAAMLSASet: ParAAM-L-SA-set for Parallel AAM - Loop - SenderAggregator - set
Similar to ParAAMLSAState but sends successively set of states instead state.
The worklist is implemented by an immutable list of sets of states.
The main method eval() loops until the worklist is empty. An unique actor ActorSenderAggregator sends successively each set of states of the worklist to actors ActorEval (modulo the number of these actors) and then collects each of these results.
-
class
ParAAMLSAState[Exp, Abs, Addr, Time] extends SeqAAM[Exp, Abs, Addr, Time]
ParAAMLSAState: ParAAM-L-SA-state for Parallel AAM - Loop - SenderAggregator - state
ParAAMLSAState: ParAAM-L-SA-state for Parallel AAM - Loop - SenderAggregator - state
The worklist is implemented by an immutable list of sets of states.
The main method eval() loops until the worklist is empty. An unique actor ActorSenderAggregator sends successively each state of the worklist to actors ActorEval (modulo the number of these actors) and then collects each of these results.
Extend SeqAAM class to reuse common code.
-
final
class
Parts[Item] extends Iterable[List[Item]]
Iterable class to iterates (without deterministic order) on nbPart "equals" parts on items from a sequence of sequences.
Iterable class to iterates (without deterministic order) on nbPart "equals" parts on items from a sequence of sequences. When totalSize is not divisible by nbPart, the firsts parts contain one item more than the lasts. When totalSize <= nbPart, the result is a sequence of totalSize List of one item.
totalSize and nbPart must be > 0 and totalSize must be equals to the total number of items in seqs
By example, Parts(List(Set(1, 2, 3), Set(4, 5, 6, 7, 8, 9, 10), Set(), Set(11, 12)), 12, 5) gives an iterator on List(3, 2, 1), List(6, 5, 4), List(8, 7), List(10, 9), List(12, 11) (with maybe a different order for items from the same set).
TODO: Possible better idea: The order is not important, so it may be possible to access concurrently to seqs and build parts in parallel.
-
final
class
PartsHybrid[Item] extends Iterable[List[Item]]
Iterable class to iterates (without deterministic order) on nbParts lists items from a sequence of sequences.
Iterable class to iterates (without deterministic order) on nbParts lists items from a sequence of sequences.
listSize and nbPart must be > 0 and listSize must be equals to the size of seqs
By example, PartsHybrid(List(Set(1, 2, 3), Set(4, 5, 6, 7, 8, 9, 10), Set(), Set(11, 12)), 5, 3) gives an iterator on List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10), List(11, 12) (with maybe a different order for items from the same set).
-
sealed
trait
Position extends MemoHashCode
This trait represents a position in a source file.
This trait represents a position in a source file. It's currently a wrapper around scala.util.parsing.input.Position, but will probably be updated in the future.
-
trait
Primitive[Addr, Abs] extends AnyRef
Each primitive has to implement this trait.
- abstract class Primitives[Addr, Abs] extends AnyRef
-
trait
RealLattice[F] extends LatticeElement[F]
A lattice for floats
-
trait
SExp extends MemoHashCode
Abstract grammar elements for S-expressions include some positional information.
Abstract grammar elements for S-expressions include some positional information. This serves two purposes: identify where the s-expression resides in the input file, and as tagging information for the abstract machine.
-
case class
SExpId(id: Identifier) extends SExp with Product with Serializable
An identifier, such as foo, bar, etc.
- class SExpLexer extends Lexical with SExpTokens
-
case class
SExpPair(car: SExp, cdr: SExp, pos: Position) extends SExp with Product with Serializable
An s-expression is made of pairs, e.g., (foo bar) is represented as the pair with identifier foo as car and another pair -- with identifier bar as car and value nil as cdr -- as cdr.
An s-expression is made of pairs, e.g., (foo bar) is represented as the pair with identifier foo as car and another pair -- with identifier bar as car and value nil as cdr -- as cdr. Pairs are pretty-printed when converted to string. i.e., (foo bar) is stringified as (foo bar) and not (foo . (bar . ()))
-
case class
SExpQuoted(content: SExp, pos: Position) extends SExp with Product with Serializable
A quoted element, such as 'foo, '(foo (bar)), etc.
- trait SExpTokens extends Tokens
-
case class
SExpValue(value: Value, pos: Position) extends SExp with Product with Serializable
A literal value, such as 1, "foo", 'foo, etc.
-
case class
SchemeAnd(exps: List[SchemeExp], pos: Position) extends SchemeExp with Product with Serializable
An and expression: (and exps...)
-
case class
SchemeBegin(exps: List[SchemeExp], pos: Position) extends SchemeExp with Product with Serializable
A begin clause: (begin body...)
-
case class
SchemeCase(key: SchemeExp, clauses: List[(List[SchemeValue], List[SchemeExp])], default: List[SchemeExp], pos: Position) extends SchemeExp with Product with Serializable
A case expression: (case key ((vals1...) body1...) ...
A case expression: (case key ((vals1...) body1...) ... (else default...))
-
case class
SchemeCond(clauses: List[(SchemeExp, List[SchemeExp])], pos: Position) extends SchemeExp with Product with Serializable
A cond expression: (cond (test1 body1...) ...)
-
case class
SchemeDefineFunction(name: Identifier, args: List[Identifier], body: List[SchemeExp], pos: Position) extends SchemeExp with Product with Serializable
A function definition: (define (name args...) body...)
-
case class
SchemeDefineVariable(name: Identifier, value: SchemeExp, pos: Position) extends SchemeExp with Product with Serializable
A variable definition: (define name value)
-
case class
SchemeDo(vars: List[(Identifier, SchemeExp, Option[SchemeExp])], test: SchemeExp, finals: List[SchemeExp], commands: List[SchemeExp], pos: Position) extends SchemeExp with Product with Serializable
Do notation: (do ((<variable1> <init1> <step1>) ...) (<test> <expression> ...) <command> ...)
-
trait
SchemeExp extends MemoHashCode
Abstract syntax of Scheme programs (probably far from complete)
-
case class
SchemeFuncall(f: SchemeExp, args: List[SchemeExp], pos: Position) extends SchemeExp with Product with Serializable
A function call: (f args...)
-
case class
SchemeIf(cond: SchemeExp, cons: SchemeExp, alt: SchemeExp, pos: Position) extends SchemeExp with Product with Serializable
An if statement: (if cond cons alt) If without alt clauses need to be encoded with an empty begin as alt clause
-
case class
SchemeLambda(args: List[Identifier], body: List[SchemeExp], pos: Position) extends SchemeExp with Product with Serializable
A lambda expression: (lambda (args...) body...) Not supported: "rest"-arguments, of the form (lambda arg body), or (lambda (arg1 .
A lambda expression: (lambda (args...) body...) Not supported: "rest"-arguments, of the form (lambda arg body), or (lambda (arg1 . args) body...)
- trait SchemeLattice extends AnyRef
-
case class
SchemeLet(bindings: List[(Identifier, SchemeExp)], body: List[SchemeExp], pos: Position) extends SchemeExp with Product with Serializable
Let-bindings: (let ((v1 e1) ...) body...)
-
case class
SchemeLetStar(bindings: List[(Identifier, SchemeExp)], body: List[SchemeExp], pos: Position) extends SchemeExp with Product with Serializable
Let*-bindings: (let* ((v1 e1) ...) body...)
-
case class
SchemeLetrec(bindings: List[(Identifier, SchemeExp)], body: List[SchemeExp], pos: Position) extends SchemeExp with Product with Serializable
Letrec-bindings: (letrec ((v1 e1) ...) body...)
-
case class
SchemeNamedLet(name: Identifier, bindings: List[(Identifier, SchemeExp)], body: List[SchemeExp], pos: Position) extends SchemeExp with Product with Serializable
Named-let: (let name ((v1 e1) ...) body...)
-
case class
SchemeOr(exps: List[SchemeExp], pos: Position) extends SchemeExp with Product with Serializable
An or expression: (or exps...)
-
class
SchemePrimitives[Addr, Abs] extends Primitives[Addr, Abs]
This is where we define Scheme primitives
-
case class
SchemeQuoted(quoted: SExp, pos: Position) extends SchemeExp with Product with Serializable
A quoted expression: '(foo (bar baz)) The quoted expression is *not* converted to a Scheme expression, and remains a simple s-expression, because that's exactly what it should be.
-
class
SchemeSemantics[V, Addr, Time] extends BaseSchemeSemantics[V, Addr, Time]
Extend base Scheme semantics with:
Extend base Scheme semantics with:
- atomic evaluation: parts of some constructs can be evaluated atomically without needing to introduce more states in the state graph. For example, (+ 1 1) can directly be evaluated to 2 without modifying the store. Also, to evaluate (+ 1 (f)), we can directly push the continuation and jump to the evaluation of (f), instead of evaluating +, and 1 in separate states.
-
case class
SchemeSet(variable: Identifier, value: SchemeExp, pos: Position) extends SchemeExp with Product with Serializable
A set! expression: (set! variable value)
-
case class
SchemeValue(value: Value, pos: Position) extends SchemeExp with Product with Serializable
A literal value (number, symbol, string, ...)
-
case class
SchemeVar(id: Identifier) extends SchemeExp with Product with Serializable
An identifier: name
- trait SemanticError extends MemoHashCode
-
abstract
class
Semantics[Exp, Abs, Addr, Time] extends AnyRef
This is where the interface of a language's semantics is defined.
This is where the interface of a language's semantics is defined. By defining the semantics of a language, you get an abstract abstract machine for free (but you might need to adapt existing lattices to support values from your language).
Semantics should be defined as small-step operational semantics. To define a semantics, you have to implement the Semantics trait. You'll need to specialize it on the type of expression of your language (e.g., ??? for ANF, ANFSemantics specializes on ANFExp). To do so, you need to define what actions should be taken when:
- Evaluating an expression e (stepEval) 2. Continuing evaluation when a value v has been reached (stepKont)
To have a simple overview of how semantics should be defined, look at the ANFSemantics.scala, as it defines semantics of ANF Scheme, a very lightweight language. A more complex definition resides in SchemeSemantics.scala.
-
class
SeqAAM[Exp, Abs, Addr, Time] extends EvalKontMachine[Exp, Abs, Addr, Time]
SeqAAM: Sequential AAM (with list)
SeqAAM: Sequential AAM (with list)
This is a reimplementation of the AAM class of Scala-AM written by Quentin Stiévenart. A fork of the original version of Scala-AM used is available here: https://bitbucket.org/OPiMedia/scala-am. The subsumption part has been removed. So this class corresponds in fact to the AAMNS (AAM No Subsumption) class of Scala-AM in this copy repository.
Compared to AAMNS of Scala-AM this class used Set Scala native data structures instead to specific WorkList and VisitedSet. The recursive loop has been replaced by a for loop.
The worklist is implemented by an immutable list of states.
This sequential machine (or the SeqAAMS and SeqAAMLS alternative) is the comparison point for the different version of parallel machines implemented in Scala-Par-AM.
The original description by Quentin Stiévenart: Implementation of a CESK machine following the AAM approach (Van Horn, David, and Matthew Might. "Abstracting abstract machines." ACM Sigplan Notices. Vol. 45. No. 9. ACM, 2010).
A difference with the paper is that we separate the continuation store (KontStore) from the value store (Store). That simplifies the implementation of both stores, and the only change it induces is that we are not able to support first-class continuation as easily (we don't support them at all, but they could be added).
Also, in the paper, a CESK state is made of 4 components: Control, Environment, Store, and Kontinuation. Here, we include the environment in the control component, and we distinguish "eval" states from "continuation" states. An eval state has an attached environment, as an expression needs to be evaluated within this environment, whereas a continuation state only contains the value reached.
-
class
SeqAAMLS[Exp, Abs, Addr, Time] extends SeqAAM[Exp, Abs, Addr, Time]
SeqAAMLS: Sequential AAM with List of Sets
SeqAAMLS: Sequential AAM with List of Sets
Version of SeqAAM with a different worklist implementation.
The worklist is implemented by an immutable list of sets of states.
Extend SeqAAM class to reuse common code.
-
class
SeqAAMLSH[Exp, Abs, Addr, Time] extends SeqAAM[Exp, Abs, Addr, Time]
SeqAAMLSH: SeqAAMLS with direct identification of Halted states
SeqAAMLSH: SeqAAMLS with direct identification of Halted states
Version of SeqAAMLS that includes to the worklist only the not halted states. Halted states are directly identified in the set of successors.
The worklist is implemented by an immutable list of sets of states.
Extend SeqAAM class to reuse common code.
-
class
SeqAAMS[Exp, Abs, Addr, Time] extends SeqAAM[Exp, Abs, Addr, Time]
SeqAAMS: Sequential AAM with Set
SeqAAMS: Sequential AAM with Set
Version of SeqAAM with a different worklist implementation.
The worklist is implemented by an immutable set of states.
Extend SeqAAM class to reuse common code.
-
case class
SomePosition(p: scala.util.parsing.input.Position) extends Position with Product with Serializable
The actual wrapper
- abstract class Store[Addr, Abs] extends MemoHashCode
-
trait
StringLattice[S] extends LatticeElement[S]
A lattice for strings
-
trait
SymbolLattice[Sym] extends LatticeElement[Sym]
A lattice for symbols
- class Timeout extends AnyRef
- trait Timestamp[T] extends AnyRef
- trait TimestampWrapper extends AnyRef
- case class TimestampedKontStore[KontAddr](content: Map[KontAddr, Set[Kont[KontAddr]]], timestamp: Int)(implicit evidence$4: KontAddress[KontAddr]) extends KontStore[KontAddr] with Product with Serializable
- case class TypeError(name: String, operand: String, expected: String, got: String) extends SemanticError with Product with Serializable
- case class UnboundAddress(addr: String) extends SemanticError with Product with Serializable
- case class UnboundVariable(name: Identifier) extends SemanticError with Product with Serializable
- case class UserError(reason: String, pos: Position) extends SemanticError with Product with Serializable
-
sealed abstract
class
Value extends AnyRef
S-expressions and related values
- case class ValueBoolean(value: Boolean) extends Value with Product with Serializable
- case class ValueCharacter(value: Char) extends Value with Product with Serializable
- case class ValueInteger(value: Int) extends Value with Product with Serializable
- case class ValueReal(value: Double) extends Value with Product with Serializable
- case class ValueString(value: String) extends Value with Product with Serializable
- case class ValueSymbol(sym: String) extends Value with Product with Serializable
- case class VariadicArityError(name: String, min: Int, got: Int) extends SemanticError with Product with Serializable
-
final
class
ZipRemainsIterator[Item1, Item2] extends Iterator[(Item1, Item2)]
Iterator class to iterates on results equal to the zip(seq1, seq2) function and then get the remains of the two initial sequences.
Iterator class to iterates on results equal to the zip(seq1, seq2) function and then get the remains of the two initial sequences.
https://www.scala-lang.org/api/current/scala/collection/Iterator.html#zip[B](that:scala.collection.IterableOnce[B]):Iterator[(A,B)]
-
final
class
ZipRemainsIterator2[Item1, Item2] extends Iterator[(Item1, Item2)]
Similar to ZipRemainsIterator but the second sequence is a sequence of non empty sequences and the iteration is done on items of seq1 and items of inner sequences of seqSeq2.
Value Members
- object Address
- object BoolLattice
- object Cardinality
- object CardinalityInf extends Cardinality with Product with Serializable
- object CardinalityPrimitiveLikeInf
- object CardinalityPrimitiveLikeNumber
- object CharLattice
- object ClassicalAddress extends AddressWrapper
- object Colors
-
object
Concrete
Some implementations of these abstract domains
- object ConcreteBooleanEfficient
-
object
Configuration
Helpers to configure machine
- object ConstantPropagation
- object Count
- object CountInfinity extends Count with Product with Serializable
- object CountOne extends Count with Product with Serializable
- object Effect
- object EffectKind
- object Environment
- object Expression
- object Graph
- object GraphDOTOutput extends GraphOutput
- object GraphOutputNode
- object IntLattice
- object IsSchemeLattice extends Serializable
- object JoinLattice extends Serializable
- object KontStore
- object LatticeElement
-
object
Main extends App
Scala-Par-AM is a modified version of Scala-AM with the goal to study the parallelization of abstract interpretation, focused on analysis of Scheme programs.
Scala-Par-AM is a modified version of Scala-AM with the goal to study the parallelization of abstract interpretation, focused on analysis of Scheme programs. Some unused parts of Scala-AM have been removed. The essential parts are in the machine/ sub-directory.
This main program executes some abstract machines on some Scheme programs depending of some parameters and print results in TSV format (data separated by tabulation).
Run with
--helpcommand line parameter to show all options:$ java -jar scala-par-am.jar --help
Or directly with the shell script that also set some JVM configurations:
$ ./scala-par-am.sh --help
This example:
$ ./scala-par-am.sh --files "Scheme-examples/OPi/factorial*.scm" --machines SeqAAMLS,ParAAMLSAPart,ParAAMCPart --processes 1,4,2
runs on files that match the "Scheme-examples/OPi/factorial*.scm" path with machine SeqAAMLS on 1 process, with machine ParAAMLSAPart on 4 and 2 processes, and with machine ParAAMCPart with 1, 4 and 2 processes.scala-par-am.jar can be downloaded directly https://bitbucket.org/OPiMedia/scala-par-am/downloads/
scala-am.jar must be accessible in the classpath to use oldAAM machine. Download it if necessary: https://bitbucket.org/OPiMedia/scala-am/downloads/
Depending of command line parameters, for each lattice specified, for each bound, for each address, for each file Scheme program, for default step and/or step with filter, for each machine and for each number of processes this program do the following:
1. The input Scheme program is parsed. It is done by:
- Parsing the file as a list of s-expressions (exp/SExp.scala, exp/SExpParser.scala)
- Compiling these s-expressions into Scheme expressions (exp/scheme/Scheme.scala)
2. To run the program, we need an abstract machine and some semantics. Semantics definitions have to implement the Semantics interface (semantics/Semantics.scala).
3. Once the abstract machine is created and we have a semantics for the program we want to analyze, the abstract machine can perform its evaluation, relying on methods of the semantics class to know how to evaluate expressions. The abstract machine only deals with which states to evaluate in which order, where to store values, where to store continuations, how to push and pop continuations, etc. The semantics encode what to do when encountering a program construct. For example, the semantics can tell what to evaluate next, that a continuation needs to be pushed, or that a variable needs to be updated. The abstract machine will then respectively evaluate the expression needed, push the continuation, or update the variable.
Multiple abstract machine implementations are available, defined in the machine/ directory. Every abstract machine implementation has to implement the AbstractMachine interface (machine/AbstractMachine.scala).
List of all available machines:
- oldAAM: to call AAMNS (AAM No Subsumption) of Scala-AM https://bitbucket.org/OPiMedia/scala-am
- SeqAAM: sequential machine where the worklist implemented with a list of states
- SeqAAMS: sequential machine where the worklist implemented with a set of states
- SeqAAMLS: sequential machine where the worklist implemented with a list of sets of states
- SeqAAMLSH: SeqAAMLS that includes to the worklist only the not halted states
- ParAAMLSAState: ParAAM-L-SA-state for Parallel AAM - Loop - SenderAggregator - state
- ParAAMLSASet: ParAAM-L-SA-set for Parallel AAM - Loop - SenderAggregator - set
- ParAAMLSAPart: ParAAM-L-SA-part for Parallel AAM - Loop - SenderAggregator - part
- ParAAMCSState: ParAAM-C-S-state for Parallel AAM - Concurrent - Sender - state
- ParAAMCSSet: ParAAM-C-S-set for Parallel AAM - Concurrent - Sender - set
- ParAAMCSPart: ParAAM-C-S-part for Parallel AAM - Concurrent - Sender - part
- ParAAMCState: ParAAM-C-state for Parallel AAM - Concurrent - state
- ParAAMCSet: ParAAM-C-set for Parallel AAM - Concurrent - set
- ParAAMCPart: ParAAM-C-part for Parallel AAM - Concurrent - part
- ParAAMCHybrid: ParAAM-C-hybrid
- ParAAMCSetH: ParAAM-C-set-halt
- ParAAMCPartH: ParAAM-C-part-halt
- ParAAMCHybridH: ParAAM-C-hybrid-halt
The abstract machine also uses a lattice to represent values. Lattices should implement the JoinLattice trait that can be found in lattice/JoinLattice.scala, which provides the basic features of a lattice.
- The repository of Scala-Par-AM: https://bitbucket.org/OPiMedia/scala-par-am
- ScalaDoc of this code: http://www.opimedia.be/DS/online-documentations/Scala-Par-AM/html/be/opimedia/scala_par_am/Main$.html
- The repository of the starting fork of Scala-AM: https://bitbucket.org/OPiMedia/scala-am
- The original repository of Scala-AM: https://github.com/acieroid/scala-am
- Master thesis about this project: https://bitbucket.org/OPiMedia/efficient-parallel-abstract-interpreter-in-scala/
Source https://bitbucket.org/OPiMedia/scala-par-am/src/master/scala-par-am/src/main/scala/Main.scala
Authors:
Olivier Pirson
Quentin Stiévenart (for the original Scala-AM that composes the biggest part of this project)
- Version
June 18, 2020
- object MayFail
- object Parts
- object PartsHybrid
- object Position
- object ReadEffect extends EffectKind with Product with Serializable
- object RealLattice
- object SExpList
- object SExpParser extends TokenParsers
- object Scheme
-
object
SchemeCompiler
Object that provides a method to compile an s-expression into a Scheme expression
- object SchemeExp
- object SchemeLattices
- object SchemeOps
-
object
SchemeUndefiner
Remove defines from a Scheme expression, replacing them by let bindings.
Remove defines from a Scheme expression, replacing them by let bindings. For example: (define foo 1) (define (f x) x) (f foo) Will be converted to: (letrec ((foo 1) (f (lambda (x) x))) (f foo)) Which is semantically equivalent with respect to the end result
- object Store
- object StringLattice
- object SymbolLattice
- object Timeout
- object Timestamp
- object Type
- object Util
- object ValueNil extends Value
- object ValueSensitiveAddress extends AddressWrapper
- object WriteEffect extends EffectKind with Product with Serializable
- object ZeroCFA extends TimestampWrapper
- object ZipRemainsIterator
- object ZipRemainsIterator2