Lambda the Ultimate

The tone of the writing definitely is "d'oh, d00d!". He also treats Haskell = FP. He thinks mathematical proofs are declarative (iirc, in first order logic deductions are sequential).

The part he tries to rip apart referential transparency with his alleged "formal logic" is hilarious.

He's not pissed off at functional programming. He's pissed off at himself not being able to convince that "young FP supporter" he was talking to.

While Haskell certainly isn't the alpha and omega of FP; the rest of the cwell-known languages commonly referred to as "FP" languages (the Lisp family, the ML family) aren't that different, when you get right down to it, from many of the so-called imperative languages out there. Lisp and its cousins are dynamically-typed eager languages with side effects; ML and it's cousins are statically-typed eager languages with side effects; ignoring the issue of type inference there are plenty of examples of both in common industrial use. (And it won't be long IMHO before an "OO" language with type inference starts gaining popularity--perhaps it will be O'caml; perhaps it will be something that looks more like C/C++/Java but looks just like O'Caml, modulo the syntax).

Haskell, being a lazy language, does stand out among the crowd for that fact; and is the language which is most different from Perl and its ilk.

In many cases, the difference between a "functional" language and an "imperative" relates more to the programming culture surrounding the language; not to the intrinsic features of the language proper. Two examples of this phenomenon are:

* Common Lisp vs. Scheme. The latter is based on the former in quite a few ways; the two have undergone quite a bit of divergent parallel evolution since. Feature-wise, they have a lot of similarities. CL, however, is usually used in an imperative fashion, whereas Scheme is often used more in a functional style. Little in the definitions of either language dictates this divergence (although mandatory TCE in Scheme makes recursion formualtion of algorithms more convenient).

* C++. Long bashed as a lousy OO langauge; it has enjoyed a bit of a renaissance as a functional language, as people have discovered what fun you can have with templates. :) At it's heart, though, still lurks C--a good old fashioned, down-and-dirty imperative beast. :)

While the author's tone is decidedly non-scholarly; I wouldn't hold that against him.

"* C++. Long bashed as a lousy OO langauge; it has enjoyed a bit of a renaissance as a functional language, as people have discovered what fun you can have with templates. :) At it's heart, though, still lurks C--a good old fashioned, down-and-dirty imperative beast. :)"

http://www.kfa-juelich.de/zam/FACT/start/index.html

uses http://www.cc.gatech.edu/~yannis/fc++/

C++, Common Lisp, and Ocaml are all billed as "multiparadigm" though, so I'd expect them to have more imperative communities.

Have you read Lambda: The Ultimate Political Party? That gets into the language-as-a-community idea.

What is missing in your taxonomy are lazy evaluated dynamic languages. Computer algebra systems like Mathematica or Maple may fit into this category allthough they enable expression evaluation both in lazy and eager mode. An example of a Maple session:

> f:=a+b;
                       a+b
> g := Eval(f,a=8);
                       g := (a + b)|     
                                   |a = 8

> R0 := expand(Eval(a+b,a = 8));

                      R0 := /a|     \ + b
                            \ |a = 8/    
> value(g);
                             8 + b

He mostly seems to be disgruntled with dynamic scoping. Well, that and the fact that no real computer can perform infinite operations. I'm not quite sure what these two things actually have to do with the pros or cons of the functional paradigm per se.

iirc, in first order logic deductions are sequential

I'm not sure what you exactly mean, so maybe you are right. But this isn't true from my interpretation of sequential.

I'm familiar with natural deduction for first-order logic. There is a very standard syntax that emphasizes the tree structure of a proof. This syntax is more common in Europe than it is over here in the US. If you are familiar with Philip Wadler's papers, you've seen it before.

(Well, Philip is usually doing type theory, so the syntax is extended a bit from natural deduction. He actually has a paper talking about how this extension relates to the Curry-Howard isomorphism.)

Anyway, this isn't what I'd call "sequential." It's sequential analogous to the way that order of operations is sequential. If you want to evaluate

(1 + 2) * (3 + 4)

it doesn't matter if you evaluate 1+2 or 3+4 first, but you must evaluate both before you evaluate the multiplication sign. In the case of

1 + (2 * (3 + 4))

Without applying algebra, you don't have any choice in what to evaluate first. There are examples of sequential expressions, but not all expressions are sequential. Since there is no computation in first-order logic, you may check the nodes in any order, so the analogy isn't perfect.

But yes, Mr. Perl Monk is quite confused, and it's quite obvious he has only the most superficial acquaintance with functional programming and Haskell.

I am not familiar with the tree representation. Once the deduction is there I suppose you can "check" it any way you want, but I was referring to the actual execution of a deduction: a formula from a previous step and a logical axiom or premiss leading into the next formula via modus ponens.

