Experiments in Computing: A Survey
---
paper_title: Histories of Computing

paper_content:

Computer technology is pervasive in the modern world, its role ever more important as it becomes embedded in a myriad of physical systems and disciplinary ways of thinking. The late Michael Sean Mahoney was a pioneer scholar of the history of computing, one of the first established historians of science to take seriously the challenges and opportunities posed by information technology to our understanding of the twentieth century.Mahoneys work ranged widely, from logic and the theory of computation to the development of software and applications as craft-work. But it was always informed by a unique perspective derived from his distinguished work on the history of medieval mathematics and experimental practice during the Scientific Revolution. His writings offered a new angle on very recent events and ideas and bridged the gaps between academic historians and computer scientists. Indeed, he came to believe that the field was irreducibly pluralistic and that there could be only histories of computing.In this collection, Thomas Haigh presents thirteen of Mahoneys essays and papers organized across three categories: historiography, software engineering, and theoretical computer science. His introduction surveys Mahoneys work to trace the development of key themes, illuminate connections among different areas of his research, and put his contributions into context. The volume also includes an essay on Mahoney by his former students Jed Z. Buchwald and D. Graham Burnett. The result is a landmark work, of interest to computer professionals as well as historians of technology and science. (20110615)
---
paper_title: Proof of Algorithms by General Snapshots

paper_content:

A constructive approach to the question of proofs of algorithms is to consider proofs that an object resulting from the execution of an algorithm possesses certain static characteristics. It is shown by an elementary example how this possibility may be used to prove the correctness of an algorithm written in ALGOL 60. The stepping stone of the approach is what is called General Snapshots, i.e. expressions of static conditions existing whenever the execution of the algorithm reaches particular points. General Snapshots are further shown to be useful for constructing algorithms.
---
paper_title: Curriculum '78—is computer science really that unmathematical?

paper_content:

In 1979, Ralston was investigating curricula for discrete mathematics [95] and Shaw was participating in evaluations of Curriculum 78 and the role of mathematics in undergraduate computer science. They combined their notes to form a criticism of the mathematical content of Curriculum ’78 that appeared in Communications of the ACM [94]. Some comments on the paper appeared a few months later [69]
---
paper_title: Was early entry a competitive advantage? US universities that entered computing in the 1940s

paper_content:

The author discusses whether early entry was a competitive advantage in academic computing. This is accomplished by examining the first three decades of computing at five universities - MIT, Harvard, the University of Pennsylvania, Columbia and Princeton - that initiated computing programs in the 1940s.
---
paper_title: Should computer scientists experiment more

paper_content:

Computer scientists and practitioners defend their lack of experimentation with a wide range of arguments. Some arguments suggest that experimentation is inappropriate, too difficult, useless, and even harmful. This article discusses several such arguments to illustrate the importance of experimentation for computer science. It considers how the software industry is beginning to value experiments, because results may give a company a three- to five-year lead over the competition.
---
paper_title: Experimental Validation In Software Engineering

paper_content:

Although experimentation is an accepted approach toward scientific validation in most scientific disciplines, it only recently has gained acceptance within the software development community. In this paper we discuss a 12-model classification scheme for performing experimentation within the software development domain. We evaluate over 600 published papers in the computer science literature and over one hundred papers from other scientific disciplines in order to determine: (1) how well the computer science community is succeeding at validating its theories, and (2) how computer science compares to other scientific disciplines. Published by Elsevier Science B.V.
---
paper_title: Computing as a discipline

paper_content:

The final report of the Task Force on the Core of Computer Science presents a new intellectual framework for the discipline of computing and a new basis for computing curricula. This report has been endorsed and approved for release by the ACM Education Board.
---
paper_title: Program development by stepwise refinement

paper_content:

The creative activity of programming—to be distinguished from coding—is usually taught by examples serving to exhibit certain techniques. It is here considered as a sequence of design decisions concerning the decomposition of tasks into subtasks and of data into data structures. The process of successive refinement of specifications is illustrated by a short but nontrivial example, from which a number of conclusions are drawn regarding the art and the instruction of programming.
---
paper_title: Mechanizing Proof: Computing, Risk, and Trust

paper_content:

Most aspects of our private and social lives---our safety, the integrity of the financial system, the functioning of utilities and other services, and national security---now depend on computing. But how can we know that this computing is trustworthy? In Mechanizing Proof, Donald MacKenzie addresses this key issue by investigating the interrelations of computing, risk, and mathematical proof over the last half century from the perspectives of history and sociology. His discussion draws on the technical literature of computer science and artificial intelligence and on extensive interviews with scientists and engineers.
---
paper_title: Reducibility Among Combinatorial Problems.

paper_content:

Throughout the 1960s I worked on combinatorial optimization problems including logic circuit design with Paul Roth and assembly line balancing and the traveling salesman problem with Mike Held. These experiences made me aware that seemingly simple discrete optimization problems could hold the seeds of combinatorial explosions. The work of Dantzig, Fulkerson, Hoffman, Edmonds, Lawler and other pioneers on network flows, matching and matroids acquainted me with the elegant and efficient algorithms that were sometimes possible. Jack Edmonds’ papers and a few key discussions with him drew my attention to the crucial distinction between polynomial-time and superpolynomial-time solvability. I was also influenced by Jack’s emphasis on min-max theorems as a tool for fast verification of optimal solutions, which foreshadowed Steve Cook’s definition of the complexity class NP. Another influence was George Dantzig’s suggestion that integer programming could serve as a universal format for combinatorial optimization problems.
---
paper_title: What to do till the computer scientist comes

paper_content:

The potential impact of computer science departments in the field of education is discussed. This is an expanded version of a presentation to a panel session before the Mathematics Association of America, Toronto, 30 August 1967.
---
paper_title: Computer Science and its Relation to Mathematics

paper_content:

