• Peter J. Landin, The Mechanical Evaluation of Expressions, 1964: applicative expressions, syntactic sugar, evaluation, environment, abstract machine (Papers We Love presentation)

• Peter J. Landin, The Next 700 Programming Languages, 1966: ISWIM family of programming languages, functional core, imperative features, equivalence rules, declarative languages. (This paper ends with the transcript of an interesting discussion that is still relevant today, over 50 years later.)

• John C. Reynolds, Definitional Interpreters for Higher-Order Programming Languages, 1972 / 1998: meta-circular interpreter, defunctionalization, continuation-passing style (Papers We Love presentation)

• Paul Hudak, The Conception, Evolution, and Application of Functional Programming Languages, 1989: history of functional programming languages, including lambda calculus, Y combinator, order of evaluation, call by value, call by name, and call by need (lazy evaluation)

• Christopher Strachey, Fundamental Concepts in Programming Languages, 2000: L-values and R-values, call by value, call by reference, first-class objects, ad hoc polymorphism, parametric polymorphism (Papers We Love presentation)

That’s it for now. I hope to grow this list over time.

match Unix.fork () with
| 0 -> (* child process *)
| pid -> (* parent process *)

Short and sweet, but besides being pleasant to read, is this code actually safe? What if Unix.fork returns -1? Well, it can’t. Unix.fork calls a C function that starts with the following lines of code:

int ret;
ret = fork();
if (ret == -1) uerror("fork", Nothing);

That is, if the actual system call fails, Unix.fork raises an exception that may terminate our program. We can’t accidentally kill -1 because pid is guaranteed to be a valid process ID.

If this sounds interesting, I recommend checking out Unix Systems Programming in OCaml.

An ordinary type such as [a] may depend on other types – in our case, the types of list elements – but not on the values of those elements or their number. A dependent type does depend on such dynamic values. […] One should distinguish a dependent type (which depends on a dynamic value) from a polymorphic type such as Maybe a. The type List n a from our running example is indexed by the value (the list length) and by the type (of its elements): it is both dependent (in n) and polymorphic (or, technically, parametric), in a.

In other words, List n a is parameterized by a value in addition to a type.

The different nature of the two arguments in List n a has many consequences: since the list length n is a natural number, one may apply to it any operation on natural numbers such as addition, increment, multiplication, etc.

The article brings up an interesting example in which the type checker must be convinced that List (n+m) a and List (m+n) a are the same type.

Now, deciding if two types are the same involves determining if two expressions are equal, which is generally undecidable (think of functions or recursive expressions). There is a bigger problem: in our example, n and m are just variables, whose values will be known only at run-time. The type-checker, which runs at compile-time, therefore has to determine that n+m is equal to m+n without knowing the concrete values of n and m. We know that natural addition is commutative, but the type-checker does not. It is usually not so smart to figure out the commutativity from the definition of addition. Therefore, we have to somehow supply the proof of the commutativity to the type-checker. Programming with dependent types involves a great deal of theorem proving.

function f(a, b)
    print(a, b)
end

We can call f with as many arguments as we like. Missing arguments become nil, extra arguments are discarded:

f()        -- nil nil
f(1)       -- 1   nil
f(1, 2)    -- 1   2
f(1, 2, 3) -- 1   2

In fact, function f could be written as:

function f(...)
    local a, b = ...
    print(a, b)
end

The reference manual has the following to say about local a, b = ...:

Before the assignment, the list of values is adjusted to the length of the list of variables. If there are more values than needed, the excess values are thrown away. If there are fewer values than needed, the list is extended with as many nil’s as needed. If the list of expressions ends with a function call, then all values returned by that call enter the list of values, before the adjustment (except when the call is enclosed in parentheses; see §3.4).

There is no observable difference, whether we call f(1) or f(1, nil). But for some functions, there is. Suppose we have

table.insert(t, g())

where t is a table and g is a function that may or may not return a value. As long as g returns a value, including nil, everything works as expected. (We don’t mind appending nil to a table.) When g happens to return nothing, table.insert complains about a missing argument, which may be surprising, considering that Lua is supposed to adjust the number of arguments to the number of parameters:

stdin:1: wrong number of arguments to 'insert'
stack traceback:
    [C]: in function 'insert'
    stdin:1: in main chunk
    [C]: in ?

