Previous Up Next

16  Translate

basically done, some omissions, but not thoroughly tested.

This is a complex module. It is described in [App98b, Chapter 7]. One main client is the semantic module (cf. Section ??).

Different from what is stated in [App98b], I use symbols as argument for the new_level and not Temp.label. I reported it to Appel as potential error. This also required that the function new_level gives back the label, as well, since the Semant-module must store this in the environment.

In the end, it would be nice to make a it a functor over FRAME to get a retargetable compiler.

[L-value and r-value] What are l-values and r-values? What’s the difference on the level of the intermediate language?

In the source language, a variable can “denote” different things, either the address of the variable or the value stored there. For left-hand of an assignment, it’s the address which is meant, on the right-hand side it’s the value. So another word for l-value is assignable variable. The conversion of an l-value to an r-value, i.e., the “dereferencing”, is perfomed in the tree language by the operator Tree.Mem.

[Integer constants] How are they concretely translated? I.e., what is the result of the function int_exp?

[Nil expression] How is the nil-expression translated?

I translated it to a statement Exp(Const(0)), which just throws away the integer constant. It’s not clear whether that’s the best solution, but there is no skip-statement in the tree language. According to page 153, a similar thing is done for the conversion of a Tree.stm into a Tree.exp by the function unNx: it adds simply the Const(0) at the end of the statement to make it an expression. Another posibility would be to translate it to a label which is never used elsewhere.

[Sequence] How is a sequence of statements translated? Currently, what is kept is just the last element.

We distinguish in the translation of a sequence according to whether the result type is UNIT or not, i.e., whether there is no result value or whether the last element is evaluated. In the latter case, the translation is a bit more complex, as the last element has to be treated separately.

Currently, the construction is done in two phases, first, while type checking, the expressions are translated in isolation, and afterwards, they are glued together by the function seqlist. I’m not sure whether this is the best solution or even correct. Currently, the function seqlist, transforms a non-empty list of expressions e0,… en, into

    Eseq(Seq(e0,Seq(…  Seq(en−2,en−1)…)),en)

In the process, the ei except the last one are unwrapped into a Tree.stm, en into a Tree.exp.

[Complement] Why does page 161 mention unary complement? What is it anyway?

[Conditionals] How are the binary boolean operators of the abstract syntax translated?

There are some remarks at page 161. Abstractly, the result of a comparison operator is a boolean value.6 But, being primarily used for deciding or taking branches, the are better translated in a branching or conditional tree expression.

[Conditionals] What would happen if we translated the boolean value not into a conditional expression but a value? Would this be possible? Is it less efficient code? What does Appel mean if he says that “the whole point” of the Cx-construction is easy combination with the & and |-operators? They are translated away already anyway?

It seems that this code corresponds to the explanation given at page 162. It’s the un-fancy inefficient solution.

[Conditionals] How are conditionals translated?

Currently it’s done in the simplest possible way as shown in Figure 1.7

[[c]]C L_t L_f L_t: r <- [[e2]]E; jump L_join; L_f: r <- [[e3]]E; jump L_join L_join:: r
Figure 1: Simple-minded translation of a conditional

The whole expression is assumed to give back a value, i.e., the expression is translated into a Tree.exp, and not a Tree.stmt and the trailing temporary is the expression where the result is given back.

The problem is that the structure get’s rather spaghetti-like in case the expressions inside are not Translate.Ex’s, but conditional expressions, for instance in the following fragment:

if (1 < 2 ) then (3 < 5 ) else true fi

Then converting 3<5 into an expression introduces an inner level of conditional jumps and the result will look as follows:

CJump 1 < 2 L_t L_f L_t: [t_105] t_106 <- 1 // 1 = true CJump (3<5) L10, L11 // if 3<5, the keep the 1 L11: t_106 <- 0 // else 0 L10: [t_105] <- t_106 // give back the result in t_105 jump L_j // and join it L_f: t_105 <- Mem(t_102 + 4); // ``variable'' true jump L_j L_j: t_105 // end result

The translation distinguishes which form the translations of the branches e1 and e2 have. In case they are both conditional expressions themselves, i.e., Tree.Cx-expressions, then Figure 2.

λ L_t. λ L_f. [[c]]C Lc_1 Lc_2; Lc_1: [[e2]]C L_t L_f; Lc_2: [[e3]]C L_t L_f;
Figure 2: Translation of a conditional

In case neither branch returns a value, then the whole conditional expression does not return a value and is therefore translated into a Tree.Nx. In all other cases, a Tree.Ex is produced. The one-armed conditional does not generate a return value as enforced by the type system.

How is an ordinary expression interpreted as conditional?

The semantics is as follows:
              t_r <- 1
              [turn the Cx into a  conditional expression: unCx]
              t_r <- 0
Previous Up Next