Human languages share a number of universal architectural features, from atomic meaning properties (e.g., connectedness, Gärdenfors, 2000) to how these meanings combine to generate more complex senses (i.e., compositionality). In this talk, I will present the first results of a new research program investigating experimentally the cognitive origins of these shared features of language in non-human primates to determine whether these features reflect properties of the language faculty or rather domain-general forces potentially shared across cognitive systems and species. I will report three studies suggesting that baboons (Papio papio) (i) like to manipulate 'concepts' of the same shape as ours, (ii) can respond to negation-like operators <t,t>, (iii) report responses in a "compositional" manner.