Showing posts from September, 2009

Simple Pascal-triangle implementations

-- The first version can output a row of Pascal's triangle:
import System.Environment(getArgs)

pas 0       = [1]
pas n | n>0 = let l = pas (n-1) in zipWith (+) (0:l) (l++[0])

main = do
    [s] <- getArgs
    print . pas $ read s

-- The second revision can output a certain number of rows of the triangle:
import System.Environment(getArgs)

pas = iterate nextline [1] where
    nextline l = zipWith (+) (0:l) (l++[0])

main = do
    [s] <- getArgs
    putStr . unlines . map show $ take (read s+1) pas

-- And the last monolith solves a very simple homework assignment:
import Data.List(intersperse)
import System.Environment(getArgs)

pas 0 = [1]
pas n = let l = pas (n-1) in zipWith (+) (0:l) (l++[0])

strPas s = do
    let n = read s
    if n<0 || n>30 then
        fail "Pascal out of range"
    else do
        let list = concat . intersperse " " . map show
        return (n, list $ pas n)

main = do
    l <- getArgs
    case l of
        [s] -> do (_,o) <- strPas s

Discussion on Ada, Java and Clean

We had a discussion on programming language preferences last week with a friendly undergraduate guy. He strongly prefers C++ and Qt, also showing enthusiastic interest in studying Concurrent Clean, while showing great dislike of Java, C# and Ada.

I won't go through the whole argument here, but the most interesting aspect of his mentality is disliking the last one. He went on to demonstrate the inferiority of Ada with examples that prove true even in the case of Clean or Haskell!

In favor of C++, he mentioned the forgiving nature of the type system. As an issue against Java, he named garbage collection, and against Ada, he listed many issues like instance derivation of type classes and the obscure syntax (I think he used a word like incongruent).

He was desperate even after I told him that he will face with very similar issues under Clean. Well, in my opinion, he will have a great time after getting hang of all that! ;-)

Haskell optimization

edit2: added Real World Haskell link via Mr. baja :-)
(edit1: tiny formatting correction)

Chapter 25. Profiling and optimization from Real World Haskell by Bryan O'Sullivan, Don Stewart, and John GoerzenAcovea (Analysis of Compiler Options via Evolutionary Algorithm) - this is compatible with virtually all compilersEvolving faster Haskell programs via Acovea - 18% runtime reduction in one case, even for hand-tuned code!Haskell as fast as C: working at a high altitude for low level performance - this shows that introducing higher abstractions shouldn't automatically cause a slowdownMap fusion: Making Haskell 225% faster a similar articleHaskellWiki: Performance/GHC optimization tricks and tips to apply by handAnd a little reminder about the secret option used during our discussion on performance analysis:
ghc -ddump-simpl $FILE > core.txt

Which one is better, functional or logic programming?

The following paper illustrates that you don't always need to decide:
Expressivity of Functional-logic Languages and their Implementation by Juan José Moreno Navarro, LSIIS - Facultad de Informática, Universsidad Politécnica de Madrid

It first shows simple problems in which one or the other is superior. Then it goes on to plot a possible implementation of a hybrid language in detail.

Lightweight web browsing as I do

edit: tiny formatting correction

I usually browse the web with many instances of the graphic links2 (my own patched version) and Epiphany concurrently, depending on the complexity of the site in question.

When I was on Firefox, I used flashblock to lighten the load on my rusty old processor. I did hack it up for Epiphany around the time I made the switch, but gave up on it sometime later, as the exact blocking scheme looked pretty inefficient. I.e., I could sometimes observe an embedded object loading and taking up a lot of CPU time until the blocker has hidden it from sight. I never cared to come up with Java blocking similar to NoScript on this browser.

As I rarely used it anyway, I simply removed the Java plugin package from my system, and extracted the Flash plugin to a subfolder of my profile directory. A hackish script of mine deleted or recreated a symbolic link to the plugins on demand, which was basically the only course-grained way I have been controlling this up until today.


Refactoring driven development instead of complete rewrites

I happen to share Joel Spolsky's view on the question of whether it's worth it to rewrite from scratch. He goes into great detail to show that you'd be almost always better off to reuse and refactor as much as you can from an evolutionarily tried and mostly working solution.

He puts it as follows:The idea that new code is better than old is patently absurd. Old code has been used. It has been tested. Lots of bugs have been found, and they've been fixed. There's nothing wrong with it. It doesn't acquire bugs just by sitting around on your hard drive.
He then goes on to analyze some of the most prominent issues that could lead the development team to consider a rewrite, and how to solve them without throwing away code.

Nevertheless, would you be surprised if I shared that, according to my limited information, some modules of a certain programming language refactoring tool go through regular rewriting from scratch? It seems that not all eat their own dog food.

