| Framing 3d objects |
[21 Jul 2009|09:58pm] |
Today I ran into some code in Spore that has to do with framing pictures of creations. The problem is this: given some object created by the user, come up with a camera which takes a picture of that object.
The code worked by placing the object in front of a camera, then incrementally moving the camera around until the object fits. This is obviously inefficient. ( So today I wanted to figure out how to frame objects efficiently )
|
|
| Applicative Functors |
[18 Jun 2009|09:28am] |
|
This is a long response to a post about encoding musical patterns in Haskell.
data Pattern a = Pattern {at :: Integer -> [a], period :: Integer}
The problem was in how to make this object into a Monad; I made an argument that it was just an applicative functor instead.
The "essence" of an applicative functor is that it is just like a monad, except that the result of a computation can't be used to change the "shape" of the entire computation. For example, using [] (which is both a Monad and an Applicative instance):
(+) <$> [1,2] <*> [3,4] = concat [[1+3, 1+4], [2+3,2+4]]
whereas
[1,2] >>= \x -> if even x then [] else [x+3,x+4] = concat [[1+3,1+4], []]
Notice in the second example that the inner lists have a different shape; whether or not the result of the first 'computation' [1,2] is even changes the shape of the result for that computation. While it's easy to make this work for patterns, building a (Pattern (Pattern a)), you can't write the equivalent of "concat" unless you know the period of the resulting pattern. Without that complication, you could say type Pattern a = ReaderT Integer [] a which is just a fancy way to say type Pattern a = Integer -> [a] that automatically gives you a Monad instance.
It's easy to make Pattern into an applicative functor; it's just the composition of the applicative functors for Reader and [], with a little extra work to manage the period:
instance Functor Pattern where
fmap f (Pattern xs p) = Pattern (fmap (fmap f) xs) p
The outer fmap is using instance Functor (a ->) where fmap = (.), the inner is using instance Functor [] where fmap = map
instance Applicative Pattern where
pure x = Pattern (pure (pure x)) 1
Pattern fs pf <*> Pattern xs px = Pattern (liftA2 (<*>) fs xs) (lcm pf px)
However, Pattern *is* a monad, it's just that "concat" is ugly; we have to figure out the period of the resulting pattern, which, surprisingly, is possible: you just take the lcm of all the patterns we could return!
joinPattern :: Pattern (Pattern a) -> Pattern a
joinPattern (Pattern ps p) = Pattern f newPeriod where
newPeriod = foldl' findPeriod p $ map ps [1..p]
findPeriod p = foldl' lcm p . map period
f n = concatMap (\pat -> at pat n) (ps n)
instance Monad Pattern where
return = pure
m >>= f = joinPattern (fmap f m)
|
|
| Militarized police are a bad tactic |
[03 Feb 2009|06:58pm] |
Anyone who has known me for any period of time knows that I'm about as anti-drug-use as you can get. I don't drink or smoke, let alone make use of any other substances.
But I couldn't stop reading the Washington Post article Deadly Force. It describes a police raid on the home of the mayor of a small town. His two dogs were killed, his house trashed, and his live-in mother-in-law was held on the floor at gunpoint.
And this is not an isolated incident. The drug war has gone too far.
When someone brings weapons to bear, it raises the stakes on any encounter. Are people supposed to comply with an armed attacker just because they claim to be a police officer? That gives an obvious strategy to the bad guys: claim to be a police officer.
When our country was founded, we decided that we would rather let some bad guys go free than force innocents to submit to this trauma. These rights are enshrined in our Constitution as the Fourth Amendment: "The right of the people to be secure in their persons, houses, papers, and effects, against unreasonable searches and seizures, shall not be violated, and no Warrants shall issue, but upon probable cause, supported by Oath or affirmation, and particularly describing the place to be searched, and the persons or things to be seized."
But these rights continue to be eroded. Just recently, the Supreme Court again narrowed the Exclusionary Rule, the main protection that the Fourth Amendment gives citizens. The idea behind the Exclusionary Rule is that the only way to compel law enforcement to follow the rules is to let bad guys go free, if law enforcement doesn't follow the rules. To do so, we make evidence obtained via illegal searches inadmissible in court. But the rule has been chipped away at so many times by people who don't understand that if we don't let some bad guys go free, then we will harm good guys in the process.
How can the 4th Amendment stop unlawful searches, if law enforcement can use evidence from those very same searches to arrest and convict people? Arrests and convictions are the measures that are used to determine how good of a job they are doing, so of course they will bend the rules to the point of breaking!
Instead of being modeled after the military, law enforcement should be about reaching out and building communities. We need to have people feel safe in their homes, and feel that the police are there for their protection. Instead, the United States has close to the highest per-capita prison population in the world. Do you really think that the citizens of the U.S. are worse people than elsewhere in the world? It's no wonder people don't trust the police.
The "us vs. them" military mentality in law enforcement damages our society. Lives are cut short or ruined. People give sound advice to never talk to the police. We have the despicable rise of the "stop snitchin'" movement. This isn't the direction we want our society to go!
|
|
| overheard at MSR |
[14 Oct 2008|04:40pm] |
"The first thing you need to do is trim and cube your meat."
It sounds so dirty!
|
|
| ICFP contest results |
[24 Sep 2008|09:47am] |
Back in July, I participated in the yearly ICFP programming contest, along with Jeff Gates (Maxis) and Tod Semple (Popcap). Our team was "SPORE September 7th, only $49.99! Play Bejeweled at popcap.com!" While we were brainstorming team names, Jeff suggested "Spore 9/7" and we thought it was funny. So we took it to the most ridiculous level possible while staying within the contest rules: "team names must be no more than 63 ASCII characters."
Yesterday night, at ICFP, the contest organizers presented the results. ( Here is my summary of that report. )
|
|
| Up-to-date GHC Haskell compiler on Macbook Pro! |
[18 Sep 2008|02:58pm] |
|
I just got a new Macbook Pro to take with me to ICFP and MS Research.
One of the first things I wanted to do with it is get the latest GHC compiling so I can start hacking on it. I had given up getting it to compile on Windows; I tried many combinations of MinGW versions and the appropriate tools and always failed in some way or another.
On the other hand, on my Macbook, it was really quite easy! What follows are step-by-step directions so that anyone with a similar system can build GHC.
( Easy to follow instructions! )
|
|
| Looks like it's official |
[03 Sep 2008|03:52pm] |
I'll be heading to Cambridge, UK in early October (dates TBA, but around Oct.5 to Oct.17) to work on Haskell at MSR for two weeks.
While I'm there, I'd like to get together with friends & virtual friends who I never get to see. So, let the plan-making commence. Is there anything I need to see/do while I'm out there? When are people available?
Let me know!
|
|
| Functional Reactive Programming |
[20 Apr 2008|06:11pm] |
Recently I was reading Conal Elliott's draft paper Simply Efficient Functional Reactivity.
It's a great paper and his blog has a lot more information and a good introduction to FRP and what makes it interesting; better than I can write. Many implementations of FRP pay a big performance penalty communicating "nothing happened" between parts of the code and then re-evaluating results that can't possibly change. Conal instead flips the problem around and does data-driven evaluation: when events happen, they trigger re-evaluation of all data that depends on those events (which may include other events). Ideally, only data that needs to be recalculated is.( Read more... )
|
|
| To pozorvlak |
[06 Feb 2008|08:00pm] |
To ![[info]](http://l-stat.livejournal.com/img/userinfo.gif) pozorvlak:
Can you please explain the section "Categorical Models of Type Theory" in the wikipedia entry on Intuitionistic Type Theory?
I understand (most) of the words on their own, but the sentences seem to just stop making sense to me as I read it.
|
|
| Haskell fun |
[14 Nov 2007|12:16pm] |
I've been working on implementing games in Haskell. Specifically, rules-driven board/card games.
When these games run, they often need to ask a player to make a move. This involves interacting with the outside world in some way. The most obvious way to do this is to embed your computation in the IO Monad:
type Game a = IO a
-- or
type Game a = StateT GameState IO a
However, now you have the problem that arbitrary IO is expressible as part of a game action, which makes it harder to implement things like state tracking, replay, undo, and especially testing.
While thinking about this problem this morning, I came up with the following way to use existential types to split the game from its actions:
-- p is the type of prompts
-- r is the result type
data Prompt p r = forall a. Prompt (p a) (a -> r)
newtype Game a = Game (Either a (Prompt GamePrompt (Game a)))
So, Game t either immediately gives you a t to use, or gives you a prompt you need to reply to in order to continue the computation. Intuitively, I think this is related to the Continuation monad, but I'm not sure.
Now, a simple use of Prompt would be something like the following:
Prompt [1,3,5] (+1) :: Prompt [] Int
Code that sees this can't extract the values from the list, because they don't know the internal type of the list, but you could use it to implement something that randomly chooses:
chooseRandomly :: RandomGen -> Prompt [] a -> (RandomGen, a)
chooseRandomly gen (Prompt xs f) = (gen', f x)
where (gen', x) = choose gen xs
which uses the helper function choose :: RandomGen -> [a] -> (RandomGen, a)
This by itself is interesting and potentially useful, but where it really starts to shine is when the prompt type is a GADT:
-- a GamePrompt gives you the current game state,
-- which player needs to make a choice,
-- and a choice that player needs to make.
type GamePrompt a = (GameState, Player, GameChoice a)
data GameChoice a where
Act :: GameChoice GamePiece -- what piece should act next
Attack :: GamePiece -> GameChoice AttackType -- how should you attack?
-- etc.
You can now define a prompting function:
prompt :: GameState -> Player -> GameChoice a -> Game a
prompt state who choice = Game $ Right $ Prompt (state,who,choice) $ \a -> Game $ Left a
and use it in the middle of game code:
turn :: GameState -> Player -> Game GameState
turn state who = do
-- ...
piece <- prompt state who Act
attackType <- prompt state who (Attack piece)
-- ...
return newState
Similarily, you can write a prompt handler which gets information from the user:
promptHandler :: GamePrompt a -> IO a
promptHandler (state, who, Act) = pickPiece state who
promptHandler (state, who, AttackType piece) = attackMenu state who piece
-- etc.
The neat thing about this is that on the right side of promptHandler, you know what type you need to return, since it's forced by the type of the GADT. What this means is that pickPiece can have the specialized type GameState -> Player -> IO GamePiece; it's no longer returning a generalized IO a (which is very difficult), but a specific type of object.
Now, in order to finish computing the GameState using promptHandler, you need to be in the IO monad, but there's nothing about the game that requires this! You could just as easily have a pure AI player promptHandlerAI :: GamePrompt a -> a
To tie it all together, you need a viewer function that gets the final result:
runGame :: (forall b. GamePrompt b -> IO b) -> Game a -> IO a
runGame _ (Game (Left result)) = return result
runGame f (Game (Right (Prompt prompt next))) = do
action <- f prompt
runGame f (next action)
runGameAI :: (forall b. GamePrompt b -> b) -> Game a -> a
runGameAI _ (Game (Left result)) = result
runGameAI f (Game (Right (Prompt prompt next))) = runGameAI f (next (f prompt))
Finally, to use any of this we need a Monad implementation for Game:
instance Monad Game where
return a = Game (Left a)
Game (Left a) >>= f = f a
Game (Right (Prompt p fp)) >>= f = Game (Right (Prompt p next))
where next x = fp x >>= f
|
|
| ICFP programming contest |
[29 May 2007|07:00pm] |
I've been playing with the 2006 ICFP Programming Contest task. You have to write a virtual machine to the specifications given in the task, then use it to run the "codex" provided, which decompresses itself into another program. You then run that program on your VM and play around in the simulated "UMIX" OS. Pretty impressive work by the contest team, in my opinion.
You start out by logging into the guest account where you have access to a BASIC compiler (with a twist) and some broken sample code which the last guest apparently was using to try to hack the other passwords on the machine. As you work your way through the tasks, you get "publications" which are nonsense strings which you collect for points.
My favorite so far is the "2d" programming language in ohmega's account. Here's the given example, "plus.2d". The "plus" module adds the numbers supplied as its north and west inputs, where zero is represented as Inr () and x+1 is represented as Inl x. The test in main calculates 2+3.
,..............................|....................................,
:plus | :
: *==================* | :
-->!send [(W,S),(W,E)]!--------#--------------------+ :
: *==================* | | :
: | | | :
: | v v :
: | *==============* *============* :
: | !case N of S, E!--->!send [(N,E)]!-------
: | *==============* *============* :
: | | :
: | v :
: | *========* *================* :
: +------------------->!use plus!------>!send [(Inl W,E)]!---
: *========* *================* :
,...................................................................,
,..............................................................,
:main :
: :
: *================================================* :
: !send [(Inl Inl Inl Inr (),E),(Inl Inl Inr (),S)]!--+ :
: *================================================* | :
: | v :
: | *========* :
: +--------------------------->!use plus!-----
: *========* :
,..............................................................,
% 2d plus.2d
[2D] Parsing...
[2D] Locating modules...
[2D] Verifying wires in module 'plus'...
[2D] Verifying wires in module 'main'...
[2D] Connecting wires...
[2D] Done Parsing!
Result:
Inl Inl Inl Inl Inl Inr ()
The adventure game in howie's account is pretty fun, too.
I've gotten the passwords for all of the accounts I can see in /home, and now I have a lot of puzzles to solve. It's a lot of fun even with nothing at stake.
If you want to play with it but can't get your VM working, let me know. I might make mine available somewhere.
|
|
| The Republican Party are Pirates |
[29 Apr 2005|11:13am] |
Not in the cute, happy, Puzzle Pirates sense of the word.
I was listening to a Dubya press conference last night, and he was very careful with his words to answer the questions given while not give the reporters any juicy sound bites that might undermine his policies. But he made a couple of key mistakes that an intelligent listener might pick up on.
1) "Arr! I'll compromise with ye and only take the booty from yer ship that we can fit in our hold!" He claims to want compromise on Social Security from the Dems but lists impossible conditions for that compromise. He wants no tax increase, continued benefits for existing members, and higher benefits for future members of the Social Security program. Given that it's already going broke (albeit slowly) at least one of those has to give.
2) "Swab the decks, lads, ye'll get as much as ye deserve, I swear it!" He was very careful to specify that future beneficiaries of Social Security would get at least the same benefits under his plan as current benefits. Of course, there was no mention of Cost of Living or inflation in that analysis... one wonders if "the same benefits" means the same cash amount, or the same quality of life.
3) "Har! Ship ahoy! Me mateys, we'll be eatin' hearty tonight from that poor ship o'er there." Personal retirement accounts, even if successful at providing benefits to their owners, are a gift to the credit industry. Dubya says, "We have a lot of debt," referring to individual consumers, and this was the point that resonated in my mind. Americans do have a lot of debt. And with no property to take to recover that debt, the credit industry has to suffer some losses for taking advantage of people who are unable to make sound financial decisions in their life. But if those people all had a personal account that they had paid into, then there would be plenty of cash to plunder. Given the bankruptcy "reform" taking place, this amounts to a massive gift to the credit industry. Do they really need more encouragement to continue sending out credit applications to people with no money, to take advantage of impulsive mistakes and desperate situations?
Finally, analysis of the cash flow in this country clearly shows taxes flowing from dense, highly populated "blue" states into the federal government and out into less populated "red" states. With rules (or threats to create rules) in Congress that would basically co-opt any power held by the minority party, I think it's time to start the "No taxation without representation" cry once again.
In particular, I'm tired of the economic success of the S.S. California being plundered by the Jolly Roger of Middle America. I propose that legislation be introduced in California which co-opts the federal income tax. We can calculate what percentage of the US income tax that our citizens would be paying into the system, and what percentage of benefits we expect to get out of it, and reduce our payments to the feds appropriately. The extra money would either go into the state General Fund (budget problems solved!) or refunded to individual taxpayers.
We can fight the pirates! Our cannons are as good as theirs, and our swords twice as sharp!
|
|
| Our President |
[04 Mar 2005|05:02pm] |
I heard a quote from Dubya on the radio today. It went something like this.
"We support the growing democracy in Lebanon, and it cannot succeed while being occupied by a foreign power. And that power is Syria."
I just started laughing, and laughing, and laughing.
You see, in my head, he said this:
"We support the growing democracy in Lebanon Iraq, and it cannot succeed while being occupied by a foreign power. And that power is Syria the United States."
|
|
| Crash! |
[17 Dec 2004|03:47pm] |
I was about to leave today, when there was a loud noise outside.
There was a big accident at the intersection of 16th and Church. An SUV ran a red light and either hit or was hit by another car in the intersection. The SUV deflected onto the sidewalk, into one of the city public garbage cans (probably at least 200 lbs of weight, there), and into my house. Fortunately, nobody was hurt.
It doesn't look like there is any real damage to the house... just black paint scraping. But, wow.
I spent the next half-hour collecting insurance information and phone numbers from the drivers, and dumped a copy of that into the mailbox of our downstairs neighbor who is currently HOA president.
Crazy.
|
|
| A story |
[13 Dec 2004|03:45pm] |
Once there was a little company called Rockstar Games. They made a game called Grand Theft Auto, and it was good, and the people were happy.
Then a company called Take Two Interactive bought Rockstar. They made State of Emergency, and it was really bad, and the people were worried. But then they made Grand Theft Auto Vice City and the people's fears were assuaged.
There was also a giant named EA. EA made a game called Madden NFL Football. It was a good game, most people thought, and people kept buying it every year or two, for $50. Some people wondered why people kept buying it, but they did. And EA was happy, and the people were mostly happy.
Then Take Two made a game called ESPN NFL 2K5. It wasn't as good as the previous football titles, like Madden, but they only wanted $20 for it. Some people cheered. Others booed. Others didn't know what to make of it all.
But Take Two made the giant very angry. And the angry giant went to the NFL and said, "Lo! ESPN NFL makes me very angry! We have to do something about it."
And they did.
I'm not sure if the people lived happily ever after or not.
|
|
|
[08 Dec 2004|01:38pm] |
Things that have gone wrong lately. All of these things are projects I need to handle myself or manage.
( See all my problems )
|
|
| DDR Thursday |
[30 Jul 2004|03:03pm] |
| [ |
mood |
| |
 calm |
] |
DDR Thursday actually happened on Thursday this week.
Significant accomplishments:
- 7 greats on Kind Lady heavy (all other steps Perfect)
- 10 greats on Colors heavy
- Passed Soul 6 again (I haven't passed a Challenge course in a while). 3 non-combo steps.
zqfmbg was ahead of me on score for most of the course but he failed on Hysteria Challenge. I'm pretty confident that, had he finished, he would have been 50-100 points ahead of me.
Anyways, it was fun. It was also way more crowded than usual. Met a new nice guy there, named Edwin. Out of work (I think) sales/finance guy, who seemed pretty interested in EA. I told him I'd try and find a contact person for him. Which reminds me, I need to do that.
We're going back out house-hunting again this weekend. I hope we find a few nice places.
|
|
| navigation |
| [ |
viewing |
| |
most recent entries |
] |
| [ |
go |
| |
earlier |
] |
|
|
|
|
