An optimizing compiler for the icon programming language

Compiling code for the Icon programming language presents several challenges, particularly in dealing with types and goal-directed expression evaluation. In order to produce optimized code, it is necessary for the compiler to know much more about operations than is necessary for the compilation of most programming languages. This paper describes the organization of the Icon compiler and the way it acquires and maintains information about operations. The Icon compiler generates C code, which makes it portable to a wide variety of platforms and also allows the use of existing C compilers for performing routine optimizations on the final code. A specially designed implementation language, which is a superset of C, is used for writing Icon's run-time system. This language allows the inclusion of information about the abstract semantics of Icon operations and their type-checking and conversion requirements. A translator converts code written in the run-time language to C code to provide an object library for linking with the code produced by the Icon compiler. The translation process also automatically produces a database that contains the information the Icon compiler needs to generate and optimize code. This approach allows easy extension of Icon's computational repertoire, alternate computational extensions, and cross compilation.     

Result sequences

Expression evaluation in conventional programming languages may be viewed as a simplification of expression evaluation in the Icon programming language. The evaluation of an expression in Icon may yield a sequence of results. Goal-directed evaluation causes expressions to produce these results in an attempt to produce the successful evaluation of an enclosing expression. There are control operations that operate on result sequences. The study of expression evaluation in Icon therefore is more interesting than it is in most programming languages. This paper introduces a notation for result sequences and shows how it can be used to describe the static aspects of expression evaluation. Equivalences among control operations and expressions are demonstrated.     

Logicon: An integration of prolog into icon

This paper describes the coupling of logic programming with Icon, which is a programming language aimed at string processing. Icon and Prolog have many similarities and their integration is feasible and desirable because the weaknesses of one can be compensated for by the strengths of the other. In our case, a Prolog interpreter was written as an Icon procedure that can be linked and called by an Icon program. This interpreter deals with all Icon data types and can be called in the context of the goal-directed evaluation of Icon. We give an example showing the power of this symbiosis between these two languages where a Prolog call in Icon is a generator and an Icon call in a Prolog clause is a built-in predicate.     

Chicon—a Chinese text manipulation language

Text processing is an important computer application. Due to its importance, a number of text manipulation programming languages have been devised (e.g. Icon). These programming languages are very useful for applications such as natural language processing, text analysis, text editing, document formatting, text generation, etc. However, they were mainly designed to handle English texts, and are ineffective for Chinese. This is because English and Chinese texts are represented very differently in a computer. An English character is mainly represented in 7-bit ASCII, and its Chinese counterpart commonly in 16-bit GB or BIG-5. This difference makes direct application of English-based text manipulation programming languages to Chinese erroneous, e.g. application of Icon to reverse a string of Chinese characters. In this paper, a new dialect of Icon, referred to as Chicon (i.e. Chinese Icon), is proposed. In the design of Chicon, new data types were introduced to differentiate pure English and English/Chinese mixed texts. In addition, existing Icon text manipulation functions were modified to account for Chinese texts. Experiments have shown that Chicon not only could overcome the problems of Chinese processing in Icon, but its execution speed was actually superior to Icon in handling Chinese. Furthermore, application of Chicon to a real sized problem, namely word segmentation, has proved that the language is practical. © 1998 John Wiley & Sons, Ltd.     

A portable storage management system for the icon programming language

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.     

The Alamo Execution Monitor Architecture

Future programming environments will incorporate a tighter coupling between language runtime systems and the monitoring tools that are used to debug, tune, visualize, and understand them. Many innovations that are developed first in higher level programming language environments will migrate into mainstream languages once their properties are understood and generalized.

The Alamo execution monitor architecture was developed to facilitate rapid development of execution monitors, especially visualization tools that are instrumental in understanding complex runtime system interactions in higher level languages. Alamo simplifies the development of such tools by solving the low-level access, control, and intrusion problems inherent in monitoring.

Alamo was implemented first for the very high-level imperative goal-directed language Icon. The architecture was then implemented for ANSI C in order to broaden the impact of the work. This paper describes the ANSI C implementation of Alamo and the monitoring services it provides.     

