Horizontal drilling in soft soil provides an efficient and cost effective solution for the installation of utilities. However, with the increased congestion of underground utilities, the probability of damaging mislocated or unknown utilities increases, reducing the financial benefits of this technology and increasing the possibility catastrophic damage such as striking gas lines. It is hence important to develop instrumentation that is capable of locating obstacles lying along the bore paths. This paper discusses the development of a obstacle avoidance system based on ground penetrating radar technology. The system is a stepped frequency continuous wave (SFCW) radar that has been designed to fit within a standard 2.75 inch diameter drill head. The only above-ground components are the human machine interface (HMI) and power supply. Communication and power are transmitted underground via a wireline technique. An advanced demonstration model has been built and tested. The paper provides an overview of the requirements of an obstacle avoidance radar system. This is followed by a brief discussion of radar and antenna development required to implement the system. Finally results of indoor and outdoor field trials will be provided.

Abstract The core of the Microsoft .NET platform includes a new virtual machine (VM), the Common Intermediate Language, also known as MSIL. Unlike most other VMs, including the Java VM, MSIL is specifically designed to support a wide range of languages. While it is designed primarily for type‐safe, object‐oriented languages, it also has facilities that support both low‐level languages and very high‐level languages. For example, it accommodates unsafe pointer arithmetic and tail calls. This paper describes the implementation of a MSIL back end for lcc, a retargetable compiler for Standard C. C is at one end of the range of languages that MSIL intends to support and lcc is just about the simplest ‘real’ C compiler that is widely available. Porting lcc to MSIL thus provides a realistic test of how well MSIL supports this class of languages and provides a glimpse at its performance costs. This effort succeeded, but static initializations, function pointers, separate compilation and address arithmetic were major problem areas. These problems also suggested improvements to lcc's code‐generation interface and they exposed a long‐standing error in the lcc front end. Preliminary measurements suggest that programs compiled by the MSIL back end run two to three times slower than those compiled by lcc native Intel x86 back end, but the MSIL programs have some important diagnostic benefits. Copyright © 2003 John Wiley & Sons, Ltd.

Abstract C# is the new flagship language in the Microsoft .NET platform. C# is an attractive vehicle for language design research not only because it shares many characteristics with Java, the current language of choice for such research, but also because it is likely to see wide use. Language research needs a large investment in infrastructure, even for relatively small studies. This paper describes a new C# compiler designed specifically to provide that infrastructure. The overall design is deceptively simple. The parser is generated automatically from a possibly ambiguous grammar, accepts C# source, perhaps with new features, and produces an abstract syntax tree, or AST. Subsequent phases—dubbed visitors—traverse the AST, perhaps modifying it, annotating it or emitting output, and pass it along to the next visitor. Visitors are specified entirely at compilation time and are loaded dynamically as needed. There is no fixed set of visitors, and visitors are completely unconstrained. Some visitors perform traditional compilation phases, but the more interesting ones do code analysis, emit non‐traditional data such as XML, and display data structures for debugging. Indeed, most usage to date has been for tools, not for language design experiments. Such experiments use source‐to‐source transformations or extend existing visitors to handle new language features. These approaches are illustrated by adding a statement that switches on a type instead of a value, which can be implemented in a few hundred lines. The compiler also exemplifies the value of dynamic loading and of type reflection. Copyright © 2004 John Wiley & Sons, Ltd.

Most programming languages use static scope rules for associating uses of identifiers with their declarations. Static scope helps catch errors at compile time, and it can be implemented efficiently. Some popular languages—Perl, Tel, TeX, and Postscript—offer dynamic scope, because dynamic scope works well for variables that “customize” the execution environment, for example. Programmers must simulate dynamic scope to implement this kind of usage in statically scoped languages. This paper describes the design and implementation of imperative language constructs for introducing and referencing dynamically scoped variables—dynamic variables for short. The design is a minimalist one, because dynamic variables are best used sparingly, much like exceptions. The facility does, however, cater to the typical uses for dynamic scope, and it provides a cleaner mechanism for so-called thread-local variables. A particularly simple implementation suffices for languages without exception handling. For languages with exception handling, a more efficient implementation builds on existing compiler infrastructure. Exception handling can be viewed as a control construct with dynamic scope. Likewise, dynamic variables are a data construct with dynamic scope.

