Debugging hygienic macros

Over the past two decades, Scheme macros have evolved into a powerful API for the compiler front end. Like Lisp macros, their predecessors, Scheme macros expand source programs into a small core language; unlike Lisp systems, Scheme macro expanders preserve lexical scoping, and advanced Scheme macro systems handle other important properties such as source location. Using such macros, Scheme programmers now routinely develop the ultimate abstraction: embedded domain-specific programming languages.Unfortunately, a typical Scheme programming environment provides little support for macro development. This lack makes it difficult for programmers to debug their macros and for novices to study the behavior of macros. In response, we have developed a stepping debugger specialized to the concerns of macro expansion. This debugger presents the macro expansion process as a linear rewriting sequence of annotated terms; it graphically illustrates the binding structure of the program as expansion reveals it; and it adapts to the programmer’s level of abstraction, hiding details of syntactic forms that the programmer considers built-in.     

Stack virtualization for source level debugging

The compilation of high‐level languages to general‐purpose execution platforms poses some challenges when it comes to debugging. Typically, abstractions that are not natively supported by the execution platform must be emulated with intermediate data structures and function calls. Unfortunately, the details of the emulation are visible in the execution stack, and this unwanted information greatly reduces the effectiveness of debuggers. This paper presents a general method for constructing a virtual view of the stack, in order to mask intermediate function calls that were generated to emulate high‐level abstractions, or even to recover logical frame information that was lost during the compilation process. In particular, virtual views enable the visualization of two disjoint code representations (e.g. native code and interpreted code) as a single unified stack. We illustrate this method by showing how to handle the compilation of Bigloo, a dialect of the Scheme programming language. Copyright © 2006 John Wiley & Sons, Ltd.     

Hardware assisted high-level debugging

Hardware assistance has long been used for logic level and functional unit level hardware debugging, as well as for machine language level software debugging. Such hardware assistance includes probes to detect signals, comparators to identify matches with expected patterns, buffers to record selected events, and independent logic and software to analyze and interpret the observed events. It can also include the ability to generate selected signals to stimulate the object being debugged and the ability to isolate it from normal changes so its state can be examined. Through knowledge of the data structures and algorithms used by the operating systems, and the runtime representation, register usage, and code bursts produced by compilers, it is possible to take advantage of such hardware assistance in high-level debugging. High-level debugging here refers to debugging in terms of abstractions supported by the operating system and programming languages, as well as user defined abstractions built on top of these. This paper discusses design considerations behind a project to build such a hardware assisted high-level debugger.     

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.     

A high-level debugger for PL/I,Fortran and Basic

Dartmouth College has implemented a single debugger for several languages sharing a common runtime environment: PL/I, Basic and Fortran. The debugger is fairly powerful; users set breakpoints and traces which occur whenever the values of given variables change, or whenever certain relational expressions become true, for example. All debugging is carried on in a syntax similar to that of a high-level language. This debugger was implemented in about a month. It should be fairly easy to implement on most timesharing systems. This paper describes the debugger's user interface and gives a rough sketch of its implementation.     

Debugging mixed‐environment programs with Blink

