The Elements of Computing Systems

Noam Nisan, Shimon Schocken

Mentioned 8

This title gives students an integrated and rigorous picture of applied computer science, as it comes to play in the construction of a simple yet powerful computer system.

More on Amazon.com

Mentioned in questions and answers.

I have heard about things like "C Runtime", "Visual C++ 2008 Runtime", ".NET Common Language Runtime", etc.

  • What is "runtime" exactly?
  • What is it made of?
  • How does it interact with my code? Or maybe more precisely, how is my code controlled by it?

When coding assembly language on Linux, I could use the INT instruction to make the system call. So, is the runtime nothing but a bunch of pre-fabricated functions that wrap the low level function into more abstract and high level functions? But doesn't this seem more like the definition for the library, not for the runtime?

Are "runtime" and "runtime library" two different things?

ADD 1

These days, I am thinking maybe Runtime has something in common with the so called Virtual Machine, such as JVM. Here's the quotation that leads to such thought:

This compilation process is sufficiently complex to be broken into several layers of abstraction, and these usually involve three translators: a compiler, a virtual machine implementation, and an assembler. --- The Elements of Computing Systems (Introduction, The Road Down To Hardware Land)

As per Wikipedia: runtime library/run-time system.

In computer programming, a runtime library is a special program library used by a compiler, to implement functions built into a programming language, during the runtime (execution) of a computer program. This often includes functions for input and output, or for memory management.


A run-time system (also called runtime system or just runtime) is software designed to support the execution of computer programs written in some computer language. The run-time system contains implementations of basic low-level commands and may also implement higher-level commands and may support type checking, debugging, and even code generation and optimization. Some services of the run-time system are accessible to the programmer through an application programming interface, but other services (such as task scheduling and resource management) may be inaccessible.


Re: your edit, "runtime" and "runtime library" are two different names for the same thing.

Possible Duplicates:
References Needed for Implementing an Interpreter in C/C++
Books On Creating Interpreted Languages
How to create a language these days?
Learning to write a compiler

Possible Duplicate:
Learning to write a compiler

Ok so I'm only 13 years old. I know some c++, VERY good at php, pro at css html, okay at javascript. So I was thinking of how was c++ created I mean how can computer understand what codes mean? How can it read...... so is it possible I can create my own language and how?

If you know C -- it sounds like you do -- grab a used copy of this ancient book: http://www.amazon.com/Craft-Take-Charge-Programming-Book-Disk/dp/0078818826

In it there's a chapter where the author creates a "C" interpreter, in C. It's not academically serious like the Dragon book would be, but I remember it being pretty simple, very practical and easy to follow, and since you're just getting started, it would be an awesome introduction to the ideas of a "grammar" for languages, and "tokenizing" a program.

It would be a perfect place for you to start. Also, at $0.01 for a used copy, cheaper than the Dragon Book. ;)

Check out this book, The Elements of Computing Systems: Building a Modern Computer from First Principles it takes you step by step through several aspects of designing a computer language, a compiler, a vm, the assembler, and the computer. I think this could help you answer some of your questions.

I really recommend Programming Language Pragmatics. It's a great book that takes you all the way from what a language is through how compilers work and creating your own. It's a bit more accessible than the Dragon Book and explains how things work before jumping in headfirst.

I am looking for a simple compiler that compiles a simple language, I need it to write a paper about it and to learn how compilers work, I am not looking for a sophisticated thing just a simple language (by simple I mean a small code because for example gcc is toooooo big). any help is appreciated.

You could also try this book : The Elements of Computing Systems.

Though a book that intends to cover right from designing a microprocessor to a language with its compiler, you could just focus on the relevant chapters.

Chapter 10: Syntax analysis is what you can work through, if you intend to focus only on the compiler front end part. However, chapter 9 should be a pre-requisite as it describes the design of a high level language for which a compiler is implemented. This high level language is actually a simple OO java like language, hence the compiler actually compiles to a VM.

