Today's large-scale computations, e.g., in the Cloud, are subjectto a multitude of risks concerning the divulging and ownership ofprivate data. Privacy risks are mainly addressed using a largevariety of encryption-based techniques. However, these are costlyto operate, lead to large aggregates of data that are highlyvaluable attack targets and do not allow to flexibly handlesubsets of such aggregates. Furthermore, today's computations haveto ensure privacy properties in the context over highly variableand complex software compositions; however, no general support forthe declarative definition and implementation ofprivacy-preserving applications has been put forward.In this article, we present a compositional approach to thedeclarative and correct composition of privacy-preservingapplications in the Cloud. Our approach provides language supportfor the compositional definition of encryption- andfragmentation-based privacy-preserving algorithms. This languagecomes equipped with a set of laws that allows us to verify privacyproperties. Finally, we introduce implementation support in Scalathat ensures certain privacy properties by construction usingadvanced features of Scala's type system.