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
- parametric types (Int(31) and such),
- primitives that can be applied to any pair of "compatible" arguments
(same types, ignoring the size), and delivering results of the "biggest"
argument type
- unspecified types such as "Integer" that subsume all specified types
- type query primitives (widthof) accessible to library functions, but
not user functions.
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:
- Round(), when a rounding takes place, i.e. the "real" results
lies in the interval between two representable numbers
- Overflow(), when the result is larger than any representable
number,
- Underflow(), when the result is smaller than any representable
number,
- DivZero(), when a division by zero takes place (this is
not the same as Overflow!)
- other undefined-ness operators like TangensUndefined()
whenever a tangens-function is applied to arguments of pi/2.
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
- throw a "real" exception, i.e. abort the on-going computation and
return to the next (i.e., dynamically preceding and matching) "catch"
expression, or
- return an "approximate" result of the required type.
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.