18

Since machine language (e.g., 0110101000110101) computer languages have generally evolved to higher forms of abstraction, generally making it easier to understand the code when it's applied to a problem. Assembler was an abstraction over machine code, C was an abstraction over assembler, etc.

Object-oriented design seems to be very good at allowing us to model a problem in terms of objects, e.g., the problem of a university course registration system can be modeled with a Course class, a Student class, etc. Then, when we write the solution in an OO language, we have similar classes which get responsibilities and that generally is helpful for design, especially for modularizing the code. If I give this problem to 10 independent teams who solve it with an OO method, generally the 10 solutions will have the classes relating to the problem in common. There can be lots of differences when you start to get into coupling and interactions of those classes, so there's no such thing as "zero representational gap."

My experience with Functional Programming is very limited (no real-world use, only Hello World type programs). I'm failing to see how such languages allow easily mapping FP solutions to problems (with a low representational gap) the way OO languages do.

I understand the advantages of FP with respect to concurrent programming. But am I missing something, or is FP not about reducing a representational gap (making solutions easier to understand)?

Another way to ask this: would the FP code of 10 different teams solving the same real-world problem have a lot in common?


From Wikipedia on Abstraction (computer science) (emphasis mine):

Functional programming languages commonly exhibit abstractions related to functions, such as lambda abstractions (making a term into a function of some variable), higher-order functions (parameters are functions), bracket abstraction (making a term into a function of a variable).

The representational gap could be potentially increased, because [some] real-world problems aren't modeled easily with such abstractions.


Another way I see decreasing representational gap is in tracing the solution elements back to the problem. The 0's and 1s in machine code is very hard to trace back, whereas the Student class is easy to trace back. Not all OO classes trace easily to the problem space, but many do.

Don't FP abstractions always need explaining to find out which part of the problem space they are solving (apart from math problems)? OK - I'm good on this part. After looking at many more examples, I see how FP abstractions are very clear for parts of the problem that are expressed in data processing.


The accepted answer to a related question Can UML be used to model a Functional program? -- says "Functional programmers don't have a lot of use for diagrams." I really don't care if it's UML, but it makes me wonder about FP abstractions being easy to understand/communicate, if there are no diagrams that are widely used (assuming this answer is correct). Again, my level of FP use/understanding is trivial, so I understand no need for diagrams on simple FP programs.

OO design has function/class/package-levels of abstraction, with encapsulation (access control, information hiding) at each, which makes managing complexity easier. These are elements that allow going from the problem to the solution and back easier.


