Looking for narrow interfaces in automatic differentiation using graph drawing

Automatic differentiation is a powerful technique for evaluating derivatives of functions given in the form of a high-level programming language such as Fortran, C, or C++. This technique is superior, in terms of accuracy, to numerical differentiation because it avoids the truncation error involved in divided difference approximations. In automatic differentiation, the program is treated as a potentially very long composition of elementary functions to which the chain rule of differential calculus is applied over and over again. Because of the associativity of the chain rule, there is room for different strategies computing the same numerical results but whose computational cost may vary significantly. Several strategies exploiting high-level structure of the underlying computer code are known to reduce computational cost as opposed to blindly applying automatic differentiation. An example includes “interface contraction” where one takes advantage of the fact that the number of variables passed between subroutines is small compared with the number of propagated directional derivatives. Unfortunately, these so-called narrow interfaces are not immediately available. The present study investigates the use of the VCG graph drawing tool to recognize narrow interfaces in the computational graph, a certain directed acyclic graph used to represent data dependences of variables in the underlying computer code.     

C高效程序设计的技巧

该文从基于8051核的MCU结构特征出发,结合C语言自身特点,给出若干高效C程序设计的技巧。实践证明,在C程序设计中依据8051的功能特性对源代码进行优化,能大幅度提高最终程序的执行效率。     

扩展的高层次行为描述内部模型

随着片上系统(SOC)技术的发展,越来越多的功能模块被集成到单一芯片中。适合硬件描述的HDL语言很难满足实现复杂算法功能的要求,C++等高级语言可以高效地描述算法功能,但是在综合和验证时遇到很大困难。文章介绍了一种允许使用C和VHDL独立描述原始模块,通过创建统一内部模型IIR的办法实现对功能元件和算法模块的混合处理。IIR内部模型以XML文件格式作为外部存储,能够方便地被划分、综合、验证等处理程序使用,避免了重复的原始描述文件分析,提高了研发效率。     

Algorithm-oriented generic libraries

We outline an approach to construction of software libraries in which generic algorithms (algorithmic abstractions) play a more central role than in conventional software library technology or in the object-oriented programming paradigm. Our approach is to consider algorithms first, decide what types and access operations they need for efficient execution, and regard the types and operations as formal parameters that can be instantiated in many different ways, as long as the actual parameters satisfy the assumptions on which the correctness and efficiency of the algorithms are based. The means by which instantiation is carried out is language dependent; in the C + + examples in this paper, we instantiate generic algorithms by constructing classes that define the needed types and access operations. By use of such compile-time techniques and careful attention to algorithmic issues, it is possible to construct software components of broad utility with no sacrifice of efficiency.     

Term Graphs for Computing Derivatives in Imperative Languages

Automatic differentiation is a technique for the rule-based transformation of a subprogram that computes some mathematical function into a subprogram that computes the derivatives of that function. Automatic differentiation algorithms are typically expressed as operating on a weighted term graph called a linearized computational graph. Constructing this weighted term graph for imperative programming languages such as C/C++ and Fortran introduces several challenges. Alias and definition-use information is needed to construct term graphs for individual statements and then combine them into one graph for a collection of statements. Furthermore, the resulting weighted term graph must be represented in a language-independent fashion to enable the use of AD algorithms in tools for various languages. We describe the construction and representation of weighted term graphs for C/C++ and Fortran, as implemented in the ADIC 2.0 and OpenAD/F tools for automatic differentiation.     

一种梯形图编程系统的研究与实现方法

详细阐述了一种梯形图编程系统的数据结构与实现方法.该系统选用Visual C 作为开发语言,实现了梯形图语言向指令表语言的转换、显示、编辑、以及语法、逻辑错误检测与处理以及程序传输等功能.该梯形图编程系统可用于多种现场测控设备如PLC、RTU等.     

Automatic Generation of Staged Geometric Predicates

Algorithms in Computational Geometry and Computer Aided Design are often developed for the Real RAM model of computation, which assumes exactness of all the input arguments and operations. In practice, however, the exactness imposes tremendous limitations on the algorithms—even the basic operations become uncomputable, or prohibitively slow. In some important cases, however, the computations of interest are limited to determining the sign of polynomial expressions. In such circumstances, a faster approach is available: one can evaluate the polynomial in floating-point first, together with some estimate of the rounding error, and fall back to exact arithmetic only if this error is too big to determine the sign reliably. A particularly efficient variation on this approach has been used by Shewchuk in his robust implementations of Orient and InSphere geometric predicates.We extend Shewchuk's method to arbitrary polynomial expressions. The expressions are given as programs in a suitable source language featuring basic arithmetic operations of addition, subtraction, multiplication and squaring, which are to be perceived by the programmer as exact. The source language also allows for anonymous functions; the use of such functions enables the common functional programming technique of staging. The method is presented formally through several judgments that govern the compilation of the source expression into target code, which is then easily transformed into SML or, in case of single-stage expressions, into C.     

Removing partial parametrization for efficient implementation of functional languages

