Compilation of Id^{−}: A Subset of Id

Zena M. Ariola Aiken Computational Laboratory

Harvard University

Arvind Laboratory for Computer Science Massachusetts Institute of Technology

November 1, 1990

Abstract

Compilation of Id, a higher-order non-strict functional language augmented with Istructures, is described in terms of two languages. The first language is called Kid, which is a Kernel language for Id. Kid is further translated into a language where all Kid data structures and functions are represented using only one data structure. This second language is called P-TAC for Parallel Three Address Code. The operational semantics of both Kid and P-TAC are presented in terms of two contextual reduction systems. Formalization of many commonly known optimizations is also presented in the contextual reduction framework.

Keywords and phrases: Term Rewriting Systems, Contextual Reduction Systems, Dataflow, Functional Languages, I-structures, Compiler Optimizations.

1 Introduction

2.53in

Figure 1: Compilation scheme

We describe the compilation of Id^{−}, a subset of the Id language, in terms of successive translations into different languages. Each of the successive languages has a precise operational semantics, which is given in terms of rewrite rules. The compilation scheme is shown in Figure 1. Id^{−} does not contain the following features of Id:

abstract types and algebraic types except lists;

overloading;

mutable structures.

Id^{−} is first parsed into de-sugared Id^{−}, where enough parentheses are inserted to make operator associativity and precedence irrelevant. Desugared Id^{−} also does not contain patterns in function definitions. During the de-sugaring phase list-comprehensions and array-comprehensions are transformed into nested loops. We will informally describe this phase in the next Section.

In the next phase de-sugared Id^{−} is translated into Kid, the Kernel language for Id. Kid is a subset of Id except for the notion of multiple values which have been inspired by dataflow graphs. Essentially a Kid program contains only primitive patterns and simple expressions. The Kid syntax and operational semantics are given in Section 3. The translation from de-sugared Id^{−} to Kid, including the compilation of complex patterns into primitive patterns, is described in Section 4.

Kid serves several purposes. Since Id is too complex to be given direct operational semantics, it is preferable first to give a translation of Id into a smaller language such as Kid. Thus, Id is defined indirectly in terms of the rewrite rule semantics of Kid. Kid is also the intermediate language in which a large number of architecture independent compiler optimizations are performed. These optimizations are described in Section 5. We think that many other types of analyses such as Milner style type checking, or abstract interpretation for storage reclamation should be performed at the Kid level. These analyses are not described in this document.

An implementation method that is preferred by many researchers eliminates explicit environments containing the value of free variables of a function. This requires applying a program transformation known as lambda-lifting. Lambda-lifting involves two steps: first, all nested function definitions (λ-expressions) of a Kid program are “closed” by turning their free variables into parameters. In the second step, all closed definitions are lifted to the top level. Lambdalifting should be done after optimizations have been performed on Kid programs. There are many algorithms for doing lambda-lifting and we do not describe any of them in this document.

Interested reader is referred to Johnsson’s paper [7].

The next step is to translate a lambda-lifted Kid program into P-TAC [1], which is a much smaller language than Kid. This translation calls for choosing a machine representation for each type of Kid value and thus, involves many low level efficiency issues. P-TAC and its operational semantics are given in Section 6. A translation from Kid into P-TAC is given in Section 7. We end the document by showing in Section 8 how a P-TAC program is extended with Signals [2] which are needed to detect termination and for resource management.

Our compiling approach allows the formalization of questions related to correctness [1]. For example, it will make sense to talk about the correctness of lambda-lifting, or the correctness of the translation from Kid to P-TAC. Moreover, since there exists an independent operational semantics of Id^{−} in terms of a even smaller subset of kernel Id [5], it may be possible to prove the correctness of the translation between de-sugared Id^{−} and Kid. Another advantage of our approach is that we are able to delay the introduction of concepts tied to specific machines or even to the dataflow computation model until we actually generate machine code. However, in this document we do not go below the P-TAC level.

2 Desugared Id^{−}

The syntax of de-sugared Id^{−} is described in Figure 2. As can be seen from the grammar, desugared Id is fully parenthesized and thus has no operator precedence. Thus, an Id expression like

            (f x) : map f xs

becomes

            ((f x):((map f) xs))

Id has curried versions of infix binary operators which are written by enclosing the operator in parenthesis. Thus, (+) represents the curried +, and it makes sense to write ((+) 2) in Id. In de-sugared Id^{−} we treat the curried version of an operator as a constant, which has a standard function definition associated with it. For the sake of symmetry we have also included curried versions of all unary operators in de-sugared Id^{−}.

UOP ∈ Unary Operator
BOP ∈ Binary Operator
E  ∈ Expression
P  ∈ Pattern
V ariable ::= x | y | z | ⋯ | a | b | ⋯ | f | ⋯ | x_{1} | ⋯ | F | G | ⋯
Constant ::= Integer | Boolean | () | Nil | (Not) | ⋯ | (+) | (−) | ⋯ | Make nD array
UOP  ::= Negate | Not | nD Bounds | I nD array | Open cons
BOP  ::= + | − | ∗ | ⋯ | == | Eq? | < | ⋯ | And | :
E  ::= V ariable | Next V ariable | Constant

| (UOP E) | (E BOP E) | (E E) | E[E] | E.cons 1 | E.cons 2

| (E, E) | (E, E, E) | ⋯

| (If E then E else E) | {Case E of Clause [ | Clause]^{∗} }

| {While E do [Statement; ]^{∗} Finally E}

| {For V ariable ← E to E step E do [Statement; ]^{∗} Finally E} | \{Fun [V ariables]^{∗} = E\} | \{\underline{Fun} [V ariables]^{∗} = E\}

| Block
Block  ::= {[Statement; ]^{∗} In E}
Statement ::= Binding | Command
Binding ::= P = E
Command ::= E[E] = E | E.cons 1 = E | E.cons 2 = E
Clause  ::= P = E
P  ::= Nil | V ariable | Next V ariable | (P, P) | (P, P, P) | ⋯ | (P : P)
P rogram ::= Block

Figure 2: Grammar of de-sugared Id^{−}

During the de-sugaring phase multi-clause functions, are turned into equivalent case expressions, as shown in the example below

           Def map f Nil  = Nil
            |  map f x:xs = (f x) : map f xs;

becomes

           Def map  t1 t2 = { Case (t1, t2)   of
                                |  (f,  Nil)  = Nil
                                |  (f,  x:xs) = (f x) : map f xs }

where t1 and t2 are new variables. Furthermore, all function definitions are turned into λ - expressions.

          map =  { Fun t1 t2 = { Case (t1, t2)   of
                                   |  (f,  Nil)  = Nil
                                   |  (f,  x:xs) = (f x) : map f xs } }

If the Id function is defined as substitutable (Defsubst) then the corresponding λ-expression (\underline{Fun}) is underlined. The “underlined” λ-expressions are then expanded in line during optimizations (see Section 5 ).

The most complex part of the de-sugaring phase is the transformation of comprehensions into loops. This is described in detail in [3]. Here we only illustrate the idea using the following example:

           {: e || x <- xs ; y <- ys}

A typical translation of this list-comprehension is given in terms of nested map-list operations followed by a list flattening operation. In Id we make use of “open lists” to generate a tail recursive program. Basically, in the following program, a open list (signified by h in the inner loop) is generated for each element of xs and then these open lists are “glued” together in the outer loop.

           { h1  =  Open_cons ();
             hn  = { For x <- xs do
                      Next h1 =
                         { Case ys of
                            | Nil = h1
                            | y:yss =
                                 { h =  Open_cons ();
                                   h1.cons_2 = h.cons_2;
                                  In { For y <- ys do
                                         t  = Open_cons ();
                                         t.cons_1 = e;
                                         h.cons_2 = t;
                                         Next h = t;
                                      Finally h }}};
                     Finally h1 };
             hn.cons_2 = Nil;
            In h1.cons_2 }

The above translation is correct if we treat open lists and lists as the same type. However, there are several subtle issues regarding type checking that are still not resolved.

3 Kid : The Kernel Id Language

3.1 Kid

Kid has only uncurried operators and no complex expressions. A major subset of Kid is simply the λ-calculus with constants and let blocks. However, unlike other functional languages, let - blocks play a fundamental role in the operational semantics of Kid. The syntax of Kid is given in Figure 3. Every expression, except a block or λ-expression, consists of a combinator followed by the corresponding number of arguments. The translation from Id^{−} to Kid also has the flavor of turning an applicative TRS into a functional one.

An important feature of Kid is the concept of multiple values. The expression

x, y = {_{2} a = ⋯; b = ⋯; In a, b}

is a well-formed-expression, where “x, y” indicates multiple variables, not to be confused with a 2-tuple. The 2 after the curly brace indicates that two values are to be returned by this block

