Languages from Turing Machine

From Turing Machine to von Neumann Architecture

• 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.

Programming languages designed for the von Neumann architecture

• Examples:

  1. FORTRAN
  2. C / C++
  3. Java
  4. Python
  5. $\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.

von Neumann languages going beyond TM

• 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`
      }
  }
  

More about von Neumann languages

• 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.