endoprogramming

Full-text: PDF
Movies: Quicktime

Todd L. Veldhuizen. Dynamic Multilevel Graph Visualization. Eprint arXiv:cs.GR/07121549, December 2007.

Abstract: We adapt multilevel, force-directed graph layout techniques to visualizing dynamic graphs in which vertices and edges are added and removed in an online fashion (i.e., unpredictably). We maintain multiple levels of coarseness using a dynamic, randomized coarsening algorithm. To ensure the vertices follow smooth trajectories, we employ dynamics simulation techniques, treating the vertices as point particles. We simulate fine and coarse levels of the graph simultaneously, coupling the dynamics of adjacent levels. Projection from coarser to finer levels is adaptive, with the projection determined by an affine transformation that evolves alongside the graph layouts. The result is a dynamic graph visualizer that quickly and smoothly adapts to changes in a graph.

Full-text: PDF

Todd L. Veldhuizen. Parsimony Principles for Software Components and Metalanguages. Generative Programming and Component Engineering (GPCE 2007), Salzburg, Austria, October 1-3, 2007. arXiv:0707.4166

Abstract: Software is a communication system. The usual topic of communication is program behavior, as encoded by programs. Domain-specific libraries are codebooks, domain-specific languages are coding schemes, and so forth. To turn metaphor into method, we adapt tools from information theory---the study of efficient communication---to probe the efficiency with which languages and libraries let us communicate programs. In previous work we developed an information-theoretic analysis of software reuse in problem domains. This new paper uses information theory to analyze tradeoffs in the design of components, generators, and metalanguages. We seek answers to two questions: (1) How can we judge whether a component is over- or under-generalized? Drawing on minimum description length principles, we propose that the best component yields the most succinct representation of the use cases. (2) If we view a programming language as an assemblage of metalanguages, each providing a complementary style of abstraction, how can these metalanguages aid or hinder us in efficiently describing software? We describe a complex triangle of interactions between the power of an abstraction mechanism, the amount of reuse it enables, and the cognitive difficulty of its use.

Slides in pdf.

Abstract. "The design of metaprogramming languages requires appreciation of the tradeoffs that exist between important language characteristics such as safety properties, expressive power, and succinctness." These slides are from PEPM 2006, and are based on the paper of the same name which may be found at arXiv:cs.PL/0512065.

Full-text: PostScript, PDF, or Other formats

Todd L. Veldhuizen. Tradeoffs in Metaprogramming. ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM 2006), Charleston, South Carolina, January 9-10 2006. arXiv:cs.SE/0512065

Abstract: The design of metaprogramming languages requires appreciation of the tradeoffs that exist between important language characteristics such as safety properties, expressive power, and succinctness. Unfortunately, such tradeoffs are little understood, a situation we try to correct by embarking on a study of metaprogramming language tradeoffs using tools from computability theory. Safety properties of metaprograms are in general undecidable; for example, the property that a metaprogram always halts and produces a type-correct instance is -complete. Although such safety properties are undecidable, they may sometimes be captured by a restricted language, a notion we adapt from complexity theory. We give some sufficient conditions and negative results on when languages capturing properties can exist: there can be no languages capturing total correctness for metaprograms, and no `functional' safety properties above can be captured. We prove that translating a metaprogram from a general-purpose to a restricted metaprogramming language capturing a property is tantamount to proving that property for the metaprogram. Surprisingly, when one shifts perspective from programming to metaprogramming, the corresponding safety questions do not become substantially harder --- there is no `jump' of Turing degree for typical safety properties.

Full-text: PostScript, PDF, or Other formats

(Nordic Journal of Computing, accepted)

Abstract: We study embeddings of programming languages into one another that preserve what reductions take place at compile-time, i.e., staging. A certain condition -- what we call a `Turing complete kernel' -- is sufficient for a language to be stage-universal in the sense that any language may be embedded in it while preserving staging. A similar line of reasoning yields the notion of safety-preserving embeddings, and a useful characterization of safety-universality. Languages universal with respect to staging and safety are good candidates for realizing domain-specific embedded languages (DSELs) and `active libraries' that provide domain-specific optimizations and safety checks.

Full-text: PostScript, PDF, or Other formats

(Updated Oct 2, 2005)

Abstract: We analyze software reuse from the perspective of information theory and Kolmogorov complexity, assessing our ability to ``compress'' programs by expressing them in terms of software components reused from libraries. A common theme in the software reuse literature is that if we can only get the right environment in place--- the right tools, the right generalizations, economic incentives, a ``culture of reuse'' --- then reuse of software will soar, with consequent improvements in productivity and software quality. The analysis developed in this paper paints a different picture: the extent to which software reuse can occur is an intrinsic property of a problem domain, and better tools and culture can have only marginal impact on reuse rates if the domain is inherently resistant to reuse. We define an entropy parameter $H \in [0,1]$ of problem domains that measures program diversity, and deduce from this upper bounds on code reuse and the scale of components with which we may work. For ``low entropy'' domains with $H$ near $0$, programs are highly similar to one another and the domain is amenable to the Component-Based Software Engineering (CBSE) dream of programming by composing large-scale components. For problem domains with $H$ near $1$, programs require substantial quantities of new code, with only a modest proportion of an application comprised of reused, small-scale components. Preliminary empirical results from Unix platforms support some of the predictions of our model.

Slides in pdf.

Talk given at the Dagstuhl workshop Software Libraries: Design and Evaluation, Schloss Dagstuhl, Germany, March 9-11 2005

Abstract. This talk surveys the major ideas of software libraries. First I trace the early history of libraries. One of the earliest libraries was the EDSAC's in the 1950s, stored as reusable paper tapes in a set of filing drawers, with an accompanying catalogue detailing the subroutines and their characteristics. Then I enumerate several perspectives on software libraries: libraries may usefully be regarded as knowledge bases, reuse repositories, language extensions, domain experts, abstractions, de-facto standards, defect management strategies, software compression, a stable platform, a technology adoption vehicle, and a communication medium. Each of these perspectives yields interesting questions and concerns about library design. Due to time limitations I cover only the first four of these in detail.

Slides in pdf.

Abstract. Domain-specific languages give programmers expressive notations tailored to the problem at hand. Producing a wholly new language is a massive effort, and so good practice is to realize DSLs by reusing an existing ``host'' language, either by writing a translator from the DSL to the host language, or defining the DSL as a library in the host language. In either approach, one may encounter the challenge that the problem domain requires optimizations and safety checks not supported by the host language. In this talk I will overview a research program aimed at developing more powerful host languages that have the power to realize any domain-specific optimizations and safety checks we might desire.

Slides in pdf format.

Abstract. By some accounts, the computer science literature comprises some 2 million publications and is growing at an ever-faster rate. In this talk, I overview the structure of the literature and outline strategies for searching it, emphasizing modern tools available online.