Ronald Fischer is a software developer for Software-Entwicklung & Consulting and can be reached at Straubinger Strasse 20, D8000 Munchen 21, W. Germany.
Looking back at approximately 30 years of steady development of programming languages, there is no doubt that development strives towards more generality, more abstraction, and --last but not least --more expressional power. The first assembler programs of the early 1950s were a giant achievement over machine code (binary) programming. Later, the first so called high-level language was invented by software pioneer John Backus. This language was called Fortran, and its descendant, Fortran 77, is still in use today.
The next development in programming languages was known as "non-procedural languages" (sometimes called 5th-generation languages, a term that I do not like because it has become rather worn over the years). The very same expression is used today not only for pure database languages like SQL, Nomad, and RAMIS but also for true general-purpose languages such as Prolog.
No one debates that you can code a given problem much faster using, say, Prolog rather than assembler. We call this modern approach "high-level programming," compared to the "low level" of assembly language. So why do assemblers still exist? As every system programmer knows, there are situations where you have to use assembler. Most operating system kernels are, for instance, written in assembler. Even the famous Lilith machine, designed in the early 1980s by a design team led by Pascal inventor Niklaus Wirth, had a few critical routines written in machine language, although most of the operating system was coded in Modula-2. The reasons for such decisions are --in most cases --speed, but sometimes space considerations also play a critical role.
On the other hand, given a sufficiently huge problem, like coding a multiuser operating system, it becomes too complex for the human brain to manage at assembly level. In most applications, a mix of assembler and high-level language (HLL) is used. Examples are the PICK operating system (Basic+assembler) and some of IBM's mainframe operating systems (PL/1 and assembler). One could call this approach "two-level programming," because languages at precisely two different levels are used.
When developing system software, two-level programming is often an unsatisfactory solution: For much of the code, the HLL is "too high," but assembly language is too "low." System programmers therefore have been looking for languages that can better accommodate the range of needs. We call a programming language that satisfies this property "variable level."
Many experiments were carried out in this area during the late 1960s and throughout the 1970s: BCPL, BLISS, SPL3000 (Hewlett-Packard) and Siemens SPL are just a few examples. Three languages, however, proved to be very successful: C, which was used to write the Unix operating system, PL/M used for system programming by Digital Research, and Charles Moore's Forth. But only the latter really earns the tag "variable level," because neither C nor PL/M, despite their success, provide a single framework for system programming: Both Unix and Digital Research's Concurrent CP/M contain some assembler code and the user does not have much influence on the degree of abstraction or "level" of the statements used.
Forth is different. A Forth program consists of a collection of words (similar to functions or procedures in other languages). Each word in turn is composed of other words. The user therefore may assign to each conceptional level (or abstraction layer) a family of Forth words that are defined in terms of lower-level words only. The assembler is integrated into the language and represents the bottom level. In practice, this means that a function for searching through a text file uses high-level Forth words like EOF?, GET-NEXT-LINE, or MATCH-PATTERN, while an interrupt handler manipulates bits and bytes.
Variable-Level Approaches
Recently two new languages aimed at variable-level programming have gained attention from system programmers: FUTURE86 and CDL2. The remainder of this article covers some of the main features of these languages. For comparison purposes, two sample programs are coded in FUTURE86 and CDL2. Because many readers may be familiar with C, these sample programs are described first in C. All programs were developed on a 80386 system running PC-DOS 3.3. The compilers used were MIX Power C, Development Associates FUTURE86, and epsilon CDL2Lab.
The first example is a subroutine, AUXOUT, which sends one character to the serial device (called AUX under DOS). This is an example of a low-level system dependent function, because it is unlikely that the very same call exists on different operating systems. Although DOS, for example, has one primary serial port --namely AUX -- other operating systems might always require an identification of which serial interface to use.
Most C compilers support some generic interface to the host system. For example, Power C has among its functions a routine called bdos, which accepts three parameters and generates an INT 21H interrupt to call DOS. The parameters are placed in the registers AH, DX, and AL, respectively, and correspond therefore to function code, function argument, and function code parameter. For this example, a quick look in IBM's DOS Technical Reference Manual tells that we have to use 4 as the function code (auxiliary output) and the character to be output as arguments. The code parameter is not used; we deliberately set it to zero. Listing One shows the resulting function.
The second example is of much higher level. Suppose we have two character strings, S and T, and one character transformation function XTRANS, which accepts one character and delivers an arbitrarily transformed character. The objective is to design a function SFILT, which appends S to T, but by doing so applies XTRANS to every character of S. For this example, we assume that the array holding T must be large enough to also accommodate S.
As an application, imagine that you want to send one record of a binary file to the printer. Because the data may also contain nonprintable characters, such as escape sequences, we cannot blindly output the record. Instead, each nonprintable character should be replaced by a dash. This could be accomplished with SFILT in the following way: Let S be the record to be printed, let T be a sufficiently large buffer containing the string
"RECORD #12 (non-printables replaced by '-'): "
and finally let XTRANS be the function that maps nonprintable characters into dashes and leaves others unchanged.
For the sake of brevity assume in the example a fixed function named XTRANS; in practice, this function itself would be passed as a parameter for added flexibility so that different calls of SFILT could use different transformation functions. For the same reason, no concrete implementation of XTRANS is given.
The resulting C program is shown in Listing Two. Efficiency is not the primary goal, however, because FUTURE86 and CDL2 are biased towards recursive function calls, we will also use recursion in the C example. This makes it easier to compare the examples. In a real project, of course, you would use a loop.
The FUTURE86 Language
The history of FUTURE86 dates back to 1979. At this time Akira Katagiri, a Japanese scientist, implemented a Forth compiler for a Z-80-based microcomputer system. During this work, he found some deficiencies in this language, most notably the lack of readability. He then devised a successor, appropriately called FIFTH, and implemented it on different environments. FIFTH is widely used in Japan.
FUTURE86 is an evolution of FIFTH created during the 1980s. The first compiler was commercially available in 1987. Like FIFTH, it augmented the power of Forth without being just another Forth dialect. Despite its short history, FUTURE86 has already been used to implement numerous projects. For example, software for sophisticated, automatic postal scales and a natural language compiler has used FUTURE86. Like Forth, every FUTURE86 program implicitly operates on two stacks, called the data stack (that is, "stack") and the return stack. These names are a little bit misleading, because the return stack may also contain temporary data in addition to return addresses. Most predefined functions, however, operate on the data stack.
An expression is written in reverse polish notation (RPN). The sentence 15 27 101 + for instance pushes the numbers 15, 27, and 101 sequentially onto the data stack. The operation "+" then consumes the two topmost elements, 27 and 101, and replaces them by their sum. The data stack now contains the numbers 15 and 128. For readers unfamiliar with Forth or the Hewlett-Packard pocket calculators, this may look strange. In practice, you soon get acquainted with this type of operation.
Not everything in FUTURE86 is RPN, however, because this paradigm only applies to the evaluation of programs. Compile time expressions, on the other hand, are written in the more traditional infix notation. The following statements, for instance, set MAXLENGTH to 1024.
BUFSIZE EQU 256
NO-OF-BUFFERS EQU 4
MAXLENGTH EQU BUFSIZE
* NO-OF-BUFFERS
In fact, every sentence may contain compile time expressions in infix notation by enclosing them in parentheses, like this:
17 (34 * 45 + 8) VAR @ OVER -
Other differences from Forth concern the dependency between words: Because FUTURE86 was designed as a compiled language, two-pass compilation allows extensive forward referencing. This even applies to different compilation units: It is common practice for words in different modules to mutually call each other.
FUTURE86 also contains an assembler. Unlike Forth, assembler statements -- which may be freely intermixed with FUTURE86 words -- follow the syntax generally available on the target machine. On a 80186 system, you could for example, write: BOUND BX,[TESTLOC] inside any high-level definition. It is therefore the responsibility of the programmer to select the desired abstraction level at every single line of code!
Other minor differences from Forth concern the usage of some reserved words. The FUTURE86 version of LOOP functions, for example, is slightly different than its Forth counterpart.
Now let's look at how the sample programs are written in FUTURE86. Listing Three demonstrates one possible solution of the AUXOUT problem. The definition of AUXOUT, as every definition of a new word, starts with a colon, followed by the name of the function.
We assume that the character to be output is located on the stack. That is, to send the escape character to the serial interface you write: 27 AUXOUT. The predefined word !DL pops the top value from the stack and stores it in the pseudo CPU DL register. Of course, words like !DL are hardware dependent. The next word, AUXOUT-FUN, pushes this constant onto the stack, which now contains the number 4 only; the 27 is still in pseudoregister DL. Then, the word INT_21H is called. This function removes the top value of the stack (4), uses it as DOS function code (that is, pushes it into AH) and performs an interrupt (21 hex). The semicolon closes the definition.
At first, words like !DL seem strange for programmers getting used to traditional languages such as Fortran or Pascal. In reality, however, even this enhances readability. Because FUTURE86 --such as Forth or Lisp --is not committed to the traditional "Letter+Digit" identifiers, one can devise more meaningful names, like: IS-THERE-STILL-ROOM-IN-THE-BUFFER? which, by the way, is a perfectly legal FUTURE86 word. In the case of !DL, one needs to understand that the exclamation mark is generally used in the context "store from stack into ...," while the character "@" does the inverse.
The SFILT program in Listing Four is more complicated. The function XTRANS was --for testing purposes --defined as nonoperation, which is the shortest possible function definition. To comprehend SFILT, you have to understand FUTURE86's unique string concept.
A string always consists of two parts: A string buffer somewhere in memory, holding left justified the string characters, and a control block called SINFO (String INFOrmation), consisting of a pointer to the buffer and a length field. For string operations the SINFO is stored in the data stack. The simplest way to create a string is to place it within a quote, like this:
: HELLO "Hello world!" SPRINT;
The execution of HELLO would allocate a place in memory, large enough to hold all the characters, place the appropriate SINFO on the data stack and call the word SPRINT (String PRINT), which causes the string to be printed.
Our definition of SFILT assumes that the SINFO's of the destination string T and the source string S (in that order) are placed on the stack. On return, these SINFOs should be replaced by the updated SINFO of the destination string. This behavior of SFILT is depicted in the comment line labeled "stack flow."
Following the C example SFILT starts by determining the source strings length, which is the second part of its SINFO and therefore on top of the stack. Because IF consumes its argument, this data item has to be duplicated by the word SLEN. Many FUTURE86 functions remove their arguments from the stack, so this is quite a common operation.
The next steps (CGET and XTRANS) remove the first character from the source string and transform it. The following three lines temporarily save the character to the return stack, interchange the stack position of the two SINFOs, then restore the character to the stack.
The word C+ appends the character to the destination string. Then, the SINFOs stack position is interchanged again SFILT is recursively called.
The ELSE part simply discards the now empty SINFO of the source string from the stack to fulfill the functional description of SFILT. The word THEN matches the IF and is similar to Fortran's ENDIF statement.
The lines below demonstrate the usage of SFILT. The destination buffer is called DEST and may hold up to 80 bytes. This buffer is initialized with the function SETUP.MAIN calls SETUP, then SFILT, and finally prints the resulting string using SPRINT. This also shows how words work together: As mentioned, SFILT leaves the destination string's SINFO on the stack which, in turn, is consumed by SPRINT.
The CDL2 Language
CDL2 is a radically different language. It's precursor was CDL (compiler description language), a generator used to produce compilers from a given affix grammar. The first implementation of CDL took place at the Mathematical Center in Amsterdam (The Netherlands), and soon it became popular at a number of European universities.
In 1974 the language was extended by adding modularity and the ability to serve as a general-purpose programming language --CDL2 was born. Since 1980 it has become available outside the university community. It has been used for numerous commercial applications: A Cobol compiler from the German company MBP, the Prolog compiler MProlog, Mephisto (a chess computer), and EUMEL are but a few examples. EUMEL is a German operating system featuring the programming language Elan, which is targeted to education institutions (high schools, universities, and so on).
There are four basic elements of a CDL2 program: actions, tests, predicates, and functions. The most traditional form is the action: A piece of code that performs some operations, possibly changing its environment. The function is a similar construct, but preserving the environment like a mathematical function. A test is a special function that delivers a Boolean result.
Depending on the outcome, succeeding statements in a clause are skipped or executed. Finally, a predicate is an action that may either fail or succeed. Failure causes backtracking so the behavior is similar to Prolog clauses.
Every building block (action, test, and so on) may itself call other building blocks, in the same way FUTURE86 words may call other words. There are, however, no primitives in CDL2! The programmer therefore has to define the bottom layer himself. This is accomplished by defining an Action as a Macro, that is, consisting of assembly language instructions only. The same is true, of course, for tests, predicates, and functions. For simplicity, I refer in the sequel to "actions" only when I mean all four kinds of building blocks. Unlike FUTURE86, assembly statements and high-level CDL2 statements cannot be intermixed when defining an action.
To put different actions together is, however, not sufficient to produce a CDL2 program. The language was definitely designed for programming-in-the-large, for projects requiring a large staff, and delivering tens of thousands of code lines. Therefore, the design of the project is an integral part of the language.
All actions belonging to the same topic are grouped in a SECTION. A set of sections forms a LAYER (see Listing Five). Layers can be thought of as stacked one on top of another. Each layer must explicitly state which actions are exported to or imported from other layers. The top layer, for instance, could represent the specification of the problem. The next layer then could be a prototype, and by step-wise refinement, we reach the bottom layer, consisting of the applications low-level words. Therefore, most assembly language will be found in this bottom layer but not necessarily all: This is completely up to the designer. So, variable-level programming may not only be accomplished by thinking in words or statements but in a more general abstract entity, the layer.
Different layers together form a MODULE. A module is vaguely related to separate compilation units in other programming languages. In practice, each programmer on a CDL2 project will work on one and only one module at a time.
Finally, different modules together form a PROGRAM. It should be clear by now that CDL2 was designed to be only used for large applications. We therefore only sketch our example programs by defining a few actions, leaving out the lowest part and overall program organization.
Listing Six shows the layout of the AUXOUT action. As in the previous examples, the DOS function code is defined by a compile time constant. Note that for improved readability CDL2 identifiers may contain embedded spaces as that constant has been called "AUXOUT FUN."
The action AUXOUT expects one parameter C, the character to be output. Every CDL2 statement consists of a procedure evocation (where a procedure could be action, test, predicate or function) and actual parameters are separated by plus signs (+). Statements are separated by commas (sequential execution) or semicolons (parallel alternatives).
The action header follows the same format but states the formal parameters. In addition, the type of the parameter (input, output, or inout) is specified by placing the '>' character to the appropriate side (left, right, or both) of the parameter name. In this example C is therefore an input parameter. A colon at the end of the header line specifies the ACTION as containing CDL2 statements. An equal sign would specify it as assembly language action.
The subsequent three lines load the registers and perform the interrupt. In this particular example I also enclosed the definitions necessary to get the assembly instructions. The CDL2 words used in this small example are defined in the last three lines of Listing Six.
SFILT is only loosely sketched, because a complete CDL2 implementation would be beyond the scope of this article. As can be seen from Listing Seven, the destination string TARGET is defined as an out parameter because it will be modified during evaluation of the action. Note also the different usage of semicolon and comma to separate the statements.
Conclusion
Today there is no generally accepted opinion on how a programming language should look. This begins with the schism between functional programming (no assignment statements, no state change, no loops, no history), object-oriented programming (every object has its own history) and traditional imperative programming ("let Cobol and Fortran live forever!") and ends with debates if Basic should be allowed/ forbidden in high schools. Industry programmers and scientists agree only on the fact that we have some kind of software crisis (we would like to do much more programming but we do not know how to manage it).
Variable-level programming is certainly a good compromise for those projects where performance considerations prevent the complete usage of a high-level language. Very likely this will still be true for at least the next 20 years.
Due to its roots in grammar analysis CDL2 may attract even more attention in the near future. As parallel processing becomes more feasible, rule-based languages, like CDL2 or Prolog, could benefit immediately by new technologies because they are easily expandable to cope with simultaneous exploration of different, but parallel branches or rules.
In the next century we will likely have hardware that runs Smalltalk, Prolog, or Miranda at the speed of a today's 8086 object code. Maybe then we will no longer require FUTURE86, CDL2, or their future successors. My opinion, however, is that the requirements of projects will increase --at more or less -- the same rate of the performance of new hardware. The problems may shift slightly, but they won't disappear.
Notes
The examples have been developed using the POWER C compiler by MIX Software. This is one of the least expensive C compiler available but is complemented with the debugger CTRACE, a very powerful development tool and probably the C compiler with the best price/performance ratio available. For further information, contact Mix Software, 1132 Commerce Dr., Richardson, TX 75081.
At present, only one implementation of FUTURE86 is available in the U.S., although in Japan a similar version is sold by RIGY Corp. The U.S. version is available from Development Associates. It runs under PC/MS-DOS and contains code generators for both the 8086 and 80186. Other instruction sets, like the protected mode instructions of the 80286 processor, can be user defined with a CODEMACRO facility.
The compiler comes complete with debugger (FDT86) and libraries of CGA graphics, serial communications, Hayes and XModem protocols, and floating point. Libraries are delivered in source code; thus, the graphics library may be extended to accommodate EGA or VGA formats. An optional debugger (REM86) is available for target use and functions via the serial communication line.
Although the debugger commands are line oriented and remind me of the now obsolete Microsoft SYMDEB, it has a powerful operation mode called "F-mode." In this mode, FUTURE86 commands may be entered interactively, and it is even possible to compile new words. In this respect FDT86E acts similarly to an interactive Forth environment and has proven useful for debugging the example programs. For more information, contact Development Associates, 1520 South Lyon, Santa Ana, CA 92705.
The implementation used was the PC-DOS version of CDL2LAB from the German company epsilon. Several other versions are available from epsilon, including versions for OS/2 (IBM PS/2), VMS (VAX), NOS(Cyber 180), BSD Unix (VAX), and Unix V (Sun 3/50, PCS Cadmus, Nixdorf Targon). Code generators for cross compilation are also available for TOS (Atari) and even the good old CP/M.
CDL2LAB extends the CDL2 compiler by providing an integrated environment, grouped around a central database. Documentation is available in English. For further information on CDL2, contact epsilon, Kurfurstendamm 188/189, D1 Berlin 15, W. Germany.
Availability
All source code for articles in this issue is available on a single disk. To order, send $14.95 (Calif. residents add sales tax) to Dr. Dobb's Journal, 501 Galveston Dr., Redwood City, CA 94063; or call 800-356-2002 (from inside Calif.) or 800-533-4372 (from outside Calif.). Please specify the issue number and format (MS-DOS, Macintosh, Kaypro).
Variable-Level Programming by Ronald Fisher
[LISTING ONE]
Copyright © 1989, Dr. Dobb's Journal<a name="0117_000b">
#include <dos.h>
#define AUXOUT 4 /* DOS function id for aux.output */
void auxout(char c)
/* Function: Sends character c to auxiliary output */
{ bdos(AUXOUT,c,0); /* generate INT 21 */ }
<a name="0117_000c"><a name="0117_000c">
<a name="0117_000d">[LISTING TWO]<a name="0117_000d">
#include <string.h>
extern char xtrans(char c);
char *sfilt(char *source, char *target)
/* Appends source to target and applies function xtrans to */
/* every character appended. */
{
if(*source) /* check if length of source > 0 */
{
/* find terminating 0 of target string */
char *end_of_target = target+strlen(target);
/* replace terminating 0 by transformed first char of source */
*(end_of_target++) = xtrans(*source);
/* add new terminating 0 to target - hope we have enough room */
*end_of_target = '\0';
/* drop leading character from source and call sfilt again */
sfilt(strcpy(source,source+1),target);
}
/* we are done! */
return target;
}
<a name="0117_000e"><a name="0117_000e">
<a name="0117_000f">[LISTING THREE]<a name="0117_000f">
\ Synopsis: c AUXOUT
\ Stack diagram: c ---
\ Function: Sends c to serial output device AUX
AUXOUT-FUN EQU 4 \ Function code for serial output
: AUXOUT
!DL \ load c into DL
AUXOUT-FUN \ load function code
INT_21H ; \ call DOS
<a name="0117_0010"><a name="0117_0010">
<a name="0117_0011">
[LISTING FOUR]<a name="0117_0011">
\ String transformation
\ Synopsis: destination, source SFILT
\ Stack flow: sinfo1 sinfo2 --- sinfo1'
\ Function: Appends string referred to by sinfo2 to string sinfo1
\ and applies transformation function XTRANS to every character
\ of the source string. Returns updated sinfo1.
DEST DSB 80 \reserve 80 char string buffer
TEMP DSB 80 \provide temporary buffer space for 2nd string
: XTRANS ; \empty definition of arbitrary transformation function
\input is sinfo1 sinfo2; output is sinfo1+sinfo2(transformed)
: SFILT
SLEN \sinfo1 sinfo2 --- sinfo1 sinfo2 stringlength2
IF \compare length of source string to zero
CGET \ not zero: --- sinfo1 sinfo2' char
XTRANS \ apply transformation: --- sinfo1 sinfo2' char'
\stack has sinfo1, sinfo2, trsanslatedchar
>R \save chr
SSWAP \sinfo2 sinfo1
R> \get chr
C+ \append chr to sinfo1
SSWAP \sinfo1 sinfo2
\next instruction is assembler...if we use high level call linkage
\there is danger of return stack overflow...this way is stable
JMPS SFILT \recursively call til entire string scanned
ELSE
SDROP \ string exhausted...discard sinfo
THEN ; \complete
: DEST-INIT \ --- sinfo1
"You know that " ;
: SOURCE \ --- sinfo2
"Some different alpha characters are commonly used in Germany." ;
: SETUP \ --- sinfo
DEST-INIT DEST SCOPY ; \copy string to string buffer
\main procedure
: MAIN
SETUP \initialize destination area
SOURCE SFILT \translate and append source
SPRINT ; \output result to console
\ Define MAIN as startup routine:
END MAIN
<a name="0117_0012"><a name="0117_0012">
<a name="0117_0013">[LISTING FIVE]<a name="0117_0013">
MODULE string handling.
LAYER main layer.
SECTION string transformers.
....
ENDSEC string transformers.
SECTION char transformers.
....
ENDSEC char transformers.
ENDLAY main layer.
ENDMOD string handling.
<a name="0117_0014"><a name="0117_0014">
<a name="0117_0015">[LISTING SIX]<a name="0117_0015">
CONST auxout fun = 4. # DOS function code 'serial output' #
# Synopsis: auxout +c #
# Function: Sends character c to device AUX #
# Note: AUX defaults to COM1. This assignment may be #
# changed by the MODE command of DOS #
ACTION auxout +>c :
loadax +auxout fun,
loaddl +c,
int21.
# The syntax of the following terminal productions depends #
# on the code generator used. #
ACTION loadax +>value = "MOV AX," value.
ACTION loaddl +>value = "MOV DL," value.
ACTION int21 = "INT 21H".
<a name="0117_0016"><a name="0117_0016">
<a name="0117_0017">
[LISTING SEVEN]<a name="0117_0017">
# Synopsis: sfilt +source string +target string #
# Function: Appends source to target string by applying #
# transformation 'xtrans' to every character of #
# source string #
VAR first char . # temporary variable to hold one char #
ACTION sfilt +>source +>target> :
nullstring +source; # finish when source=NULL #
(but first +source +first char,# else drop first char #
xtrans +first char, # translate it #
append char +first char+target,# append to target #
sfilt +source +target). # repeat the process #
# Refinement. Note that the following base words have to be #
# expanded by appropriate assembler statements. #
TEST nullstring +>string = ........ # test if string=NULL #
ACTION but first +>string> +char> = .........
# move head of string to char #
ACTION xtrans +>a char> = ......... # translate 'a char' #
ACTION append char +>char +>str>=.. # append char to str #
