Class 27: Translating Conditionals

Held Friday, April 6, 2001

Summary

Today we consider how to translate conditionals.

Notes

• Are there more questions on the type checker? I know that some of you wanted to talk to me, and I'm happy to use some class time.
• There were enough problems interpreting the x86 assembly that I'll schedule a few classes on assembly-language programming.
  • Yes, it does mean that I have to learn x86 and AT&T syntax quickly.
  • Andrew has pointed out that x86 assembly is painful with regards to real numbers, so you are allowed to skip real numbers in the code-generation phase of your compiler. (You do still need to check types.)
• Michelle has asked that I be available early next Friday for an Easter trip to Chicago. Since I'd already scheduled a pause in the course next Friday, I'm cancelling class.
  • We will still have lab on Thursday.

Overview

• Basic issues
• Strict conditionals
• Short-circuit conditionals
• Case statements

Basic Issues

• The first issue to consider in translating conditionals is how to represent truth values. Typically, 0 is false and non-0 is true, but other options also exist.
  • We'll use the 0/non-0 form.
• It helpers to remember that a basic conditional consists of a test expression, a true part, and a possibly empty false part.
• Surprisingly (or not so surprisingly) there are two common strategies for translating conditionals. that are primarily related to the interpretation of boolean expressions involving and and or.
  • If you know that the first argument to and is false, do you need to evaluate the second?
  • If you know that the first argument to or is true, do you need to evaluate the second?
• If your language doesn't require the evaluation of all arguments to and and or, your language supports short-circuit evaluation.
• If your language requires the evaluation of all arguments to and and or, your language supports strict evaluation.
• What does Pascal do?

Translating Strict Conditionals

• Life is somewhat simpler with strict conditionals because you can use traditional expression evaluation strategies.
• Translate the expression, the true part, and the false part.
• Generate three new labels for the true part, the false part, and the end of the conditional.
• Join it all together with

  code-for-expression
  Jump-if-Zero location-for-expression-result label-for-falsepart
  Jump label-for-truepart
  label-for-truepart
  code-for-truepart
  Jump label-for-end
  label-for-falsepart
  code-for-falsepart
  Jump label-for-end
  label-for-end
  

• Why do we include that extra jumps at the beginning and end? Because they make it easier to rearrange the code.

Translating Short-Circuit Conditionals

• In short-circuit evaluation, your code needs to jump out of the expression evaluation code when the result of the boolean operator is known.
• Hence, we pass two extra parameters to the procedure for generating code for boolean expressions: the label to jump to if the expression is true and the label to jump to if the expression is false.
• The translation of the conditional is straightforward.

  code-for-short-circuit-expression
  Jump label-for-truepart
  label-for-truepart
  code-for-truepart
  Jump label-for-end
  label-for-falsepart
  code-for-falsepart
  Jump label-for-end
  label-for-end
  

• You may wonder what has happened to the first Jump-if-Zero. It's now encapsulated in the code for the short-circuit expression.
  • Hence, we need to figure out how to translate boolean expressions.
• Here are some examples

  /* Translate a less-than expression. */
  translate(LessThan(Exp left, Exp right), truelabel, falselabel)
    CodeLoc l = translate(left);
    CodeLoc r = translate(right);
    return JoinCode(l.code, r.code,
                    new Instruction(JumpLT l.loc r.loc truelabel),
                    new Instruction(Jump falselabel));
  
  /* Translate a not expression. */
  translate(Not(subexp), truelabel, falselabel)
    return translate(not(subexp), falselabel, truelabel);
  
  /* Translate an or expression. */
  translate(Or(bexp1,bexp2), truelabel, falselabel)
    // The new label will fall between the code for bexp1
    // and the code to bexp2.
    Label newlabel = new Label();
    // If bexp1 is true, jump to true label.  Otherwise,
    // do the code for bexp2.
    Code code1 = translate(bexp1, truelable, newlabel);
    // The result now depends only on bexp2.
    Code code2 = translate(bexp2, truelabel, falselabel);
    return JoinCode(code1, newlabel, code2);
  
  /* Translate an and expression. */
  translate(And(bexp1,bexp2), truelabel, falselabel)
    // The new label will fall between the code for bexp1
    // and the code to bexp2.
    Label newlabel = new Label();
    // If bexp1 is false, jump to false label.  Otherwise,
    // do the code for bexp2.
    Code code1 = translate(bexp1, newlabel, falselabel);
    // The result now depends only on bexp2.
    Code code2 = translate(bexp2, truelabel, falselabel);
    return JoinCode(code1, newlabel, code2);
  

Translating Case Statements

• The simplest technique is to treat the case statement as a sequence of ifs.
• However, if the cases are grouped together you can
  • Generate a label for each piece of code;
  • Make an array of those labels indexed by the corresponding value.
  • Do an indexed jump.
• An intermediate solution is to build a "search tree" for decisions.