Lisp is not functional (2010)
letoverlambda.com
letoverlambda.com
Come on. Returning a value from an (if ...) already makes it more functional than a lot of languages. Sure, it's not functional in the sense Haskell is functional, but you could certainly write all your code in a functional manner using it, abstracting out any side effects via macros. I would say it's fairly well-geared towards functional programming if one was determined to use it for such a thing.
That said, I wouldn't call lisp a "functional" language. I'd call it multi-purpose. It CAN be functional, it CAN be imperative, it CAN be object-oriented.
It's certainly not the least functional language ever created though.
With side effects rife within Lisp's standard library, and with things like dynamic variables included with the language, I have a difficult time believing that it would be easy to "abstract out" side effects with some macros, while simultaneously providing a convenient, broad set of capabilities to program with. At that point, you might as well use macros to compile a whole new DSL within Lisp.
In order to quell the issue of "functional" having many definitions, the author chose one, and wrote about it. I don't see your alternative, which seems to be "accept that functional means something different and write about that", as one that is worthwhile to pursue.
People are not compilers. If you want to redefine a word that is already in your readers' vocabulary with a meaning ascribed you've kind of got to talk about why you're doing that and why your redefinition is worthwhile and the alternative, generally accepted meaning needs to be jettisoned. Or you risk unintentional impersonation of a crank, which would be a shame if you're actually correct.
You makd it look like he's trying to push a new definition, which is not true.
But if the definition is the author's own special definition, the conclusion may be true and still be completely uninteresting. The standard definition is the standard one for a reason - it turns out to be useful for having meaningful conversations about the issue.
But even if you accept the author's definition, then you run into:
> In fact it can be argued that lisp is one of the least functional languages ever created
For that to be true, "one of the least functional languages ever created" must be a really large set. That set must include, say, 95% of all languages ever created - which makes the claim not a very meaningful statement.
I am more used to thinking of it in terms of having function values (closures), but I think you could argue the lexical scoping that leads to SSA is all that's necessary once you have closures.
In any case, the vast majority of the lisp code I've read has been imperative and non-functional.
Like which? Pretty much every language has a ternary operator. Lisp's IF is not a function, by the way. A truly functional IF would have to wrap THEN and ELSE clause in lambdas so that all arguments can be evaluated before deciding which one of them to execute.
Lisp is in fact organized around the idea of a function being a pure function and it was that way from the beginning.
This is why the sequential execution of forms with side effects has dedicated macros/operators with names like prog and progn. These provide "the program feature": giving step by step procedural instructions that tell the machine what to do, rather than an expression which computes a value. The only reason to use (progn x1 x2 ... y) is that x1 x2 ... have side effects. If they only compute values that are discarded, the whole thing may be optimized down to just y.
Also, there is a funny quirk in the terminology whereby Lisp people still refer to the arguments of cond as being "cond pairs", even though you can write procedural bodies consisting of multiple forms, and it has been that way for decades:
(cond
(this-condition do-this and-do-this yield-this-value) ;; triplet, not pair
(that-condition do-that and-do-that yield-that-value)
...)
Of course, even ancient Lisp had rplaca and rplacd to mutate conses, and set and setq to mutate variables. The 1960 Lisp 1.5 manual describes arrays (indexed from zero (damn it!) and mutable).
Calling Lisp "least functional" is completely silly, since it was the first tool which enabled computer scientists to translate pure recursion on paper directly into executable code. There are countless languages which might take such a title, by virtue of having no support for functional programming.
McCarthy's original Lisp was organized around purity, but that preceded Common Lisp by many decades. And, while some names carried over from the original Lisp, Common Lisp had no intention to replicate all of the intents and virtues of McCarthy's Lisp. Even before CL was made, millions of lines of application code had been written in a number of dialects, which had nothing to do with translating math or anything like that.
1. what counts as functional programming (and more specifically "why lang X is not really functional")
2. inventing new jargon, particularly in cases where existing terminology is mostly adequate, but some hair-splitting detail is not properly covered by a word already in use. this tendency might be a natural consequence of spending all day on macro expansions.
It's like someone saying to a scientist, "that's just a theory, man."
Even that's not precise. What mathematicians call computable functions, programmers call total, pure functions, and even then only as an approximation.
Funny, but OO people did something like that too.
2. inventing new jargon, particularly in cases where existing terminology is mostly adequate
Many programmers are guilty of this, particularly if they are young. Once you've been around a few decades, you start seeing this pattern.
[1] https://xkcd.com/thing-explainer/
[2] http://splasho.com/upgoer5/phpspellcheck/dictionaries/1000.d...
It always disappoints me when I read such things; it turns FP into a moving goalpost or a mirage. If you really like FP and want it to be more widely adopted, an approach of encouragement, "steps in the right direction", etc. will do more good than "holier than thou" scorn.
I've tried to follow this attitude when e.g. discussing on HN and answering on Stack Overflow; I wrote up some of my longer FP descriptions into a blog post at http://chriswarbo.net/blog/2015-01-18-learning_functional_pr...
* a language enables functional programming: maybe Python, Java 8, ...
Provides some functional programming constructs like lexical closures, but the main programming style is something else.
* a language supports functional programming: Lisp, ...
Has a lot of support for functional programming (closures, higher order functions, ...) and the library/software is using it extensively. One can develop in a mostly functional subset.
* a language enforces functional programming: Miranda, Haskell, SML, ...
Most of the language organised around functional programming including all of its library and code. It's the dominant paradigm.
The complexities surrounding state in CL are not unlike any other non-functional language. I find it hard to call a language functional if it doesn't strongly encourage immutability (or require it) and, preferably, have persistent data structures.
It's for these two reasons that I don't think Swift is functional, and I don't consider CL to be functional.
They might say, "Clojure is a lisp," but when referring to "Lisp" (i.e. without an article "a" or "the") they're talking about CL.
Certainly Doug Hoyte, the author of this phenomenal ~400 page book on Common Lisp programming, is aware of that.
In any case, what I was responding to in your earlier comment was the implication (I thought) that Hoyte doesn't understand "lisp as a family of languages with many dialects." But since you've read LOL, that cannot have been your point...
Common Lisp hackers may use "Lisp" colloquially as a shorthand for the language they're working with ("Common Lisp" is a bit of a mouthful, after all), but I don't think many of them are confused about the existence and nature of other lisps, or that they tend to disagree with academics on this.
All these languages are somewhat compatible with the original Lisp 1.
Then there is the wider Lisp family which includes Scheme, Dylan, Clojure, ECMAScript, Racket, SKILL, Hop, Logo, ...
Without setcar! setcdr! and friends R4RS Scheme is functional, and with these it is mostly-functional, which is good-enough.
Racket, BTW, evolved mcons to make this distinction explicit.
Common Lisp, obviously, cannot be called functional, but it is trivial to derive a good-enough mostly-functional subset of Common Lisp. Actually, CL, being a kitchen sink for many dialects of Lisp, notably the one from Symbolics, cannot be as balanced and refined as early Schemes used to be, because it incorporates lots of "destructive" primitive procedures, without marking them explicitly in any standardized way or packaging them in a separate package, which, arguably, would make writing a mostly-functional CL code much easier.
http://conal.net/blog/posts/the-c-language-is-purely-functio...
(pointing out why rigorous classification is silly)
I found this statement entirely fascinating, as it reminds me of the definition and motivation of interface in Java and many other languages. And no-one has ever claimed Java to be a functional language because of interfaces!
Maybe we can call Lisp a slow-functional language.
> Clearly lisp procedures are not functions
Some are. Others are not.
The only thing a language needs to be legitimately called a functional language is for functions to be first-class data objects. It's helpful but not necessary for them to be lexically scoped. It is also helpful but not necessary to have a conditional expression. Common Lisp has all of these things. In fact, Common Lisp has all of the features commonly associated with modern functional languages except static type inference (and you can add that if you really want it).
Common Lisp is not a purely functional language, but that's true of pretty much every language except Haskell.
This is the reason lexical closures are so important. They are what let you "allocate" an infinite amount of memory so you can be Turing-complete without side-effects.
Sure
> so it's a PDA.
Wrong
Now, that is not a proof (yet) because there's an additional wrinkle: pointer dereferencing lets you reach an arbitrary distance back up the stack in a single step, and that might be the thing that takes you from PDA-land into TM-land. But you only have a finite number of pointers in the current frame, and each of those can only be dereferenced a finite number of times in the current frame and so this is equivalent to just having a local copy of that finite amount of information in the current frame and so you're still a PDA.
Now, it turns out that argument is actually wrong. But figuring out why it's wrong is not so easy. It makes an interesting exercise writing an emulator for a two-stack machine in purely functional C. But you're right, it can be done.
get_data_from_stack(parent_pointer, num_levels);
Of course, C is ultimately a finite state machine because pointers have a fixed width. "sizeof pointer" is a constant expression. The absolute number of objects which can be addressed is finite. In an abstract program which doesn't use sizeof on pointers or work with their internal representation in any way, we can relax this model to allow an unlimited space; we just understand that we can have as many stack frames as we want and that somehow, the & operator in any one of them produces unique pointers.
> Of course, C is ultimately a finite state machine because pointers have a fixed width.
Yes, but I'm willing to let that slide as long as you never do anything with a pointer but dereference one or compare two of them to see if they're equal (because you have to assume that to make any interesting computational model Turing-complete). But I'm not willing to let num_levels slide. If num_levels has a fixed width (and in C it would have to unless you show me how to build a purely functional bignum library) this solution won't work.
It really is not trivial to figure out how to make this work.
If exclusively pure function is the litmus test for functional language, then most languages including Haskell are not functional.
The telling sign of this fact is that you can actually use equational reasoning and substitution as a method to prove statements about your Haskell programs.
Let's start with the author's definition of functional programming, a functional language is a programming language made up of functions, and let's say we agree. Now, what is a function? The author addresses that, too: A function is a concept from math that has been with us for centuries: A function is a static(??), well-defined mapping from input values to output values. The first, and relatively minor, problem here is what one means by "well-defined". Usually, precise definitions are given in a specific formalism, and different formalisms have different definitions of a function. For example, the classical definition of a function is the set-theoretic one, which says that a function is a (usually infinite) set of ordered pairs, i.e., a relation, with the property of being single-valued. This set is sometimes called the graph of the function. Obviously, finite computers can't store such infinite structures, and so they can't represent functions in the classical sense. Functional languages usually define functions as algorithms, allowing to represent a subset of the classical function called the computable, or constructive functions. Those functions also correspond to (some) classical functions, so this is indeed a minor issue.
The problem is that programming languages don't even define constructive functions. For example, the function of the square root is computable, but it (at least its real-valued version) is only defined on the nonnegative reals (let's not worry about representing the reals for now). Another example is the maximum function over a set of naturals, which is only defined for finite sets (and a maximum function over sets of integers is even more complicated). However, most programming languages, even the functional ones, allow their "functions" to be applied to objects outside their domain, something that does not make sense. So functional programming languages call their "functions" partial functions, but partial functions, unlike classical or even constructive functions, are no longer the same well-known mathematical object. So in Haskell, for example, sqrt and max are not functions of the familiar kind, and neither are log, div and many other "mathematical" "functions". Ironically, it is C that treats some functions (such as division) most similarly to math by declaring that division by zero is undefined, i.e., doesn't have to mean anything. Of course, meaningless in math is very different from meaningless in programming, as a program will have some observable behavior even ruled meaningless.
Next, we can restrict our programming language to actual computable mathematical functions, sometimes called in the programming community total functions (to distinguish them from partial functions). Instead of declaring, like in C or in math, that a program that compiles may mean nothing, and instead of specifying a meaningful yet very unmathematical behavior, we can forbid meaningless things (like applying a function to an argument outside its domain) from being accepted as a well-formed program. This is possible, at least in principle, in several ways, one of them (probably not the most convenient) is with dependent types. But doing so is still problematic. For one, if a programming language only allows total functions, the programmer must prove to the language that the argument is indeed in the function's domain. This can be very, very hard (undecidable in general), and part of the reason why no such language is actually used to produce real software (with a couple of minor exceptions that only prove the rule). The other problem is that even then, the objects called functions in the programming language only represent mathematical functions as an approximate denotation, as they really express computations, and computations are not functions -- they are processes that consume time and memory.
To demonstrate the difficulty further, consider that in math, two functions are equal iff their mapping is the same. In those total functional languages this is not necessarily the case, and there are different kinds of equality.
So if you want to be mathematically precise, you can never really program with functions, or at least not the familiar mathematical function. At some point in the definition of "functional" -- whatever definition you use -- you're going to have to make some concessions and approximations. I think that it is well accepted by now that "functional" is a spectrum, and one that includes Lisp.
A short and nice discussion of this can be found in section 1.1 of Jean-Yves Girard's Proofs and Types[1]. I don't think anyone can accuse Girard of not knowing what functions and functional programming are.
Yes, compared to pure lambda calculus, lisp is not purely functional. In the space of programming languages, it's a functional programming language more so than any other kind.
A program is usually said to be functional when it uses some concepts of functional programming, such as first-class functions and higher-order functions. However, a first-class function may use techniques from the imperative paradigm, such as arrays or input/output methods are not purely functional programs, therefore the first-class function needs not be purely functional. Lisp is an "impure" functional language by the current definition.
However, The main article is absurd. Lisp may not be a "Pure" functional language but it is a still a functional language.
If you change the definition of "functional" to "a language with first class functions and stateful closures", as you seem to implicitly want, then yes, Lisp is functional.