In that sense I do not find proofs declarative.

Proofs are Programs: 19th Century Logic and 21st Century Computing by Philip Wadler

Type Theory and Functional Programming by Simon Thompson (Now freely available online!)

Features from every language ever invented is buried somewhere in Perl. And if it's not, it soon will be.

Because Turing proved that all programming languages are equivalent

Any references?

I remember him proving existence of Universal Turing Machine, and indecidability of halting problem (for a-machines), but this?...

From "From the Church-Turing Thesis to the First-Order Algorithm Theorem", by Saul A. Kripke:

the obvious fundamental importance of Turing's work both for logic and computer science has led to an overemphasis on his paper as the justification for the Church-Turing thesis. It is even said that Turing proved a theorem that every “function computable by a human being in a routine way” is Turing computable. Though several have endorsed this claim, it is hard for me to see how it could really meet modern standards of rigor.

(I didn't read the paper, as access to it is limited (IEEE). Grrr.)

More obviously, Turing machine deals with functional computations (it computes values of functions from finite strings to finite strings), and not with processes. There are many ideas about dropping this requirement of finiteness of input and output, but somehow I don't feel them solving the problem.

PS: I realize that you may be just kidding, as even if all PLs are equivalent to TM, the nonfunctional requirements rule the game - usability, performance, maintanence, etc., are very different for different PLs. That's why I prefer not to see a program as a manufactured machine - I think this perspective distorts reasoning about program properties, transformations, descriptions of SE processes, etc.

PPS: I guess I am "pissed off about" Turing tarpit :-)

Yes, as you guessed, I was kidding. Specifically, I was poking fun at the (ab)usage of the Church-Turing Thesis by the author of the article up above, which used it to essentially say what I did.

From what I understand the Church-Turing Thesis is basically that any "Turing-equivalent" language can compute the same set of mathematical functions as any other. Of course there's a huge gap between saying that and saying that all languages are equivalent! cf:

Church's thesis, upon which we base our whole definition of 'computing', explicitly states that Turing machines, lambda calculus, while programs, Post systems, mu-recursive grammars, blah-de-blah-de-blah, are all equivalent...

Yes, the syntactic sugar of functional programming is somewhat different from the syntactic sugar of non-functional programming. Yes, functional programming does encourage a different set of techniques for solving problems. Yes, those techniques encourage different ways of thinking about problems and data.

No, functional programming is not some kind of magic pixie dust you can sprinkle on a computer and banish all problems associated with the business of programming. It's a mindset-altering philosophy and/or worldview, not a completely novel theory of computation. Accept that. Be happy about it. At least friggin' COPE.

WHAT?! Functional programming isn't magic pixie dust?! I don't think I can COPE!!

There was a related discussion on the extremeperl yahoo groups mailing list, hopefully related
enough to mention it here.
The discussion started with href="http://groups.yahoo.com/group/extremeperl/message/166" >HaskellDB, crossed the edges of the href="http://groups.yahoo.com/group/extremeperl/message/209" >Turing Tarpit, ended with, href="http://groups.yahoo.com/group/extremeperl/message/226">I haven't found a problem that I needed Haskell to
solve.
I think the moral of the story is that some people are perfectly happy where they are, and any attempts to change that will only upset them.


--Shae Erisson - ScannedInAvian.com

The point of lazy evaluation is that the order of evaluation does not matter (i.e. referential transparency). I gather he doesn't understand how monads thread the state, so he's assuming that haskell acts like perl in the way it handles state.