A new discipline called Computer Science has recently arrived on the scene at most of the world's universities. The present article gives a personal view of how this subject interacts with Mathematics, by discussing the similarities and differences between the two fields, and by examining some of the ways in which they help each other. A typical nontrivial problem is worked out in order to illustrate these interactions.
---
paper_title: A theoretician’s guide to the experimental analysis of algorithms

paper_content:

This paper presents an informal discussion of issues that arise when one attempts to analyze algorithms experimentally. It is based on lessons learned by the author over the course of more than a decade of experimentation, survey paper writing, refereeing, and lively discussions with other experimentalists. Although written from the perspective of a theoretical computer scientist, it is intended to be of use to researchers from all fields who want to study algorithms experimentally. It has two goals: first, to provide a useful guide to new experimentalists about how such work can best be performed and written up, and second, to challenge current researchers to think about whether their own work might be improved from a scientific point of view. With the latter purpose in mind, the author hopes that at least a few of his recommendations will be considered controversial.
---
paper_title: One man's view of computer science

paper_content:

A number of observations and comments are directed toward suggesting that more than the usual engineering flavor be given to computer science. The engineering aspect is important because most present difficulties in this field do not involve the theoretical question of whether certain things can be done, but rather the practical question of how can they be accomplished well and simply. ::: ::: The teaching of computer science could be made more effective by various alterations, for example, the inclusion of a laboratory course in programming, the requirement for a strong minor in something other than mathematics, and more practical coding and less abstract theory, as well as more seriousness and less game-playing.
---
paper_title: Computer Science and the Representation of Knowledge

paper_content:

This chapter contains sections titled: Parts and Wholes, Old and New Concepts of Knowledge and Intelligence, Research in Artificial Intelligence, Conceptual Representations, Self-Knowledge and Programming Knowledge, Editors' Postscript, References
---
paper_title: The Computer from Pascal to von Neumann

paper_content:

From the Publisher: ::: In 1942, Lt. Herman H. Goldstine, a former mathematics professor, was stationed at the Moore School of Electrical Engineering at the University of Pennsylvania where he assisted in the creation of the ENIAC, the first electronic digital computer. ::: The ENIAC was operational in 1945, but plans for a new computer were already under way. The principal source of ideas for the new computer was John von Neumann, who became Goldstine's chief collaborator. After World War II, at the Institute for Advanced Study, they built the prototype of the present-day computer. ::: Herman Goldstine writes as both historian and scientist in this first examination of the development of computing machinery, from the seventeenth century through the early 1950s. His personal involvement lends a special authenticity to his narrative.
---
paper_title: An ACM executive committee position on the crisis in experimental computer science

paper_content:

The following is the text of a letter commenting on the Feldman Report sent to Dr. Richard C. Atkinson, Director of the National Science Foundation, and other Administration and Congressional officials.
---
paper_title: Rejuvenating experimental computer science: a report to the National Science Foundation and others

paper_content:

This report is based on the results of an NSF sponsored workshop held in Washington, D.C. on November 2, 1978. The co-authors of the report are: Gordon Bell, Digital Equipment Corporation; Bernard A. Galler, University of Michigan; Patricia Goldberg, IBM Corporation; John Hamblen, University of Missouri at Rolla; Elliot Pinson, Bell Telephone Laboratories; and Ivan Sutherland, California Institute of Technology. Also participating in the workshop were representatives of NSF and other government agencies. In addition to the authors, a number of other people have contributed to the contents of this report. In preparation for the original workshop, all doctorate-granting computer science departments in the nation were asked for comments and suggestions on the problems of experimental computer science. A version of the current report dated January 15 was circulated to these departments and to a number of industrial and government groups for criticism. The editors and authors of this final version gratefully acknowledge the contribution of a large number of other people at all stages in the preparation of the report. [Note: Following this presentation of the report, there is a position paper on the crisis in experimental computer science written by the ACM Executive Committee.]
---
paper_title: Assigning Meanings to Programs

paper_content:

This paper attempts to provide an adequate basis for formal definitions of the meanings of programs in appropriately defined programming languages, in such a way that a rigorous standard is established for proofs about computer programs, including proofs of correctness, equivalence, and termination. The basis of our approach is the notion of an interpretation of a program: that is, an association of a proposition with each connection in the flow of control through a program, where the proposition is asserted to hold whenever that connection is taken. To prevent an interpretation from being chosen arbitrarily, a condition is imposed on each command of the program. This condition guarantees that whenever a command is reached by way of a connection whose associated proposition is then true, it will be left (if at all) by a connection whose associated proposition will be true at that time. Then by induction on the number of commands executed, one sees that if a program is entered by a connection whose associated proposition is then true, it will be left (if at all) by a connection whose associated proposition will be true at that time. By this means, we may prove certain properties of programs, particularly properties of the form: ‘If the initial values of the program variables satisfy the relation R l, the final values on completion will satisfy the relation R 2’.
---
paper_title: A university's educational program in computer science

paper_content:

After a review of the power of contemporary computers, computer science is defined in several ways. The objectives of computer science education are stated, and it is asserted that in a North American university these will be achieved only through a computer science department. The program at Stanford University is reviewed as an example. The appendices include syllabi of Ph.D. qualifying examinations for Stanford's Computer Science Department.
---
paper_title: Towards a Mathematical Science of Computation

paper_content:

In this paper I shall discuss the prospects for a mathematical science of computation. In a mathematical science, it is possible to deduce from the basic assumptions, the important properties of the entities treated by the science. Thus, from Newton’s law of gravitation and his laws of motion, one can deduce that the planetary orbits obey Kepler’s laws.
---
paper_title: Experimental Validation In Software Engineering

paper_content:

Although experimentation is an accepted approach toward scientific validation in most scientific disciplines, it only recently has gained acceptance within the software development community. In this paper we discuss a 12-model classification scheme for performing experimentation within the software development domain. We evaluate over 600 published papers in the computer science literature and over one hundred papers from other scientific disciplines in order to determine: (1) how well the computer science community is succeeding at validating its theories, and (2) how computer science compares to other scientific disciplines. Published by Elsevier Science B.V.
---
paper_title: Is computer science science?

