Let's say I have a programming language that allows procedures, i.e., methods without return values, and immutable data-structures, so no sideeffecting inside a procedure. Is it possible to simulate a program written in a language with return values in our language?

In other words, do return values allow for a more advanced model of computation? I guess it may be possible with Continuation-passing style, but i would appreciate other thoughts on this.

  • 3
    $\begingroup$ This question is underspecified. It does not take much to make a language Turing-complete, but it's not clear what exactly you allow. In particular, we 1) only ever really need one procedure (using more is just for readability) and 2) we don't need data structures at all, (mutable) registers with numbers are sufficient. Please describe more specifically what your language can and can not do, and give a non-trivial example of a program. $\endgroup$ – Raphael Jul 15 '15 at 5:46
  • $\begingroup$ Methods for classes with immutable structure can still have side-effect, since they may normally access global variables. Also can they take parameters passed by reference or by name. What is mutable, and when, in your language? If all you have is procedure calls that have no side-effect of any kind and return nothing, I suspect that your language is block-of-wood complete, meaning it will compute exactly as much as a block of wood. $\endgroup$ – babou Jul 15 '15 at 9:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.