The best part of it all is that you could actually follow the instructions and implement the front end part in any language of your choice, if you think that will further your understanding. It gels pretty well if you combine it with compiler theory.

And, you can find my review of the book here.

I know a little about assembly, and that there are 4 or 8 or so general purpose registers. How do all the programs on a computer work with just that amount of registers, especially with multithreading and everything?

Multi-threading itself doesn't affect the number of registers in use. When a thread is swapped out, it generally has its registers saved to memory and the next thread to run has those registers loaded up from its previous save.

An example is a system having a thread control block structure (TCB). This structure would contain (while the thread wasn't running), the saved instruction pointer, stack pointer, general purpose registers, floating point registers, thread statistics and so on. In short, everything needed to totally restore the thread to the state it was in when it was swapped out for another thread to run.

And not everything that goes on in a computer is done in registers. Modern compilers can optimise code so that the data items used the most are kept in registers but the vast majority of data is held in memory and only bought into registers when needed.

The best book I've ever read on the subject is Tanenbaum's "Structured Computer Organization" which examines computers in terms of layers, from the digital logic level up to the operating system level, with each level building on the previous.

           alt text

Aside: my dream is to one day write a book just like this that covers everything, from the quark level up to Emacs :-)

The other variables and thread stacks are usually stored in protected memory space, where they can be called into registers when needed.

You may want to check out the book The Elements of Computing Systems for a good understanding of how your computer's CPU works. The book is set up as a series of projects where you work up from a NAND gate to a CPU, assembler, simple compiler, and on to a small operating system. It's invaluable in understanding how all your computer's parts fit together.

I am reading and studying The Elements of Computing Systems but I am stuck at one point. Sample chapter skip the next 5 instruction s can be found here.

Anyway, I am trying to implement a Virtual Machine (or a byte code to assembly translator) but I am stuck at skip the next 5 instruction one point.

You can find the assembly notation here.

The goal is to implement a translator that will translate a specific byte code to this assembly code.

An example I have done successfully is for the byte code

push constant 5

which is translated to:

@5
D=A
@256
M=D

As I said, the assembly language for Hack is found in the link I provided but basically:

@5  // Load constant 5 to Register A
D=A // Assign the value in Reg A to Reg D
@256// Load constant 256 to Register A
M=D // Store the value found in Register D to Memory Location[A]

Well this was pretty straight forward. By definition memory location 256 is the top of the stack. So

push constant 5
push constant 98

will be translated to:

@5
D=A
@256
M=D
@98
D=A
@257
M=D

which is all fine..

I also want to give one more example:

push constant 5
push constant 98
add

is translated to:

@5
D=A
@256
M=D
@98
D=A
@257
M=D
@257  // Here starts the translation for 'add' // Load top of stack to A
D=M   // D = M[A] 
@256  // Load top of stack to A 
A=M   // A = M[A]
D=D+A
@256
M=D

I think it is pretty clear.

However I have no idea how I can translate the byte code

eq

to Assembly. Definition for eq is as follows:

Three of the commands (eq, gt, lt) return Boolean values. The VM represents true and false as -1 (minus one, 0xFFFF) and 0 (zero, 0x0000), respectively.

So I need to pop two values to registers A and D respectively, which is quite easy. But how am I supposed to create an Assembly code that will check against the values and push 1 if the result is true or 0 if the result is false?

The assembly code supported for Hack Computer is as follows:

enter image description here enter image description here enter image description here

I can do something like:

push constant 5
push constant 6
sub

which will hold the value 0 if 2 values pushed to the stack are equal or !0 if not but how does that help? I tried using D&A or D&M but that did not help much either..

I can also introduce a conditional jump but how am I supposed to know what instruction to jump to? Hack Assembly code does not have something like "skip the next 5 instructions" or etc..

