ALDiSP: An Evaluation of the Concepts

During my work on the development of AL-2, the successor to ALDISP, the need arose to extract what "features" of ALDiSP were real novelties, and which of those are worth preserving. A "novelty" in this sense is unique solution to a problem, i.e. either a new solution to a known problem, or a solution to a new problem. There is really nothing new under the sun, as far as solutions to well-known problems are concerned, so the real interesting items in the following list are problems unique to ALDiSP's application area, the specification of real-time DSP algorithms.

Good Ideas

What follows are those things that turn out, in the end, to be good ideas.

Numeric Types

This is a DSP-related problem, and it is not addressed in its entirety in ALDiSP (since there is no static type system). The question is: how does one construct a type systems with dozens of overlapping numeric types? The ALDiSP "solution" uses A "better" way to handle these kinds of types will be used in AL-2, namely type classes. There will be a minor hack; a type such as Int(31) will, type-theoretically, not be parameterized with a numeric argument (thus mixing type and value domains), but with a "anonymous width type". That is, the "31" really stands for "the type of 31-bit-values", and there is an infinite number of such types available.

Related to the problem of many types is the handling of overflow, underflow, and exceptions.

Exception Mechanisms

When thinking about the issue of exceptions (and even before I got the idea of using them to model rounding, of all things), I noticed that they are dynamically scoped. Why then not going the whole way and saying that exceptions really consist of two constructions, one for dynamical scoping of variables, the other for catch and throw? The distinction becomes more obvious in a CPS-based IR, since catch/throw are then simple function calls, while there is still a need for a dynamic binding mechanism. Conversely, in an "imperative" environment, there is some need for special catch/throw support, but the "dynamic environment" can be modelled by global (stack) variables.

Once the distinction between exception binding and invocation is made, the two kinds of exception functions (returning and non-returning) evolve naturally: Returning (aka non-aborting) exceptions are ordinary functions, while non-returning (aka aborting) exceptions are functions that invoke a "throw".

Overflow, Underflow, and Exceptions

These are really hard, and many languages ignore these issues entirely. (dynamically typed languages like Scheme or Mathematica often change the types when encountering an overflow or undefined argument, i.e. (sqrt -1) => "0 + i"; statically-typed machine-oriented languages like C ignore the issue entirely, up to the point that there is no way to check for an integer overflow, or delegate it to libraries (#include "ieee754.h", anyone?). ALDiSP solves it by a combination of library conventions and core language support (non-aborting exceptions).

Whenever an arithmetic result can't be represented in the expected result type of a function, one (or more) of a number of predefined exceptions is called:

Each of these exceptions is provided with enough arguments to reconstruct the "real" result and any of the "possible" results, and each of these exceptions can either Using these mechanisms, any machine behaviour can be modelled faithfully, and the user does not have to think about the issue except when it is explicitly needed (the default system exceptions model the target hardware in its "most efficient" configuration).

Assertions via Type Tests

The general assertion operator, [type]expr, has turned out to create no substantial problems. In combination with procedural types, it also obivates the need for a special (restricted?) "proof language" (e.g., an equation-only language or somesuch).

Bad Ideas

The following ideas turned out to cause unforseen problems. Almost all the problems are combinations with the number one problem (dynamic typing), and the number two problem (automatic dereferencing).

Dynamic Typing

Not having a static type system is hell for a partial evaluator. More than half of the code of the evaluator consists of type checks, which also introduce major redundancies.

Automatic Dereferencing (in combination with dynamic typing)

There is no "type" like "suspension deliviering Int(4)", because any access to a suspension will transparently delivering its result. Otherwise, a call like
(suspend ... until ...) + 42
would be a type-mismatch, if evaluated before the suspension is finished, and otherwise ok. But now, everytime type-information of an expression is needed, the actual value is needed -- and that implys waiting for the value to be computed!

There are far too many places in the compiler where automatic dereferencing might be possible.

Overloading (in combination with Automatic Dereferencing)

Even worse, there are "hidden tyep tests" whenever an overloaded function is applied: to resolve the overloading, the arguments are tested for their type-ness.

Procedural Types (in combination with Overloading)

Even worse: the type-tests may invoke arbitrary predicates, since any predicate can be used as a type. Originally introduced to provide extra security (PRE assertions on the arguments), they can be used to resolve overloaded functions. What happens when one of the predicates accesses a promise, or even a suspension?

No Signal Type

The atomic constructs for evaluation constrol, suspensions & promises, should have been defines as signal-producing, i.e. repetitive. As it is, there is no "real signal type sig(x)", but instead a (suspend(pair(x,suspend(...)))) type. In the long run worse, the "built-in repetitiveness" of other signal-manipulating languages is absent from ALDiSP, resulting in a complex run-time model: after each control event (i.e. suspension evaluation), things have to be set up again for the next cycle. The opposing model would be to set things up once and for all, and let them stay that way. The complexity of the abstract scheduler solves this very problem, but not in every incarnation.
Last changed on 1995-10-05 13:41. Comments&corrections to mfx@pobox.com.