Skip to main content

Posts

Showing posts from 2008

my personal profiling guide

This is suited for functional programming.

Blind optimizations: just say NO.

1. Write some unit tests that ensure your code stays correct.
2. DO NOT ASSUME ANY KNOWLEDGE ON WHAT SHOULD BE OPTIMIZED- but try to "see"
possible bottlenecks.
3. Write a the smallest possible program that uses the code to optimize, such that
the program exhibits the functionality that seems to be the bottleneck(s).
Design this program to run for a few seconds without user interaction.
4. Use a decent profiler to profile a complete run of this program
5. Optimize the bad code in this order
- estimate the complexity of the code around hotspots
- try diffrent data structures and algorithms
- try to involve background knowledge
- try to combine several functions into one
- records should fit into the cache of the target platform
- add more strictness(dangerous)
- move common subexpressions or constant subexpressions to a higher scope(generalisation of precalculation)
- us…

ArrowLoop - finally seeing the light at the end of a long tunnel

Today I achieved something I long lusted to acheive, I made the step from fix to loop.
Basically by going from the applicative order Y combinator:


(define (y f)
((lambda (ff)
(lambda (xx)
(f (ff ff) xx)))
(lambda (ff)
(lambda (xx)
(f (ff ff) xx)))))

(define (fak f n)
(if (= 0 n)
1
(* (f (- n 1)) n)))

((y fak) 5)



to writing the same in lazy haskell:



y f = f $ y f

fak r 0 = 1
fak r n = n * r (n - 1)

-- ghci> y fak 5 ----> 120


someone told me that
fix = y
and that fix and loop are closely related.
I found an aspiring blogpost and thought it would be fun to
do the fibonacci recursion instead of the simple factorial.

That resulted in:


data SF a b = SF {runSF :: [a] -> [b]}

instance Arrow SF where
arr f = SF (map f)
(SF f) >>> (SF g) = SF (f >>> g)
first (SF f) = SF $ unzip >>> (first f) >>> zip'