The Abstract Syntax Description Language (ASDL) is a language for specifying the tree data structures often found in compiler intermediate representations. The ASDL generator reads an ASDL specification and generates code to construct, read and write instances of the trees specified. Using ASDL permits a compiler to be decomposed into semi-independent components that communicate by reading and writing trees. Each component can be written in a different language, because the ASDL generator can emit code in several languages, and the files written by ASDL-generated code are machine- and language-independent. ASDL is part of the National Compiler Infrastructure project, which seeks to reduce dramatically the overhead of computer systems research by making it much easier to build high-quality compilers. This paper describes dividing lcc, a widely used retargetable C compiler, into two components that communicate via trees defined in ASDL. As the first use of ASDL in a ‘real’ compiler, this experience reveals much about the effort required to retrofit an existing compiler to use ASDL, the overheads involved, and the strengths and weaknesses of ASDL itself and, secondarily, of lcc. Copyright © 1999 John Wiley & Sons, Ltd.

Most debuggers are notoriously machine-dependent, but some recent research prototypes achieve varying degrees of machine-independence with novel designs. Cdb, a simple source-level debugger for C, is completely independent of its target architecture. This independence is achieved by embedding symbol tables and debugging code in the target program, which costs both time and space. This paper describes a revised design and implementation of cdb that reduces the space cost by nearly one-half and the time cost by 13 per cent by storing symbol tables in external files. A symbol table is defined by a 31-line grammar in the Abstract Syntax Description Language (ASDL). ASDL is a domain-specific language for specifying tree data structures. The ASDL tools accept an ASDL grammar and generate code to construct, read, and write these data structures. Using ASDL automates implementing parts of the debugger, and the grammar documents the symbol table concisely. Using ASDL also suggested simplifications to the interface between the debugger and the target program. Perhaps most important, ASDL emphasizes that symbol tables are data structures, not file formats. Many of the pitfalls of working with low-level file formats can be avoided by focusing instead on high-level data structures and automating the implementation details. Copyright © 1999 John Wiley & Sons, Ltd.

cdb is a simpe, source-level debugger for ANSI/ISO C programs compiled by lcc, a retargetable C compiler. cdb is completely independent of its target architecture. This independence is achieved by embedding a small amount of itself — a nub — in the program to be debugged and by having the compiler emit machine-independent symbol-table data and related code. This paper describes the design of a nub interface for debugging, a target-independent implementation of this interface for cdb, and the implementation of cdb itself. When compared to platform-specific debuggers, cdb's implementation is minuscule: the nub, debugger, and associated communications routines take about 1500 lines of C, and fewer than 600 lines were added to lcc's front end to emit symbol tables and breakpoint hooks. All this code is machine independent.

EZ is a system that integrates traditional operating systems and programming languages into a very-high-level persistent string processing language. The authors describe the design and initial implementation of a distributed memory manager that distributes EZ's virtual address space transparently among a network of homogeneous computers. The design adapts the techniques used in recent implementation of shared virtual memory for use in EZ's persistent environment. Unlike most implementations of shared virtual memory, control information is distributed and migrates. This memory manager works in concert with a distributed mark-and-sweep garbage collector, which is also concurrent and real-time. This collector trades time for space and minimal disruption of mutators, which reduces communication costs.>

We are developing techniques for building retargetable debuggers. Our prototype, 1db, debugs C programs compiled for the MIPS R3000, Motorola 68020, SPARC, and VAX architectures. It can use a network to connect to faulty processes and can do cross-architecture debugging. 1db's total code size is about 16,000 lines, but it needs only 250–550 lines of machine-dependent code for each target.

Abstract Copying garbage collectors are becoming the collectors of choice for very high‐level languages and for functional and object‐oriented languages. Copying collectors are particularly efficient for large storage regions because their execution time is proportional only to the amount of accessible data, and they identify and compact this data in one pass. In contrast, mark‐and‐sweep collectors execute in time proportional to the memory size and compacting collectors require another pass to compact accessible data. The performance of existing systems with old compacting mark‐and‐sweep collectors might be improved by replacing their collectors with copying collectors. This paper explores this possibility by describing the results of replacing the compacting mark‐and‐sweep collector in the Icon programming language with four alternative collectors, three of which are copying collectors. Copying collectors do indeed run faster than the original collector, but at a significant cost in space. An improved variant of the compacting mark‐and‐sweep collector ran even faster and used little additional space.