Many answers speak of how analysis and design are done in FP in a way analogous to OO, but nobody cites anything high-level so far (paul cited some interesting stuff, but it's low-level). I did a lot of Googling yesterday and found some interesting discussion. The following is from Refactoring Functional Programs by Simon Thompson (2004) (emphasis mine)

In designing an object-oriented system, it is taken for granted that design will precede programming. Designs will be written using a system like UML which is supported in tools such as Eclipse. Beginning programmers may well learn a visual design approach using systems like BlueJ. Work on a similar methodology for functional programming is reported in FAD: Functional Analysis and Design, but little other work exists. There may be a number of reasons for this.

  • Existing functional programs are of a scale which does not require design. Many functional programs are small, but others, such as the Glasgow Haskell Compiler, are substantial.

  • Functional programs directly model the application domain, thus rendering design irrelevant. Whilst functional languages provide a variety of powerful abstractions, it is difficult to argue that these provide all and only the abstractions needed to model the real world.

  • Functional programs are built as an evolving series of prototypes.

In the PhD thesis cited above, the benefits of using Analysis and design methodologies (ADM) are outlined independent of paradigms. But an argument is made that ADMs should align with the implementation paradigm. That is, OOADM works best for OO programming and is not well applied to another paradigm such as FP. Here's a great quote that I think paraphrases what I call representational gap:

one can argue at length regarding which paradigm provides the best support for software development, but one achieves the most natural, efficient and effective development package when one remains within a single paradigm from problem description through to implementation and delivery.

Here are the set of diagrams proposed by FAD:

  • function dependency diagrams which present a function with those it uses in its implementation;
  • type dependency diagram which provides the same service for types; and,
  • module dependency diagrams which present views of the module architecture of the system.

There's a case study in section 5.1 of the FAD thesis, which is a system to automate the production of data relating to a football (soccer) league. The requirements are 100% functional, e.g., input football results, produce league tables, scoring tables, attendance tables, transfer players between teams, updating data after new results, etc. No mention of how FAD works to solve non-functional requirements is documented, apart from stating that "new functionality should be allowed at a minimal cost", something that is nearly impossible to test.

Sadly, apart from FAD, I don't see any modern references for modeling languages (visual) that are proposed for FP. UML is another paradigm, so we should forget that.

closed as too broad by Euphoric, Doval, Fuhrmanator, GlenH7, Robert Harvey Jan 28 '15 at 17:01

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

20

The basic data is structured the same in pretty much any paradigm. You're going to have a Student, a Course, etc. whether it's an object, a struct, a record, or whatever. The difference with OOP isn't how the data is structured, it's how the functions are structured.

I actually find functional programs much more closely match how I think about a problem. For example, to plan a student's schedule for next semester, you think about things like lists of courses a student has completed, courses in a student's degree program, courses offered this semester, courses a student has completed prerequisites for, courses with times that don't conflict, etc.

Suddenly, it's not so clear which class should create and store all these lists. Even less so when you have complex combinations of these lists. However, you must choose one class.

In FP, you write functions that take a student and a list of courses and return a filtered list of courses. You can group all such functions together in a module. You don't have to couple it with one class or another.

So your data models end up looking more like how OOP programmers think of their models, before they get polluted with classes that have no other purpose than providing convenient places to put functions that operate on combinations of other classes. No weird CourseStudentFilterList or similar classes that you always end up needing in OOP, but never think about in the beginning design.

  • 5
    @BenAaronson the problem in my experience is that then any function related to a student is added to the Student class and its responsibilities grow and grow until you need to introduce StudentCourseFilterer to keep things manageable – AlexFoxGill Jan 26 '15 at 12:03
  • 3
    @Den Hybrid approaches have their merits. It's not true, however, that the distinction is artificial. There are lots of compromises Scala had to make in order to fit OOP and FP (less powerful type inference is one. Complexity is another: yes, a language that mixes OOP and FP tends to be more complex -- as in "hard to use and understand" -- than one of its purer brothers on the two extremes). – Andres F. Jan 26 '15 at 14:04
  • 3
    @Den See also Erik Meijer's "'Mostly Functional' programming doesn't work", which argues against the hybrid approach and for going full "fundamentalist" FP. – Andres F. Jan 26 '15 at 14:05
  • 4
    @Den The popularity you describe is, I'm afraid, an accident of history. I use Scala at work, and it's a complex beast due to the way it attempts to mix FP and OOP. Switching to a true FP language like Haskell feels like a breath of fresh air -- and I'm not talking from an academic perspective either! – Andres F. Jan 26 '15 at 14:27
  • 3
    @Den I can't tell what either of those functions do. However, I can tell you if the first function in FP was a sort or a filter, it would be named filter or sort, not func (just like you named it IFilter, etc). In general, in FP you'd name it func or f when either sort or filter is a valid choice! For example, when writing a higher-order function that takes func as a parameter. – Andres F. Jan 26 '15 at 14:34
10

When I took my Java class years ago, we were expected to show our solutions to the entire class, so I got to see how people think; how they solve problems logically. I fully expected the solutions to cluster around three or four common solutions. Instead, I watched as 30 students solved the problem in 30 completely different ways.

Naturally, as fledgling programmers gain experience, they will gain exposure to common software patterns, begin using those patterns on their code, and then their solutions may coalesce around a few optimal strategies. These patterns form a technical language by which experienced developers can communicate.

The technical language that underpins functional programming is math. Accordingly, the problems that are most suitable to solve using functional programming are essentially math problems. By math, I'm not referring to the kind of math that you would see in business solutions, like addition and subtraction. Rather, I'm talking about the kind of math that you might see on Math Overflow, or the kind of math you would see in Orbitz' search engine (it's written in Lisp).