instance ArrowLoop SF where
loop (SF f) = SF (\ins ->
let (outs, rs) = (zip' >>>…

Got Religious

[this is the only religious post you will ever encounter on this blog]

After an excessive amount of thinking, reading and
weighting pros and cons I came to the final conclusion that
actually and deep down in me, I beleive that
1. God exists
2. Christianity makes sense

Many, many arguments exits against 1 and also 2.

But as soon as you accept 1. arguing against 2 becomes
really hard. All objections brought into field against 2. failed to
convince me finally; ok some of them convinced me at first,
and it took years to find out that they were errornous.
Many objections seem clever at first, but really contain
discrepancies or stem from pure ignorance.
Most of those uttering them, do not really reflect
these objections very well. A nice example is
the following "objection" against 1. and partly 2.:
"If god was almighty, could he create a
stone so heavy, that he can't lift it?"
It takes a bit of thinking, but is actually easy to debilitate. I will
leave that as an exercise to t…

Erlang code snippet....

Code like that:

blah(X) ->
X1 = f(X),
X2 = g(X1),
X3 = h(X2),
i(X3).

is very error prone, and worse very hard to extend. Just adding another
function application between f(X) and g(X1) requires you to alter all lines
upto the end of the function:

blah(X) ->
X1 = f(X),
X2 = j(X1)
X3 = g(X2),
X4 = h(X3),
i(X4).

This causes 2*numberoflinestoendoffunction potential error sources;

And this is also not at all a very functional style.
Why not rewriting it like this:

blah(X) ->
(chain([
f,
g,
h,
i
]))(X).

where one chains together the functions. Adding a function invocation in between is as easy as pie.



chain(FunList) ->
lists:foldl(
fun combine/2,
fun id/1,
FunList).

id(X) -> X.

combine(F,G) ->
RF = to_local_function(F),
RG = to_local_function(G),
fun(X) ->
RF(RG(X))
end.

to_local_function(F) ->
case F of
{FM, FF} -> F;
_ when is_atom(F) -> {?MODULE, F}
end.

Another solution might be using the state m…

Lazy Evaluation(there be dragons and basement cats)

Lazy Evaluation and "undefined"
I am on the road to being a haskell programmer, and it still is a long way to go. Yesterday I had some nice guys from #haskell explain to me lazy evaluation.

Take a look at this code:

Prelude> let x = undefined in "hello world"
"hello world"
Prelude>

Because of Haskells lazyness, x will not be evaluated because it is not used, hence undefined will not be evaluated and no exception will occur.

The evaluation of "undefined" will result in a runtime exception:

Prelude> undefined
*** Exception: Prelude.undefined
Prelude>


Strictness
Strictness means that the result of a function is undefined, if one of the arguments, the function is applied to, is undefined.
Classical programming languages are strict. The following example in Java will demonstrate this. When the programm is run, it will throw a RuntimeException, although the variable "evilX" is never actually used, strictness requires that all
arguments of a fu…

BlogPostAnswer.hs

{-
Intro
-}
module BlogPostAnswer where

import System.Environment

{-

This is haskell source code, which relates
to a nice blog post of someone comparing
java with python.
Original post

I picked some of the python-java comparisons
from that post, which I would like to
extend in order to contrast java and python
with haskell.

You can actually use the complete post as a
haskell source code file. All prose is
embedded in "{-" and "-}", wich are the block
comment tokens in haskell syntax.

I am a beginner haskell-hacker, and I dont have
a clue about python, so enlighten me, if you spot
a mistake.

Like python, haskell allows you to use indenting
as part of the syntax, unlike python however, you
also have the choice of using "{", "}" and ";"
instead of, or combined with, indentation.

Also, like in python, and unlike java you don't need
to put type declarations into you source code.

The step from java to haskell is
not the step from a statically typed language
to…

NumberCheck in haskell

import System.Environment
import Data.Char

main = do
arg:_ <- getArgs
putStrLn (arg ++ " is " ++ (result arg))
where result arg = if check arg then "correct" else "incorrect"
check arg = dotOrDigit `all` arg && oneOrZeroDots arg
dotOrDigit = (`elem` ['0'..'9'] ++ ['.'])
oneOrZeroDots = (<=1) . length . (filter ('.'==))

logs display, little experiment

this code ...


module LogDiffMarker where

type ReferenceWords = [String]
type Lines = [Line]
type Line = String

mark_diffrent_words :: (ReferenceWords, Lines) -> Line -> (ReferenceWords, Lines)
mark_diffrent_words (ref,i) line = (next_ref, i ++ [unwords line_with_em])
where (line_with_em, next_ref) = mark_diffrences (words line) ref ([],[])
mark_diffrences l1 [] (line_acc, ref_acc) = (line_acc ++ ["<b>"] ++ l1 ++ ["</b>"], ref_acc ++ l1)
mark_diffrences [] r (line_acc, ref_acc) = (line_acc, ref_acc)
mark_diffrences (h1:t1) (h2:t2) (line_acc, ref_acc)
| h1 == h2 = mark_diffrences t1 t2 (line_acc ++ [h1] ,ref_acc ++ [h2])
| otherwise = mark_diffrences t1 t2 (line_acc ++ ["<b>" ++ h1 ++ "</b>"],ref_acc ++ [h1])

mark_diffrent_lines :: Lines -> Lines
mark_diffrent_lines = (["<pre>"]++) . (++["</pre>"]) . snd . (foldl mark…

functional music, honorable mention of new composer C.W. Boese

just after the previous post a talented composer (Boese) used the small framework for functional music in haskell for one of his compisitions. His work balances harmony and disharmony in an unbalanced way and thereby balances the unbalancing and balancing forces driving the excellent piece of modern algorithmic music. with his silent permission the source as well the interpretation is attached to this post.

Here's the interpretation using an artifical Clarinet: play.

Here's the source:

boeseboese = Rest (2/4) :+: (hochlauf (-2) 3 boese) :=: (hochlauf (2) 3 boese) :+: boese
boese = rpt 3 freak :=: rpt 3 ghoul :=: rpt 3 funk
grund = (Note (Cis,5) 1)
freak = rptm (Trans (round (abs (duration ghoul)))) 3 funk
ghoul = akkord grund 0
funk = Trans terz grund :=: rptm (Trans quinte) 4 ghoul

just append that to the previous program and adapt the main function.


Maybe it's also worth mentioning, that this was the first piece of haskell code written by him.
Haskell syntax helps to create framewo…

Learning Haskell, functional music

As you might have realized, I started to learn Haskell. One of the most fun things to do in any programming language is creating some kind of audible side effects with a program.
Already back in the days when I started programming, I always played around with audio when toying around with a new language.

I have found a wonderful set of lecture slides about haskell and multimedia programming, called school of expression. Inspired by the slides about functional music I implemented a little song. Ahh ... and yes it is intended to sound slightly strange.

I used the synthesis toolkit to transform the music to real noise, simply by piping skini message to std-out.

I used this command line to achieve the results audible in the table:

sven@hhi1214a:~/Mukke$ ghc -o test1 test1.hs && ./test1 | stk-demo Plucked -n 16 -or -ip

Sound samples:

Pluckedplay
Clarinetplay
Whistle(attention very crazy!)play


As always the source...

stueck = anfang :+: mitte :+: ende

anfang = groovy :+: (Trans (-5) trickie)
m…

Haskell Thread Ring Benchmark

Not as fast as the erlang version coming soon:


import Control.Monad
import Control.Concurrent
import System.Environment
import System.CPUTime

fork_ring_elem prev_mvar _ = do
next_mvar <- newEmptyMVar
forkIO (ring_elem prev_mvar next_mvar)
return next_mvar

ring_elem :: MVar Int -> MVar Int -> IO ()
ring_elem prev_mv next_mv = run
where run = do
token <- takeMVar prev_mv
putMVar next_mv (token - 1)
when ( token > 0 ) run

first_ring_elem :: MVar Int -> MVar Int -> IO ()
first_ring_elem prev_mv next_mv = run
where run = do
token <- takeMVar prev_mv
putMVar next_mv (token - 1)
putStrLn "."
when ( token > 0 ) run

main = do
(procsArg:roundsArg:_) <- getArgs
first_mvar <- newMVar ((read procsArg) * (read roundsArg))
t1 <- getCPUTime
last_mvar <- foldM fork_ring_elem first_mvar [2..(read procsArg)]
t2 <- getCPUTime
putStrLn ("forked processes in " ++ (…

coping emacs #1

After having written a lot of erlang code with emacs(uhhm ... no, erlide, the erlang eclipse plugin, is not yet a viable alternative...), I decided to start (back-)porting eclipse features to emacs. Yeahhhh! I am now among those 1337 |-|4><025 that have their own ".emacs" in ~.

Well one feature, that I can't live without, is moving the current line with Alt - up/down, this is really usefull together with anotherthe other feature: duplicating the current line(Ctrl-Alt-up/down).

Below is the elisp code that provides these features and binds them to the keys these are bound to in eclipse. Note: In contrast to the eclipse version of this feature, this implementation does not(yet) work with regions, but with lines only.

Ok, put this in your ~/.emacs

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Written by Sven Heyll in 2008
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun sh-wind-col (thunk)
(let ((col (- (p…

Visualisation of DNA

After some attention has been caought by the wonderfull Rainbow DNA project, I have decided to join the club! Here is a very simplistic, far more useless way of visualising DNA: turtle graphics.
I really cannot put up a website with comlete renderings of the DNA using turtle graphics, but I uploaded two sample images to my flikr account. I wanted to find out if turtle graphics could reveal diffrent sets of patterns as those perceivable with a color plot of basepairs.

Attached is source code so you can see what the program does. You can also reuse the part that proceses the contents of "gbk" files containing genome data.

The code is just a hack done at night while I was waiting in a starbucks for a friend to pick me up, so if you think this code is a mess - you earned your degree, I was just curios after I found out about the rainbow dna project.

Well the idea of the program is very simple:
1. Initialise the turtle to be in center of the screen
2. read the next basepair, for each…

Boyer Moore Search Algorithm

I needed to find a String in a text file, so I wrote(rather hacked) a scheme imlementation of the boyer moore string search algoritm.

This is just a hack. But it is commented. What do you think?
(I decided to use this blog also as my cut-paste-source from now on.)


;; searches for string using boyer moore algorithm
(define (>>boyer-moore needle haystack)
(define needle-len (string-length needle))
(define hs-len (string-length haystack))
(define r-needle-list (reverse (string->list needle)))
;; two tables are build
;; compute the bad character shift table
;; it contains the number of chars to skip, if a character is encountered that is not the last of the search string.
;; (this table is only used after the search cursor was replaced)
(define bad-char-shift-table
(let loop
((shift 0)
(nlist r-needle-list)
(table '()))
(if (eq? nlist '())
table
(if (assv (car nlist) table)
(loop (+ 1 shift) (cdr nlist) table)