Skip navigation

Programming and Programming Languages

  • Page 3 of 5
Building a Modern Computer from First Principles

In the early days of computer science, the interactions of hardware, software, compilers, and operating system were simple enough to allow students to see an overall picture of how computers worked. With the increasing complexity of computer technology and the resulting specialization of knowledge, such clarity is often lost. Unlike other texts that cover only one aspect of the field, The Elements of Computing Systems gives students an integrated and rigorous picture of applied computer science, as its comes to play in the construction of a simple yet powerful computer system.Indeed, the best way to understand how computers work is to build one from scratch, and this textbook leads students through twelve chapters and projects that gradually build a basic hardware platform and a modern software hierarchy from the ground up. In the process, the students gain hands-on knowledge of hardware architecture, operating systems, programming languages, compilers, data structures, algorithms, and software engineering. Using this constructive approach, the book exposes a significant body of computer science knowledge and demonstrates how theoretical and applied techniques taught in other courses fit into the overall picture.Designed to support one- or two-semester courses, the book is based on an abstraction-implementation paradigm; each chapter presents a key hardware or software abstraction, a proposed implementation that makes it concrete, and an actual project. The emerging computer system can be built by following the chapters, although this is only one option, since the projects are self-contained and can be done or skipped in any order. All the computer science knowledge necessary for completing the projects is embedded in the book, the only pre-requisite being a programming experience.The book's web site provides all tools and materials necessary to build all the hardware and software systems described in the text, including two hundred test programs for the twelve projects. The projects and systems can be modified to meet various teaching needs, and all the supplied software is open-source.

This innovative text presents computer programming as a unified discipline in a way that is both practical and scientifically sound. The book focuses on techniques of lasting value and explains them precisely in terms of a simple abstract machine. The book presents all major programming paradigms in a uniform framework that shows their deep relationships and how and where to use them together. After an introduction to programming concepts, the book presents both well-known and lesser-known computation models ("programming paradigms"). Each model has its own set of techniques and each is included on the basis of its usefulness in practice. The general models include declarative programming, declarative concurrency, message-passing concurrency, explicit state, object-oriented programming, shared-state concurrency, and relational programming. Specialized models include graphical user interface programming, distributed programming, and constraint programming. Each model is based on its kernel languagea simple core language that consists of a small number of programmer-significant elements. The kernel languages are introduced progressively, adding concepts one by one, thus showing the deep relationships between different models. The kernel languages are defined precisely in terms of a simple abstract machine. Because a wide variety of languages and programming paradigms can be modeled by a small set of closely related kernel languages, this approach allows programmer and student to grasp the underlying unity of programming. The book has many program fragments and exercises, all of which can be run on the Mozart Programming System, an Open Source software package that features an interactive incremental development environment.

Game Design Fundamentals

As pop culture, games are as important as film or television—but game design has yet to develop a theoretical framework or critical vocabulary. In Rules of Play Katie Salen and Eric Zimmerman present a much-needed primer for this emerging field. They offer a unified model for looking at all kinds of games, from board games and sports to computer and video games. As active participants in game culture, the authors have written Rules of Play as a catalyst for innovation, filled with new concepts, strategies, and methodologies for creating and understanding games .Building an aesthetics of interactive systems, Salen and Zimmerman define core concepts like "play," "design," and "interactivity." They look at games through a series of eighteen "game design schemas," or conceptual frameworks, including games as systems of emergence and information, as contexts for social play, as a storytelling medium, and as sites of cultural resistance.Written for game scholars, game developers, and interactive designers, Rules of Play is a textbook, reference book, and theoretical guide. It is the first comprehensive attempt to establish a solid theoretical framework for the emerging discipline of game design.

Uncertainty is a fundamental and unavoidable feature of daily life; in order to deal with uncertaintly intelligently, we need to be able to represent it and reason about it. In this book, Joseph Halpern examines formal ways of representing uncertainty and considers various logics for reasoning about it. While the ideas presented are formalized in terms of definitions and theorems, the emphasis is on the philosophy of representing and reasoning about uncertainty; the material is accessible and relevant to researchers and students in many fields, including computer science, artificial intelligence, economics (particularly game theory), mathematics, philosophy, and statistics.

Halpern begins by surveying possible formal systems for representing uncertainty, including probability measures, possibility measures, and plausibility measures. He considers the updating of beliefs based on changing information and the relation to Bayes' theorem; this leads to a discussion of qualitative, quantitative, and plausibilistic Bayesian networks. He considers not only the uncertainty of a single agent but also uncertainty in a multi-agent framework. Halpern then considers the formal logical systems for reasoning about uncertainty. He discusses knowledge and belief; default reasoning and the semantics of default; reasoning about counterfactuals, and combining probability and counterfactuals; belief revision; first-order modal logic; and statistics and beliefs. He includes a series of exercises at the end of each chapter.