Programmers build large‐scale systems with multiple languages to leverage legacy code and languages best suited to their problems. For instance, the same program may use Java for ease of programming and C to interface with the operating system. These programs pose significant debugging challenges, because programmers need to understand and control code across languages, which often execute in different environments. Unfortunately, traditional multilingual debuggers require a single execution environment. This paper presents a novel composition approach to building portable mixed‐environment debuggers, in which an intermediate agent interposes on language transitions, controlling and reusing single‐environment debuggers. We implement debugger composition in Blink, a debugger for Java, C, and the Jeannie programming language. We show that Blink is (i) simple: it requires modest amounts of new code; (ii) portable: it supports multiple Java virtual machines, C compilers, operating systems, and component debuggers; and (iii) powerful: composition eases debugging, while supporting new mixed‐language expression evaluation and Java native interface bug diagnostics. To demonstrate the generality of interposition, we build prototypes and demonstrate debugger language transitions with C for five of six other languages (Caml, Common Lisp, C#, Perl 5, Python, and Ruby) without modifications to their debuggers. Using real‐world case studies, we show that diagnosing language interface errors require prior single‐environment debuggers to restart execution multiple times, whereas Blink directly diagnoses them with one execution. Copyright © 2014 John Wiley & Sons, Ltd.     

How to integrate object orientation with structured analysis anddesign

The author argues that while object-oriented languages are popular, many developers mistakenly believe that to use them means they must stop using structured analysis and design. He shows that there is no conflict. He describes object-oriented abstractions and real-time structured-analysis/structured-design abstractions and shows how to integrate the two     

基于像素的多边形等距区域子分算法

目的 多边形等距是计算机图形学、计算几何、计算机辅助几何设计领域的一个基础性问题,并且有着广泛的应用。为了有效地处理各种类型的多边形等距问题,提出一种基于像素的多边形等距区域子分算法。方法 利用四叉树数据结构对给定区域进行子分,再利用区间算术计算出符合等距要求的全体像素集。针对只是由线段组成的多边形采用点到线段的最短距离算子加快计算速度。结果 利用区域子分算法处理了不同类型的多边形等距问题,并与传统的基于像素的多边形等距膨胀算法进行了比较。本文算法能有效处理各种多边形的等距问题,相对于传统的基于像素的膨胀算法,在顶点处的处理效果上更好,并且耗时也更短。所提区域子分算法比传统边等距方法适用范围更广,能够有效地处理一些边等距算法不能处理的多边形等距问题。结论 本文算法其优点是不需要考虑自交和连接问题,并且可以处理其他许多常规方法处理不了的各种类型的多边形等距问题,包括带有弧段和孤岛的情况。     

Grammar‐driven generation of domain‐specific language debuggers

Domain‐specific languages (DSLs) assist a software developer (or end‐user) in writing a program using idioms that are similar to the abstractions found in a specific problem domain. Tool support for DSLs is lacking when compared with the capabilities provided for standard general‐purpose languages (GPLs), such as Java and C++. For example, support for debugging a program written in a DSL is often non‐existent. The lack of a debugger at the proper abstraction level limits an end‐user's ability to discover and locate faults in a DSL program. This paper describes a grammar‐driven technique to build a debugging tool generation framework from existing DSL grammars. The DSL grammars are used to generate the hooks needed to interface with a supporting infrastructure constructed for an integrated development environment that assists in debugging a program written in a DSL. The contribution represents a coordinated approach to bring essential software tools (e.g. debuggers) to different types of DSLs (e.g. imperative, declarative, and hybrid). This approach hides from the end‐users the accidental complexities associated with expanding the focus of a language environment to include debuggers. The research described in this paper addresses a long‐term goal of empowering end‐users with development tools for particular DSL problem domains at the proper level of abstraction without depending on a specific GPL. Copyright © 2007 John Wiley & Sons, Ltd.     

Inference in hybrid Bayesian networks with large discrete and continuous domains

Inference in Bayesian networks with large domain of discrete variables requires significant computational effort. In order to reduce the computational effort, current approaches often assume that discrete variables have some bounded number of values or are represented at an appropriate size of clusters. In this paper, we introduce decision-tree structured conditional probability representations that can efficiently handle a large domain of discrete and continuous variables. These representations can partition the large number of values into some reasonable number of clusters and lead to more robust parameter estimation. Very rapid computation and ability to treat both discrete and continuous variables are accomplished via modified belief propagation algorithm. Being able to compute various types of reasoning from a single Bayesian network eliminates development and maintenance issues associated with the use of distinct models for different types of reasoning. Application to real-world steel production process data is presented.     

Efficient Abstractions for GPGPU Programming

General purpose (GP)GPU programming demands to couple highly parallel computing units with classic CPUs to obtain a high performance. Heterogenous systems lead to complex designs combining multiple paradigms and programming languages to manage each hardware architecture. In this paper, we present tools to harness GPGPU programming through the high-level OCaml programming language. We describe the SPOC library that allows to handle GPGPU subprograms (kernels) and data transfers between devices. We then present how SPOC expresses GPGPU kernel: through interoperability with common low-level extensions (from Cuda and OpenCL frameworks) but also via an embedded DSL for OCaml. Using simple benchmarks as well as a real world HPC software, we show that SPOC can offer a high performance while efficiently easing development. To allow better abstractions over tasks and data, we introduce some parallel skeletons built upon SPOC as well as composition constructs over those skeletons.     

On tolerant fuzzy c-means clustering and tolerant possibilistic clustering

This paper presents two new types of clustering algorithms by using tolerance vector called tolerant fuzzy c-means clustering and tolerant possibilistic clustering. In the proposed algorithms, the new concept of tolerance vector plays very important role. The original concept is developed to handle data flexibly, that is, a tolerance vector attributes not only to each data but also each cluster. Using the new concept, we can consider the influence of clusters to each data by the tolerance. First, the new concept of tolerance is introduced into optimization problems. Second, the optimization problems with tolerance are solved by using Karush–Kuhn–Tucker conditions. Third, new clustering algorithms are constructed based on the optimal solutions for clustering. Finally, the effectiveness of the proposed algorithms is verified through numerical examples and its fuzzy classification function.     

Graphical and incremental type inference. A graph transformation approach

We present a graph grammar based type inference system for a totally graphic development language. NiMo (Nets in Motion) can be seen as a graphic equivalent to Haskell that acts as an on-line tracer and debugger. Programs are process networks that evolve giving total visibility of the execution state, and can be interactively completed, changed or stored at any step. In such a context, type inference must be incremental. During the net construction or modification only type safe connections are allowed. The user visualizes the type information evolution and, in case of conflict, can easily identify the causes. Though based on the same ideas, the type inference system has significant differences with its analogues in functional languages. Process types are a non-trivial generalization of functional types to handle multiple outputs and deferred arguments even in higher order parameters, partial application in any order and curried-uncurried coercion. Here we present the elements to model graphical inference, the notion of structural and non-structural equivalence of type graphs, and a graph unification and composition calculus for typing nets in an incremental way.     

Refinement calculus: A basis for translation validation,debugging and certification

In this paper, we show how refinement calculus provides a basis for translation validation of optimized programs written in high level languages. Towards such a direction, we shall provide a generalized proof rule for establishing refinement of source and target programs for which one need not have to know the underlying program transformations. Our method is supported by a semi-automatic tool that uses a theorem prover for validating the verification conditions. We further show that the translation validation infrastructure provides an effective basis for deriving semantic debuggers and illustrate the development of a simple debugger for optimized programs using this approach using Prolog. A distinct advantage of semantic debugging is that it permits the user to change values at run-time only when the values are consistent with the underlying semantics.     

Dynamic verification of C++ generic algorithms

Dynamic verification is a new approach to formal verification, applicable to generic algorithms such as those found in the Standard Template Library (STL, part of the Draft ANSI/ISO C++ Standard Library). Using behavioral abstraction and symbolic execution techniques, verifications are carried out at an abstract level such that the results can be used in a variety of instances of the generic algorithms without repeating the proofs. This is achieved by substituting for type parameters of generic algorithms special data types that model generic concepts by accepting symbolic inputs and deducing outputs using inference methods. By itself, this symbolic execution technique supports testing of programs with symbolic values at an abstract level. For formal verification one also needs to generate multiple program execution paths and use assertions (to handle while loops, for example), but the authors show how this can be achieved via directives to a conventional debugger program and an analysis database. The assertions must still be supplied, but they can be packaged separately and evaluated as needed by appropriate transfers of control orchestrated via the debugger. Unlike all previous verification methods, the dynamic verification method thus works without having to transform source code or process it with special interpreters. They include an example of the formal verification of an STL generic algorithm     

Lock-and-key strategies for handling undefined variables

Most programming languages ignore the problem of undefined variables and permit compilers to allow the leftover contents of the memory cells belonging to such variables to be referenced. Although efficient, this type of semantics does not support software engineering, because defects might arise in subtle ways and might be difficult to locate. Two other types of semantics that better support software engineering are to either initialize all variables to some default, e.g. zero, or to require that all references to undefined variables be treated as errors. However, these types of semantics are obviously more expensive than simply ignoring the undefined variables entirely. In this paper, we propose a simple technique that works equally well for both of these latter two types of semantics, and whose efficiency compares favorably for certain realistic programs with more traditional implementations of these semantics. Furthermore, we provide a mechanism for using this technique through Ada implementations of two abstract data types where undefined variables respectively exhibit these two types of semantics, and whose implementations of these semantics use our technique. These abstract data types allow our technique to be selectively used in strictly those situations where the cost of the technique is justified. We provide practical examples illustrating these situations.     

Chunks and Tasks: A programming model for parallelization of dynamic algorithms

We propose Chunks and Tasks, a parallel programming model built on abstractions for both data and work. The application programmer specifies how data and work can be split into smaller pieces, chunks and tasks, respectively. The Chunks and Tasks library maps the chunks and tasks to physical resources. In this way we seek to combine user friendliness with high performance. An application programmer can express a parallel algorithm using a few simple building blocks, defining data and work objects and their relationships. No explicit communication calls are needed; the distribution of both work and data is handled by the Chunks and Tasks library. This makes efficient implementation of complex applications that require dynamic distribution of work and data easier. At the same time, Chunks and Tasks imposes restrictions on data access and task dependencies that facilitate the development of high performance parallel back ends. We discuss the fundamental abstractions underlying the programming model, as well as performance, determinism, and fault resilience considerations. We also present a pilot C++ library implementation for clusters of multicore machines and demonstrate its performance for irregular block-sparse matrix–matrix multiplication.     

Empirical studies on programming language stimuli

Comprehending and debugging computer programs are inherently difficult tasks. The current approach to building program execution and debugging environments is to use exclusively visual stimuli on programming languages whose syntax and semantics has often been designed without empirical guidance. We present an alternative: Sodbeans, an open-source integrated development environment designed to output carefully chosen spoken auditory cues to supplement empirically evaluated visual stimuli. Originally designed for the blind, earlier work suggested that Sodbeans may benefit sighted programmers as well. We evaluate Sodbeans in two experiments. First, we report on a formal debugging experiment comparing (1) a visual debugger, (2) an auditory debugger, and (3) a multimedia debugger, which includes both visual and auditory stimuli. The results from this study indicate that while auditory debuggers on their own are significantly less effective for sighted users when compared with visual and multimedia debuggers, multimedia debuggers might benefit sighted programmers under certain circumstances. Specifically, we found that while multimedia debuggers do not provide instant usability, once programmers have some practice, their performance in answering comprehension questions improves. Second, we created and evaluated a pilot survey analyzing individual elements in a custom programming language (called HOP) to garner empirical metrics on their comprehensibility. Results showed that some of the most widely used syntax and semantics choices in commercial programming languages are extraordinarily unintuitive for novices. For example, at an aggregate level, the word for , as in a for loop, was rated reliably worse than repeat by more than 673% by novices. After completing our studies, we implemented the HOP programming language and integrated it into Sodbeans.