Compositionality - What exactly is it?

xholonWorkbook.xml

<?xml version="1.0" encoding="UTF-8"?>
<!--Xholon Workbook http://www.primordion.com/Xholon/gwt/ MIT License, Copyright (C) Ken Webb, Wed Nov 20 2019 07:42:13 GMT-0500 (Eastern Standard Time)-->
<XholonWorkbook>

<Notes><![CDATA[
Xholon
------
Title: Compositionality - What exactly is it?
Description: 
Url: http://www.primordion.com/Xholon/gwt/
InternalName: f6c8079d9f26d21d725ff33bf5b17e05
Keywords: 

My Notes
--------
November 16, 2019

I could define Xholon as something like this.
Xholon is a tool for:
 * exploring things and the ways that things are combined,
 * constructing/building things from other things,
 * building shortcuts,
 * combining paths into shorter paths,
 * exploring exaptation,
    - my definition: you can only build something new from things that you already have on hand
    - and maybe: you can only get to X if you are currently adjacent to X
    - but see wikipedia for stricter "real" definitions
 * exploring how everything in the universe is connected,
 * exploring ways of combining independently-developed components/parts

I want to systematically explore "Compositionality", whatever that is.

"Compositionality" is another name for, and/or is closely related to "Applied Category Theory".


References
----------
(1) search: Compositionality

(2) https://en.wikipedia.org/wiki/Principle_of_compositionality
    In mathematics, semantics, and philosophy of language, the principle of compositionality is the principle
    that the meaning of a complex expression is determined by the meanings of its constituent expressions and the rules used to combine them.
    This principle is also called Frege's principle, because Gottlob Frege is widely credited for the first modern formulation of it.
    The principle was never explicitly stated by Frege, and it was arguably already assumed by George Boole decades before Frege's work.
    
    The principle of compositionality states that in a meaningful sentence, if the lexical parts are taken out of the sentence, what remains will be the rules of composition.
    Take, for example, the sentence "Socrates was a man".
    Once the meaningful lexical items are taken away—"Socrates" and "man"—what is left is the pseudo-sentence, "S was a M".
    The task becomes a matter of describing what the connection is between S and M. 

(3) https://plato.stanford.edu/entries/compositionality/
    Anything that deserves to be called a language must contain meaningful expressions built up from other meaningful expressions.
    How are their complexity and meaning related?
    The traditional view is that the relationship is fairly tight:
    the meaning of a complex expression is fully determined by its structure and the meanings of its constituents
    —once we fix what the parts mean and how they are put together we have no more leeway regarding the meaning of the whole.
    This is the principle of compositionality, a fundamental presupposition of most contemporary work in semantics.

(4) http://www.compositionality-journal.org/
    About
    Compositionality describes and quantifies how complex things can be assembled out of simpler parts.

(5) https://golem.ph.utexas.edu/category/2018/05/compositionality.html

(6) https://www.reddit.com/r/compositionality/
    Compositionality describes and quantifies how complex things can be assembled out of simpler parts.
    Compositionality, the journal, is a new diamond open-access journal for research using compositional ideas, most notably of a category-theoretic origin, in any discipline.
    Topics may concern foundational structures, an organizing principle, or a powerful tool.
    Example areas include but are not limited to: computation, logic, physics, chemistry, engineering, linguistics, and cognition.
    
    Posted byu/MakeTotalDestr0i - 1 year ago
    You are in an elevator at ground level headed to the top of the burj kalifa and you have to verbally explain compositionality to someone
    of slightly above average IQ with a general college-level body of knowledge before you get to the top. What is your elevator speech?
    
    aukkras
    Let me tell you something, we could have used stairs to get to the top, stopping at each floor, but we decided to make shortcut and use elevator.
    That's what commutativity is about - making shortcuts.
    And you know what ? If the floors wheren't connected with stairs we couldn't make this shortcut.
    That's what compositionality is about - making shortcuts possible ;)
    
    ThePhysicsDetective
    Compositionality is all about understanding complicated things because you understand simpler things, and how they interact or combine.
    For example, you use it to understand how a magnet works.
    Ever seen the Feynman interview? Here, I've got it on my laptop. Check this out:
    
    dxholmes
    If you want to understand something new, it helps to relate it to something you already know.
    You've probably seen a few powerful, recurring ideas in science and math;
    for example, the general idea of networks appears in chemistry, biology, probability theory, engineering, and so on.
    By searching for analogies between different areas, we can uncover these repeated patterns and to show the connections between them.
    These insights deepen our understanding and point the way to unexpected discoveries.
    Compositionality is, abstractly, the way in which things fit together.
    The surprise is that by studying how things fit together systematically,
    you learn more about the things themselves and are better able to discover analogies between different systems.
    That's what compositionality is, and why it serves as a useful organizing principle.
    
  ) https://www.reddit.com/r/compositionality/comments/8f4or7/compositionality_a_manifesto/
    a compositional perspective on the world; one that emphasises the study of a whole through not only its parts, but the precise way it is built up from its parts.
    'make science fun and cool again'
    
    What sorts of articles do we envision in Compositionality?
    We welcome theoretical articles, such as those in category theory, logic, and other mathematical tools for modelling composition.
    In particular, however, we hope to provide a new home for research of more computational and applied natures.
    We will welcome papers on implementation.
    
  ) https://www.reddit.com/r/compositionality/comments/8ipty1/what_is_compositionality/
    What is compositionality?
    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?
    
    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

  ) https://www.reddit.com/r/compositionality/comments/8ihbm5/software_for_ct/
    At ACT 2018, we had a long discussion about the state of categorical software, and our dreams for what software for applied category theory might look like in the next ten years.
    Here is an editable summary of our discussions, and a good resource for finding all sorts of category theory software, such as
    * Algebraic Query Language, which uses categorical structures to perform database queries,
    * Globular/Homotopy.io, a language for higher categories and higher dimensional programming,
    * Quantomatic, a tool for graph rewriting
    * TikZit, for drawing string diagrams.
    Other collections of categorical software can be found at Categorical Data, and we hope, eventually on the Applied Category Theory github. And programmers on the Azimuth Forum also have been discussing things to build.
    Have we missed any software projects? Do you have one you'd like to add, whether existing or still to be embarked upon? We'd love to hear about it.