This paper describes a program transformation technique for functional languages called removing partial parametrization. By transforming functional programs into equivalent ones without partial parametrization, each function is applied to the same number of arguments as its formal parameters. A new method of improving the efficiency of the implementation of functional language is to design the compiler according to the features of the program without partial parametrization. We have used this method in the environment-based implementation of the functional programming language LK. Programs run considerably faster and consume less memory space than traditional ones.     

Konrad Zuse's Plankalku¨l: the first high-level, “non vonNeumann” programming language

Konrad Zuse was the first person in history to build a working digital computer, a fact that is still not generally acknowledged. Even less known is that in the years 1943-1945, Zuse developed a high-level programming model and, based on it, an algorithmic programming language called Plankalku¨l (Plan Calculus). The Plankalku¨l features binary data structure types, thus supporting a loop-free programming style for logical or relational problems. As a language for numerical applications, Plankalku¨l already had the essential features of a “von Neumann language”, though at the level of an operator language. Consequently, the Plankalku¨l is in some aspects equivalent and in others more powerful than the von Neumann programming model that came to dominate programming for a long time. To find language concepts similar to those of the Plankalku¨l, one has to look at “non-von Neumann languages” such as APL or the relational algebra. This paper conveys the syntactic and semantic flavor of the Plankalku¨l, without presenting all its syntactic idiosyncrasies. Rather, it points out that the Plankalku¨l was not only the first high-level programming language but in some aspects conceptually ahead of the high-level languages that evolved a decade later     

Application of reflection in a model transformation language

Computational reflection is a well-known technique applied in many existing programming languages ranging from functional to object-oriented languages. In this paper we study the possibilities and benefits of introducing and using reflection in a rule-based model transformation language. The paper identifies some language abstractions to achieve structural and behavioral reflection. Reflective features are motivated by examples of problems derived from the experience with currently used transformation languages. Example solutions are given by using an experimental language with reflective capabilities. The paper also outlines possible implementation strategies for adding reflection to a language and discusses their advantages and disadvantages.     

Theory and practice of unparsed patterns for metacompilation

Several software development tools support the matching of concrete syntax user-supplied patterns against the application source code, allowing the detection of invalid, risky, inefficient or forbidden constructs. When applied to compilers, this approach is called metacompilation. These patterns are traditionally parsed into tree patterns, i.e., fragments of abstract-syntax trees with metavariables, which are then matched against the abstract-syntax tree corresponding to the parsing of the source code. Parsing the patterns requires extending the grammar of the application programming language with metavariables, which can be difficult, especially in the case of legacy tools. Instead, we propose a novel matching algorithm which is independent of the programming language because the patterns are not parsed and, as such, are called unparsed patterns. It is as efficient as the classic pattern matching while being easier to implement. By giving up the possibility of static checks that parsed patterns usually enable, it can be integrated within any existing utility based on abstract-syntax trees at a low cost. We present an in-depth coverage of the practical and theoretical aspects of this new technique by describing a working minimal patch for the GNU C compiler, together with a small standalone prototype punned Matchbox, and by lying out a complete formalisation, including mathematical proofs of key algorithmic properties, like correctness and equivalence to the classic matching.     

一种面向无线传感网应用重编程的逻辑式编程语言

无线传感网的发展,使其需要具有高效地更新其上运行的应用软件的能力.为了解决这个问题,提出了一种面向无线传感网应用重编程的逻辑式编程语言及其处理系统ReLog.ReLog语言根据无线传感网应用的普遍特点,基于传统逻辑式语言进行扩展,并提供合适的编程抽象,方便程序员高效地构建、修改程序.同时,语言的处理系统使用中间代码将应用程序与系统软件解耦,从而减少应用更新时所需传输的更新代码的规模,提高更新效率.通过一个数据收集应用案例评估了ReLog语言及其执行机制,结果表明：使用ReLog语言能够获得简洁、易修改的程序;同时,语言的执行机制能够显著降低传输应用更新代码的能量和时间开销.     

CBack: A simple tool for backtrack programming in C

Backtrack programming is such a powerful technique for problem solving that a number of languages, especially in the area of artificial intelligence, have built-in facilities for backtrack programming. This paper describes CBack, a simple, but general tool for backtrack programming in the programming language C. The use of the tool is illustrated through examples of a tutorial nature. In addition to the usual depth-first search strategy, CBack provides for the more general heuristic best-first search strategy. The implementation of CBack is described in detail. The source code, shown in its full length, is entirely written in ANSI C and highly portable across diverse computer architectures and C compilers.     

面向对象方法的多形性及其应用

多形性是将多个意义赋予同一名字的能力。在面向对象方法中,运用多形性可以大大提高开发软件的效率和质量。该文首先介绍了多形性的几种表现形式,然后着重通过几个具体的例子说明如何利用面向对象编程语言Ｃ＋＋中的虚函数机制来灵活运用多形性,最后对多形性的实质及不足之处作了探讨。     

SEMANOL (73) a metalanguage for programming the semantics of programming languages

Summary SEMANOL is a practical programming system for writing readable formal specifications of the syntax and semantics of programming languages. SEMANOL is based on a theory of semantics which embraces algorithmic (operational) and extensional (input/output) semantics. Specifications for large contemporary languages have been constructed in the formal language, SEMANOL (73), which is a readable high-level notation. A SEMANOL (73) specification can be executed (by an existing interpreter program); when given a program from the specified language, and its input, the execution of the SEMANOL (73) specification produces the program's output. The demonstrated executability of SEMANOL (73) provides important practical advantages. This paper includes discussions of the theory of semantics underlying SEMANOL, the syntax and semantics of the SEMANOL (73) language, the use of the SEMANOL (73) language in the SEMANOL method for describing programming languages, and the contrast between the Vienna definition method (VDL) and SEMANOL.     

Compiler Verification and Compiler Architecture

We study issues in verifying compilers for modern imperative and object-oriented languages. We take the view that it is not the compiler but the code generated by it which must be correct. It is this subtle difference that allows for reusing standard compiler architecture, construction methods and tools also in a verifying compiler.Program checking is the main technique for avoiding the cumbersome task of verifying most parts of a compiler and the tools by which they are generated. Program checking remaps the result of a compiler phase to its origin, the input of this phase, in a provably correct manner. We then only have to compare the actual input to its regenerated form, a basically syntactic process. The correctness proof of the generation of the result is replaced by the correctness proof of the remapping process. The latter turns out to be far easier than proving the generating process correct.The only part of a compiler where program checking does not seem to work is the transformation step which replaces source language constructs and their semantics, given, e.g., by an attributed syntax tree, by an intermediate representation, e.g., in SSA-form, which is expressing the same program but in terms of the target machine. This transformation phase must be directly proven using Hoare logic and/or theorem-provers. However, we can show that given the features of today's programming languages and hardware architectures this transformation is to a large extent universal: it can be reused for any pair of source and target language. To achieve this goal we investigate annotating the syntax tree as well as the intermediate representation with constraints for exhibiting specific properties of the source language. Such annotations are necessary during code optimization anyway.     

Efficient and accurate derivatives for a software process chain in airfoil shape optimization

When using a Newton-based numerical algorithm to optimize the shape of an airfoil with respect to certain design parameters, a crucial ingredient is the derivative of the objective function with respect to the design parameters. In large-scale aerodynamics, this objective function is an output of a computational fluid dynamics program written in a high-level programming language such as Fortran or C. Numerical differentiation is commonly used to approximate derivatives but is subject to truncation and subtractive cancellation errors. For a particular two-dimensional airfoil, we instead apply automatic differentiation to compute accurate derivatives of the lift and drag coefficients with respect to geometric shape parameters. In automatic differentiation, a given program is transformed into another program capable of computing the original function together with its derivatives. In the problem at hand, the objective function consists of a sequence of programs: a MATLAB program followed by two Fortran 77 programs. It is shown how automatic differentiation is applied to a sequence of programs while keeping the computational complexity within reasonable limits. The derivatives computed by automatic differentiation are compared with approximations based on divided differences.     

扩展面向对象编程（XOOP）的理论和方法

针对使用继续的传统对象系统在映射真实世界的对象关系时遇到的各种困难,提出一种普遍的软件工程方法,即扩展的面向对象方法（XOO）,它通过支持双向派生、归纳、更一般的多态机制等技术,来补足继承机制的不足,并进一步增强对象方法在描述对象关系方面的能力。作者强调了虚归纳是一种普遍的软件工程方法,它使得归纳与继承的高效结合成为可能,可以作为重用已有类库代码和与继续类层次结合的有效方法。文中还描述了XOOP的一个较为完整的实现－－编程语言C。     

Source transformation in software engineering using the TXL transformation system

Many tasks in software engineering can be characterized as source to source transformations. Design recovery, software restructuring, forward engineering, language translation, platform migration, and code reuse can all be understood as transformations from one source text to another. The tree transformation language, TXL, is a programming language and rapid prototyping system specifically designed to support rule-based source to source transformation. Originally conceived as a tool for exploring programming language dialects, TXL has evolved into a general purpose source transformation system that has proven well suited to a wide range of software maintenance and reengineering tasks, including the design recovery, analysis and automated reprogramming of billions of lines of commercial Cobol, PL/I, and RPG code for the Year 2000. In this paper, we introduce the basic features of modern TXL and its use in a range of software engineering applications, with an emphasis on how each task can be achieved by source transformation.     

Continuation-Passing C, compiling threads to events through continuations

In this paper, we introduce Continuation Passing C (CPC), a programming language for concurrent systems in which native and cooperative threads are unified and presented to the programmer as a single abstraction. The CPC compiler uses a compilation technique, based on the CPS transform, that yields efficient code and an extremely lightweight representation for contexts. We provide a proof of the correctness of our compilation scheme. We show in particular that lambda-lifting, a common compilation technique for functional languages, is also correct in an imperative language like C, under some conditions enforced by the CPC compiler. The current CPC compiler is mature enough to write substantial programs such as Hekate, a highly concurrent BitTorrent seeder. Our benchmark results show that CPC is as efficient, while using significantly less space, as the most efficient thread libraries available.