Swift and the Legacy of Functional Programming(realm.io)
realm.io
Swift and the Legacy of Functional Programming
https://realm.io/news/tryswift-rob-napier-swift-legacy-functional-programming/
181 comments
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.
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...
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 ;-)
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 ;-)
Excuse my ignorance but why is the first one parallelizable but not the second?
Maybe we aren't speaking the same language, but I never mentioned parallelism in my text.
We could talk about why the first example could be parallelized of course, but that's not what I wanted to talk about and you missed the point ;-)
We could talk about why the first example could be parallelized of course, but that's not what I wanted to talk about and you missed the point ;-)
Actually, I responded to the wrong post. I meant to post my reply to svachalek.
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.
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.
As a matter of fact loops that mutate state are not parallelizable because you can't analyze what they do in order to infer intent and thus some imposed ordering with which you could efficiently distribute the required work while at the same time guaranteeing correctness - solve that and you'd solve the Halting problem ;-)
Can't be done.
Can't be done.
Well, you can't solve it in the general case. But parallelizing compilers can and have been written that perform a conservative analysis -- they can prove some subset of all parallelizable loops as parallelizable, and for the ones they can't prove as such, they err toward 'remain serialized'.
For a simple example, code that performs regular array-based accesses, where index computations are simple affine functions (a*i + b) of a single iteration variable 'i', is a case that's received a lot of attention. See e.g. Polly for LLVM.
For a simple example, code that performs regular array-based accesses, where index computations are simple affine functions (a*i + b) of a single iteration variable 'i', is a case that's received a lot of attention. See e.g. Polly for LLVM.
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.
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.
Put another way, the first example is about data flow. The required value is specified declaratively, in the form of an expression.
The second example is about control flow. The required behaviour is specified imperatively, in the form of a statements to be executed in a defined order, and the combined effect of those statements is to update the list until it has the required value.
In the second case, the programmer specifies more details explicitly. In this case, those extra details probably aren’t helping, but the optimiser still has to prove that transforming the control flow (for example, into a parallelised form) really will give the same observable behaviour. In the first case, the optimiser doesn’t have to prove the things the programmer never specified anyway, so it has more latitude in how it implements the underlying computation.
The second example is about control flow. The required behaviour is specified imperatively, in the form of a statements to be executed in a defined order, and the combined effect of those statements is to update the list until it has the required value.
In the second case, the programmer specifies more details explicitly. In this case, those extra details probably aren’t helping, but the optimiser still has to prove that transforming the control flow (for example, into a parallelised form) really will give the same observable behaviour. In the first case, the optimiser doesn’t have to prove the things the programmer never specified anyway, so it has more latitude in how it implements the underlying computation.
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.
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.
> For example, the first one is completely open to being performed in parallel
So what do you actually have to do to make this actually run in parallel? Or do you truly get it automatically?
So what do you actually have to do to make this actually run in parallel? Or do you truly get it automatically?
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.
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.
Don't know about Swift, but in Haskell you substitute parallel versions of map and filter that are guaranteed to mean the same thing.
Hence why "structure and interpretation of computer programs" is a very important read.
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.
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.
Is the first one two loops or one?
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.
The real answer is that it doesn't matter. Just like for most code, the output assembly or machine code doesn't matter.
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.
Naïvely, two. The compiler can probably figure out that the semantics are the same and choose depending on what its model says will be faster.
I think the readability is a bit of a wash.
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:
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.
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 }
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:
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:
Bad:
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
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:
Bad:
filter (\x -> tricky_logic_1) $
map (\x -> tricky_logic_2) $ xs
-- 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.
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?"
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.
How do you debug several places at the same time?
You have a ton of those statements, that's why you organize them in functions, and go debugging high level functions before you go into lower level ones, and then into atomic statements.
Anyway, you'll almost certainly want to do that in an repl. I don't know if swift supports one, if not that would be a real drawback.
You have a ton of those statements, that's why you organize them in functions, and go debugging high level functions before you go into lower level ones, and then into atomic statements.
Anyway, you'll almost certainly want to do that in an repl. I don't know if swift supports one, if not that would be a real drawback.
They do, it's really slick how well they have it integrated.
> 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.
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.
> I think the point was that you can debug things that have names because they are separately watchable.
Note I said “reason”, not “debug”. When manipulating algebraic expressions, I don't need to give every subexpression a name - that would be torture!
Note I said “reason”, not “debug”. When manipulating algebraic expressions, I don't need to give every subexpression a name - that would be torture!
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:
Kinda reminds me of microservices, actually. Tough to debug, but good in other ways.
fs = [f(x) for x in xs]
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.
And the source code comments are the why.
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.
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, 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)
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)
> You're just duplicating the validation logic (or worse, the "objects creation" assumes it's given valid names and does no checks)
I think the right way to do it is with a fold.
I think the right way to do it is with a fold.
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.
[0] http://hackage.haskell.org/package/base-4.9.0.0/docs/Data-Ma...
[1] https://doc.rust-lang.org/std/iter/trait.Iterator.html#metho...
[0] http://hackage.haskell.org/package/base-4.9.0.0/docs/Data-Ma...
[1] https://doc.rust-lang.org/std/iter/trait.Iterator.html#metho...
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
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.
validPerson : thunk
validPerson : invalid : invalid : invalid : ... : thunk
validPerson : invalid : ... : validPerson
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.
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.
Oh! yes. Yes we're on the same page as far as laziness goes. The lazy version will only construct as much of the intermediate list as you need to get the next answer, and potentially the garbage collector can reclaim the parts of the intermediate list that have already gone past.
But, there's already a good clean functional composable answer to this kind of thing,
fold takes an operation (like map does) a list (like map does) and an accumulator for building up results, and it returns the resulting accumulator.
the op would look something like
Map forces you to build the intermediate representation, which the imperative version avoids.
But, there's already a good clean functional composable answer to this kind of thing,
fold takes an operation (like map does) a list (like map does) and an accumulator for building up results, and it returns the resulting accumulator.
foldl(op, names, acc){
if(names.empty)
return acc
else
foldl(op, names.tail, op(names.head, acc)
}
the op would look something like
op(name, acc){
let p = Person.init(name)
if(p.isValid)
return acc += [p]
else
return acc
}
Map forces you to build the intermediate representation, which the imperative version avoids.
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.
but java provides collect. which is, like, the right way to do it.
I'm just sort of mystified that people are defending map.filter over filter.map (which isn't crazy, as name.isValidPerson isn't provided.) but, you know, fold is a thing.
I'm just sort of mystified that people are defending map.filter over filter.map (which isn't crazy, as name.isValidPerson isn't provided.) but, you know, fold is a thing.
> so they would not allocate an intermediate list
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.
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.
Practice will help make the former more readable.
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:
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)
I find it easier to read with the exception of the anonymous variables. In scala, I would write
val persons = names
.map { name => Person(name = name) }
.filter { person => person.isValid }Dunno, it's fairly obvious what you're working with, being explicit doesn't buy that much (for me at any rate).
val persons =
names.map(Person.apply).
filter(_.isValid) let persons = [ p | n <- names
, p <- peopleNamed n
, isValid p ]
Eh, maybe for more complicated examples, but I think that comprehension is a lot more complicated than:
filter isValid (map peopleNamed names)Except that doesn't support multiple people with the same name.
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.
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!
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!
It's ugly, but possible:
NSArray *filteredArray = [array filteredArrayUsingPredicate:[NSPredicate predicateWithBlock:^BOOL(id object, NSDictionary *bindings) {
return [object test];
}]];You mean something like:
a := #(1 2 3 4 5).
Transcript show: (a printString); cr.
b := a select: [:x | x \\ 2 == 0].
Transcript show: (b printString); cr.
Other than the $0, yes I do. Easier to read and think about in respect to operations on a collection.
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.
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.
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'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.
its almost a wash in this case, but when you start having a very complicated flow, the first way becomes easier and easier in relation.
It also depends on the language obviously. In this example, the first example has special tokens for the filter. It doesn't have to be so.
It also depends on the language obviously. In this example, the first example has special tokens for the filter. It doesn't have to be so.
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.
No, but this shouldn't be taken as an indictment of FP general. I prefer
persons = filter isValid (map init names)
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.
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.
The first is much more declarative. When everything in the language looks and acts like that, it's pretty easy to read.
When it's optional, well, sadness ensues.
When it's optional, well, sadness ensues.
If you learn Haskell or OCaml, you'll prefer the first snippet. I took a couple of MOOCs and blogged how I incorporated what I learned into my Swift:
https://h4labs.wordpress.com/2016/09/30/functional-swift-usi...
https://h4labs.wordpress.com/2016/09/30/functional-swift-usi...
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.
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 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.
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.
persons = [person for person in (Person(name) for name in names) if person.isValid()]
i've been struggling with python incomprehensions since time immemorial. map/filter are a breeze.
It's easy. The first bit:
It's almost like a select query in (pseudo) SQL.
[personIt's almost like a select query in (pseudo) SQL.
select person from people where person.isvalid = true [person for person in people if person.isvalid]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.
(filter (fn[p] (p :valid?))
(map (fn[n] (Person n) names))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):
And incidentally, this would probably be something like (EDIT: made example more realistic):
filter personIsValid (map initPerson names)
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.
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.
I'm not sure what you're talking about? My example contains no periods and only one kind of brackets? Did you reply to the wrong post?
Admittedly, it might be written with $ in practice, but that's a fairly simple idiom, and I tend to avoid it.
Admittedly, it might be written with $ in practice, but that's a fairly simple idiom, and I tend to avoid it.
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:
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).
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
`(let ((,sym (whatever))) (do-something ,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).
That's because your code assumes those convenience functions exist while the parent's code writes out the anonymous functions.
The direct translation of yours' to Clojure would be:
The direct translation of yours' to Clojure would be:
(filter valid-person? (map init-person names))
filter (\p -> isValid p) (map (\n -> Person n) names)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)
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)
Not a Haskell expert, but maybe monomorphism restriction
can require you to perform an eta abstraction. Just saying.
Huh? No, anyone who writes it in Haskell would not use those lambda abstractions. You would just use "filter isValid (map Person names)".
I'm assuming Person is a record constructor, is isValid here a field in that record or another function?
Haskell doesn't distinguish the two. If you define Person with named fields including isValid, you automatically get a function named isValid that returns that field, or you can write your own isValid function that examines the whole Person.
[deleted]
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.
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.
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.
Coming from ruby and using a lot of maps and functional constructs I personally think the first one is way easier to read.
Me too. The first one is harder to read, and also the first one is harder to extend if the business rules change.
I find it easier to read but I'd struggle to come up with it myself from zero
I find it much easier. It might be a question of getting used to it.
In Python, the only good language, this could be expressed as:
[person for person in (Person(name) for name in names) if person.isValid()]
filter(lambda p: p.isValid, map(Person, names))
persons = []
for name in names:
person = Person(name)
if person.isValid():
persons.append(person)So much for "There's Only One Way To Do It". :)
That is long gone, specially regarding string formatting.
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()]
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.
Just kidding. The bottomline of this page and talk is that Swift is still not functional. But you can do cool things with it.
https://en.wikipedia.org/wiki/Dylan_(programming_language)
(for those who didn't get the joke... ;-)
(for those who didn't get the joke... ;-)
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.
Well said. I can write exceedingly low defect code without folds. I can't do so with implicit IO everywhere, ad hoc polymorphism, and dynamic typing.
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.
Ask five programmers to define functional programming, get fifteen different answers.
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.
"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".
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.
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.
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”.
So much for “Lisp comes from [the] untyped lambda calculus”.
Your "function-oriented programming" has an older and more suitable term: https://en.wikipedia.org/wiki/Procedural_programming
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.
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.
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.
Seems to me that's because functional programming continues to evolve (which is great!) and newfangled properties and semantics get folded in.
To me the core is "no side effects" though (for pure FP). It's interesting to see what others consider to be the most salient feature(s).
To me the core is "no side effects" though (for pure FP). It's interesting to see what others consider to be the most salient feature(s).
Same thing can be said for object-oriented programming, unfortunately.
There's only one definition that matters: functional programming is programming with mathematical (pure) functions.
As a consequence you get referential transparency and thus equational reasoning. But change this definition and the term becomes meaningless.
As a consequence you get referential transparency and thus equational reasoning. But change this definition and the term becomes meaningless.
Though by this definition, Lisp, the granddaddy of functional programming languages, is not a functional programming language.
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 :-)
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:
(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...)
* (eq (expt 2 100) (expt 2 100))
NIL
(Disclaimer: I'm not saying functional programming is the right approach for writing every program, but if a language can't even get arithmetic and relational operators right...)
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?)
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.
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.
[deleted]
> 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?
;-)
If a tree falls in a forest and no one is around to hear it, does it make a sound?
If a program satisfies a property but the compiler cannot prove it, can we still rely on it?
;-)
If a tree falls in a forest and no one is around to hear it, does it make a sound?
If a program satisfies a property but the compiler cannot prove it, can we still rely on it?
> If a program satisfies a property but the compiler cannot prove it, can we still rely on it?
It's very simple: You can rely on what you can prove. This applies both to compiler authors and compiler users. That sometimes one can prove things the other can't shouldn't come off as a surprise. Neither party has all the information: The compiler author doesn't know the intended meaning of the program submitted to the compiler by the user. The user doesn't (need to) know the internal details of how the compiler works.
It's very simple: You can rely on what you can prove. This applies both to compiler authors and compiler users. That sometimes one can prove things the other can't shouldn't come off as a surprise. Neither party has all the information: The compiler author doesn't know the intended meaning of the program submitted to the compiler by the user. The user doesn't (need to) know the internal details of how the compiler works.
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.
http://www.lispworks.com/documentation/lw51/CLHS/Body/f_eq.h...
An implementation is permitted to make "copies" of characters and numbers at any time. The effect is that Common Lisp makes no guarantee that eq is true even when both its arguments are "the same thing" if that thing is a character or number.
http://www.lispworks.com/documentation/lw51/CLHS/Body/f_eq.h...
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.
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.
I am also aware of that. I am not really trying to convince you of anything, mostly trying to prevent casual readers from being taught Common Lisp from you. Look at the example you just gave, this is beyond ridiculous. I would prefer if you were focusing on what you want to fight "for", not what you want to fight "against".
You like having a strong separation between the language and its implementation. I get it. Note however that if you are the Haskell compiler, you can know things the programmer cannot, or you can inject code that can perform manipulations the programmer cannot express. There probably is an identity equality operator down there, that people cannot access. If you like that, I can understand; I can understand the appeal for a strict separation of concerns and the desire to express only the high-level intent. But really, I think this is not much different in CL and that you are focusing on implementation details. In CL the separation is not enforced, and that is your main problem with it.
The CL compiler is defined at the language specification level. You have access to internals, by choice, just as if you were writing Haskell ASTs using an Haskell compiler's internal API. As such, you can cross abstraction barriers whenever you need. We already discussed about this once, you can use purely functional data-structures (see FSET) and EQUALP and code to that functional interface and pretend there is no computer down there. Then, if you want, you can play with packages and symbols to make MAP & co. refer to the parallel version (see LPARALLEL), re-compile and have parallel code (this works best with unqualified symbols and different package definitions for the same file).
In all PL discussions, there is eventually mention of an hypothetical sufficiently smart compiler. The CL point of view is (among other things) that such a compiler is one where a programmer can easily add its own extensions. That allows you to express the intent of the program clearly in one place and have the implementation details elsewhere.
You like having a strong separation between the language and its implementation. I get it. Note however that if you are the Haskell compiler, you can know things the programmer cannot, or you can inject code that can perform manipulations the programmer cannot express. There probably is an identity equality operator down there, that people cannot access. If you like that, I can understand; I can understand the appeal for a strict separation of concerns and the desire to express only the high-level intent. But really, I think this is not much different in CL and that you are focusing on implementation details. In CL the separation is not enforced, and that is your main problem with it.
The CL compiler is defined at the language specification level. You have access to internals, by choice, just as if you were writing Haskell ASTs using an Haskell compiler's internal API. As such, you can cross abstraction barriers whenever you need. We already discussed about this once, you can use purely functional data-structures (see FSET) and EQUALP and code to that functional interface and pretend there is no computer down there. Then, if you want, you can play with packages and symbols to make MAP & co. refer to the parallel version (see LPARALLEL), re-compile and have parallel code (this works best with unqualified symbols and different package definitions for the same file).
In all PL discussions, there is eventually mention of an hypothetical sufficiently smart compiler. The CL point of view is (among other things) that such a compiler is one where a programmer can easily add its own extensions. That allows you to express the intent of the program clearly in one place and have the implementation details elsewhere.
> Note however that if you are the Haskell compiler, you can know things the programmer cannot, or you can inject code that can perform manipulations the programmer cannot express.
Those would be implementation details, not part of the language itself. Hence...
> There probably is an identity equality operator down there, that people cannot access.
... this doesn't make sense.
> You have access to internals, by choice, just as if you were writing Haskell ASTs using an Haskell compiler's internal API.
However, there's no way to portably manipulate compiler internals in Haskell. Heck, Haskell syntax, unlike Lisp syntax, can actually be represented in multiple ways: named variables, de Bruijn indices and levels, HOAS, etc. And this is a good thing.
> In all PL discussions, there is eventually mention of an hypothetical sufficiently smart compiler.
I wouldn't have brought it up myself.
> The CL point of view is (among other things) that such a compiler is one where a programmer can easily add its own extensions.
There's no dichotomy between extensibility and abstraction enforcement, even if you try to set up one.
Those would be implementation details, not part of the language itself. Hence...
> There probably is an identity equality operator down there, that people cannot access.
... this doesn't make sense.
> You have access to internals, by choice, just as if you were writing Haskell ASTs using an Haskell compiler's internal API.
However, there's no way to portably manipulate compiler internals in Haskell. Heck, Haskell syntax, unlike Lisp syntax, can actually be represented in multiple ways: named variables, de Bruijn indices and levels, HOAS, etc. And this is a good thing.
> In all PL discussions, there is eventually mention of an hypothetical sufficiently smart compiler.
I wouldn't have brought it up myself.
> The CL point of view is (among other things) that such a compiler is one where a programmer can easily add its own extensions.
There's no dichotomy between extensibility and abstraction enforcement, even if you try to set up one.
> ... this doesn't make sense.
In order to have an ML, you take a subset of Common Lisp and specialize/extend it in a very specific direction. The part that are removed from Lisp are the one you don't care about. I care about being able to use different equivalence classes, including the ones the compiler is going to require, like identity equality, because this matters when I implement abstractions myself.
> However, there's no way to portably manipulate compiler internals in Haskell.
Yes, why not, that would be damn useful. The alternative is to hack each implementation in its own way.
> Heck, Haskell syntax, unlike Lisp syntax, can actually be represented in multiple ways: [...]
Do you get the difference between internal and external representations? When you see (lambda (a) (+ a 1)), you don't know how the code is represented internally and how its value, when executed, is represented internally (when my compiler performs data-flow analysis, it uses a specific internal representation I don't need to know). Yet, you have access to a uniform API, defined at the language level, to manipulate data. That's why you can have the same source code working on the JVM, interpreted using a C/C++ runtime or directly expressed as assembly. In that sense, there is a separation between the language and its implementation. But part of the language specification is also there to guarantee a uniform way of building new extensions and integrate them with the compiler. That is a good thing. What is not enforced is how and when each feature is used. If that matters, dump a specialized Lisp image that you call the "compiler" and call it with Make on a file expressed in your custom DSL.
> There's no dichotomy between extensibility and abstraction enforcement, even if you try to set up one.
I am not trying to set up one. Just read more carefully.
In order to have an ML, you take a subset of Common Lisp and specialize/extend it in a very specific direction. The part that are removed from Lisp are the one you don't care about. I care about being able to use different equivalence classes, including the ones the compiler is going to require, like identity equality, because this matters when I implement abstractions myself.
> However, there's no way to portably manipulate compiler internals in Haskell.
Yes, why not, that would be damn useful. The alternative is to hack each implementation in its own way.
> Heck, Haskell syntax, unlike Lisp syntax, can actually be represented in multiple ways: [...]
Do you get the difference between internal and external representations? When you see (lambda (a) (+ a 1)), you don't know how the code is represented internally and how its value, when executed, is represented internally (when my compiler performs data-flow analysis, it uses a specific internal representation I don't need to know). Yet, you have access to a uniform API, defined at the language level, to manipulate data. That's why you can have the same source code working on the JVM, interpreted using a C/C++ runtime or directly expressed as assembly. In that sense, there is a separation between the language and its implementation. But part of the language specification is also there to guarantee a uniform way of building new extensions and integrate them with the compiler. That is a good thing. What is not enforced is how and when each feature is used. If that matters, dump a specialized Lisp image that you call the "compiler" and call it with Make on a file expressed in your custom DSL.
> There's no dichotomy between extensibility and abstraction enforcement, even if you try to set up one.
I am not trying to set up one. Just read more carefully.
> Do you get the difference between internal and external representations? When you see (lambda (a) (+ a 1)), you don't know how the code is represented internally and how its value, when executed [emphasis mine], is represented internally
I'm not talking about representations of semantic objects. I'm talking about representations of syntax. In Lisp's case, you don't get to choose - the macro system critically depends on a particular representation (named variables). Have fun writing macros that operate on HOAS.
I'm not talking about representations of semantic objects. I'm talking about representations of syntax. In Lisp's case, you don't get to choose - the macro system critically depends on a particular representation (named variables). Have fun writing macros that operate on HOAS.
> In Lisp's case, you don't get to choose - the macro system critically depends on a particular representation (named variables)
Please tell me how Haskell represents HOAS and how this is not possible in Lisp.
Also, read Barzilay's paper (http://scheme2006.cs.uchicago.edu/15-barzilay.pdf), or about the Ergo Project (1988! http://repository.cmu.edu/cgi/viewcontent.cgi?article=2763&c...).
Please tell me how Haskell represents HOAS and how this is not possible in Lisp.
Also, read Barzilay's paper (http://scheme2006.cs.uchicago.edu/15-barzilay.pdf), or about the Ergo Project (1988! http://repository.cmu.edu/cgi/viewcontent.cgi?article=2763&c...).
> Please tell me how Haskell represents HOAS and how this is not possible in Lisp.
I'm not talking about representing some object language's syntax in Haskell or Lisp. I'm talking about representing Haskell or Lisp's syntax in some other metalanguage (possibly Haskell or Lisp itself). How would you implement a macro expander that operates on HOAS?
> Barzilay's paper (http://scheme2006.cs.uchicago.edu/15-barzilay.pdf)
The object language implemented in that paper isn't the whole of Scheme, and in particular, it doesn't have macros.
> Ergo Project (1988! http://repository.cmu.edu/cgi/viewcontent.cgi?article=2763&c...)
Sorry, I can't find an explicit description of any object language's syntax in this paper.
I'm not talking about representing some object language's syntax in Haskell or Lisp. I'm talking about representing Haskell or Lisp's syntax in some other metalanguage (possibly Haskell or Lisp itself). How would you implement a macro expander that operates on HOAS?
> Barzilay's paper (http://scheme2006.cs.uchicago.edu/15-barzilay.pdf)
The object language implemented in that paper isn't the whole of Scheme, and in particular, it doesn't have macros.
> Ergo Project (1988! http://repository.cmu.edu/cgi/viewcontent.cgi?article=2763&c...)
Sorry, I can't find an explicit description of any object language's syntax in this paper.
In what language do we input code as HOAS, and target that representation with macros?
(Can't we expand macros in a conventional representation with symbols and environments and then go to HOAS?)
(It's not news that macros are weak in some sense; I mean you can shoot yourself in the foot with the classic non-hygienic ones; you can disrespect even the first order abstract syntax that you're working in: the macro can re-locate a piece of raw syntax which contains identifier references into the wrong scope where those references resolve otherwise.)
Anyway, have fun fishing for mackerel with your bear trap?
(Can't we expand macros in a conventional representation with symbols and environments and then go to HOAS?)
(It's not news that macros are weak in some sense; I mean you can shoot yourself in the foot with the classic non-hygienic ones; you can disrespect even the first order abstract syntax that you're working in: the macro can re-locate a piece of raw syntax which contains identifier references into the wrong scope where those references resolve otherwise.)
Anyway, have fun fishing for mackerel with your bear trap?
The “conventional” representation of syntax using explicitly named variables is utterly inconvenient and error-prone for anything other than parsing. The very first thing I want to do after parsing is convert the syntax tree to de Bruijn indices/levels or HOAS.
In Lisp, symbols are very important. And symbols are identity. An identity with other dressing, such as having a character string name which is somewhat of a semantic footnote.
"Functional programming" doesn't restrict the kinds of obejcts you can work with. An identity value, whose virtue is that it is different from other identities, is a legitimate concept which can be treated under functional programming.
I guess your problem is that you don't want non-symbolic objects from behaving like identities; only symbolic ones.
That is to say, two symbols are equal iff they are actually the same symbol, otherwise not---but other kinds of entities are treated differently.
There is something to be said for having just one kind of equality, which is appropriately defined for every kind of object.
Pragmatic issues get in the way though.
Let's consider "this list [1,2,3]" versus "that list [1,2,3]". What if we have lazy lists (as those things tend to crop up in functional languages, particularly non-strictly evaluated ones). Is "this infinite list [1,2,3, ...]" equal to "that infinite list [1,2,3,...]" even if they are generated by completely separate lazy procedures?
Your equality then has to basically test that two Turing computations are equivalent: that the underlying lazy generation procedures themselves are computing the same thing, even if in different ways.
In that vein, what do you do about structures with cycles and shared structure? Is the list #1=(1 . #1#) equal to another one that is also #1=(1 . #1#). (Lisp's equal functions don't have to handle this; but we could specify an equal function which does).
Equality is not so simple that we can just cover all of its nuances with a blanket rule based on some handwaving principle.
"Functional programming" doesn't restrict the kinds of obejcts you can work with. An identity value, whose virtue is that it is different from other identities, is a legitimate concept which can be treated under functional programming.
I guess your problem is that you don't want non-symbolic objects from behaving like identities; only symbolic ones.
That is to say, two symbols are equal iff they are actually the same symbol, otherwise not---but other kinds of entities are treated differently.
There is something to be said for having just one kind of equality, which is appropriately defined for every kind of object.
Pragmatic issues get in the way though.
Let's consider "this list [1,2,3]" versus "that list [1,2,3]". What if we have lazy lists (as those things tend to crop up in functional languages, particularly non-strictly evaluated ones). Is "this infinite list [1,2,3, ...]" equal to "that infinite list [1,2,3,...]" even if they are generated by completely separate lazy procedures?
Your equality then has to basically test that two Turing computations are equivalent: that the underlying lazy generation procedures themselves are computing the same thing, even if in different ways.
In that vein, what do you do about structures with cycles and shared structure? Is the list #1=(1 . #1#) equal to another one that is also #1=(1 . #1#). (Lisp's equal functions don't have to handle this; but we could specify an equal function which does).
Equality is not so simple that we can just cover all of its nuances with a blanket rule based on some handwaving principle.
> An identity value, whose virtue is that it is different from other identities, is a legitimate concept which can be treated under functional programming.
Of course. But I don't want object identities to be the only values I can manipulate. I like having values like the list [1,2,3].
> Your equality then has to basically test that two Turing computations are equivalent: that the underlying lazy generation procedures themselves are computing the same thing, even if in different ways.
Indeed, this means that equality of higher-order values is undecidable. Therefore, don't rely on testing whether higher-order values are equal - you just can't! This is also why laziness by default is such a bad idea.
> In that vein, what do you do about structures with cycles and shared structure?
In Standard ML, `val rec xs = 1 :: xs` simply doesn't compile. The right-hand side of a `val rec` definition must be a function literal. This guarantees that inductive data types (such as lists and trees) mean the right thing, and that structural recursion on them always terminates.
> Equality is not so simple that we can just cover all of its nuances with a blanket rule based on some handwaving principle.
I'm not handwaving anything.
Of course. But I don't want object identities to be the only values I can manipulate. I like having values like the list [1,2,3].
> Your equality then has to basically test that two Turing computations are equivalent: that the underlying lazy generation procedures themselves are computing the same thing, even if in different ways.
Indeed, this means that equality of higher-order values is undecidable. Therefore, don't rely on testing whether higher-order values are equal - you just can't! This is also why laziness by default is such a bad idea.
> In that vein, what do you do about structures with cycles and shared structure?
In Standard ML, `val rec xs = 1 :: xs` simply doesn't compile. The right-hand side of a `val rec` definition must be a function literal. This guarantees that inductive data types (such as lists and trees) mean the right thing, and that structural recursion on them always terminates.
> Equality is not so simple that we can just cover all of its nuances with a blanket rule based on some handwaving principle.
I'm not handwaving anything.
and if it was about OOP, you'd get a hierarchy of answers that no one can follow and is unsound ;)
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.
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.
It is the programming style I learned to program in Lisp and Caml Light, and when Haskell was still known as Mirada.
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.
That's just one aspect of functional programming. By that definition, almost any modern language is functional.
Take it from the other side: why would a language that allows to create higher-order functions/closures not be called functional?
Because that makes the term meaningless. You may as well ask "why don't we call any language that lets you do two actions in sequence 'procedural'?"
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.
That doesn't make the term meaningless, it just means that "functional programming" is a victim of its own success.
If you can apply the term to every programming language in widespread use today[1], then yes, it is pretty useless. There is real value in having the term "functional programming" be meaningful and denote a certain class of languages; defining that as "any language with first-class function values" is too broad as to render the term meaningless.
[1] Even C has this with Apple's Blocks extension (http://clang.llvm.org/docs/Block-ABI-Apple.html).
[1] Even C has this with Apple's Blocks extension (http://clang.llvm.org/docs/Block-ABI-Apple.html).
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.
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.
> Most languages only have higher-order procedures, not higher-order functions.
What do you mean by that?
What do you mean by that?
Functions have the following properties:
(0) A function maps every element of its domain to a unique element of its codomain.
(1) Functions don't exist in time, let alone change over time.
(2) Two functions with the same domain and codomain are equal if they map the same domain elements to the same codomain elements.
Since when do so-called “first-class functions” in most programming languages behave like this?
(0) A function maps every element of its domain to a unique element of its codomain.
(1) Functions don't exist in time, let alone change over time.
(2) Two functions with the same domain and codomain are equal if they map the same domain elements to the same codomain elements.
Since when do so-called “first-class functions” in most programming languages behave like this?
Every modern language is functional. :P But more accurately, every modern language is generally multi-paradigm.
No, wrong. You can pass pointers to functions in C.
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)
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 always thought FP == pure functions. I guess not?
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?
Where's the Swift proposal for the enhancements? Product and Sum support? Algebraic data types?
I enjoyed the talk, thank you.
The part about "lifting" a type was an 'aha' moment for me and now I understand!*.
I mean, I did this intuitively, but now I know the name of the technique, which is really good.
Thank you, I've learned something new today!
The part about "lifting" a type was an 'aha' moment for me and now I understand!*.
I mean, I did this intuitively, but now I know the name of the technique, which is really good.
Thank you, I've learned something new today!
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.
Scala is about as functional as it gets - the only remotely mainstream language that's more so is Haskell, IME. What kind of issues did you have?
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:
https://issues.scala-lang.org/browse/SI-1338
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.
https://issues.scala-lang.org/browse/SI-1338
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.
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.
PS: http://typelevel.org/
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.
PS: http://typelevel.org/
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).
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).
RIP the term "Object Oriented" as Alan Kay defined it.
easier to read than this?
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.