(7) https://arxiv.org/abs/1803.05316
    Seven Sketches in Compositionality: An Invitation to Applied Category Theory
    Brendan Fong, David I Spivak
    (Submitted on 14 Mar 2018 (v1), last revised 12 Oct 2018 (this version, v3))

    This book is an invitation to discover advanced topics in category theory through concrete, real-world examples.
    It aims to give a tour: a gentle, quick introduction to guide later exploration.
    The tour takes place over seven sketches, each pairing an evocative application, such as databases, electric circuits, or dynamical systems,
    with the exploration of a categorical structure, such as adjoint functors, enriched categories, or toposes.
    No prior knowledge of category theory is assumed.
    
    A feedback form for typos, comments, questions, and suggestions is available here: this https URL
  ) https://docs.google.com/document/d/160G9OFcP5DWT8Stn7TxdVx83DJnnf7d5GML0_FOD5Wg/edit

(8) https://blog.statebox.org/modularity-vs-compositionality-a-history-of-misunderstandings-be0150033568
    Modularity vs Compositionality: A History of Misunderstandings, Fabrizio Romano Genovese, Sep 24, 2018
    Having worked on compositional structures for my PhD degree, I am used to hearing about compositionality a lot.
    Though to my utmost surprise, the word “compositionality” is not just confined to the academic environment as I believed,
    but is actually often used in enterprise as a buzzword connected to outrageous claims.

    We call a system modular when it is composed of various parts that can be linked to each other.

    Well, let me tell you, ninety-nine percent of the time you hear the word “compositionality” you are being (intentionally?) lied to.
    What people really mean is “modularity”.
    In fact, compositionality is an incredibly difficult property to achieve when it comes to implementing complex systems.
    
    But what is the difference?
    
    response to a question:
    You are perfectly right. A system is compositional exactly when you can predict things arising when you link things together.
    So yes, all compositional systems are modular, while the opposite is not true (a modular system can be non-compositional).

(9) https://simons.berkeley.edu/workshops/logic2016-3
    Compositionality, Dec. 5 – Dec. 9, 2016
    The compositional description of complex objects is a fundamental feature of the logical structure of computation.
    The use of logical languages in database theory and in algorithmic and finite model theory provides a basic level of compositionality,
    but establishing systematic relationships between compositional descriptions and complexity remains elusive.
    Compositional models of probabilistic systems and languages have been developed,
    but inferring probabilistic properties of systems in a compositional fashion is an important challenge.
    In quantum computation, the phenomenon of entanglement poses a challenge at a fundamental level to the scope of compositional descriptions.
    At the same time, compositionally has been proposed as a fundamental principle for the development of physical theories.
    This workshop will focus on the common structures and methods centered on compositionality that run through all these areas.