paper_content:

Computer science meets every criterion for being a science, but it has a self-inflicted credibility problem.
---
paper_title: An ACM executive committee position on the crisis in experimental computer science

paper_content:

The following is the text of a letter commenting on the Feldman Report sent to Dr. Richard C. Atkinson, Director of the National Science Foundation, and other Administration and Congressional officials.
---
paper_title: Experimental Evaluation in Computer Science: A Quantitative Study

paper_content:

A survey of 400 recent research articles suggests that computer scientists publish relatively few papers with experimentally validated results. The survey includes complete volumes of several refereed computer science journals, a conference, and 50 titles drawn at random from all articles published by ACM in 1993. The journals of Optical Engineering (OE) and Neural Computation (NC) were used for comparison. Of the papers in the random sample that would require experimental validation, 40% have none at all. In journals related to software engineering, this fraction is 50%. In comparison, the fraction of papers lacking quantitative evaluation in OE and NC is only 15% and 12%, respectively. Conversely, the fraction of papers that devote one fifth or more of their space to experimental validation is almost 70% for OE and NC, while it is a mere 30% for the computer science (CS) random sample and 20% for software engineering. The low ratio of validated results appears to be a serious weakness in computer science research. This weakness should be rectified for the long-term health of the field. The fundamental principle of science, the definition almost, is this: the sole test of the validity of any idea is experiment. —Richard P. Feynman. Beware of bugs in the above code; I have only proved it correct, not tried it. —Donald E. Knuth
---
paper_title: Rejuvenating experimental computer science: a report to the National Science Foundation and others

paper_content:

This report is based on the results of an NSF sponsored workshop held in Washington, D.C. on November 2, 1978. The co-authors of the report are: Gordon Bell, Digital Equipment Corporation; Bernard A. Galler, University of Michigan; Patricia Goldberg, IBM Corporation; John Hamblen, University of Missouri at Rolla; Elliot Pinson, Bell Telephone Laboratories; and Ivan Sutherland, California Institute of Technology. Also participating in the workshop were representatives of NSF and other government agencies. In addition to the authors, a number of other people have contributed to the contents of this report. In preparation for the original workshop, all doctorate-granting computer science departments in the nation were asked for comments and suggestions on the problems of experimental computer science. A version of the current report dated January 15 was circulated to these departments and to a number of industrial and government groups for criticism. The editors and authors of this final version gratefully acknowledge the contribution of a large number of other people at all stages in the preparation of the report. [Note: Following this presentation of the report, there is a position paper on the crisis in experimental computer science written by the ACM Executive Committee.]
---
paper_title: Alan Turing's Legacy: Info-Computational Philosophy of Nature

paper_content:

Alan Turing’s pioneering work on computability, and his ideas on morphological computing support Andrew Hodges’ view of Turing as a natural philosopher. Turing’s natural philosophy differs importantly from Galileo’s view that the book of nature is written in the language of mathematics (The Assayer, 1623). Computing is more than a language used to describe nature as computation produces real time physical behaviors. This article presents the framework of Natural info-computationalism as a contemporary natural philosophy that builds on the legacy of Turing’s computationalism. The use of info-computational conceptualizations, models and tools makes possible for the first time in history modeling of complex self-organizing adaptive systems, including basic characteristics and functions of living systems, intelligence, and cognition.
---
paper_title: Verification, Validation, and Confirmation of Numerical Models in the Earth Sciences

paper_content:

Verification and validation of numerical models of natural systems is impossible. This is because natural systems are never closed and because model results are always nonunique. Models can be confirmed by the demonstration of agreement between observation and prediction, but confirmation is inherently partial. Complete confirmation is logically precluded by the fallacy of affirming the consequent and by incomplete access to natural phenomena. Models can only be evaluated in relative terms, and their predictive value is always open to question. The primary value of models is heuristic.
---
paper_title: Beyond the algorithmization of the sciences

paper_content:

Algorithmic thinking is transforming both the descriptive sciences and the humanities, bringing them all closer to the mathematical core of computer science.
---
paper_title: Three Myths of Computer Science

paper_content:

In this paper I will discuss a basic concept of computer science-the concept of a computer program-and three related distinctions of computer science-software vs. hardware, digital vs. analogue, and model vs. theory. I believe all of these notions are important, and if properly understood, provide an important part of the conceptual framework of computer science. But, when these notions are misunderstood, certain myths tend to evolve. With regard to artificial intelligence work these myths perpetuate sloppy research, and with regard to philosophy these myths promote misconceptions related to the mind-body problem and scientific methodology.
---
paper_title: The Role of Models in Computer Science

paper_content:

Taking Brian Cantwell Smith's study, “Limits of Correctness in Computers,” as its point of departure, this article explores the role of models in computer science. Smith identifies two kinds of models that play an important role, where specifications are models of problems and programs are models of possible solutions. Both presuppose the existence of conceptualizations as ways of conceiving the world “in certain delimited ways.” But high-level programming languages also function as models of virtual (or abstract) machines, while low-level programming languages function as models of causal (or physical) machines. The resulting account suggests that sets of models embedded within models are indispensable for computer programming.
---
paper_title: The computer scientist as toolsmith II

paper_content:

A process for producing a photographic film having thereon a magnetic recording layer by applying a dispersion of a magnetic substance to an antihalation layer of a light-sensitive film for cinema, where the dispersion contains a compound or compounds, having at least two or more isocyanato groups or thioisocyanato groups or the anti-halation layer is previously processed with a solution containing the compound. A photographic film where either the magnetic layer contains, or the antihalation layer has been processed with, such a compound or compounds.
---
paper_title: Experimental Methodologies for Large-Scale Systems: a Survey

paper_content:

The increasing complexity of available infrastructures with specific features (caches, hyperthreading, dual core, etc.) or with complex architectures (hierarchical, parallel, distributed, etc.) makes it extremely difficult to build analytical models that allow for a satisfying prediction. Hence, it raises the question on how to validate algorithms if a realistic analytic analysis is not possible any longer. As for some many other sciences, the one answer is experimental validation. Nevertheless, experimentation in Computer Science is a difficult subject that today still opens more questions than it solves: What may an experiment validate? What is a ''good experiment''? How to build an experimental environment that allows for "good experiments"? etc. In this paper we will provide some hints on this subject and show how some tools can help in performing ''good experiments'', mainly in the context of parallel and distributed computing. More precisely we will focus on four main experimental methodologies, namely in-situ (real-scale) experiments (with an emphasis on PlanetLab and Grid'5000), Emulation (with an emphasis on Wrekavoc) benchmarking and simulation (with an emphasis on SimGRID and GridSim). We will provide a comparison of these tools and methodologies from a quantitative but also qualitative point of view.
---
paper_title: Back to experimentation

paper_content:

A composition based on extract from cacti is used as an insecticide against soft bodied insects injurious to plants. A process for preparing the extract and its use as an insecticide are given.
---
paper_title: Rejuvenating experimental computer science: a report to the National Science Foundation and others

paper_content:

This report is based on the results of an NSF sponsored workshop held in Washington, D.C. on November 2, 1978. The co-authors of the report are: Gordon Bell, Digital Equipment Corporation; Bernard A. Galler, University of Michigan; Patricia Goldberg, IBM Corporation; John Hamblen, University of Missouri at Rolla; Elliot Pinson, Bell Telephone Laboratories; and Ivan Sutherland, California Institute of Technology. Also participating in the workshop were representatives of NSF and other government agencies. In addition to the authors, a number of other people have contributed to the contents of this report. In preparation for the original workshop, all doctorate-granting computer science departments in the nation were asked for comments and suggestions on the problems of experimental computer science. A version of the current report dated January 15 was circulated to these departments and to a number of industrial and government groups for criticism. The editors and authors of this final version gratefully acknowledge the contribution of a large number of other people at all stages in the preparation of the report. [Note: Following this presentation of the report, there is a position paper on the crisis in experimental computer science written by the ACM Executive Committee.]
---
paper_title: Empirical studies to build a science of computer science

paper_content:

A connector plated contact point having a curvilinear area terminating in a feather edge. Optionally the contact has a conductive underbody having a feather edge. Both feather edged metals have a raised central portion. The contact is formed on a contact plater having a pair of opposed belts for grasping and driving contact point through a pair of opposed jaws to be plated by contact on an anode roller, the same describing a helical trace on the roller.
---
paper_title: Epistemology as Information Theory: From Leibniz to Omega

paper_content:

In 1686 in his Discours de Metaphysique, Leibniz points out that if an arbitrarily complex theory is permitted then the notion of"theory"becomes vacuous because there is always a theory. This idea is developed in the modern theory of algorithmic information, which deals with the size of computer programs and provides a new view of Godel's work on incompleteness and Turing's work on uncomputability. Of particular interest is the halting probability Omega, whose bits are irreducible, i.e., maximally unknowable mathematical facts. More generally, these ideas constitute a kind of"digital philosophy"related to recent attempts of Edward Fredkin, Stephen Wolfram and others to view the world as a giant computer. There are also connections with recent"digital physics"speculations that the universe might actually be discrete, not continuous. This systeme du monde is presented as a coherent whole in my book Meta Math!, which will be published this fall.
---
paper_title: Experimental Validation In Software Engineering

paper_content:

Although experimentation is an accepted approach toward scientific validation in most scientific disciplines, it only recently has gained acceptance within the software development community. In this paper we discuss a 12-model classification scheme for performing experimentation within the software development domain. We evaluate over 600 published papers in the computer science literature and over one hundred papers from other scientific disciplines in order to determine: (1) how well the computer science community is succeeding at validating its theories, and (2) how computer science compares to other scientific disciplines. Published by Elsevier Science B.V.
---
paper_title: Computing as a discipline

paper_content:

The final report of the Task Force on the Core of Computer Science presents a new intellectual framework for the discipline of computing and a new basis for computing curricula. This report has been endorsed and approved for release by the ACM Education Board.
---
paper_title: The role of experimentation in software engineering: past, current, and future

paper_content:

Software engineering needs to follow the model of other physical sciences and develop an experimental paradigm for the field. This paper proposes the approach towards developing an experimental component of such a paradigm. The approach is based upon a quality improvement paradigm that addresses the role of experimentation and process improvement in the content of industrial development. The paper outlines a classification scheme for characterizing such experiments.
---
paper_title: Debugging as a Science, that too, when your Program is Changing

paper_content:

Program debugging is an extremely time-consuming process, and it takes up a large portion of software development time. In practice, debugging is still very much of an art, with the developer painstakingly going through volumes of execution traces to locate the actual cause of an observable error. In this work, we discuss recent advances in debugging which makes it systematic scientific activity in its own right. We explore the delicate connections between debugging and formal methods (such as model checking) in the overall task of validating software. Moreover, since any deployed software undergoes changes in its lifetime, we need debugging methods which can take the software evolution into account. We show how symbolic execution and Satisfiability Modulo Theories (SMT) solvers can be gainfully employed to greatly automate software debugging of evolving programs.
---
paper_title: The Science of Debugging

paper_content:

From the Publisher: ::: The only two eternals of software development are writing the code - and then debugging it. Effective debugging involves far more than walking through code with a debugger. This book recognizes that and sets out to make debugging less baffling, faster, and more effective by providing readers with the knowledge, tips, and techniques needed to rapidly identify, track down, and repair bugs. It goes further by offering practical tips on minimizing bugs and making them easier to find when they do occur. It includes chapters on testing and maintenance as they relate to debugging. Each chapter concludes with a "bug problem" and answers to these problems are provided in the last chapter. Above all, this is a book written by developers who've spent years tracking down bugs and offers practical, hands-on advice to make that task more predictable.
---
paper_title: Back to experimentation

paper_content:

A composition based on extract from cacti is used as an insecticide against soft bodied insects injurious to plants. A process for preparing the extract and its use as an insecticide are given.
---
paper_title: On the effectiveness of the test-first approach to programming

paper_content:

Test-driven development (TDD) is based on formalizing a piece of functionality as a test, implementing the functionality such that the test passes, and iterating the process. This paper describes a controlled experiment for evaluating an important aspect of TDD: in TDD, programmers write functional tests before the corresponding implementation code. The experiment was conducted with undergraduate students. While the experiment group applied a test-first strategy, the control group applied a more conventional development technique, writing tests after the implementation. Both groups followed an incremental process, adding new features one at a time and regression testing them. We found that test-first students on average wrote more tests and, in turn, students who wrote more tests tended to be more productive. We also observed that the minimum quality increased linearly with the number of programmer tests, independent of the development strategy employed.
---
paper_title: An ACM executive committee position on the crisis in experimental computer science

paper_content:

The following is the text of a letter commenting on the Feldman Report sent to Dr. Richard C. Atkinson, Director of the National Science Foundation, and other Administration and Congressional officials.
---
paper_title: Experimentation in software engineering

paper_content:

A framework is presented for analyzing most of the experimental work performed in software engineering over the past several years. The framework of experimentation consists of four categories corresponding to phases of the experimentation process: definition, planning, operation, and interpretation. A variety of experiments are described within the framework and their contribution to the software engineering discipline is discussed. Some recommendations for the application of the experimental process in software engineering are included.
---
paper_title: Rejuvenating experimental computer science: a report to the National Science Foundation and others

paper_content:

This report is based on the results of an NSF sponsored workshop held in Washington, D.C. on November 2, 1978. The co-authors of the report are: Gordon Bell, Digital Equipment Corporation; Bernard A. Galler, University of Michigan; Patricia Goldberg, IBM Corporation; John Hamblen, University of Missouri at Rolla; Elliot Pinson, Bell Telephone Laboratories; and Ivan Sutherland, California Institute of Technology. Also participating in the workshop were representatives of NSF and other government agencies. In addition to the authors, a number of other people have contributed to the contents of this report. In preparation for the original workshop, all doctorate-granting computer science departments in the nation were asked for comments and suggestions on the problems of experimental computer science. A version of the current report dated January 15 was circulated to these departments and to a number of industrial and government groups for criticism. The editors and authors of this final version gratefully acknowledge the contribution of a large number of other people at all stages in the preparation of the report. [Note: Following this presentation of the report, there is a position paper on the crisis in experimental computer science written by the ACM Executive Committee.]
---
paper_title: Experimental Methodologies for Large-Scale Systems: a Survey

paper_content:

The increasing complexity of available infrastructures with specific features (caches, hyperthreading, dual core, etc.) or with complex architectures (hierarchical, parallel, distributed, etc.) makes it extremely difficult to build analytical models that allow for a satisfying prediction. Hence, it raises the question on how to validate algorithms if a realistic analytic analysis is not possible any longer. As for some many other sciences, the one answer is experimental validation. Nevertheless, experimentation in Computer Science is a difficult subject that today still opens more questions than it solves: What may an experiment validate? What is a ''good experiment''? How to build an experimental environment that allows for "good experiments"? etc. In this paper we will provide some hints on this subject and show how some tools can help in performing ''good experiments'', mainly in the context of parallel and distributed computing. More precisely we will focus on four main experimental methodologies, namely in-situ (real-scale) experiments (with an emphasis on PlanetLab and Grid'5000), Emulation (with an emphasis on Wrekavoc) benchmarking and simulation (with an emphasis on SimGRID and GridSim). We will provide a comparison of these tools and methodologies from a quantitative but also qualitative point of view.
---
paper_title: An insightful comparison between experiments in mobile robotics and in science

paper_content:

Experiments are essential ingredients of science, both to confirm/refute a theory and to discover new theories. It is a common belief that experimentation in mobile robotics has not yet reached a level of maturity comparable with that reached in science, for example in physics, considered as the paradigm of a mature, stable, and well-founded scientific discipline. In this paper, starting from a representative sample of the current state of the art, we identify some basic issues of experiments in mobile robot localization and mapping. These issues, when viewed in the context of some general principles about experiments in science and engineering, lead us to derive some insightful considerations on the role of experiments in mobile robotics. Reflecting the background of the authors, the paper has an interdisciplinary nature at the meeting point of mobile robotics and philosophy of science.
---
paper_title: The Neglect of Experiment

paper_content:

Acknowledgments List of abbreviations Introduction 1. The discovery of parity nonconservation 2. The nondiscovery of parity nonconservation 3. CP or not CP 4. The role of experiment 5. Do experiments tell us about the world? 6. The epistemology of experiment 7. The epistemology of experiment: case studies 8. Forging, cooking, trimming and riding on the bandwagon: fraud in science Conclusion Notes Index.
---
paper_title: Experimental Methodologies for Large-Scale Systems: a Survey

paper_content:

The increasing complexity of available infrastructures with specific features (caches, hyperthreading, dual core, etc.) or with complex architectures (hierarchical, parallel, distributed, etc.) makes it extremely difficult to build analytical models that allow for a satisfying prediction. Hence, it raises the question on how to validate algorithms if a realistic analytic analysis is not possible any longer. As for some many other sciences, the one answer is experimental validation. Nevertheless, experimentation in Computer Science is a difficult subject that today still opens more questions than it solves: What may an experiment validate? What is a ''good experiment''? How to build an experimental environment that allows for "good experiments"? etc. In this paper we will provide some hints on this subject and show how some tools can help in performing ''good experiments'', mainly in the context of parallel and distributed computing. More precisely we will focus on four main experimental methodologies, namely in-situ (real-scale) experiments (with an emphasis on PlanetLab and Grid'5000), Emulation (with an emphasis on Wrekavoc) benchmarking and simulation (with an emphasis on SimGRID and GridSim). We will provide a comparison of these tools and methodologies from a quantitative but also qualitative point of view.
---
paper_title: Computer science is a new engineering discipline

paper_content:

Hartmanis calls computer science “a new species among the sciences,” whose science and engineering aspects are particularly close. I have argued that it would be more accurate to call computer science a new species of engineering [Loui 1987]. Let me summarize the argument. The goal of engineering is the production of useful things, economically, for the benefit of society. These things include artifacts such as steel bridges, electronic circuits, automobile engines, and jet aircraft. Engineers also design manufacturing and chemical processes. A process is similar to a computational algorithm, which is a method for processing information. (Whether a process or an algorithm is patentable is a legalistic matter,) Like traditional engineering disciplines, computer science is concerned with producing useful things such as microprocessors, software, and databases. Furthermore, economic constraints require engineers to seek efficient solutions to technical problems in the design and manufacture of products. An emphasis on efficiency is also a distinguishing characteristic of computer science. Unlike other creative arts, engineering disciplines have a scientific basis—the engineering sciences: statics, dynamics, mechanics of solids, thermodynamics, fluid mechanics, and so on. Since World War II, all engineering disciplines have matured by incorporating their scientific foundations. The scientific fundamentals of computer science include Boolean algebra, computability theory, and automata and formal languages. The fundamental concepts and principles of computer science are rooted not in the physical phenomena of force, heat, and electricity, but in mathematics. Computer science is therefore a new kind of engineering. I agree with Hartmanis that attempts to distinguish computer science from computer engineering are futile. One conventional view—espoused by computer engineers-is that computer science comprises only theory and computer engineering comprises everything else. But excluding theory of computation from computer engineering would be as inconceivable as excluding circuit theory, linear system theory, communication theory, control theory, electromagnetic theory, and semiconductor theory from modern electrical engineering. A fortiori, the role of automata theory in computer science is analogous to the role of linear system theory in electrical engineering: the theories provide effective models for the design, analysis, and understanding of programs and circuits.
---
paper_title: Should computer scientists experiment more

paper_content:

Computer scientists and practitioners defend their lack of experimentation with a wide range of arguments. Some arguments suggest that experimentation is inappropriate, too difficult, useless, and even harmful. This article discusses several such arguments to illustrate the importance of experimentation for computer science. It considers how the software industry is beginning to value experiments, because results may give a company a three- to five-year lead over the competition.
---
paper_title: Experimental Validation In Software Engineering

paper_content:

Although experimentation is an accepted approach toward scientific validation in most scientific disciplines, it only recently has gained acceptance within the software development community. In this paper we discuss a 12-model classification scheme for performing experimentation within the software development domain. We evaluate over 600 published papers in the computer science literature and over one hundred papers from other scientific disciplines in order to determine: (1) how well the computer science community is succeeding at validating its theories, and (2) how computer science compares to other scientific disciplines. Published by Elsevier Science B.V.
---
paper_title: Some Observations About the Nature of Computer Science

paper_content:

This paper discusses the nature of computer science as a science by analyzing computer science and comparing or contrasting it with other sciences. In particular, we compare and contrast various aspects of computer science with physics, astronomy, and mathematics. Our analysis of computer science and comparison with other sciences is primarily in terms of: ::: ::: (a) ::: ::: the roles played by experiments and theory, ::: ::: ::: ::: ::: (b) ::: ::: how research paradigms and problem areas are determined and change, ::: ::: ::: ::: ::: (c) ::: ::: the relation and interaction of the science and engineering aspects, ::: ::: ::: ::: ::: (d) ::: ::: comparing historical developments.
---
paper_title: Empirical studies to build a science of computer science

paper_content:

A connector plated contact point having a curvilinear area terminating in a feather edge. Optionally the contact has a conductive underbody having a feather edge. Both feather edged metals have a raised central portion. The contact is formed on a contact plater having a pair of opposed belts for grasping and driving contact point through a pair of opposed jaws to be plated by contact on an anode roller, the same describing a helical trace on the roller.
---
paper_title: The computer scientist as toolsmith II

paper_content:

A process for producing a photographic film having thereon a magnetic recording layer by applying a dispersion of a magnetic substance to an antihalation layer of a light-sensitive film for cinema, where the dispersion contains a compound or compounds, having at least two or more isocyanato groups or thioisocyanato groups or the anti-halation layer is previously processed with a solution containing the compound. A photographic film where either the magnetic layer contains, or the antihalation layer has been processed with, such a compound or compounds.
---
paper_title: Towards a Mathematical Science of Computation

paper_content:

In this paper I shall discuss the prospects for a mathematical science of computation. In a mathematical science, it is possible to deduce from the basic assumptions, the important properties of the entities treated by the science. Thus, from Newton’s law of gravitation and his laws of motion, one can deduce that the planetary orbits obey Kepler’s laws.
---
paper_title: Experimental Validation In Software Engineering

paper_content:

Although experimentation is an accepted approach toward scientific validation in most scientific disciplines, it only recently has gained acceptance within the software development community. In this paper we discuss a 12-model classification scheme for performing experimentation within the software development domain. We evaluate over 600 published papers in the computer science literature and over one hundred papers from other scientific disciplines in order to determine: (1) how well the computer science community is succeeding at validating its theories, and (2) how computer science compares to other scientific disciplines. Published by Elsevier Science B.V.
---
paper_title: Experimental Evaluation in Computer Science: A Quantitative Study

paper_content:

A survey of 400 recent research articles suggests that computer scientists publish relatively few papers with experimentally validated results. The survey includes complete volumes of several refereed computer science journals, a conference, and 50 titles drawn at random from all articles published by ACM in 1993. The journals of Optical Engineering (OE) and Neural Computation (NC) were used for comparison. Of the papers in the random sample that would require experimental validation, 40% have none at all. In journals related to software engineering, this fraction is 50%. In comparison, the fraction of papers lacking quantitative evaluation in OE and NC is only 15% and 12%, respectively. Conversely, the fraction of papers that devote one fifth or more of their space to experimental validation is almost 70% for OE and NC, while it is a mere 30% for the computer science (CS) random sample and 20% for software engineering. The low ratio of validated results appears to be a serious weakness in computer science research. This weakness should be rectified for the long-term health of the field. The fundamental principle of science, the definition almost, is this: the sole test of the validity of any idea is experiment. —Richard P. Feynman. Beware of bugs in the above code; I have only proved it correct, not tried it. —Donald E. Knuth
---
paper_title: Empirical studies to build a science of computer science

paper_content:

A connector plated contact point having a curvilinear area terminating in a feather edge. Optionally the contact has a conductive underbody having a feather edge. Both feather edged metals have a raised central portion. The contact is formed on a contact plater having a pair of opposed belts for grasping and driving contact point through a pair of opposed jaws to be plated by contact on an anode roller, the same describing a helical trace on the roller.
---
paper_title: Experimental Methodologies for Large-Scale Systems: a Survey

paper_content:

The increasing complexity of available infrastructures with specific features (caches, hyperthreading, dual core, etc.) or with complex architectures (hierarchical, parallel, distributed, etc.) makes it extremely difficult to build analytical models that allow for a satisfying prediction. Hence, it raises the question on how to validate algorithms if a realistic analytic analysis is not possible any longer. As for some many other sciences, the one answer is experimental validation. Nevertheless, experimentation in Computer Science is a difficult subject that today still opens more questions than it solves: What may an experiment validate? What is a ''good experiment''? How to build an experimental environment that allows for "good experiments"? etc. In this paper we will provide some hints on this subject and show how some tools can help in performing ''good experiments'', mainly in the context of parallel and distributed computing. More precisely we will focus on four main experimental methodologies, namely in-situ (real-scale) experiments (with an emphasis on PlanetLab and Grid'5000), Emulation (with an emphasis on Wrekavoc) benchmarking and simulation (with an emphasis on SimGRID and GridSim). We will provide a comparison of these tools and methodologies from a quantitative but also qualitative point of view.
---
paper_title: Science and substance: a challenge to software engineers

paper_content:

For 25 years, software researchers have proposed improving software development and maintenance with new practices whose effectiveness is rarely, if ever, backed up by hard evidence. We suggest several ways to address the problem, and we challenge the community to invest in being more scientific. >
---
paper_title: An ACM executive committee position on the crisis in experimental computer science

paper_content:

The following is the text of a letter commenting on the Feldman Report sent to Dr. Richard C. Atkinson, Director of the National Science Foundation, and other Administration and Congressional officials.
---
paper_title: Experimental Methodologies for Large-Scale Systems: a Survey

paper_content:

The increasing complexity of available infrastructures with specific features (caches, hyperthreading, dual core, etc.) or with complex architectures (hierarchical, parallel, distributed, etc.) makes it extremely difficult to build analytical models that allow for a satisfying prediction. Hence, it raises the question on how to validate algorithms if a realistic analytic analysis is not possible any longer. As for some many other sciences, the one answer is experimental validation. Nevertheless, experimentation in Computer Science is a difficult subject that today still opens more questions than it solves: What may an experiment validate? What is a ''good experiment''? How to build an experimental environment that allows for "good experiments"? etc. In this paper we will provide some hints on this subject and show how some tools can help in performing ''good experiments'', mainly in the context of parallel and distributed computing. More precisely we will focus on four main experimental methodologies, namely in-situ (real-scale) experiments (with an emphasis on PlanetLab and Grid'5000), Emulation (with an emphasis on Wrekavoc) benchmarking and simulation (with an emphasis on SimGRID and GridSim). We will provide a comparison of these tools and methodologies from a quantitative but also qualitative point of view.
---
paper_title: Back to experimentation

paper_content:

A composition based on extract from cacti is used as an insecticide against soft bodied insects injurious to plants. A process for preparing the extract and its use as an insecticide are given.
---
paper_title: Management Information Systems Research: What’s There in a Methodology?

paper_content:

Management information systems (MIS) is both a young and unique field, constantly experiencing rapid change and turmoil. Consequently, MIS research faces dual changes of rigor and relevance. Many research methodologies exist that provide various combinations of rigor and relevance. The MIS researcher selects a methodology based on several factors including rigor, relevance, subject area, and personal preferences. In this article, we examine thirteen different methodologies as used by seven leading MIS journals during a recent five-year period. The results of this extensive analysis yielded some interesting results. Survey methodology consistently ranks at the top; while frameworks and conceptual models, lab experiments, and case studies also found significant use among the MIS community. Several trends were observed, one of them being a greater use of the case study method and other qualitative technologies over the years. Clear patterns also emerged based on the journal itself and the subject areas. At a macro level, this information should help authors in the choice of appropriate methodologies to use in specific subject areas and in targeting manuscripts to appropriate journals. It would also be helpful to journal editors in assessing the type of research and methods being used across journals and subjects, and whether they need to make any changes in the emphases of their own journals.
---
paper_title: Experimental Validation In Software Engineering

paper_content:

Although experimentation is an accepted approach toward scientific validation in most scientific disciplines, it only recently has gained acceptance within the software development community. In this paper we discuss a 12-model classification scheme for performing experimentation within the software development domain. We evaluate over 600 published papers in the computer science literature and over one hundred papers from other scientific disciplines in order to determine: (1) how well the computer science community is succeeding at validating its theories, and (2) how computer science compares to other scientific disciplines. Published by Elsevier Science B.V.
---
paper_title: TREC: Continuing information retrieval's tradition of experimentation

paper_content:

Large-scale test collections drive improvement in search technology to help users find information in free text.
---
paper_title: Computer science and the Pygmalion effect

paper_content:

Can computer science learn from the social sciences? We focus our discussions on an undesired phenomenon that commonly affects software developers. Known as the Pygmalion effect, this phenomenon has been studied intensely by social scientists but almost entirely ignored by computer scientists. Pygmalion was a sculptor who fell in love with his statue, Galatea, brought to life for him by Aphrodite. In the 1960s, R. Rosenthal and L. Jacobson, two American psychologists, used this myth to name an observation of theirs: whenever someone evaluates something, the evaluator's expectations concerning the evaluated object influence the evaluation, in a way that tends to prove the evaluator's initial hypothesis. Intensive studies since then have confirmed this initial observation: virtually every evaluation process in which humans intervene is prone to the Pygmalion effect, and computer science is no exception: the expectations of computer systems evaluators can strongly bias the outcome of the evaluation.
---
paper_title: A theoretician’s guide to the experimental analysis of algorithms

paper_content:

This paper presents an informal discussion of issues that arise when one attempts to analyze algorithms experimentally. It is based on lessons learned by the author over the course of more than a decade of experimentation, survey paper writing, refereeing, and lively discussions with other experimentalists. Although written from the perspective of a theoretical computer scientist, it is intended to be of use to researchers from all fields who want to study algorithms experimentally. It has two goals: first, to provide a useful guide to new experimentalists about how such work can best be performed and written up, and second, to challenge current researchers to think about whether their own work might be improved from a scientific point of view. With the latter purpose in mind, the author hopes that at least a few of his recommendations will be considered controversial.
---
paper_title: Experimental Evaluation in Computer Science: A Quantitative Study

paper_content:

A survey of 400 recent research articles suggests that computer scientists publish relatively few papers with experimentally validated results. The survey includes complete volumes of several refereed computer science journals, a conference, and 50 titles drawn at random from all articles published by ACM in 1993. The journals of Optical Engineering (OE) and Neural Computation (NC) were used for comparison. Of the papers in the random sample that would require experimental validation, 40% have none at all. In journals related to software engineering, this fraction is 50%. In comparison, the fraction of papers lacking quantitative evaluation in OE and NC is only 15% and 12%, respectively. Conversely, the fraction of papers that devote one fifth or more of their space to experimental validation is almost 70% for OE and NC, while it is a mere 30% for the computer science (CS) random sample and 20% for software engineering. The low ratio of validated results appears to be a serious weakness in computer science research. This weakness should be rectified for the long-term health of the field. The fundamental principle of science, the definition almost, is this: the sole test of the validity of any idea is experiment. —Richard P. Feynman. Beware of bugs in the above code; I have only proved it correct, not tried it. —Donald E. Knuth
---
paper_title: Albert Einstein and empirical software engineering

paper_content:

The author believes that scientists apply scientific investigative techniques to gain more understanding of what makes software "good" and how to make software well. Often, they adapt investigative techniques from other disciplines to define measures that make sense in the business, technical, and social contexts people use for decision making. However, the author believes that sometimes failure can educate as well as success. Examples from nineteenth-century physics show how a change in perspective can lead to explanations for previously misunderstood phenomena. The author claims that scientists must also consider whether their measurements constrict their view of what is really happening in the development process, and they must change or expand the approach if they are. Science clearly illustrates the limitations of an overly literal approach to building and maintaining software. Too often, the author believes, scientists tend to view software development the same way nineteenth-century physicists viewed the universe. Taking a cue from Einstein, scientists should shape their theories and models to fit a more probabilistic reality.
---
paper_title: Measurement and experimentation in software engineering

paper_content:

The contributions of measurement and experimentation to the state of the art in software engineering are reviewed. The role of measurement in developing theoretical models is discussed, and concerns for reliability and validity are stressed. Current approaches to measuring software characteristics are presented as examples. In particular, software complexity metrics related to control flow, module interconnectedness, and Halstead's Software Science are discussed. The use of experimental methods in evaluating cause-effect relationships is also discussed. Example programs of experimental research which investigated conditional statements and control flow are reviewed. The conclusion argues that many advances in software engineering will be related to improvements in the measurement and experimental evaluation of software techniques and practices.
---
paper_title: The Neglect of Experiment

paper_content:

Acknowledgments List of abbreviations Introduction 1. The discovery of parity nonconservation 2. The nondiscovery of parity nonconservation 3. CP or not CP 4. The role of experiment 5. Do experiments tell us about the world? 6. The epistemology of experiment 7. The epistemology of experiment: case studies 8. Forging, cooking, trimming and riding on the bandwagon: fraud in science Conclusion Notes Index.
---

Title: Experiments in Computing: A Survey

Section 1: Introduction
Description 1: Introduce the historical background and development of computing as an empirical or experimental science, emphasizing various debates such as mathematical, engineering, and scientific nature.

Section 2: Experimentation in Computing
Description 2: Discuss the significance and various interpretations of empirical and experimental research in computing, including historical context and shifts in methodological debates.

Section 3: Empirical Dimensions of Computing
Description 3: Explore different perspectives on computing and empirical research, distinguishing between computing as a subject of research and as an instrument for research.

Section 4: Subjects and Topics
Description 4: Examine various subjects and topics that have been studied experimentally in computing, drawing examples from literature.

Section 5: Activities
Description 5: Outline various experimental activities in computing, including exploration, construction, testing, simulation, and performance analysis.

Section 6: Terminology and Classifications
Description 6: Analyze the diverse terminology and classifications used for experimentation in computing, highlighting different interpretations and uses of the term “experiment.”

Section 7: Critique of Experimentation
Description 7: Present critical viewpoints on the role and nature of experiments in computing, addressing issues like differences with natural sciences, artificial data, and careless use of terminology.

Section 8: Five Views on Experimental Computer Science
Description 8: Describe five different uses of the term "experiment" in computing literature: feasibility experiment, trial experiment, field experiment, comparison experiment, and controlled experiment.

Section 9: Discussion
Description 9: Discuss the evolution and multidimensional nature of experiments in modern science and computing, arguing for a deeper, non-idealized, naturalistic understanding of experimentation in computing disciplines.