Measuring the Performance and Behavior of Icon Programs

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.     

An intermediate language to define dynamic semantics

An instruction set is given for an abstract machine which uses a pushdown stack as its principal memory. The proposed instructions serve the similar purposes of (1) defining the dynamic semantics of programming languages by describing the operations of programs on the abstract machine and (2) describing an intermediate language to be used in compiling programming languages into machine language. It is shown how the intermediate language can be used in the translation of the programming languages ADA, FORTRAN and PASCAL into IBM 360 assembly language and advantages over other intermediate languages such as three-address code and P-code.     

A simple system for constructing distributed,mixed-language programs

The Mixed-Language Programming (MLP) System is a simple system that facilitates construction of sequential programs in which procedures can be written in different programming languages to exploit heterogeneity in language functionality. In addition, MLP provides a simple remote procedure call (RPC) facility that allows heterogeneity in machine functionality to be exploited. To minimize implementation cost, the system does not solve all of the problems related to mixed-language programming; rather, MLP is designed to handle common situations well. Among the unique aspects of MLP are its advanced facilities, which allow complex situations to be handled with user intervention; for example, these facilities allow arguments of a type not defined by a language to be used by procedures written in that language. This paper overviews the use of MLP and describes its implementation. In addition, two programs that have been written using the MLP system—a small database system and a collection of plot routines—are discussed. The system executes on a collection of Vaxes and Suns running Berkeley UNIX. Currently supported languages are C, Pascal and Icon.     

用于漏洞检测的中间语言表示方法

现有Web漏洞检测方法中使用的中间语言针对特定编程语言设计,在对多种编程语言源代码进行漏洞抽象表示时,无法将多语言下的同类型漏洞用统一的中间语言表示,增加了后续漏洞分析处理的难度。针对该问题提出了一种基于污点分析的中间语言表示方法,实现多编程语言下同类型漏洞信息的统一抽象表示。该中间语言设计过程中将漏洞发生过程抽象为三元组表示,将与三元组相关的代码元素抽象为中间语言的关键字,根据三元组间的语义关系设计了该中间语言的语法。在转义时,利用污点分析方法跟踪污染源的执行路径,对路径中的源代码进行转义得到中间语言表示。最后将该中间语言用于漏洞检测模型,实验结果表明该中间语言与对照中间语言相比对编程语言中漏洞信息的抽象表示更具普适性,对漏洞检测具有有效性。     

Portable real-time software for 8-bit microprocessors

This paper discusses a method for developing efficient and portable software for 8-bit microprocessors used in real-time applications. The technique used is to design an ‘intermediate level language’ (ILL) which defines low-level primitives to support the real-time application programming and the constructs of high level languages. Thus, the high level language (HLL) program goes through two stages of translation; first to the ILL code and then to the machine code of a microprocessor. The ILL instruction set developed bridges the gap between high level languages and the poor instruction set of microprocessors. This allows the development of optimized and portable code for the microprocessors. The ILL operations, data types, data organization, control structures, synchronization, communication and multi-tasking facilities are described. The effectiveness of this technique is shown by comparing the code generated by the ILL approach with the code available for a sample real-time application written directly in assembly level language.     

The implementation of generators and goal-directed evaluation in icon

Two features of the Icon programming language strongly influence its implementation: generators and goal-directed evaluation. A generator is an expression that is capable of producing a sequence of results. In goal-directed evaluation, the results of generators are produced automatically in an attempt to complete computations successfully. This paper describes the generated code and run-time support for generators, goal-directed evaluation, and related control structures.     

Adding graphics to a high-level programming language

When graphics input/output capabilities are added to a programming language originally designed with a text stream input/output model, various design decisions affect the ease with which the graphics facilities are learned and used by applications programmers. In adding window system facilities to the Icon programming language, some design decisions were made very differently from the conventional wisdom, resulting in substantial benefits for programmers. In addition, some pre-existing Icon language features have proved to be useful in graphics programming.     