(10) https://en.wikipedia.org/wiki/Denotational_semantics
    Broadly speaking, denotational semantics is concerned with finding mathematical objects called domains that represent what programs do.
    For example, programs (or program phrases) might be represented by partial functions or by games between the environment and the system.
    An important tenet of denotational semantics is that semantics should be compositional:
    the denotation of a program phrase should be built out of the denotations of its subphrases.
    
    Compositionality
    An important aspect of denotational semantics of programming languages is compositionality, by which the denotation of a program is constructed from denotations of its parts.
    For example, consider the expression "7 + 4". Compositionality in this case is to provide a meaning for "7 + 4" in terms of the meanings of "7", "4" and "+".

    A basic denotational semantics in domain theory is compositional because it is given as follows.
    We start by considering program fragments, i.e. programs with free variables. A typing context assigns a type to each free variable. For instance, in the expression (x + y) might be considered in a typing context (x:nat,y:nat). We now give a denotational semantics to program fragments, using the following scheme.

    We begin by describing the meaning of the types of our language: the meaning of each type must be a domain. We write 〚τ〛 for the domain denoting the type τ. For instance, the meaning of type nat should be the domain of natural numbers: 〚nat〛= ℕ⊥.
    From the meaning of types we derive a meaning for typing contexts. We set 〚 x1:τ1,..., xn:τn〛 = 〚 τ1〛× ... ×〚τn〛. For instance, 〚x:nat,y:nat>〛= ℕ⊥×ℕ⊥. As a special case, the meaning of the empty typing context, with no variables, is the domain with one element, denoted 1.
    Finally, we must give a meaning to each program-fragment-in-typing-context. Suppose that P is a program fragment of type σ, in typing context Γ, often written Γ⊢P:σ. Then the meaning of this program-in-typing-context must be a continuous function 〚Γ⊢P:σ〛:〚Γ〛→〚σ〛. For instance, 〚⊢7:nat〛:1→ℕ⊥ is the constantly "7" function, while 〚x:nat,y:nat⊢x+y:nat〛:ℕ⊥×ℕ⊥→ℕ⊥ is the function that adds two numbers.

    Now, the meaning of the compound expression (7+4) is determined by composing the three functions 〚⊢7:nat〛:1→ℕ⊥, 〚⊢4:nat〛:1→ℕ⊥, and 〚x:nat,y:nat⊢x+y:nat〛:ℕ⊥×ℕ⊥→ℕ⊥.

    In fact, this is a general scheme for compositional denotational semantics. There is nothing specific about domains and continuous functions here. One can work with a different category instead. For example, in game semantics, the category of games has games as objects and strategies as morphisms: we can interpret types as games, and programs as strategies. For a simple language without general recursion, we can make do with the category of sets and functions. For a language with side-effects, we can work in the Kleisli category for a monad. For a language with state, we can work in a functor category. Milner has advocated modelling location and interaction by working in a category with interfaces as objects and bigraphs as morphisms.[19] 

(11) https://julesh.com/2017/04/22/on-compositionality/
    Jules Hedges, On compositionality, Posted on Apr 22, 2017 by juleshedges
    good examples, useful concepts

(12) http://www.cs.ox.ac.uk/activities/quantum/
   ) http://www.cs.ox.ac.uk/research/fls/projects.html
   ) http://www.cs.ox.ac.uk/projects/FSCM/
     Foundational Structures for Compositional Meaning, 1st October 2011 to 30th September 2016, Mehrnoosh Sadrzadeh
   ) http://www.cs.ox.ac.uk/projects/lint/
     Logic of Interaction and Information Flow, 1st October 2008 to 31st March 2012
     Our current understanding of computation has widened enormously beyond the original "closed world'' picture of numerical calculation in isolation from the environment.
     In the age of the Internet and the Web, and now of pervasive and ubiquitous computing, it has become clear that interaction and information flow between multiple agents are essential features of computation.
     The standard unit of description or design, whether at a micro-scale of procedure call-return interfaces or hardware components,
     or a macro-scale of software agents on the Web, becomes a process or agent, the essence of whose behaviour is how it interacts with its environment across some defined interface.
     These developments have required the introduction of novel mathematical models of interactive computation.
     The traditional view whereby a program is seen as computing a function or relation from inputs to outputs is no longer sufficient: what function does the Internet compute?

     One of the compelling ideas which has taken root is to conceptualize the interaction between the System and the Environment as a two-person game.
     
     Game Semantics

   ) http://www.tzevelekos.org/papers