This orientation has some important ramifications for functional programmers trying to solve real-world programming problems:

  1. Functional programming is more declarative than imperative; it concerns itself primarily with telling the computer what to do, not how to do it.

  2. Object-oriented programs are often built from the top-down. A class design is created, and the details are filled in. Functional programs are often built from the bottom-up, starting with small, detailed functions that are combined into higher-level functions.

  3. Functional programming can have advantages for prototyping complex logic, constructing flexible programs that can change and evolve organically, and building software where the initial design is unclear.

  4. Object-oriented programs can be more suitable for business domains because the classes, messages between objects, and the software patterns all provide a structure that maps to the business domain, captures its business intelligence and documents it.

  5. Because all practical software produces side-effects (I/O), purely functional programming languages require a mechanism to produce those side-effects while remaining mathematically pure (monads).

  6. Functional programs can be more readily proven, due to their mathematical nature. Haskell's type system can find things at compile time that most OO languages cannot.

And so on. As with many things in computing, object-oriented languages and functional languages have different tradeoffs.

Some modern OO languages have adopted some of the useful functional programming concepts, so that you can have the best of both worlds. Linq, and the language features that were added to support it, is a good example of that.

  • 6
    @thepacker: You do have state in functional programming. Only the representation is different: in OOP you use mutable variables whereas in functional programming you can use infinite streams of states that are created on the fly when the program needs to inspect them. Unfortunately, state is often identified with mutable variables, as if mutable variables were the only way to represent state. As a consequence, many believe that a programming language without mutable variables cannot model state. – Giorgio Jan 25 '15 at 21:54
  • 12
    "Accordingly, the problems that are most suitable to solve using functional programming are essentially math problems.": I do not agree with this statement (see also my previous comment), at least I do not see why it should be true or what it actually means. You can see traversing a directory structure as a math problem and implement it with a recursive function, but since the customer does not see the source code, you are just solving a practical problem like finding a file somewhere in the file system. I find such a distinction between math and non-math problems artificial. – Giorgio Jan 26 '15 at 8:03
  • 5
    +1, but I'm not sold on points 2 and 4. I've seen plenty of Haskell tutorials and blog posts that start by tackling a problem top-down, defining all the types and operations to see how it all fits together while leaving every value and function definition undefined (well, defined to throwing an exception). It seems to me that Haskell programmers tend to model the problem more thoroughly because they're more inclined to add trivial types for the sake of semantics - e.g. adding a SafeString type to represent strings that have been HTML-escaped - and generally keeping more track of effects. – Doval Jan 26 '15 at 19:33
  • 4
    "the problems that are most suitable to solve using functional programming are essentially math problems." That simply is not true. The fact that the concept of Monads comes from category theory also does not mean that mathematical tasks are the most natural/fit domain for functional languages. All it means is that code written in strongly typed functional languages can be described, analysed and reasoned about using mathematics. This is a powerful extra feature, not something which stops you writing "Barbie Horse Adventures" in Haskell. – itsbruce Jan 26 '15 at 19:58
  • 6
    @itsbruce Barbie Horse Adventures is a serious mathematical simulation of the highest caliber, it's pidgeon holing FP into overly-complex numerical projections like matrices describing the physical shimmering of Barbie's hair over a discrete period in a variety of possible real world environments that convinces people to completely dismiss it as irrelevant to their every-day business problem coding. – Jimmy Hoffa Jan 26 '15 at 21:10
7

I would like to stress an aspect that I find important and that has not been covered in the other answers.

First of all, I think that the representational gap between problems and solutions can be more in the mind of the programmer, according to their background and to the concepts they are more familiar with.

