Posted by Tom Moertel
Thu, 23 Mar 2006 21:51:00 GMT
I ran across a fun programming puzzle (via
Raganwald):
Given a deck of n unique cards, cut the deck i cards from top
and perform a perfect shuffle. A perfect shuffle begins by putting
down the bottom card from the top portion of the deck followed by
the bottom card from the bottom portion of the deck followed by
the next card from the top portion, etc., alternating cards until
one portion is used up. The remaining cards go on top. The problem
is to find the number of perfect shuffles required to return the
deck to its original order. Your function should be declared as:
static long shuffles(int nCards,int iCut);
Please send the result of shuffles(1002,101) along with your
program and your resume to ‘resume’ at nextag.com.
It’s a fun problem, so give it a try before reading on.
Warning: small spoilers ahead
Read more...
Posted in programming, haskell, fun stuff
Tags haskell, puzzles, shuffles
3 comments
no trackbacks
Posted by Tom Moertel
Tue, 22 Nov 2005 22:26:00 GMT
As seen in Haskell Weekly
News, Mon Hon Cheong
announced Frag, a first-person
shooter written in – wait for it – Haskell. It uses
HOpenGL for its OpenGL binding
and Yampa for reactive game
elements.
Cool!
Posted in functional programming, haskell
Tags frag, haskell, opengl, yampa
2 comments
no trackbacks
Posted by Tom Moertel
Sat, 27 Aug 2005 21:12:00 GMT
One of the projects I’m working on is a language to help researchers
manipulate genetics information. Despite all the well-publicized
advances in genetics, researchers still spend about a third of their
time writing shell, awk, and Perl scripts to manipulate their data.
If researchers can get some of this time back, they can use it to
think about more interesting problems, like curing cancer and stuff like that.
Read more...
Posted in functional programming, haskell
Tags haskell, parsec, parsing
7 comments
no trackbacks
Posted by Tom Moertel
Sat, 09 Apr 2005 18:10:00 GMT
If you write software that deals with concurrency, you are doubtless familiar with the painful limitations of the concurrency abstractions that most programming languages, runtimes, and operating systems offer us humble programmers. The one-big-select idiom, the need to impose a global ordering policy on lock taking, and the myriad things that can unexpectedly bite you in the behind when managing threads are not-so-subtle reminders that the programming world still has a few fundamental problems to solve.
Thus I was impressed when I read Tim Harris, Simon Marlow, Simon Peyton Jones, and Maurice Herlihy’s paper on Composable memory transactions a couple of months ago. The paper introduced some Very Cool Stuff (especially if you program in Haskell, for which there is an implementation available). More recently at the Links meeting at ETAPS (another cool thing a’brewing), the same team gave a talk on the subject: Concurrency Unlocked: transactional memory for composable concurrency. Check out the slides from the talk for a summary of the problem and the STM solution.
The gist is that today’s ubiquitous concurrency abstraction – the lock – is fundamentally at odds with the most successful technique we humans have for building complex systems: gluing simple systems together. Composable memory transactions, on the other hand, do not have this problem. As a result, they offer a fundamentally simpler and more mentally scalable solution for building complex concurrent systems.
To quantify this coolness, we have only to look at section 4.2 of the paper. In about 25 lines of code the authors give an implementation for what is effectively the heart of an instant messaging server. I am not kidding. Multiple writers with serialized writes into each channel, multiple readers on each channel with independent read positions and buffering. Yeah, it’s in there.
Do yourself a favor. Check out the slides from the talk and then read the paper. This is some seriously cool stuff. You ought to know about it.
Update 2007-01-16: Since I wrote this article, Software Transactional Memory has received a lot of attenttion. Here are a couple of pointers worth checking out:
Posted in programming languages, haskell, good stuff
Tags concurrency, haskell, stm, transactions
no comments
no trackbacks
Posted by Tom Moertel
Sat, 26 Mar 2005 00:06:00 GMT
In the last few days I have been learning
Ruby, something I have had on my
to-do list for a long time. Luckily, I now have a project for which Ruby on Rails
is perfect, and so now is the perfect time to get more into Ruby.
Naturally, I am making much use of the second edition of “The Pickaxe,” (pragmatic) Dave Thomas’s book
Programming Ruby (the first edition of which is available online). Overall, it is a great book: good organization, lively writing, and superb examples.
But I must say I have one source of frustration. I am a computer-language guy, and I frequently find myself thinking, that’s great, but what exactly does this mean? I’ll give you an example, which I found quite surprising.
Using the following Ruby code, you can create what is in effect your own while-loop construct:
def my_while(cond)
break unless cond
yield
retry
end
i = 0
my_while i < 10 do
print i
i += 1
end
At first, this blew my mind. Why? Because while reading the book, I
was building an understanding of the semantics of the Ruby language
in my head, and my understanding of what it means to call a function
(iterator) with a block was wrong. In my understanding, calling a
function results in evaluating its arguments in the caller’s
evaluation context, entering the evaluation context of the function,
binding the argument values, passing in the associated block, and then
evaluating the function body. When retry is called, I reasoned
mistakenly, the evaluation stops and begins anew at the beginning of
the function body, in this case, back at the break expression.
But, clearly, that cannot be what is happening. If it
were, the loop would never terminate. The condition
i < 10 would be evaluated only once – when the
my_while function was called – and thus true would be forever bound to cond
within the evaluation context of the function’s body.
At this point, I became curious. What’s really going
on with retry? To understand its relationship to function calls, I
started looking for the calling semantics of Ruby. (No luck finding
them, btw.) Are arguments passed as thunks that get reevaluated upon
each access? No, that seemed too wasteful and bizarre.
Pickaxe II said, “retry will reevaluate any arguments to the
iterator before restarting it.” Yes, clearly, that is what is
happening. But what is happening under the hood? What does that statement
really mean?
So, after thinking about it, I concluded that what is going on is
that a function call in Ruby works like this. Given a function f,
a block b, and arguments xs, the call f(xs){b}
means this:
- let k be the current continuation (i.e., just before the call)
- evaulate xs and bind the resulting values to f’s formal arguments
- bind b internally to the current block
- evaluate the body of f
Now, if inside of f’s body we encounter a retry, the evaluator
basically calls k (with a nil argument, I expect). This jumps
back to step 2, from which evaluation continues. Any side effects up
to this point are retained (so we could have previously incremented
i, for example), which is what eventually allows the code within the function
body to choose an execution path which does not contain a
retry expression, and thus avoid looping forever.
Just to make sure I really had the semantics down, I wrote an
evaluator for a mini-Ruby in Haskell. (I find that I understand something
better after I build it from the ground up.)
module MiniRuby where
import Control.Monad.Cont
import Control.Monad.Reader
import Control.Monad.State
import Data.List
import Data.Maybe
type Identifier = String
type Value = String
type Env = [(Identifier, Value)]
type RubyEvalCxt a = ContT a (ReaderT FcallCxt (State Env)) a
data FcallCxt = FC { retryCall :: Exp
, blockCont :: Value -> Exp }
type Exp = RubyEvalCxt Value
eval :: Env -> FcallCxt -> Exp -> Value
eval env fc =
(`evalState` env) . (`runReaderT` fc) . (`runContT` return)
evalTop = eval [] $
FC { retryCall = return "TOPLEVEL RETRY"
, blockCont = const $ return "TOPLEVEL BLOCK" }
fcall :: Exp -> [(Identifier, Exp)] -> Exp -> Exp
fcall fn args blk = callCC evalFn
where
evalFn fnCont = (`local` do { bindArgs; fn }) $ \fc ->
fc { retryCall = evalFn fnCont >>= fnCont
, blockCont = const blk }
bindArgs = mapM_ (uncurry (=:=)) args
yield_ = yield "YIELD"
yield :: Value -> Exp
yield value = callCC $ \k -> do
bc <- asks blockCont
local (\fc -> fc { blockCont = k }) (bc value)
retry :: Exp
retry = do
k <- asks retryCall
k
bind :: Identifier -> Value -> Exp
bind i v = do
modify ((i,v) :)
return v
infixr 1 =:=
class Bindable v where (=:=) :: Identifier -> v -> Exp
instance Bindable Value where (=:=) = bind
instance Bindable Exp where i =:= e = bind i =<< e
val :: Identifier -> Exp
val i = gets $ fromMaybe (i ++ "=UNDEFINED") . lookup i
test1 = do
"i" =:= "0"
my_while [("cond", condExp)] $
"i" += 1
val "i"
where
my_while = fcall $ do
cond <- val "cond"
if cond == "true"
then do { yield_; retry }
else return cond
a += b = a =:= (liftM $ show . (b+) . read) (val a)
condExp = do
i <- val "i"
return $ if (read i) < 10 then "true" else "false"
test2 = do
f [] $ do
"j" =:= "J"
"l" =:= "L"
mapM val (words "i j k l") >>= return . unwords
where
f = fcall $ do
"i" =:= "I"
"k" =:= "K"
yield_
test3 = do
f [] $ do
rba <- yield "J-via-yield"
yield rba
yield "M-via-yield"
mapM val (words "i j k l m") >>= return . unwords
where
f = fcall $ do
"i" =:= "I"
"j" =:= yield_
"k" =:= "K"
"l" =:= yield "Right-back-atcha!"
"m" =:= yield_
Here’s what the code does when executed:
> evalTop test1
"10"
> evalTop test2
"I J K L"
> evalTop test3
"I J-via-yield K Right-back-atcha! M-via-yield"
I must say that I really like Ruby’s semantics. So far, I find
Ruby to be a seriously cool programming language.
Posted in functional programming, programming languages, haskell, ruby
Tags evaluators, haskell, ruby
6 comments
no trackbacks
Posted by Tom Moertel
Sat, 12 Feb 2005 17:00:00 GMT
I have been managing the LectroTest project with the
monotone revision control
system. For the last few months, monotone has been undergoing some
growing pains that have made it less stable than I would like for everyday
use. Thus I thought that I would give darcs a try.
I have been following the progress of darcs since it was first
announced on the Haskell-Cafe mailing list on 9 April 2003. Darcs is
written in Haskell, one of my favorite programming languages, and
that was my initial draw. Still, until yesterday I had never
used it for any of my projects because I felt it was immature and
needed some more real-world testing before I committed work to it.
In the last three months, Darcs has gained mainstream attention
(triggered by a favorable write-up in Linux Weekly News) and a growing user base. Under
the gaze of these new eyeballs, darcs has matured much. I thought it
was time for another look.
Darcs has a small, easy-to-understand command set and yet offers
"modern" source-code management features such as distributed
development (via HTTP, ssh, and email), change sets, and cherry
picking. Want to start an experimental branch of your project? Just
check out another copy and use it for the branch. Each working copy
is a complete, independent repo. Want to publish a project repository
to the world? Just copy it to a public web server. Want to start
working on someone else's project? A single "darcs get
http://other.project.com/project" gives you a complete, stand-alone
copy. Your own personal branch. Start hacking.
To try darcs on something I was familiar with, I decided manage my
LectroTest development with it. The first thing I did was change to
the LT working directory and use "darcs init" to create a darcs
repository there.
[tom@bifur Flippi]$ cd ~/work/research/perl/qc/ # LT root dir
[tom@bifur qc]$ darcs init
[tom@bifur qc]$ l
blib/ mt.db
_build/ mtdb.dump
Build* perl-Test-LectroTest-0.2007-1.src.rpm
Build.PL pod2htmd.tmp
Build.PL~ pod2htmi.tmp
buildrpm* posts/
buildrpm~ prop2.pl
Changes prop2.pl~
Changes~ README
checkpods* t/
checkpods~ Test-LectroTest-0.2001.tar.gz
ctime.pl Test-LectroTest-0.2002.tar.gz
ctime.pl~ Test-LectroTest-0.2003.tar.gz
CVS/ Test-LectroTest-0.2004.tar
_darcs/ Test-LectroTest-0.2004.tar.gz
Example1.pl~ Test-LectroTest-0.2005.tar.gz
lib/ Test-LectroTest-0.2006.tar.gz
Makefile.PL Test-LectroTest-0.2007.tar.gz
MANIFEST Test-LectroTest-0.2008.tar.gz
MANIFEST~ Test-LectroTest-0.2009.tar.gz
MANIFEST.bak Test-LectroTest-0.201.tar.gz
MANIFEST.SKIP tex/
MANIFEST.SKIP~ THANKS
META.yml THANKS~
monotone.db TODO
monotone.db.bak TODO~
monotone.db.pre-changesets toms-notes.txt
monotone.db-pre-sql3 toms-notes.txt~
MT/
You can see that there is a lot of accumulated cruft
in my working directory, including CVS, monotone, and
now darcs revision-control artifacts. To prevent
Perl’s Module::Build from thinking the _darcs
directory is meaningful, I added it to the manifest-skip file.
[tom@bifur qc]$ echo '\b_darcs\b' >> MANIFEST.SKIP
Next I added my LectroTest sources, docs, and related files
to the darcs repo.
[tom@bifur qc]$ darcs add Build.PL buildrpm Changes \
checkpods MANIFEST MANIFEST.SKIP tex THANKS TODO \
toms-notes.txt tex/Makefile tex/titlepage.ltxThe “darcs whatsnew” command asks darcs to tell me what is
changed in the working directory with respect to the repository
state.
[tom@bifur qc]$ darcs whatsnew -s
A ./Build.PL
A ./Changes
A ./MANIFEST
A ./MANIFEST.SKIP
A ./THANKS
A ./TODO
A ./buildrpm
A ./checkpods
A ./tex/
A ./tex/Makefile
A ./tex/titlepage.ltx
A ./toms-notes.txt
The files that I added are new because I had not yet recorded
them to the repository. Before I did that, I added the
remaining LT assets.
[tom@bifur qc]$ darcs add t # add the tests dir
[tom@bifur qc]$ darcs add t/*.t
[tom@bifur qc]$ darcs add lib
[tom@bifur qc]$ cd lib
[tom@bifur lib]$ l
Test/
[tom@bifur lib]$ darcs add Test
[tom@bifur lib]$ cd Test
[tom@bifur Test]$ l
LectroTest/ LectroTest.pm~ LectroTest::Tutorial.pod~
LectroTest.pm LectroTest.pm.bak
[tom@bifur Test]$ darcs add LectroTest LectroTest.pm
[tom@bifur Test]$ cd LectroTest
[tom@bifur LectroTest]$ l
Compat.pm Generator.pm~ Simple.pm~ Tutorial.pod
Compat.pm~ Generator.pm.bak Test.pm~ Tutorial.pod~
Compat.pm.bak Property.pm TestRunner.pm Tutorial.pod.bak
CVS/ Property.pm~ TestRunner.pm~
Generator.pm Property.pm.bak TestRunner.pm.bak
[tom@bifur LectroTest]$ darcs add *.pm *.pod
At this point, it looked like I had all of the files under
darcs’s watchful eye.
[tom@bifur LectroTest]$ darcs w -s # abbreviated: w -> whatsnew
A ./Build.PL
A ./Changes
A ./MANIFEST
A ./MANIFEST.SKIP
A ./THANKS
A ./TODO
A ./buildrpm
A ./checkpods
A ./lib/
A ./lib/Test/
A ./lib/Test/LectroTest/
A ./lib/Test/LectroTest.pm
A ./lib/Test/LectroTest/Compat.pm
A ./lib/Test/LectroTest/Generator.pm
A ./lib/Test/LectroTest/Property.pm
A ./lib/Test/LectroTest/TestRunner.pm
A ./lib/Test/LectroTest/Tutorial.pod
A ./t/
A ./t/001.t
A ./t/002.t
A ./t/003.t
A ./t/004.t
A ./t/005.t
A ./t/compat.t
A ./tex/
A ./tex/Makefile
A ./tex/titlepage.ltx
A ./toms-notes.txt
[tom@bifur LectroTest]$ cd ../../.. # back up to project home
That looked right. It was time to record my changes.
This was straightforward.
[tom@bifur qc]$ darcs record --all # record all changes
Darcs needs to know what name (conventionally an email address) to use
as the patch author, e.g. 'Fred Bloggs <fred@bloggs.invalid>'.
If you provide one now it will be stored in the file
'_darcs/prefs/author' and used as a default in the future. To change
your preferred author address, simply delete or edit this file.
What is your email address? Tom Moertel <tom@moertel.com>
What is the patch name? Initial checkin of sources
Do you want to add a long comment? [yn] n
Finished recording patch 'Initial checkin of sources'
Now what did darcs think has changed?
[tom@bifur qc]$ darcs w -s
No changes!
Excellent.
One cool feature of darcs is that every working directory
is also a complete, independent repository. To make a branch,
then, is as simple as checking out a new repository.
Of course, because there is no central repository in the darcs model,
“checking out” is a concept that does not really apply. Rather, what
I must do is set up a new repository and then “push” my existing
repository’s patches to it. I can push in many ways, including
via ssh to a remotely hosted repository, but here I will just set up
a new repo in /tmp and push to it on the local filesystem.
[tom@bifur qc]$ mkdir /tmp/lt && pushd /tmp/lt
/tmp/lt ~/work/research/perl/qc
[tom@bifur lt]$ darcs init # set up new repo at /tmp/lt
[tom@bifur lt]$ popd
~/work/research/perl/qc
[tom@bifur qc]$ darcs push /tmp/lt # push to repo at /tmp/lt
Sat Feb 12 01:26:15 EST 2005 Tom Moertel <tom@moertel.com>
* Initial checkin of sources
Shall I push this patch? (1/1) [ynWvxqadjk], or ? for help: y
Finished applying...
Now, I can begin working on my new branch in the /tmp/lt working
directory.
[tom@bifur qc]$ cd /tmp/lt
[tom@bifur lt]$ l
Build.PL Changes _darcs/ MANIFEST posts/ tex/ TODO
buildrpm checkpods lib/ MANIFEST.SKIP t/ THANKS toms-notes.txt
[tom@bifur lt]$ emacs lib/Test/LectroTest.pm # fix typo
[tom@bifur lt]$ darcs record
hunk ./lib/Test/LectroTest.pm 38
-of your software. LectroTest then checks your software see whether
+of your software. LectroTest then checks your software to see whether
Shall I record this patch? (1/1) [ynWsfqadjk], or ? for help: y
What is the patch name? Fixed stupid typo in intro text of T::LectroTest.pm
Do you want to add a long comment? [yn] n
Finished recording patch 'Fixed stupid typo in intro text of T::LectroTest.pm'
Now my branch repository contains two patches:
[tom@bifur lt]$ darcs changes
Sat Feb 12 13:20:07 EST 2005 Tom Moertel <tom@moertel.com>
* Fixed stupid typo in intro text of T::LectroTest.pm
Sat Feb 12 01:26:15 EST 2005 Tom Moertel <tom@moertel.com>
* Initial checkin of sources
Because the typo that I fixed is not unique to my new branch, I ought
to make sure that the original branch gets the fix, too. To do so, I
just push it:
[tom@bifur lt]$ darcs push ~/work/research/perl/qc
Pushing to /home/thor/work/research/perl/qc...
Sat Feb 12 13:20:07 EST 2005 Tom Moertel <tom@moertel.com>
* Fixed stupid typo in intro text of T::LectroTest.pm
Shall I push this patch? (1/1) [ynWvxqadjk], or ? for help: y
Finished applying...
And now my patch has been pushed back up to the mainstream
branch! This is an attractive development model.
So far, I like darcs. Its source code–management model is
simple and powerful. Its command set is small enough to actually
grok. Using darcs has me wondering why other SCM systems have made
the problem seem so complicated. My life is complicated enough as it
is.
I think I just switched to darcs.
Posted in programming
Tags darcs, haskell, monotone, scm, source
1 comment
no trackbacks
Posted by Tom Moertel
Sat, 13 Mar 2004 17:00:00 GMT
In another draft of his article about Scheme programming, jacob shows how he approaches the problem of writing a TCP port scanner. That seemed like a fun problem, and so I whipped up this version in one of my favorite programming languages, Haskell:
module Main (main) where
import Control.Concurrent
import Control.Exception
import Data.Maybe
import Network
import Network.BSD
import System.Environment
import System.Exit
import System.IO
main :: IO ()
main = do
args <- getArgs
case args of
[host, from, to] -> withSocketsDo $
scanRange host [read from .. read to]
_ -> usage
usage = do
hPutStrLn stderr "Usage: Portscan host from_port to_port"
exitFailure
scanRange host ports =
mapM (threadWithChannel . scanPort host . fromIntegral) ports >>=
mapM_ hitCheck
where
hitCheck mvar = takeMVar mvar >>= maybe (return ()) printHit
printHit port = putStrLn =<< showService port
threadWithChannel action = do
mvar <- newEmptyMVar
forkIO (action >>= putMVar mvar)
return mvar
scanPort host port =
withDefault Nothing (tryPort >> return (Just port))
where
tryPort = connectTo host (PortNumber port) >>= hClose
showService port =
withDefault (show port) $ do
service <- getServiceByPort port "tcp"
return (show port ++ " " ++ serviceName service)
withDefault defaultVal action =
handle (const $ return defaultVal) action
Example usage:
$ ./Portscan internalhost.moertel.com 1 1000
21 ftp
22 ssh
80 http
111 sunrpc
139 netbios-ssn
443 https
445 microsoft-ds
631 ipp
709
720
Care to give it a try in your favorite programming language?
Posted in programming, haskell
Tags haskell, portscan
3 comments
no trackbacks
