If this interests you, I would highly recommend his (and others') 2007 HOPL III paper "A history of Haskell: being lazy with class" [0].
SPJ is famous in the PL world for his exceptional gift of explaining advanced topics in a very palatable manner. He's also amazingly kind, and quite generous with his time when he can be. I have yet to meet someone with a negative opinion of him.
I feel to really see the full picture you need to be able to do point free programming with a language that supports the point free style as a first class feature.
Functional programming is about function composition. If you haven't picked up on this notion, than you haven't fully understood FP.
I'm a bit skeptical of the premise that either composition or application is a high enough bar. Consider stack-based/concatenative languages such as Forth. Composition and application are foundational aspects of that language, but nobody really considers Forth to be functional. On the other hand, the concatenative language called Joy is considered functional -- by its authors at the very least -- but it also introduces purity to the mix.
I bring up composition because this it is the most important differentiator between FP and all paradigms. I wrote about it another reply:
FP used to mean just "no side effects". (Barbara Liskov mentions this old understanding of FP here: https://www.youtube.com/watch?v=qAKrMdUycb8). That is a desideratum for the even bigger buzz-phrases "referential transparency" and "equational reasoning", which are the goals of the FP research programme and have yet to really materialize.
As a counterpoint to your claim that understanding point-free style is a fundamental part of understanding functional programming, how about this 1998 paper by Andrew Appel, "SSA is Functional Programming" http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.3... which locates the essence of functional programming in the fact of immutable data (equivalent to imperative Single Static Assignment code).
As to why I advocate the point free style for educational purposes and why I believe immutability is just buzz that hinders true understanding of why function composition is fundamental to FP I get into that here: https://news.ycombinator.com/item?id=22292105
I am quite aware Backus was talking about compositional programming in his Turing Award speech, and his work backs that position up, and as I stated, I think that is the proper ground level for functional programming, but most programmers do not agree.
The wide-spread and well understood meaning of functional programming is programming in an expression oriented way, with immutability of data and lack of side-effects being the tent pole rules, laziness/eagerness of evaluation becomes the pivot point between most languages, with the divergence between compositional and applicative languages being almost completely absent.
With all the conflation and mass propagation of the term functional, I have to agree with Conan Elliott and recommend a more rigorous approach to terminology, I don’t whether is adopt his usage of denotational in place of functional, but some clarity in the semantic space would be a good idea.
— Edited to fix autocorrected errors.
>with the divergence between compositional and applicative languages being almost completely absent.
Most FP languages have facilities to do both anyway. And the isomorphisms between the two concepts are small in distance so it doesn't matter too much if you use applicative over compositional. So really when I say you should do "point-free" to see the big picture I'm advocating that more for educational purposes rather than practical (though I'm not opposed to practical).
That being said you and I are pretty much in agreement, I was just unaware of the whole academic thing.
Just for reference, if you want to see the divergence between applicative (which is basically every modern language in production or in research) and compositional look at some of Manfred von Thun's papers he wrote about the Joy Programming Language. Some people strongly disagree with his stance, but I find him easy to read in any event, see the link below. Also, in several places linked from [0], Thun discusses the Categorical Abstract Machine and has a few references which served as a nice jumping off point for more reading.
[1] http://joy-lang.org/papers-on-joy/joy-compared-with-other-fu...
Do you have the source where Backus actually talks about the stuff you mentioned?
Also, with regard to the CT thing, I totally get that. The predominance of CT-based concepts (no matter how far they are actually removed from the mathematical background of actual CT) are one of the defining features of modern functional programming, to the point people make jokes about needing to know CT to write ‘Hello World’ in Haskell. However, and I admit to having an unhealthy obsession with following PLT academia, it really is a little bit of a smoke screen. Nearly all ‘functional’ languages are based on the lambda calculus and various augmentations thereto, and so most of the CT applied in the area tends to be refinements and imports of various constructs into some potentially BiCartesian Closed Category (which is what the lambda calculus with the common functional programming additions of product and sum types and 1st class functions is as a category). But as I said before, the fundamental construct in the computational model is application via substitution. All of the advanced categorical constructs and tools still hold for compositional languages, but, as the theory goes, you gain an algebraic theory of manipulation of the actual programming language by virtue of the categorical properties of composition (and the inferred lack of hand-wringing over the semantics of substitution.
Sorry for the wall of text, this particular corner of CS and PLT is my favorite place, so any chance to talk about it I jump on.
—————————————————————- 0 - https://www.thocp.net/biographies/papers/backus_turingaward_... 2 - http://citeseerx.ist.psu.edu/viewdoc/citations;jsessionid=B9... 3 - http://joy-lang.org/papers-on-joy/joy-compared-with-other-fu...
Missed one: Conal Elliot.
Poor Conal. He had to stop using the name Functional Reactivate Programming to Denotative Continuous Time Programming because the FRP name became a buzzword for a bunch of non-FRP systems
Yes! But more broadly about composition in general.
Also datatype composition. Building DSLs that allow you to compose small constructs into larger ones preserving the same type so you can compose even further. Maybe even inhibiting some algebraic properties so you can reason about your compositions. About identity, reflexivity, associativity, transitivity etc.
So many real world problems can be tackled this way and getting this right can make you so extraordinarily productive!
Functional programming in general is not about data composition. There is a difference between function composition and data composition in FP.
Function composition produces a new type given two separate types. In your example the type is the same.
In Haskell if you wanted to do data composition, you would need something like dependent types or some rudimentary form of it. If such a thing was invented, it may look something like this:
a -> b -> (a * b)
(a -> b) -> (c -> a) -> (c -> b)
The tuple type actually shares an isomorphism with the concepts I am describing above. However it ascribes a sort of "order" on the types and feels more like a container of two types than it does a composition of types. I will illustrate below:
a -> b -> (a,b) != a -> b -> (b,a)
a -> b -> (a * b) == a -> b -> (b * a)
data Expr = Const Int | Add Expr Expr | Mul Expr Expr
myExpr = Mul (Add (Const 1 2)) 4
The difference is rather blurry, because data constructors are very much like functions.
> Function composition produces a new type given two separate types.
Yes and no. The type might look different, but it's still a function! You can change the function domain to something else (like a DB query) to better see how this is actually type-preserving in a meaningful way:
Query a b -> Query c a -> Query c b
The type is different. Functions are a class of types. The output of function composition is absolutely a different type but within the class of function types.
>It's very easy to compose data in Haskell.
I suggest you reread my post, I do not believe you fully understood it. You can compose data in ALL languages.
>Query a b -> Query c a -> Query c b
I mentioned the tuple type in my post which is essentially the same thing as what you're doing sans the constructor. In type theory these things are called "Product types."
Products are commutative, but in Haskell Data composition does not hold this property. See below:
(a,b) != (b,a)
Query a b != Query b a
(a * b) == (b * a)
I know how types and type constructors work, it's completely irrelevant in the context of what I was trying to say about composition in FP.
It seems to me you're probably talking about a very specific technical form of composition. I'm not.
To me a simple function like `vertically :: [Ui] -> Ui` is also about composition. The input and output types of the `vertically` function are not the same no, but informally we're still composing UIs into UIs. Which is exactly the level of detail I care for in this discussion.
Maybe that's exactly why the likes of Elixir feel so much less functional than some other FP langs. You don't usually compose functions, merely use function application (|>).
To me, functional programming is the feeling that you can successfully reason about a local fragment of code, because you know what the code (and its callers, and callees) can and cannot do with the data being passed around. It's functional in the mathematical sense -- i.e., the output is a pure function of the input, no matter how convoluted the definition -- and knowing this helps us to reason more clearly, mainly because we don't have to worry about unseen effects at a distance. So, functional programming is a feeling of confidence achieved by making data transformations as local and as pure as possible.
That doesn't strike me as a very good definition. It's possible for an imperative language to be explicit about its data-flows.
The SPARK language does this. It's certainly not a functional language.
https://docs.adacore.com/spark2014-docs/html/ug/en/source/ho...
It's interesting that, while Ada is imperative, SPARK contract annotations aren't. I won't take up the challenge, but I think someone could argue that SPARK-minus-Ada may indeed be functional (although SPARK-minus-Ada is no longer a programming language).
I don't agree that functional programming is uniquely difficult to define. Again, I agree with Wikipedia, which offers a definition that seems fine: [Functional programming] treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data. [1]
It's true that we can disagree on whether immutability, or function composition, should be considered the true crux of functional programming. This isn't unique to FP though. In the object-oriented world, some consider inheritance to be the heart of OOP, and some consider dynamic-dispatch to be what really counts. [3]
> SPARK-minus-Ada is no longer a programming language
I think I agree, but I think we're in a minority (we seem to disagree with Wikipedia here). If you're working at a level of abstraction so high that you no longer think about algorithms, you aren't really 'programming'.
'Constraint programming'... isn't. The 'programmer' isn't really programming, they're writing a formal problem-description.
Formal specification languages like B-Method [4] aren't considered programming languages, for the same reason.
[0] https://en.wikipedia.org/wiki/Constraint_programming
[1] https://en.wikipedia.org/wiki/Functional_programming
The definition of FP is fuzzy and it feels like a "feeling." However, as humans we can formally define the word with an exact definition that fits the "feeling." We've already done it with mathematics and it improved our understanding by a huge margin.
What I see in practice is that we have various tribes, using various FP languages, who each define FP in terms of the languages they use (e.g., an FP lang must have certain type-system features, or be non-strict, or etc.). To put it crudely, FP is the thing that we do in our language, and which we perceive others as not doing. I've used the term "tribe" intentionally, as I do think that tribal thinking has had a role to play in the muddying of the term.
Given this, I think it's reasonable to demote FP to the level of "feeling", at least in general conversation. Discussions within a certain language community, or in the context of a book or article, are a different matter of course since a formal, contextual definition can be given there.
This was largely what people thought of mathematics before euclid formalized geometry. An exact definition exists for FP as it did for geometry and like geometry we will instantly recognize the definition of FP when someone finally decides to translate our intuition into formalization.
b = (F.G.H)(y)
(note F.G.H is a composition of 3 functions
into 1, it can be thought of as a single function that is
called with parameter y)
b = y |> F |> G |> H
The isomorphism between applicative and point free styles are so close that it basically doesn't matter which style to use. You can easily convert from one style to the other. I advocate the point free style more for educational purposes. To help you see that the composition of functions is fundamental to FP.
The question of how to Design things or how to abstract things in programming is thus in essence a discussion about different ways of composing things (aka different ways of abstracting things). It is the drive behind all the arguments behind different programming styles, different programming languages and different system designs.
The way you compose primitives in functional programming is through function composition. The debate between functional programming and procedural programming and OOP from a "design" perspective is thus the debate between which primitive composes better:
The function or the procedure or the object?
It's a question of Design and at the heart of it lies composition.
I think most people who love functional programming know on some level that the "design" of functional programs "feels" better. Most of them have never thought about "why" this is the case. They have never tried to answer the question of what is the true nature "design" from a programming language perspective. What is this vague thing we are optimizing for? We are constantly inventing new programming languages/patterns in attempt to answer the question and instead much of the time we move in a flat circle and come back to where we were before (see golang).
I believe FP moves the ball forward in terms of design. The thing is, most people can't see why. They rely on inexact feelings, and a lot of the times they even feel the opposite. I've heard people talk about FP is just a fad similar to design patterns and OOP. Without the ability to develop an exact concrete answer why one "design" is better than the other, we will always move in circles even when we discover a "design" that is actually better.
If you want an exact, concrete answer to the question of "design" the answer lies in the mechanics of composition.
However I think the claim "functional programming is about function composition", together with the claim that "other things commonly associated such as immutability are not defining features of functional programming", is a stronger claim that seems unsubstantiated. There are many design choices analogous to immutability vs mutability that people argue are defining features of or are not defining features of FP. A Lisper might argue that closures over first-class mutable data can be part of the FP paradigm, or even that an FP language must allow that, while a Haskeller might argue that no, this must be modelled on top of immutable data. I see merit in common arguments presented for both viewpoints. A Haskeller might argue that monadic composition and syntactic support for it is a defining feature of FP, because simulating it with only "plain" function composition is deficient in some way. A criticism of this might be that monad transformers don't compose well. They might argue functions that functions should not be strict by default, because non-strict functions compose better than functions which are not. There's a great Quora answer that talks about this (https://www.quora.com/After-Haskell-there-is-no-language-whi...) and I remember a blog post framing this more explicitly in terms of composition that I can't find right now. I'm just sketching arguments that I've heard/thought about, but all these arguments deal with composition, abstraction and functions.
I don't like the framing of "does a procedure or an object compose better" because not all design choices fall into one of those, in fact I think very few do in a useful way. Is multiple dynamic dispatch (e.g. Julia) a way to compose functions or objects?
I never went into why FP is better. I only said I believe it is better and that composition lies at the heart of this differentiation. So you are offering an opinion on something that I haven't expanded upon yet.
Allow me to explain why I believe composition in FP is a "better design" than other paradigms. First let's get on the same page about the true nature of design. What is it? I talk about it here: https://news.ycombinator.com/item?id=21953290
Once we're on the same page on what is design in general you can read about why I believe FP is better in general. I posted on quora, a definition of "good design" in the context programming and program organization. Then I go into why FP under this definition is "better."
https://www.quora.com/Is-senior-full-stack-engineer-Ilya-Suz...
The answer is not straightforward and I get into the caveats in the comments on that quora post.
I believe the definitions for design that I am describing are universal and concretely illustrate what we all talk about when we talk about "design." If you have a different definition of design than the problem is just semantic in nature. At the very least I think we can agree that in terms of this definition of "good design" FP is the better than OOP and imperative.
If you follow the links, read and completely understand what I'm writing you will see I covered everything. Right now it appears you didn't read it.
In the links I provided, I define "design," and I operate within the bounds of that definition so you are clear about what I'm talking about. Please read.
Which one of your links define the terms "FP" and "OOP"?
It sounds unnecessarily abstract. Isn't functional programming simply avoiding side effects? It forces you to use immutable datatype and write "pure" functions.
In another post I illustrate exactly why I believe that it IS NOT necessarily abstract and in fact fundamental to FP: https://news.ycombinator.com/item?id=22292105