OOP and FP look at data and operations from two different perspectives and provide different tradeoffs, as Robert Harvey has pointed out already.

One important aspect in which they differ is the way in which they allow to extend your software.

Consider the situation in which you have a collection of data types and a collection of operations, for example you have different image formats and you maintain a library of algorithms to process images.

Functional programming makes it easier to add new operations to your software: you only need a local change in your code, namely you add a new function, which handles different input data formats. On the other hand, adding new formats is more involved: you need to change all the functions you have already implemented (non local change).

The object-oriented approach is symmetric to this: each data type carries its own implementation of all the operations and is responsible of choosing the right implementation at runtime (dynamic dispatching). This makes it easy to add a new data type (e.g. a new image format): you just add a new class and implement all its methods. On the other hand, adding a new operation means to change all the classes that need to provide that operation. In many languages this is done by extending an interface and adapting all classes implementing it.

This different approach to extension is one of the reasons why OOP is more appropriate for certain problems where the set of operations varies less often than the set of data types on which these operations work. A typical example are GUIs: you have a fixed set of operations that all widgets must implement (paint, resize, move, and so on) and a collection of widgets that you want to extend.

So, according to this dimension, OOP and FP are just two specular ways of organizing your code. See SICP, in particular Section 2.4.3, Table 2.22, and paragraph Message passing.

Summarizing: in OOP you use data to organize operations, in FP you use operations to organize data. Each approach is stronger or weaker according to the context. In general, none of the two has a higher representational gap between problem and solution.

  • 1
    Actually, Visitor Pattern (in OOP) gives you same power as you said for FP. It allows you to add new operations while making adding new classes harder. I wonder if you can do same in FP (eg. adding new formats instead of operations). – Euphoric Jan 26 '15 at 8:38
  • 1
    The image processing scenario doesn't seem like the best example. Surely you'd convert the images into some internal format and process that instead of writing separate implementations of all your image processing stuff for each image type? – Hey Jan 26 '15 at 8:49
  • 1
    @Giorgio maybe I'm not getting the intended meaning from this part: "adding new formats is more involved: you need to change all the functions you have already implemented." – Hey Jan 26 '15 at 9:14
  • 2
    @Hey Giorgio is likely referring to the so-called Expression Problem. "Adding new formats" means "adding new constructors (aka 'cases') to a datatype". – Andres F. Jan 26 '15 at 13:02
  • 1
    @Euphoric: I have not looked into the details, but the FP counterpart to the visitor pattern should involve an Other variant / constructor in your data type, and an extra function parameter to be passed to all functions to handle the other case. It is, of course, awkward / less natural with respect to the OOP solution (dynamic dispatch). In the same way, the visitor pattern is awkward / less natural than the FP solution (a higher-order function). – Giorgio Jan 26 '15 at 13:13
5

Most functional languages are not Object-Oriented. That does not mean they have no objects (in the sense of complex types which have specific functionality associated with them). Haskell, like java, has Lists, Maps, Arrays, all kinds of Trees and many other complex types. If you look at the Haskell List or Map module you will see a set of functions very similar to the methods in most equivalent OO-language library modules. If you inspect the code, you will even find similar encapsulation, with some types (or their constructors, to be precise) and functions only usable by other functions in the module.

The way you work with these types in Haskell is often hardly different from the OO way. In Haskell I say

  null xs
  length xs

and in Java you say

  xs.isEmpty
  xs.length

Tomato, tomato. The Haskell functions are not tied to the object but they are closely associated with its type. ¨Ah, but,¨ you say, ¨in Java it is calling which ever length method is appropriate to the actual class of that object¨. Surprise - Haskell does polymorphism too with type classes (and other things).

In Haskell, if I have is - a collection of integers - it does not matter whether the collection is a list or set or array, this code

  fmap (* 2) is

will return a collection with all the elements doubled. Polymorphism means that the appropriate map function for the specific type will be called.

