The Elements of Computing Systems
Noam Nisan and Shimon Schocken
The Elements of Computing Systems
Building a Modern Computer from First Principles
The MIT Press
Cambridge, Massachusetts
London, England
6 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 Kong.
Printed and bound in the United States of America.
Library of Congress Cataloging-in-Publication Data
Nisan, Noam.
The elements of computing systems: building a modern computer from first principles /
Noam Nisan and Shimon Schocken.
p. cm.
Includes bibliographical references and index.
ISBN 0-262-14087-X (alk. paper)
1. Electronic digital computers. I. Schocken, Shimon. II. Title.
TK7888.3.N57 2005
004.16—dc22 2005042807
10987654321
Note on Software
The book’s Web site (http://www.idc.ac.il/tecs) provides the tools and materials necessary
to build all the hardware and software systems described in the book. These include a hard-
ware simulator, a CPU emulator, a VM emulator, and executable versions of the assembler,
virtual machine, compiler, and operating system described in the book. The Web site also in-
cludes all the project materials—about 200 test programs and test scripts, allowing incremental
development and unit-testing of each one of the 12 projects. All the supplied software tools
and project materials can be used as is on any computer equipped with either Windows or
Linux.
To our parents,
For teaching us that less is more.
Contents
Preface ix
Introduction: Hello, World Below 1
1 Boolean Logic 7
2 Boolean Arithmetic 29
3 Sequential Logic 41
4 Machine Language 57
5 Computer Architecture 79
6 Assembler 103
7 Virtual Machine I: Stack Arithmetic 121
8 Virtual Machine II: Program Control 153
9 High-Level Language 173
10 Compiler I: Syntax Analysi s 199
11 Compiler II: Code Generation 223
12 Operating System 247
13 Postscript: More Fun to Go 277