Lazy evaluation, as well as Dataflow variables (Single Assignment, Promises, or whatever you want to label them as), guarantee that the values will not change. They may not currently be evaluated, and you may have to wait until they are evaluated, but they do not change. The first four chapters of CTM (all I've gotten thru so far) are exactly about how lazy evaluation is not time or order dependent.

The larger question, though, is what are the defining characteristics of Functiontal Programming. Well, Object Oriented Programming generally is defined in terms of:

• Encapsulation
• inheritance
• polymorphism

• parametric genericity
• higher order functions
• referential transparency

When he says that lazy evaluation is a side-effecting state change, he's talking about actual implementations of Haskell, not the abstract language definition, and he's correct about that, as far as I know. No implementations of Haskell I know of automatically get concurrency and parallelism, and there are good reasons to suspect that that's a hard problem in general. (At least, if you want a speedup on loosely-coupled multiprocessor machines.)

With regard to referential transparency, it's not that he doesn't "get" it --- he wrote a pretty lucid and insightful explanation of exactly when it's safe to replace a variable with the expression that gave it its value in an imperative language. I don't fully understand what he wrote about Haskell and frames of reference, though.

It's possible to get deadlocks in the lazy evaluation, but this is not so much a time-space consideration as it is a variation on the halting problem. Easy enuf to avoid as well. Assuming you get no deadlocks, then there should be no other side-effects.

His point about referential transparency seems to be that the only advantage is really tied up in lexical scoping. But the idea of referential transparency is that if I call a function 1000 times (or infinite times if you prefer) with the same parameters, I will get the same result each and every time.

As for concurrency and parallelism, you can attain these with Haskell, but you may not get an efficient implementation. But if it's hard to get these with referential transparency, then it's nigh on impossible without them.

My recollection of what RT means is not simply that you can call a function repeatedly to get the same results. That just sounds like the definition of a function!

Referential transparency is a property of contexts, not generally of languages. The term dates back to Quine (Word and Object) and before that Whitehead and Russell (Principia Mathematica). Roughly, a context C[-] is referentially opaque if it can distinguish some variable from its value, i.e., there is some variable x that can be instantiated with its value v where C[x] != C[v].

A simple example is quotation. Let C[-] be the context

"[]" has two syllables.

C[-] is referentially opaque because, e.g., if The man refers to Cicero, then C[-] can distinguish the two:

C[The man] = "The man" has two syllables. = T
C[Cicero] = "Cicero" has two syllables. = F

Sestoft has a paper (Referential transparency, definiteness, and unfoldability) that attempts to extend the definition of referential transparency to apply to languages in a useful way, though I have my reservations about it. (Sorry, it doesn't seem to be available online.)

A short paper by Will Clinger in the early 80's (Nondeterministic call be need is neither lazy nor by name) discusses RT as well, IIRC. And another apology: I could only find this one on ACM's web site.

Incidentally, this seems to be what the Perl author was getting at -- his terminology is unfamiliar to me, but he seems to be pretty close to the classical definition of referential transparency. From what I understand (which is limited), it seems to be a very subtle notion and interacts with language features in very subtle ways. I'm skeptical of people who make fast and loose claims with regards to RT. The author is right to be "pissed off." :)

But maybe we're saying the same thing? Because any equality relation will have rules like

\Gamma |- e1 = e1' : T' -> T 
\Gamma |- e2 = e2' : T'
-------------------------------------
\Gamma |- e1 e2 = e1' e2' : T 

If I understand you, the "real" notion of RT that you mean to formalize, as it might apply to languages, is that you can substitute equivalent expressions in any program without changing the meaning of the program ("substitute equals for equals").

But the problem is, where are you going to allow this substitution? In any non-trivial language, there are going to be limitations about what parts of a program you're allowed to swap out, whether to avoid variable capture, or because certain contexts, like quotations, "don't count." Even in Haskell, you can't replace (\x -> x) with (\y -> y) in the context "[]".

(This is where it gets slippery: if you let the language designer choose which contexts "don't count," then it's trivial to define any language as referentially transparent.)

Perhaps we are saying the same thing, because the point is that the notion of equality isn't enough; you also need to specify the contexts, whether via congruence rules or a grammar of contexts.

Though in a sense my point is inarguable, because it's a historical one. The originators of the terms "referentially transparent" and "referentially opaque" defined them in terms of context, and they have generations of historical usage that way, before they started being confused by us computer types in the last 30-odd years.

PS - on further reading, it seems you're suggesting that, to compare apples to apples, we could require the language to derive its notion of equality and congruence rules directly from the reduction relation. I suppose it's plausible... you'd need to state the ground rules about the reduction relation. This is the crux of the problem: languages are diverse and we're trying to have a statement that applies to all languages, so there must be a set of assumptions about the language that are at the same time unrestrictive and yet equalizing.

I need to go check out the Sestoft paper again from the library and look at it more closely. No time right now.

I guess I'm saying that:

1. For any given language, the only interesting equality relations are the ones that preserve equality under its reduction relation. You can still have more than one possible equality relation, of course.

2. As an aside, observe that each equality relation gives rise to a notion of context, via the congruence rules of the equality relation. Furthermore, there's a slightly different notion of context for each possible equality -- but the important point here is that we can treat context as a derived notion.

3. "Referential transparency" means that you can construct an equality relation which is consistent with the full beta rule for functions variable-bindings. So ML and Scheme are not "referentially transparent", because you can only preserve equality when substituting values for arguments.

4. What if we don't have functions in the language? (For example, Prolog.) I don't know what to say here, because I haven't thought hard enough about this.

Sestoft's paper is interesting. I recommend checking it out.

Even if the article has a good definition of referential transparency (clearly copied from a logic text, with the Venus example), his examples don't seem to make any sense at all in the context of FP.

In his Myth #3, he first demonstrates referential opacity using what he calls a dynamically scoped variable. I don't see how that maps to any real functional language I know of. The best you could do in a functional language is make the function rely on a variable defined in an enclosing scope, but that doesn't break referential transparency.

His second example in Myth #3 ends up complaining that length('three') does not equal length(3), without actually showing that there's any reason to expect that they should be equal, whether by RT or anything else. His definition isn't clear enough (for me) to be sure what he's trying to say (is he making a misleading pun on the fact that the function he defined is called 'equals'?), but regardless, I'm not seeing the connection to an RT violation in functional languages.

His myth # 4 is just silly, basically redefining lexical scoping as mutation, and by doing it in Perl (which is statement oriented as opposed to expression oriented) he can make it look marginally plausible, because lexical scope is less explicit.

If there's a real issue here with respect to RT and FP, I'd like to hear what it is. I don't think the article makes any such case.

[Edit: also, notwithstanding any subtle applications of early definitions of referential transparency, there's a fairly well-established use of the term which (as I'm sure we all know) means something like "An expression E is referentially transparent if any subexpression and its value (the result of evaluating it) can be interchanged without changing the value of E." (Foldoc) The existence of this meaning pretty much makes the Perl article's point moot - it's arguing about a different definition of the term than the one intended by those he's arguing against.]

The thing is, you can come up with an established set of ground rules for any particular language, saying "these are the expressions, these are the notions of subexpressions, and this is the notion of equality." Then you can say whether some program or expression is referentially transparent.

But it just doesn't work when you try to extend this to compare two languages, which is in essence what FP'ers are doing when they try to claim "my language is great 'cause it's referentially transparent." I can always come back and say, "cool, boss, so's my language." I just define either the set of relevant contexts and/or the equality relation to make the claim true.

In an informal sense, we often probably know what each other means when we talk about RT in one language or another. But AFAIK, there's no precise way to make the comparison.

(And this, of course, is completely disregarding the debate of whether being RT is a uniformly good thing...)

"That just sounds like the definition of a function!"

Yes, in the mathematical sense. But functions in most programming languages are loaded with side effects, so they don't behave like real functions. For the same arguments, they may result in completely different values. I guess the canonical example is that of bank teller operations.

I'd say the "bank teller operations" example is the canonical anti-example. I've built a fair number of "accounting systems," in the sense that they dealt with accounts that had credits and debits.

First of all, from an accounting point of view, the whole idea of updating a total is bogus. For certain performance reasons one might keep a total stored somewhere, but you do that only if you have to, because you know it may not be accurate, and you never use that total in any place where you care if the result is approximate rather than correct.

Instead, you keep a record of transactions (credits and debits), and that's your account. When someone makes a deposit, you take the list of transactions, and add the credit to the end of the list. You do the same for a withdrawl, except adding a debit. When you want to know the total, you sum up all of the credits and debits, and hand out that number, perhaps along with the time of the last transaction.

Now, accountants do this for auditing purposes. Database folks do this to avoid logical errors, because you only have one way to get the true balance, so it's impossible to end up in a state where the sum of the transactions is different from the balance.

But of course, when you do this in FP, you always *do* get the same answer with the same inputs, because the list of inputs is a list of transactions and a deposit or withdrawl. If you give it the same list of transactions and the same deposit, you always get the same answer.

What you didn't see in your example (because you didn't follow proper accounting principles) was that you actually weren't handing the same arguments to the function every time, your bank account was external state that the function was modifying. The truly functional way of looking at it, if you're going to look at it that way at all, would be to take the state out of the the deposit function, hand it a bank balance and a deposit amount, and have it return the new balance amount.

... but i was just pointing out a simple and naive example implementation, like the one found in SICP and many entry-level CS books.

Before monads, i heard taking time as an explicity parameter was a necessity in Haskell to conserve functional purity...

Is he confused, or am I?

My take on a lot of the weird things he says in that piece is the he is really talking about FP in Perl rather than FP in general.

Many of his objections seem to assume that you are actually NOT using pure FP, or even a close approximation.

In spite of his mention of Haskell, I sincerely doubt that he has more than superficial familiarity with it, or if he does he's not really commenting on it.

Viewed through this lense, I don't know that we need to devote the attention to this that we have so far. ;-)

I agree. Though he seemed knowledgeable in general, some of his arguments really went off on tangents. Maybe he has a point, but he didn't get it across very well.

The part about referential transparancy was especially confusing. Just because Perl's dynamic scoping "breaks referential transparency" doesn't mean FP doesn't have referential transparency.

Also, while debuking the notion that "Functional programming is 'different from' imperative programming":

It's a mindset-altering philosophy and/or worldview, not a completely novel theory of computation.

What is the key defining characteristic of FP?

I am prepared to call a language "functional" iff it has first-class lexical closures.

I am prepared to call an FP language "pure" iff its formal semantics admit no observable mutable state.

Avoidance of side effects and/or referential transparency?

That's it, in my mind. Consider Erlang, which didn't have higher-order functions for a long time (and still doesn't have lazy evaluation or type inference), but was still functional, because of the general style of coding involved.

Avoidance of side-effects

If that is the criterion, all languages are FP: you can always avoid side-effects where possible.

FP languages are simply ones that help you along in that avoidance (actually minimize or contain would be better than saying avoid). Probably stating the obvious, but FP is about functions, in the same way that OOP is about objects.

Referential integrity is one aspect to FP, since we are trying to use the well-driven road of functions as they are treated in the maths (where side effects are not usually allowed). Higher Order functions are another aspect since we are interested in manipulating functions as data. And, of course, we have to worry about types when we are manipulating functions.

[I tried to fix a typo but I posted twice somehow]

Structured programming works better for the analogy you are trying to achieve.

Today's expert will write functional programs even when working in C, just like an expert from twenty to thirty years ago would write structured programs even when working in Basic.

Would anyone call Basic a "structured" programming language? I think not. Would anyone call C an unstructured programming language, even though it has a "goto" statement? Well, I might. But not using the traditional technical sense of the word.

Perhaps answer is not the technological features of a language, but the common culture of its programmers. Thus calling a language "imperative" vs. "functional" is really an idiom for describing the community.

By this criteria, JavaScript is imperative and OCAML is a functional. This seems right, even though they both have mutation and higher-order functions.

Of course, the design of a language has indelible effects on the culture that grows up around it. If you could go back and try again, I don't think that you could ever get a structured programming culture out of Basic, nor will you ever get a functional programming culture out of C.

Now that the world has changed a bit, and many of the big new languages have all been intentionally designed and aggressively marketed by large corporations, marketing will increasingly factor into shaping this culture, along with the traditional factors of educational systems, inherited culture, and technical features.

Perl being Perl, it's almost impossible to avoid side-effects. Even when you aren't on a strictly conceptual level. The implementation often alters the underlieing data structures of variables when it doesn't strictly need to for the code at hand (but may need to for some extreme edge case).

This question reminds me of a discussion between two Greek philosophers around 500 BC. As I remember it:

Herakleitos, the obscure, argued "Panta Rei - everything moves". He also said that all stuff is made of fire (we would say energy).

Parmenides basically argued "What is - is", stating that all stuff just is and that movement itself is an illusion (which was later translated to atomism by Democritus - everything is made out of atoms, stuff which cannot be divided further, and void).

It's funny to see that at some fundamental level nothing has changed over the last 2500 years since both ideas can be found in various forms both in physics and computer science. In fact, it is, I think, a possible explanation for the basis of the difference between OO and FP.

OO as a software engineering principle tries to dissect the world into atoms (data); FP tries to dissect the world into energy (algorithms). It is also funny to note that both also have corresponding abstraction principles (over data or over algorithms).

Taking the metaphor further it also gives a good argument never to go into an OO vs FP war since you're probably discussing views-of-the-world/beliefs/religion and not science.

[EDIT: killed what could be taken for a rant]

The other thought is whether anything will actually change in the next 2500 years ;-)

So back to your question: I guess an answer is "functional programming is a way of looking at the world." (it is a religion ;-)

Ah well, it is sunday afternoon, right?

There's a nice Monad.Reader article coming up soon (next issue hopefully) that compares and contrasts functional programming and object oriented programming. There really are definite and clear differences.

--Shae Erisson - ScannedInAvian.com

I would say the religious flavor is caused by the lack of clear terminology with either camp. Who can define "functional programming" or "object oriented programming"? No one, because they are meaningless terms, like "operating system", etc.

Who can define "automobile", "luck", "war" or "meaning"? I liked Scott's original question since it addressed the issue in terms of "I know what it is when I see it" and he asked what functional programming is. This in contrast to the more often asked question "what constitutes a (good) functional programming language".

Now the metaphor is flawed, as all metaphors are but, I think, it gives some insight into why our ape-like brains pick up FP and OO as fundamentally different engineering principles (in principle "What happens if I throw the rocks vs. what happens if I stack the rocks") and the metaphor shows that we are still dealing with very old views of the world. I find that amusing.

Views of the world are what people use to master its complexity and mastering complexity is exactly what (software) engineers do daily; which is why I think engineers should know some basic philosophy.

This is not some deep insight or science; let's not go kuro5hin on this one.

Who can define "automobile", "luck", "war" or "meaning"?

What? You don't know what these words mean? What is wrong with you? ;-)

But seriously, just because words are slippery (their names can be bound to subtly different things) doesn't mean that you can't come up with unambiguous, clear definitions for specific purposes.

Part of the problem with the terms "OO" and "FP" is that we usually apply them indiscriminately to
a) communities with particular values and perspectives
b) styles of programming
c) features of programming languages
among others.