An Introduction to Distributed Algorithms takes up some of the main concepts and algorithms, ranging from basic to advanced techniques and applications, that underlie the programming of distributed-memory systems such as computer networks, networks of workstations, and multiprocessors. Written from the broad perspective of distributed-memory systems in general it includes topics such as algorithms for maximum flow, program debugging, and simulation that do not appear in more orthodox texts on distributed algorithms.

Moving from fundamentals to advances and applications, ten chapters—with exercises and bibliographic notes—cover a variety of topics. These include models of distributed computation, information propagation, leader election, distributed snapshots, network synchronization, self- stability, termination detection, deadlock detection, graph algorithms, mutual exclusion, program debugging, and simulation.

All of the algorithms are presented in a clear, template- based format for the description of message-passing computations among the nodes of a connected graph. Such a generic setting allows the treatment of problems originating from many different application areas.

The main ideas and algorithms are described in a way that balances intuition and formal rigor—most are preceded by a general intuitive discussion and followed by formal statements as to correctness complexity or other properties.


Types and Semantics

In recent years, object-oriented programming has emerged as the dominant computer programming style, and object-oriented languages such as C++ and Java enjoy wide use in academia and industry. This text explores the formal underpinnings of object-oriented languages to help the reader understand the fundamental concepts of these languages and the design decisions behind them.

The text begins by analyzing existing object-oriented languages, paying special attention to their type systems and impediments to expressiveness. It then examines two key features: subtypes and subclasses. After a brief introduction to the lambda calculus, it presents a prototypical object-oriented language, SOOL, with a simple type system similar to those of class-based object-oriented languages in common use. The text offers proof that the type system is sound by showing that the semantics preserves typing information. It concludes with a discussion of desirable features, such as parametric polymorphism and a MyType construct, that are not yet included in most statically typed object-oriented languages.

A type system is a syntactic method for automatically checking the absence of certain erroneous behaviors by classifying program phrases according to the kinds of values they compute. The study of type systems--and of programming languages from a type-theoretic perspective—-has important applications in software engineering, language design, high-performance compilers, and security.This text provides a comprehensive introduction both to type systems in computer science and to the basic theory of programming languages. The approach is pragmatic and operational; each new concept is motivated by programming examples and the more theoretical sections are driven by the needs of implementations. Each chapter is accompanied by numerous exercises and solutions, as well as a running implementation, available via the Web. Dependencies between chapters are explicitly identified, allowing readers to choose a variety of paths through the material.The core topics include the untyped lambda-calculus, simple type systems, type reconstruction, universal and existential polymorphism, subtyping, bounded quantification, recursive types, kinds, and type operators. Extended case studies develop a variety of approaches to modeling the features of object-oriented languages.

This book presents the "great ideas" of computer science, condensing a large amount of complex material into a manageable, accessible form; it does so using the Java programming language. The book is based on the problem-oriented approach that has been so successful in traditional quantitative sciences. For example, the reader learns about database systems by coding one in Java, about system architecture by reading and writing programs in assembly language, about compilation by hand-compiling Java statements into assembly language, and about noncomputability by studying a proof of noncomputability and learning to classify problems as either computable or noncomputable. The book covers an unusually broad range of material at a surprisingly deep level. It also includes chapters on networking and security. Even the reader who pursues computer science no further will acquire an understanding of the conceptual structure of computing and information technology that every well-informed citizen should have.

An Introduction to Programming and Computing

This introduction to programming places computer science in the core of a liberal arts education. Unlike other introductory books, it focuses on the program design process. This approach fosters a variety of skills--critical reading, analytical thinking, creative synthesis, and attention to detail--that are important for everyone, not just future computer programmers.The book exposes readers to two fundamentally new ideas. First, it presents program design guidelines that show the reader how to analyze a problem statement; how to formulate concise goals; how to make up examples; how to develop an outline of the solution, based on the analysis; how to finish the program; and how to test. Each step produces a well-defined intermediate product. Second, the book comes with a novel programming environment, the first one explicitly designed for beginners. The environment grows with the readers as they master the material in the book until it supports a full-fledged language for the whole spectrum of programming tasks.All the book's support materials are available for free on the Web. The Web site includes the environment, teacher guides, exercises for all levels, solutions, and additional projects.

Introducing Computer Science

This lively introduction to computer science and computer programming in Scheme is for non-computer science majors with a strong interest in the subject and for computer science majors who lack prior programming experience. The text allows the student to experience the computer as a tool for expressing ideas, not as a frustrating set of mathematical obstacles. This goal is supported by the use of Scheme, a modern dialect of Lisp, designed to emphasize symbolic programming.

  • Page 3 of 5