let persons = names
.map(Person.init)
.filter { $0.isValid }
easier to read than this?
var persons: [Person] = []
for name in names {
let person = Person(name: name)
if person.isValid {
persons.append(person)
}
}
I understand and appreciate the value of compact code, but I find the first one harder to read. A lot of inferred/token based coding is harder for me to mentally parse.
I think if the second one is easier, you've more or less been taught to think like a microprocessor. That happens to most of us after a few years of writing imperative code. The more abstract functional approach is, however, conceptually simpler and more powerful at the same time. (For example, the first one is completely open to being performed in parallel.)
With a little experience, functional programming is quite straightforward. Practically everything comes down to map, filter, and fold, or whatever they're called in a given language.
I can't help thinking like a microprocessor. Even when mixing functional style into my code, my brain tries to get a grasp on how it's going to be processed.
So the first example looks to me like two loops (hopefully the compiler does a better job on that), while the second one is obviously one loop.
I am already trying to guess how a compiler would parallelize that...
The second one might be obviously a single loop, but it is not obvious that it is O(n) and depends on the implementation of "append". It also tells you nothing about how the memory gets accessed and I'm assuming here that the for loop works just as well over linked lists and over arrays. In other words your knowledge that this is a single loop can be very misleading when thinking of expected performance. Which is fine because we work with abstractions such that we don't have to think about such details all the time, because that's not doable.
The first example is simply more abstract. It might be a single loop in case the implementation is lazy, it might be two loops in case it is strict. However, look closer. Those filter and map operations can be applied to basically anything you want, including asynchronous / infinite streams.
Your second loop on the other hand would have a hard time being translated to anything else than something that works on finite lists and that builds a finite buffer and not doing anything else while doing this.
Or in other words, your knowledge about this manual loop is not transferable ;-)
As a matter of fact, any implementation of the same algorithm has the same parallelizing possibilities. You just need a smart enough compiler.
But a "smart enough compiler" is what compiler people say when they are talking about their version of the abstract anthropogenic equivalent AI. The fact is that the first one is much easier to parallelize, so that real implementations actually do it, while the second one is not done on practice. And it's easier to parallelize because there are some extra guarantees on the signature of those functions that a for loop does not give.
In the first one, you are simply telling it to map and filter every element. Since you can do that to each element in an independent way and the code is more abstract, the map and filter can be done in parallel without you knowing (I'm not sure if would execute in parallel in Swift, I know that in java you can change the way it does it by using parallel streams).
But in the second example, you are telling it to iterate over each element, sequentially. Since you are telling step by step what needs to be done, it's not parallelizable unless you implement it to be so.
They're both parallelizable, but the second one is harder to automatically parallelize.
There are guarantees about the way a map function works. It doesn't mutate its input, it only has access to one element at a time, you can't access the data structure you're building, etc.
All of these traits are true of the imperative version as well, but it's a lot harder to write a program which understands that. Meanwhile, you know that's how map and filter work, so it's trivially easy to know that those guarantees hold.
I don't think that will happen in Swift, but conceptually there's nothing that stops the compiler from doing it since you're not specifying the order that anything happens. Some Haskell compilers can automate parallelization of the equivalent code. But pragmatically speaking, you can convert code in this style to parallel code without changing the algorithm; for example various "map-reduce" servers are built around the idea of mapping and reducing, which are fundamental concepts of functional programming.
In contrast, in the imperative form, you are specifying how items are appended to a list, which means that any attempt to do it in parallel could change the order of the operations and therefore the order of the result. Sure, a sufficiently smart compiler could in theory figure out what "should" happen and see how to optimize it, but in practice today's smartest compilers can barely handle the functional case.
I find the first one to be far easier to read. You can basically just read it from top to bottom and know exactly what it does. "Take names, turn each one into a Person, keep the ones that are valid."
The second one takes a lot more work. First, I have to read through the code and recognize that this is a loop that accumulates values into a new array. Then I have to pick it apart and see exactly where the accumulation takes place, and how that value is derived. It's not hard by any means, but the first one is far more straightforward.
Two. These methods are not lazy by default. Of course, you have to know the language pretty well to know that, but I do. For anyone wondering, you can write names.lazy.map(...) to get lazy evaluation.
It depends. Using lazy data structures, transducers, or a number of other common tricks would turn it into one loop. Haskell, Clojure, Ruby, Scala, Swift, and many other languages make it pretty easy to do.
But the second one is more debuggable than the first, which I think is even more important than readability.
In the first case, you need to rewrite the control structure to even be able to inspect anything:
let allPersons = names.map(Person.init)
{log allPersons[0].name}
{breakpoint}
let persons = allPersons.filter { $0.isValid }
There are lots of data structures in this style of programming that don't have any names. Who knows what kind of data structures map and filter create in order to do their work. Are we allocating 2 arrays? 1? None? In the procedural style, everything that exists in memory has a name.
It's also totally unclear what the order of operations is. Are Person.init and $0.isValid alternated? Is the `map` run in full before the `filter` starts? No way to know.
People talk shit about procedural programming, as if it's antiquated. But the core promise of functional programming—that you can stop thinking about the underlying procedures—never seems to fully pan out. So when you inevitably need to start digging under the hood to figure out what your declarative code actually means in practice, you end up having to think procedurally anyway. Now you're thinking procedurally, but your code is declarative, and the runtime is trying as hard as it can to prevent you from knowing what's exactly happening moment to moment.
I think there are specific cases where a declarative interface is the right abstraction. CSS is a good example. But these are narrowly defined domains with relatively clear semantics that get frequent use, so the time it takes to learn the semantics will pay off.
The idea of littering your entire codebase thickly with declarative APIs, each of which has unique control structures that must be understood in order to read code, is not a good approach in my opinion.
This is what Rails is, and it creates a situation where you are captive to your tools: you can do a lot very easily, but you cannot stray far beyond the declarations that your library author overlords have chosen for you, or you quickly find yourself in a space where in order to not shoot yourself in the foot you need to have a huge body of internals in your head.
> But the second one is more debuggable than the first, which I think is even more important than readability.
The first is less likely to require debugging in the first place.
> There are lots of data structures in this style of programming that don't have any names.
So you can only reason about things that have names? Now we know where idiomatic Java comes from.
> Who knows what kind of data structures map and filter create in order to do their work.
In most reasonable implementations, the only data structure being created is the final result (a functorial value in map's case, a sequence in filter's case). For example, in SML:
fun map _ nil = nil
| map f (x :: xs) = f x :: map f xs
fun filter _ nil = nil
| filter p (x :: xs) =
if p x then x :: filter p xs
else filter p xs
> But the core promise of functional programming—that you can stop thinking about the underlying procedures—never seems to fully pan out.
Functional programming doesn't promise freedom from procedures. It promises (and delivers) freedom from physical object identities when you only care about logical values.
---
@banachtarski:
Code that's likely to require debugging (say, because it implements tricky algorithms) should be isolated from the rest anyway, regardless of whether your program is written in a functional style or not. Say, in Haskell:
-- Now trickyFunction1 and trickyFunction2 can be
-- tested in isolation. Or whatever.
trickyFunction1 x = ...
trickyFunction2 x = ...
filter trickyFunction1 (map trickyFunction2 xs)
> The first is less likely to require debugging in the first place.
I'm all for functional languages but this scares me a bit. What do you do when you need to debug something and everything ends up being harder to debug but "less likely to need debugging." I've actually run into this situation a number of times and faced with a sea of linked compound expressions, debugging can be a daunting proposition.
It's still a net win in my experience. The minor inconvenience of inserting a few temporary variables to hold intermediate values is much less than the burden of all the additional reading and debugging needed when you spell out every step for everything you want to do.
It's kind of strange to me. We generally acknowledge that not repeating yourself and dividing responsibilities sensibly leads to better code that has fewer bugs and is easier to reason about. And yet when we consider doing the same thing with iteration, we say, "Whoa, hang on. Why can't we just write out the whole thing every time instead of factoring the common bits into a function?"
Comment out all but the first and output the result. If it's what you expected, uncomment next line and output the result. Is it what you expected. Repeat... Debugging is just a specialized form of troubleshooting so the same rules apply. Bring the system to a known good, and increase until you find where it breaks.
You have a ton of these types of statements. Which one do you apply the treatment too? Your approach only allows doing this troubleshooting approach to a single place at a time easily.
> So you can only reason about things that have names?
I think the point was that you can debug things that have names because they are separately watchable.
But apart from that breaking things down and naming them can make for easier comprehension. This is true in written English: Naming actors when explaining something and using an active voice is generally recommended. e.g "The user enters a password and the program encrypts it and stores it in the database" Rather than: "Passwords will be stored encrypted"
But also in mathematics. When working something out it's better to name intermediate values (x,y) and then use them in new equations rather than use the equivalent of a point free style that you sometimes see in functional programs.
You're 100% right about debugability. It's the main reason I don't push to use haskell every day. That said, I think we really need to get clever and think of good tools to debug in spite of these difficulties. Most complex bugs are from interacting systems that can't be found by step debugging. For example, the following code is considered pythonic, and for good reason:
fs = [f(x) for x in xs]
The other commenter's points about being cleaner and less prone to debugging are totally legit. If we can make e.g. list/set comprehensions debuggable, we can probably make other FP idioms debuggable and get the best of both worlds.
Kinda reminds me of microservices, actually. Tough to debug, but good in other ways.
Yes, I find the first one easier to read. It might be me being weird, but I suspect you just haven't built up the instincts to read the first one more quickly. There's no "magic" or anything tricky going on here — it's just a normal use of map and filter. Even good and useful things can seem less readable before you're used to reading them.
With the map, you know, as soon as you see the map that you're making a new list based on an old list. With the for loop, you have to read and understand every single line of the for loop to understand what it's doing.
I find the first example much more intuitive. It declares intent, rather than the mechanics of delivery. And that's where we need to be heading as programmers.
This. So much. Declaring intent (what) is much more useful than declaring the mechanics (how). I don't typically care about the "how", just the "what". And the more readable that is, the better.
It's a matter of habit more than code readability.
Five years ago, I would have found the second form easier to read. These days, not only do I find the first form much clearer but I find the second one a bit smelly because it mutates data.
It's actually surprising how quickly you get used to the first form of code once the language you use supports it.
In this case, it's unfortunate that there's no, "will this name create a valid person object?" predicate. much much better to filter the names, then make the objects.
In this case, as long as append is O(1), i think the imperative version has a big benefit, it avoids building the name size list of persons. If you've got a billion names and 2 valid person objects, the imperative version is a big win. Of course that predicate i mentioned is the right way to go though.
I think the right way to do it is with a fold. But that's not built in, so hard to expect of novices.
I see what you're saying about mutation, i guess i have a higher tolerance for mutating stuff that you have the only reference to. I'm not really sure doing a += [validPerson] is much of a win. (but i think would be the right answer in a fold)
> In this case, it's unfortunate that there's no, "will this name create a valid person object?" predicate. much much better to filter the names, then make the objects.
No "object" is made if the name can't create a "valid person object", it'll return a stack-allocated null/nothing value. That pattern is also much better for concurrency issues.
> much much better to filter the names, then make the objects.
You're just duplicating the validation logic (or worse, the "objects creation" assumes it's given valid names and does no checks)
In Haskell you'd use `mapMaybe :: (a -> Maybe b) -> [a] -> [b]`[0], it's a combined map+filter+map specialised for Maybe (option types). Rust has Iterator::filter_map[1] which does more or less the same thing.
Most languages implement map and filter in terms of lazy sequences so they would not allocate an intermediate list (Scala is an exception but I believe you can request laziness).
hmm, i don't think lazyness is enough. for example, in the billion names example, let's say the first and last elements are valid. at the first step you'll wind up with something like
because the intermediate calculations still need to happen.
getting that first answer is cheap and quick. getting the second answer requires evaluating those billion - 1 thunks.
maybe you're thinking of list fusion? AFAIK, only haskell does that.
Perhaps i'm misunderstanding your point. But even then, lisp, scheme, smalltalk, python and perl don't implement map and filter in a lazy way. Of course, i'm thinking in terms of haskell lazy, perhaps, again, i'm misunderstanding and you mean something else.
In retrospect, i think i'll revise my opinion and say map.filter is probably a bigger code smell than referentially transparent mutation.
I understood from your comment that the imperative version "avoids building the name size list of persons" that you thought the declaritive version would construct an intermediate List[Person] the same size as the source list of names. Most modern languages (e.g. C#, F#, Clojure, Rust) implement map and filter using lazy sequences rather than eagerly constructing intermediate collections (admittedly I don't have much experience with the languages you list).
The use laziness will avoid the need to construct a large intermediate collection of Person instances. Obviously you'll need to iterate the entire source collection to find all valid Persons but the same applies to the imperative version. The lazy version composes better however and avoids extra work if some downstream caller only requires the first n valid Persons.
Even Java manages to get your example to work efficiently with map/filter. It's not rocket science. Just because some library designers screwed it up doesn't invalidate the whole concept.
Not quite. Lazy sequences make it so that thinking about fusion/deforestation makes sense. This is an optimization the compiler can make. Naively, you still end up with as many allocations as before (just in a different order).
In Haskell, this sort of optimization is actually user-customizable using REWRITE RULES. And you get it for lists out of the box.
It helps, for me, that I have more of a math background (academically) than CS (dual majors, but strongly preferred the math coursework).
For me, I see three ways to write, as an example, a summation:
n
Σ g(i)
i=1
vs.
seq(1,n).map(g).sum() // or something similar
vs.
for(i = 1; i < n; i++)
sum = g(i)
In my mind, the first is what I see, and is what shows up on paper. The second is what I want to write (and will in any language that lets me). The third is what I often have to write when a language requires that I be more explicit (like C).
Well I was basing mine on the original. If peopleNamed in fact returns a list, then I'm not really sure what it's doing to create that? (I assumed your example was Haskell, in which case I don't think it can do anything particularly useful)
In any case, all you'd need to add is something like concat.
I think it depends what you're used to. I used to be a Scala programmer, then I moved to JS.
At the moment I'm working in Objective-C, and I literally just wrote a loop to filter an array and form a new array with the results like the one in the example - and god I wish there was an as straight-forward, easily understandable functional way in Obj-C to do it like in the Swift example.
I miss these 'nice' things - I don't need the fully functional Haskell package, but I like having some of the nice things Swift has, just because I got used to them and can actually write and read them better, and it is definitely more elegant!
Personally, I prefer the map/filter approach because people is now a let constant, but I work at a startup with people that don't come from a software development background that would have next to no idea what that line even means. So don't forget your code's target audience, I've personally had to back off some of the more functional styling in Swift just so I'm not the only one that can maintain our code base.
For that reason, I really wish Swift had list comprehensions, just because it's the first "slightly functional" exposure most non-developers get if they come from Python.
I don't think it's THAT difficult to learn to understand functional style programming. I like to think that I would consider trying to show my team mates the joys and positive aspects of functional programming before I just wrote them off, were I in your situation.
I used to find the first example more difficult to read until I learned Haskell. Now I find it much more explicit about what's happening.
In the first example, because I know what "map" means, I know that `Person.init` is applied to each name. And then I know that only the valid `Person`s are returned by the `filter` call.
In the second example, I have to understanding the unique logic of the loop block to get to the same conclusion.
For me it's neutral, except for one critical difference.
I've been shepherding a bunch of front end Javascript tests, and recently had to go through fixing a systemic problem with how we were handling multiple promises.
The broken code didn't look too different from your second example, but the same three people made the same mistake repeatedly, leading to tests that generated empty lists and thus didn't verify anything.
Now, I'm not claiming this is a good pattern of testing. Indeed in all of the straightforward cases I removed the array entirely, and with great relish (especially since it also sped up the tests dramatically). And there are obviously some gaps in their theory of testing that they didn't notice the problem until I pointed it out.
But it did illustrate to me again that there are (alarmingly) a lot of people struggling with basic data manipulation, and if your language supports anything like list comprehensions, I think you should probably get used to using them. It keeps those gaps out, and makes people decompose the problem instead of mashing together a block of conditional code that reads like a Choose Your Own Adventure.
I don't see why either is more difficult. For the functional version, you just need understand the meaning map and filter, and for the imperative version, you need to understand the meaning of for loops and append.
I think part of the answer is that for many functional is a new hotness. The same thing happened with Scala (probably still does). With type inference and functional shortcuts, you can get a lot into one compact space. This is "impressive".
The other thing is that experience brings the ability to track what's going on. The formulation of the answer here is probably new to you. As you get use to this, or Streams for Java, or threading for Clojure, etc, you'll understand it by default.
I found the first one easier to read up until I got to the lambda syntax. Map and Filter are intuitive to me, but I wasn't at all clear what { $0.isValid } was doing.
I definitely hear what you're saying. In this particular case I find the more succinct map/filter a little easier to grok, but as soon as you have a bunch more clauses with some flatMap() and reduce(), the "functional" way can get out of hand quickly. In simple cases, I prefer (Python's) list comprehensions. In more complex cases, I prefer the loop(s).
I find Python's list comprehensions mind-numbing in many simple cases, such as [x for x in xs if some_condition(x)] rather than just xs.filter(some_condition). We're repeating the variable name three times and zero of those times convey any useful information, and we don't find out until the very end of the line that the everything except "[", "]" and "some_condition" was ignorable.
And in cases where a data-deriving loop has so much going on directly in the loop body that it makes map/filter/reduce hard to read, there's very often some refactoring that would improve either version.
This is the one case where python's list comprehension syntax isn't so efficient. Don't worry about it - be consistent and use it nevertheless. It doesn't matter much.
In the cases where x gets also transformed or you do some unpacking the syntax is very efficient and easy to read: [f(y) for x, y in items if g(x)]. Basically it's a poor man's relations programming (think databases). It's brilliant. (And definitely easier to read and write than the Haskell list comprehension syntax).
In this particular case I find the more succinct map/filter a little easier to grok, but as soon as you have a bunch more clauses with some flatMap() and reduce(), the "functional" way can get out of hand quickly.
Funnily enough, I find exactly the opposite: for me, the functional style is significantly easier to work with when things get crazy. I think this is mostly because you tend to be composing recognisable patterns, which in turn means the only custom code you’re writing is the “interesting” parts, like deciding exactly which data to select or exactly how to combine each pair of elements. With lots of loops and conditionals and early exits, I also have to work out whether the code is really doing what it looks like or whether there are edge cases that work differently, and even the “what it looks like” part can wind up scattered across several places in the code that are some distance apart.
Some of the projects I work on do a lot of quite intricate manipulations of complicated data structures. Earlier incarnations were written in Python, but even there I found myself using a functional style for most of these situations as the code base grew in size and complexity. More recently, for various reasons including that one, I’ve been writing this sort of code in Haskell, a language designed for that programming style and therefore cleaner in both syntax and semantics. IMHO, it would be hard to overstate how much easier the newer code is both to write originally and to read, fix and extend later. Possibly the most striking thing is how much shorter the code is: the functional style combined with a language and libraries designed to support it really is remarkably expressive for data crunching work compared to the “longhand” form of writing out all of the loops and conditionals manually.
For me the problem with Haskel (and, by extension, Swift) is the syntax is very complicated. The example above is better taught through a functional language that has almost no syntax like a Lisp.
Haskell's syntax isn't actually that complicated. There are some common functions with operator names that can be hard to read if you're not used to them, but those are library defined. The syntax itself is actually fairly simple.
And incidentally, this would probably be something like (EDIT: made example more realistic):
filter personIsValid (map initPerson names)
in Haskell. Which looks much cleaner than the lisp to me.
Except in these two brief examples, Haskell employs syntactic sugar with hidden semantics that nobody but an acolyte would understand (periods and two kinds of brackets mean what?). At least the Lisp scoping here is explicit and employs minimal abstruse sugar.
I'll admit Lisp's myriad nesting of brackets is not ideal either. But surely there are more elegant and intuitive notations for functional scoping than is seen here.
Lisp provides its own solution to the nesting of parentheses: if you're writing an expression which is too deep, you can invent an ideal syntax which more direclty expresses what you want to say. Then teach Lisp to understand that syntax. Then there is a myriad of parentheses in the macros which implement the syntax; elsewhere, there are fewer parentheses.
Very simple example: once upon a time, in the early 1960's, Lisp only had the COND operator. There was no IF. Programmers often had to make two-way decisions using COND, writing things like (COND (condition then-expr) (T else-expr)). Too many parentheses. So they came up with the IF macro allowing (IF condition then-expr else-expr). This simply expanded to the COND. Six parentheses are reduced to two.
Like most other programmers, Lisp programmers care about not writing mountains of distracting, irrelevant code that is hard to understand. That's why the backquote syntax was invented for instance. Before the backquote syntax, macros were difficult to write.
Say you wanted to transform the syntax (foo bar) into (let ((bar (whatever))) (do-something bar)).
You had to write a macro function which took the object (foo bar) as a single argument, analyzed it, and then constructed the output. Suppose we already have the BAR part of the (foo bar) from in a variable called SYM. Then we have to do something like:
(list 'let (list (list sym '(whatever))) (list 'do-something bar))
;; I'm not going to bother to get this right
With the invention of the backquote, this could be rewritten like this:
`(let ((,sym (whatever))) (do-something ,sym))
A nice template which looks like the output that we want, and indicates the places where we want to stick the variable BAR symbol, held in SYM.
Obviously, backquote templates have parentheses. But the notation itself isn't parentheses; it consists of the backtick syntax, and the commma operator for interpolating values. Also a ,@ operator for splicing lists. In some Lisp dialects, the backtick is transformed into a nested list object. For instance `(a b ,c) might turn into (quasiquote a b (unquote c)) "under the hood".
Lispers also invented destructuring: being able to write the macro with a kind of pattern match for the syntax, so that the elements of the to-be-transformed-form are pulled apart into separate variables.
Lisp is not a finished language. New ideas continue, and new surface syntax like the backquote is not off the table. Usually, Lisp programmers would, I think, prefer that such new syntax integrate into Lisp by not "disturbing" surrounding syntax by involving it in ambiguity. Something tidy and simple that has a big payoff is best.
Lisp programmers are not tone-deaf to notational advantages, and do not regard macros as the one and only way to reduce verbosity.
I'm conducting my own one-man research program into improving Lisp and have come up with some great new ideas.
I have a Lisp dialect which is quite ergonomic, leading to terse programs for everyday "data munging" tasks (and continuing to get better).
No one would ever write the latter, because (\p -> isValid p) is equivalent to isValid.
However you're right that the function names would probably be a little longer in practice, and I've edited my example to reflect that. (But they're not convenience functions, they just have longer names due to Haskell's more limited namespacing)
That you have to put parentheses around expressions does not make the syntax go away in Lisp. The 'has almost no syntax' is mostly a misconception. Syntax in Lisp is provided by special operators (LET, ...) and macros (DEFUN, ...).
Often people assume the relatively simple syntax for s-expressions is the syntax of the programming language Lisp. It isn't. Lisp syntax is defined on top of s-expression.
There is a certain straightforwardness about the second format, because it is general and plain. But at the same time, it could be anything -- it's much harder to tell at a glance that a for loop is a filter than it is to tell that `filter` is a filter.
Pitching in with the sea of other voices: I prefer the first. Vastly.
In fact, while I still have issue reasoning about some aspects of functional programming when writing the code - it is magnitudes easier for me to read, maintain, modify, or extend the code.
I often wish it was only the reading. That may be a matter of getting used to it and there may be pluses to the functional style. But when it comes to using a debugger loops seem to be so much more approachable.
In fairness, the list comprehension would probably be the most "Pythonic" way to do this. The nested iterator might be discouraged (under "explicit is better than implicit," perhaps), so a more Pythonic snippet might look like:
persons = [Person(name) for name in names]
valid_persons = [person for person in persons if person.isValid()]
Take this all with a grain of salt, though -- I haven't spent that much time internalizing classical Pythonicness.
Yo, would be nice to have some functional programming language with decent syntax to program apple machines. Let's call it Dylan to honor the most recent winner of the Nobel prize for literature.
Just kidding. The bottomline of this page and talk is that Swift is still not functional. But you can do cool things with it.
I dunno; I think the bottom line of this page is that functional programming is a set of approaches for solving problems, and some of those approaches can be done in Swift.
Haven't read the article yet, but the problem I find with this attitude generally is that the constraints found in FP are what I find valuable, and what are usually missing from languages which support functional approaches.
My take was that you can solve problems by breaking things down. In functional programming you do so with functions. In Swift you can do so with types.
If they are truly functional programmers, asking them will always return the same referentially transparent answer. Only side-effecting functions would return different answers at different times :-)
The term "functional programming" is overloaded, but I think there's a sensible way to split the term into two halves.
"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.
Actually, both of those families come from lambda calculus, except in different way. Lisp comes from untyped lambda calculus (and adds things like car, cdr and eq on top of it), while Haskell (and ML) comes primarily from typed lambda calculus.
I offer a definition of "functional programming" as "based on semantics of lambda calculus".
Lisp does not come from lambda calculus. Anonymous functions in Lisp get their LAMBDA name from lambda calculus, that's all. MacCarthy admitted that he didn't even understand lambda calculus properly, which is why early Lisp was dynamically scoped: lambdas didn't capture lexical variables. Whereas lambda calculus is lexical. Lexical scoping was adopted in later Lisp dialects and into Common Lisp, making those dialects retroactively related to lambda calculus. (Emacs Lisp shows the traditional behavior of dynamic scoping; therefore it couldn't be said to be related to 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.
I guess you're right, it doesn't come so much from lambda calculus as I claimed, it was more inspired by it. Although to be fair, in the time the Lisp appeared, it was the closest thing (by a wide margin) to lambda calculus. I think it was a valiant effort to bridge the gap in that direction (and the design choices were influenced by the trade off that he also wanted a practical programming language).
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.
Here are some features that the lambda calculus doesn't have: n-ary functions for n other than 1, macros (or any other means to analyze its own syntax), dynamically scoped variables, physical object identities, etc. In the untyped lambda calculus, any two alpha-equivalent terms are internally indistinguishable - in fact, you can even make them externally indistinguishable using a nameless representation of syntax like “de Bruijn indices”.
So much for “Lisp comes from [the] untyped lambda calculus”.
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.
Procedural programming usually does not include the use of higher-order functions, and "function-oriented" here seems proper for Lisp and some styles of Python, with their heavy use of filter/map/apply/parallel-map-reduce etc.
In mathematics a function is a mapping having the property that each input is related to exactly one output. This brings with it certain properties you can rely on. In particular functions themselves are also values that can be passed around as parameters or returned by other functions, hence higher order functions.
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.
The original LISP was influenced by Alonzo Church's lambda calculus, see: https://dl.acm.org/citation.cfm?id=367199 - however if you'll study its history the first Lisps were only experiments and for example they didn't have lexical scoping, but dynamic scoping. The Lisp descendant that made FP doable was Scheme, bringing lexical scoping and call/cc.
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 :-)
It indeed isn't. Here's my litmus test. Is 2^100 always equal to 2^100? Let's ask SBCL:
* (eq (expt 2 100) (expt 2 100))
NIL
Damn object identities, ruining muh equalities.
(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...)
I don't see how support for multiple equalities makes something not a functional language.
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?
> 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?)
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.
Structural equivalence is given by EQUALP and has of course its own limitations (but works with trees, user-defined structs and hash-tables, for example). Of course, if you use the identity comparison, you get different results. I agree CL does not fit your definition of functional programming.
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.
I'm aware of EQUALP. But the problem remains that it's possible to distinguish between supposedly “equal” values. Lisp and Scala are first and foremost object-oriented languages - whatever values you want to manipulate are always subordinate to objects whose physical identity in memory matters in the language's semantics, no matter how irrelevant they might be for your problem domain.
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.
The author of this article did reference a classic treatment, though: John Backus's lecture.
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.
Most people would agree that in functional programming we can pass functions around as first class objects. What we disagree on is the definition of function.
Most languages only have higher-order procedures, not higher-order functions.
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.
A term does not necessarily become meaningless when it applies to a lot of things. "Functional" might be a broad category after all, not the exclusive name of a subset of functional languages. And if your language allows different paradigms, it will be called "functional and imperative and object-oriented... ". At best, if a property is so common that most language have it, it can be assumed to be satisfied by default. As for "procedural", the definition on wikipedia is a little more precise and does not apply to all languages: https://en.wikipedia.org/wiki/Procedural_programming.
It is a bit snarky, but also has a ground truth: pointers to functions aren't functions.
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)
That's not a function, that's a closure. And you can simulate that in C by creating a struct that contains the function pointer and the set of captured data (and then when you invoke the function you pass the struct to it as a parameter).
I would call a language like Haskell "purely functional" and a language like OCaml "impurely functional". A functional programming language to me is a programming language where functions are in charge of data. In a language like Java, data is in charge of functions (broadly speaking). In a language like Prolog, relations are in charge of data. It's all about what perspective the programmer has between the abstraction and the data.
You have it backwards. In Java, collections of procedures (aka objects) are in charge of data. In Haskell and OCaml, data exists independently of the procedures that will operate on it.
The talk discusses how you can incorporate a few functional techniques (map, filter) but the speaker's main goal seems that he wants Swift to be changed to allow for a couple of other functional ideas to be brought into the language.
Where's the Swift proposal for the enhancements? Product and Sum support? Algebraic data types?
There seem to be a lot of "pretend" functional languages around these days. I have recently been engaging with Scala. Having heard and read so much about how it embraces functional style I was kind of shocked to find the number of limitations and practical impediments to actually using it that way. I am starting to wonder if functional programming has finally fallen victim to the same problem that has afflicted all other methodologies - becoming too popular, part of the hype cycle and getting misinterpreted and misapplied everywhere as a consequence.
I didn't mean that the language itself isn't functional - it certainly wants to be. But when I tried to naively apply it using the idiomatic constructs that I found online I got a lot of performance and memory issues. In fact some code that I wrote in Groovy (which I thought would be slow) was much faster than the naive port I did to Scala (which is commonly said to hit nearly native java speed). When I dug into those by profiling it turned out that I needed to have a deep understanding of how the compiler was treating Scala constructs to avoid performance pitfalls. A good example is here:
Another is that I've almost never managed to use recursion in my algorithms because Scala seems to have very limited ability to successfully optimize tail recursive calls.
Another problem is all kinds of unexpected boxing, unboxing, and implicit conversions of collections that I wasn't expecting.
Again - all the language features are there, just in practice it isn't working out for me very well when I try to use them idiomatically. I'm still learning. But I also learned Haskell and the experience was very different - once I figured out the idiomatic way to do something it usually was also well optimized.
ML sits somewhere in between Scala and Haskell. Like Haskell, ML has typed mutable data (`foo` and `foo ref` are different types). Like Scala, ML doesn't distinguish between effectful and effect-free procedures.
Scala is similar to Lisp and other higher-order-but-not-quite-functional languages in that it's littered with unwanted object identities. All you need to do is use the `eq` method to see when two “equal” objects are really not the same.
This sounds pretty misinformed. There are plenty of choices in between Scala and Haskell; Clojure and Elixir are two other relatively popular languages that come to mind.
You might have fallen victim to misinformation yourself.
In general, functional programming in Scala tends to be more FP, with code tending to be more pure than in Clojure and I have no experience with Elixir, but I have some experience with Erlang and FP code in Scala tends to be held at a higher standard than in Erlang.
Of course, you've picked 2 dynamic languages as examples and FP in dynamic languages is different than that practiced in static languages like Haskell or Scala. LISP developers for example don't think so much about monads or other abstractions with mathematical foundations, because LISP developers tend to work around such needs by doing macros (which then have composability problems) or by bending the rules a little, or in other words I've seen no LISP to make a serious attempt at reasoning about I/O in a pure way.
And IMO code in static languages tends to be more pure because of the types, because by having an expressive type system, the developers then want that type system to explain everything. Or in other words, dynamic languages are cool for your day job, but if you want to actually feel what FP is all about, you're better off going for a static languages like Haskell, or even Scala or OCaml.
Thanks for your reply, I think this is a matter of interpretation of what functional actually means. I personally consider the fact that Scala allows you to get away with immutability so easily (as evidenced with the implementation of all the immutable collections) a very bad thing. It might be just a matter of taste, though; Scala was my gateway drug to functional programming, and I considered implicit parameters and all these immutable containers something very un-functional.
You cannot get away with these things as easily in the Erlang VM (and thus Elixir). I agree with your assessment that Clojure with its macros is an ugly hack, and requires discipline to get right.
Having said that, Haskell also takes a lot of discipline to get right (no lazy I/O, for example), and allows you to get away with ugly things as well (unsafePerformIO). The type system makes it a lot easier to get right though (or in other words, more difficult to do the wrong thing).