As Peter points out in an earlier post, in sense a) they are like a Kuhnian paradigm, but in senses b) and c) quite specific definitions are possible (as demonstrated convincingly in Peter's book, CTM).

So before we blithely dismiss ideas as "religion" or terms as without substance, it may be worthwhile to make the effort to sort out what they might mean in more restricted and well-defined settings.

Good, so you agree that I can narrowly define FP as an engineering practice where my basic building blocks for composing programs are functions which relates well to an engineering paradigm where I try to dissect a given problem space by viewing it as a predicate over a world in which all solutions are fundamentally composed out of stuff which moves other stuff around which is actually a very old view of the universe which corresponds well with my ape-like mindset ;-)

Btw, I didn't try to be dismissive about OO or FP as religions; I gave a metaphor which, if taken as truth, exposes that OO and FP have underlying belief systems and that, therefor, there are reasons why (a) there is a big percieved dichotomy and (b) there is an additional argument which make debates easily tend to degenerate to religious wars.

I think it is a useful but not too important metaphor which gives rise to one definition of FP. Sometimes you need (non-mathematical) metaphors like that to broaden your understanding of concepts. I.e.: When do I, don't I, use FP? What are good engineering paradigms for FP? What is the role of rewriting in FP? How do we abstract over "movement"? Or even: Should an FP interface be based on animation?

