The Elements of Computing Systems - Javier

1 Table of Contents Title PageCopyright PageDedicationPrefaceIntroductionChapter 1 - Boolean Logic Project Chapter 2 - Boolean Arithmetic Project Chapter 3 - Sequential Logic Project Chapter 4 - Machine Language Hack Machine Language Project Chapter 5 - Computer Architecture The Hack Hardware Platform Project Chapter 6 - Assembler Hack Assembly-to-Binary Translation Project Chapter 7 - Virtual Machine I: Stack Arithmetic VM Specification, Part Project Chapter 8 - Virtual Machine II: Program Control VM Specification, Part Project Chapter 9 - High-Level Language The Jack Language Writing Jack Project Chapter 10 - Compiler I: Syntax Analysis Project Chapter 11 - Compiler II: Code Generation Project Chapter 12 - Operating system The Jack OS Project Chapter 13 - Postscript: More Fun to Go Hardware Hardware High-Level Communications Appendix A.

2 - Hardware Description Language (HDL)Appendix B: - Test Scripting LanguageIndex 2005 Massachusetts Institute of Technology All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying,recording, or information storage and retrieval) without permission in writing from the publisher. This book was set in Times New Roman on 3B2 by Asco Typesetters, Hong and bound in the United States of America. Library of Congress Cataloging-in-Publication Data Nisan, Elements of Computing Systems : building a modern computer from first principles / Noam Nisan and Shimon bibliographical references and 0-262-14087-X (alk.)

3 Paper)1. Electronic digital computers. I. Schocken, Shimon. II. dc222005042807 10 9 8 7 6 5 4 3 2 1 Note on Software The book s Web site ( ) provides the tools and materials necessary to build all the hardware and software systemsdescribed in the book. These include a hardware simulator, a CPU emulator, a VM emulator, and executable versions of the assembler, virtualmachine, compiler, and operating system described in the book. The Web site also includes all the project materials about 200 test programsand test scripts, allowing incremental development and unit-testing of each one of the 12 projects.

4 All the supplied software tools and projectmaterials can be used as is on any computer equipped with either Windows or our parents,For teaching us that less is What I hear, I forget; What I see, I remember; What I do, I understand. Confucius, 551-479 BC Once upon a time, every computer specialist had a gestalt understanding of how computers worked. Theoverall interactions among hardware, software, compilers, and the operating system were simple andtransparent enough to produce a coherent picture of the computer s operations.

5 As modern computertechnologies have become increasingly more complex, this clarity is all but lost: the most fundamentalideas and techniques in computer science the very essence of the field are now hidden under manylayers of obscure interfaces and proprietary implementations. An inevitable consequence of thiscomplexity has been specialization, leading to computer science curricula of many courses, each coveringa single aspect of the wrote this book because we felt that many computer science students are missing the forest for thetrees.

6 The typical student is marshaled through a series of courses in programming, theory, andengineering, without pausing to appreciate the beauty of the picture at large. And the picture at large issuch that hardware and software Systems are tightly interrelated through a hidden web of abstractions,interfaces, and contract-based implementations. Failure to see this intricate enterprise in the flesh leavesmany students and professionals with an uneasy feeling that, well, they don t fully understand what sgoing on inside believe that the best way to understand how computers work is to build one from scratch.

7 With thatin mind, we came up with the following concept. Let s specify a simple but sufficiently powerfulcomputer system , and have the students build its hardware platform and software hierarchy from theground up, starting with nothing more than elementary logic gates. And while we are at it, let s do it say this because building a general-purpose computer from first principles is a huge , we identified a unique educational opportunity not only to build the thing, but also to illustrate,in a hands-on fashion, how to effectively plan and manage large-scale hardware and softwaredevelopment projects.

8 In addition, we sought to demonstrate the ability to construct, through recursiveascent and human reasoning, fantastically complex and useful Systems from nothing more than a fewprimitive building The book exposes students to a significant body of computer science knowledge, gained through a seriesof hardware and software construction tasks. These tasks demonstrate how theoretical and appliedtechniques taught in other computer science courses are used in practice. In particular, the followingtopics are illustrated in a hands-on fashion: Hardware: Logic gates, Boolean arithmetic, multiplexors, flip-flops, registers, RAM units, counters,Hardware Description Language (HDL), chip simulation and testing.

9 Architecture: ALU/CPU design and implementation, machine code, assembly language programming,addressing modes, memory-mapped input/output (I/O). Operating Systems : Memory management, math library, basic I/O drivers, screen management, file I/O,high-level language support. Programming languages: Object-based design and programming, abstract data types, scoping rules,syntax and semantics, references. Compilers: Lexical analysis, top-down parsing, symbol tables, virtual stack-based machine, codegeneration, implementation of arrays and objects.

10 Data structures and algorithms: Stacks, hash tables, lists, recursion, arithmetic algorithms, geometricalgorithms, running time considerations. Software engineering: Modular design, the interface/implementation paradigm, API design anddocumentation, proactive test planning, programming at the large, quality assurance. All these topics are presented with a very clear purpose: building a modern computer from the groundup. In fact, this has been our topic selection rule: The book focuses on the minimal set of topics necessaryfor building a fully functioning computer system .