ABSTRACT Creating and managing large-scale software remains a task which requires many levels of expertise, well defined processes, adherence to standards, and careful documentation. Even when all these pre-requisites are in place, overruns and failures are common. We support an alternate paradigm to conventional concepts of software creation: composition. We have seen composition already being used in practice for a long time, but typically in an ad-hoc fashion by experienced personnel. Composition is becoming more common, as large-scale services, as databases, mathematical modeling tools, and web-browsers are combined to rapidly create substantial, but hard to maintain and often short-lived systems. However, tools to support this shift are minimal and fragmented. To address this issue the CHAIMS project is developing an approach based on a very-high level programming language (CLAM) for software service composition. This language supports the concept of megaprogramming, that is programming by composition of remote services, typically provided by autonomous suppliers. Its compiler is starting to generate a variety of invocation sequences for current and developing standards for software interoperation, as CORBA and JAVA RMI. CHAIMS is intended for building applications using large services, which we refer to as services. The size of service we envision typically justifies a dedicated processor, although services can share a single processor when performance demands permit. A repository links suppliers of services and composers of applications, giving details of location, protocols, and data-types. In this paper we focus on the composition of heterogeneous services.