MV  ∈ Multiple Variable
SE  ∈ Simple Expression
PF i_{m}  ∈ Primitive Function with i arguments and m outputs
Ap E_{m}  ∈ Applicative Expression with m outputs
Case E_{m} ∈ Case Expression with m outputs
Loop E_{m} ∈ Loop Expression with m outputs
lambda E ∈ Lambda Expression
E m  ∈ Expression with m outputs
V ariable ::= x | y | z | ⋯ | a | b | ⋯ | f | ⋯ | x_{1} | ⋯
MV_{m}  ::= \underbrace{V ariable, ⋯, V ariable}_{m}
Constant ::= Integer | Boolean | () | (Not) | ⋯ | (+) | (−) | ⋯

| Nil | Make nD array | Error | ⊤

SE  ::= V ariable | Constant
SE_{m}  ::= \underbrace{SE, ⋯, SE}_{m} | SE, SE_{m−1} | SE, SE, SE_{m−2} | ⋯
PF 1_{1}  ::= Negate | Not | nD Bounds | I nD array | Open cons | Cons 1 | Cons 2
PF 1_{m}  ::= Detuplem
PF 2_{1}  ::= + | − | ∗ | ⋯ | Equal? | Eq? | < | ⋯ | And | Cons | Apply

| P nD select | Make tuple2

PF N_{1}  ::= Make tuplen
Ap E_{m}  ::= Apn,m (SE_{n+1})
Case E_{m} ::= Bool casem (SE, E_{m}, E_{m}) | List casem (SE, E_{m}, E_{m})
Loop E_{m} ::= WLoopm (SE_{m+3}) | FLoopm (SE_{m+4})
lambda E ::= λn,m (MV_{n}) . (E_{m}) | \underline{λn,m} (MV_{n}) . (E_{m})
E_{1}  ::= SE_{1} | PF 1_{1} (SE) | PF 2_{1} (SE_{2}) | PF N_{1} (SE_{n}) | Ap E_{1}

| Case E_{1} | Loop E_{1} | lambda E | Block_{1}

E_{m}  ::= SE_{m} | P F 1_{m} (SE) | Ap E_{m} | Case E_{m} | Loop E_{m} | Block_{m}
Block_{m}  ::= {m [Statement; ]^{∗} In SE_{m}}
Statement ::= Binding | Command
Binding ::= MV_{m} = E_{m}
Command ::= P nD store (SE, SE, SE) | Cons store 1 (SE, SE)

| Cons store 2 (SE, SE) | Store error | ⊤_{s}

P rogram ::= Block_{1}

Figure 3: Grammar of Kid expression. Multiple values avoid packaging values in a data structure, and they are useful in expressing some optimizations. Thus, in Kid a binding has the form MV = E, where MV stands for multiple variable. Suppose we have m variables on the left-hand-side, then the expression E on the right-hand-side must return m values. In the sequel we capture the number of values that an expression produces by subscripting the corresponding syntactic category. Thus, to express the above binding we will write MV_{m} = E_{m}. Note that the combinator “Apply” appears as a PF 2_{1} in the grammar because all Id^{−} procedures return only one result. We also use subscripted combinators to express a family of combinators. For example, Make tuplen stands for Make tuple2, Make tuple3, etc. . Subscripts in a combinator do not necessarily represent the number of values to be returned by the application of the combinator.

We will use the following conventions to minimize the use of subscripts.

