3 ms·

You've just defined “pure” as “can be given a denotational semantics”. I have news for you: even ALGOL can be given a denotational semantics. --- @pron Nowad

You've just defined “pure” as “can be given a denotational semantics”. I have news for you: even ALGOL can be given a denotational semantics. --- @pron Nowadays I prefer the terms “effect-free” and “effectful”, rather than “pure” and “impure”, since I don't want to suggest that effects are somehow “wrong” or “evil”. By definition, values are effect-free. An effect is anything that invalidates some equational law that holds for values. For example, integer equality is decidable, and `x == x` evaluates to `true` when `x` is any integer value. However, if we substitute `x` with the expression `foo()`, where: int counter = 0; // or any other initial value int foo() { return counter++; } Then `foo() == foo()` doesn't evaluate to `true` anymore. Hence `foo` is an effectful procedure. Of course, nontermination is an effect too. If we had defined `foo` as: int foo() { while(true); return 0; } Then `foo() == foo()` would similarly fail to evaluate to `true`.

pron 10y ago
Yeah, I know my definitions are problematic. Remember that the term "referential transparency" was introduced to computer science by Strachey in his Fundamental Concepts in Programming Languages as a property of procedural, imperative languages. How would you define pure? --- > An effect is anything that invalidates some equational law that holds for values. Ah, I can certainly accept that as a definition, except that I'm not sure how different it is from mine, because the equational law you refer to applies to syntactic terms (`foo` in your example) and the language's equality operator (`==` in your example). It's easy to come with an equivalence relation that would hold for `foo`, but not at the syntax level (e.g., equality that takes `foo` to mean `foo`'s definition and the content of the heap, and the value of `foo` would not be its return value but its behavior -- i.e., the behavior of foo for equal heap contents is always the same).
- catnaroek 10y ago
  > except that I'm not sure how different it is from mine, because the equational law you refer to applies to syntactic terms An effectful language can be given a denotational semantics. At least from what I've seen, when most people say “pure”, they mean “effect-free”. > It's easy to come with an equivalence relation that would hold for `foo`, but not at the syntax level [emphasis mine] Yep, indeed, that's the whole point.
  - pron 10y ago
    > when most people say “pure”, they mean “effect-free” But saying "effect free" doesn't mean much unless you define what an effect is, and what constitutes an effect depends on the language. I meant to define the same thing without referring to another vague definition.
    - catnaroek 10y ago
      I already defined above what an effect is. My definicion is technically precise and language-independent.
      - pron 10y ago
        OK, so you define effect-freedom using the language's equality operator. I agree it's a better definition than mine, but I think assembly language and BASIC would still qualify as effect-free (provided there's no concurrency) even though some people would not consider them pure.
        catnaroek 10y ago
        > OK, so you define effect-freedom using the language's equality operator. Not the runtime equality testing operator. Rather, the language's static notion of contextual equivalence. It just happens to be the case that most high-level languages provide a built-in equality testing operator that works on primitive types, returning `true` iff its operands are contextually equivalent values. > I think assembly language and BASIC would still qualify as effect-free I don't even know what a good notion of contextual equivalence for any assembly language would be. As for BASIC, I haven't used the old ones, so I can't comment on them. I've used Visual Basic, which most certainly has effectful procedures.
        pron 10y ago
        > Not the runtime equality testing operator. Rather, the language's static notion of contextual equivalence. How is that different from denotational semantics? > The ones that can be effectful or effect-free are specific computations, not whole languages. Well, we could define an effect-free language as one where all programs are effect-free. But anyway, what is the "static notion of contextual equivalence" in assembly (or BASIC), and how can you write an effectful program in such a language?

pron 10y ago

Yeah, I know my definitions are problematic. Remember that the term "referential transparency" was introduced to computer science by Strachey in his Fundamental Concepts in Programming Languages as a property of procedural, imperative languages. How would you define pure? --- > An effect is anything that invalidates some equational law that holds for values. Ah, I can certainly accept that as a definition, except that I'm not sure how different it is from mine, because the equational law you refer to applies to syntactic terms (`foo` in your example) and the language's equality operator (`==` in your example). It's easy to come with an equivalence relation that would hold for `foo`, but not at the syntax level (e.g., equality that takes `foo` to mean `foo`'s definition and the content of the heap, and the value of `foo` would not be its return value but its behavior -- i.e., the behavior of foo for equal heap contents is always the same).

catnaroek 10y ago
> except that I'm not sure how different it is from mine, because the equational law you refer to applies to syntactic terms An effectful language can be given a denotational semantics. At least from what I've seen, when most people say “pure”, they mean “effect-free”. > It's easy to come with an equivalence relation that would hold for `foo`, but not at the syntax level [emphasis mine] Yep, indeed, that's the whole point.
- pron 10y ago
  > when most people say “pure”, they mean “effect-free” But saying "effect free" doesn't mean much unless you define what an effect is, and what constitutes an effect depends on the language. I meant to define the same thing without referring to another vague definition.
  - catnaroek 10y ago
    I already defined above what an effect is. My definicion is technically precise and language-independent.
    - pron 10y ago
      OK, so you define effect-freedom using the language's equality operator. I agree it's a better definition than mine, but I think assembly language and BASIC would still qualify as effect-free (provided there's no concurrency) even though some people would not consider them pure.
      - catnaroek 10y ago
        > OK, so you define effect-freedom using the language's equality operator. Not the runtime equality testing operator. Rather, the language's static notion of contextual equivalence. It just happens to be the case that most high-level languages provide a built-in equality testing operator that works on primitive types, returning `true` iff its operands are contextually equivalent values. > I think assembly language and BASIC would still qualify as effect-free I don't even know what a good notion of contextual equivalence for any assembly language would be. As for BASIC, I haven't used the old ones, so I can't comment on them. I've used Visual Basic, which most certainly has effectful procedures.
        pron 10y ago
        > Not the runtime equality testing operator. Rather, the language's static notion of contextual equivalence. How is that different from denotational semantics? > The ones that can be effectful or effect-free are specific computations, not whole languages. Well, we could define an effect-free language as one where all programs are effect-free. But anyway, what is the "static notion of contextual equivalence" in assembly (or BASIC), and how can you write an effectful program in such a language?