It is a metaphor - a rapid prototype throw-away argument.

And hey, I am an advocate of FP; please shoot, but uhm, please try to miss also ;-)

Taking the metaphor further it also gives a good argument never to go into an OO vs FP war since you're probably discussing views-of-the-world/beliefs/religion and not science.

The two camps fit rather well the definition of paradigm given by Thomas Kuhn in "The Structure of Scientific Revolutions". Each camp can solve certain problems well and has a different set of unsolved research issues. They speak different enough languages that meaningful discussion between them is difficult (although not impossible, though). Kuhn's book is really interesting by the way -- I strongly recommend actually reading it and not just reading people's comments about it.

What he says is that referential transparency does not really exist in functional programming languages, because the same symbol can be declared in two different places but with a different value, thus creating the same problem that imperative languages have: at one place a symbol has value X, and in another place it has value Y, therefore confusing the programmer and increasing the chance of introducing bugs. Here is an example:

(1) let x = 5
(2) let y = 5
(3) let p = if x == y then print('x equals y') else print ''
(4) let y = 6
(5) let p = if x == y then print('x equals y') else print ''

Here is the explanation of the problem, related to how a programmer may be thinking:

1. x has value 5.
2. y has value 5, therefore x equals y (the programmer learns this at this point).
3. print 'x equals y' because (2) is true.
4. y has value 6.
5. print 'x equals y' because (the programmer remembers that) (2) is true.