(13) https://www.academia.edu/39952616/Using_Logic_to_Evolve_More_Logic_Composing_Logical_Operators_via_Self-Assembly
    Using Logic to Evolve More Logic: Composing Logical Operators via Self-Assembly, 2019, Travis LaCroix
    Department of Logic and Philosophy of Science, University of California, Irvine
    
    Abstract.
    I consider how complex logical operations might self-assemble in a
    signalling-game context via composition of simpler underlying dispositions. On
    the one hand, agents may take advantage of pre-evolved dispositions; on the
    other hand, they may co-evolve dispositions as they simultaneously learn to
    combine them to display more complex behaviour. In either case, the evolution
    of complex logical operations can be more efficient than evolving such capac-
    ities from scratch. Showing how complex phenomena like these might evolve
    provides an additional path to the possibility of evolving more or less rich no-
    tions of compositionality. This helps provide another facet of the evolutionary
    story of how sufficiently rich, human-level cognitive or linguistic capacities may
    arise from simpler precursors.
    
    The signalling game, presented in a classical context in Lewis (1969) and an evolutionary context in Skyrms (1996, 2010), has been well-studied.
    The basic sender-receiver model has been extended to shed light on a variety of philosophically interesting phenomena that arise in communicative contexts.
    Barrett and Skyrms(2017) ask how such games might evolve in the first place. In some cases, actors may interact in such ways that can usefully be characterised as a game.
    This is thefocus of their notion of self-assembly. Under this description, individuals with prior strategies for solving decision problems may come to interact.
    These interactionsthen compose to form games.
    Once such simple games have arisen, they may themselves compose to form more complex games—
    ones that are, perhaps, able to deal with novel phenomena more efficiently than learning a new disposition from scratch.
    This may happen in a variety of plausible ways—via ritualisation, template transfer, analogical reasoning, or modular composition.
    Thus, self-assembly concerns howgames and the dispositions that they implement might evolve together.

(14) https://uci.academia.edu/tlacroix
    Travis LaCroix
    University of California, Irvine, Logic and Philosophy of Science, Graduate Student
    I’m a Ph.D candidate in the department of Logic and Philosophy of Science at the University of California, Irvine, supervised by Jeffrey A. Barrett. I am currently a visiting researcher at Mila—the Québec Artificial Intelligence Institute—associated with Université de Montréal, supervised by Yoshua Bengio. I previously received an MA in Social Science from the Institute for Mathematical Behavioral Sciences at UC Irvine, as well as an MA in Philosophy from Simon Fraser University and a BA in Philosophy (hons.) and English Literature from the University of British Columbia. My primary research interests concern the evolution of social-dynamical phenomena in general—specifically the evolution of linguistic phenomena, including communication, meaning, and compositionality.
    Supervisors: Jeffrey A. Barrett (PhD), Nic Fillion (MA), John Woods (BA), and Yoshua Bengio
    Address: Montréal, Québec, Canada

(15) https://travislacroix.github.io/research/
   ) https://travislacroix.github.io/files/ND-Dissertation-Summary.pdf

(16) https://rosieresearch.com/self-assembling-bricks/

(17) http://openaccess.thecvf.com/content_cvpr_2017/papers/Stone_Teaching_Compositionality_to_CVPR_2017_paper.pdf

(18) https://tikzit.github.io/
    TikZiT is a super simple GUI editor for graphs and string diagrams.
    Its native file format is a subset of PGF/TikZ, which means TikZiT files can be included directly in papers typeset using LaTeX.
    Pre-built versions are available for systems running Windows, Linux, or macOS.
    TikZiT is an open source project licensed under the GNU General Public License, Version 3.
    It is maintained primarily by Aleks Kissinger, with contributions (notably the TikZ parser) from Alexander Merry, Chris Heunen, and K. Johan Paulsson.

(19) https://github.com/appliedcategorytheory/TikZWD
    A TikZ library of wiring diagrams
    Brendan Fong
    This is the standard package of TikZ wiring diagrams we use at MIT, mostly written by David Spivak and Patrick Schultz.
    Please feel free to use and reshape, and please contribute edits of your own. We hope one day this might turn into a proper package!

(20) https://web.stanford.edu/~cgpotts/manuscripts/liang-potts-semantics.pdf
    Bringing machine learning and compositional semantics together, Percy Liang and Christopher Potts
   ) https://web.stanford.edu/class/cs224u/materials/cs224u-compsemlearn-concepts.pdf
    Compositionality
    The meaning of a phrase is a function of the meanings of its immediate syntactic constituents and the way they are combined.

