Safe Haskell	None
Language	Haskell98

ExCF

Contents

Types
Evaluation functions

Description

This module calculates the exact control graph by evaluating a CPSScheme
program, following the definitions in Olin Shivers' "Control-Flow
Analysis of Higher-Order Languages".

Synopsis

Types

type Closure = (Lambda, BEnv) Source

A closure is a lambda expression bound to a binding environment

type Contour = Integer Source

A contour is an identifier for the contours (or dynamic frames) generated at each call of a lambda expression

type BEnv = Label :⇀ Contour Source

A binding environment maps the labels of Lambda and Let bindings to the innermost contour generated for these expressions

type VEnv = (Var :× Contour) :⇀ D Source

A variable environment maps variable names together with a contour to a value. The second parameter is required to allow for different, shadowed bindings of the same variable to coexist.

data D Source

A semantical value can either be

Constructors

DI Const	A constant
DC Closure	A closed lambda expression
DP Prim	A primitive value
Stop	The special continuation passed to the outermost lambda of a program

Instances

Show D Source

type CCtxt = Label :× BEnv Source

The origin of an edge in the control graph is a call position bundled with the binding environment at that point.

type CCache = CCtxt :⇀ D Source

The resulting control flow graph has edges from call sites (annotated by the current binding environment) to functions (e.g. lambdas with closure, primitive operations, or Stop)

type Ans = CCache Source

The result of evaluating a program is the control flow graph.

Evaluation functions

evalCPS :: Prog -> Ans Source

evalCPS evaluates a whole program, by initializing the envirnoments and passing the Stop continuation to the outermost lambda

evalV :: Val -> BEnv -> VEnv -> D Source

evalC (called A by Shivers) evaluates a syntactical value to a semantical piece of data.

evalF :: D -> [D] -> VEnv -> Contour -> Ans Source

evalF evaluates a function call, distinguishing between lambda expressions, primitive operations and the special Stop continuation. It calles evalC for the function bodies.

evalC :: Call -> BEnv -> VEnv -> Contour -> Ans Source

evalC evaluates the body of a function, which can either be an application (which is then evaluated using evalF) or a Let statement.