{  is the same as {1
Bool case is the same as Bool case1
List case is the same as List case1
WLoop  is the same as WLoop1
FLoop  is the same as FLoop1
Apn  is the same as Apn,1
λn  is the same as λn,1

3.2 The Rewrite Rules of Kid

We now present a set of rewrite rules, R_{Kid}, to define the operational semantics for Kid. R_{Kid} is a Contextual Rewrite System described in [8]. We assume that a primitive function is only applied to arguments of appropriate types, i.e., the type checking has been done statically.

All the variables that appear on the left-hand-side of the rules are meta-variables that range over appropriate syntactic categories. By convention, we use capital letters for meta-variables and small letters for Kid variables. All variables that appear on the right-hand-side of the rules are either meta-variables or “new” Kid variables. We will make use of the following convention regarding meta-variables:

\begin{aligned}X_{i}, Z_{i}, Y_{i}, F_{i}, P, B, U, D & ∈ & V ariable and Constant \\ C & ∈ & Constant \\ S_{i}, SS_{i} & ∈ & Statement \\ S, S′ & ∈ & [Statement]^{∗} \\ E_{i} & ∈ & Expression \end{aligned}

It should be noted that in contextual rewriting, the statement above the line must be in the context (lexical scope) of the expression below the line. This raises some subtle free variable capture possibilities in case of function application. To avoid these problems, we will assume that all bound variables in a Kid program have been assigned unique names to begin with. When the possibility of free variable capture arises during rewriting, we will rename all bound variables of an expression to completely new variables explicitly, by applying the function RB to the expression. For example,

RB [[{x = + (a, 1) In x}]] = {x′ = + (a, 1) In x′}

The notation E [Y/X] means the substitution of Y for X in E. Usually this implies avoiding capture of free variables. However, due to our assumption that all variables occurring in a term to be reduced are unique, E [Y/X] will simply indicate naive substitution, that is, substitution where no danger of free variable capture exists and where X can be replaced by Y without regards to scope. Moreover, we will use the notation X_{n,m}^{→} to stand for (X_{n}, ⋯, X_{m}), X_{m}^{→} for X_{1,m}^{→}, and

E [Y_{n}^{→} / X_{n}^{→}] for E [Y_{1}/X_{1}, ⋯, Y_{n}/X_{n}], which is the same as (⋯ ((E [Y_{1}/X_{1}]) [Y_{2}/X_{2}]) ⋯) [Y_{n}/X_{n}]).

In the following, \underline{n} represents a numeral.

δ rules

+ (\underline{m}, \underline{n})  − ; − ; →_{δ} \underline{+(m, n)}
⋮
Equal? (\underline{n}, \underline{n}) − ; − ; →_{δ} True
Equal? (\underline{m}, \underline{n}) − ; − ; →_{δ} False  (if m ≠ n)

Case rules

Bool casem (True, E_{1}, E_{2}) − ; − ; → E_{1}
Bool casem (False, E_{1}, E_{2}) − ; − ; → E_{2}

\frac{X = Nil}{List casem (X, E_{1}, E_{2}) − ; − ; → E_{1}}

\frac{X = Open cons ()}{List casem (X, E_{1}, E_{2}) − ; − ; → E_{2}}

Arity Detection rule

\frac{F = λ_{n}(Z_{n}^{→}).E}{Apply (F, X) − ; − ; → Apply1 (F, \underline{n}, X)}

\frac{F = λ(Z).E}{Apply (F, X) − ; − ; → Ap (F, X)}

\frac{F_{i} = Applyi (F, \underline{n}, X_{i}) i < (n−1)}{Apply (F_{i}, X_{i+1}^{→}) − ; − ; → Applyi+1 (F, \underline{n}, X_{i+1}^{→})}

\frac{F_{n−1} = Applyn−1 (F, \underline{n}, X_{n−1}^{→}) i = (n−1)}{Apply (F_{n−1}, X_{n}^{→}) − ; − ; → Ap (F, X_{n}^{→})}

Similar rules apply for \underline{λn}.

Application rule

\frac{F = λn,m (Z_{n}^{→}) . (E)}{Apn,m (F, X_{n}^{→}) − ; − ; → (RB[[E]]) [X_{n}^{→} / Z_{n}^{→}]}

A similar rule applies for \underline{λn,m}.

Loop rules

WLoopn (P, B, X_{n}^{→}, True) − ; − ; → {n t_{n}^{→} = Apn,n (B, X_{n}^{→}); t_{p} = Apn (P, t_{n}^{→}); t′_{n}^{→} = WLoopn (P, B, t_{n}^{→}, t_{p}) In t′_{n}^{→}}

WLoopn (P, B, X_{n}^{→}, False) − ; − ; → X_{n}^{→}

In the following two rules we assume that the index variable is the first variable in X_{n}^{→}.

FLoopn (U, D, B, X_{n}^{→}, True) − ; − ; → {n t_{2,n}^{→} = Apn,n−1 (B, X_{n}^{→}); t_{1} = + (X_{1}, D); t_{p} = < (t_{1}, U); t′_{n}^{→} = FLoopn (U, D, B, t_{n}^{→}, t_{p}) In t′_{n}^{→}}

FLoopn (U, D, B, X_{n}^{→}, False) − ; − ; → X_{n}^{→}

Tuple rule

\frac{X = Make tuplen (X_{n}^{→})}{Detuplen (X) − ; − ; → X_{n}^{→}}

List rules

Cons (X, Y) − ; − ; → \{ \begin{matrix}t & = & Open cons (); \\ Cons store 1 (t, X); \\ Cons store 2 (t, Y) \\ In t\} \end{matrix}

\frac{Cons store 1 (X, Y)}{Cons 1 (X) − ; − ; → Y}

\frac{Cons store 2 (X, Y)}{Cons 2 (X) − ; − ; → Y}

\frac{Cons store 1 (X, Y)}{Cons store 1 (X, Y′) − ; − ; → ⊤_{s}}

\frac{Cons store 2 (X, Y)}{Cons store 2 (X, Y′) − ; − ; → ⊤_{s}}

Array rules

\frac{X = I nD array (X_{b})}{nD Bounds (X) − ; − ; → X_{b}} \frac{P nD store (X, Y, Z)}{P nD select (X, Y) − ; − ; → Z}

\frac{P nD store (X, Y, Z)}{P nD store (X, Y, Z′) − ; − ; → ⊤_{s}}

Multivariable rule

X_{n}^{→} = Y_{n}^{→} − ; − ; → (X_{1} = Y_{1}; ⋯ X_{n} = Y_{n})

Substitution rules

\frac{X = Y}{X − ; − ; → Y} ; \frac{X = C}{X − ; − ; → C}

Block Flattening rule

{m X_{n}^{→} = {n SS_{1}; SS_{2}; ⋯  {m X_{n}^{→} = Y_{n}^{→};
In Y_{n}^{→}}  − ; − ; →  SS_{1}; SS_{2}; ⋯
S_{1}; ⋯ S_{n}  S_{1}; ⋯ S_{n}
In Z_{m}^{→}}  In Z_{m}^{→}}

Propagation of ⊤

\begin{matrix}\{m X = ⊤; S_{1}; ⋯ S_{n} In Z_{m}^{→} \} & − ; − ; → & ⊤ \\ \{m ⊤_{s}; S_{1}; ⋯ S_{n} In Z_{m}^{→} \} & − ; − ; → & ⊤ \end{matrix}

4 Translating Desugared Id^{−} into Kid

4.1 Simplification of Expressions

We give the translation in terms of the following functions:

Translate Expression, TE : Id^{−} Expression ⟶ Kid Expression
Translate Statement, TS : Id^{−} Statement ⟶ list (Kid Statement)
Translate Binding,  TB : Id^{−} Binding  ⟶ list (Kid Binding)
Translate Operator, TO : Id^{−} Operator ⟶ Kid Operator
Pattern Matching,  PM : Case expression ⟶ Kid Expression

The exact syntax of Case expression is given in Section 4.3.

We will write TE[[E_{1}]] = E_{2}, where the expression enclosed in double brackets represents an Id^{−} expression and E_{2} is the corresponding Kid expression. The whole translation is given in terms of syntactic categories. The proper way of reading a translation function such as

“TE[[(UOP E_{1})]] = {t_{1} = TE[[E_{1}]]; t = TO[[UOP]] (t_{1}); In t} ” is that “TE” when applied to a unary

expression in Id^{−} produces the Kid expression on the right-hand-side.

Throughout, the emphasis is on clarity of Id^{−} to Kid translation rather than its efficiency. We will use the same conventions introduced in Section 3.2, with the addition of meta-variable P_{i} that ranges over Patterns. As before X_{n}^{→} indicates multiple meta-variables. The lower case variables, such as t_{i}, x_{i}, that appear in the translated expression represent new Kid variables. The translation procedure given below does not require lexical scope analysis for variables. However, after the translation is complete a procedure to make all bound variables unique has to be applied before any rewriting can be done.

A common situation in the translation procedure is the need to replace variable X by a new variable t in some Id expression E. This idea can be expressed by addding another block around E as in { X = t; t′ = E; In t′ }. To avoid clutter, we will write E [t/X]_{B} as a shortand for { X = t; t′ = E; In t′ }. (As an aside, it should be noted that since we do not assume unicity of variables during translation, we can not use the notion for naive substitution. Conversely, the use of E [X_{n}^{→} / Z_{n}^{→}]_{B} in the application rewrite rule, given earlier, would have been incorrect, because it could lead to duplication of bound variables Z_{n}^{→}, while expanding two different applications of the same function).

TE: Id^{−} Expression ⟶ Kid Expression

TE[[X]] = X

TE[[Next X]] = next(X)

Where “next” is a function on identifiers that keeps the association between a variable and its corresponding nextified version during the loop translation phase. After the translation is complete, next(X) is treated like an ordinary identifier which is different from X.

TE[[C]] = C

TE[[(UOP E)]] = \{ \begin{matrix}t_{1} & = & TE[[E]]; \\ t & = & TO[[UOP]] (t_{1}) \\ & In t\} \end{matrix}

TE[[(E_{1} BOP E_{2})]] = \{ \begin{matrix}t_{1} & = & TE[[E_{1}]]; \\ t_{2} & = & TE[[E_{2}]]; \\ t & = & TO[[BOP]] (t_{1}, t_{2}) \\ & In t\} \end{matrix}

TE[[(E_{1} E_{2})]] = \{ \begin{matrix}t_{1} & = & TE[[E_{1}]]; \\ t_{2} & = & TE[[E_{2}]]; \\ t & = & Apply (t_{1}, t_{2}) \\ & In t\} \end{matrix}

TE[[E_{1}[E_{2}]]] = \{ \begin{matrix}t_{1} & = & TE[[E_{1}]]; \\ t_{2} & = & TE[[E_{2}]]; \\ t & = & Ap2 (Select, t_{1}, t_{2}) \\ & In t\} \end{matrix}

where Select is a standard function definition in Kid (see Section 4.2).

TE[[E.cons 1]] = \{ \begin{matrix}t_{1} & = & TE[[E]]; \\ t & = & List case (t_{1}, Error, Cons 1 (t_{1})) \\ & In t\} \end{matrix}

Similarly for E.cons 2.

TE[[(E_{1}, ⋯, E_{n})]] = { t_{1} = TE[[E_{1}]]; ⋮ t_{n} = TE[[E_{n}]]; t = Make tuplen (t_{n}^{→}) In t}

TE[[(If E_{1} then E_{2} else E_{3})]] = \{ \begin{matrix}t_{1} & = & TE[[E_{1}]]; \\ t & = & Bool case (t_{1}, TE[[E_{2}]], TE[[E_{3}]]) \\ & In t\} \end{matrix}

TE[[\{ Case E of ; | P_{1} = E_{1} ; ⋮ ; | P_{n} = E_{n} \}]] = \{ \begin{matrix}t_{1} & = & TE[[E]]; \\ t & = & PM[[\{ Case (t_{1}) of | P_{1} = TE[[E_{1}]] ⋮ | P_{n} = TE[[E_{n}]] \}]] \\ & In t\} \end{matrix}

Where PM is described in the Section 4.3.

TE[[{ While E do S_{1}; ⋮ S_{n}; Finally E_{f} }]] = TSLE[[{ While TE[[E]] do TS[[S_{1}]]; ⋮ TS[[S_{n}]]; Finally TE[[E_{f}]] }]]

Note that TE uses an auxiliary function TSLE which stands for “Translate simple loop expression”. However this is only done for clarity of exposition. In fact, we are slightly abusing our notation because the expression inside TSLE[[ ]] is a mixture of Id^{−} and Kid syntax.

TSLE[[\{ While E do next(X_{1}) = E_{1}; ⋮ next(X_{n}) = E_{n}; Y_{1} = E_{y_{1}}; ⋮ Finally E_{f} \}]] = \{ \begin{matrix}p & = & \underline{λ_{n}} (X_{n}^{→}) . (E); \\ b & = & \underline{λ_{n,n}} (X_{n}^{→}) . (\{n next(X_{1}) = E_{1}; ; ⋮ ; next(X_{n}) = E_{n}; ; Y_{1} = E_{y_{1}}; ; ⋮ ; In next(X_{1}), ⋯, next(X_{n}) \}); \\ t_{p} & = & Apn (p, X_{n}^{→}); \\ t_{n}^{→} & = & WLoopn (p, b, X_{n}^{→}, t_{p}); \\ t_{f} & = & E_{f} [t_{n}^{→} / X_{n}^{→}]_{B} \\ & In t_{f}\} \end{matrix}

Notice that the correspondence between the formal parameters of the procedure “b” and the multiple value returned is not accidental. It will be wrong to have (X_{1}, ⋯, X_{n}) as input and (next(X_{n}), ⋯, next(X_{1})) as output, because the values of the nextified variables come either from the surrounding scope or from the previous iteration. The λ-expressions corresponding to the predicate and loop body are underlined indicating the fact that they can be inlined at compile time.

TE[[{ For X ← E_{i} to E_{b} step Es do S_{1}; ⋮ S_{n}; Finally E_{f} }]] = TSLE[[{ For X ← TE[[E_{i}]] to TE[[E_{b}]] step TE[[E_{s}]] do TS[[S_{1}]]; ⋮ TS[[S_{n}]]; Finally TE[[E_{f}]] }]]

TSLE[[ \{For X_{1} ← E_{i} to E_{b} step E_{s} do next(X_{2}) = E_{2}; ⋮ next(X_{n}) = E_{n}; Y_{1} = E_{y_{1}}; ⋮ Finally E_{f} \}]] = \{ \begin{matrix}b & = & \begin{matrix}\underline{λ_{n,n−1}} (X_{n}^{→}) . \\ (\{n−1 next(X_{2}) = E_{2}; ; ⋮ ; next(X_{n}) = E_{n}; ; Y_{1} = E_{y_{1}}; ; ⋮ ; In next(X_{2}), ⋯, next(X_{n}) \}); \end{matrix} \\ t_{i} & = & E_{i}; \\ t_{b} & = & E_{b}; \\ t_{s} & = & E_{s}; \\ t_{p} & = & ≤ (t_{i}, t_{b}); \\ t_{n}^{→} & = & FLoopn (t_{b}, t_{s}, b, t_{i}, X_{2,n}^{→}, t_{p}); \\ t_{f} & = & E_{f} [t_{n}^{→} / X_{n}^{→}]_{B} \\ & In t_{f}\} \end{matrix}

TE[[{Fun X_{n}^{→} = E}]] = λn (X_{n}^{→}) . (TE[[E]])
TE[[\{\underline{Fun} X_{n}^{→} = E\}]] = \underline{λn} (X_{n}^{→}) . (TE[[E]])
TE[[{S_{1}; ⋯ S_{n}; In E}]] = { TS[[S_{1}]];
⋮
TS[[S_{n}]];
t = TE[[E]]
In t }

TS: Id^{−} Statement ⟶ list (Kid Statement)

Often an Id^{−} statement translates into a group of Kid statements. We will enclose the translated statement or statements within parenthesis even though parenthesis are not part of Kid syntax. These parenthesis do not introduce a new lexical scope.

TS[[P = E]] = (t = TE[[E]]; TB[[P = t]])

TS[[E_{1}[E_{2}] = E_{3}]] = ( \begin{matrix}t_{1} & = & TE[[E_{1}]]; \\ t_{2} & = & TE[[E_{2}]]; \\ t_{3} & = & TE[[E_{3}]]; \\ t & = & Ap3 (Store, t_{1}, t_{2}, t_{3})) \end{matrix}

where Store is a standard function defined in Kid (see Section 4.2 ).

TS[[E_{1}.cons 1 = E_{2}]] = ( \begin{matrix}t_{1} & = & TE[[E_{1}]]; \\ t_{2} & = & TE[[E_{2}]]; \\ t & = & List case (t_{1}, \{ Store error In ()\}, \{ Cons store 1 (t_{1}, t_{2}) In () \} ) ) \end{matrix}

Similarly for cons 2. TB: Id^{−} Bindings ⟶ list (Kid Binding)

TB[[(P_{1}, ⋯, P_{n}) = X]] = (t_{n}^{→}= Detuplen (X);
TB[[P_{1} = t_{1}]];
⋮
TB[[P_{n} = t_{n}]] )
TB[[(P_{1} : P_{2}) = X]] = (t_{1}, t_{2} = List case2 (X, ( Error, Error ), (Cons 1 (X), Cons 2 (X)) );
TB[[P_{1} = t_{1}]];
TB[[P_{2} = t_{2}]])
TB[[Y = X]] = (Y = X)
TB[[Next Y = X]] = (next(Y) = X)

TO: Id^{−} Operator ⟶ Kid Operator

TO[[UOP]] = the corresponding Kid PF 1 TO[[BOP]] = the corresponding Kid PF 2

The Kid operator corresponding to Id^{−} “:” is Cons and for “==” is Equal?.

4.2 Definition of Standard Functions

In our translation from Id^{−} to Kid we have introduced two new functions Select and Store. These are not primitive operators in Kid, therefore we give their definitions. Similarly we give a definition for Make 1D array. For the sake of brevity we give these definitions in Id^{−}. These definitions and Make 1D array can be written as follows

      Make_1D_array = { Fun b f = { (l,u) = b ;
                                     a = I_array b;
                                     i = l;
                                     d = { While i ≤ u  do
                                            a[i] = f i;
                                            Next i = i+1
                                           Finally () }
                                     In a } }

Like lists we are treating I-arrays and functional arrays as the same type. However, functional arrays have a different degree of polymorphism than I nD array. We are ignoring these subtle issues in the above translation.

      Select = { Fun x i = { (l,u) =  1D_Bounds x;
                             In
                               If (i > u Or i < l)  then
                                                 Error
                                                    else
                                                 P_1D_select x i } }
      Store = { Fun x i y = { (l,u) =  1D_Bounds x;
                               In
                                 If (i > u Or i < l)  then
                                                 { Store_error In () }
                                                      else
                                                 { P_1D_store x i y In () } } }

The above Id^{−} definitions can be translated into Kid by adding the following rules:

TE[[P nD select x i]] = P nD select (x, i)

TS[[P nD store x i y]] = P nD store (x, i, y)

TE[[Error]] = Error TE[[Store error]] = Store error

4.3 Pattern Matching: Elimination of Complex Patterns

Pattern matching in Id follows a different philosophy than other functional languages such as Miranda and Haskell. In both these languages clauses in patterns are examined from top to bottom and patterns in a clause are examined from left to right. Within the limitations of the above rule, pattern matching does not force the evaluation of a pattern whose type is irrefutable (tuples are examples of irrefutable patterns) [6]. Miranda in addition allows repeated occurrences of a variable in a clause.

Id pattern matching is designed to be order-insensitive and is maximally non-strict for sequential implementations. In Id, patterns must not overlap to allow order-insensitivity. Id also does not permit repeated variables.

Determination of which variables are necessary to evaluate to resolve patterns is quite tricky as illustrated by the following example (due to Lennart Augustsson):

       { Case (x, y, z) of
          |   (1, 0, w) = 1
          |   (0, w, 1) = 2
          |   (w, 1, 0) = 3 }

First of all notice that the patterns are non-overlapping, i.e., only one can be true for a given x, y and z. Second, notice that top-to-bottom and left-to-right rule will evaluate x and then evaluate y or z depending upon the value of x. Thus, if x does not terminate no answer will ever be produced. Notice if y = 1 and z = 0 one could demand the answer 3 regardless of the x. Traversal of patterns in a different order will force evaluation of different variable.

Id pattern matching rules will force the evaluation of all three variables in this example because no unique sequential order exists. (In Miranda and Haskell, all three variables will be evaluated only if y turns out to be 1 or z turns out to be 0).

Now we informally describe a simplified version of the pattern matching algorithm used by the Id compiler [4]. For Id^{−} we take into consideration lists and tuples only. In the following we describe various cases that arise during pattern matching.

The signature of the pattern matching function is

PM : Case expression ⟶ Kid Expression

where Case-expression is defined as follows

Case expression ::= {Case SE of [ | Clause]^{∗}}
Clause  ::= P = Kid Expression
P  ::= Nil | Variable | () | (P, P) | (P, P, P) | ⋯ | (P : P)
SE  ::= () | (Variable, ⋯, Variable )

If the pattern is a variable, say “X”, then “X” is equivalent to “(X)”.

As was stated earlier, no scope analysis of variable names is required for the translation from Id to Kid. Thus, we will not assume that all bound variable names are unique in the Kid program that is generated by the translation process.

Variable rule

The column of patterns corresponding to a case variable consists only of variables.

PM[[ {Case (X_{1,i−1}^{→}, X_{i}, X_{i+1,n}^{→}) of ; |  (P 1_{1,i−1}^{→}, Y_{1}, P 1_{i+1,n}^{→}) = E_{1} ; ⋮ ; |  (P m_{1,i−1}^{→}, Y_{m}, P m_{i+1,n}^{→}) = E_{m}}]] =

\{ \begin{matrix}t = X_{i}; \\ t_{f} = PM[[ \{Case (X_{1,i−1}^{→}, X_{i+1,n}^{→}) of ; |  (P 1_{1,i−1}^{→}, P 1_{i+1,n}^{→}) = E_{1}[t/Y_{1}]_{B} ; ⋮ ; |  (P m_{1,i−1}^{→}, P m_{i+1,n}^{→}) = E_{m}[t/Y_{m}]_{B}\}]] \\ In t_{f} \} \end{matrix}

Note that meta-variables Y_{1} ⋯ Y_{m} may be distinct.

Irrefutable pattern rule

The column of patterns corresponding to a case variable consists of at least one tuple and zero or more variables. Without loss of generality in the following rule we assume the tuple to be a 2-tuple.

PM[[ {Case (X_{1,i−1}^{→} , X_{i} ,  X_{i+1,n}^{→}) of ; |  (P 1_{1,i−1}^{→} , Y_{1} ,  P 1_{i+1,n}^{→}) = E_{1} ; ⋮ ; |  (P k_{1,i−1}^{→} , Y_{k} ,  P k_{i+1,n}^{→}) = E_{k} ; |  (P l_{l,i−1}^{→} , (Y l_{1} , Y l_{2}) ,  P l_{i+1,n}^{→}) = E_{l} ; ⋮ ; |  (P m_{1,i−1}^{→} , (Y m_{1} , Y m_{2}) , P m_{i+1,n}^{→}) = E_{m}}]] =

{t_{1}, t_{2} = Detuple2 (X_{i});
t  = X_{i};
t_{f}  = PM[[ {Case (X_{1,i−1}^{→} , t_{1} ,  t_{2} ,  X_{i+1,n}^{→}) of ; |  (P 1_{1,i−1}^{→} , t_{1,1} , t_{1,2} , P 1_{i+1,n}^{→}) = E_{1}[t/Y_{1}]_{B} ; ⋮ ; |  (P k_{1,i−1}^{→} , t_{k,1} , t_{k,2} , P k_{i+1,n}^{→}) = E_{k}[t/Y_{k}]_{B} ; |  (P l_{l,i−1}^{→} , Y l_{1} , Y l_{2} , P l_{i+1,n}^{→}) = E_{l} ; ⋮ ; |  (P m_{1,i−1}^{→} , Y m_{1} , Y m_{2} , P m_{i+1,n}^{→}) = E_{m}}]]

In t_{f}}

Refutable pattern rule

The column of patterns corresponding to a case variable consists of only Nil’s and (Y_{1} : Y_{2})’s.

PM[[ {Case (X_{1,i−1}^{→} , X_{i} ,  X_{i+1,n}^{→}) of |  (P 1_{1,i−1}^{→} , Nil ,  P 1_{i+1,n}^{→}) = E_{1} ⋮ |  (P k_{1,i−1}^{→} , Nil ,  P k_{i+1,n}^{→}) = E_{k} |  (P l_{l,i−1}^{→} , Y l_{1} : Y l_{2} ,  P l_{i+1,n}^{→}) = E_{l} ⋮ |  (P m_{1,i−1}^{→} , Y m_{1} : Y m_{2} , P m_{i+1,n}^{→}) = E_{m}}]] =

List case (X_{i},
PM[[ {Case (X_{1,i−1}^{→} , X_{i+1,n}^{→}) of ; |  (P 1_{1,i−1}^{→} , P 1_{i+1,n}^{→}) = E_{1} ; ⋮ ; |  (P k_{1,i−1}^{→} , P k_{i+1,n}^{→}) = E_{k}}]],

\{ \begin{matrix}t_{h}, t_{t} = Cons 1 (X_{i}), Cons 2 (X_{i}); \\ t_{f} = PM[[ \{Case (t_{h} ,  t_{t} ,  X_{1,i−1}^{→} , X_{i+1,n}^{→}) of ; |  (Y l_{1} , Y l_{2} , P l_{1,i−1}^{→} , P l_{i+1,n}^{→}) = E_{l} ; ⋮ ; |  (Y m_{1} , Y m_{2} , P m_{1,i−1}^{→} , P m_{i+1,n}^{→}) = E_{m}\}]] \\ In t_{f}\} ) \end{matrix}

Note that if the case expression is not exhaustive then an alternative that will raise a run-time error is generated. As, for example:

PM[[ \begin{matrix}\{Case & X & of \\ | & Y_{1} : Y_{2} & = E\}]] \end{matrix} = PM[[ \begin{matrix}\{Case & X & of \\ | & Y_{1} : Y_{2} & = E \\ | & Nil & = Error\}]] \end{matrix}
PM[[ \begin{matrix}\{Case & X & of \\ | & Nil & = E\}]] \end{matrix} = PM[[ \begin{matrix}\{Case & X & of \\ | & Nil & = E \\ | & t_{1} : t_{2} & = Error\}]] \end{matrix}

Mixed variable-refutable patterns

The column of patterns corresponding to a case variable consists of at least one refutable pattern. In such a case each variable is replaced by all the possible alternatives, as shown below:

PM[[ \begin{matrix}\{Case & (X_{1}, & X_{2}, & X_{3} & ) & of \\ | & (Nil , & Y_{1,1} : Y_{1,2} , & Y_{1} & ) & = E_{1} \\ | & (Y_{2,1} : Y_{2,2} , & Y_{2} , & Nil & ) & = E_{2} \\ | & (Y_{3} , & Nil , & Y_{3,1} : Y_{3,2} & ) & = E_{3}\}]] = \end{matrix}

\{ \begin{matrix}t_{3}^{→} & = & X_{3}^{→}; \\ t_{f} & = & PM[[ \begin{matrix}\{Case & (X_{1}, & X_{2}, & X_{3} & ) & of \\ | & (Nil , & Y_{1,1} : Y_{1,2} , & Nil & ) & = E_{1}[t_{3}/Y_{1}]_{B} \\ | & (Nil , & Y_{1,1} : Y_{1,2} , & t_{1,1} : t_{1,2} & ) & = E_{1}[t_{3}/Y_{1}]_{B} \\ | & (Y_{2,1} : Y_{2,2} , & Nil , & Nil & ) & = E_{2}[t_{2}/Y_{2}]_{B} \\ | & (Y_{2,1} : Y_{2,2} , & t_{2,1} : t_{2,2} , & Nil & ) & = E_{2}[t_{2}/Y_{2}]_{B} \\ | & (Nil , & Nil , & Y_{3,1} : Y_{3,2} & ) & = E_{3}[t_{1}/Y_{3}]_{B} \\ | & (t_{3,1} : t_{3,2} , & Nil , & Y_{3,1} : Y_{3,2} & ) & = E_{3}[t_{1}/Y_{3}]_{B}\}]] \end{matrix} \\ In t_{f}\} \end{matrix}

This rule can be applied only after checking that none of other rules apply. It should be noted that patterns can be tested in many different orders, each giving rise to a correct program though non necessarily the same program. The above rules cover all legal cases. If we ever get tuple and list patterns in one column, the compiler will flag it as a type violation.

Empty variable rule

PM[[ {Case () of ; |  () = E_{1} ; ⋮ ; |  () = E_{m}}]] = Compiler Error “overlapping patterns”

PM[[ \begin{matrix}\{Case & () & of \\ | & () & = E\}]] \end{matrix} = E

5 Optimizations of Kid Programs

Following is a partial list of optimizations rules for Kid. Optimizations include all R_{Kid} rules, except the application rule. Optimizations should be performed after type checking and after all bound variables have been assigned unique names. Applicability of certain optimization rules requires some semantic check such as “\underline{m} > 0”. We write such semantic predicates above the line but following an “&”.

It is believed that all optimizations to be presented in this section preserve at least partial correctness. So far this has been proven for only a small subset of them [1].

Kid Rewrite rules

All Kid rewrite rules can be applied at compile time except for the Application rule, which can cause non-termination.

Inline Substitution

\frac{F = \underline{λn,m} (Z_{n}^{→}) . (E)}{Apn,m (F, X_{n}^{→}) − ; − ; → (RB [[E]]) [X_{n}^{→} / Z_{n}^{→}]}

Partial Evaluation

\frac{F = λn,m (Z_{n}^{→}) . (E)}{Apply (F, X) − ; − ; → \begin{matrix}\{f = λn−1,m (z_{n−1}^{→}) . ((RB [[E]]) [z_{n−1}^{→} / Z_{2,n}^{→}, X/Z_{1}]) \\ In f\} \end{matrix}}

A similar rule applies for \underline{λn,m}.

Fetch Elimination

\frac{X = Cons (X_{1}, X_{2})}{Cons 1 (X) − ; − ; → X_{1}}

\frac{X = Cons (X_{1}, X_{2})}{Cons 2 (X) − ; − ; → X_{2}}

Algebraic Identities

And (True, X) − ; − ; → X

Or (False, X) − ; − ; → X

+ (X, 0) − ; − ; → X

∗ (X, 1) − ; − ; → X

⋮

The above rules preserve total correctness, while the following rules preserve only partial correctness. Any algebraic rule that does not have a precondition can be included in the following rules.

And (False, X) − ; − ; → False
Or (True, X) − ; − ; → True

∗ (X, 0) − ; − ; → 0

− (X, X) − ; − ; → 0

Equal? (X, X) − ; − ; → True

⋮

The following rules are also partially correct but are not confluent.

\frac{X = + (X_{1}, \underline{m}) & \underline{m} > 0}{Less (X_{1}, X) − ; − ; → True}

\frac{X = + (X_{1}, \underline{m}) & \underline{m} > 0}{Less (X, X_{1}) − ; − ; → False}

\frac{X = + (X_{1}, \underline{m}) & \underline{m} > 0}{Greater (X_{1}, X) − ; − ; → False}

\frac{X = + (X_{1}, \underline{m}) & \underline{m} > 0}{Equal? (X_{1}, X) − ; − ; → False}

⋮

Common Subexpression Elimination

\frac{Y_{m}^{→}= PFN_{m} (X_{n}^{→})}{P F N_{m} (X_{n}^{→}) − ; − ; → Y_{m}^{→}}

Primitive functions I nD array, Open cons, Apply and Apn,m are excluded from this optimization because they (may) cause side-effects.

Lift Free Expressions

\frac{& FE(E, λn,m (Z_{n}^{→}) . (\{m Y = E; S In X_{m}^{→} \}))}{λn,m (Z_{n}^{→}) . (\{m Y = E; S In X_{m}^{→} \}) − ; − ; → \{m \begin{aligned}t_{1} & = & E; \\ t & = & λn,m (Z_{n}^{→}) . (\{m Y = t_{1}; S In X_{m}^{→} \}) \\ & In t \} \end{aligned}}

Where FE(e, e′) return true if the expression e is free in e′. This optimization allows us to deal with loop invariants, that is, expressions that do not depend on the nextified variables. A similar rule applies for \underline{λn,m}. (See the restrictions in the common subexpression elimination rule).

Hoisting Code out of a Conditional

\frac{& FE(E, (Boolcasen (X, \{n Y = E; S In X_{n}^{→} \}, \{n Y′ = E; S′ In X′_{n}^{→} \})))}{Bool casen (X, \{n Y = E; S In X_{n}^{→} \}, \{n Y′ = E; S′ In X′_{n}^{→} \}) − ; − ; → \{n t_{1} = E; t_{n}^{→} = Bool casen (X, \{n Y = t_{1}; S In X_{n}^{→} \}, \{n Y′ = t_{1}; S′ In X′_{n}^{→}\}) In t_{n}^{→} \}}

Eliminating Circulating Variables

Suppose in the loop body of an Id program there exists an expression like “Next x = x ” , then the variable x can be made into a free variable of the loop and its circulation can be avoided. Without loss of generality we assume that the nextified variable to be eliminated is the last one.

\frac{\begin{matrix}P = \underline{λn} (X_{n}^{→}) . (E) & | \\ B = \underline{λn,n} (X′_{n}^{→}) . (\{n S In Z_{n−1}^{→}, X′_{n}\}) \end{matrix}}{WLoopn (P, B, Y_{n}^{→}, Y_{p}) − ; − ; → \{ \begin{matrix}p = \underline{λn−1} (x_{n−1}^{→}) . (RB[[E]] [x_{n−1}^{→} / X_{n−1}^{→}, Y_{n}/X_{n}]); \\ b = \underline{λ_{n−1,n−1}} (x′_{n−1}^{→}) . (RB[[\{n−1 S In Z_{n−1}^{→}\}]] [x′_{n−1}^{→} / X_{n−1}^{→}, Y_{n}/X′_{n}]); \\ t_{n−1}^{→}= WLoopn−1 (p, b, Y_{n−1}^{→}, Y_{p}) \\ In t_{n−1}^{→}, Y_{n}\} \end{matrix}}

A similar optimization applies to for-loops.

Eliminating Circulating Constants

Suppose in the loop body there exists an expression like “Next x = t ”, where the variable t is a free variable of the loop body then its circulation can be avoided. Such situations may arise as a consequence of lifting invariants from a loop. The following example illustrates this transformation:

          { While (p x y) do
              Next x = t;
              Next y = f x y;
            Finally  y}

This may be transformed as follows:

        If (p x y) then
                { y1 = f x y;
                 In
                   { While (p t y1) do
                       Next y1 = f t y1;
                     Finally  y1} }

                    else
                 y

Notice that it is only after the first iteration that the value of “x” is t. Thus, to avoid the circulation of the nextified variable “x”, the loop has to be peeled once. This rule can be expressed as follows. Please note that we could have also written Z_{n} instead of t_{n} on the righthand-side.

\frac{\begin{matrix}P = \underline{λn} (X_{n}^{→}) . (E) & | \\ B = \underbrace{\underline{λn,n} (X′_{n}^{→}) . (\{n S In Z_{n}^{→}\})}_{ρ} & F E(Z_{n}, ρ) \end{matrix}}{WLoopn (P, B, Y_{n}^{→}, Y_{p}) − ; − ; → Bool casen (Y_{p}, \{n p  = \underline{λn−1} (x_{n−1}^{→}) . (RB[[E]] [x_{n−1}^{→} / X_{n−1}^{→}, t_{n}/X_{n}]); b  = \underline{λn−1,n} (x′_{n−1}^{→}) . (RB[[\{n−1 S In Z_{n−1}^{→}\}]] [x′_{n−1}^{→} / X′_{n−1}^{→}, t_{n}/X′_{n}]); t_{n}^{→}  = Apn,n (B, Y_{n}^{→}); t_{p}  = Apn−1 (p, t_{n−1}^{→}); t′_{n−1}^{→} = WLoopn−1 (p, b, t_{n−1}^{→}, t_{p}); In t′_{n−1}^{→}, t_{n}\}, Y_{n}^{→})}

Peeling the Loop once

FLoopn (U, D, B, X_{n}^{→}, X) − ; − ; → Bool casen (X, {n t_{2,n}^{→} = Apn,n−1 (B, X_{n}^{→}); t_{1} = + (X_{1}, D); t_{p} = < (t_{1}, U); t′_{n}^{→} = FLoopn (U, D, B, t_{n}^{→}, t_{p}) In t′_{n}^{→}},

X_{n}^{→})

Loop Body Unrolling K times

\frac{& remainder ((U −X_{1})/D, \underline{k}) = 0}{FLoopn (U, D, B, X_{n}^{→}, X_{p}) − ; − ; → \{n b = \underline{λn,n−1}(x_{n}^{→}) . (\{n−1 t_{2,n}^{1}^{→} = Apn,n−1 (B, x_{n}^{→}); t_{1}^{1} = + (X_{1}, D); t_{2,n}^{2}^{→} = Apn,n−1 (B, t_{n}^{1}^{→}); t_{1}^{2} = + (t_{1}^{1}, D); ⋮ t_{2,n}^{k}^{→} = Apn,n−1 (B, t_{n}^{k−1}^{→}) In t_{2,n}^{k}^{→}\} ); t_{n}^{→} = FLoopn (U, D, b, X_{n}^{→}, X_{p}); In t_{n}^{→}\}}

Suppose r = remainder((U − X_{1})/D, \underline{k}) , and r is not zero. We can still apply the above transformation by first peeling the loop r times.

6 P-TAC: Parallel Three Address Code

6.1 P-TAC

The syntax of P-TAC is given in Figure 4. In P-TAC, I-structure Storage is modelled in greater detail which requires the notion of Labels. All composite objects, that is, data structures and closures are stored in I-structure store and assigned unique labels, which are treated as constants that can be substituted freely.

6.2 Rewrite rules of P-TAC

In the following V stands for a ground value.

δ rules

+ (\underline{m}, \underline{n}) − ; − ; →_{δ} \underline{+(m, n)} ; ⋮

UDF ∈ User Defined Function
GV ∈ Ground Value
Integer  ::= 1 | 2 | ⋯ | \underline{n} | ⋯
Boolean  ::= True | False
V ariable ::= x | y | z | ⋯ | a | b | ⋯ | f | ⋯ | x_{1} | x_{2} | ⋯
MV_{m}  ::= \underbrace{V ariable, ⋯, V ariable}
Label  ::= L | L1 | ⋯ | L′ | ⋯
PF 1  ::= Negate | Not | Allocate
PF 2  ::= + | − | ∗ | ⋯ | Less | Equal? | P select
PF 3  ::= Ack store
UDF  ::= F | G | ⋯
SE  ::= V ariable | UDF | GV
SE_{m}  ::= \underbrace{SE, ⋯, SE}_{m}
GV  ::= Integer | Boolean | () | Label | Error | ⊤
E_{1}  ::= SE | PF 1 (SE) | PF 2 (SE_{2}) | PF 3 (SE_{3}) | Apn (SE_{n+1})

| Dispatchn (SE, \underbrace{E, ⋯, E}_{n}) | WLoop1 (SE_{4}) | FLoop1 (SE_{5}) | Block

E_{m}  ::= SE_{m} | Apn,m (SE_{n+1}) | Dispatchn,m (SE, \underbrace{E_{m}, ⋯, E_{m}}_{n})

| WLoopm (SE_{m+3}) | FLoopm (SE_{m+4}) | Block_{m}

Block_{m}  ::= {m [Statement; ]^{∗} In SE_{m}}
Statement ::= Binding | Command | Store Error
Command ::= P store (SE_{3}) | ⊤_{s}
Binding ::= MV_{m} = E_{m}

Figure 4: Grammar of P-TAC

Conditional rule

Dispatchn,m (\underline{i}, E_{i−1}^{→}, E_{i}, E_{i+1,n}^{→}) − ; − ; → E_{i}

I structure rules

Allocate (\underline{n}) − ; − ; → L

where L is a brand new label.

\frac{P store (L, \underline{i}, V)}{P select (L, \underline{i}) − ; − ; → V}

\frac{P store (L, \underline{i}, V)}{P store (L, \underline{i}, V′) − ; − ; → ⊤s}

where V is either an Integer or a Boolean or a Label or Error. The following rules are the same as the corresponding rules in Kid.

Application rule

\frac{F = λn,m (Z_{n}^{→}) . (E)}{Apn,m (F, X_{n}^{→}) − ; − ; → (RB[[E]]) [X_{n}^{→} / Z_{n}^{→}]}

A similar rule applies for \underline{λn,m}.

Loop rules

WLoopn (P, B, X_{n}^{→}, True) − ; − ; → {n t_{n}^{→} = Apn,n (B, X_{n}^{→}); t_{p} = Apn (P, t_{n}^{→}); t′_{n}^{→} = WLoopn (P, B, t_{n}^{→}, t_{p}) In t′_{n}^{→}}

WLoopn (P, B, X_{n}^{→}, False) − ; − ; → X_{n}^{→}

FLoopn (U, D, B, X_{n}^{→}, True) − ; − ; → {n t_{2,n}^{→} = Apn,n−1 (B, X_{n}^{→}); t_{1} = + (X_{1}, D); t_{p} = < (t_{1}, U); t′_{n}^{→} = FLoopn (U, D, B, t_{n}^{→}, t_{p}) In t′_{n}^{→}}
FLoopn (U, D, B, X_{n}^{→}, False) − ; − ; → X_{n}^{→}

Multivariable rule

X_{n}^{→} = Y_{n}^{→} − ; − ; → (X_{1} = Y_{1}; ⋯ X_{n} = Y_{n})

Substitution rules

\frac{X = Y}{X − ; − ; → Y} ; \frac{X = V}{X − ; − ; → V}

where V is either an Integer or a Boolean or a Label or Error.

Block Flattening rule

{m X_{n}^{→} = {n SS_{1}; SS_{2}; ⋯  {m X_{n}^{→} = Y_{n}^{→};
In Y_{n}^{→}} − ; − ; → SS_{1}; SS_{2}; ⋯
S_{1}; ⋯ S_{n}  S_{1}; ⋯ S_{n}
In Z_{m}^{→}}  In Z_{m}^{→}}

Propagation of ⊤

\begin{matrix}\{m X = ⊤; S_{1}; ⋯ S_{n} In Z_{m}^{→} \} & − ; − ; → & ⊤ \\ \{m ⊤_{s}; S_{1}; ⋯ S_{n} In Z_{m}^{→} \} & − ; − ; → & ⊤ \end{matrix}

7 Translation of Kid into P-TAC

Prior to translating Kid to P-TAC, λ-lifting is performed. A Kid program after λ -lifting only contains closed λ-expressions. The translator, given a Kid program, produces the corresponding P-TAC program and a set, “D” , of definitions. The set D is initialized with constants that are introduced by the translator.

7.1 Simple Kid Expressions

TE[[X]] = X

TE[[C]] = C

where C ranges over Integers and Booleans.

TE[[Negate (X)]] = Negate (X)

The same holds for Not.

TE[[+ (X, Y)]] = + (X, Y)
TE[[WLoopm (P, B, X_{m}^{→}, X_{b})]] = WLoopm (P, B, X_{m}^{→}, X_{b})

The same holds for FLoop.

TE[[Bool casem (X, E_{1}, E_{2})]] = {m t = BooltoInt (X); t_{m}^{→} = Dispatch2,m (t, E_{1}, E_{2}); In t_{m}^{→}}

BooltoInt is a coercion function which converts True to 0 and False to 1.

TE[[{m X_{1} = E_{1}; ⋯ X_{n} = E_{n}; S_{1}; ⋯ S_{m} In Y_{m}^{→} }]] = {m X_{1} = TE[[E_{1}]]; ⋮ X_{n} = TE[[E_{n}]]; TS[[S_{1}]]; ⋮ TS[[S_{m}]]; In Y_{m}^{→} }

7.2 Data Structure Representations

There are usually several reasonable ways to represent each data structure in terms of a P-TAC array. For each type we present one representation, though not necessarily the most efficient one. We have included a “type” tag field for all composite objects, even though it is not needed by the P-TAC interpreter since Id is a statically typed language. We might need types information for other reasons, such as, garbage collection, and printing values in a partially executed program.

Tuples

All n-tuple data types may be represented as follows:

1.5in

TE[[Make tuplen (X_{n}^{→})]] = \{t = Allocate (\underline{n + 1}); P store (t, Type, “n tuple”);

P store (t, 1, X_{1});
⋮
P store (t, \underline{n}, X_{n});
In t}

TE[[Detuplem (X)]] = \{m t_{1} = P select (X, 1); ⋮ t_{m} = P select (X, \underline{m}); In t_{m}^{→}\}

38

1D-Arrays

1D-arrays “Array (l, u)” may be represented as follows:

2.5in The constant definition Headersize = 2 should be included in the set “D”.

TE[[nD Bounds (X)]] = P select (X, Bounds)

TE[[I array (X)]] = \{ \begin{matrix}l & = & P select (X, Lower); \\ u & = & P select (X, Upper); \\ s & = & − (u, l); \\ size & = & + (s, 3); \\ t & = & Allocate (size); \\ P store (t, Type, “Array”); \\ P store (t, Bounds, X); \\ In t\} \end{matrix}

TE[[P 1D select (X_{1}, X_{2})]] = \{ \begin{matrix}t_{b} & = & P select (X_{1}, Bounds); \\ l & = & P select (t_{b}, Lower); \\ t_{1} & = & − (X_{2}, l); \\ t_{2} & = & + (t_{1}, Headersize); \\ t & = & P select (X_{1}, t_{2}) \\ & In t\} \end{matrix}

TE[[P 1D store (X_{1}, X_{2}, X_{3})]] = \{ \begin{matrix}t_{b} & = & P select (X_{1}, Bounds); \\ l & = & P select (t_{b}, Lower); \\ t_{1} & = & − (X_{2}, l); \\ t_{2} & = & + (t_{1}, Headersize); \\ t & = & P store (X_{1}, t_{2}, X_{3}) \\ & In t\} \end{matrix}

A representation that will be more efficient for computing the slot address may want to store l and u values redundantly in two additional fields.

2D-Arrays

The translation given below assumes that the matrix is stored in the row major order. The following constant definitions should be included in the set “D”.

First dim = 1 Second dim = 2
First index = 1 Second index = 2
TE[[I 2D array (X)]] = \{ \begin{matrix}d_{1} & = & P select (X, First dim); \\ d_{2} & = & P select (X, Second dim); \\ l_{1} & = & P select (d_{1}, Lower); \\ u_{1} & = & P select (d_{1}, Upper); \\ l_{2} & = & P select (d_{2}, Lower); \\ u_{2} & = & P select (d_{2}, Upper); \\ s_{1} & = & − (u_{1}, l_{1}); \\ s_{2} & = & − (u_{2}, l_{2}); \\ s′_{1} & = & + (s_{1}, 1); \\ s′_{2} & = & + (s_{2}, 1); \\ s & = & ∗ (s′_{1}, s′_{2}); \\ size & = & + (s, Headersize); \\ t & = & Allocate (size); \\ P store (t, Type, “Array”); \\ P store (t, Bounds, X); \\ In t\} \end{matrix}

Translation for I nD array can be given in a similar fashion.

TE[[P 2D select (X_{1}, X_{2})]] = \{ \begin{matrix}b & = & P select (X_{1}, Bounds); \\ d_{1} & = & P select (b, First dim); \\ d_{2} & = & P select (b, Second dim); \\ l_{1} & = & P select (d_{1}, Lower); \\ u_{1} & = & P select (d_{1}, Upper); \\ l_{2} & = & P select (d_{2}, Lower); \\ u_{2} & = & P select (d_{2}, Upper); \\ r & = & − (u_{2}, l_{2}); \\ r′ & = & + (r, 1); \\ i & = & P select (X_{2}, First index); \\ j & = & P select (X_{2}, Second index); \\ i′ & = & − (i, l_{1}); \\ j′ & = & − (j, l_{2}); \\ o & = & ∗ (i′, r′); \\ o′ & = & + (o, 1); \\ ad & = & + (o, j′); \\ ad′ & = & + (ad, Headersize); \\ t & = & P select (X_{1}, ad′) \\ In t\} \end{matrix}

A similar rule applies for P 2D store, and higher dimensional arrays.

Lists

The list data type can be represented as follows:

3in It is often possible to store niladic constructors using much less space by combining them with pointers. We won’t discuss such machine dependent representations in this paper.

The following constant definitions should be included in the set “D”.

Nil size = 2
Cons size = 4
Nil Tag = 0
Cons Tag = 1

TE[[Nil]] = {t = Allocate (Nilsize); P store (t, Type, “List”); P store (t, Tag, Nil Tag); In t}

TE[[Open cons ()]] = \{ \begin{matrix}t = Allocate (Cons size); \\ P store (t, Type, “List”); \\ P store (t, Tag, Cons Tag); \\ In t\} \end{matrix}

TE[[Cons 1 (X)]] = P select (X, Hd)

TE[[Cons 2 (X)]] = P select (X, Tl)

TE[[Cons (X_{1}, X_{2})]] = \{ \begin{matrix}t = Allocate (Cons size); \\ P store (t, Type, “List”); \\ P store (t, Tag, Cons Tag); \\ P store (t, Hd, X_{1}); \\ P store (t, Tl, X_{2}); \\ In t\} \end{matrix}

TS[[Cons store 1 (X_{1}, X_{2})]] = P store (X_{1}, Hd, X_{2});

TS[[Cons store 2 (X_{1}, X_{2})]] = P store (X_{1}, Tl, X_{2});

TE[[List casem (X, E_{1}, E_{2})]] = {m t = P select (X, Tag); t_{m}^{→} = Dispatch2,m (t, E_{1}, E_{2}); In t_{m}^{→}}

7.3 Function Calls and Closures

At the machine level, the apply operator checks if the arity of the function has been satisfied or not, and in case the arity has not been satisfied, it stores the argument in a data stucture called a closure. There is great choice in representing closures and associated function calling conventions. In fact, a function can be compiled using several different calling conventions and the compiler can pick up the most appropriate one for a given application. As an illustration we chose the following representation for the closure data type:

2in The constant definition Closure size = 5 should be included in the set “D”. We begin by describing a procedure that builds a closure given an old closure and an argument.

Make closure = \underline{λ} (cl, X) . (\{ \begin{matrix}f & = & P select (cl, Funcname); \\ f_{fc} & = & P select (cl, Fastcallname); \\ n & = & P select (cl, Arity); \\ ch & = & P select (cl, Chain); \\ cl′ & = & Allocate (Closure size); \\ P store (cl′, Type, “Closure”); \\ P store (cl′, Functionname, f); \\ P store (cl′, Fastcallname, f_{fc}); \\ P store (cl′, Arity, n′); \\ P store (cl′, Chain, ch′); \\ n′ & = & − (n, 1); \\ ch′ & = & Ap2 (Arg chain, X, ch); \\ In cl′\} ) \end{matrix}

where the function to build argument chains is defined as follows:

Arg chain = \underline{λ} (X, Xs) . ( \begin{matrix}\{xs′ = Allocate (2); \\ P store (xs′, Arg, X); \\ P store (xs′, Rest, Xs); \\ In xs′\} ) \end{matrix}

The argument chain can be destructured using the following function:

Argsn = \underline{λ} (X) . (\{n t_{1}  = P select (X, Chain); a_{n}  = P select (t_{1}, Arg); t_{2}  = P select (t_{1}, Rest); a_{n−1} = P select (t_{2}, Arg); t_{3}  = P select (t_{2}, Rest); ⋮ a_{1}  = P select (t_{n−1}, Arg); In a_{n}^{→}\} )

These three definitions must be included in the “D” set.

Now we can give the translation for the apply operator. As stated earlier, the apply basically checks to see if the arity is satisfied and either makes a new closure or calls Ap.

TE[[Apply (F, X)]] = \{ \begin{matrix}n & = & P select (F, Arity); \\ fire_{b} & = & Equal? (n, 1); \\ fire_{i} & = & BooltoInt(fire_{b}); \\ res & = & Dispatch2,2 (fire_{i}, \\ & \{ \begin{matrix}fun & = & P select (F, Functioname); \\ as & = & P select (F, Chain); \\ as′ & = & Ap2 (Arg chain, X, as); \\ res′ & = & Ap (fun, as′); \\ In res′\}, \end{matrix} \\ & Ap2 (Make closure, F, X)) \\ In res\} \end{matrix}

TE[[Apn,m (F, X^{→})]] = {m f′ = P select (F, Fastcallname); t_{m}^{→} = Apn,m (f′, X^{→}); In t_{m}^{→} }

The only thing that remains to be described is the creation of the first closure for a function. It is built as a consequence of translating a λ-expression.

TE[[λn (X_{n}^{→}) . (E)]] = {cl = Allocate (Closure size); P store (cl, Type, “Closure”);

P store (cl, Functioname, ‘T_{c});
P store (cl, Fastcallname, ‘T_{fc});
P store (cl, Arity, \underline{n});
P store (cl, Chain, “End”);
In cl}

The following two function definitions are included in the set D.

T_{c} = λ1 (Xs) . \{ \begin{matrix}X_{n}^{→} & = & Ap1,n (Argsn, Xs); \\ t & = & TE[[E]]; \\ In t\} \end{matrix}

T_{fc} = λn (X_{n}^{→}) . TE[[E]]

‘T_{c} indicates the name T_{c} and not the value associated to T_{c}. Note that TE[[E]] can be computed once and shared between the curried aabd the fastcall version of the function. The same translation rule applies for \underline{λn}.

8 Signals

Before introducing signals, the P-TAC program is canonicalized, that is, all blocks are flattened and variables and values are substituted. Furthermore, dead code should be eliminated. We add signals only to non-strict combinators, and to combinators that produce side-effect, such as P store. The output of a strict operator can be interpreted as the signal that the instruction has indeed fired. We give the signal transformation using the translation functions S, SE and SC. The transformation is applied also to each constant definition in “D” .

S[[λn,m (X_{n}^{→}).{m Y_{1}  = Se_{1} ; ⋮ ; Y_{n}  = Se_{n} ; Y_{n+1} = Nse_{1} ; ⋮ ; Y_{n+m} = Nse_{m} ; C_{1} ; ⋮ ; C_{k} ; In R_{m}^{→}}]] = λn,m+1 (X_{n}^{→}) . ({m+1 Y_{1}  = Se_{1} ⋮ Y_{n}  = Se_{n} Y_{n+1}, S_{1} = SE[[Nse_{1}]] ⋮ Y_{n+m}, S_{m} = SE[[Nse_{m}]] S_{m+1}  = SC[[C_{1}]]; ⋮ S_{m+k}  = SC[[C_{k}]]; S′  = Syncm+k+i (Deadvariables, S_{m+k}^{→}) In R_{m}^{→}, S′})

Where Se_{i} stands for an expression involving strict operators, whilst Nse_{i} stands for either an applicative or a loop expression. Deadvariables are the parameters that are not being used in the body of the function.

SE[[WLoopn (P, B, Y_{n}^{→}, Y)]] = WLoopn^{′} (P, B, Y_{n}^{→}, S_{p}, Y)

Where S_{p} is the signal associated with the invocation of the predicate.

SE[[Apn,m (F, X_{n}^{→})]] = Apn,m+1 (F, X_{n}^{→}) SC[[P store (X, I Z)]] = Ack store (X, I Z)

Where Ack store is a new P-TAC function symbol of arity 3, which generates a Signal when the store actually takes place. The new rewrite rules are:

WLoopn^{′} (P, B, X_{n}^{→}, S, True) − ; − ; → {n+1 t_{n}^{→}, S_{b} = Apn,n+1 (B, X_{n}^{→}); t_{p}, S_{p} = Apn,2 (P, t_{n}^{→}); S′  = Sync3 (S, S_{b}, S_{p}); t′_{n}^{→}, S_{l} = WLoopn^{′} (P, B, t_{n}^{→}, S′, t_{p}) In t′_{n}^{→}, S_{l}}

WLoopn^{′} (P, B, X_{n}^{→}, S, False) − ; − ; → X_{n}^{→}, S
Ack store (L, \underline{i}, V)

− ; − ; →
{t = Signal;
P store (L, \underline{i}, V);
In t}
Syncn (V_{n}^{→}) − ; − ; → ()

Sync produces a void value when all the signals are received.

Acknowledgments

We would like to thank Shail Aditya for reading several earlier drafts of this paper and suggesting changes for better readability. This paper has benefitted a lot by informal discussions with the members of Computation Structures Group.

References

[1] Z. M. Ariola and Arvind. P-TAC: A parallel intermediate language. In Proc. ACM Conference on Functional Programming Languages and Computer Architecture, London, 1989. Also: CSG Memo 295, MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA 02139, USA.

[2] T. Kenneth R. A Compiler for the MIT Tagged-Token Dataflow Architecture. Technical Report LCS TR-370, MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA 02139, August 1986.

[3] R. S. Nikhil. Notes on Translating List Comprehensions in Id. Technical report, MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA 02139, USA, January 1988.

[4] R. S. Nikhil and Arvind. Notes on Pattern Matching Algorithm. Technical report, MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA 02139, USA, February 1988.

[5] R. S. Nikhil and Arvind. Programming in Id: a parallel programming language. 1990. (book in preparation).

[6] P. J. Simon L. The implementation of Functional Programming Languages. Prentice-Hall International, Englewood Cliffs, N.J., 1987.

[7] J. Thomas. Lambda lifting: Transforming programs to recursive equations. In Springer-Verlag LNCS 201 (Proc. Functional Programming Languages and Computer Architecture, Nancy, France), September 1985.

[8] A. Zena Matilde and Arvind. Contextual Rewriting. 545 Technology Square, Cambridge, MA 02139, USA, 1990. In preparation.

Contents

1 Introduction 1

2 Desugared Id^{−} 3

3 Kid : The Kernel Id Language 7 3.1 Kid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2 The Rewrite Rules of Kid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4 Translating Desugared Id^{−} into Kid 15 4.1 Simplification of Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.2 Definition of Standard Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.3 Pattern Matching: Elimination of Complex Patterns . . . . . . . . . . . . . . . . 22

5 Optimizations of Kid Programs 27

6 P-TAC: Parallel Three Address Code 32 6.1 P-TAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 6.2 Rewrite rules of P-TAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

7 Translation of Kid into P-TAC 36 7.1 Simple Kid Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 7.2 Data Structure Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 7.3 Function Calls and Closures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

8 Signals 45