5

I believe there are languages where all names with associated values cannot have their associated values changed. An example would be a language where all names behave like a does in the following C code:

int main(void)
{
  const int a = 0;
  a = 1;
}

i.e., all names act like what C calls a "read-only variable" here.

I know that certain constructs, like C's for loop, wouldn't be possible if one could not reassign variables. But I believe that languages where variables are exclusively read-only will use tail-recursive functions to accomplish looping.

If a language does not permit assigning new values to variables, what features (like tail recursion, in the above example) are needed to allow for programs to be written, that would otherwise be difficult / impossible to write without reassignment?

Jackson
  • 412
  • 3
  • 6
  • Can you give an example of such a language? – TZHX Sep 18 '16 at 18:38
  • 11
    Are you maybe asking about immutability in the context of functional programming? – MetaFight Sep 18 '16 at 18:52
  • @MetaFight Assuming that my "for instance" example were true (I don't know), I wondered, "More generally, does a 'constants only' rule impose other requirements on language features?" (So, I don't think it *just* has to do with functionalism.) – Jackson Sep 18 '16 at 19:41
  • Unless universal constants can only be accomplished in a functional language. But I don't know that, either. – Jackson Sep 18 '16 at 19:49
  • @TZHX Emphasis on "believe." I don't actually know if such a language exists or not, but with the breadth of options, I assumed there was at least one. I thought this was the case with Haskell, but it seems Haskell does have "explicitly-enabled mutable cells." I also assumed that even if there wasn't one, my question could still be answered in the abstract. – Jackson Sep 18 '16 at 20:00
  • Erlang does not allow variables to have their values changed after creation. Recursion is used instead of loops, and a services allow shared and updatable state between threads – Michael Shaw Sep 18 '16 at 23:53
  • 2
    XSLT is a language of that type where all variables are *immutable*. See [this SO post](http://stackoverflow.com/questions/3344965/increment-a-value-in-xslt) for an example how to write a loop without recursion. – Doc Brown Sep 19 '16 at 06:22
  • 1
    Are these constants only assigned values during compile time? – JeffO Sep 19 '16 at 17:09
  • Using the term "constant" seemed to cause confusion. I was speaking of `const`-like functionality. I've updated the question to reflect that. – Jackson Sep 19 '16 at 22:34
  • Does reference counting count as immutability? Also, do you count objects that can only be initiated with their constructor and after that can't be changed? – Pieter B Sep 20 '16 at 10:41

1 Answers1

7

With only constants, and without any variables, all your programs would be totally predictable and -- through constant propagation -- could be simply rewritten producing directly the expected output.

How would you manage user input in such a world ? How would you define even simple arithmetic functions, like f(x)=x^2 without precalculating and embedding in your program an infinity of combinations ?

However, there are several functional languages around. In these you have constants as in any language. But also variables/parameters, which can take a value (e.g. function parameter, user input), but can't be changed thereafter. We then don't talk about constants but about immutable variables.

In this functional approach you can write programs having the full expressiveness of a turing machine. The code is easier to analyze in terms of value propagation, as each function is stateless (i.e. it depends only on the function's input). And you don't have to cope with side effects on global or local variables. Keep in mind however that such functional language (e.g. Caml, or F#) are not yet mainstream.

Christophe
  • 74,672
  • 10
  • 115
  • 187
  • 3
    It's not unheard of for functional programmers to refer to immutable variables as constants, in fact, in my reading, it's fairly common. – RubberDuck Sep 18 '16 at 20:43
  • 1
    @RubberDuck yes. And they are not the only ones, as some mainstream languages use a const qualifier for variables passed by reference to express that they should not be muted – Christophe Sep 18 '16 at 21:07
  • Thanks for pointing that out @RubberDuck. The "constants" I was referring to in my question actually were "immutable variables." – Jackson Sep 18 '16 at 21:26
  • I'm not sure this is strictly true. Surely I can write a recursive chaotic function using only constants which will unpredicably halt say when it runs out of memory – Ewan Sep 19 '16 at 18:43
  • @Ewan i agree that it's possible to get unpredictable result if using constants to trigger undefined behavior (e.g. Null pointer dereferencing in c or c++). But it is predictably unpredictable, and it's known upfront that it's surprise assured. Nevertheless, i think that OP had in mind to achieve some useful algorithm. i propose you to answer in a separate answer and show the code for further debate on this specific aspect. – Christophe Sep 19 '16 at 18:51
  • I would, but im not sure i really understand what the question is. – Ewan Sep 19 '16 at 21:20
  • @Christophe You claim, "In this functional approach you can write programs having the full expressiveness of a turing machine." In posing this question, I hoped to find out *why* that was true: "What components of a language with only immutable variables make it a turing machine?" Is it possible for you to explain that in a single SO answer? Or have you already? – Jackson Sep 19 '16 at 22:40
  • 2
    @Jackson functional programming is based on lambda calculus and it was proven that lambda calculus is Turing complete: http://cstheory.stackexchange.com/questions/625/relationship-between-turing-machine-and-lambda-calculus . To show it intuitively: instead of loops using counters an reusing variables, you'd use recursive functions only binding new values to parameter instantiations. Every step is a function applied to the result of the previous steps, and so on until the first step – Christophe Sep 20 '16 at 05:55