This book guides students through an exploration of the idea that thinking might be understood as a form of computation. Students make the connection between thinking and computing by learning to write computer programs for a variety of tasks that require thought, including solving puzzles, understanding natural language, recognizing objects in visual scenes, planning courses of action, and playing strategic games. The material is presented with minimal technicalities and is accessible to undergraduate students with no specialized knowledge or technical background beyond high school mathematics. Students use Prolog (without having to learn algorithms: “Prolog without tears!”), learning to express what they need as a Prolog program and letting Prolog search for answers.
After an introduction to the basic concepts, Thinking as Computation offers three chapters on Prolog, covering back-chaining, programs and queries, and how to write the sorts of Prolog programs used in the book. The book follows this with case studies of tasks that appear to require thought, then looks beyond Prolog to consider learning, explaining, and propositional reasoning. Most of the chapters conclude with short bibliographic notes and exercises. The book is based on a popular course at the University of Toronto and can be used in a variety of classroom contexts, by students ranging from first-year liberal arts undergraduates to more technically advanced computer science students.
C# is an object-oriented programming language that is similar to Java in many respects but more comprehensive and different in most details. This book offers a quick and accessible reference for anyone who wants to know C# in more detail than that provided by a standard textbook. It will be particularly useful for C# learners who are familiar with Java. This second edition has been updated and expanded, reflecting the evolution and extension of the C# programming language. It covers C# versions 3.0 and 4.0 and takes a look ahead at some of the innovations of version 5.0. In particular, it describes asynchronous programming as found in 5.0.
Despite the new material, C# Precisely remains compact and easy to navigate. It describes C# in detail but informally and concisely, presenting lambda expressions, extension methods, anonymous object expressions, object initializers, collection initializers, local variable type inference, type dynamic, type parameter covariance and contravariance, and Linq (language integrated query), among other topics, all in aabout 250 pages. The book offers more than 250 examples to illustrate both common use and subtle points. Two-page spreads show general rules on the left and relevant examples on the right, maximizing the amount of information accessible at a glance.
In Software Abstractions Daniel Jackson introduces an approach to software design that draws on traditional formal methods but exploits automated tools to find flaws as early as possible. This approach--which Jackson calls “lightweight formal methods” or “agile modeling”--takes from formal specification the idea of a precise and expressive notation based on a tiny core of simple and robust concepts but replaces conventional analysis based on theorem proving with a fully automated analysis that gives designers immediate feedback. Jackson has developed Alloy, a language that captures the essence of software abstractions simply and succinctly, using a minimal toolkit of mathematical notions. This revised edition updates the text, examples, and appendixes to be fully compatible with the latest version of Alloy (Alloy 4).
The designer can use automated analysis not only to correct errors but also to make models that are more precise and elegant. This approach, Jackson says, can rescue designers from “the tarpit of implementation technologies” and return them to thinking deeply about underlying concepts.
Software Abstractions introduces the key elements: a logic, which provides the building blocks of the language; a language, which adds a small amount of syntax to the logic for structuring descriptions; and an analysis, a form of constraint solving that offers both simulation (generating sample states and executions) and checking (finding counterexamples to claimed properties).
The ubiquity of combinatorial optimization problems in our society is illustrated by the novel application areas for optimization technology, which range from supply chain management to sports tournament scheduling. Over the last two decades, constraint programming has emerged as a fundamental methodology to solve a variety of combinatorial problems, and rich constraint programming languages have been developed for expressing and combining constraints and specifying search procedures at a high level of abstraction. Local search approaches to combinatorial optimization are able to isolate optimal or near-optimal solutions within reasonable time constraints.
This book introduces a method for solving combinatorial optimization problems that combines constraint programming and local search, using constraints to describe and control local search, and a programming language, COMET, that supports both modeling and search abstractions in the spirit of constraint programming.
After an overview of local search including neighborhoods, heuristics, and metaheuristics, the book presents the architecture and modeling and search components of constraint-based local search and describes how constraint-based local search is supported in COMET. The book describes a variety of applications, arranged by meta-heuristics. It presents scheduling applications, along with the background necessary to understand these challenging problems. The book also includes a number of satisfiability problems, illustrating the ability of constraint-based local search approaches to cope with both satisfiability and optimization problems in a uniform fashion.
Scheme is a general-purpose programming language, descended from Algol and Lisp, widely used in computing education and research and a broad range of industrial applications. This thoroughly updated edition of The Scheme Programming Language provides an introduction to Scheme and a definitive reference for standard Scheme, presented in a clear and concise manner. Written for professionals and students with some prior programming experience, it begins by leading the programmer gently through the basics of Scheme and continues with an introduction to some of the more advanced features of the language. The fourth edition has been substantially revised and expanded to bring the content up to date with the current Scheme standard, the Revised6 Report on Scheme. All parts of the book were updated and three new chapters were added, covering the language’s new library, exception handling, and record-definition features. The book offers three chapters of introductory material with numerous examples, eight chapters of reference material, and one chapter of extended examples and additional exercises. All of the examples can be entered directly from the keyboard into an interactive Scheme session. Answers to many of the exercises, a complete formal syntax of Scheme, and a summary of forms and procedures are provided in appendixes. The Scheme Programming Language is the only book available that serves both as an introductory text in a variety of courses and as an essential reference for Scheme programmers.
Some books on algorithms are rigorous but incomplete; others cover masses of material but lack rigor. Introduction to Algorithms uniquely combines rigor and comprehensiveness. The book covers a broad range of algorithms in depth, yet makes their design and analysis accessible to all levels of readers. Each chapter is relatively self-contained and can be used as a unit of study. The algorithms are described in English and in a pseudocode designed to be readable by anyone who has done a little programming. The explanations have been kept elementary without sacrificing depth of coverage or mathematical rigor.The first edition became a widely used text in universities worldwide as well as the standard reference for professionals. The second edition featured new chapters on the role of algorithms, probabilistic analysis and randomized algorithms, and linear programming. The third edition has been revised and updated throughout. It includes two completely new chapters, on van Emde Boas trees and multithreaded algorithms, substantial additions to the chapter on recurrence (now called “Divide-and-Conquer”), and an appendix on matrices. It features improved treatment of dynamic programming and greedy algorithms and a new notion of edge-based flow in the material on flow networks. Many new exercises and problems have been added for this edition. As of the third edition, this textbook is published exclusively by the MIT Press.
Downloadable instructor resources available for this title: instructor’s manual, file of figures in the book, and pseudocode
This text is the first comprehensive presentation of reduction semantics in one volume; it also introduces the first reliable and easy-to-use tool set for such forms of semantics. Software engineers have long known that automatic tool support is critical for rapid prototyping and modeling, and this book is addressed to the working semantics engineer (graduate student or professional language designer). The book comes with a prototyping tool suite to develop, explore, test, debug, and publish semantic models of programming languages. With PLT Redex, semanticists can formulate models as grammars and reduction models on their computers with the ease of paper and pencil. The text first presents a framework for the formulation of language models, focusing on equational calculi and abstract machines, then introduces PLT Redex, a suite of software tools for expressing these models as PLT Redex models. Finally, experts describe a range of models formulated in Redex. PLT Redex comes with the PLT Scheme implementation, available free at http://www.plt-scheme.org/. Readers can download the software and experiment with Redex as they work their way through the book.
Hundreds of programming languages are in use today--scripting languages for Internet commerce, user interface programming tools, spreadsheet macros, page format specification languages, and many others. Designing a programming language is a metaprogramming activity that bears certain similarities to programming in a regular language, with clarity and simplicity even more important than in ordinary programming. This comprehensive text uses a simple and concise framework to teach key ideas in programming language design and implementation. The book’s unique approach is based on a family of syntactically simple pedagogical languages that allow students to explore programming language concepts systematically. It takes as premise and starting point the idea that when language behaviors become incredibly complex, the description of the behaviors must be incredibly simple. The book presents a set of tools (a mathematical metalanguage, abstract syntax, operational and denotational semantics) and uses it to explore a comprehensive set of programming language design dimensions, including dynamic semantics (naming, state, control, data), static semantics (types, type reconstruction, polymporphism, effects), and pragmatics (compilation, garbage collection). The many examples and exercises offer students opportunities to apply the foundational ideas explained in the text. Specialized topics and code that implements many of the algorithms and compilation methods in the book can be found on the book’s Web site, along with such additional material as a section on concurrency and proofs of the theorems in the text. The book is suitable as a text for an introductory graduate or advanced undergraduate programming languages course; it can also serve as a reference for researchers and practitioners.
Introduction to Object-Oriented Databases provides the first unified and coherent presentation of the essential concepts and techniques of object-oriented databases. It consolidates the results of research and development in the semantics and implementation of a full spectrum of database facilities for object-oriented systems, including data model, query, authorization, schema evolution, storage structures, query optimization, transaction management, versions, composite objects, and integration of a programming language and a database system.
The book draws on the author's Orion project at MCC, currently the most advanced object-oriented database system, and places this work in a larger context by using relational database systems and other object-oriented systems for comparison.
Contents: Introduction. Data Model. Basic Interface. Relationships with Non-Object-Oriented Databases. Schema Modification. Model of Queries. Query Language. Authorization. Storage Structures. Query Processing. Transaction Management. Semantic Extensions. Integrating Object-Oriented Programming and Databases. Architecture. Survey of Object-Oriented Database Systems. Directions for Future Research and Development.
Constraint logic programming, the notion of computing with partial information, is becoming recognized as a way of dramatically improving on the current generation of programming languages. This collection presents the best of current work on all aspects of constraint logic programming languages, from theory through language implementation.
Beginning in the mid-1980s constraint logic programming became a powerful and essential theoretical concept whose first practical application was the development of efficient programming languages based on Prolog. Benhamou and Colmerauer have taken care to illustrate the strong links between current research and existing CLP languages. The first part of the book focuses on significant theoretical studies that propose general models for constraint programming, and the two following parts develop current ideas on themes derived from these languages (numerical constraints, Booleans, and other finite domains). The concluding part on CLP language design gathers work on original constraints and on top-level implementation.