{:check ["true"]}
Turing Machine is powerful but cumbersome.
- No symbolic representation of states in control logic
- No organization in control logic
- No labeling of memory addresses
- No organization of memory
John von Neumann recognizes how electronics can be used to implement the universal Turing Machine while providing many crucially practical improvements.
- Programmable control logic
- Organize states of control logic into different processors
- Use variables to refer to memory addresses
- Use multiple types (fast vs slow) storage medium as memory, and connect them using data bus.
von Neuman and his team designed and implemented the first computer in 1949.
The design has deeply impacted the future computer design. Until the very recent proliferation of GPU, most of the computing is done using the same architecture.
Examples:
- FORTRAN
- C / C++
- Java
- Python
- $\dots$
Variables are used to memory addresses.
split=8
- C/C++ pointers
- Java variables are always pointers to objects
- Array variables are memory offsets
The reason is that data is stored in linearly indexed storage that are modeled after the tape of a TM.
Programs are sequences of statements.
split=8
- Statements are executed in sequence (by default)
- The order of execution is crucial to the correctness of the computation.
Statements correspond the state transition of the TM. The state transitions occur sequentially in a specific order.
Flow control constructs are necessary.
split=8
- Loop and iteration are necessary.
- Branching with if-else is necessary.
TM control logic offers branching and
goto
which is a form of primitive loops.
Statements are organized into functions:
void *
memcpy (void *dest, const void *src, size_t len)
{
char *d = dest;
const char *s = src;
while (len--)
*d++ = *s++;
return dest;
}
Functions are further organized:
box
For example: in Java
- Functions are grouped as methods of a class.
- One or more classe form a package.
Variables are scoped:
class Student {
String name;
void report(String name) {
print(name); // refers to argument `name`
}
void report() {
print(name); // refers to object field `name`
}
}
TM does not provide any syntactic constructions
TM is purely an mechanical specification of computation. Similarly processors based on the von Neumann architecture can only carry out primitive instructions (e.g. memory fetch, branching, register assignment, arithmetics).
box
von Neumann languages have very complex syntax specifications.
Each language must come up with their own human-friendly syntax.
Pro: when programmer is proficient with the syntax they can be highly productive in specifying large scale software.
Con: every language has its own syntax. While they are generally quite similar, to produce correct code, programmers must spend time to become proficient with a particular language.
Computation vs data description
Computation description (while-loop, if-else, assignments, etc) is different from data description (lists, hash-maps, scalars).
Code parsing and generation for von Neumann languages is hard.
box
More than half of the course Compilers will be dedicated to the specification, parsing and generation of code for the von Neumann architecture.
von Neumann languages are highly efficient and optimized.
box
The von Neumann architecture is so successful that it's still the most dominant design for modern CPUs.