Lowering in language design, part one

Programming language designers and users talk a lot about the “height” of language features; some languages are considered to be very “high level” and some are considered to be very “low level”. A “high level” language is generally speaking one which emphasizes the business concerns of the program, and a low-level language is one that emphasizes the mechanisms of the underlying hardware. As two extreme examples, here’s a program fragment in my favourite high-level language, Inform7:

Overlying relates one thing to various things. The verb to
overlie (it overlies, they overlie, it is overlying) implies 
the overlying relation. 

The jacket overlies the shirt. The shoes overlie the socks. 
The slacks overlie the undershorts. The shirt overlies the
undershirt.

Before wearing something when something (called the impediment)
which overlies the noun is worn by the player: try taking off
the impediment; if the player is wearing the impediment, stop 
the action.

This is part of the source code of a game;1 specifically, this is the code that adds a rule to the game that describes what happens when a player attempts to put on a pair of socks while wearing shoes. Note that the function which takes two objects and returns a Boolean indicating whether one overlies the other is not written as a function but rather as a relation associated with a verb, and that the language even allows you to provide a conjugation for a non-standard verb so that you can use it in any natural English form in your program. It is hard to imagine a language getting closer to the business domain.

By contrast, x86 assembler is a very low-level language:

add ebx, eax
neg ebx 
add eax, ebx
dec ecx

In one sense we know exactly what this fragment is doing; adding, negating and decrementing the values in registers eax, ebx and ecx. Why? Hard to say. The business domain is nowhere found here; this is all mechanism.

A compiler is a device which translates a program written in one language into an equivalent program in another language; typically the source language is a high-level language and the target language is a low-level language. A common technique along the way though is to have the compiler “lower” from high-level language features to low-level language features in the same language. For example, the C# 3 compiler goes through several stages of lowering when it is working on a query expression:

IEnumerable query = 
  from c in customers 
  where c.City == "London" 
  select c;

is first lowered into this equivalent C# fragment:

IEnumerable query = customers.Where(c=>c.City == "London");

which is then lowered to

IEnumerable query = Enumerable.Where(customers, c=>c.City == "London")

and then

static bool Lambda(Customer c)
{
  return c.City == "London";
}
static Func lambda;
...
if (lambda == null) lambda = Lambda;
IEnumerable query = Enumerable.Where(customers, lambda);

And then the conversion from method group Lambda can be lowered into a call to Delegate.Create and so on.

You can think of there being a “proto-C#” language which has no async methods, query comprehensions, extension methods, using statements, for loops, iterator blocks, lambdas, lifted operators, and so on; during compilation the compiler lowers C# program into this “proto-C#” language which can then be more easily transformed into IL.

Next time on FAIC I’ll discuss a principle of language design that C# does not cleave to, and discuss how some of the proposed new features for C# 6 bring C# more in line with that principle.


1. When In Rome 1: Accounting For Taste by Emily Short.

About these ads

9 thoughts on “Lowering in language design, part one

    • That’s correct. I’ve recently changed hosting services; the new service unfortunately does not support the footnote plugin I was using previously, so it will take me a while to manually update the links. Thanks for the note though.

  1. Pingback: Lowering in language design, part one | Fabulous adventures in coding « The Wiert Corner – irregular stream of stuff

    • Agreed!

      Inform 7 doesn’t perform any lowering that I can think of; it does translate to the C-like Inform 6, which isn’t much different from other compilers that translate to an intermediate language like C or assembly.

      However, it is a great example of what “high level” means in terms of thinking about business rather than implementation. For instance, the relation here is 1:N (“relates one thing to various things”), but relations can also be 1:1, N:1, N:N, or groupwise, or defined by a conditional expression instead of by relating specific objects. The implementations of those types are all very different (properties, bitmaps, hash tables, static functions, etc.), but those details are handled by the compiler and hidden from the programmer.

      Or take the syntax for testable assertions about objects: “something which overlies the noun is worn by the player” asserts that there exists some object of the class “thing” which relates to the noun in one way (overlying) and the player in another (being worn, i.e. the inverse of the wearing relation), but what might that mean in terms of implementation? Loop over all objects and test the class and both relations for each? Use an index optimized for class, or for one relation, and test the other two attributes for each matching object? Build a composite index for multiple attributes? Again, the compiler is free to choose the implementation.

  2. Pingback: Lowering in language design, part two | Fabulous adventures in coding

  3. This is not the first time you have mentioned Inform7. Since you are fan, where is your adventure? I would like to play it.

    • I have tried writing a few short programs just to get the hang of the language but nothing worth publishing. To see just how powerful the language was, I tried implementing the C# 1.0 overload resolution algorithm in it and I managed to get pretty far before the inability to construct arbitrarily many objects with different tags made it difficult.

  4. Pingback: Lowering in language design, part two | Dot Net RSS

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s