The weekend spent on absorbing information relating to P's relation to NP, I shall now solidify my understandings through regurgitation of what I've understood.
First, the types of texts that I've found either went deep into the topic (from the theoretical perspective) or brushed lightly upon it (the way a book on programming treats mathematics). I'll try to walk a fine line between both while maintaining clarity. Hopefully it works.
What are P and NP?
These have to do with timing. Not in seconds, but in 'effort'. For example, consider sorting books in a book-shelf. You could scan through the 'N' books to sort, find the smallest one (or whatever sorting criteria you want), and put it at the beginning of the shelf. This operation could be repeated for the remaining books. So, to sort 'N' books, you'd look at (on average) 'N/2' books to find the next one to place to the left of the shelf. That involves looking at 'N^(N/2)' books. In the big picture, we say 'N^N' (N to the N) operations will be needed. As the number of books increase, this method of sorting will be excruciatingly slow. It is left as an exercise to the reader to translate looking at book titles to actual time.
They also have something to do with 'polynomial time'. That is, a number that can be expressed in the form of 'N^x' where 'N' is the number of elements to work on and 'x' is a constant. Sorting books according to our previous example takes much longer than polynomial time (think of very large 'N').
P looks at problems that take polynomial time. Specifically, deterministic problems. Typically involving Turing machines (but I don't want to go into the details of tapes). Essentially, any problem whose solution expressed as a series of unambiguous steps takes polynomial time is in P.
And NP also looks at problems that take polynomial time. This time, problems whose solution is expressed non-deterministically. Back to our book sorting problem, we looked at 'N/2' books (on average) to find the next book to place on the shelf. But what if we just 'looked at all the books at once' and happened to pick the right one. Something similar goes on with 'Oracle machines'. However, NP is easier to understand as the time it takes to verify the problem. In other words, our book sorting would take 'N' time in non-deterministic polynomial time (NP-time)
And why is P versus NP important?
The crux of the problem: are all the problems in NP also part of P? Essentially, NP problems are easy to verify but can be hard to compute. Like our sorting problem, we only need to inspect each book once to confirm that they are sorted. Similar ideas are used in cryptography -- a very difficult problem must be solved by the person who attempts to intercept the message.
Problems in P are those that are practically solvable (well, practically this is debatable, theoretically this is true). There are problems that are much more difficult. Let's call these NP-Complete (ok, technically NP-Complete problems are a class of problems where if one is easily solved then all of them can be easily solved. They are very difficult to solve though). For example, given a series of numbers, find the subset whose sum is the greatest. Short of attempting every possible combination of numbers, a solution is hard to find (programmers may chime in with 'dynamic programming' rolling off their tongue. But, that just stores intermediate results, all potential combinations are still evaluated.).
Back to encryption, if P = NP then there is a way to easily decrypt data. From what I read, a lot of things would become much easier.
But that is the essential nature of P = NP as far as I can tell for now. I might change my mind as I become more informed.
Monday, July 25, 2011
Friday, July 22, 2011
Haskell to Solve Programming Challenges
There are times when I do silly things. This is one of them. Here are my solutions to the first 3 problems for the June 2011 Waterloo Local Contest (http://plg1.cs.uwaterloo.ca/~acm00/) -- not the most difficult, but good enough given my knowledge of Haskell.
So... Let's start with the game of 31. Just call the method `finishGame` with the input string. It runs quite fast.
import List
-- Get the score from a list that is the game
scoreForGame :: (Integral a) => [a] -> a
scoreForGame x = foldl (+) 0 x
-- Change an int into a list
gameFromInt :: (Integral a) => a -> [a]
gameFromInt 0 = []
gameFromInt x = (x `mod` 10) : gameFromInt (x `div` 10)
-- Obtain the player for a game
data Player = A | B deriving (Show)
playerFromGame :: (Integral a) => [a] -> Player
playerFromGame x = if (even $ length x) then B else A
otherPlayer :: Player -> Player
otherPlayer B = A
otherPlayer A = B
-- Score a single move
scoreMove :: (Integral a) => a -> [a] -> a -> a
scoreMove score deck play
| score + play > 31 = -1
| otherwise = if (elem 1 $ map (scoreMove (score+play) deckMinusPlay) (nub deckMinusPlay)) then -1 else 1
where deckMinusPlay = delete play deck
-- Generate deck
deck :: (Integral a) => [a]
deck = [1..6] ++ [1..6] ++ [1..6] ++ [1..6]
-- Finish the game!
-- Takes the game and writes out the winner!
finishGame :: (Integral a) => a -> Player
finishGame a = if (r > 0) then p else otherPlayer p
where
d = deck \\ sort g
g = gameFromInt a
s = scoreForGame g
p = playerFromGame g
r = if (elem 1 $ map (scoreMove s d) (nub d) ) then -1 else 1
Ok. That actually wasn't that bad. And it worked. Some people might complain that scoreMove returns 1 if the current player wins else -1 -- and keeps flipping the numbers between invocations. Note that I check to see if the element is 1 rather than the more intuitive maximum as this allows Haskell to do lazy evaluation (on the first 1 found within the map over elements in deck stop processing since the player won!).
The \\ operator was a challenge to find. It's great! In `List', it subtracts the elements between lists. Eg, [1,2,3,4,5] \\ [2,3] = [1,4,5].
On to problem 2. Factoring large numbers. Actually, using Haskell is probably cheating as you need to maintain a list of prime numbers to at least finish in 30 seconds (Haskell cached it for me)... The code is quite simple:
import Control.Parallel
-- Generate an infinite list of primes?!
divides :: (Integral a) => a -> [a] -> Bool
divides _ [] = False
divides n (x:xs)
| x*x <= n = (n `mod` x == 0) || (divides n xs)
| otherwise = False
firstPrime' :: (Integral a) => [a] -> a -> a
firstPrime' (p:primes) value
| (value `mod` p == 0) = p
| p*p > value = value
| otherwise = firstPrime' primes value
firstPrime :: (Integral a) => a->a
firstPrime = firstPrime' primes
nextPrimes :: (Integral a) => a -> [a] -> [a]
nextPrimes trial primes
| (divides trial primes) = nextPrimes (trial+2) primes
| otherwise = trial:(nextPrimes (trial+2) (primes ++ [trial]))
primes :: (Integral a) => [a]
primes = 2:3:(nextPrimes 5 [3])
-- Return all the factors of a!
factor :: (Integral a) => a -> [a]
factor 1 = []
factor a = p:(factor $ a `div` p)
where p = firstPrime a
main :: IO ()
main = do
print $ factor 90
print $ factor 1234567891
print $ factor 18991325453139
print $ factor 18991325453143
print $ factor 18991325453141
print $ factor 12745267386521023
One comment I should make, lazy evaluation was essential! Also, I am aware that (primes ++ [trial]) will do a complete list traversal of primes to append a single element. Without that, the recursion was destroying the performance on the divides and firstPrime'. In total, it's about 19 seconds to run. Slower when more CPU is used...
Next off! Computing the fibonacci sequence. Once it hit me that I should try to avoid recursion (it's so natural) then I got this very nice and very fast solution:
import Control.Parallel
fib :: (Integral n) => n -> n
fib 1 = 1
fib 2 = 1
fib x = (fib $ x-1) + (fib $ x-2)
fibList' :: Integer -> Integer -> [Integer]
fibList' m1 m2 = m2:(fibList' (m2+m1) m1)
fibList :: [Integer]
fibList = (fibList' 1 1)
fib'' :: [Integer] -> Integer -> Integer
fib'' (x:xs) n
| n <= 1 = x
| otherwise = fib'' xs (n-1)
fib' :: Integer -> Integer
fib' = fib'' fibList
main :: IO ()
main = do
print $ fib' 100
print $ fib' 997
print $ fib' 1000
print $ fib' 1009
print $ fib' 4500
I think for this 3rd problem, the challenge was to work with very large numbers efficiently. Which Haskell does automagically.
Why infinite lists? lazy evaluation is the answer! I find it makes the algorithm cleaner even though a few things had to be shuffled around. I did have fun typing fibList and seeing all the numbers in the fibonacci sequence appear. And hopefully, written in this way it can cache intermediate results (but it runs so fast I don't think it even matters)!
Done a few programming challenges for the day!
So... Let's start with the game of 31. Just call the method `finishGame` with the input string. It runs quite fast.
import List
-- Get the score from a list that is the game
scoreForGame :: (Integral a) => [a] -> a
scoreForGame x = foldl (+) 0 x
-- Change an int into a list
gameFromInt :: (Integral a) => a -> [a]
gameFromInt 0 = []
gameFromInt x = (x `mod` 10) : gameFromInt (x `div` 10)
-- Obtain the player for a game
data Player = A | B deriving (Show)
playerFromGame :: (Integral a) => [a] -> Player
playerFromGame x = if (even $ length x) then B else A
otherPlayer :: Player -> Player
otherPlayer B = A
otherPlayer A = B
-- Score a single move
scoreMove :: (Integral a) => a -> [a] -> a -> a
scoreMove score deck play
| score + play > 31 = -1
| otherwise = if (elem 1 $ map (scoreMove (score+play) deckMinusPlay) (nub deckMinusPlay)) then -1 else 1
where deckMinusPlay = delete play deck
-- Generate deck
deck :: (Integral a) => [a]
deck = [1..6] ++ [1..6] ++ [1..6] ++ [1..6]
-- Finish the game!
-- Takes the game and writes out the winner!
finishGame :: (Integral a) => a -> Player
finishGame a = if (r > 0) then p else otherPlayer p
where
d = deck \\ sort g
g = gameFromInt a
s = scoreForGame g
p = playerFromGame g
r = if (elem 1 $ map (scoreMove s d) (nub d) ) then -1 else 1
Ok. That actually wasn't that bad. And it worked. Some people might complain that scoreMove returns 1 if the current player wins else -1 -- and keeps flipping the numbers between invocations. Note that I check to see if the element is 1 rather than the more intuitive maximum as this allows Haskell to do lazy evaluation (on the first 1 found within the map over elements in deck stop processing since the player won!).
The \\ operator was a challenge to find. It's great! In `List', it subtracts the elements between lists. Eg, [1,2,3,4,5] \\ [2,3] = [1,4,5].
On to problem 2. Factoring large numbers. Actually, using Haskell is probably cheating as you need to maintain a list of prime numbers to at least finish in 30 seconds (Haskell cached it for me)... The code is quite simple:
import Control.Parallel
-- Generate an infinite list of primes?!
divides :: (Integral a) => a -> [a] -> Bool
divides _ [] = False
divides n (x:xs)
| x*x <= n = (n `mod` x == 0) || (divides n xs)
| otherwise = False
firstPrime' :: (Integral a) => [a] -> a -> a
firstPrime' (p:primes) value
| (value `mod` p == 0) = p
| p*p > value = value
| otherwise = firstPrime' primes value
firstPrime :: (Integral a) => a->a
firstPrime = firstPrime' primes
nextPrimes :: (Integral a) => a -> [a] -> [a]
nextPrimes trial primes
| (divides trial primes) = nextPrimes (trial+2) primes
| otherwise = trial:(nextPrimes (trial+2) (primes ++ [trial]))
primes :: (Integral a) => [a]
primes = 2:3:(nextPrimes 5 [3])
-- Return all the factors of a!
factor :: (Integral a) => a -> [a]
factor 1 = []
factor a = p:(factor $ a `div` p)
where p = firstPrime a
main :: IO ()
main = do
print $ factor 90
print $ factor 1234567891
print $ factor 18991325453139
print $ factor 18991325453143
print $ factor 18991325453141
print $ factor 12745267386521023
One comment I should make, lazy evaluation was essential! Also, I am aware that (primes ++ [trial]) will do a complete list traversal of primes to append a single element. Without that, the recursion was destroying the performance on the divides and firstPrime'. In total, it's about 19 seconds to run. Slower when more CPU is used...
Next off! Computing the fibonacci sequence. Once it hit me that I should try to avoid recursion (it's so natural) then I got this very nice and very fast solution:
import Control.Parallel
fib :: (Integral n) => n -> n
fib 1 = 1
fib 2 = 1
fib x = (fib $ x-1) + (fib $ x-2)
fibList' :: Integer -> Integer -> [Integer]
fibList' m1 m2 = m2:(fibList' (m2+m1) m1)
fibList :: [Integer]
fibList = (fibList' 1 1)
fib'' :: [Integer] -> Integer -> Integer
fib'' (x:xs) n
| n <= 1 = x
| otherwise = fib'' xs (n-1)
fib' :: Integer -> Integer
fib' = fib'' fibList
main :: IO ()
main = do
print $ fib' 100
print $ fib' 997
print $ fib' 1000
print $ fib' 1009
print $ fib' 4500
I think for this 3rd problem, the challenge was to work with very large numbers efficiently. Which Haskell does automagically.
Why infinite lists? lazy evaluation is the answer! I find it makes the algorithm cleaner even though a few things had to be shuffled around. I did have fun typing fibList and seeing all the numbers in the fibonacci sequence appear. And hopefully, written in this way it can cache intermediate results (but it runs so fast I don't think it even matters)!
Done a few programming challenges for the day!
Sunday, July 17, 2011
Branding the Perfect Image
Perfection. The opposite of being human. How interesting.
We accept nothing but perfection from the leaders of the world. Some brands attempt to portray themselves as perfect, hiding faults to promote products (unless legally obliged). And now branding seems to be entering the world of social media, with people participating in campaigns for some reward (or without realizing it).
As people get brought into this mess of branding / advertising, their language must be monitored. Bad things may not be said (in the past nor the future as everything is recorded for infinity - easily searched). Even a minor mistake, redacted, can spread like wildfire as it gets cached (remembered) within various minds, machines, and search engines. Who will control what this legion of unwashed masses does to help promote a brand?
Why do I bring this up? Some people use social media to socialize, voice honest opinions. Others use the media to present an image of themselves. The latter is useful for brands as they play the game of perfection. The former can get the message across but will not let hesitate to post an honest idea. SLAPPs are probably the best vehicle to keep everyone in line.
What makes the social media useful are the honest opinions. Those that call out defects, problems, lemons if you will. Attempting to use this word of mouth to spread a fixed message appears to be restricted to the set of people willing to appear perfect.
People aren't perfect.
Sunday, July 10, 2011
In Search of Software Simplicity
15 years ago I was making small video-games as a hobbyist. The games were simple, pushing QBasic to its limits.
Jump forward to today, 2011, and I'm still making video-games as a hobbyist. The software development landscape has greatly changed. Things look nicer, and the complexity of software development has jumped. I try to keep up by abstracting away concepts.
The last concept I tried to abstract away was physics. Of course there are plenty of physics engines out there, but I believe it is best that I understand how these work. And more often than not, they are too powerful for what I wish to develop.
Even my simplistic set of objects are often times overkill for what I wish to do...
The last object I created, which I should have created a long time ago, is called "Angle". It allows me to take and compare angles (even though they only exist between -PI and PI). Something that makes my software more error prone and has greatly helped in reducing bugs.
Another object that I have is "Particle". It's a point in space (2D or 3D) that has certain physical properties such as mass, velocity, etc. A character is in essence a particle (it shares the same properties). But, it can not go through anything. So, should I infuse, within particle, all the potential logic to handle the case where it is within a bounding box that can collide with this specific world, or should I implement a custom type of object.
The arguments against the custom object are well known. Code reuse.
But the arguments for creating a custom object are also strong: Polluting a clean code-base for a one-time-use object is not worth it. The particle object need not be that complex - leaving it simple means I can more easily reuse it when the time comes.
What if something else needs this code? Then I'll worry about abstraction. No use abstracting away something when I'm prototyping. The goal isn't a library but something to test the feasibility. The library is just a nice side-effect that happens when I try to keep track of the big picture.
Maybe code reuse is not the ultimate in software simplicity.
I'll leave this rant on one final note: there once was an article (I believe the Daily WTF) which talked about the added efficiency of using the built-in functions to delete folders rather than recursively deleting folders. Then it came to me, wouldn't it be more obvious if the right solution were to combine "fmap" with the "delete function" and a "file list"...
Complexity from combinations of simple elements, what a great thought!
Jump forward to today, 2011, and I'm still making video-games as a hobbyist. The software development landscape has greatly changed. Things look nicer, and the complexity of software development has jumped. I try to keep up by abstracting away concepts.
The last concept I tried to abstract away was physics. Of course there are plenty of physics engines out there, but I believe it is best that I understand how these work. And more often than not, they are too powerful for what I wish to develop.
Even my simplistic set of objects are often times overkill for what I wish to do...
The last object I created, which I should have created a long time ago, is called "Angle". It allows me to take and compare angles (even though they only exist between -PI and PI). Something that makes my software more error prone and has greatly helped in reducing bugs.
Another object that I have is "Particle". It's a point in space (2D or 3D) that has certain physical properties such as mass, velocity, etc. A character is in essence a particle (it shares the same properties). But, it can not go through anything. So, should I infuse, within particle, all the potential logic to handle the case where it is within a bounding box that can collide with this specific world, or should I implement a custom type of object.
The arguments against the custom object are well known. Code reuse.
But the arguments for creating a custom object are also strong: Polluting a clean code-base for a one-time-use object is not worth it. The particle object need not be that complex - leaving it simple means I can more easily reuse it when the time comes.
What if something else needs this code? Then I'll worry about abstraction. No use abstracting away something when I'm prototyping. The goal isn't a library but something to test the feasibility. The library is just a nice side-effect that happens when I try to keep track of the big picture.
Maybe code reuse is not the ultimate in software simplicity.
I'll leave this rant on one final note: there once was an article (I believe the Daily WTF) which talked about the added efficiency of using the built-in functions to delete folders rather than recursively deleting folders. Then it came to me, wouldn't it be more obvious if the right solution were to combine "fmap" with the "delete function" and a "file list"...
Complexity from combinations of simple elements, what a great thought!
Friday, July 1, 2011
My Latest Haskell Experiments
Many moons have risen in the night sky as I tried with great difficulty to become a Haskell master. Lacking knowledge of category theory and Monads being this abstract notion with no concrete definition. My infatuation with the language began with the desire to write a better programming language where I could express select computations and generate code to optimally handle a variety of data structures. Haskell expressed purity in its functioning and strict type checking. Winner it clearly was.
This year, marking at least the third, I have again revisited Haskell. No language has managed to elude me before. I will figure this one out. This year, a book I have invested in. A book I have read cover to cover. Another attempt at writing a code generator followed.
As I programmed Prolog, my mind always translated the code to it's sequential equivalent. If this is done, then all possibilities are recursively enumerated until a solution is found.
Haskell, with Monads, is another story. My problem was this silly attempt to maintain an imperative mindset rather than thinking functionally. Hence, now I will document what I have discovered -- as many must have done before. For someone wiser than I who can extrapolate the interesting portions and run forward -- someone who wishes to see how the thinking differs. For tutorials, many have written much better texts than I could.
I'll start with the concept of laziness. Haskell is lazy. In an imperative language, suppose you had a for loop. As long as it writes to a memory location (or potentially could write to a memory location) it will be run. Haskell takes a goal and follows a chain of dependencies until it has finished the calculation at hand. Back to our for loop, this means the compiler (or language) would need to provide a way to determine if a given write to a memory address will actually impact the resulting computation in the future. This is possible for certain local computations on the stack, but anything dealing with shared objects is next to impossible. Forget about static memory locations.
If we logically follow this path of thought, it means that Haskell has some restrictions on the language to allow it to do such reasoning. Two things come to mind. First global non-constant variables must go. Suppose an object were to change a global variable, how would it know that no other object were to access that variable? It becomes impossible with libraries unless everything must register for the data it will read from a-priori.
Actually, for the second thing, local variables as well should be constant. Parameters passed to functions should be constant. As should be the return values. Essentially, all data becomes immutable. Why do we want this? All computations can now be represented as an acyclic graph. You can start with a variable -- it is computed by calling a function, let's say. That function's input is known, and the result is computed from information that is known. So, let's say every computation that must be done for any value is known. Then all that you need is to look at the graph of computations, only compute the nodes (that hold the operations) whose result benefits the desired computation at hand.
Some may wonder about determinism. That is covered by the second thing. If every variable is constant and can only change by creating a new constant whose value is computed by a series of predictable constant values then a function will always return the same output for a given input.
Implied by determinism and constant everything is the need for recursion. Why recursion? It creates more stack space to put constant values. It also creates a framework to destroy values when they are no longer needed.
So that leads us to state... how do we manage state? Here, Haskell is very elegant. Imagine you have an object that represents state. Manipulating that object returns a new state object. That old state object is discarded and the new one is used. Haskell provides ways to automate this process. This is the last piece of mind-bending...
Consider a multi-parameter function that returns a single value. Suppose you gave a single parameter to the function and a new function was created with one-less parameter. Let's call the first parameter the state and the return value is a combination of the state and some value (which we have yet to define).
Now, let's create functions that work on two inputs (the state and the data) and outputs two things (the state and the data). The first function takes in a function, state, data, and outputs state and data. Suppose the function to our function just manipulates data based on the current state.
A bit mind-bending, but now the state management is separated from the computations. This doesn't always work, but when it does it's quite neat. Error handling can be simplified in a similar way. The error state can be a container that checks return values to make sure they are valid. Push the idea further, since it's a function calling a function doing the actual work, the function that does the calling can first ensure that only non-error states can continue computations. Want an exception state? sure, have a function that takes two functions (the second only gets called on error).
Let's push this a bit further. Our error functions last parameter is the data, but the first is the state. Recall that we can assign values to the first parameters to create new functions? Now, push this further and say assign a function with the promise to evaluate the results if successful. In C this might look like: eval(func1, data1, eval(func2, data2, eval(func3, data3, ...)))... Messy. In Haskell: eval func1 data1 $ eval func2 data2 $ eval func3 data3. Read it backwards...
Isn't that cleaner? I'd need to get back to the book to give further insights as I'm too quickly jumping into Monads... But, I think the point is made.
Haskell glues functions within functions (think containers) to abstract away computations. Error handling can be seen as a series of functions. As is state maintenance. The typical machinery for this is a Monad.
Ok, quickly. Monads. Monads just say that a given object (some type of state) wraps another object (computation). They define operators that must function for each Monad, and each Monad must conform to a set of rules so they behave as other programmers expect.
First, a Monad should be able to take a computation object and wrap it in a state object. Second, given a function operating on the data, the Monad should be able to do the computations exactly as though they were done devoid of state. Last, computations should give the same result no matter the order. (a*b)*c = a*(b*c).
Well, something like that. The concept, for a person used to the imperative style, should see a consistent use of the class adapter pattern. The adaptee is the computation, the client is the state.
This year, marking at least the third, I have again revisited Haskell. No language has managed to elude me before. I will figure this one out. This year, a book I have invested in. A book I have read cover to cover. Another attempt at writing a code generator followed.
As I programmed Prolog, my mind always translated the code to it's sequential equivalent. If this is done, then all possibilities are recursively enumerated until a solution is found.
Haskell, with Monads, is another story. My problem was this silly attempt to maintain an imperative mindset rather than thinking functionally. Hence, now I will document what I have discovered -- as many must have done before. For someone wiser than I who can extrapolate the interesting portions and run forward -- someone who wishes to see how the thinking differs. For tutorials, many have written much better texts than I could.
I'll start with the concept of laziness. Haskell is lazy. In an imperative language, suppose you had a for loop. As long as it writes to a memory location (or potentially could write to a memory location) it will be run. Haskell takes a goal and follows a chain of dependencies until it has finished the calculation at hand. Back to our for loop, this means the compiler (or language) would need to provide a way to determine if a given write to a memory address will actually impact the resulting computation in the future. This is possible for certain local computations on the stack, but anything dealing with shared objects is next to impossible. Forget about static memory locations.
If we logically follow this path of thought, it means that Haskell has some restrictions on the language to allow it to do such reasoning. Two things come to mind. First global non-constant variables must go. Suppose an object were to change a global variable, how would it know that no other object were to access that variable? It becomes impossible with libraries unless everything must register for the data it will read from a-priori.
Actually, for the second thing, local variables as well should be constant. Parameters passed to functions should be constant. As should be the return values. Essentially, all data becomes immutable. Why do we want this? All computations can now be represented as an acyclic graph. You can start with a variable -- it is computed by calling a function, let's say. That function's input is known, and the result is computed from information that is known. So, let's say every computation that must be done for any value is known. Then all that you need is to look at the graph of computations, only compute the nodes (that hold the operations) whose result benefits the desired computation at hand.
Some may wonder about determinism. That is covered by the second thing. If every variable is constant and can only change by creating a new constant whose value is computed by a series of predictable constant values then a function will always return the same output for a given input.
Implied by determinism and constant everything is the need for recursion. Why recursion? It creates more stack space to put constant values. It also creates a framework to destroy values when they are no longer needed.
So that leads us to state... how do we manage state? Here, Haskell is very elegant. Imagine you have an object that represents state. Manipulating that object returns a new state object. That old state object is discarded and the new one is used. Haskell provides ways to automate this process. This is the last piece of mind-bending...
Consider a multi-parameter function that returns a single value. Suppose you gave a single parameter to the function and a new function was created with one-less parameter. Let's call the first parameter the state and the return value is a combination of the state and some value (which we have yet to define).
Now, let's create functions that work on two inputs (the state and the data) and outputs two things (the state and the data). The first function takes in a function, state, data, and outputs state and data. Suppose the function to our function just manipulates data based on the current state.
A bit mind-bending, but now the state management is separated from the computations. This doesn't always work, but when it does it's quite neat. Error handling can be simplified in a similar way. The error state can be a container that checks return values to make sure they are valid. Push the idea further, since it's a function calling a function doing the actual work, the function that does the calling can first ensure that only non-error states can continue computations. Want an exception state? sure, have a function that takes two functions (the second only gets called on error).
Let's push this a bit further. Our error functions last parameter is the data, but the first is the state. Recall that we can assign values to the first parameters to create new functions? Now, push this further and say assign a function with the promise to evaluate the results if successful. In C this might look like: eval(func1, data1, eval(func2, data2, eval(func3, data3, ...)))... Messy. In Haskell: eval func1 data1 $ eval func2 data2 $ eval func3 data3. Read it backwards...
Isn't that cleaner? I'd need to get back to the book to give further insights as I'm too quickly jumping into Monads... But, I think the point is made.
Haskell glues functions within functions (think containers) to abstract away computations. Error handling can be seen as a series of functions. As is state maintenance. The typical machinery for this is a Monad.
Ok, quickly. Monads. Monads just say that a given object (some type of state) wraps another object (computation). They define operators that must function for each Monad, and each Monad must conform to a set of rules so they behave as other programmers expect.
First, a Monad should be able to take a computation object and wrap it in a state object. Second, given a function operating on the data, the Monad should be able to do the computations exactly as though they were done devoid of state. Last, computations should give the same result no matter the order. (a*b)*c = a*(b*c).
Well, something like that. The concept, for a person used to the imperative style, should see a consistent use of the class adapter pattern. The adaptee is the computation, the client is the state.
Saturday, April 23, 2011
Organic Game Creation
What makes a video-game fun? Could it be that the construction process embeds itself within the gameplay? A fun construction process yields a fun game. A boring process yields more of the same (not that it isn't good, but not great).
For the past year, I've been trying to make games whose control scheme was easy. Focusing on usability. But that's not how I design games. Design is such a harsh word filled with connotations which are negative in this discourse and my lines of reasoning, let's say "create". If I were to paint a portrait, I would not design that much. I would plan a general feel for the portrait, and let the portrait come to life through the process of adding lines. Wouldn't it be silly to plan where the lines go and send it off to someone else?
The best games that I have created were the ones where I did not care about usability initially. They were intended to be fun and challenge people. Some were easy. Others very difficult. They each started as a sketch, an overall idea of how things were placed. Then details got filled in gradually. Adding features that I (egoistically) enjoyed, and removed others.
Like when I draw, I can never predict the final outcome of a game I create. There is a sense of what it may look like, but the final version is always a surprise. It took me at least a year to figure out this process which counters the current industry standard.
Now to push forward my prototypes and see which survive. May the best be submitted to the App Store (and hopefully accepted) for all to enjoy.
I can not yet fully argue about process being reflected in gameplay, but I am more than certain now that it is the case.
Sunday, April 3, 2011
Canadian Politics: Rants
A week into the campaign, and there are signs and commercials abound for the various parties.
The Conservatives are attacking Ignatieff. Ignatieff says something along the lines that he is the only one who speaks for the Liberals... that doesn't sound menacing at all... it sounds like the impression that I have of Harper -- he is the one that speaks for the Conservatives. I call it fear-mongering. It was bad enough last election... I miss the educated responses.
Speaking of educated responses, the debate is coming up. These have degraded over time. It is getting ridiculous. Last one, each person stuck to (as much as humanly possible) reiterating slogans and avoiding questions. Well, that's what I recall anyway.
And of memory... it's this short-term memory of people that is allowing politicians to get away with so much stuff. How is it that Harper can be against a coalition but have proposed one when it was to his advantage? (and how accurate is this statement given everyone lies -- white lies maybe -- to their advantage).
I can't blame people for their indifference to the political scene. Sometimes I feel that these people in power are fighting more to retain their job rather than get stuff done. For example, Conservatives with a budget to campaign on -- that's silly! Even sillier is the NDP laying out a set of requirements in the budget for their vote... The Conservatives will most likely get in. They will most likely have support of 25% of the population (50% vote, 25% vote for them -- 50% are too jaded and don't care).
Many ask what can be done for the low voter turn-out. I sometimes am tempted to turn in an empty ballot - but that is prone to tampering, so maybe not vote. The only reason to vote, I find, is to show support for a party. Which becomes $2 for whoever I vote for (who typically have no chance of coming to power in the riding I'm in -- Bloc Quebecois currently holds the riding). If the Conservatives do cancel the $2 per vote, I practically have no reason to vote. Go-go Harper! Before we even consider cancelling the $2, there needs change so people have reason to vote.
That gets me started on "strategic voting" -- people voting not for who they think would be best, but voting for who they think has a potential of winning and being the lesser of 2 evils. First-past-the post is nice (representation-wise), but when the representative is planted there and moved around, it makes little sense. And any changes must maintain the ability to elect independents (I seriously consider them more and more as time goes by).
Maybe the Conservatives have something to motivate the voting population. But without a platform, I can't tell.
That leads to my last comment for today. Why aren't the regional representatives put front and centre? Why do I not hear them campaigning? After all, it's not the leader that will speak for the population of a given region but the person campaigning to become an MP.
Actually, the Liberals have a nice nugget in their platform. More transparency, and opening up questions to netizens. Rounding up the hyperactive MPs in parliament and bringing the discourse to that of respectful debate then the distrust in the political class may go away (the last times I listened to parliamentary sessions wasn't to be educated, but for the entertainment. and I paraphrase what one MP said "Yes Mr. Speaker. It is essential that I speak of the incompetence of the previous MP from the opposition" and goes off repeating the same insults at least 3 times so they become true... sigh...).
Subscribe to:
Posts (Atom)