Problems when trying to Type Check Assembly Code

Portable Assembler

There are good reasons for why C is so popular.

C is an imperfect abstraction, but barely so. Consider the case of a simple parameterized function that accepts a list and returns the first element if it exists. In Haskell you might write this as follows.

head :: [a] -> a
head [] = error "Empty list"
head (x:_) = x

Trying to write Generics in C

To attempt to capture some of this behavior in C, you might need to introduce the concept of a List. Unfortunately this concept doesn’t fit perfectly into the C type system. The problem with lists are that they contain another type. The first container declaration is no problem, just declare an IntList type.

struct IntList {
   head: int,
   tail: *IntList,
}

The problem with C here is that each new list requires a new declaration.

struct FloatList {
   head: float,
   tail: *FloatList,
}

Not only do you need a new list, but you will also need to rewrite every function for each type. This is an M by N problem, creating a lot of duplicate work.

Generating C Code from a Macro System

One approach to dealing with this problem in C is to use macros somehow. Maybe you even could create a smart macro system that still meaningfully type checks things for you. What you are quickly moving towards is a full blown compiler, leading into the concepts introduced in C++. I won’t journey into the benefits or downsides of C++ right now. I would like to keep my focus here on the problems with compilers for functional languages. Functional languages surprisingly have similar problems.

Generating Parameterized Code for a Functional Language

In the Haskell code presented above, compiled functional languages don’t get a free pass. The generated assembly code still might have multiple data structures and multiple code implementations. C is a portable assembler. Generated machine code tends to look a lot like C code. So why don’t we use C as an intermediate language?

• intermediate C compilers create yet another dependency

• intermediate C is already so similar to machine code, you might as well just skip it

A Better Type System for C

C is not so far off target, we might want to pay our respects and learn some lessons from it. What are some good ideas from C?

• Nominal Types (specify size and representation)

• Structures and Unions (specify alignment of composite data with fields)

• Portable Instructions for common operations on common types

What can we improve on from C?

• Parameterized Types

• Function Types

Summary

There is a lot of interest in compilers now as ever. There are tradeoffs when balancing complexity vs convenience in language design. C and C++ are languages at both extremes of that spectrum. FP languages have similar tradeoffs.