14
$\begingroup$

I think I'm pretty confused about what's called a calculus and what's called a programming language.

I tend to think, and might have been told, that a calculus is a formal system for reasoning about the equivalence of programs. Programs have an operational semantics specified by a machine, that should (I think?) be deterministic. In this way, a (correct) calculus for a language $L$ is a proof method for program equivalence.

This seems like a reasonable split to me, but is this the commonly accepted meaning? Or maybe it's even wrong?

Related, why are some operational semantics nondeterministic (assume it is confluent)? What is gained from leaving the choice of strategy open?

I'd really appreciate some clarification on these; and concrete references even more! Thanks!

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ They are different words for different ways of looking at the same thing. $\endgroup$
    – Raphael ♦
    Jun 13, 2017 at 4:47
  • 1
    $\begingroup$ @Raphael, how does it answer the question? This is not the place to do philosophy. $\endgroup$
    – fade2black
    Jun 13, 2017 at 4:58
  • 4
    $\begingroup$ Sometimes a little philosophy is necessary, anywhere. $\endgroup$
    – André Souza Lemos
    Jun 13, 2017 at 14:24

3 Answers 3

Reset to default
10
$\begingroup$

The meaning of the words is not fixed, but I can give you my interpretation.

A calculus is something that we calculate with in the sense of juggling equations (think manipulation of Taylor series or computation of integrals in analysis). A calculus tells us what the rules of manipulation are, but not which ones we should used in a given situation.

A programming language is something that tells us how to calculate. It tells us precisely how to use the rules. We typically let the computer use the rules, as it is much faster. The rules may be non-deterministic, and there may be very good reasons for them being non-deterministic. It may be in the nature of the calculus that it is non-deterministc (think concurrent communicating processes), or fixing a particular strategy may be detrimental to implementation techniques and optimization.

For example, the $\lambda$-calculus is an equational theory. There are expressions and equations telling us when expressions are equal. The equations do not tell us how to apply them, although people usually have hidden agendas and they present the equations so that later on they can derive useful evaluation strategies from them. But in its essence $\lambda$-calculus is a bunch of equations. It is not a programming language.

In contrast, Standard ML is a programming language. It is given in terms of operational semantics, i.e., rules of computation. There are derived notions of equality (contextual equivalence, observational equivalence, etc.) which we can put on top of it to think of it as a kind of calculus.

Of course, there are often useful connecitons between a calculus and its manifestation as a programming language. Confluent normalization is just one way of passing from the calculus to the programming language (although sadly some people have made it into a religion of sorts). The interplay between calculi and programming languages is important: the programming languages can actually be used, but the calculi explain what the programs are about.

Just to annoy people, let me also state that pretending that there is no difference between a calculus and its operational manifestation sometimes leads to skewed views of programming and mini-religions within the programming community. You may try to guess which language I have in mind. (It's a very cool language!)

Improve this answer
$\endgroup$
9
  • $\begingroup$ So a programming languages is a calculus equipped with a strategy / rewriting system compatible with it? $\endgroup$
    – xavierm02
    Jun 13, 2017 at 9:54
  • $\begingroup$ Well, maybe. Do operational steps always preserve meaning? That is, if a program $p$ makes one step computation to a program $p'$, do we necessarily want to require that $p = p'$? $\endgroup$
    – Andrej Bauer
    Jun 13, 2017 at 14:21
  • $\begingroup$ I'd say no because of the labels on the transitions in $\pi$-calculus. I think it fits in you classification as a programming language (even though I think I've also seen it presented by equations, but it's not the natural way to define it, and those equations don't really represent computations). $\endgroup$
    – xavierm02
    Jun 13, 2017 at 14:39
  • $\begingroup$ You could present equations that speak not only about the program but also about its environment (state or transitions). But I wouldn't say such a thing is a calculus. Rather it's an algebraic model. $\endgroup$
    – Andrej Bauer
    Jun 13, 2017 at 15:36
  • $\begingroup$ Thanks a lot, Andrej, this makes sense to me. I realize it might vary from person to person, but I'm accepting this answer as (I think) it's the best one. $\endgroup$
    – Guido
    Jun 23, 2017 at 22:32
1
$\begingroup$

The goal of calculi is not just to study program equivalences, it's to study programs. An example of fancy calculus is this where the strategy (call-by-value or call-by-name) is determined locally. It could be implemented someday in a programming language but it's first studied as a calculus. You also use calculi to study type systems (with some calculi such as the one in Martin-Löf type theory also computing types).

I believe the main difference is that calculi are meant to be (relatively) easy to study formally while programming languages are meant to be (relatively) easy to use. This leads the the following differences:

Calculi tend to be minimalist while PLs tend to have redundancy (for loop when you already have while loop, switch when you already have if, ...) to make expressing what you want easier.

Calculi have fully specified semantics, while a PLs semantics is often described by a default interpreter / compiler.

Some operational semantics are non-deterministic because it allows:

  • To prove things about all "subsemantics".
  • To allow implementation to choose and therefore to (maybe) speed up things.
  • Because sometimes, you have a "radnom()" operation, and if you don't care about probabilities but only what's possible, non-determinism is a good way to represent it.

Note that call-by-value is non-deterministic: You can choose to evaluate either the function or the argument first.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Nah, I disagree that it's about level of formalization or sophistication. $\endgroup$
    – Andrej Bauer
    Jun 13, 2017 at 9:42
1
$\begingroup$

"Programming language" and "calculus" are polysemic terms, that is, they mean different things depending on the context.

In some contexts, programming languages and calculi have converged to refer to the same concept, that of a rewriting system based on a set of formal rules that can be "mechanically" applied.

The reason why this convergence is occasionally enigmatic to us (but not to working software developers or mathematicians) is that our job is to conceive concrete programming languages as if they were calculi, and to physically embody calculi in concrete programming languages.

To answer your question directly, the confusion between calculi and programming languages (to the extent that it exists) is not an accident, but a project. Our project. It is a testament of our relative success as a scientific discipline.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.