Why are there so many of these "I finally understand [cloures | pointers | misc CS concept]" posts? I mean these are pretty fundamental concepts that any first year CS student should be able to grasp pretty quickly.
"I've finally found an application for closures" is almost as daft as "I've finally found an application for variables".
If you haven't found an application for such-and-such basic programming concept yet, chances are that's because your experience is so limited that you should probably spend more time coding instead of writing ejaculatory blog posts.
(not directed at the parent directly, more at the article, which wasted a minute of my precious life)
Monads are another high-theoretical concept that needs a real-world metaphor. So far, the best one I've heard is the "nuclear waste" one. I've been trying to grok monads for about two years now.
Try this: My goal is to perform an inorder traversal of a binary search tree which stores integers. I wish to multiply each value in the tree by its index in the inorder traversal, so the min item is multiplied by zero and the maximum item by n-1.
How would you write this algorithm? In most languages, you can use mutable state as you are traversing the tree: create a variable called, say, 'i' which is multiplied by the current node, added to the current sum, and incremented after visiting each node.
In a pure functional language, you can't do this. Now imagine how you would implement it: you write a recursive function which accepts the current value of 'i', calls the left subtree, visits the node, increments i, calls the right subtree and returns the sum. But wait: you don't know how many elements were in the subtree, so each recursive call has to return the new value of i. Now you have the problem of "threading" the state of i properly through the different calls, and this is error-prone.
Monads help. You can think of a monad as passing an invisible argument to every function call, and then when that returns, doing something with it. In the case of the State monad, the invisible argument is the current state. The way it is threaded is as follows: when the previous function returns, take its state and execute the next function.
The exciting part about monads is that there are other possible threadings. The Reader monad, for instance, says the following: when the previous function returns, execute the next function. (Throw away the state.) This allows, for instance, read-only configuration data to be passed through your program without specifying it in every argument to every function that might need it. Functions can locally change the configuration data for their subfunctions, but they can't change it for their parents.
A monad is fundamentally a data structure -- an abstract data structure, with a known set of operations. With the State monad above, the data structure is a tuple (s, v) -- the 's' is the state, and the 'v' is the value. The whole thing is what the monadic function returns. The set of operations includes 'bind', which defines the sequencing logic, and 'return', which defines how to insert a value into the data structure (for State, 'return' just leaves the state untouched and puts the value into the monad).
One could think of some different data structures, and see whether they lead themselves to interesting monads. I like the Maybe data type. If you're used to OCaml, this is called Option. It is a variant type: either it contains a value (Just v) or it doesn't (Nothing). So how can this be thought of as a monad?
Here's one proposal: if the previous function returned a value, execute the next function. If it returned Nothing, then return Nothing. (i.e., don't execute the next function at all.)
Is this useful? Potentially. Let's say we want to look up a value in a map, and if it is found, then take some action. If it wasn't found, then don't take any action. The lookup function returns a Maybe value, which you can then sequence (using monadic bind) to the rest of the actions -- the sequencing operation takes care of the "did it succeed?" logic. If the next action doesn't return a Maybe value, then our code must use 'return' to insert its value back into the monad.
There's more. The List monad sequences by passing EACH value in the list to the next operation, and concatenating the results into a new list. The Continuation monad sequences just by executing the next operation, but it provides 'callcc,' which passes the given operation a closure which, when executed, executes the operation following 'callcc'.
Sorry for the brief explanation, I have to run. Ask me questions if you want more.
That was actually understandable! I've run into this "problem" before when playing around with FP, and I never quite knew how to solve it without ugly hacks. Now I know - thanks!
Speaking of which, I don't know why someone hasn't hooked a closure system into html. Think of it, you can bind links to an instance of the website on archive.org -- if eventually it goes down, you can at least recover what the author meant to point to.
Because many of us never were CS undergrads. We formally learnt to program in the context of another field (Mech Eng in my case - FORTRAN, MATLAB and DCL), and prior to that were entirely self-taught. Many of us have many years of experience with procedural and object-oriented styles and are only recently coming to the functional style, either out of pure interest, or out of necessity. So bear with us :-)
This example demands that you understand some domain-specific needs (of a text editor), so it's a little annoying.
But, the main idea is right on the mark. The point is that the natural structure of the code (that uses closures) is completely impossible to achieve without closures.
Maybe now he also understands why objects are often preferable. Closures are liked handicapped objects. Names are resolved when the closures is created, not when it is called. This is not nearly as flexible as an object, where names are resolved when the function is called.
The venerable master Qc Na was walking with his student, Anton. Hoping to prompt the master into a discussion, Anton said "Master, I have heard that objects are a very good thing - is this true?" Qc Na looked pityingly at his student and replied, "Foolish pupil - objects are merely a poor man's closures."
Chastised, Anton took his leave from his master and returned to his cell, intent on studying closures. He carefully read the entire "Lambda: The Ultimate..." series of papers and its cousins, and implemented a small Scheme interpreter with a closure-based object system. He learned much, and looked forward to informing his master of his progress.
On his next walk with Qc Na, Anton attempted to impress his master by saying "Master, I have diligently studied the matter, and now understand that objects are truly a poor man's closures." Qc Na responded by hitting Anton with his stick, saying "When will you learn? Closures are a poor man's object." At that moment, Anton became enlightened.
To be honest, I still don't get it. He says, "Such and such will help you understand closures" and then a few lines of python, then suddenly, "because start_pos is a closure".
Which, really, still doesn't explain what he means. That and for the love of god, I hate things such as Clojure. Call me a stick in the mud, but I like languages in which I don't have to mentally expand 80% of words.
21 comments
[ 605 ms ] story [ 410 ms ] threadI think it's interesting to see how other people solve problems.
If you haven't found an application for such-and-such basic programming concept yet, chances are that's because your experience is so limited that you should probably spend more time coding instead of writing ejaculatory blog posts.
(not directed at the parent directly, more at the article, which wasted a minute of my precious life)
Pointers are easy if you understand the basics of how a computer works and know a language like C.
Likewise, closures are easy when you know a little about functional programming and understand first class functions.
Try this: My goal is to perform an inorder traversal of a binary search tree which stores integers. I wish to multiply each value in the tree by its index in the inorder traversal, so the min item is multiplied by zero and the maximum item by n-1.
How would you write this algorithm? In most languages, you can use mutable state as you are traversing the tree: create a variable called, say, 'i' which is multiplied by the current node, added to the current sum, and incremented after visiting each node.
In a pure functional language, you can't do this. Now imagine how you would implement it: you write a recursive function which accepts the current value of 'i', calls the left subtree, visits the node, increments i, calls the right subtree and returns the sum. But wait: you don't know how many elements were in the subtree, so each recursive call has to return the new value of i. Now you have the problem of "threading" the state of i properly through the different calls, and this is error-prone.
Monads help. You can think of a monad as passing an invisible argument to every function call, and then when that returns, doing something with it. In the case of the State monad, the invisible argument is the current state. The way it is threaded is as follows: when the previous function returns, take its state and execute the next function.
The exciting part about monads is that there are other possible threadings. The Reader monad, for instance, says the following: when the previous function returns, execute the next function. (Throw away the state.) This allows, for instance, read-only configuration data to be passed through your program without specifying it in every argument to every function that might need it. Functions can locally change the configuration data for their subfunctions, but they can't change it for their parents.
Was this helpful? I can continue, if you wish.
A monad is fundamentally a data structure -- an abstract data structure, with a known set of operations. With the State monad above, the data structure is a tuple (s, v) -- the 's' is the state, and the 'v' is the value. The whole thing is what the monadic function returns. The set of operations includes 'bind', which defines the sequencing logic, and 'return', which defines how to insert a value into the data structure (for State, 'return' just leaves the state untouched and puts the value into the monad).
One could think of some different data structures, and see whether they lead themselves to interesting monads. I like the Maybe data type. If you're used to OCaml, this is called Option. It is a variant type: either it contains a value (Just v) or it doesn't (Nothing). So how can this be thought of as a monad?
Here's one proposal: if the previous function returned a value, execute the next function. If it returned Nothing, then return Nothing. (i.e., don't execute the next function at all.)
Is this useful? Potentially. Let's say we want to look up a value in a map, and if it is found, then take some action. If it wasn't found, then don't take any action. The lookup function returns a Maybe value, which you can then sequence (using monadic bind) to the rest of the actions -- the sequencing operation takes care of the "did it succeed?" logic. If the next action doesn't return a Maybe value, then our code must use 'return' to insert its value back into the monad.
There's more. The List monad sequences by passing EACH value in the list to the next operation, and concatenating the results into a new list. The Continuation monad sequences just by executing the next operation, but it provides 'callcc,' which passes the given operation a closure which, when executed, executes the operation following 'callcc'.
Sorry for the brief explanation, I have to run. Ask me questions if you want more.
Lincoln
I'm going to have to do a bit more reading on this and try some experiments I think. Can't wait for Real World Haskell to ship!
But, the main idea is right on the mark. The point is that the natural structure of the code (that uses closures) is completely impossible to achieve without closures.
Great stuff! I think the author gets it. :-)
Counter example:
list(1, 2, 3, 4) map(+(1))
http://iolanguage.com/
Chastised, Anton took his leave from his master and returned to his cell, intent on studying closures. He carefully read the entire "Lambda: The Ultimate..." series of papers and its cousins, and implemented a small Scheme interpreter with a closure-based object system. He learned much, and looked forward to informing his master of his progress.
On his next walk with Qc Na, Anton attempted to impress his master by saying "Master, I have diligently studied the matter, and now understand that objects are truly a poor man's closures." Qc Na responded by hitting Anton with his stick, saying "When will you learn? Closures are a poor man's object." At that moment, Anton became enlightened.
Which, really, still doesn't explain what he means. That and for the love of god, I hate things such as Clojure. Call me a stick in the mud, but I like languages in which I don't have to mentally expand 80% of words.