Home » forums » LtU Forum

Branching constructs in intermediate languages

I'm reading Bolingbroke and Peyton Jones' excellent paper Types Are Calling Conventions, and following along by building a quick-and-dirty interpreter for their proposed intermediate language.

There are a couple of options for how to structure the branching construct in such an intermediate language, and I'm curious if anyone has explored the advantages and disadvantages. Bolingbroke and Peyton Jones' have a case expression (branching on values only, since the whole language is in ANF and the idea is to make strictness/laziness explicit) and a very simple pattern language (a wildcard, literals, and unwrapping a single layer of data constructor binding it's arguments), along with an operational semantics that (if I'm reading it correctly) requires evaluating the list of alternatives in order.

Is this easier to work with than an if/then/else expression? Is it to be preferred simply because it doesn't require distinguishing a Boolean type in the intermediate language?

It's clearly equivalent and easy to understand either way, but I'm wondering if one or the other makes it easier to express common optimizations/transformations. Are there other sensible options besides these two?

By Douglas McClean at 2009-11-01 23:07 | LtU Forum | previous forum topic | next forum topic | other blogs | 5208 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

I would say a case

I would say a case expression is easier for the front-end to target and the back-end to generate nice code for. There are laws that apply to cases in general that may not be so obvious for a collection of if expressions. Finally, in a situation like, if null xs then ... else ... head xs, tail xs..., it is probably more difficult to recognize that those heads and tails are safe as opposed to a straightforward, case xs of [] -> ... | (y:ys) -> ...). Overall, I'd say using case would provide more uniformity and expose more relevant structure than using if. It's easier (but usually not necessary) to recognize if as a special case of case than it is to recognize case as one of several patterns of if expressions.

By Derek Elkins at Mon, 2009-11-02 07:29 | login or register to post comments

Sounds right

Thanks Derek. I agree with all of that.

By Douglas McClean at Mon, 2009-11-02 22:43 | login or register to post comments