Functional Thinking after OO
squirrel.pl
squirrel.pl
However, I also see that there are very hard parts to purely functional as well. For instance, to be entirely side-effect free your language has to be able to enforce immutability (which JS lacks). It's also hard (or at least not obvious) how to do certain types of logic flows in a purely functional.
For small domain spaces I can visualize how purely functional bottom-up programming effectively causes you to write a DSL for your problem.
However I don't have the experience/wisdom to understand if this holds true as the size of the domain increases. Basically, I have concerns that purely functional solutions don't scale (not from a performance perspective, but from an organizational/architectural one).
My experience with complex business logic makes me worried that complex new business rules would be difficult to implement in purely functional way and would cause frequent, painful refactoring.
I would love to hear from someone that's done a purely functional application with a large surface area that has been subjected to a real-world business environment to comment on the subject.
Unix Pipes
I believe using them to compose several small programs together to get a new solution has been fairly well documented :)
Erlang does both, maybe that's where the confusion is coming from. They're very complementary, though: having separate, concurrent processes seems to be an excellent pressure release for difficulties that can build up doing pure functional programming.
Also, Erlang has an novel (and extremely effective!) error-handling system for the actors, while error handling for Unix pipelines (or asynch/event-loop systems!) can be tricky.
Unix pipes are lazy lists.
Operations on lazy lists allow you to use Mealy machine [1] created from pure functions. Mealy machine uses pure functions that transforms input and previous state to output and next state, which state then goes back on the next cycle.
And then you suddently have Turing completeness (because of arbitrary state).
My argument is supported by the fact that Unix pipes could not change the topology of computation structure, so do lazy lists, while actors could.
I worked at a betting exchange where the backend was written entirely in erlang. There were a lot of areas in the code where we had to deal with incredibly complicated business rules.
For example, we were not allowed to allow customers to gamble money they didn't have in their account but we did want to allow them to sell out of a position. This meant keeping track their minimum possible gains from all their current positions to figure out how much money they could safely be allowed to use. Money laundering regulations meant we also had to keep track of where different pools of money came from (eg different bank accounts, paypal etc) and these pools could not be allowed to mix (eg you can't deposit money into the site using paypal and then withdraw it into your bank account). Users are allowed to pick their own odds so we always had to be very careful whether money gets rounded up or down. And then there were promotions giving extra money for new members or for large deposits and any bets had to be taken from bonus pools before other money pools.
Functional programming is a very overloaded term so I will talk about specific things that made this easier. I personally find it much easier to construct complex data structures and maintain invariants on them when using algebraic types + pattern matching rather than objects. The use of immutable data structures made it much easier to verify that no operation ever changed the total amount of money in the system and to safely implement highly concurrent systems. First class functions were used throughout the code but we probably could have replaced most uses by objects with little change to the overall structure.
I think that in general OO conflates the management of code and the management of runtime state. In erlang modules are the unit of code management and processes the unit of state management. I would also point out that an entirely purely functional program is impractical with current software and probably not desirable in general.
Bear in mind that most of the advocacy for functional programming tends to from people who have only just encountered the idea and are extremely excited. There are much more nuanced viewpoints available if you dig a little eg Rich Hickey's ideas on the separation of state and identity: http://wiki.jvmlangsummit.com/images/a/ab/HickeyJVMSummit200...
I did write some vaguely related stuff about the benefits of their declarative web framework here: http://scattered-thoughts.net/one/1280/511009/453845. I may also ask if I can open source the transactional actors library I wrote there. That would probably be worth writing about.
1. Start with code centered around pure functions. This is a really good default for your project. It gives you flexibility, completely DRY code, and an easy way to think about concurrency.
2. Store large datasets or shallow objects inside maps. They can be efficient and work really well with functions, especially in languages like Python and Clojure. They're even more useful when, for example, they have a literal dot notation (Javascript) for keys.
3. Sometimes, though, it's just easier to structure data inside of objects. Having a map of maps of maps is fine, but projects can quickly become confusing--at least in my experience. The problem is especially bad if multiple people are coding around maps without any enforced structure or validation on creation. In these cases, objects can make things simple and (often) more unified. When I use objects, though, it's good to avoid mutable state. I think of an object as a handy, unified interface to a map, but with the following extras in a unified way:
- A constructor, potentially with sensible defaults
- Validations and sensible fallbacks
- Data-specific error messages
- Methods that are closely related to the data it
holds (and always return the object itself, so
chaining is simple)
Using a functional style doesn't mean you can't use constructors, and constructors don't necessarily mean you have to use objects.
> Validation is contextual; what validation you apply is dependent on the source of the data.
> Often in an API we are more restrictive than we may be in a user interface, demanding that everything be specified explicitly. In a UI we may assist the user by filling in values on their behalf. The specifics of this depend on the UI and the objects in question.
> At the same time, we are often more restrictive in a UI. For instance, we may demand that the user enter something that appears to be a valid phone number. But for historical reasons, we may not make that demand for objects that already exist, or we may put in a tight restriction on the UI keeping in mind that it can more easily be relaxed and refined than a restriction in the domain objects or underlying database. Also, we may trust the programmer to use the API in a reasonable way, but we seldom trust user data in the same way.
-- http://formencode.org/Design.html#validation-as-directional-...
Lately I've even played with the idea that maybe Clojure style strict separation of data and functions is just taking the single responsibility principle of OO design to it's ultimate conclusion as the responsibilities of storing a piece of data in memory and the responsibility of deriving new data from it are separated...
On the other hand, I completely disagree that top-down programming is strongly tied to OO programming. At the very least, it certainly is possible to do bottom up programming in OO languages. That's my normal working mode...
This obviously works for the single programmer, who understands the code he's written (assuming he/she hasn't been away from the code too long), but what happens when you have to maintain someone else's code? If I have to jump into a particular spot on the code to solve a problem, how do I know you've defined <+- as some special monad?
As a maintenance programmer, it seems like I'd have to learn a whole new language with each program I have to maintain. (and I, the hypothetical maintenance programmer, am probably not as smart as the original programmer).
It is isomorphic to "creating an API". It's really more a perspective on the situation than a literal description of what's going on. No matter what you're programing in, you're building up some sort of language that subsequent programmers will have to understand to work on your code.
Note that this is different from overloading the same name to mean different things depending on context.
If your code uses a lot of new utilities, some readers may complain that it is hard to understand. People who are not yet very fluent in Lisp will only be used to reading raw Lisp. In fact, they may not be used to the idea of an extensible language at all. When they look at a program which depends heavily on utilities, it may seem to them that the author has, out of pure eccentricity, decided to write the program in some sort of private language.
All these new operators, it might be argued, make the program harder to read. One has to understand them all before being able to read the program. To see why this kind of statement is mistaken, consider the case described on page 41, in which we want to find the nearest bookshops. If you wrote the program using find2, someone could complain that they had to understand the definition of this new utility before they could read your program. Well, suppose you hadn’t used find2. Then, instead of having to understand the definition of find2, the reader would have had to understand the definition of find-books, in which the function of find2 is mixed up with the specific task of finding bookshops. It is no more difficult to understand find2 than find-books. And here we have only used the new utility once. Utilities are meant to be used repeatedly. In a real program, it might be a choice between having to understand find2, and having to understand three or four specialized search routines. Surely the former is easier.
So yes, reading a bottom-up program requires one to understand all the new operators defined by the author. But this will nearly always be less work than having to understand all the code that would have been required without them.
If people complain that using utilities makes your code hard to read, they probably don’t realize what the code would look like if you hadn’t used them. Bottom-up programming makes what would otherwise be a large program look like a small, simple one. This can give the impression that the program doesn’t do much, and should therefore be easy to read. When inexperienced readers look closer and find that this isn’t so, they react with dismay.
We find the same phenomenon in other fields: a well-designed machine may have fewer parts, and yet look more complicated, because it is packed into a smaller space. Bottom-up programs are conceptually denser. It may take an effort to read them, but not as much as it would take if they hadn’t been written that way.
"So yes, reading a bottom-up program requires one to understand all the new operators defined by the author. But this will nearly always be less work than having to understand all the code that would have been required without them."
Here's the problem: it's hard to build good abstractions. Every abstraction has a cost and an overhead in learning it, getting used to it, managing the cognitive overhead. The binary black-and-white phrasing of this argument utterly sidesteps any mention of the tradeoffs involved. Most abstractions we encounter in real-world code fail to take into account the cost of using an abstraction. You built it, you're used to it, you can't empathize with others who need to learn it.
Here's my stab at articulating the tradeoffs: http://news.ycombinator.com/item?id=2329613
Common Lisp is a great language, but it's littered with crappy abstractions: too many kinds of equality http://www.nhplace.com/kent/PS/EQUAL.html, an inability to override or extend coerce, redundant control abstractions like keyword args to reverse traversal order (http://dreamsongs.com/Files/PatternsOfSoftware.pdf, pages 28-30), the list goes on and on.
I see that in my code all the time: my abstractions tend to suck until I use them myself, at which point I fix them.
The problem is, we often have to build abstractions that others will use before we use them ourselves. At that point we're kinda stuck, because the necessary changes will break code, and that's scary.
I used to think the same thing. But I'm starting to realize that you have to make some assumption about what tools future readers of your code have at their disposal, and that these assumptions change the cost and overhead of abstractions.
Here's a degenerate example. We all know that where you draw your function boundaries hugely impacts readability. You don't want one single function for your entire program, and you don't want every function being one-liners either. There tends to be a sweet spot that takes into account how often a code fragment is needed before extracting it into its own function. But if you take into account that a java programmer reading it in his IDE can jump to the call with a keystroke, that tends to move the sweet spot downward. Now I need less reuse to justify method extraction.
A less degenerate example: ruby has monkey-patching, where you can change a function or class's behavior without touching the file where it's defined. This tends to be viewed as a bad thing because now it difficult to visualize a function's b does. But I'm starting to realize this depends on how hard it is to search for the function. It's painful when you have a load path and have to search multiple disjoint directory trees for a monkey-patch. But it would be fine if everything's in a single flat directory.
I've been working on an arc-like language, and I find I can be extremely promiscuous with my monkey-patching extensions because the language implementation is designed from the ground up to live in the same directory as your app, and finding monkey-patches takes just a simple grep. (Hopefully it's not just that it's just me hacking on it.)
Here's my implementation: http://github.com/akkartik/wart
I remember thinking when I first read through pg's essays a few years back and again now that you can do this in declarative languages as well using functions.
For example, my programs often looks something like this:
main(){
var data = getData();
pushData(data);
}
function getData(){
var data = fetchDataFromSource();
var errors = validateData(data);
if(errors != null)
//handle errors
return processData(data);
}
function fetchDataFromSource(){
...
}
function validateData(var data){
...
}
...
Building larger programs is about clean abstractions. What your doing only needs basic functions for abstraction, but when you try to do something larger you'll begin to need/want more ways to abstract your code. Then the differences will become clear.
But, you punted by not actually handling the errors. As others comments show, your example may need more abstraction tools once you try to handle the errors :)
getData = fetchDataFromSource . validateData . ProcessData
getData = fetchDataFromSource =<< validateData =<< ProcessData
getData = ProcessData . validateData . fetchDataFromSourceFor a simple example like this, that might be the cleanest solution. For anything more complicated (like recursive descent parsing), a processing chain like this is an ideal application for a monad, where the binding between functions would be customized to avoid calling ProcessData altogether.
function getData() {
return processData(validateData(fetchDataFromSource()));
}Compare to the non-duplicated code in my Lisp redis client: https://github.com/mattsta/er/blob/681e4f91d0601d2997b2b5b7a... . In the Lisp version, each redis-cmd-* call is a macro created by a macro which calls another macro to create the function in a polymorphic way.
You are one step closer to Lisp enlightenment.
basic_execute_command = {
# snip
### SET COMMANDS ###
"sadd": "Add ``value`` to set ``name``"
, "scard": "Return the number of elements in set ``name``"
, "sismember": "Return a boolean indicating if ``value`` is a member of set ``name``"
, "smembers": "Return all members of the set ``name``"
, "smove": "Move ``value`` from set ``src`` to set ``dst`` atomically"
, "spop": "Remove and return a random member of set ``name``"
, "srandmember": "Return a random member of set ``name``"
, "srem": "Remove ``value`` from set ``name``"
# snip
}
def _basic_execute_command (self, cmd):
return lambda *args: self.execute_command(cmd.upper(), *args)
# snip
def __init__ (self, *args, **kwargs):
# snip
for cmd in self.basic_execute_command:
self.__dict__[cmd] = self._basic_execute_command(cmd)
# snip
I know that Lisp ranks above Python on the metaprogramming scale, but simply adding easy object introspection can allow for cool factoring constructs that a Java (or similar) programmer wouldn't even consider. It's possible to make copy-pasta in any language.
You could have all the redis connection instances share the same command dict, or make it a variable in the package.
---R: Return the string value of the key
function Sidereal:get(key) end
cmd("GET", "k")
---R: Set a key to a string returning the old value of the key
function Sidereal:getset(key, value) end
cmd("GETSET", "kv")
---R: Multi-get, return the strings values of the keys
function Sidereal:mget(key_list) end
cmd("MGET", "K")
FWIW, I need to update it - antirez changed the protocol in a recent version, and I haven't gotten back to it yet. It should remove a good portion of the code, though - he switched everything to using the bulk form.
I have a genuine interest in the answers to this as it is one of the things putting me off learning an otherwise very interesting paradigm.
But check out node.js for the rest of your pain. It is very event driven and can easily be coded completely side-effect free due to closures.
For a clean answer to function + event-driven, see Erlang, which will blow pretty much any other attempt to solve the problems Erlang solves out of the water. Functional doesn't have a problem with event-based, functional blows imperative and OO out of the water at event-based. (Partially because it's a lot easier to write sophisticated runtime like Haskell's or Erlang's that can transparently deal with sync issues that drive imperative programs crazy.) Not enough people are good enough at both OO and functional for this to be commonly understood.
You'll know functional languages have entered the mainstream to stay when someone writes a useful functional GUI.
> programming a GUI or other heavily event-driven environment
Nitrogen is a nice event-based GUI library written in erlang. Have a look at the demos here: http://nitrogenproject.com/demos
Indeed. Haskell for example, just `tags' all side-effecting code in the type system. You are free to use lots of side-effects in Haskell. (Even though that would miss the point of the language.)
I feel that a language that would allow both styles to mix even further (immutable objects, pattern matching, tags (for ADTs), multimethods, concurrency) would be really cool to use.
The Problem with putting everything in a language and supporting everything equally is that people tend to do the wronge thing (like in JS up until the last years) and languages get to big (scala, d, CL).
I think a language that tends to FP (and makes it idiomatic) but allow other styles but makes them a bit harder to use. (in a lisp you can always make it look good again if you really know that, that is the right thing to do).
For first-class functions to be convenient, minimally you need a terse syntax for in-line functions, the ability to call function values as you would normal functions, and closures. (this last, fortunately, all of the above support) I'd argue that language support for currying is also extremely valuable and difficult to live without, because it greatly increases the situations in which a given function is useful. It's frustrating to me that mainstream "scripting" languages like JS, Lua, and Ruby can't get all of these aspects right - I hope for pattern matching and ADTs in a mainstream language, too, but I'm still waiting for a good implementation of first-class functions to arrive!
It was an interesting project, because almost everything I could find about implementing pattern-matching assumed the patterns could be analyzed at compile time, rather than building some kind of dispatch tree at runtime. After trying some more elaborate methods (e.g. building a decision tree via CPS), I figured out that just indexing (on the first field, by default) and then doing linear search within the index's patterns got 90% of the benefit with very little runtime analysis.
E.g. I start with a high level flow of a program.
int main() {
outputData( processData( getData() ) );
}
int @getData() {
return 0;
}
int @processData(int param1) {
}
void @outputData(int param1) {
}
As more function calls are added, each compilation generates more provisional functions, which can be filled out. Also as the completed function's parameters and types become concrete, the compiler can update the provisional caller or callee functions.
This kind of help from a compiler can really make test-driven development easy. I can write the tests first that make calls to yet-to-exist functions and the compiler generate the provisional version for me. And the tests run right the way.
Also, working with partial information complicates the type inference; in your example, at best, it could infer () -> `a for getData, `a -> `b for processData, and `b -> () for outputData.
In some languages (such as Smalltalk, Lua, and Ruby), there is an explicit "message not understood" hook that is called when a nonexistent function is referenced, and you can define stub behavior there.
The "message not understood" hook in dynamic languages is good for runtime handling of missing functions, but I actually want the compiler to generate the source code for the provisional functions, to make exploratory development easier.
I tend to write code bottom-up rather than top-down, testing it in a REPL and/or with tests, but have Emacs functions to generate boilerplate for languages that need it.
The foundation of OO approach is modeling system as it is with all its complexity. This approach is cheaper, ie. easy on the brain, yet it results in the much more unnecessary complex, bloated, system. The same, structurally, code is multiplied through the system because it is bound to different data. Please spare me lectures about how it is an incorrect approach - you'd insult hundreds, if not thousands, of smart people whose source code i've seen during the last almost 20 years. You can look yourself at any OO project in the open source or at your workplace.