How is it that referential transparency (the ability to swap a reference with it's value: no hidden inputs) and homoiconicity (both the source and the resulting syntax tree sharing the same structure) are mutually exclusive?

What homoiconicity offers is the macro system, the ability to operate on the syntax tree as a regular language data structure.

The difference is a language like Haskell enforces referential transparency where in a lisp it is up to the developer whether or not a function will be referentially transparent.

"How is it that referential transparency..."

That was incorrect, I meant: "the kinds of metaprogramming associated with homoiconicity are mutually exclusive with referential transparency".

A macro could not, for instance, take a variable name as an argument and return a result that's based on the value of that variable and maintain referential transparency. So that would be a pretty weak macro system.

I suppose there may be other uses for homoiconicity, but I don't know enough about lisp to comment on that.

Maybe I don't understand referential transparency, but why not? `or` is a macro in Clojure:

(def a 10) (def b 20) (or a b) => 20

Is `or` not referentially transparent?

(please excuse my poor knowledge of lisp... check out the wikipedia page if my explanation falls apart: http://en.wikipedia.org/wiki/Referential_transparency_%28com...)

My clojure interpreter gives "10" not "20".

The function "or" is referentially transparent, because if you call it with the same argument values you are going to get the same result every time. (or 10 20) is the same as 10.

However, the following function is not referentially transparent:

  (defn incx [] (do (def x (+ x 1)) x))

Because subsequent calls return different results:

  (def x 2)
  (incx)
  (incx)

Things like side effects and many kinds of metaprogramming break referential transparency.

It seems to me that what you've demonstrated is that side effects are possible in Clojure, esp. with sufficiently obfuscated (read: un-idiomatic) code. But you're working too hard anyway; Clojure explicitly admits mutability already, through various concurrency pieces like atoms and refs.

That said, if any admission of mutability is sufficient to disqualify a language from claiming to encourage or support referential transparency, then Haskell fails the test, too. unsafePerformIO is a trivial example. I'm sure if you were determined to introduce nondeterminism, you could find a lot more. But that's not the point, is it?

Maybe there's a way to demonstrate your point, but what you've shown here doesn't involve homoiconicity or macros at all.

I should have known that my poor knowledge of lisp would not be excused on HN ;-)

Anyway, I tried learning enough clojure to prove that routine metaprogramming would often be not referentially transparent.

First, note from the wikipedia page that "referentially transparent" essentially means that the same function with the same arguments will always produce the same result, and that you can call it more (throwing away the result) or fewer (replacing calls with the result) times without affecting the meaning of the program.

So, mutating variables (assignment) violates it, as does reading mutable variables other than the arguments. So, using "def" on a variable that already has a value is not referentially transparent.

But let me show you something closer to what I had in mind when I said that referential tranparency and metaprogramming are essentially inconsistent.

Take the simple macro:

  (defmacro swapargs [x] 
    (list (nth x 0) (nth x 2) (nth x 1)))

First, I'll show that the argument that it takes must be the code itself, rather than the result of evaluating the code. The "or" macro before made it hard to tell whether it was taking the code as arguments or the result of evaluating the code as arguments. But with the macro above, it's easy to see:

  (swapargs (mod 7 5)) => 5
  (swapargs (mod 10 8)) => 8

If we are trying to show that swapargs is referentially transparent, we assume that it will return the same result given the same arguments. Because (mod 7 5) = (mod 10 8), then we know it must not be taking the result as an argument (because the result of the mod is 2 in both cases, but the result of swapargs is different). So it's taking the code itself.

Next, we show that give the same code-as-an-argument, it may return different results in different contexts. That's easy to show:

  (defn foo [a b] (swapargs (mod a b)))
  (foo 7 5)
  (foo 10 8)

Now, we can't replace the call to swapargs with its result, because it changes depending on the values of "a" and "b" at the time, even though the argument is always the same code "(mod a b)".

So, this kind of advanced metaprogramming doesn't seem compatible with referential transparency. Perhaps some subsets are, but I don't even think the C macro system could be supported in a referentially-transparent way.

I also think that kind of metaprogramming tends to defeat many kinds of static analysis, such as advanced type systems. I'm less sure of that one, but for practical purposes now it seems to be true.

So, I think lisp and haskell are close to local maximums for their particular philosophies, but neither one is any kind of epitome of programming or "more powerful" than the other.

Personally, I think lisp-style metaprogramming is very cool, and I am happy I spent a few minutes trying out clojure. However, I don't think it is solving a problem that is very important to me at a practical level. I am trying to learn haskell because it is trying to solve the kinds of problems that I actually have -- mainly software engineering problems (greater confidence in code, more readability and maintainability). Not sure whether it will help solve those problems for me, but they are trying very hard to do so, and make some pretty compelling arguments.

As presented, the example macro doesn't demonstrate referential transparency, but then again, the example appears to be incorrect.

The issue is invoking "(swapargs (mod 7 5))". I tried this in the Scheme REPL (Chicken to be precise), in which the macro was defined:

  (define-syntax swapargs
    (syntax-rules ()
      ((_ ls) (list (list-ref ls 0) (list-ref ls 2)
                    (list-ref ls 1)))))

  (swapargs '(a b c)) => (a c b)
  (swapargs (swapargs '(a b c))) => (a b c)

In other words, the macro does show referential transparency.

However, the following doesn't work:

  (swapargs (modulo 7 5)) => Error: (list-tail) bad   
                             argument type: 2

The problem is the argument is evaluated first, and "2" is not a list. (The macro requires a list-of-3 argument.)

  (modulo 7 5) => 2

Probably, what was intended was like this:

  (swapargs '(module 7 5)) => (modulo 5 7)

And again:

  (swapargs (swapargs '(module 7 5))) => (module 7 5)
  (eval (swapargs '(module 7 5))) => 5
  (eval (swapargs (swapargs '(module 7 5)))) => 2
  (eval (swapargs (swapargs '(module 10 8)))) => 2

It looks like confusion between literal and evaluable lists prompted the wrong conclusion, but in this case it's simple to rectify.

Of course, macros in Scheme/Lisp can easily become convoluted and bug-ridden as much as any code, even aside from arguments about the virtues of "hygienic" vs. "unhygienic" systems. Properly constructed, macros remain an essential feature of Lisp/Scheme languages.

BTW, if we're comparing qualities of programming languages, here's a real-life example showing the particular merit of Scheme. I took on the task of creating a complex application (a web server supporting multiple hosts) and decided to write it primarily in Scheme (and some C). The first version was up and running in less than half a year.

Inevitably, months after the project was deployed changes were necessary. Despite the length of time since last seen, the code wasn't obscure to me, it was easy to understand and pick up where I'd left off before. Definitely different from prior experiences.

The crux is getting a good grasp on its core, macrology perhaps among the harder parts. But understood, Scheme allows enhanced productivity, as I've known it more so than other languages "under load" in parallel situations.

Thank you for the detailed reply.

When you say my example is incorrect, do you mean that it's incorrect in clojure, or only in scheme? I tried my examples in clojure and they appear to work and appear to demonstrate a lack of referential transparency. I assume that clojure is a valid lisp to make a point about metaprogramming and macros.

Also, it looks like it's fairly easy in scheme to show the same thing, which it looks like you started to do (I'm not sure whether you agree with me about that or not):

  (define-syntax swapargs
    (syntax-rules ()
      ((_ ls) (list (list-ref ls 0) (list-ref ls 2)
                    (list-ref ls 1)))))
  
  (define a 7)
  (define b 5)
  (eval (swapargs '(modulo a b))) => 5
  (define a 10)
  (define b 8)
  (eval (swapargs '(modulo a b))) => 8

The two calls to "eval" are identical, yet return different results. That breaks referential transparency.

"showing the particular merit of Scheme"

From what I know, I like lisps of various flavors. I just said that they didn't really speak to the kinds of problems that I deal with. Maybe if I wrote more lisp I would see why it does so, but currently I do not.

  > The two calls to "eval" are identical, yet return
  > different results. That breaks referential transparency.

You are right, I don't know much about the syntax of clojure, but the Scheme version works as I'd expect. Yes, the eval calls return different results, but then again, we'd expect to compute a different output for different inputs.

What I tried to show is that calling (swapargs (swapargs '(a b c))) will always return the original list, that is, demonstrates referential transparency. In the case of '(modulo a b), result of evaluation returns a the same result when repeatedly given the same a, b inputs.

The point of the macro was exchanging the second and third elements of the input list. Naturally for the modulo operation, the order of the inputs is significant, and exchanging the operands will give the "opposite" remainder as the result.

In your example the two calls to (eval ...) are not identical and the "different results" are perfectly correct, without implications for referential transparency.

Don't know what kind of applications you might have in mind, but of course, no PL is optimum in all domains. For the kinds of programs I've tackled, Lisp/Scheme has been a good fit. Or maybe it has to do with the way my brain works just as much as the purposes I am applying the language to. That wouldn't surprise me a bit.

I admit I didn't have enough time to try your code, so excuse me if I made some oversight, but it seems to me that the basic oversight that you made is that there are two steps that clojure compiler does with the code. In the first step, all macros are expanded, replacing all macro calls with the actual code they generate. Then, the resulting, "macro-free" code is compiled to bytecode. So, you can try macro calls as many times as you want: all calls with the same arguments (which are clojure forms, that is - code, and not the actual values of that code in the runtime) result in exactly the same code. 5s 8s and all the data from your example does not exist yet in that moment. Then, the transparency of functional calls is as advertised: it is referentially transparent if your code is pure (no Java calls etc.). I think the misunderstanding was in forgetting that macros are expanded and gone long before your code starts to run...

I am more interested in what the human sees than the compiler. And to a human, it does not look referentially transparent.

OK, I'll try to be more precise this time, so I hope that you reconsider at least a few things:

First, I think that the main misunderstanding is, as you mentioned, your somewhat incomplete experience of Clojure.

Second, perhaps there is a tiny bit of a strawman fallacy in your argument. Why? Well, def is not for defining "variables". It does get mentioned many times in Clojure literature: these are vars, you can change them, but they are NOT there for the regular data, but to enable you to give names to your functions and the rest of clojure artefacts. The programmer does not need to use metaprogramming or macros to shoot himself in the foot using vars as "variables". How does that relate to the wikipedia definition of referential transparency? Well, only PURE functions are referentially transparent. Def is not pure, and it is not even a function - it is a special form. Of course, it could be confusing for a novice, but it has been clearly stated many times in the literature how and why, so to anyone ho has learned the basics well and is not trying to recreate Java/python/Ruby/C coding style in Clojure, that should not be a source of problems.

As for your macro example, the first part of your argument, "First, I'll show that the argument that it takes must be the code itself, rather than the result of evaluating the code" - that is something macros are for, so the programmer expects exactly what you described, although you did not need a macro for swapping arguments in a function call.

I hope that we agree that, if we know that there are two phases in Cloure compilation process, a "macro" phase and a "regular code" phase, then everything is fine and clear. I understand that your complaint is that the programmer might forget that so she might be confused in the examples that you stated, so I will continue with that assumption in mind.

Let's try referential transparency with the function foo:

1) Is the function foo referentially transparent?

user=> (defn foo [a b] (swapargs (mod a b))) #'user/foo

user=> (foo 7 5)

5

user=> (foo 10 8)

8

user=> (foo 10 8)

8

user=> (foo 10 8)

8

user=> (foo 7 5)

5

As we can see, "the same function (foo) with the same arguments will always produce the same result, and that you can call it more (throwing away the result) or fewer (replacing calls with the result) times without affecting the meaning of the program".

2) Is swapargs macro referentially transparent?

user=> (swapargs (mod 7 5))

5

user=> (swapargs (mod 7 5))

5

user=> (swapargs (mod 7 5))

5

user=> (swapargs (mod 10 8))

8

user=> (swapargs (mod 10 8))

8

Is "the same function (swapargs) with the same arguments will always produce the same result, and that you can call it more (throwing away the result) or fewer (replacing calls with the result) times without affecting the meaning of the program"? Well, is swapargs a function? -No, but let's forget that for a sake of being fair. The proper way to resolve this is to read the documentation of swapargs. And the documentation would say that the argument to swapargs is a clojure form (something like (mod 7 5)), not a number (something like the result of calling (mod 7 5)). If we having that in mind, it is clear that swapargs is also referentially transparent, with regards to its argumens. We CAN replace swapargs with its result, s you can see in the aforementioned code. If we want our argument so be the results of (mod 7 5) we would use a function, not a macro!

With the rest of your post, I agree. Macros are not superpowerful, you can shoot yourself in the foot with them (and every lisp book warns you about that in many ways), and haskell is awasome in many ways. There could be many pitfals with clojure and macros, but I think these pitfalls are not of the kind that your examples show :)

OK, I agree now, thank you for the detailed explanation.

To summarize, you are saying that in my example, the programmer would almost certainly notice that it's a macro; at which point he would know to look at the documentation and it would still look like a referentially-transparent macro.

"lisp it is up to the developer whether or not a function will be referentially transparent"

Although that may compromise the ability of the compiler to detect mistakes even when the developer writes all referentially-transparent functions. Not sure about that, but I suspect that it does in practice (currently) even if not theoretically inherent.

> Those are mutually exclusive, so one language can't really have both.

There are Lisp computer algebra systems like Maxima and Axiom that can be used for advanced term rewriting operations. Referential transparency, which is replacing terms with their definition, is just a very simple term rewriting operation.

> If you think that homoiconicity is good, then you probably like lisp. If you think that referential transparency is good, then you probably like haskell. Those are mutually exclusive, so one language can't really have both.

This mutual exclusivity is a strange claim that I have never encountered before (but I'm not a computer scientist). Could you explain it?

I gave some more technical details in another reply. It's one of those things I thought for a long time, and I didn't think was very controversial, but I suppose it is.

Really, what I meant was the metaprogramming associated with homoiconicity can't be done in a useful and referentially transparent way. That's because "eval"-like things are not referentially transparent.

However, there are other uses for homoiconicity aside from executing the code in an eval-like way. For instance, a text editor might use that property to inspect and transform the code being edited more easily. Also, I'm sure there are plenty of times it just makes things easier.

I think metaprogramming is also at odds with static analysis (e.g. a good type system), simply because the code itself is not static enough to analyze.