Abstract This paper describes the management of register spills in a retargetable C compiler. Spills are rare, which means that testing is a bigger problem than performance. The trade‐offs have been arranged so that the common case (no spills) generates respectable code quickly and the uncommon case (spills) is less efficient but as simple as possible. The technique has proven practical and is in production use on VAX, Motorola 68020, SPARC and MIPS machines.

Abstract 1cc is a retargetable, production compiler for ANSI C; it has been ported to the VAX, Motorola 68020, SPARC, and MIPS R3000, and some versions have been in use for over a year and a half. It is smaller and faster than generally available alternatives, and its local code is comparable. This paper describes the interface between the target‐independent front end and the target‐dependent back ends. The interface consists of shared data structures, a few functions, and a dag language. While this approach couples the front and back ends tightly, it results in efficient, compact compilers. The interface is illustrated by detailing a code generator that emits naive VAX code.

Abstract Dynamic storage‐management algorithms are based either on object sizes or object lifetimes. Stack allocation, which is based on object lifetimes, is the most efficient algorithm, but severely restricts object lifetimes and creation times. Other algorithms based on object sizes, such as first fit and related algorithms, permit arbitrary lifetimes but cost more. More efficient variations capitalize on application‐specific characteristics. Quick fit, for example, is more efficient when there are only a few object sizes. This paper describes a simple algorithm that is very efficient when there are few object lifetimes. In terms of instructions executed per byte allocated, the algorithm is almost half the cost of quick fit and less than twice the cost of stack allocation. Space for all objects with the same lifetime is allocated from a list of large arenas, and the entire list is deallocated at once. An implementation in ANSI C is included.

EZ is a language-based programming environment that offers the services provided separately by programming languages and operating systems in traditional environments. These services are provided as facilities of a high-level string processing language with a 'persistent' memory in which values exist indefinitely or until changed. In EZ, strings and associative tables provide traditional file and directory services. This paper concentrates on the use of EZ procedures and their activations, which, like other values, have indefinite lifetimes. In EZ, the low-level aspects of procedure execution, such as activation record creation, references to local variables, and access to state information, are accessible via high-level language constructs. As a result, traditionally distinct services can be provided by a single service in the EZ environment. Furthermore, such services can be written in EZ itself. An editor/debugger that illustrates the details of this approach is described.

Abstract Compiler writing tools, such as parser generators, are‐commonly used to build new operators. Nevertheless, constructing compilers by hand remains common. Such compilers are often built using recursive‐descent parsing for most of the language and operator‐precedence parsing for expressions. This paper describes a simple technique for parsing expressions using recursive descent that avoids the usual proliferation of procedures that occurs when recursive descent is used to parse expressions. By taking advantage of the similarity of the productions describing expressions in most languages, the n + 1 procedures usually required to parse expressions with n precedence levels can be replaced with a table and two procedures.

Abstract Program optimization has received a great deal of attention for many years, which has resulted in numerous advances in compiler technology. The effectiveness of various simple optimizations has received comparably little attention during the same time period. The simplicity of most programs suggests that straightforward optimizations pay the greatest dividends. This paper describes three such optimizations suitable for one‐pass compilers. The optimizations involve expression rearrangement, instruction selection, and the use of a cache for the allocation of resources. The cost of these optimizations is low; none require major changes to the size or structure of the compiler or reduce compilation speed by more than 10%. The benefits are high; each optimization results in at least a 10% average reduction in object code size and a corresponding reduction in execution time. Examples and implementation details are also described.

The importance of the ability to measure the performance of programs written in high-level languages is well known. Performance measurement enables users to locate and correct program inefficiencies where automatic optimizations fail and provides a tool for understanding program behavior. This paper describes performance measurement facilities for the Icon programming language, and shows not only how these facilities provided insight into program behavior, but also how they were used to improve the implementation.

Abstract Linkers, although a well‐established component of language translation, are typically machine‐dependent, idiosyncratic, and hard for many users to understand. This paper describes a machine‐independent linker and object language. The linker embodies those linking functions that are machine‐independent and centralizes them in a single tool, simplifying compilers, assemblers, and loaders. Included are descriptions of its operation, implementation, and application.

