Difference between abstract machines and calculi

So, first of all: I'm not sure how to tag this question. Feel free to tag it differently.

I recently started reading up on CHAMs, which can express different process calculi. Slightly confused, I go to read up on abstract machines. Okay, so, abstract machines are... machines in which you can express algorithms...

My thought process then was: [...] algorithms, which are expressed in math... which is what the calculi are for.

So, from my understanding, there's some sort of implicit layering going on here where somewhere up the math-ladder there's this abstract machine which can be used to express more mathematically pure calculi, and somewhere embedded in that jumble is the concept of an algorithm expressed in the math... of the abstract machine?

What is the difference between abstract machines and calculi, if there is one?

If there is a difference, what draws the line between abstract machines and calculi?

• Without having though about this deeply, I would think that such terms are used informally. I guess that typically calculi work at a higher level of abstraction while machines model more detail. – Martin Berger Jan 8 '14 at 15:20
• The CHAM is a good example of this terminological ambiguity because depending of how you look at it, it's really high level, or really low level. – Martin Berger Jan 8 '14 at 15:39
• The CHAM is based on rewriting. This is a very basic concept (e.g. read www21.in.tum.de/~nipkow/TRaAT or joerg.endrullis.de/downloads/lics2012-tutorial.pdf), that can express more complex formalisms and semantics (expressed as calculi or abstract machine semantics). There you can get a better feeling on where the CHAM stands. – gfour Jan 26 '14 at 12:36

2 Answers

I essentially agree with Martin's comment, I can elaborate on that to make a tentative answer, knowing that there is no general formal definition of calculus or abstract machine and that what I am going to describe cannot possibly cover the meaning of all instances of these two words found in the literature.

In brief: a calculus usually gives you the abstract spefication of the meaning of programs, whereas an abstract machine usually implements that specification. Such an implementation is likely to be still high-level (i.e., many low-level details are not specified), hence the adjective "abstract", but it gets closer to what a phyisical machine would do to execute programs (according to the spefication given by the calculus).

More in detail: a calculus usually comes with an operational semantics, which gives you the meaning of programs in terms of the result they denote (if any). For this, one often uses the notation

$t\Downarrow v$,

which means that "the value (i.e., the final result) of the expression $t$ is $v$". Now, such a "big step" operational semantics (as it is sometimes referred to) is usually given in terms of a derivation system (i.e., a system in which you can prove judgments of the form $t\Downarrow v$), which is useful to reason abstractly about programs but is a bit far from describing how the execution of $t$ would look like on a concrete machine.

One may then move to a "small step" operational semantics, which is a set of rewriting rules on expressions (written $t\rightarrow t'$) describing how one can, step by step, compute the value of an expression (if any):

$t\Downarrow v\quad$ iff $\quad t\rightarrow^\ast v$.

Now, even the small-step semantics may be too coarse: typically, some rewriting rules may duplicate arbitrary big sub-expressions, and a chain of duplications may cause an exponential blow-up of the size of expressions in only a linear number of steps, which means that these steps are not so "small" after all... In particular, one may want to give a more realistic description of the execution of programs, getting even closer to the machine level. This is where abstract machines come into the picture.

It is impossible to give a general description of an abstract machine, since they may differ greatly. However, these usually include low-level components (e.g. a pointer to a "code memory" where the executed program is stored, a stack, a memory for storing the values of variables, etc.) which make them look much more like physical machines executing the programs of the language underlying the original calculus.

About where to "draw the line" between calculi and machines: this is actually a tricky question. There are calculi whose small-step semantics is more or less the same thing as an abstract machine. Lambda-calculi with explicit substitutions are examples of this: in such calculi, expressions contain constructs (the explicit substitutions) which make it possible for the small-step semantics to operate at a lower level, much closer to that of the machine.

About your reasoning on how the levels of expression of an algorithm are "layered", I am not sure I follow it, so I cannot say much. But I hope that at least I gave you some elements of answer to your last two questions.

• I'm not sure it's ideal to bring in the distinction between small and large step operational semantics. The reason is that certain interesting computational phenomena (e.g. non-termination or computation getting stuck) cannot be easily or naturally berepresented by big-step reduction relations, regardless of abstraction level. – Martin Berger Jan 9 '14 at 17:22
• I agree, but I thought that mentioning the difference would be useful to show that abstract machines are just one level (the lowest) of a "gradient" of ways of defining the operational meaning of programs, the highest level being "only the result matters" (i.e., big-step operational semantics). – Damiano Mazza Jan 10 '14 at 10:22
• You two might be interested in Leroy and Grall's work on coinductive reasoning about programs using big-step semantics (gallium.inria.fr/~xleroy/coindsem). They show that one can reason about nontermination of programs by either 1) using additional inference rules for nonterminating programs; or 2) interpreting the original inference rules coinductively (i.e. as a greatest fixpoint of the iterating function defined by the rules). – Neil Toronto Jan 13 '14 at 20:00
• @NeilToronto Yes, that's right. That's why I used the qualifier "easily or naturally". If your semantics also has additional error conditions, big-step can get more complicated than the corresponding small-step semantics. – Martin Berger Jan 13 '14 at 22:17

I would add that, typically, one uses the term "calculus" when the evaluation rules are expressed at the level of the source language. One use the term "abstract machine" when addition "machine-level" concepts are used in describing the evaluation (such as stores, pointers, stacks, etc.).