but the fact is that (5) is not true, because 'y' is changed in (4), but somehow the programmer is stuck with (2), and thus introducing a bug in the program.

In programming languages that allow introducing the same symbol with a different value, this problem can be in the same block. In programming languages that allow the same symbols in different blocks only, the problem is spilt all over different contexts, which may make the problem even harder to spot.

No matter what is the case though, the whole problem looks like the problem of assignment in imperative languages: the programmer needs to track (in his mind) the various symbols and their values each time they are being used, in order to avoid the problem of using the wrong values, which makes functional programming (almost) as difficult and error-prone as imperative programming.

I think that the solution lies in making each function unable to access symbols of the outter contexts, i.e. functions should only be allowed to use their parameters and nothing else. I don't know how much restrictive this would be, though.

"I think that the solution lies in making each function unable to access symbols of the outter contexts, i.e. functions should only be allowed to use their parameters and nothing else. I don't know how much restrictive this would be, though."

Well if you want higher-order functions it would be quite problematic.

I believe what axilmar proposed is actually killing lexical (and any other) scoping. Meaning only combinators are supported, and not closures. I might misinterpret either axilmar's proposal or the definition of closures or both, though...

and that would be very bad if you consider that functions are bound to ordinary symbols, making nearly every function in an ordinary functional language a closure.

and I must say that the closure:

(define (! n a) 
(if (eq 0 n) a (! (* n a) (- n 1))))

feels much nicer than the combinator:

(define (! n a if eq * -) 
(if (eq 0 n) a (! (* n a) (- n 1) if eq * -)))

What you're suggesting is effectively mandatory lambda-lifting - there was a time when many implementations actually did this behind the scenes!