Code sample formatting I use here

You may have noticed that I mostly use <code> tags instead of the more conventional <pre> to signal source code. Although the <code> tag was invented to show HTML markup, and mostly one-liners of those too, I find them more convenient for two good reasons.

One is that I usually publish source code instead of prose, so using <code> is the semantically more appropriate one of the two. The second is a practical one: by definition, preformatted text does not support reflowing by the end user.

Although that does make sense in most cases, especially for layout-based languages like Haskell, however, introducing scroll-bars in small windows or on embedded devices is a major nuisance. Your layout is toast even if you only have one or two lines that are too wide in the source. Though, I do try to prevent the former case as much as possible.

This question is a usability issue, as in my opinion, it's much better to fiddle a bit with deciphering the one or two lines that g…

The code escaper I use for this blog

Edit: numeric HTML escaping added (not Unicode compliant); minor refactoring (readFile and writeFile improvement, some renames)

Previously, I had two bash scripts for this task, but ironically, I had escaping problems within them, so I've decided to go for the clean, well-written solution below. I usually patch issues like this in my scripts, but sometimes it just isn't worth it. Fixing these is more akin to juggling, than to real bug fixing. So this is what I use from now on:

import Prelude hiding(readFile,writeFile)
import qualified Prelude(readFile,writeFile)
import System.Environment(getArgs)
import Data.List(group)
import Data.Char(ord)

data FileName = FileName String
readFile (FileName s) = Prelude.readFile s
writeFile (FileName s) d  = Prelude.writeFile s d

toHtml = concatMap code where
    code '&' = "&amp;"
    code '<' = "&lt;"
    code '>' = "&gt;"
    code c | ord(c)<32 || ord(c)>126 = "&#…

Three-phase AC voltage generation with triple software PWM

This is one of the assembly programs I could be kind of proud of. It's composed of a heap load of macros and is built up in an almost completely neat, high-level hierarchical structure. I could post some snippets if anyone is interested.

After making it build, it needed very few compile and test cycles despite the fact that I haven't programmed such a platform in years. I can recall one real, non-trivial defect that needed a second thought. It took some time of analyzing the (soundcard-based!) scope data to arrive at the conclusion that the embedded table contained inverted data (or something similar). Thus, actually the shell script was in (logical) error that generated the data table.

After this correction, all three outputs of the device were verified to generate perfectly shaped (unfiltered) sine waves. This was a nice feat, as the generation of the three outputs were implemented in an unintuitively tangled way in order to maximize output resolution.

Nice cross-platform puzzle framework and collection

You can find some very nice and small, MIT-licensed open source puzzles at Simon Tatham's Portable Puzzle Collection, they are all both downloadable and playable online.

They're also available from the official Debian/Ubuntu repositories as a package named "sgt-puzzles".

An interesting feat of these, is that they are being developed under a cross-platform abstract board-game framework for C. The mid-end provides some common higher level game-oriented routines. The back-end supports executable generation in the following formats: native Win32, native Mac OS X, Unix/GTK and Java applets - all from the same C source!

Note that I planned to design something similar in the future, but using much higher level domain-specific languages. You will find out more about my plans in a future post.

Nice and clean bash scripting for dialyzer dependencies

edit2: New escaper run.
edit: Backslash is fixed now.

I made a nice script that checks an Erlang source tree for base library dependencies. I needed this in order to speed up the system library PLT building analysis phase of the Dialyzer on my old computer.

The trivially implemented algorithm is only an approximation based on sed-processed program text, but according to my review it's should almost never generate a smaller set of packages than a proper parser. Note that even a proper parser would have problems with the pathological cases which this simple one would fail on.

The style is, however, much more interesting if you take a look at the attached code. What do you think about it?


##### library code

# unpure!
 [ -n "$NDEBUG" ] &&
  echo "DEBUG:" "$@" >> $LOG

# unpure!
 echo "warning:" "$@" >> $LOG

# unpure!
 echo "error: ${1}!" >&2
 sleep 1
 kill $$
 sleep 10

My Psion is sick - I'm doomed!

The backlight is out, what am I going to do now?! Nah, actually I would only be in trouble if it wasn't a sunlight readable, electroluminescent transflective FSTN LCD! :-)

You see, my current usage pattern involved less than 1% of backlight use, and in almost all cases it was more of a convenience than a necessity.

It is, however, a sign of deterioration of the flexible cable, so I am getting a bit worried. I am prepared for all possibilities.

Optimized Java bytecode scheme for embedded devices

There exist interesting research related to reducing the resource demands of Java runtimes. Squawk takes this to the extreme by providing an almost completely standards-compliant implementation of the CLDC, the smallest configuration of J2ME, on which MIDP is layered.

