20 ms·

Lisp is not functional (2010)

67 points by saint-loup 10y ago

kazinator 10y ago
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: (cond (this-condition do-this and-do-this yield-this-value) ;; triplet, not pair (that-condition do-that and-do-that yield-that-value) ...) 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.
- reikonomusha 10y ago
  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.
  - lispm 10y ago
    Lisp I of 1960 had SET and SETQ. It wasn't pure.
  - kazinator 10y ago
    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.
    - nitroll 10y ago
      Having higher order functions is not really what makes a language functional.
metaphorm 10y ago
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.
- svachalek 10y ago
  TL;DR what mathematicians call functions, programmers call pure functions, and nobody told the author. It's like someone saying to a scientist, "that's just a theory, man."
  - reikonomusha 10y ago
    The author used, more or less, a mathematician's definition.
  - pron 10y ago
    > 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.
- stcredzero 10y ago
  1. what counts as 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.
- theophrastus 10y ago
  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]) [1] https://xkcd.com/thing-explainer/ https://xkcd.com/thing-explainer/ [2] http://splasho.com/upgoer5/phpspellcheck/dictionaries/1000.dicin http://splasho.com/upgoer5/phpspellcheck/dictionaries/1000.d...
oppositelock 10y ago
Articles like this really make me think of the No True Scotsman fallacy. https://en.wikipedia.org/wiki/No_true_Scotsman https://en.wikipedia.org/wiki/No_true_Scotsman 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_duke 10y ago
  Would you care to counter the arguments the article brings up, then?
  - weatherlight 10y ago
    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.
- reikonomusha 10y ago
  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.
  - jedimastert 10y ago
    I suppose, then, it's a bit closer to moving the target
lngnmn 10y ago
Practicality beats purity. 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.
Animats 10y ago
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.
- dang 10y ago
  What program are you debugging?
  - Animats 10y ago
    https://github.com/John-Nagle/pasv/tree/master/src/CPC4 https://github.com/John-Nagle/pasv/tree/master/src/CPC4
hellofunk 10y ago
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.
- delish 10y ago
  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.
  - hellofunk 10y ago
    And there's a big group of academics, nearly all of them, that refer to lisp as a family of languages with many dialects.
    - iak8god 10y ago
      > And there's a big group of academics, nearly all of them, that refer to lisp as a family of languages with many dialects. Certainly Doug Hoyte, the author of this phenomenal ~400 page book on Common Lisp programming, is aware of that.
      - hellofunk 10y ago
        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.
        iak8god 10y ago
orthecreedence 10y ago
> 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.
- reikonomusha 10y ago
  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.
  - eikenberry 10y ago
    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.
    - reikonomusha 10y ago
      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.
amelius 10y ago
Title should be: "Lisp is not purely functional".
javajosh 10y ago
> 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!
- macintux 10y ago
  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.
- aassddffasdf 10y ago
  No, people claimed that Java was a functional language, prior to actually getting lambdas & all that comes with them, due to [anonymous] inner classes.
  - bbcbasic 10y ago
    The goalposts keep moving.
ww520 10y ago
Lisp is certainly functional. If exclusively pure function is the litmus test for functional language, then most languages including Haskell are not functional.
- reikonomusha 10y ago
  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.
  - pron 10y ago
    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.
pron 10y ago
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. [1]: http://www.paultaylor.eu/stable/prot.pdf http://www.paultaylor.eu/stable/prot.pdf
lisper 10y ago
This is complete and utter hogwash. > 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.
- ScottBurson 10y ago
  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. [0] https://github.com/slburson/fset https://github.com/slburson/fset
- ordu 10y ago
  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.
  - lisper 10y ago
    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.
- kazinator 10y ago
  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.
jegutman 10y ago
That's some nerdy click-bait there.
paulddraper 10y ago
By Haskell standards, the C language is functional http://conal.net/blog/posts/the-c-language-is-purely-functional http://conal.net/blog/posts/the-c-language-is-purely-functio... (pointing out why rigorous classification is silly)
DonHopkins 10y ago
Lisp is fun.
lispm 10y ago
I use usually this classification: * 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.
cronjobber 10y ago
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.
- kazinator 10y ago
  Well, perhaps strictly evaluated functional languages.