The cure is worse than the disease though, and the functional case simply is not as bad as the imperative one - with all bindings defined exactly once, all you need do to know the current value of an identifier is an innermost-first search of the scopes you're nested in rather than checking everywhere that may possibly have seen an identifier of the same name or a reference to it.

I think I'm very confused about scoping vs. free variables. Here I've done plenty of FP programming but apparently with some very fast-and-loose idea of what precisely is going on or allowed.

In ghci, if I try to define a function with a free variable, it doesn't like it.

Prelude> let foobar () = xyzpdq
<interactive>:1:16: Not in scope: `xyzpdq'

(Fortunately for my sanity, when xyzpdq is pre-defined to 10, then even if I later change xyzpdq's value to 20, foobar still returns 10.)

Are there only certain things that can be free? Crap, time to go back to remedial FP studies!

It seems that you are confusing static and dynamic scope. The exemples you give implicates that you are used to dynamic scoping but are using a staticaly scoped. (practicaly every modern FP is staticaly scoped.)

The diffrence lies in how free variables are evaluated. With dynamic scope the free variable is evaluated in the scope there the function is applied. With static scope on the other hand the free variable is evaluated in the scope there the function is defined.

ie then you run foobar you get the value xyzpdq had then foobar was defined. That would mean that your first example would always be an error.

(in regard to the recent discussion: I'm not sure that this really is a suitable topic for LtU as most people here know verry vell how static typing works.)

I think maybe I figured out my (simple, but very unsettling for a bit there) confusion.

I should have mentioned that my instinct is that it right for ghci to throw the error. I thought I understood the difference between dynamic and static scoping - I would have defined it as you have. What I think is confusing me is the talk of lambda lifting, in particular example. I didn't realize the 'where' was actual syntax instead of English. When it is syntax it all makes sense, because x is actually an argument to the function. In the English sense it seemed to me my ghci example proved it wouldn't be accepted.

Please excuse me here; I know a little bit about functional programming, and I'm trying to learn more, but I'm still at the stage where I find some of these finer points confusing.

First, looking at your example, it seems to me that this is not an example of functional programming because you've equated the same identifier to two different values within one scope. (At least, I don't see any indication of two different scopes in your example.) How can y be both 5 and 6? It seems to me you've turned it into a variable. (And my Haskell interpreter agrees with me: "ERROR "test.hs":2 - "y" multiply defined".)

So presumably Hasell and other purely functional languages "allow the same symbols in different blocks only," as you say. But now I don't understand how the problem is ever in "different contexts," since you only ever have to look at one block to determine what any function is going to see, which it seems to me makes any problems quite easy to spot.

I am, of course, assuming lexical scoping here, but most languages use that these days because dynamic scoping make it, well, rather difficult to determine what the value of a binding might be. (IMHO, it makes global variables look nice in comparison!)

Now it seems to me that if you look at the way this whole thing is set up in Haskell--no variables, lexical scoping--even though you let a function make use of bindings not passed in as parameters, it's going to be darn easy to find out what the heck anything's bound to, because you simply look out through increasing levels of scope until you find the definition, and there's the value. Maybe I'm naive, but this strikes me as a brilliant simplification of programming life.

So assuming a situation like that, which is one of the things that functional programming is supposed to be all about, as I understand it, does point #4 still make any sense? Or is it dragging in things like variables or dynamic scoping that don't exist in a pure functional language, making it a rant against a straw man?

And incidently, I don't see how this makes higher-order functions problamatic. Can't the function just carry a closure (is that the correct terminology) around with it, that contains all of its bindings? It seems little different than a stack.

Please excuse me here; I know a little bit about functional programming, and I'm trying to learn more, but I'm still at the stage where I find some of these finer points confusing.

Afaics, everything you wrote is correct. Forgive me for restating some of it elsewhere, but I felt some additional clarifications might be useful.

It has been 7 years since I've worked with ML, but what I clearly remember was that I entered the same symbol with different values again and again in the interpreter, ML accepted it, because the symbol was just a label for the value, not a variable, and it did not break previously defined functions.

Anyway, the guy that is 'pissed of about FP' is probably exagerrating a little bit. Although I haven't used an FP consistently for a project, I've never came up with such a problem.

In programming languages that allow the same symbols in different blocks only, the problem is spilt all over different contexts, which may make the problem even harder to spot.

This is incorrect. In a functional language, symbols in different blocks (contexts) represent different variables, even if they have the same name. There's no possibility of confusion, because their scope is lexical, i.e. determined entirely by the visible block structure of the program.

No matter what is the case though, the whole problem looks like the problem of assignment in imperative languages

No, it really doesn't. If you think this, you've misunderstood something, and should spend some time actually working in a functional language.

the programmer needs to track (in his mind) the various symbols and their values each time they are being used, in order to avoid the problem of using the wrong values

The whole point of lexical scoping is that it takes the problem about as much out of the programmer's mind as possible: you only have to look for a variable's definition in the nearest enclosing lexical scope which binds that variable. This is something that can be determined without looking in any other functions or modules, and it can be done by a trivial visual inspection, it doesn't require much thought at all. Certainly, almost no thought is required compared to the cases that are possible in imperative languages.

which makes functional programming (almost) as difficult and error-prone as imperative programming.

So far, no-one has actually produced an example to illustrate this. The example in the original article is in Perl, which is statement-oriented instead of expression-oriented, so doesn't have the same kind of lexical relationship between bound variables and their scopes. The example above rebinds y without creating the necessary scope for it, which would be illegal in a functional language.

The reason we're not seeing any examples actually written in a functional language is that they wouldn't illustrate the point they're attempting to make, because functional languages don't suffer from the claimed problem.

This is incorrect. In a functional language, symbols in different blocks (contexts) represent different variables, even if they have the same name. There's no possibility of confusion, because their scope is lexical, i.e. determined entirely by the visible block structure of the program.

No, it really doesn't. If you think this, you've misunderstood something, and should spend some time actually working in a functional language.

Perhaps you did not understand that I talked about confusion of the programmer, rather than confusion of the language. I am well aware of how FPLs work.

you only have to look for a variable's definition in the nearest enclosing lexical scope which binds that variable.

Well, you still have to look, don't you? even if it is trivial, sometimes it may create confusion, especially when it comes to communication between programmers: one programmer may speak about the instance of the outter context, while the other about the instance of the inner context. The problem could also be for a single programmer that comes back to the program after a while and forgets that the local binding exists (perhaps missing it because it was out of view at the time he inspected the function?).

Anyway, I consider the 4 points of the original article as nothing important...I just gave an clarification based on what I understood.

The reason we're not seeing any examples actually written in a functional language is that they wouldn't illustrate the point they're attempting to make, because functional languages don't suffer from the claimed problem.

I think the following can be done in ML:

val y = 3
let foo a =
local
    val y = 4
in
    y +a
end;

Perhaps you did not understand that I talked about confusion of the programmer, rather than confusion of the language. I am well aware of how FPLs work.

You are correct, I did not understand that, and I apologize for being overly critical as a result.

Nevertheless, your message seemed to imply that there was some legitimate basis for the programmer's confusion. I dispute that.

Well, you still have to look, don't you?

Right, but this does not compare to the problems that can be caused by the updating of mutable variables, which was the comparison the article was making. Whenever a variable is referenced, no matter what semantics are used, you have to look to find its definition.

Re the example you gave, I don't know what dialect that was in. In SML, it would look like this:

val y = 3

fun foo a =
  let
    val y = 4
  in
    y + a
  end

So, when you see the expression y+a, you look to the nearest enclosing scope for the definition of y, i.e. y=4 in this case. Once you find that, you're guaranteed that there's no need to look any further. The earlier definition of y isn't relevant. Again, the issues here's aren't comparable to what occurs if you're dealing with a single instance of the variable y that happens to have its value updated in different places. In that case, even if you find an earlier assignment of y, it might be in a conditional block, so you need to perform a mental dynamic evaluation of the code to determine what its value might be at the point you're interested in. Potentially, you have to look at every assignment of y between its definition and the use you're interested in. The need for this is entirely avoided by the functional approach.

1) Even giving all this, the big big evil/boon of assignment is aliasing, and that still could not happen in this "confused" "FPL".

2) In practice most programmers in lexically scoped languages don't take full advantage of that particular liberty. You very rarely see identifiers reused in the same scope.

But there is still a very minor problem: if a local value is introduced with a name of the value of the outter scope, the result of the function is different. It's still like assignment.

Here is a program:

val y = 1
fun foo a = 
let
    val x = 2
in
    x + y + a
end

What is the result of function foo 3? it is 6: x + y + a => 2 + 1 + 3 => 6.

Let's say I introduce a local variable y to function foo:

val y = 1
fun foo a = 
let
    val x = 2
    val y = 100
in
    x + y + a
end

What is the value of foo 3? it is: x + y + a => 2 + 100 + 3 => 105.

If there was a part of the program depending on foo 3 returning 6, now that part is broken.

Of course this rarely happens, and the problem is very easy to solve in FP languages, whereas in imperative languages the situation is chaotic and nearly impossible to track (especially if pointers are involved). But the problem is real nevertheless.

The breakage is in the function itself changing though, which is always a problem everywhere. I could just as easily write 100 where the y was.