[edit by Spektre] target platform summary as I see it

  • 16bit Von Neumann architecture (address is 15 bits with 16 bit Word access)
  • Data memory 32KW (Read/Write)
  • Instruction (Program) memory 32KW (Read only)
  • native 16 bit registers A,D
  • general purpose 16 bit registers R0-R15 mapped to Data memory at 0x0000 - 0x000F
  • these are most likely used also for: SP(R0),LCL(R1),ARG(R2),This(R3),That(R4)
  • Screen is mapped to Data memory at 0x4000-0x5FFF (512x256 B/W pixels 8KW)
  • Keyboard is mapped to Data memory at 0x6000 (ASCII code if last hit key?)

enter image description here

It appears there is another chapter which more definitively defines the Hack CPU. It says:

The Hack CPU consists of the ALU specified in chapter 2 and three registers called data register (D), address register (A), and program counter (PC). D and A are general-purpose 16-bit registers that can be manipulated by arithmetic and logical instructions like A=D-1 , D=D|A , and so on, following the Hack machine language specified in chapter 4. While the D-register is used solely to store data values, the contents of the A-register can be interpreted in three different ways, depending on the instruction’s context: as a data value, as a RAM address, or as a ROM address

So apparently "M" accesses are to RAM locations controlled by A. There's the indirect addressing I was missing. Now everything clicks.

With that confusion cleared up, now we can handle OP's question (a lot more easily).

Let's start with implementing subroutine calls with the stack.

     ; subroutine calling sequence
     @returnaddress   ; sets the A register
     D=A
     @subroutine
     0 ; jmp
  returnaddress:

     ...

  subroutine: ; D contains return address
  ; all parameters must be passed in memory locations, e.g, R1-R15
  ; ***** subroutine entry code *****
     @STK
     AM=M+1         ; bump stack pointer; also set A to new SP value
     M=D            ; write the return address into the stack
  ; **** subroutine entry code end ***
     <do subroutine work using any or all registers>
  ; **** subroutine exit code ****
     @STK
     AM=M-1         ; move stack pointer back
     A=M            ; fetch entry from stack
     0; jmp         ; jmp to return address
  ; **** subroutine exit code end ****

The "push constant" instruction can easily be translated to store into a dynamic location in the stack:

     @<constant>  ; sets A register
     D=A         ; save the constant someplace safe
     @STK
     AM=M+1         ; bump stack pointer; also set A to new SP value
     M=D            ; write the constant into the stack

If we wanted to make a subroutine to push constants:

   pushR2: ; value to push in R2
     @R15           ; save return address in R15
     M=D            ; we can't really use the stack,...
     @R2            ; because we are pushing on it
     D=M
     @STK
     AM=M+1         ; bump stack pointer; also set A to new SP value
     M=D            ; write the return address into the stack
     @R15
     A=M
     0 ; jmp

And to call the "push constant" routine:

     @<constant>
     D=A
     @R2
     M=D
     @returnaddress   ; sets the A register
     D=A
     @pushR2
     0 ; jmp
  returnaddress:

To push a variable value X:

     @X
     D=M
     @R2
     M=D
     @returnaddress   ; sets the A register
     D=A
     @pushR2
     0 ; jmp
  returnaddress:

A subroutine to pop a value from the stack into the D register:

   popD:
     @R15           ; save return address in R15
     M=D            ; we can't really use the stack,...
     @STK
     AM=M-1         ; decrement stack pointer; also set A to new SP value
     D=M            ; fetch the popped value
     @R15
     A=M
     0 ; jmp

Now, to do the "EQ" computation that was OP's original request:

EQ: ; compare values on top of stack, return boolean in D
      @R15         ; save return address
      M=D
      @EQReturn1
      D=A
      @PopD
      0; jmp
@EQReturn1:
      @R2
      M=D        ; save first popped value
      @EQReturn2
      D=A
      @PopD
      0; jmp
@EQReturn2:
      ; here D has 2nd popped value, R2 has first
      @R2
      D=D-M
      @EQDone
      equal; jmp
      @AddressOfXFFFF
      D=M
EQDone: ; D contains 0 or FFFF here
      @R15
      A=M         ; fetch return address
      0; jmp

