> In fact it can be argued that lisp is one of the least functional languages ever created
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.
The author very clearly defined what he means by functional, and he is correct, idiomatic Lisp is not. IF being a value-returning expression only encourages functional programming in the author's sense, since functions with conditionals can be written without explicit control flow where you can sneak side effects in. But, to be clear, flow control doesn't affect functional purity, and so it can be said that IF expressions vs. statements don't actually provide more or less functional behavior.
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.
Defining an already used word to mean something precise and then arguing based on that is fine when constrained to a subset of technical readers who are used to this idea (you see this a lot in philosophy papers), but when publishing to a general readership you can't expect people to just accept that.
I would agree with you if the author did not explicitly say what he meant, and assumed the reader knew what he meant, but the author did not make any such assumption.
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.
Maybe to acknowledge that "functional" is used with a different meaning, often, would be sensible rather than just pretending all one needs to do is re-define it from common usage and proceed.
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.
The point here is that the definition in the article is not something new. The author merely chooses to pick an accepted definition of functions, and build from there.
You makd it look like he's trying to push a new definition, which is not true.
> The author very clearly defined what he means by functional, and he is correct, idiomatic Lisp is not.
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.
If you think the author's definition is clear and precise, then Haskell definitely doesn't qualify as functional by that definition, either. E.g., Haskell only encourages writing functions (i.e. total functions), so by that definition it also just encourages functional programming. See my other comment: https://news.ycombinator.com/item?id=13601299
>Returning a value from an (if ...) already makes it more functional than a lot of languages
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.
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.
This is mostly wrong. Lisp is mistermed "functional language" due to schools which teach freshmen some subset of a Lisp dialect which they must use in a pure way to solve homework problems: no variable assignment, no loops. The second thing you hear from people after "functional language" is things like "oh yes Lisp. I remember all the recursion; it was elegant".
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:
The "cond pairs" terminology persists because cond was originally restricted to pairs! Except for the aspect that it evaluated the conditions in left to right order, it was inherently oriented toward handling the cases in functional programming: upon finding a true expression, it evaluated its result counterpart, and yielded that value. In "pure Lisp" programming, cond will still be used that way.
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.
Common Lisp, which the author is referring to, definitely was not organized around functions being pure. Common Lisp actually doesn't have a lot of high-order functions either. A notable exclusion was COMPOSE.
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.
Common Lisp has a functional argument in every library function that takes a :test and/or :key. (Even if these are not specified, they are understood to have functional default values like #'identity and #'eql). And of course apply, mapcar and other applicator friends have a functional arguments. All these things tend to be front-and-center in everyday Lisp programming, hardly "also have" features.
in the functional programming community I find an obsession with these two things
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.
> what mathematicians call functions, programmers call pure functions
Even that's not precise. What mathematicians call computable functions, programmers call total, pure functions, and even then only as an approximation.
> in the functional programming community I find an obsession with... what counts as functional programming (and more specifically "why lang X is not really functional")
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.
As regards your "2." I have often thought that Randall Munroe's approach with "Thing Explainer"[1] would serve (for the rest of us) a number of computer science theory dominated software areas exceedingly well. (how about "monad" using Munroe's strict 1000 word list?[2])
Thing Explainer is good because it is fun to read words which explain a thing that you already mostly understand in a way that you would not usually see. It can also help you see things from a point of view that you wouldn't usually have. However, when used to write about things that you don't already know about, it will probably not make it easier to understand, and may just make it less clear what is being written about.
Monads aren't actually complicated tho, they're just abstracted from reality a bit (unlike, say, object-oriented inheritance). It's much more useful to actually write a few monads yourself than read articles about them.
* 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.
Depends on the lisp. CL is not so functional, it is multi-paradigm. Clojure, however, is mostly functional.
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.
There's a big group of hackers who refer to Common Lisp as "Lisp" or "lisp." I believe Doug Hoyte is doing that. Richard Gabriel and Peter Norvig do it too.
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.
When these people talk about 'Lisp', they mean Lisp 1, Lisp 1.5, Maclisp, Standard Lisp, Emacs Lisp, Lisp Machine Lisp, Common Lisp, ISLisp, Autolisp, ...
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, ...
Well, opinions may vary, but I own this book and the word phenomenal is not appropriate. Most CL hackers I know do not take this book too seriously. It is loaded with pretense and self-congratulatory comments.
Yes, opinions vary. I found LOL very instructive, but maybe I was in just the right place when I discovered it.
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...
Thanks for clarifying. I can see how it would be confusing for someone to be dropped into chapter 5 of the book with a section title like that.
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.
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.
It's certainly possible to write procedural LISP. I'm currently debugging some from the 1980s. It's 1970s-80s style code - too many global variables and little structure larger than the function. At the time, only LISP had dynamic allocation and garbage collection. Today, you could write this code in anything from Javascript to Go.
> The real purpose behind functional programming is to separate the functional description of what should happen from the mechanics of how it actually does happen.
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!
I wouldn't conflate the ideas of declarative programming in FP (somewhat similar to SQL in that regard) with interfaces/protocols in other languages. They may render similarly in English, but that's about it.
No, people claimed that Java was a functional language, prior to actually getting lambdas & all that comes with them, due to [anonymous] inner classes.
Outside of heroic whole program compilation efforts like Stalin (telling hero worship there), Lisp can't optimize programs written in the functional style subset to the degree actual functional languages do.
Maybe we can call Lisp a slow-functional language.
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.
I like to call Lisp "semi-functional" -- it provides better support for the functional style than ordinary imperative languages, particularly if you use FSet [0] (shameless plug), but is still perfectly good for imperative programming when you want to do that.
I think you can achieve Turing completeness without higher order functions, using only primitive recursion. That tells us that whatever can be calculated with the help of higher order functions can be somehow calculated without them, without resorting to destructive manipulation.
You don't need higher order functions, but you do need lexical closures. C only has one stack, so it's a PDA. Strictly less powerful than a TM.
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.
It isn't clear that C is just A PDA. Without any destructive manipulation, C functions can use pointers to pass down and maintain a chain of contexts, so that each function potentially has random access to something at each stack level above it without having to pop anything.
It's not quite that simple. It turns out that you're right, but it's much more challenging than just saying "recurse back up". The problem is that if you're recursing then you're not in the current frame. You can only do a finite number of dereferences from the current frame. That makes every frame effectively a PDA cell.
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.
this function just recurses, decrementing num_levels until it hits zero, and chasing the parent pointers. With that, I have random access all over the stack.
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.
Something like Baker's Cheney on the MTA without actually collecting garbage. The "cheat" is that unbounded stack size implies unbounded pointer sizes, which means no finite alphabet, but "C without pointers" isn't C, and "finite stack/tape" isn't PDA/TM, so I think the "cheat" is fair :-)
So... Is C a functional language? It allows us to pass functions to functions, return them back, storing them in variables and structures, and so on. Looks like C is a functional language.
Not quite. To be a first-class data object you not only need to be able to pass and return them, but you also need to be able to create new ones at run time (i.e. you need to be able to make closures). C can't quite do that. (You can roll your own closures, but it's awkward.) But yes, C is closer to being functional than most people realize.
Haskell's functions are almost always pure, except for some ordained "special" constructs. If we use purity to test whether a language is functional, it would be very disingenuous to not call Haskell "functional" under the purity definition, despite some satellite features it includes.
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.
Haskell's functions may be mostly pure but they're certainly not total, so they're still not the familiar mathematical concept, and therefore would fail the author's definition as well.
Arguing over such definitions is futile and silly, because there's bound to be some approximation, some papering-over at some point.
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.
The author defined what he meant by functional, and by that definition, he is correct.
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.
A calculus is a “formal system”, i.e. a set of rules to do something. The rules of the Lambda Calculus describe computation. Any language that has anonymous functions which behave as closures and can be passed around freely immediately contains an encoding of the lambda calculus. Anonymous functions correspond to lambda expressions, except that in the LC functions always have exactly one argument.
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.
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.