Though logic has permeated through several fields in computing during the past decades, it is not clear exactly how and to what extent it has done so. In an attempt to better understand logic's influence in the history of programming languages (and software engineering in general), I have conducted a discussion with the computing scientist Tony Hoare who, already during the late 1960s, used ideas from mathematical logic to define programming-language semantics. The discussion's transcript, presented in this article, is compared to previously published interviews with Hoare rather technical in that many questions are directly related to mathematical logic and computability theory in particular.

According to Lee in 1996, computer scientists ‘are reaching the stage of development where each new generation of participants is unaware both of their overall technological ancestry and the history of the development of their speciality, and have no past to build upon’ [Lee, J.A.N. (1996) “Those who forget the lessons of history are doomed to repeat it” or, why I study the history of computing. IEEE Ann. Hist. Comput. 18, 54–62]. A technically and historically accurate account, as attempted here, can help us, computer scientists, grasp some of the fundamental ideas underlying our discipline. This paper describes some early contributions of Dijkstra by elaborating on his involvement in putting forward and implementing the recursive procedure as an ALGOL60 language construct. Particular attention is paid to Dijkstra's generalizing style of solving problems.

Translating an informal design intent into a formal specification is an error prone process. A designer may be able to claim that his implementation meets his formal specification. But, in many cases, he cannot confidently claim that his formal specification correctly captures the original design intent. This problem, in our views, is due to global causal reasoning, as we show with LUSTRE for a Subway system. To resolve this lack of confidence, we briefly present our interactive design tool, which forces a designer to reason locally while formally specifying the design intent.

Embedded systems are evolving from traditional, stand-alone devices to devices that participate in Internet activity. The days of simple, manifest embedded software [e.g. a simple finite-impulse response (FIR) algorithm on a digital signal processor (DSP] are over. Complex, nonmanifest code, executed on a variety of embedded platforms in a distributed manner, characterizes next generation embedded software. One dominant niche, which we concentrate on, is embedded, multimedia software. The need is present to map large scale, dynamic, multimedia software onto an embedded system in a systematic and highly optimized manner. The objective of this paper is to introduce high-level, systematically applicable, data structure transformations and to show in detail the practical feasibility of our optimizations on three real-life multimedia case studies. We derive Pareto tradeoff points in terms of accesses versus memory footprint and obtain significant gains in execution time and power consumption with respect to the initial implementation choices. Our approach is a first step to systematically applying high-level data structure transformations in the context of memory-efficient and low-power multimedia systems.

In the past decades, data structure analysis was mainly done at a high level of abstraction in the computer science community. For instance, choosing a linked list as a data structure as opposed to an array for a specific situation, was mainly motivated from a performance point of view under the implicit assumption that the computer platform (that had to run the software) consisted out of one monolithical, physical memory. In the context of mobile, embedded devices, energy consumption is as important as performance. In addition to this, the assumption of one monolithical memory is outdated for many (if not all) current-day platforms! Clearly, there is a need to improve the choices that are made during data structure analysis given specific knowledge of the memory hierarchy of the platform under investigation. We show how memory related energy consumption can heavily be reduced by taking into account the access behaviour of the application on the one hand and the available on-chip and off-chip memory space on the other hand. We do this by exploiting the sparseness that is present in onesteady state of the data structure under investigation. Analytical results show that energy reductions of a factor of 8.7 are feasible in comparison to common data structure implementations. We trade these gains off with on-chip memory space consumption of a custom memory architecture.