Putting it all together:

     @5           ; push constant 5
     D=A
     @R2
     M=D
     @returnaddress1
     D=A
     @pushR2
     0 ; jmp
  returnaddress1:

     @X                ; now push X
     D=M
     @R2
     M=D
     @returnaddress2 
     D=A
     @pushR2
     0 ; jmp
  returnaddress2:

     @returnaddress3   ; pop and compare the values
     D=A
     @EQ
     0 ; jmp
  returnaddress3:

At this point, OP can generate code to push D onto the stack:

     @R2                ; push D onto stack
     M=D
     @returnaddress4 
     D=A
     @pushR2
     0 ; jmp
  returnaddress4:

or he can generate code to branch on the value of D:

     @jmptarget
     EQ ; jmp

What would be a good methodology for learning how computers and computer programming works?

For example, would you recommend learning how circuits work, then assembly language, and then higher level languages?

Thats a tall order.

Hardware side:

  • build a cheap computer, I've always liked Arstechnica's build guides.
  • Read tons of architecture articles.
  • Install different OSs (windows, linux, etc)

Software side:

  • Learn Assembly
  • Starter book on C
  • Deep C Secrets by Peter Van Der Linden (awesome book)

Random other good books

Keep reading, keep asking questions, keep learning.

You could read Code: The Hidden Language of Computer Hardware and Software from Charles Petzold. It provides a very nice historical perspective on the development of computers.

It's a easy and very good read in my opinion.

I wanted to learn exactly what you're looking for. Of course, the full answer is: never stop learning etc... but if you want the most condensed self-paced crash course, read Charles Petzold's Code: The Hidden Language of Computer Hardware and Software then read The Elements of Computing Systems: Building a Modern Computer from First Principles.

This will jump-start your overall understanding better than a half dozen or more specialized university courses.

There's no magic bullet here and these books don't contain any secrets. They are just super-focused with exactly the goal of understanding computer related concepts in an accessible way from top to bottom.

Read Danny Hillis's The Pattern on the Stone. Learn to program. After you've been programming for a while, if you're still interested, check out The Elements of Computing Systems: Building a Modern Computer from First Principles. By then you'll have seen plenty of pointers to more things to study.

I have good knowledge of C++ and after reading The Elements of Computing Systems I have a basic knowledge of how computers work. I made a list of topics I want to learn next and books I want to buy on those topics. One of them is operating systems, but the one on the top of the list is Game development.

I am still a noob on those topics, so I wonder if I should know how an operating system (unix specifically) works before trying to learn game programming (Opengl, etc). On operating systems I have the book Operating Systems by Tanenbaum, and I want to buy The Linux Programming Interface by Michael Kerish.

On game development I was planning on buying Game Engine Architecture and Game Coding Complete to acquire a general concept of game programming and how engines work and then learn Opengl.

I am really lost on what to do first and I hope this is an appropriate question. What should I learn first, what books should I read and in what order. Should I learn how a VGA works before trying Opengl? Are there any other topics I should know before delving into games programming. I am asking this because I like to know what I am coding, what the functions I am calling do under the hood, I don't like holes in my knowledge.

Thanks.

Fluffy opinion answer incoming. Take with grain of salt.

The nice thing about programming is that that you don't need to learn everything about everything to do one thing effectively. Knowing exactly how to implement a video driver isn't required for using OpenGL effectively. The point of OpenGL is to abstract that out so you don't have to worry.

Since you want to do game development, make a project. Like recreating Asteroids using OpenGL for graphics and writing all the game logic yourself. And set about completing it. In the process you'll learn much more than simply reading. Use books as reference. At least thats what I've found works for me.

The Operating Systems book is pretty good. Its the one I read in college. But those concepts presented in it, though interesting, are not something you'll have trouble learning simultaneously with game development or anything else.

Also you should read this: http://www.linuxforu.com/tag/linux-device-drivers-series/. It's a great article series that teaches linux driver development and operating systems concepts in the process.