Ask five programmers to define functional programming, get fifteen different answers.
"Purely functional programming" is writing programs to resemble mathematical functions, with referential transparency and absence of side-effects and so forth. Also know as "what Haskell does."
"Function-oriented programming" is writing programs using functions as your main tool for abstraction, encapsulation, defining interfaces, unit of code division, etc. This part of functional programming is more typified by the Lisp family.
Most languages that are considered functional generally encourage both of these aspects, partly because they work well together. The confusion over definition comes from these two halves getting tangled, and some languages or programmers emphasizing one half over the other.
Non-functional languages that are becoming "more functional" are generally importing features from the "function-oriented" side of things, and adopting the "purely functional" aspect as a best practice convention, if at all. It's probably more accurate to say that they enable a functional style of programming, rather than that the are functional.
I offer a definition of "functional programming" as "based on semantics of lambda calculus".
So much for “Lisp comes from [the] untyped lambda calculus”.
Lambda calculus is a formalization of number theory which builds up numbers from functions. An important result is that lambda calculus is Turing complete. It shows that we can boostrap numbers and number theory from almost out of nothing, using Church numerals.
Lisp has never built numbers out of Church numerals; it had ordinary integers.
Also, lambda calculus, typed or not, does not have its own syntax as a data type. It doesn't have symbols. You don't quote a symbol and pass it to a function and so on.
So that's basically it; there is a link between Lisp and lambda calculus due to the use of the word lambda in a related way, and a somewhat stronger link between lexically scoped Lisps (which came later) and lambda calculus.
Also, even languages like Haskell are not based only on theoretical lambda calculus, but they also have primitives for data types, which could be, in theory, represented by lambda expressions.
You see, if a function isn't pure, then it isn't a (mathematical) function. But we tend to overload terms because of their marketability.
In the same way that some companies wanted to overload "open source". The general rule of thumb is that if something is desirable by the market, then it is going to get overloaded either by people not knowing what they are talking about or by sales people.
It's regrettable that we overloaded the word "function", given we could have used procedures or subroutines to denote, you know, jumps in code that trigger effects and push/pop the call stack.
And as proof, applying filter/map and other similar operations with side-effecting procedures is a really, really bad idea, because such operators are usually implemented with lazy behavior (in order for "fusion" to happen) and laziness doesn't blend well with side effects, with the result becoming non-deterministic. E.g. at least people that worked with Map-Reduce frameworks should know what I'm talking about.
Or in other words, there is no such thing as "function-oriented", there's just local application of FP where it seems to be making sense, but with all the caveats that entails.
To me the core is "no side effects" though (for pure FP). It's interesting to see what others consider to be the most salient feature(s).
As a consequence you get referential transparency and thus equational reasoning. But change this definition and the term becomes meaningless.
* (eq (expt 2 100) (expt 2 100))
NIL
(Disclaimer: I'm not saying functional programming is the right approach for writing every program, but if a language can't even get arithmetic and relational operators right...)
An implementation is permitted to make "copies" of characters and numbers at any time. The effect is that Common Lisp makes no guarantee that eq is true even when both its arguments are "the same thing" if that thing is a character or number.
http://www.lispworks.com/documentation/lw51/CLHS/Body/f_eq.h...
On the other hand, in Haskell and ML, due to their superior value-oriented design, there's no way to distinguish between “this 123456789” and “that 123456789”, or between “this list [1,2,3]” and “that list [1,2,3]”. There is only one number 123456789 and one one list [1,2,3] in the language's semantics, no matter how many copies of their representation might exist in memory.
You like having a strong separation between the language and its implementation. I get it. Note however that if you are the Haskell compiler, you can know things the programmer cannot, or you can inject code that can perform manipulations the programmer cannot express. There probably is an identity equality operator down there, that people cannot access. If you like that, I can understand; I can understand the appeal for a strict separation of concerns and the desire to express only the high-level intent. But really, I think this is not much different in CL and that you are focusing on implementation details. In CL the separation is not enforced, and that is your main problem with it.
The CL compiler is defined at the language specification level. You have access to internals, by choice, just as if you were writing Haskell ASTs using an Haskell compiler's internal API. As such, you can cross abstraction barriers whenever you need. We already discussed about this once, you can use purely functional data-structures (see FSET) and EQUALP and code to that functional interface and pretend there is no computer down there. Then, if you want, you can play with packages and symbols to make MAP & co. refer to the parallel version (see LPARALLEL), re-compile and have parallel code (this works best with unqualified symbols and different package definitions for the same file).
In all PL discussions, there is eventually mention of an hypothetical sufficiently smart compiler. The CL point of view is (among other things) that such a compiler is one where a programmer can easily add its own extensions. That allows you to express the intent of the program clearly in one place and have the implementation details elsewhere.
Those would be implementation details, not part of the language itself. Hence...
> There probably is an identity equality operator down there, that people cannot access.
... this doesn't make sense.
> You have access to internals, by choice, just as if you were writing Haskell ASTs using an Haskell compiler's internal API.
However, there's no way to portably manipulate compiler internals in Haskell. Heck, Haskell syntax, unlike Lisp syntax, can actually be represented in multiple ways: named variables, de Bruijn indices and levels, HOAS, etc. And this is a good thing.
> In all PL discussions, there is eventually mention of an hypothetical sufficiently smart compiler.
I wouldn't have brought it up myself.
> The CL point of view is (among other things) that such a compiler is one where a programmer can easily add its own extensions.
There's no dichotomy between extensibility and abstraction enforcement, even if you try to set up one.
In order to have an ML, you take a subset of Common Lisp and specialize/extend it in a very specific direction. The part that are removed from Lisp are the one you don't care about. I care about being able to use different equivalence classes, including the ones the compiler is going to require, like identity equality, because this matters when I implement abstractions myself.
> However, there's no way to portably manipulate compiler internals in Haskell.
Yes, why not, that would be damn useful. The alternative is to hack each implementation in its own way.
> Heck, Haskell syntax, unlike Lisp syntax, can actually be represented in multiple ways: [...]
Do you get the difference between internal and external representations? When you see (lambda (a) (+ a 1)), you don't know how the code is represented internally and how its value, when executed, is represented internally (when my compiler performs data-flow analysis, it uses a specific internal representation I don't need to know). Yet, you have access to a uniform API, defined at the language level, to manipulate data. That's why you can have the same source code working on the JVM, interpreted using a C/C++ runtime or directly expressed as assembly. In that sense, there is a separation between the language and its implementation. But part of the language specification is also there to guarantee a uniform way of building new extensions and integrate them with the compiler. That is a good thing. What is not enforced is how and when each feature is used. If that matters, dump a specialized Lisp image that you call the "compiler" and call it with Make on a file expressed in your custom DSL.
> There's no dichotomy between extensibility and abstraction enforcement, even if you try to set up one.
I am not trying to set up one. Just read more carefully.
I'm not talking about representations of semantic objects. I'm talking about representations of syntax. In Lisp's case, you don't get to choose - the macro system critically depends on a particular representation (named variables). Have fun writing macros that operate on HOAS.
Please tell me how Haskell represents HOAS and how this is not possible in Lisp.
Also, read Barzilay's paper (http://scheme2006.cs.uchicago.edu/15-barzilay.pdf), or about the Ergo Project (1988! http://repository.cmu.edu/cgi/viewcontent.cgi?article=2763&c...).
I'm not talking about representing some object language's syntax in Haskell or Lisp. I'm talking about representing Haskell or Lisp's syntax in some other metalanguage (possibly Haskell or Lisp itself). How would you implement a macro expander that operates on HOAS?
> Barzilay's paper (http://scheme2006.cs.uchicago.edu/15-barzilay.pdf)
The object language implemented in that paper isn't the whole of Scheme, and in particular, it doesn't have macros.
> Ergo Project (1988! http://repository.cmu.edu/cgi/viewcontent.cgi?article=2763&c...)
Sorry, I can't find an explicit description of any object language's syntax in this paper.
Hmm, you would expect that HOAS actually be helpful in this area in some ways. Since variables are no longer resolved by matching symbols to binding information in a scoped environment (all we have is direct names references to the binding inserted in the code, or something like that), we don't have hygiene issues when we move code around without having to do any alpha-renaming, or gensyms. It sounds rather convenient, unless we expressly want to do something non-hygienic.
So how would we implement a macro expander? Like we implement anything else: in whatever way that implementation satisfies the specification of macros under HOAS. What is the specification: that is the question. What are HOAS macros, or macros under HOAS?
Not having a formal specification, we might want at least some examples: OK, I have this HOAS artifact, and would like to be able to write it in a more condensed way using this other HOAS: now how to make one into the other? That gives us a function, where we can identify the inputs, which have to be arguments to the macro somehow and so it goes.
Some kind of dual macro system could be useful: a raw source code macro system for doing un-hygienic things, and then a parallel one which kicks in when the code is converted to HOAS.
Agreed. I wouldn't want to do anything non-hygienic, but, from what I can tell, most other macro users aren't exactly very fond of everything being strictly hygienic. It's precisely implementing the unhygienic bits that would be unreasonably hard with HOAS.
(Can't we expand macros in a conventional representation with symbols and environments and then go to HOAS?)
(It's not news that macros are weak in some sense; I mean you can shoot yourself in the foot with the classic non-hygienic ones; you can disrespect even the first order abstract syntax that you're working in: the macro can re-locate a piece of raw syntax which contains identifier references into the wrong scope where those references resolve otherwise.)
Anyway, have fun fishing for mackerel with your bear trap?
How the heck do you handle hierarchical run-time environments in these representations? Especially mutable ones? If we have this:
(let (a b c)
(let (d e f)
(lambda ())) ;; escapes somehow
(let (g h i)
(lambda ()))) ;; ditto
(lambda ())) ;; ditto
So we can't just flatten the entire lexical scope to some HOAS terms and pretend that its hierarchical structure doesn't exist.
The whole point to HOAS is making unbound variables irrepresentable in the first place (which is the source of the accidental variable capture problem), eliminating the need for environments as separate data structures. For example, this is the HOAS representation of closed terms of the untyped lambda calculus:
datatype term = Lam of term -> term
| App of term * term
"Functional programming" doesn't restrict the kinds of obejcts you can work with. An identity value, whose virtue is that it is different from other identities, is a legitimate concept which can be treated under functional programming.
I guess your problem is that you don't want non-symbolic objects from behaving like identities; only symbolic ones.
That is to say, two symbols are equal iff they are actually the same symbol, otherwise not---but other kinds of entities are treated differently.
There is something to be said for having just one kind of equality, which is appropriately defined for every kind of object.
Pragmatic issues get in the way though.
Let's consider "this list [1,2,3]" versus "that list [1,2,3]". What if we have lazy lists (as those things tend to crop up in functional languages, particularly non-strictly evaluated ones). Is "this infinite list [1,2,3, ...]" equal to "that infinite list [1,2,3,...]" even if they are generated by completely separate lazy procedures?
Your equality then has to basically test that two Turing computations are equivalent: that the underlying lazy generation procedures themselves are computing the same thing, even if in different ways.
In that vein, what do you do about structures with cycles and shared structure? Is the list #1=(1 . #1#) equal to another one that is also #1=(1 . #1#). (Lisp's equal functions don't have to handle this; but we could specify an equal function which does).
Equality is not so simple that we can just cover all of its nuances with a blanket rule based on some handwaving principle.
Of course. But I don't want object identities to be the only values I can manipulate. I like having values like the list [1,2,3].
> Your equality then has to basically test that two Turing computations are equivalent: that the underlying lazy generation procedures themselves are computing the same thing, even if in different ways.
Indeed, this means that equality of higher-order values is undecidable. Therefore, don't rely on testing whether higher-order values are equal - you just can't! This is also why laziness by default is such a bad idea.
> In that vein, what do you do about structures with cycles and shared structure?
In Standard ML, `val rec xs = 1 :: xs` simply doesn't compile. The right-hand side of a `val rec` definition must be a function literal. This guarantees that inductive data types (such as lists and trees) mean the right thing, and that structural recursion on them always terminates.
> Equality is not so simple that we can just cover all of its nuances with a blanket rule based on some handwaving principle.
I'm not handwaving anything.
Functional doesn't mean "the semantics of everything is tied to its printed syntax" so that if two things look the same in the syntax, they denote the same thing. (Right?)
Suppose we take Haskell and give it an equal operator which can tell that two bignums are different instances and not equal. Does it cease being functional? What if we don't use that operator anywhere in a program and don't even know it exists; how do we know the language is not functional?
I don't care about syntax. I want to manipulate the values I care about, not object identities. I want to operate on numbers, strings, lists, trees, what have you. Not memory cells that allegedly contain representations of numbers, strings, lists, trees, what have you. This is strictly a semantic issue.
> I don't see how support for multiple equalities makes something not a functional language.
FWIW, what most languages call “physical” or “reference equality” is a special case of structural equality (which is always the prior notion). Structural equality of mutable cells (which have dedicated types in Haskell and ML) happens to be physical equality.
> Suppose we take Haskell and give it an equal operator which can tell that two bignums are different instances and not equal. Does it cease being functional?
Yes.
> What if we don't use that operator anywhere in a program and don't even know it exists; how do we know the language is not functional?
Then you're doing functional programming in a non-functional language.
;-)
If a tree falls in a forest and no one is around to hear it, does it make a sound?
If a program satisfies a property but the compiler cannot prove it, can we still rely on it?
It's very simple: You can rely on what you can prove. This applies both to compiler authors and compiler users. That sometimes one can prove things the other can't shouldn't come off as a surprise. Neither party has all the information: The compiler author doesn't know the intended meaning of the program submitted to the compiler by the user. The user doesn't (need to) know the internal details of how the compiler works.
If you want to use Haskell, use Haskell. Common Lisp works differently.
And today's Common Lisp is definitely not Scheme, or an FP language. You can do FP in CLisp of course, since it's quite capable, but CLisp is a general purpose language and is used as such. And in my small experience from playing with it, there isn't much FP in CLisp, but YMMV.
Lisp in general is a big family. Emacs Lisp for example has absolutely nothing to do with FP.
Of course you can romanticize about Lisp and it definitely has some cool descendants like Clojure, but you know, don't do it too much :-)
A compact definition of functional programming is using only expressions, never statements. This leads to the idea that the effect or meaning of every computation must be encoded in its return value.
[1] Even C has this with Apple's Blocks extension (http://clang.llvm.org/docs/Block-ABI-Apple.html).
As for closures, well, closures are an implementation technique. Not distinguishing between language features and implementation techniques is a part of an established tradition that comes from Lisp, but that doesn't make it any less wrong.
What do you mean by that?
(0) A function maps every element of its domain to a unique element of its codomain.
(1) Functions don't exist in time, let alone change over time.
(2) Two functions with the same domain and codomain are equal if they map the same domain elements to the same codomain elements.
Since when do so-called “first-class functions” in most programming languages behave like this?
More importantly, you cannot make functions in C. For example, one cannot write a function that, given pointers to functions that compute 1/x and sin(x), returns a pointer to a function that returns 1/sin(x)