Abstract Increasingly powerful machine instructions complicate abstract machine design for portability. Abstract machine instructions must be “larger” than the target machine instructions that they are to exploit, but they must not grow so large as to complicate the realization of the abstract machine on real machines. This paper presents related techniques for low‐level yet machine‐independent access to typical stack and string‐processing instructions.

Abstract Block structure is traditionally considered an a priori requirement for algorithmic programming languages. Most new languages since Algol‐60 have block structure. Reasons exist, however, to omit the general form of block structure‐nested procedure definitions in which references to identifiers defined in outer procedures are permitted‐from programming languages, especially those intended for systems programming applications. This paper reviews the concept of block structure and considers its advantages and disadvantages. It concludes that, in many cases, a module facility is superior to block structure and should be considered in lieu of block structure in future languages.

Icon is a new programming language that includes a goal-directed expression evaluation mechanism.This mechanism is based on generators--expressions that are capable of producing more than one value.If the value produced by a generator does not lead to a successful result, the generator is automatically activated for an alternate value.Generators form an integral part of Icon and can be used anywhere.In addition, they form the basis for the string scanning facility and subsume some of the control expressions found in other languages.Several examples are given.

PDS is a set of procedures that provides a machine-independent method of file specification.PDS provides capabilities beyond those provided by many vendorsupplied systems.In addition, because PDS is portable, additional capabilities, such as protection schemes, file usage statistics, or some of the functions of a source code control system [5], can be added easily.The basic function of PDS is to maintain a useful directory structure and provide a set of primitives for manipulating that structure.The PDS directory structure is identical to the tree structure of the UNIX [4] file system, and many of the PDS primitives are identical to UNIX primitives.PDS is, in large part, a portable implementation of the UNIX directory system.Besides PDS's machineindependence, the major differences are the extensibility of PDS and, as described in the next section, its i/o independence.In the simplest terms, PDS provides a directory structure and a mapping from machine-independent file names to machine-dependent names.It deals only with the information describing a file; it does not use or manipulate actual files in any way.The importance of this approach is that PDS is used to specify a file but does not participate in the actual i/o to that file.Consequently, there is no impact on i/o efficiency when PDS is used.PDS manipulates a rooted tree structure in which the leaves are files or directories and the nodes are directories.A directory is simply a list of files and directories.An example is shown in Figure 1, in which circles indicate directories and squares indicate files.The root of the tree is denoted by "/", and files and directories are denoted by their "path," which specifies their absolute position in the tree.A path is composed of the names of the nodes on the path from the root

Abstract Icon is a new programming language designed primarily for non‐numerical applications. Its roots are in SNOBOL4 and SL5; as in those languages, execution‐time flexibility is an important attribute of Icon, although some aspects of programs are bound at compile time to improve efficiency. Icon, which is implemented in Ratfor, is also intended to be portable and suitable for 16‐bit computers. The storage management system in Icon is designed to meet the goals of portability, flexibility and efficiency. This is accomplished by subdividing the storage management system into a set of type‐specific storage management subsystems. This paper describes the implementation of these subsystems, their interaction, and their performance.

Abstract A portable file directory system that provides a machine‐independent method for specifying files is described. The portable directory system, or PDS, facilitates uniform usage of portable software by supplying a standard for file specification. The PDS supports a hierarchical directory structure, similar to that in UNIX and Multics, and a set of primitives for manipulating the structure and preparing files for input/output. While the PDS participates in file specification, it does not participate in the actual i/o; it has no impact on i/o efficiency. The implementation, which is easily extended to include additional capabilities, is described. Experience in using the PDS as a part of command interpreters and preprocessors is also discussed.

SNOBOL4 is best known for its string processing facilities, which are based on patterns as data objects. Despite the demonstrated success of patterns, there are many shortcomings associated with their use. The concept of patterns in SNOBOL4 is examined and problem areas are discussed. An alternative method for high-level string processing is described. This method, implemented in the programming language Icon, employs generators , which are capable of producing alternative values. Generators, coupled with a goal-driven method of expression evaluation, provide the string processing facilities of SNOBOL4 without the disadvantages associated with patterns. Comparisons between SNOBOL4 and Icon are included and the broader implications of the new approach are discussed.

