Our main result is a doubly exponential decision procedure for the first-order equality theory of streams with both arithmetic and control-oriented stream operations. This stream logic is shown to be expressive for solving basic problems of stream calculus.