5
$\begingroup$

In linear logic multiplicative disjunction is often called par. This terminology goes back at least to Girard's seminal text Linear logic. I vaguely remember that I read that "par" is an abbreviation for "parallel“. If so, why? Does anyone know the etymology of the term?

EDIT: In Linear logic and parallelism Girard calls par the "parallel connective".

$\endgroup$

2 Answers 2

4
$\begingroup$

That's right; 'par' is from 'parallelisation'. The following two quotes from Girard may be illuminative about the significance of parallelisation in linear logic:

(ii) The new connectives of linear logic have obvious meanings in terms of parallel computation, especially the multiplicatives. In particular, the multiplicative fragment can be seen as a system of communication without problems of synchronization. The synchronization is handled by proof-boxes which are typical of the additive level. Linear logic is the first attempt to solve the problem of parallelism at the logical level, i.e., by making the success of the communication process only dependent of the fact that the programs can be viewed as proofs of something, and are therefore sound.

[Linear Logic in Theoretical Computer Science 50, 1987, p. 3]

Furthermore, multiplicative connectors and rules can be generalised to make a genuine programming language. [Footnote] Cut elimination is in fact parallel communication between processes. In this language, logic does not ensure termination, but absence of deadlock.

[emphases in the original, Proofs and Types, 2003 Web edition, p. 154]

See also Di Cosmo and Miller's article Linear Logic.

$\endgroup$
2
  • $\begingroup$ Thank you. However, I fail to see linear logic's "obvious meanings in terms of parallel computation." What are they? How can the multiplicative fragment be seen "as a system of communication without problems of synchronization"? $\endgroup$ Apr 17, 2022 at 7:47
  • $\begingroup$ I recommend you to go through Girard's paper Linear Logic and Parallelism, I think it gives quite a clear explanation. You may download it from here also. $\endgroup$ Apr 17, 2022 at 9:27
0
$\begingroup$

Although historically the name 'par' does come from 'parallelism', it is interesting to note that recently Girard seems to have changed his point of view, in an attempt to give a quantum physics interpretation of linear logic.

In the paper "Schrödinger’s cut" self-published on his website (written in French), he says explicitly that 'par' stands for 'partage', meaning 'sharing' in French, and that it denotes quantum superposition. Although traditionally it is the additive conjunction which is understood as a sharing construct, in the sense of resource-sharing...

A possible reconciliation may be found in the proof-as-process interpretation of linear logic: in this setting multiplicative disjunction is understood as the parallel composition of two processes. That is, they can execute computation independently in parallel, but they can also exchange messages through shared communication channels. For more details, I recommend the recent article Par means parallel: multiplicative linear logic proofs as concurrent functional programs.

Also in his latest paper "Schrödinger’s cut III", Girard reassigns the 'parallel' interpretation to the additive disjunction 'plus', by describing the two premisses of the disjunction elimination rule in natural deduction as playing the role of 'parallel worlds'.

All this should be taken with a grain of salt though, given the playful, provocative and unscientific nature of Girard's latest writings...

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .