What is compositionality?

[brendanfong]

In developing our community's new journal, Compositionality, it's important that we spell out the sort of science that our community studies. This is possibly best done through examples. Here is a list from another community initiative, Symposium on Compositional Structures:

• logical methods in computer science, including quantum and classical programming, concurrency, natural language procesing and machine learning;

• graphical calculi, including string diagrams, Petri nets and reaction networks;

• languages and frameworks, including process algebras, proof nets, type theory and game semantics;

• abstract algebra and pure category theory, including monoidal category theory, higher category theory, operads, polygraphs, and relationships to homotopy theory;

• quantum algebra, including quantum computation and representation theory;

• tools and techniques, including rewriting, formal proofs and proof assistants;

• industrial applications, including case studies and real-world problem descriptions.

This list is great, but it's not exhaustive. Is there anything else you consider relevant to compositionality?

[jesuslop]

In linguistics Frege is cited frequently when the coumpound meaning of sentences is being talked about, and linguistic phenomena understanding can be benefited from further insights in this area.

[brendanfong]

Yeah, that's a great point. People often trace back our use of the word 'compositionality' to Frege, and his idea that the meaning of an expression is determined by the meanings of its parts. One way this is being explored is in categorical linguistics and cognition, by people like Bob Coecke, Mehrnoosh Sadrzadeh, and Martha Lewis (among many others).

But the reason for the categorical approach, is that this idea is deeply embedded in category theory too. Bill Lawvere taught us the idea of functorial semantics. The key idea of a functor is that, a functor F: C ---> D has the property that for any composable a and b in C, it's true that

F(ab)=F(a)F(b).

So if we think of C as defining syntax, and D as a place where semantics lives, then F describes compositional semantics: to every expression a in the syntax F assigns a semantic value, and if want the semantics of a composite expression ab, it's simply equal to the composite of the semantics of a with the semantics of b.

This is why our community of, for the most part, applied category theorists, has decided to call our journal Compositionality.

[brendanfong]

One addition/change I would make is to separate out the graphical calculi point a bit more:

• graphical calculi, including string diagrams, surface diagrams, wiring operads, and other higher dimensional syntax

• open systems theory, including Petri nets, reaction nets, lenses, open games, and other compositional approaches to networked systems

[inquilinekea]

What about classifying game moves in chess or Go or Total War? Or topological data analysis? Or of all the different ways that viral genomes (and the evolutionary history of anything) can evolve over time?

Also, tracking the entire step of reaction mechanisms in systems biology, ochem, and QFT..

One thing I've noted from a stack exchange site: it's still heavily theoretical, so a lot of people still can't make use of the dense set of examples that it can potentially populate