-----

Compiler Language Restrictions

-----

The Envision compiler translates user-defined coprocessor functions (input to bulk-define) into the assembler used by the coprocessor's interpreter (for debugging) and into C (for faster running times). User-defined coprocessor functions are only allowed to contain a limited subset of Scheme and Envision operations, so that the compiler can easily produce efficient output code. The user manual documents how these restrictions limit the user-level language.

Motivation

One key observation is that coprocessor functions are used for operations which will be performed many times, e.g. at every one of the 1M locations in a high-resolution digitized image. Therefore, very high efficiency is critical. Programmers have always restricted their style when writing such operations: the limitations on user-defined coprocessor functions simply make these existing restrictions clear and explicit.

A second important point is that the programmer can still define functions which are not subject to these restrictions: such functions run in main Scheme rather than in the coprocessor. A typical application would contain a mixture of high-level Scheme functions and user-defined coprocessor functions. Therefore, the limitations of the coprocessor compiler do not restrict what the programmer can do but, rather, what the programmer can do when an operation will be repeated at all (or many) image locations.

If you find the restrictions oppressive, you may prefer to think of the coprocessor as an unusually powerful programmable ALU, whose language happens to use the same syntax as Scheme.

Some of our restrictions are similar to restrictions imposed on PreScheme by Kelsey and Rees. There are, however, major differences. Our coprocessor must provide a wider range of numerical functions and must include operations for accessing sheets. On the other hand, because the Envision programmer also has access to a scheme interpreter, it is not necessary to support many scheme data types and operations in the coprocessor.

Restrictions for efficiency

All types are determined at compile-time and all polymorphism is resolved at compile-time. In this context, "type" includes not the base type (e.g. number vs. sheet) but also discrete-continuous distinctions (integer vs real, manifold vs integer-grid) and dimensionality (of points, sheets). Therefore, the only run-time type checking or type dispatching involves handling the edges of sheets (circularity or missing values) and variable precision of sheet values. Scanners are implemented by inline substitution at compile-time, so they do not require function calls inside the loop.

Second, user-defined coprocessor functions cannot do anything which dynamically allocates storage. Therefore, sheets and windows cannot be created or destroyed. Binary files cannot be opened or closed. Linked lists and similar dynamic structures are not supported.

Combined with compile-time type inference, this means that all new storage can be allocated on the stack. In generated C code, we can allocate all storage (including that for structs such as points) once, at the start of the C function, outside any scan loops. Pre-allocation of storage avoids overhead such as function calls and copying. It also means that forms which always return a non-missing point can set the missing field of their output only once, outside any scan loops.

Finally, many complex or high-level control constructs are not allowed. Some violate the above restrictions, e.g. non-tail recursion within a single coprocessor function requires dynamic storage allocation. Others seem impossible to compile into highly efficient code. Or it seems very difficult to analyze the conditions under which efficient code can be generated. We may be able to extend the set of control constructs somewhat, as we become more expert at writing compilers.

Restrictions to force good style

A number of other restrictions exist to force users to adopt an appropriate, clean style when implementing low-level image operations.

Tail recursion is not supported because it is almost never the conceptually correct way to write a low-level vision algorithm. Iterating over image locations should be replaced by scan (usually) or perhaps a loop (rarely). Recursive computations (e.g. of numerical functions) inside a scan loop either have trivial depth or will not be sufficiently efficient for image processing.

Operations for testing the types of objects are not supported, because types are determined at compile time. Header information for sheets, e.g. the domain and codomain descriptions, cannot be extracted because this is also type information. Rescaling or restricting sheets is forbidden for similar reasons.

The function = cannot be applied to inexact inputs, because such tests are numerically unstable.

String handling is not supported because characters are treated as integers inside bulk text processing algorithms (e.g. grep). Conversion between characters and integers should be done by functions which run in main scheme.

Single operations are not supported when there are corresponding bulk operations and, therefore, the single operations should not be called from inside a scan loop. For example, in main Scheme, we provide an operation for reading many bytes at once from a binary file. So, the user has no need to call read-byte inside a scan loop and therefore it is not supported. In general, no binary file I/O or window drawing operations are supported, for this reasons.

-----

Ownership, Maintenance and Disclaimers

Manual Top Page

Last modified Monday, 22-Sep-1997 22:50:13 PDT