(21) https://www.calstatela.edu/sites/default/files/groups/Department%20of%20Philosophy/phenomenal_compositionality.pdf
    And we would have a useful kind ofcompositionality after all:
    the content of a complex concept (or term) or a thought (or sentence) is a function of
     * the contents of its constituent concepts,
     * their structural arrangement, and
     * the relevant features of the experiential context in which it occurs.
    KSW: thus, the context/environment is also of crucial importance

(22) https://www.iep.utm.edu/composit/
    Compositionality in Language
    Compositionality is a concept in the philosophy of language.
    A symbolic system is compositional if the meaning of every complex expression E in that system depends on, and depends only on,
     (i) E’s syntactic structure and
     (ii) the meanings of E’s simple parts.
    If a language is compositional, then the meaning of a sentence S in that language cannot depend directly on the context that
    sentence is used in or the intentions of the speaker who uses it.
    So, for example, in compositional languages, the meanings of sentences don’t directly depend on
     * Things said earlier in the conversation
     * The beliefs or intentions of the person uttering S
     * Salient objects and events in the environment at the time that S is uttered
     * The non-semantic character of S’s simple parts, such as their shape or sound
    In compositional languages, the meaning of a sentence S directly depends only on the meanings of the words composing S,
    and the way those words are syntactically related to one another.

(23) http://math.ucr.edu/home/baez/networks_compositionality/networks_compositionality.pdf
    

]]></Notes> 

<params>
  <param name="allowAdHocGlobalClasses" value="true"/>
</params>

<_-.XholonClass>

  <!-- domain objects -->
  <PhysicalSystem/>
  <Block/>
  <Brick/>
  
  <!-- quantities -->
  <Height superClass="Quantity"/>
  
  <One/>
  <Two/>
  
</_-.XholonClass>

<xholonClassDetails>
  <Block>
    <port name="height" connector="Height"/>
  </Block>
</xholonClassDetails>

<PhysicalSystem>
  <Block>
    <Height>0.1 m</Height>
  </Block>
  <Brick multiplicity="2"/>
  
  <One/>
  <Two/>
  <Three/>
  
</PhysicalSystem>

<Blockbehavior implName="org.primordion.xholon.base.Behavior_gwtjs"><![CDATA[
  var a = 123;
  var b = 456;
  var c = a * b;
  if (console) {
    console.log(c);
  }
  //# sourceURL=Blockbehavior.js
]]></Blockbehavior>

<Heightbehavior implName="org.primordion.xholon.base.Behavior_gwtjs"><![CDATA[
  var myHeight, testing;
  var beh = {
    postConfigure: function() {
      testing = Math.floor(Math.random() * 10);
      myHeight = this.cnode.parent();
    },
    act: function() {
      myHeight.println(this.toString());
    },
    toString: function() {
      return "testing:" + testing;
    }
  }
  //# sourceURL=Heightbehavior.js
]]></Heightbehavior>

<Brickbehavior implName="org.primordion.xholon.base.Behavior_gwtjs"><![CDATA[
  $wnd.xh.Brickbehavior = function Brickbehavior() {}

  $wnd.xh.Brickbehavior.prototype.postConfigure = function() {
    this.brick = this.cnode.parent();
    this.iam = " red brick";
  };

  $wnd.xh.Brickbehavior.prototype.act = function() {
    this.brick.println("I am a" + this.iam);
  };
  //# sourceURL=Brickbehavior.js
]]></Brickbehavior>

<Brickbehavior implName="org.primordion.xholon.base.Behavior_gwtjs"><![CDATA[
  console.log("I'm another brick behavior");
]]></Brickbehavior>

<SvgClient><Attribute_String roleName="svgUri"><![CDATA[data:image/svg+xml,
<svg width="100" height="50" xmlns="http://www.w3.org/2000/svg">
  <g>
    <title>Block</title>
    <rect id="PhysicalSystem/Block" fill="#98FB98" height="50" width="50" x="25" y="0"/>
    <g>
      <title>Height</title>
      <rect id="PhysicalSystem/Block/Height" fill="#6AB06A" height="50" width="10" x="80" y="0"/>
    </g>
  </g>
</svg>
]]></Attribute_String><Attribute_String roleName="setup">${MODELNAME_DEFAULT},${SVGURI_DEFAULT}</Attribute_String></SvgClient>

</XholonWorkbook>