Aspect programming feels to me like adding functional thinking in OO. An article from a few years ago that sounds interesting
http://www.jot.fm/issues/issue_2003_07/column1.pdf and slides http://aosd.net/archive/2003/jacobson-aosd-2003.ppt
Journey From Imperative to Functional Programming
Tuesday, December 20, 2011
Tuesday, March 15, 2011
Friday, January 28, 2011
Monday, January 24, 2011
Wednesday, January 19, 2011
Finding largest rectangular area without trees
In an interview I was asked a question very similar to this or this.
In my version there is a rectangular piece of land with trees on it. We know the coordinates of the land and the location of the trees on the land. Goal is to find the largest contiguous rectangular area within our land that doesn't contain any trees.
Solving these problems require you to develop the properties of the problem that then you can base an algorithm on for which there is no time. My response in the interview was what I consider brute force method of trying to take a square and see how big it can grow. Then try to find the largest one.
But thinking about the problem more I said what if I had a land and one tree. Then I get essentially 4 areas. Now if I have two trees, I should be able to take the areas from the first tree and check to see if the 2nd tree would influence them. If the 2nd tree is inside an area, then it would give me potentially 4 areas to work with. That is the one area is replaced with up to 4 (removing the original one). If there are no tree in the area then the area is unaffected by the 2nd tree. So now I can try the 3rd, 4th... tree. Each time check the effect of the tree on the land. At the end the one with the largest area is my answer. This solution doesn't care about the size of the land, just the number of trees.
Here is what I wrote in Haskell that I think solves the problem. The implementation takes advantage of foldM library to do most of the work. In foldM signature, "a" is my land, "b" is the tree, and "ma" is List of a which is a list of land pieces. Any feedback is appreciated.
In my version there is a rectangular piece of land with trees on it. We know the coordinates of the land and the location of the trees on the land. Goal is to find the largest contiguous rectangular area within our land that doesn't contain any trees.
Solving these problems require you to develop the properties of the problem that then you can base an algorithm on for which there is no time. My response in the interview was what I consider brute force method of trying to take a square and see how big it can grow. Then try to find the largest one.
But thinking about the problem more I said what if I had a land and one tree. Then I get essentially 4 areas. Now if I have two trees, I should be able to take the areas from the first tree and check to see if the 2nd tree would influence them. If the 2nd tree is inside an area, then it would give me potentially 4 areas to work with. That is the one area is replaced with up to 4 (removing the original one). If there are no tree in the area then the area is unaffected by the 2nd tree. So now I can try the 3rd, 4th... tree. Each time check the effect of the tree on the land. At the end the one with the largest area is my answer. This solution doesn't care about the size of the land, just the number of trees.
Here is what I wrote in Haskell that I think solves the problem. The implementation takes advantage of foldM library to do most of the work. In foldM signature, "a" is my land, "b" is the tree, and "ma" is List of a which is a list of land pieces. Any feedback is appreciated.
Sunday, January 16, 2011
How glues make a difference
There are folks that say programming language does matter. Some compare it to glue that allow you freedom to build parts from smaller part. It was hard for me to appreciate this until I saw real examples. What I have learned is that with right glue your imagination can be liberated to think about possibilities and that is what make the choice of language matter.
Lets take the problem of a simple game. Let say you want to write code to implement the paddle ball.
If you think Object Oriented about this game. You see Ball, Paddle, Wall, Score..... OO techniques would give you a great way to organize your code. All the code concerning Ball would be encapsulate in the Ball object. Then the key design decision you need to make for the Ball, Paddle and Wall objects is how to detect collision between Ball and Paddle or Wall. Then figure out who does the bounce of the ball. Is the ball object going to detect the bounce, is the wall telling the ball to bounce... So you put on your "Object Think" hat on. Is it the ball that is detecting the collision, the wall? Hmmmm "Trying to Object Think and nothing is happening. You give up, may be the Collision Manager that watches over all objects is simpler to think about! Object Think => Let manager decide :) You also need to worry about user input controlling the Paddle. Is the code event driven (Inversion of Control) or is it polling for the inputs....
However you decide to slice the implementation among your object, one thing is going to be true. You are only thinking about the objects in the paddle game. At best you may be able to reuse your ideas in similar game. But the design, if you call what you are doing here as design, is adhoc and has very limited potential.
If you step back and drop your OO thinking and start looking at problem differently you be surprised at how all games are the same and hence can be implemented on common model.
If you think of the game as a computation instead of bunch of object then it all looks different. You ask yourself what is nature of the computation in this game? One possible answer is to see the game as Interactive (user controls the paddle via key inputs) Animation (graphics that changes over time). You can further define Animation as time-series (functions of time) graphics. So now you have three different concepts. Interactive, Time-Series, and Graphics. Sum of them would give you the language to express the game while each one of those ideas can be viewed by itself. What would Interactive computation need to have? What would Time-Series computation need? and finally what would Graphics packages need to have to be fully expressive. In all three cases you are asking yourself the compositional needs of each of your concern and define a language for it. For instance, on the graphics you will define a language to have simple shapes, complex shapes as and/or/xor of simple shapes, transposition of shapes..... Most likely you will find an existing library that defines appropriate DSL for each of the concerns of our game.
Ideally you want a programming language that allows you to compose notions (in this case interactive, animation, and graphics) in one grand notion such that you can express your game in. So you say key x causes mouse to go left, or right, ball travels at some velocity (speed and direction), when the ball hits wall or paddle it bounces ( you defined a bounce as change in the direction of velocity). If ball passes the edge it is outside, game is over.. You are done. It is all basically the description of the game. Even better, you can reuse the same notions and may be describe the car racing game. If the approach interest you, you can get more details in SOE.
All of sudden in the new perspective you have something that is truly re-usable. You may be able to implement this in Java too. But the key idea, as we saw here, is that the standard OO techniques leads you to a dead end, you are worrying about non issues and the result has limited potential. Furthermore, where your native language doesn't give you the compositional capabilities you need, you be forced to try to figure out ways to implement them. It may be verbose, ugly and hard to understand which is why most people end up with mainstream usage model of the language.
So that is how the language does matter. Glues make it all possible to build powerful abstraction.
Lets take the problem of a simple game. Let say you want to write code to implement the paddle ball.
If you think Object Oriented about this game. You see Ball, Paddle, Wall, Score..... OO techniques would give you a great way to organize your code. All the code concerning Ball would be encapsulate in the Ball object. Then the key design decision you need to make for the Ball, Paddle and Wall objects is how to detect collision between Ball and Paddle or Wall. Then figure out who does the bounce of the ball. Is the ball object going to detect the bounce, is the wall telling the ball to bounce... So you put on your "Object Think" hat on. Is it the ball that is detecting the collision, the wall? Hmmmm "Trying to Object Think and nothing is happening. You give up, may be the Collision Manager that watches over all objects is simpler to think about! Object Think => Let manager decide :) You also need to worry about user input controlling the Paddle. Is the code event driven (Inversion of Control) or is it polling for the inputs....
However you decide to slice the implementation among your object, one thing is going to be true. You are only thinking about the objects in the paddle game. At best you may be able to reuse your ideas in similar game. But the design, if you call what you are doing here as design, is adhoc and has very limited potential.
If you step back and drop your OO thinking and start looking at problem differently you be surprised at how all games are the same and hence can be implemented on common model.
If you think of the game as a computation instead of bunch of object then it all looks different. You ask yourself what is nature of the computation in this game? One possible answer is to see the game as Interactive (user controls the paddle via key inputs) Animation (graphics that changes over time). You can further define Animation as time-series (functions of time) graphics. So now you have three different concepts. Interactive, Time-Series, and Graphics. Sum of them would give you the language to express the game while each one of those ideas can be viewed by itself. What would Interactive computation need to have? What would Time-Series computation need? and finally what would Graphics packages need to have to be fully expressive. In all three cases you are asking yourself the compositional needs of each of your concern and define a language for it. For instance, on the graphics you will define a language to have simple shapes, complex shapes as and/or/xor of simple shapes, transposition of shapes..... Most likely you will find an existing library that defines appropriate DSL for each of the concerns of our game.
Ideally you want a programming language that allows you to compose notions (in this case interactive, animation, and graphics) in one grand notion such that you can express your game in. So you say key x causes mouse to go left, or right, ball travels at some velocity (speed and direction), when the ball hits wall or paddle it bounces ( you defined a bounce as change in the direction of velocity). If ball passes the edge it is outside, game is over.. You are done. It is all basically the description of the game. Even better, you can reuse the same notions and may be describe the car racing game. If the approach interest you, you can get more details in SOE.
All of sudden in the new perspective you have something that is truly re-usable. You may be able to implement this in Java too. But the key idea, as we saw here, is that the standard OO techniques leads you to a dead end, you are worrying about non issues and the result has limited potential. Furthermore, where your native language doesn't give you the compositional capabilities you need, you be forced to try to figure out ways to implement them. It may be verbose, ugly and hard to understand which is why most people end up with mainstream usage model of the language.
So that is how the language does matter. Glues make it all possible to build powerful abstraction.
Saturday, January 15, 2011
Wiggle room to exploit alternate representations and implementations.
A nice presentation on Parallel programming.
My Favorit slide:
My favorite comment was about the C language having the address of operator (pointers). Whereas a Java program has no such thing and thus JVM can garbage collect knowing that the program is not depending on the memory location as it may have been in C. By giving up the address of operator, the JVM has the wiggle room to implement the garbage collection.
Abstractions are made based on the properties (aka "wiggle room") of the underlying concept.
My Favorit slide:
Algebraic Properties Are Important!
• Associative: grouping doesn’t matter!
• Commutative: order doesn’t matter!
• Idempotent: duplicates don’t matter!
• Identity: this value doesn’t matter!
• Zero: other values don’t matter!
Invariants give the implementation wiggle room, that is, the
freedom to exploit alternate representations and implmentations.
In particular, associativity gives implementations the necessary
wiggle room to use parallelism—or not—as resources dictate.
My favorite comment was about the C language having the address of operator (pointers). Whereas a Java program has no such thing and thus JVM can garbage collect knowing that the program is not depending on the memory location as it may have been in C. By giving up the address of operator, the JVM has the wiggle room to implement the garbage collection.
Abstractions are made based on the properties (aka "wiggle room") of the underlying concept.
Tuesday, January 11, 2011
Monday, January 10, 2011
Insight into continuation and Haskell
A really nice introduction to continuation.
The talk covers Scheme's implementation of Continuation. What is interesting to note is that in language like Scheme, or Java to implement continuation you need hooks in the native language. For instance, in this interview Bill Venners tries to explain the Java CM changes that are required to capture the continuation.
But if you look at Haskell version of continuation, you realize that there are no changes in the underlying language. Continuation, just like Exception handling is implemented as a library (Control.Monad.Control.ContT). Even delimited continuation can be done as a library: MonadCont or CC-delcont.
The talk covers Scheme's implementation of Continuation. What is interesting to note is that in language like Scheme, or Java to implement continuation you need hooks in the native language. For instance, in this interview Bill Venners tries to explain the Java CM changes that are required to capture the continuation.
But if you look at Haskell version of continuation, you realize that there are no changes in the underlying language. Continuation, just like Exception handling is implemented as a library (Control.Monad.Control.ContT). Even delimited continuation can be done as a library: MonadCont or CC-delcont.
Thursday, January 6, 2011
Nice talk....
The "Monadologie: Professional Help for Type Anxiety" talk by Chris League does nice job explaining:
* CPS and Delimited Continuation
* Application of Continuation to Parsing
* State monad application to the tree injection.
* CPS and Delimited Continuation
* Application of Continuation to Parsing
* State monad application to the tree injection.
Monadologie: Professional Help for Type Anxiety from Nathan Hamblen on Vimeo.
Subscribe to:
Posts (Atom)