These examples are, in truth, not really complex types but the same applies in more difficult problems. The idea that functional languages do not let you model complex objects and associate specific functionality with them is simply wrong.

There are important and significant differences between the functional and OO style but I don´t think this answer has to deal with them. You asked if functional languages prevent (or hinder) intuitive modelling of problems and tasks. The answer is No.

  • As a matter of fact, you can use type classes in Java/C#; you just to explicitly pass the dictionary of functions, instead of having the compiler infer the correct one based on the type. – Doval Jan 26 '15 at 14:07
  • Oh, definitely. As William Cook said, much OO code actually makes more frequent use of higher order functions than functional code does, even though the coder probably is not aware of it. – itsbruce Jan 26 '15 at 14:29
  • 2
    You are making a false distinction. A list is no more an inert data structure than a stack or a queue or a tic-tac-toe simulator. A list can hold anything (in Haskell it might well be partially applied functions) and defines how those things can be interacted with. You could apply a list full of partially applied functions to another list of values and the result would be a new list containing every possible combination of functions from the first and input from the second. That's much more than a C struct. – itsbruce Jan 26 '15 at 19:27
  • 3
    Types are used for more varied things in functional languages than imperative/OO ones (the type systems tend to be more powerful and consistent, for one thing). Types and their functions are used to shape code paths (which is why several functional languages simply do not have keywords for loops - not needed), for example. – itsbruce Jan 26 '15 at 19:42
  • 4
    @Fuhrmanator "I'm not seeing how this is done in FP" So you're complaining something you don't understand doesn't make sense; go learn it, understand it thoroughly, and then it will make sense. Maybe after it makes sense you'll decide it is crap and you don't need others to prove it to you, though other people such as above do understand it and haven't come to that conclusion. You appear to have brought a knife to a gun fight, and now you're telling everybody that guns are useless because they aren't sharp. – Jimmy Hoffa Jan 26 '15 at 23:25
4

FP does indeed strive for a reduction in the representational gap:

Something you'll see a lot of in functional languages is the practice of building the language up (using bottom-up design) into an Embedded Domain Specific Language (EDSL). This lets you develop a means of expressing your business concerns in a way that is natural for your domain within the programming language. Haskell and Lisp both pride themselves on this.

Part (if not all) of what enables this ability is more flexibility and expressiveness within the base language(s) itself; with first class functions, higher-order functions, function composition, and in some languages, algebraic data types (AKA discriminated unions) and the ability to define operators*, there's more flexibility available for how to express things than there is with OOP, which means you'll probably find more natural ways to express things from your problem domain. (It should say something that many OOP languages have been adopting many of these features recently, if not starting out with them.)

* Yes, in many OOP languages you can override the standard operators, but in Haskell, you can define new ones!

