This paper concerns the theory of partial maps under composition and more generally, the RCsemigroups introduced by Jackson and Stokes [Semigroup Forum 62 (2001) 279-310] (semigroups with a unary operation called (right) closure). Many of the motivating examples have a natural meetsemilattice structure; the inverse semigroup of all injective partial transformations of a set and the semigroup of all binary operations under composition are two examples. We here view the semilattice meet as an additional operation, thereby obtaining a variety of algebras with one unary and two binary operations. The two non-semigroup operations are then shown to be captured by a single binary operation, via the notion of an agreeable semigroup. We look at a number of properties of these structures including their congruences (which are uniquely determined by their restriction to certain idempotents), a relationship with so-called interior semigroups, and a natural category associated with a large variety of RC-semigroups (which includes all inverse semigroups). For example, we show that the existence of equalisers in this category is intimately connected with the existence of the natural meet-semilattice structure.