It's also of importance to note, that the source is almost entirely written in Java itself! They have worked around the issue of implementing lower level routines by falling back to a common subset of Java and C for those parts. That's a nifty trick, and I wanted to blog about something similar long time ago. It's a good thing that I'm not dreaming all the time and many of my ideas can be realized in practice.

A complete runtime including the interpreter and the garbage collectors of the said takes up 25KiB of ROM. The standard CLDC library takes up a further 146KiB of ROM when uncompressed, or 64KiB if compressed. To execute the null program, it needs about half a kilobyte of RAM for the Java heap and anot…

Is Java a slow language?

You can have a look for yourself at the Computer Language Benchmarks Game:Java vs. Erlang (Erlang in the industry)Java vs. ScalaJava vs. C# Mono (note that I'm told that Mono's runtime may be inferior in some aspects to the official .NET CLR)

Various approaches to detailed analysis:
Java performance (Wikipedia)Java is Slow Revisited (2007)Performance of Java versus C++ by J.P.Lewis and Ulrich Neumann, Computer Graphics and Immersive Technology Lab, University of Southern California (2003)Java theory and practice: Urban performance legends, revisited (IBM, 2005)Java Performance (Code Instructions)

All in all, we can conclude that neither Java, nor it's much higher level sibling, Scala deserves a reputation for being slow, though memory usage does show room for improvement. However, I would look forward to seeing results of the game tests ran under different virtual machines.

I am working on a post about efficient high level embedded programming (including Java), so do stay tun…

Progress report for this blog

Let's get back to work. Before you lose all hope, I'll cheer you up with the fact that I'm not at all out of ideas. There are dozens of articles of mine in the works, actually in excess of fifty, which you could enjoy soon!

Most stand pretty good, many of which are almost complete. Others need to get decomposed, refactored, supplemented with additional references, illustration or corrections.

I've taken your expressed wishes into consideration, so there are many hardware related among them now.

Leading edge language type system research: Cayenne and Epigram (links)

Cayenne (programming language) is implemented in Haskell and provides a very rich research alternative with dependent typesEpigram (programming language) is based on ALF, and for which the compiler can certify a proof of correctness thanks to the strong type system also based on dependent types

At first, those listed weren't of an interest to me, but the more I browse through their materials, the more I'm reminded about my goals laid out about an ideal programming environment many years ago. If only these things provided a less ugly syntax... :-)

Program Erlang/OTP without the syntax quirks

I think I can say that you can be pretty comfortable with Erlang after a while, but you never forget how clear and conscious Haskell (or Scala, etc.) code is compared to that. If only you needed to type less punctuation and if it had static types... Anyway you can both have your pie and eat it according to some projects:

Targeting a Haskell compiler for the Erlang BEAM

The following were newbie hacking attempts at transforming Haskell syntax to Erlang syntax at the source level:
The Haskerl index of some related mails
[erlang-questions] Any recent progress on Haskerl?
(the project page seems to be unavailable at the moment)

Haskell vs. Erlang vs. Scala

Comparing Haskell, Erlang and Scala by way of examples and intelligent analysis:
An Example Syntax in Haskell, Erlang and Scala (blogtrader)The multicore crises: Scala vs. Erlang (a detailed and informed analysis by Niclas Nilsson and nice follow-up discussion)Programming language shootout game on x86-64: HaskellProgramming language shootout game on x86-64: ErlangProgramming language shootout game on x86-64: Scala

Of course, all three are great languages, with Haskell having an edge over the competition in pureness and syntax neatness, Scala in technology, experience transfer and sometimes syntax, while Erlang has the edge over provenly great concurrency, scalability and a beginner-friendly straight-forward syntax - in exchange for being a dynamic language.

Expect to read more introductory articles on Scala in the future.

My interests at Wikipedia

I've uploaded a preliminary version of my interests to the Wikipedia user page of bkil.

I'll keep you posted if I find something else interesting, but you could also follow the logs. Your suggestions are welcome!

Oh no, I've been infected by a virus again!!

Edit: typo fixes

Yesterday, I needed to get a monochromatic ID picture printed to photographic paper and while at it, I also needed to print a page of text. I've visited a nearby mall in the morning for this reason.

To my surprise, they had decent automated kiosks just for this purpose at the photo specialty store. Naturally, none of them could read my flash key drive, even after asking for assistance from the pretty lady at the counter. She said this does happen sometimes. Thankfully everything went fine after manually selecting the image at her computer, as the drive was read in a second there. Probably too many files on the drive for the bogous software to cope with. Anyway, the whole process about five to ten minutes.

After that, I went to the normal printing booth for my other task. The guy was busy on the phone for about five minutes while he was acting as if he was refilling paper. After hanging up, he asked for the place where he could find the items to print. I quickly provi…