In my experience working with functional languages (mostly F# and Haskell, some Clojure, and a little Lisp and Erlang), I have an easier time mapping the problem space down into the language than I do with OOP -- especially with algebraic data types, which I find more flexible than classes. Something that threw me for a loop when starting out with FP, particularly with Haskell, was that I had to think/work at a bit higher level than I was used to in imperative or OOP languages; you might be running into this a bit as well.

  • Business concerns (from the customer) aren't expressed very often in higher-order functions. But a customer can write a one-line user story and provide you with business rules (or you can get them out of the customer). I'm interested in the (top-down?) domain modeling (from those artefacts) that allows us to arrive at abstractions of the problem that map to first-class functions, etc. Can you cite some references? Can you use a concrete example of a domain, the abstractions, etc.? – Fuhrmanator Jan 26 '15 at 21:54
  • 3
    @Fuhrmanator A customer can still write one-line user stories and business rules regardless of whether you use OOP and FP. I don't expect customers to understand higher-order functions any more than I expect them to understand inheritance, composition or interfaces. – Andres F. Jan 26 '15 at 23:06
  • 1
    @Fuhrmanator How often have you had the customer express their concerns in terms of Java generics or abstract base classes and interfaces? Dear God. Paul has given you a very good answer, explaining a practical and reliable method of modelling using techniques which are surely not too hard to visualise. And yet you insist that it be described in terms of one specific modelling technique for one particular paradigm, as if that were somehow the most natural way to represent design and anything else can be redrawn in its terms. – itsbruce Jan 26 '15 at 23:44
  • @Fuhrmanator This might not be as high-level as you're looking for but should give some insight into the design process using functional techniques: Designing With Types. I'd recommend browsing that site in general because it has some excellent articles. – paul Jan 27 '15 at 0:04
  • @Fuhrmanator There's also this Thinking Functionally series – paul Jan 27 '15 at 0:13
3

As Niklaus Wirth put it, "Algorithms + Data Structures = Programs". Functional programming is about the way to organize algorithms, and it does not tell a lot about ways to organize data structures. Indeed, there exist FP languages both with mutable (Lisp) and immutable (Haskell, Erlang) variables. If you want to compare and contrast FP with something, you should pick imperative (C, Java) and declarative (Prolog) programming.

OOP is on the other hand a way to build data structures and attach algorithms to them. FP does not prevent you from building data structures similar to OOP ones. If you don't believe me, have a look at Haskell type declarations. However, most FP languages agree that functions do not belong to data structures and should rather be in the same namespace. This is done in order to simplify building new algorithms via function composition. Indeed, if you know what input a function takes and what output it produces, why should it matter which data structure it belongs too? For example, why does add function have to be called on an instance of Integer type and passed an argument instead of simply being passed two Integer arguments?

Therefore, I don't see why FP should make solutions harder to understand in general, and I don't think it does it anyway. However, keep in mind that a seasoned imperative programmer will certainly find functional programs harder to understand than imperative ones, and vice versa. This is similar to Windows - Linux dichotomy when folks who have invested 10 years in becoming comfortable with Windows environment find Linux difficult after a month of usage, and those who are used to Linux cannot achieve the same productivity in Windows. Hence, the 'representational gap' you are talking about is very subjective.

  • Because of encapsulation and data hiding, which are not OO principles per se, I don't entirely agree with OO being data structures + algorithms (that's the internal view only). The beauty of any good abstraction is that there's some service it provides to solve part of the problem, without one needing to understand too many of the details. I think you're talking encapsulation when you separate functions and data in FP, but I'm too green to know for sure. Also, I edited my question to refer to tracing from the solution back to the problem (to clarify the meaning of representational gap). – Fuhrmanator Jan 26 '15 at 13:27
  • if you know what input a function takes and what output it produces, why should it matter which data structure it belongs too? That sounds a lot like cohesion, which for any modular system is important. I'd argue that not knowing where to find a function would make it harder to understand a solution, which is due to higher representational gap. Lots of OO systems have this problem, but it's because of bad design (low cohesion). Again, the namespace issue is out of my expertise in FP, so maybe it's not as bad as it sounds. – Fuhrmanator Jan 26 '15 at 19:27
  • 1
    @Fuhrmanator But you do know where to find a function. And there is only one function, not multiple functions with the same name, defined for each datatype (again, see the "Expression Problem"). For example, for Haskell library functions (which you're encouraged to use, instead of rediscovering the wheel or making a slightly less useful versions of said functions), you have wonderful discovery tools such as Hoogle, which is so powerful it lets you search by signature (try it! :) ) – Andres F. Jan 26 '15 at 19:41
  • 1
    @Fuhrmanator, after "That sounds a lot like cohesion", I would have expected you to logically conclude that FP languages let you write programs with higher cohesion but you surprized me. :-) I think you should pick an FP language, learn it and decide for your own. If I were you, I'd suggest to start with Haskell since it is quite pure and therefore will not let you write code in imperative style. Erlang and some Lisp are also good choices but they mix in other programming styles. Scala and Clojure, IMO, are quite complicated to start from. – mkalkov Jan 27 '15 at 20:05

Not the answer you're looking for? Browse other questions tagged or ask your own question.