Objects do have state, but they can be either mutable or immutable. The link in my original comment describes an immutable stack (written in OCaml, but is fairly readable) where both push and pop returns a new stack object. The original object is never changed. In a mutable stack, push would return void (or unit in OCaml), which signifies a side-effect. pop would return the element, and the object changes in-place.