Linking assembly code to PASCAL programs for microprocessors

High level languages used for programming microprocessors still need some assembly code to cover all the programming requirements and aspects. Using assembly code in a high level language program introduces certain difficulties and disadvantages. Practical suggestions to minimise the use of assembly code procedures in a high level language program is presented. (The high level language discussed is pascal/64000.)     

基于标记语言的并行多核编程方法

提出一种在多核平台上的快速多线程编程模型ThreadXML。该模型通过使用标记语言形式,提高程序的开发效率,支持可视化,增强并行程序设计的移植性。其中,语言模型编译器的实现采用代码模板技术和面向对象技术相结合的方式,能将ThreadXML源代码转换成目前可执行的程序代码,辅助可视化工具采用图元对象和代码模板技术实现。     

A unifying approach to goal-directed evaluation

Goal-directed evaluation, as embodied in Icon and Snobol, is built on the notions of backtracking and of generating successive results, and therefore it has always been something of a challenge to specify and implement. In this article, we address this challenge using computational monads and partial evaluation. We consider a subset of Icon and we specify it with a monadic semantics and a list monad. We then consider a spectrum of monads that also fit the bill, and we relate them to each other. For example, we derive a continuation monad as a Church encoding of the list monad. The resulting semantics coincides with Gudeman’s continuation semantics of Icon. We then compile Icon programs by specializing their interpreter (i.e., by using the first Futamura projection), using type-directed partial evaluation. Through various back ends, including a run-time code generator, we generate ML code, C code, and OCaml byte code. Binding-time analysis and partial evaluation of the continuation-based interpreter automatically give rise to C programs that coincide with the result of Proebsting’s optimized compiler. Basic Research in Computer Science (www.brics. dk), funded by the Danish National Research Foundation. Olivier Danvy, Ph.D., Habilitation: He is an Associate Professor at the Department of Computer Science at the University of Aarhus, in Denmark. He obtained his Ph.D. degree in 1986 and his Habilitation in 1993 from the Université Pierre et Marie Curie (Paris VI), France. His research interests are in Programming Languages in general and in Partial Evaluation and Continuations in particular. He has published over 75 refereed research papers and edited several proceedings. He has both served on and chaired program committees of scientific meetings in the area of Programming Languages. He is presently chairing the PEPM steering committee at ACM SIGPLAN and serving as external reviewer in computer science for the Danish Universities, as board member in the BRICS PhD School, and as co-Editor-in-Chief of the journal Higher-Order and Symbolic Computation (http://www.wkap.nl/journals/hosc). Bernd Grobauer, M.Sc.: He is a Ph.D. student at the BRICS International Ph.D. school, University of Aarhus, Denmark, and will graduate in the summer of 2001. He obtained his Masters degree from the Munich University of Technology (TUM), Germany. His research interests are in formal methods (especially theorem proving) and programming languages (semantics of programming languages, program analysis, program transformation, types). He serves as editorial assistant for the journal Higher-Order and Symbolic Computation and as chairman of the BRICS Juniorklubben. Morten Rhiger, M.Sc.: He is a Ph.D. student at the BRICS International Ph.D. school, University of Aarhus, Denmark, and will graduate in the summer of 2001. He obtained his Masters degree from the University of Aarhus in 1998. His research interests are in the semantics and implementation of programming languages.     

The design and implementation of dynamic hashing for sets and tables in icon

Two key features in the Icon programming language are tables and sets. An Icon program may use one large set or table, or thousands of small ones. To improve space and time performance for these diverse uses, their hashed data structures were reimplemented to dynamically resize during execution, reducing the minimum space requirement and achieving constant-time access to any element for virtually any size set or table. The implementation is adapted from Per-Åke Larson's dynamic hashing technique by using well-known base-2 arithmetic techniques to decrease the space required for small tables without degrading the performance of large tables. Also presented are techniques to prevent dynamic hashing from interfering with other Icon language features. Performance measurements are included to support the results.