This article studies sums over all compositions of an integer. We derive a generating function for this quantity, and apply it to several special functions, including various generalized Bernoulli numbers. We connect composition sums with a recursive tree introduced by Woon and extended by Fuchs under the name general PI tree, in which an output sequence is associated with an input sequence by summing over each row of the tree built from this input sequence. Our link with the notion of compositions allows to introduce a modification of Fuchs' tree that takes into account nonlinear transforms of the generating function of the input sequence. We also introduce the notion of generalized sums over compositions, where we look at composition sums over each part of a composition.