Log in

No account? Create an account
Ryan Ingram's Journal [entries|friends|calendar]
Ryan Ingram

[ userinfo | livejournal userinfo ]
[ calendar | livejournal calendar ]

A beautiful piece of code I ran into today [29 Mar 2012|01:40pm]
Y-combinator in Haskell as a lexeme-palindrome (the same way that "run, spot, run" is a palindrome)

y f = y where y = f y
post comment

The return of DDR Wednesday [16 May 2011|02:04pm]
Haven't done one of these in a while, but I'm planning to hit up SVGL this Wednesday evening starting around 7-7:30pm. Any of the old crew want to make a party of it? xtalcy/i-gene, I'm talking to you!

Might even play a round of minigolf!
3 comments|post comment

WTF spam [22 Feb 2011|01:28pm]
What the heck is up with all the spam on LJ recently? If they don't solve this problem soon I think it's time to finally delete my account.

Am I the only person getting all this garbage?
3 comments|post comment

SEATTLE [25 Aug 2010|02:37pm]
[ mood | excited ]

I'm going to be in Seattle for PAX, September 3rd to 5th. If you will be around, and want to hang out, leave a comment. I'd love to meet up with people.

1 comment|post comment

[15 Dec 2009|07:27pm]
Halfway done with the worst month of my life.
post comment

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 efficientlyCollapse )
2 comments|post comment

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]]
[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)

post comment

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!
post comment

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!
4 comments|post comment

[24 Sep 2008|10:29am]
Spore/Popcap ICFP contest reportCollapse )
post comment

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.Collapse )
4 comments|post comment

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!Collapse )

post comment

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!
2 comments|post comment

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...Collapse )
8 comments|post comment

To pozorvlak [06 Feb 2008|08:00pm]
To 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.
5 comments|post comment

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
9 comments|post comment

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!
 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.
post comment

cute [05 May 2005|04:27pm]
This is wayyy too cute...Collapse )
2 comments|post comment

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!
post comment

[29 Mar 2005|02:02pm]
For zqfmbg:

Your very own Vanity Domain Name
1 comment|post comment

[ viewing | most recent entries ]
[ go | earlier ]