We can introduce a variable

local b = g()
table.insert(t, b)

or put parentheses around the call to g

table.insert(t, (g()))

to force exactly one result, turning nothing into nil, as if g returned nil. And nil is not nothing. All three functions

function f() end
function g() return end
function h() return nil end

are interchangeable when used liked this:

local x = f(); print(x) -- nil
local y = g(); print(y) -- nil
local z = h(); print(z) -- nil

But only h returns nil, whereas f and g return nothing:

print(f()) --
print(g()) --
print(h()) -- nil

for i = 1, 5 do
    print(i)
    if i == 3 then i = i + 1 end
end

The numbers from 1 to 5, skipping 4? Because that’s what we expect from an equivalent loop in, say, C++:

for (int i = 1; i <= 5; i++) {
    std::cout << i << "\n";
    if (i == 3) i++;
}

Except it’s not equivalent. Lua’s for-loops are implemented in terms of while. Above example is translated to:

do
    local _i, _end, _step = 1, 5, 1
    while _i <= _end do
        local i = _i
        print(i)
        if i == 3 then i = i + 1 end
        _i = _i + _step
    end
end

Quoting from Programming in Lua:

The for loop has some subtleties that you should learn in order to make good use of it. First, all three expressions are evaluated once, before the loop starts. […] Second, the control variable is a local variable automatically declared by the for statement and is visible only inside the loop. […] Third, you should never change the value of the control variable.

Some 20 years ago I wanted to develop a tool to design VLSI chips. I didn’t have a Forth for my new PC, so I thought I’d try a different approach: machine language. Not assembler language, but actually typing the hex instructions. […] My conclusion was that Forth is more efficient than machine language. Partly because of its interactivity and partly because of its syntax.
—Charles Moore

My opinion is that OOP is one of the great frauds perpetrated on the community. […] OOP was designed so that its clients could claim superior wisdom for being on the “inside”. The truth of the matter is that the single most important aspect of OOP is an approach devised decades ago: encapsulation of subroutines and data. All the rest is frosting.
—Thomas E. Kurtz

The best way to avoid tough debugging is to write things very carefully in the first place.
—Brian Kernighan

Software engineering is in many ways a very pathetic field, because so much of it is anecdotal and based on people’s judgments or even people’s aesthetic judgments.
—Peter Weinberger

C is a reasonably good language for compilers to generate, but the idea that human beings should program in it is completely absurd.
—Bertrand Meyer

In my view, concurrent programming is concerned with coordination, whereas parallel programming is concerned with efficiency. In a way, you could say parallel programming is about avoiding coordination to the extent possible for the sake of performance. It seems reasonable to assume that concurrency and parallelism call for different tools.

Concurrent languages such as Go support parallelism basically out of the box: create a number of independent tasks and make sure they are scheduled by a pool of worker threads. Done in a few lines of code. Problem solved?

I agree that a single set of concurrency constructs is too limiting for the kind of parallel programs we’d want to write. Consider parallel loops, for example. Relatively straightforward to implement in Go, but starting a goroutine for each iteration? Hardly practical. This is not to say that goroutines and channels can’t be used to implement parallel loops efficiently; they can, it’s just more work. But programmers shouldn’t have to worry about goroutines and channels when all they want to do is run some iterations of a loop in parallel.

The simplest definitions I can think of are: Concurrency is dealing with multiple things at the same time (multiple things interleaved within the same time frame). Parallelism is multiple things happening at the same time (truly simultaneously).

That’s all. No mention of processes or threads, just “things”, which might be single instructions. Neither definition implies determinism or nondeterminism. There is deterministic concurrency (coroutines) as well as nondeterministic parallelism (threads). Concurrency may be the answer to our nondeterministic woes, but concurrency per se is a more general concept. Ditto for parallelism.

Given above definitions, it seems plausible to think of parallelism as an instance of concurrency: every parallel program is also a concurrent program. If there’s parallelism, and it doesn’t look like we’re dealing with multiple things at the same time, it’s because a lower level is taking care of it for us.

Can concurrency exist independently of parallelism? Certainly! Can parallelism exist independently of concurrency? That’s the more interesting question. I’m tempted to say no.