Archive for March, 2009

Hamming Numbers in prolog


Basic testing weather a number is hamming is straightforward. It can be something like this:

hamming(X) :- X =< 0, !, fail.
hamming(X) :-0 =:= (X mod 2), !, Y is X // 2,  hamming(Y).
hamming(X) :-0 =:= (X mod 3), !, Y is X // 3,  hamming(Y).
hamming(X) :-0 =:= (X mod 5), !, Y is X // 5,  hamming(Y).

But if want to make an ordered list of of all hamming numbers using lazy algorithm, we should try harder.

See this nice site that compares functional and logical languages for a solution.

His solution uses dif predicate to make the evaluation lazy. There are also other predicates for co-routines in Prolog, like freeze.

Prolog’s  freeze/frozen are similar to scheme’s promise/force.

three star programmer


There is a nice set of articles on, three star XXX;

It started  from *** in C – as it states, “Being called a ThreeStarProgrammer is usually not a compliment”.

There is a similar concept in PerlThreeStarPerl (I don’t speak Perl enough to understand this…) and  ThreeStarJava (three layers of inner classes).

Probably similar  “rating” can be invented for more languages. For Lisp it could be something like “number of sequential closing brackets” (probably it is only notable when more than ten; just to remind, that nobody knows what whether it stands for Lost in Stupid Parentheses or Language of Insufferable Superfluous Parentheses).

I think I can be rated as 3-star Haskeller as I wrote a sequence of three map.

h15 = 1 : foldl1 merge ( ap (map map (map (*) [2, 3, 5])) [h15])

I believe it is readable; probably it is bad.

C# versus C++


In my previous post I’ve tried to explain why I think there are too many programming languages, and stated that it would be better that only 2-3 would survive.

I chosen:

  • Haskell for being ultimately functional (it is very good for certain reasons),
  • Python for being ultimately easy to read and write, and
  • C++ (C++0x) for  no-compromise in it’s performance-orientation (“zero-overhead principle”) and being extremely flexible.

Of course, the choice is  quite accident (i.e. Python could be replaced with javascript, Haskell with some Lisp dialect etc.)

All I wanted to say is that there is no need for more than one language per niche, and there is no so much niches.

For general-purpose applications were speed is critical I’ve chosen C++. Why not C#? Well…

  • C++ is more general-purpose
  • It has better performance (at least for now)

Every point where C# is better that C++,  C++ can either (most cases) implement it as a library,  or add a missing feature in future version. Obviously, vice-versa is almost as true as this is. But if those both language will develop in same direction to a common denominator (C# with option to disable garbage-collection etc. or C++ with features from C#), it not really important how you’ll name it (let’s call it ManagedC+# or whatever…)

For now, if you think you need C#, think again:

  • maybe you need  Python with C++ (try SWIG and Boost.Bind)
  • if performance is less important – just Python
  • if you code for funHaskell is ideal
  • may be you don’t need to write it at all, maybe somebody already wrote it – check in on sourceforge.

H + vowel + r

