A lambda calculus backend without data constructors and `case`, what could go wrong?

Question

I'm working on a lazy lambda calculus backend. I'm roughly following the concepts from Implementing functional languages: a tutorial. It presents Core as an intermediate language, and it has data constructors (Pack{x, y}) and case expressions as well as a primitive integer type and a few built-in operations on it. Unlike modern Haskell Core, it is lazily evaluated everywhere except at case and primitive ops.

I decided to simplify Core a bit: my version of Core does not have explicit data constructors or case expressions. Instead, data declarations are meant to be lowered to Scott encoded supercombinators, e.g.

data Data = Constr1 arg11 arg12 | Constr2 arg21 arg22 arg23
-- becomes
constr1 arg11 arg12 case1 case2 = case1 arg11 arg12
constr2 arg21 arg22 arg23 case1 case2 = case2 arg21 arg22 arg23

This way, constr1 x y and constr2 x y z act as head normal form, and doing case on them is just a matter of passing two branches as lambdas accepting fields as arguments.

What kind of downsides would this approach have (relative to Core as presented in the linked paper), if any? e.g.

• Is this incorrect in some subtle way (e.g. unintended reduction or failed reduction)?
• Would it make some FP langs harder to compile to it?

It is assumed that the input code is typechecked under some type system (STLC, System F, ...).

Answer 1

There is nothing fundamentally wrong about doing this. It is semantically correct. However, I wouldn’t recommend it: there are many reasons you might not want to do things this way.

Optimization

GHC is an optimizing compiler, and most of its optimizations are performed on Core. Many of these optimizations take advantage of the code/data distinction; here are a few examples:

• The inliner knows that data constructor applications are safe to duplicate because they are always work-free.

• The case-of-case transformation (see A transformation-based optimiser for Haskell § 5) can rewrite nested case expressions even when the data constructor is not statically known, which can significantly improve code generation.

• The strictness analyzer (see A transformation-based optimiser for Haskell § 6) exploits the structure of case expressions to do its work. You say that your language is completely lazy, which is fine for an exploratory project, but support for strictness of some kind is very much mandatory for a lazy language to be practically useful, so you’ll want this eventually.

• Data constructors are used to guide automatic unboxing via the worker-wrapper transformation (see A transformation-based optimiser for Haskell § 6).

• Call-pattern specialization (pdf) specializes functions applied to known data constructors.

I’m sure there are others I’m forgetting, but this is a decent list.

Code generation

The structure of case expressions is extremely useful during code generation. They are a part of the STG language, which is GHC’s intermediate step between Core and portable assembly, and they’re used in the following ways:

• case expressions can be compiled in such a way that the continuation is stored on a fairly traditional call stack, which is very efficient. Supercombinators, in contrast, require case RHSs to be individually reified as distinct heap-allocated lambda expressions. This is enormously more expensive.

• In addition to the previous point, explicit case expressions allow the calling convention used in pattern-matching to be optimized in additional ways. One such optimization is described in Faster laziness using dynamic pointer tagging (pdf), which allows matching on an evaluated constructor to be made more efficient.

• The control-flow guarantees of case expressions also enable GHC join points optimization, which further cuts down on the number of closures that need to be allocated on programs have been transformed by optimizations.

Debugging the compiler

When your compiler has a bug, you will want it to be able to dump its internal representation as it flows through the compiler pipeline. Data constructors and case expressions are enormously easier to read than lambda soup.

Runtime

Preserving data constructors through the compiler pipeline allows them to be distinguished from lambdas at runtime via their heap object headers (GHC generally refers to these as “info tables”). This has several advantages of its own:

• It is possible to write a runtime debugger that can inspect the contents of runtime values even if their types are not dynamically known. Also, it allows inspecting values that are not otherwise normally printable (like functions) and inspecting values without forcing unevaluated fields.

• Tagging distinct constructors is very useful for implementing memory profiling, as it allows the contents of the heap to be broken down by type.

Summary

There are probably other reasons I’m not thinking about, but these are the major ones that come to mind, and it’s already a pretty long list. Even if you don’t care about optimization or performance, I think the improvement in the general debuggability of the system is quite significant. Given the work required to distinguish data constructors is not terribly large, I think they more than pay for themselves.