What is a "model of computation"?

Question

... What does it mean that in C++ and Java the model of computation is "that of the computer"? Why is that not the case for functional languages?

---

I'm reading Bjarne Stroustrup's interview form Masterminds of Programming, of which I copy the relevant excerpt below:

In the context of C++ and other languages, "close to the hardware" means that the model of computation is that of the computer — sequences of objects in memory and operations as defined on objects of fixed sized — rather than some mathematical abstraction. This is true for both C++ and Java, but not for functional languages. C++ differs from Java in that its underlying machine is the real machine rather than a single abstract machine.

What does that mean, in practical terms?

From the quote above, as far as this "model of computation" thing goes, I'd draw the conclusion that there's three categories of languages (I guess the boundaries are shaded, though...?)

• Like C++ ("model of computation of the actual computer")
• Like Java ("model of computation of an abstract computer")
• Functional languages ("model of computation of a non-computer")

I kinda of see how the 3 differ, but I can't really map this to anything that could help me understand what the meaning of "model of computation" is.

Answer 1

What Stroustrup probably is referring to is the imperative vs. (pure) functional distinction:

The imperative school typically starts with a model of computation like Turing Machines: You have states, a tape which holds data, and a head which works on the tape and can overwrite or move left or right and change state based on the state and tape content it's currently on.

Real computers can - very roughly - be modeled as RAM Machines. You have RAM and can write to arbitrary cells in constant time (effects like cache locality may matter in practice, but are ignored for simplicity). The computer executes assembly instructions, which may operate on the RAM (but most often operate on registers for performance, another feature our simplistic model omits). You have arithmetic operations, conditional jumps, unconditional jumps, memory stores and writes, etc.

C compiles pretty transparently to assembly (at least with optimizations disabled; for example, ++ will probably map to the INC instruction on x86 - you can easily see how most operators correspond directly to assembly); C was designed to work well with various assembly languages, and later on, following its popularity, assembly languages were influenced by C (e.g. LEA in x86).

Consider the following simple "sum" example from Godbolt:

int testFunction(int* input, int length) {
  int i, sum = 0;
  for (i = 0; i < length; ++i)
    sum += input[i];
  return sum;
}

and the corresponding assembly:

testFunction:
        push    rbp
        mov     rbp, rsp
        mov     QWORD PTR [rbp-24], rdi
        mov     DWORD PTR [rbp-28], esi
        mov     DWORD PTR [rbp-8], 0
        mov     DWORD PTR [rbp-4], 0
        jmp     .L2
.L3:
        mov     eax, DWORD PTR [rbp-4]
        cdqe
        lea     rdx, [0+rax*4]
        mov     rax, QWORD PTR [rbp-24]
        add     rax, rdx
        mov     eax, DWORD PTR [rax]
        add     DWORD PTR [rbp-8], eax
        add     DWORD PTR [rbp-4], 1
.L2:
        mov     eax, DWORD PTR [rbp-4]
        cmp     eax, DWORD PTR [rbp-28]
        jl      .L3
        mov     eax, DWORD PTR [rbp-8]
        pop     rbp
        ret

as you can see, this is a pretty transparent abstraction over the way computers work under the hood; this is what makes C so efficient.

Functional programming attacks everything from a different angle often criticized as not being sufficiently C-like: As fundamental model of computation, you start with Lambda Calculus: You can create and apply anonymous functions; functions themselves are first-class and can be passed around freely as parameters. This is not close to assembly at all (though there were developments such as Lisp machines to make machines be closer to functional programming in the past). One main difference lies in mutability: Functions are pure; they can not mutate anything. From a programmer's perspective, this has the advantage of eliminating unwanted side effects. But from a hardware perspective, it's not close at all to how we would want to express computation on a RAM machine: Going back to our simple sum example, we have two variables we're mutating there - i and sum. These will go in registers / memory cells which we will mutate. This isn't possible in functional programming; we'd have to write a (tail-)recursive function instead which manages i and sum as parameters. Also, remember the array? This is close to how memory works: You have one big indexable array of bytes. In functional programming, you typically don't start out with arrays; instead, you'd use a linked list. The ability to just instantiate functions also implies some kind of object management is required; this typically entails some kind of garbage collection / reference counting. (Note that functional programming languages aren't all bad. Lack of side effects makes it much easier to reason about programs. For example you get parallelizability of function execution for free.)

Ultimately, Turing Machines, RAM Machines, and Lambda Calculus are all turing-complete - everything that can be computed with any of these models of computation can be computed with any other just as well, but RAM Machines are closest to the actual computers we use.

C, C++ and Java are all (among other things) imperative languages. In contrast to C and C++, Java has typically used a virtual machine (the JVM; there are Java AoT compilers that target machine code as well, though). This allows it much better platform-independence; the VM has to guarantee f.e. that two's complement is used for integers (whereas in C relying on the underlying representation of ints is undefined behavior - after all some CPUs may be using one's complement). The Java VM also has the notable difference of being stack- rather than register-based and including a garbage collector. In general, bytecode interpretation is slower than directly executing assembly on the bare metal due to the interpreter overhead.

(It should also be noted that C++ and Java are rather complex now. Both of them have to a fair degree been influenced by functional programming. For example Java has closures, which mean the subset of Java using just closures is effectively Lambda Calculus; that is, pure functional programming is possible with Java. The same goes for C++. But for the most part code written in these languages is still imperative.)