67 points by saint-loup 10y ago

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: (cond (this-condition do-this and-do-this yield-this-value) ;; triplet, not pair (that-condition do-that and-do-that yield-that-value) ...) 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.

reikonomusha 10y ago
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.
- lispm 10y ago
  Lisp I of 1960 had SET and SETQ. It wasn't pure.
- kazinator 10y ago
  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.
  - nitroll 10y ago
    Having higher order functions is not really what makes a language functional.

metaphorm 10y ago

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.

svachalek 10y ago
TL;DR what mathematicians call functions, programmers call pure functions, and nobody told the author. It's like someone saying to a scientist, "that's just a theory, man."
- reikonomusha 10y ago
  The author used, more or less, a mathematician's definition.
- pron 10y ago
  > 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.
stcredzero 10y ago
1. what counts as 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.
theophrastus 10y ago
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]) [1] https://xkcd.com/thing-explainer/ https://xkcd.com/thing-explainer/ [2] http://splasho.com/upgoer5/phpspellcheck/dictionaries/1000.dicin http://splasho.com/upgoer5/phpspellcheck/dictionaries/1000.d...

oppositelock 10y ago

Articles like this really make me think of the No True Scotsman fallacy. https://en.wikipedia.org/wiki/No_true_Scotsman https://en.wikipedia.org/wiki/No_true_Scotsman 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_duke 10y ago
Would you care to counter the arguments the article brings up, then?
- weatherlight 10y ago
  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.
reikonomusha 10y ago
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.
- jedimastert 10y ago
  I suppose, then, it's a bit closer to moving the target

lngnmn 10y ago

Practicality beats purity. 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.

Animats 10y ago

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.

dang 10y ago
What program are you debugging?
- Animats 10y ago
  https://github.com/John-Nagle/pasv/tree/master/src/CPC4 https://github.com/John-Nagle/pasv/tree/master/src/CPC4

hellofunk 10y ago

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.

delish 10y ago
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.
- hellofunk 10y ago
  And there's a big group of academics, nearly all of them, that refer to lisp as a family of languages with many dialects.
  - iak8god 10y ago
    > And there's a big group of academics, nearly all of them, that refer to lisp as a family of languages with many dialects. Certainly Doug Hoyte, the author of this phenomenal ~400 page book on Common Lisp programming, is aware of that.
    - hellofunk 10y ago
      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.
      - iak8god 10y ago

orthecreedence 10y ago

> 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.

reikonomusha 10y ago
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.
- eikenberry 10y ago
  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.
  - reikonomusha 10y ago
    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.

amelius 10y ago

Title should be: "Lisp is not purely functional".

javajosh 10y ago

> 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!

macintux 10y ago
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.
aassddffasdf 10y ago
No, people claimed that Java was a functional language, prior to actually getting lambdas & all that comes with them, due to [anonymous] inner classes.
- bbcbasic 10y ago
  The goalposts keep moving.

ww520 10y ago

Lisp is certainly functional. If exclusively pure function is the litmus test for functional language, then most languages including Haskell are not functional.

reikonomusha 10y ago
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.
- pron 10y ago
  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.

pron 10y ago

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. [1]: http://www.paultaylor.eu/stable/prot.pdf http://www.paultaylor.eu/stable/prot.pdf

lisper 10y ago

This is complete and utter hogwash. > 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.

ScottBurson 10y ago
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. [0] https://github.com/slburson/fset https://github.com/slburson/fset
ordu 10y ago
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.
- lisper 10y ago
  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.
kazinator 10y ago
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.

jegutman 10y ago

That's some nerdy click-bait there.

paulddraper 10y ago

By Haskell standards, the C language is functional http://conal.net/blog/posts/the-c-language-is-purely-functional http://conal.net/blog/posts/the-c-language-is-purely-functio... (pointing out why rigorous classification is silly)

DonHopkins 10y ago

Lisp is fun.

lispm 10y ago

I use usually this classification: * 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.

cronjobber 10y ago

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.

kazinator 10y ago
Well, perhaps strictly evaluated functional languages.