Abstract A simple technique for communication among separately compiled modules using the existing facilities of most operating systems is proposed. The access control capabilities of existing hierarchical file systems can be used to control access to shared objects (e.g. procedures, types, data structures). Information about shared objects, such as type and date/time of compilation, is stored in description files, and access to a description file implies access to those objects. Declarations cause the appropriate information to be maintained in the description files. The advantage of this approach is that it is based on existing mechanisms with which most programmers are well acquainted.

The filter facility of the SL5 programming language permits the programmer to attach a procedural component to a variable. This procedural component can be used to ‘filter’ values assigned to the variable or to filter the value of the variable whenever it is fetched. Filters are the basis for the inclusion, at the source language level, of such features as tracing, dynamic datatype checking, generators, and dynamic protection mechanisms. Most importantly, filters are used for argument binding, permitting various methods of argument transmission to be defined in SL5 itself. This paper gives an overview of SL5, describes the filter facility, and gives several examples of its use.

Abstract An event association facility for the SNOBOL4 programming language is described. This facility permits the execution of a programmer‐defined function to be associated with the occurrence of a specified event. The events with which associations can be made are those applicable to program debugging. Associations can be made with events such as variable referencing, statement execution, program interruption, function call and return, and execution‐time errors. By making event associations available at the source‐language level, debugging aids can be written in SNOBOL4 itself, using the full capabilities of that language. As illustrated by several examples, this approach facilitates the implementation of simple yet powerful debugging aids written in the same language as the programs to be debugged. Event associations provide a mechanism for the unification of the existing SNOBOL4 debugging facilities, and a basis for the addition of other events. The implementation of event associations is also described.

Results of measuring the performance of the storage management subsystem in an implementation of SNOBOL4 are described. By instrumenting the storage management system, data concerning the size, lifetime, and use of storage blocks were collected. These data, like those obtained from conventional time measurement techniques, were used to locate program inefficiencies. In addition, these measurements uncovered some deficiencies in the storage management system, and provided the basis upon which to judge the heuristics used in the garbage collector.

Abstract The implementation of the SNOBOL4 programming language requires some scheme for dynamic allocation and reclamation of storage. This paper describes the method used in a machine‐dependent implementation of SNOBOL4 called SITBOL. Available storage is divided into two regions: one for the allocation of storage for permanent or immovable objects and one for objects that are subject to reclamation. Reclamation is accomplished by a four‐phase algorithm, which includes marking, address adjustment and compaction. The reclamation process is supplemented by several heuristics that reduce the cost of reclamation and increase the amount of storage reclaimed. The storage overhead of the technique is analysed and compared with an alternate method. Some empirical measurements of actual SNOBOL4 programs are given that substantiate the results of the analysis.

Abstract Adaptable programs are one of the benefits of structured programming. The adaptability of a program is the degree to which it can be transformed into another program that performs a similar, but slightly different, function. While it is clear that the aims of structured programming are best satisfied by the use of modern programming languages, a great number of programmers must use languages such as Fortran. To alleviate this situation, a number of preprocessors have been introduced that give Fortran a more structured facade. This paper describes an experiment performed to test the adaptability of programs written in RATFOR, one of these preprocessors. Judging from the results, the use of a good preprocessor can significantly increase the adaptability of Fortran programs.

SL5 is a programming language developed for experimental work in generalized pattern matching and high-level data structuring and access mechanisms. This paper describes the procedure mechanism and the conventions for the interpretation of identifiers in SL5. Procedure invocation in SL5 is decomposed into the separate source-language operations of context creation, argument binding and procedure activation, and allows SL5 procedures to be used as recursive functions or coroutines. This decomposition has led to rules for scoping and for the interpretation of identifiers that are different from those found in other programming languages. Several examples of SL5 procedures are given, including a scanner based on the coroutine model of pattern matching.

Abstract This paper describes a new facility in the SNOBOL4 programming language that provides the capability to associate the execution of a programmer‐defined function with the act of assigning a variable a value or retrieving the value of a variable. The facility, called programmer‐defined variable association, subsumes the existing built‐in associations used for input, output and value tracing and provides, at the source‐language level, the protection and datatype coercion mechanisms used in keywords. Several applications are described that illustrate the usefulness of this addition to the language. The facility is especially useful for program monitoring and debugging. The implementation of this facility and the effect of implementation techniques on programming language design are also discussed.