word UK pronunciation US pronunciation Homophones
here (UK) IPA: /hɪə(ɹ)/, SAMPA: /hI@(r\)/ /hɪɹ/, SAMPA: /hIr/ here
hair hâr, IPA: /heə/, /heɹ/, SAMPA: /he@/ hare
hare /hɛɚ/, /heɹ/, /heə/ hair
heir âr, IPA: /eə(r)/, SAMPA: /e@(r)/ air
her IPA: /hɜː(ɹ)/, SAMPA: /h3:(\r)/ IPA: /hɝ/ SAMPA: /h3`/
air IPA: /ɛə/, SAMPA: /E@/ IPA: /ɛə/, SAMPA: /E@/ Ayr, Eire, ere, heir
hire aɪə(r) higher
hear hēə(r), IPA: /hɪə(ɹ)/, SAMPA: /hI@(r)/ hēə(r), IPA: /hɪə(ɹ)/, SAMPA: /hI@(r)/ here
ear Rhymes: -ɪə(r)

Programming languages should die


There are too many programming languages, and almost all of them must die.
There is no reasons (other then historic) for most of them.

The only exceptions:
C++ (upcoming version) – when you need uncompromising performance. Kind of multiplatform multiparadigm assembler.
Python – pseudocode, when you want only a proof of concept or when speed isn’t important, or for education.
Haskell – when you want to enjoy the process of writing code.

Although Paul Graham says LISP is the only computer programming language so far to be discovered, rather than invented, it is wrong. With all the respect to Lisp/Scheme and their elegance, those cannot be not quick enough (beeing dynamic-typed) nor pure enough (like Haskell), so they must die.

Here is a “proof” that Haskell is not “invented” but “discovered” – Curry-Howard isomorphism – it is just a notation of mathematical concept.

So is also SQL and Prolog, but those those, of course, should die, too.
SQL probably can be replaced by library (e.g. Haskell), LINQ, Google’s MapReduce. Everything done in Prolog is can be quite easy done on any functional language, but not vice-versa. It is good only for very specific tasks, and I don’t believe in domain-specific languages.

Undoubtfully, C#, Java and Delphi/(Object) Pascal, D etc. must die – there is no real reason for them to exist – they are too close to C++, but with many compromises.

Lua is similar to but worse than Python – and  thus must be replaced by it.

(Visual) Basic, Fortran and Cobol should never been born at all:  It’s well known that teaching Basic is a crime, and that the inventor of Fortran regrets about it.

Algol, Pl/2, Modula, Ada etc.  were important once, are obsolete.

So  are C with classes, Objective-C, Smalltalk and even Eiffel, with all the respect.

Perl is write-only language. It is not necessary. “Yes, sometimes Perl looks like line noise to the uninitiated, but to the seasoned Perl programmer, it looks like checksummed line noise with a mission in life.” Awk, Bash-scripts etc. – all can be easily replaced by, say,  Python. They can be implemented as a library, no need for separate language.

There is no reason to use ML, OCaml, F# – if you want to write functional-style – use Haskell, otherwise – don’t pretend (or use Python or use Boost).

I  can continue: Forth is write-only, assemblers aren’t portable (use C++), PHP is inconsistent etc.

JavaScript/ActionScript (EcmaScript) ? Nice language.  But die anyway!

Prolog for .net


P# – sourceforge .

Hamming numbers


Hamming aka Ugly, 5-smooth aka Regular numbers.
It is considered to be a trivial task to write it using any functional language, but very difficult on imperatice languages.
My goal is to check whether it is easy (possible) to write a lazy algorithm on functional-style on C++ using boost library (generator_iterator or proto library).

Before I start with c++, let me play with Haskell and Python to understand what I want.
Merge is boring on both languages.

--does WordPress supports Haskell syntax highlight? probably not...
merge xx@(x:xs) yy@(y:ys)
 | x  y = y : xx `merge` ys
 | otherwise = x : xs `merge` ys
def merge(it1, it2):
        if (i1i2):
                yield i2
                yield i1

def merge3(l1, l2, l3):
    merge(l1, ( i for i in merge(merl2, l3)))
  • Python version 1:Now, Python.
    Interesting discussion can be found here, but I changed it to work on Python 3K and too look nicer. (For me, almost always shorter == nicer.

    def m1_235():
     yield 1
     for i in merge3((2*i for i in m1_235(),
     3*i for i in m1_235(),
     5*i for i in m1_235()):
     yield i
  • Python version 2:It uses internal tool to be more lazy: it frees unneeded memory. Haskell (as beeng more lazy) does this automatically.
    from itertools import tee
    def m3_235():
         def _m235():
             yield 1
             for n in merge3((2*i for i in m2),
                         (3*i for i in m3),
                         (5*i for i in m5)):
                 yield n
         m1 = _m235()
         m2, m3, m5, mRes = tee(m1, 4)
         return mRes
    it = m3_235()

    Now, let’s have fun with haskell

  • Taken from WikiPedia
hamming = 1 : map (2*) hamming `merge` map (3*) hamming `merge` map (5*) hamming
  • more one-line variants
h2= 1 : map (2*) h2 `merge` map (3*) h2 `merge` map (5*) h2
h3= 1 : foldl1 merge [map (2*) h3, map (3*) h3, map (5*) h3]
h7= 1 : foldl1 merge [map ((*) 2) h7, map((*) 3) h7, map((*) 5)h7]
h11 = 1 : foldl1 merge (map ((flip $ x->;map $(x*)) h11) [2, 3, 5])
h12 = 1 : foldl1 merge [map f h12 |f <- map (*) [2, 3, 5]]
h15 = 1 : foldl1 merge ( ap (map map (map (*) [2, 3, 5])) [h15])
h16 = 1 : foldl1 merge [ [f h | h<-h16 ] | f <- map (*) [2, 3, 5]]
h17 = 1 : foldl1 merge [ [f h | h<-h17, f<-[(*2), (*3), (*5)]]]
h18 = 1 : foldl1 merge [ [f h | h<-h18, f<-map (*) [2, 3, 5]]]
h19 f1 f2 f3= (1 : foldl1 merge ( ap (f1 f2 (f3 (*) [2, 3, 5])) [h19 f1 f2 f3]))-- take 111 (h19 map map map)
h20 = 1 : foldl1 merge ( ap (f f (f (*) [2, 3, 5])) [h20]) where f=map

to test them, you should write something like take 111 h2

To be continued: Probably with prolog and C++

Hello world!


Welcome to This is your first post. Edit or delete it and start blogging!