From Java to Erlang via Python

Erlang - Parallel Programming without Pain

2008-05-29T09:58:00.002+10:00

Joe Armstong's Lecture on InfoQ. Must watch.

My First Mac and Virtual Box Experience

2008-05-22T01:09:00.006+10:00

I am officially a Mac convert.

Still learning how to survive on one mouse button and use these fn, control, option and command keys. But so far so good. My MBP experience is absolutely positive.

Before the purchase, I was slightly worried about if I may pay too much for a fine GUI. After last few days of hand-on experience, I think, as many MBP users has attested, the premium is well worth it.

I, in particular, appreciate the BSD root of Mac OSX. Whenever I cannot use the Mac OSX GUI to get thing done, I can always fall back to command line alternatives.

Vista is a staggering failure of MS Corp in every sense (I have used Vista for a year). As Paul Graham puts it, Microsoft has ceased to be relevant. They still have market share, but it is a market share going to erode fast, under the attacks of Sun, Linux and FOSS. The unwillingness to waste any more time on Vista is my prime motivation to switch.

The very first application I have downloaded is the VirtualBox. Basically within seconds I can start a new virtual instance of Ubuntu 8.04 beta. By default I can only ssh into the box via NAT. Will need to do some research to see how to get bridging done in Mac OSX.

The second application I tried is, not surprisingly, QuickSliver, an utility that warranted an hour of Google Tech Talk.

The Importance of Being Nosy (Nosetests, Really)

2008-05-10T04:04:00.008+10:00

Unit testing

One of a few important lessons I learn from Java development is the importance of unit test. It is of course not a silver bullet to the software reliability/quality problem, but the consequence not adopting it can only be more dire.

I used only JUnit to implement unit tests in Java (Since JUnit is "good enough", I never explore the alternative framework TestNG.). Actually, problems in writing unit tests usually have very little to do with the frameworks themselves, but more with:

A. The legacy code base you want to test against. For example, if the existing code base design is not modular enough, you have to go through some refactoring process to make unit testing possible. It is not the kind of luxury we can afford very often.

B. Mock objects. EasyMock has made mocking a dependency easier, but maintaining the mock object codes still requires considerable effort.

Unit testing and Python

I think unit testing is even more important for Python programmers.

Since everything happens in runtime for Python, errors in your scripts, no matter syntactical or logical, will not be caught until you actually execute the line of code where the bug lives*.

On top of it, a majority of commercial/in-house software contains so many features. The sheer number of possible combination of the execution pathways means thorough manual testing is simply unattainable, if not unrealistic.

If at the end of the day, a production issue in your python software arises and it turns out to be "incorrect indentation", the managers and users will look down on you pretty hard ("Did you really test it?"). Unit test + coverage tools can help us to avoid these kind of situation.

Besides, unit tests can be used to safeguard corner cases and exceptional conditions. For financial applications, one of those commonly-seen mistakes is that a program fails to perform properly when a certain event (e.g. rollover) happens on a public holiday. With unit testing, we can subject the relevant codes to different combination of date and instruments, so we can make sure it will, for instance, calculate accrual correctly no matter what.

Comparing Java, I find it easier to do unit testing in Python because, with Python's "Duck Typing" capability, we do not have to worry about maintaining mock objects at all. Whenever you need to mimic a dependency's behavior, just write a dummy class with just enough attributes/methods the testee expects. End of story.

No more record and play APIs, as in EasyMock.

Nosetests makes it easy

So, you can understand why I am so glad to find nose. Nosetests is, in a nutshell, a unit test discovery tool. It can traverse down a python source code directory and pick up classes that extends unittest.Testcase, doc test, and any classes/methods that follow the default naming convention. I can now mix any testing styles depending on the task at hand.

I usually use the following parameters with nosetests:


--verbosity=3 --with-doctest -s --exe

"--exe" is necessary because in cygwin, my primary development environment, py files are usually set to be "executable".

Feedback

Do you have any tips and idea on unit testing/software quality assurance to share? Feel free.

* It is not entirely true. If you want to catch syntactic error before run-time, you can use the compiler module to parse each py file individually. It is useful when you try to refactor by renaming modules/variables using tools like sed. This allows to make sure the regex does not do anything stupid with your code.

Python in the Corporate World

2008-04-16T00:39:00.012+10:00

Python is used widely in academia, open source projects and start-up. However, when it comes to the corporate world, it seems to me it is not making a lot of inroad. At least this is true in the finance industry, which I am more familiar with.

A quick check on the python.org's success stories, only two companies are listed as Fortune 500, and none of them is in the finance.

Occasionally there are ads looking for people with python skill in the financial sector, but the positions are usually of support or operation nature, not application development.

From first glimpse, it is a classic chicken-and-egg problem: there is not enough skillful python programmers out there to fill the jobs, it is difficult to start new projects in python. However, if python programming job market is weak, there is little incentives for students or programmers to pick up this non-mainstream language.

But there is something more than just supply-demand. I believe a common perception that, somehow, dynamic scripting languages are not for large scale projects and is difficult to maintain also make people shy away from using Python.

The not for large scale projects argument is a not too hard to counter. We just need to find some good examples of high visibility. For example, Google Groups and mercurial.

However, there may not be a clean-cut answer to the question of maintainability. First of all, we have a generation of programmers who have used to statically typed languages and their accomplishing IDEs (such as Java and Eclipse). To this group of audience, the idea that one can build a full-fledged application using just API documentation, command line tools and vi/emacs is beyond imagination. It is easy to conclude that, without IDE support, it is difficult to refactor the code base, which is an essential step in keeping the application in good heath.

Secondly past experience may still leave a bad taste. If you have done maintenance of legacy applications written in perl, some of them could make you feel like you have just visited a programmer's hell. Cryptic code and inconsistent style are everywhere. (But it'd still be way better than tcl. Luckily I have not come across any such programs yet). This bad memory certainly make people think twice before embracing dynamic scripting language in general, Python in particular.

A disclaimer I must make: what I wrote above is based on my experience only, and your organization may be free of the above issues, especially if yours is relatively smaller in scale (so it is relatively easier to innovate) or relatively young (so there are less legacy applications). But today in most of the giant, multinational financial institutions that inspire to be a "financial supermarket" for all, the decision markers, especially the "professional manager" type, have a total different mind-set. First of all they will not be benefited much, personally, by giving green light to the use of non-mainstream technology/language that promise better result and higher productivity. On the other hand, they have everything to lose if the brave decision does not deliver. Java (or C# if it is a MS Window shop) is always a safe bet, even though it means one need an army of programmers to get thing done. In essence, it is an agency problem.

Common Questions about Working as a Python Developer

2008-04-09T13:02:00.011+10:00

I haven't posted much recently because I am starting a new job. It is the third time I switched language. Now, I am officially a Python Developer. Hurray!

Since I have always kept myself busy by constantly picking up new computer languages, I know a dozen of odd and exotic languages. Therefore, after I landed on this job, I am surprised by some "interesting" questions about Python that people asked. And these people are no amateur. They are C or Java developers by profession.

Here are the questions:

1) What is Python?

Well, it is a dynamic scripting language. A good overview here.

To emphasize that it is a real programming language, I'd also add that Python is used very extensively within Google.

2) Isn't Python an very old language?

Oh, this question makes me feel like I am the last Eyak speaker!

Python appeared in 1991 when the creator Guido van Rossum released it to the public. It is actually a very young language.

Let's compare other still active languages and the time of first appearance:

Ruby - 1995
Java - 1995
Visual Basic (VB4 to VB.Net) - 1995
Lua - 1993

Perl - 1987
Erlang - 1987
C++ - 1983

C - 1972
Cobol - 1959
Fortran - 1957

The debut of Python is a rather recent event in the history of computer language chronologically.

But another meaning implied by 'Old' is related to the vitality or dynamism of the language. A low public profile seems to indicates there is not much going on in this language.

It is entirely a matter of perception.

To me, python never feels old. The language is continuously improving and evolving. The community is healthy and the members on the mailing list are friendly, helpful and intelligent. The language users are willing to embrace changes to make Python better.

It is in stark contrast with Java. The discussion of the Closure has highlighted the inertia of the Java language.

But don't get me wrong: in other arena of Java eco-system, there are still a lot of energy and innovation such as OpenJDK. OpenJDK may even eventually force the hand of Microsoft to open-source their CLR. (Hopefully)

3) Is Python more powerful than Java?

Wow, it is a dangerous questions! My PC answer is: they are designed for different tasks, and each of them have their distinct advantages in the problem domain that these languages are created to serve.

Besides, everyone has their own notion of Powerfulness. We will end up comparing orange to apple.

For me, power is only one of the consideration. Python's readability is another attractive feature. While Python cannot stop a programmer from writing cryptic code, at least it spares you the eyesore caused by bizarre programming styles that some 'gifted' programmers use.

4) Isn't Python dead?

The news of Python's death is largely exaggerated.

Postscript:

I think the latest announcement of Google App Engine will make a wider audience aware of Python and how good it is.
Lately a lot of innovation in programming languages (groovy, python and erlang for example) have an European root. Is it a sign that US has under-invested in research in both public and private sections?

Erlang Mailing List - String as List 3

2008-02-19T08:15:00.002+11:00

This is the last installment of the digest of the topic of "String as List".

Hasan Veldstra opined that lack of library support make string operation difficult. He was working on an Erlang Unicode string library based on ICU (http://www.icu-project.org/) for the past week, and expected to release an alpha version soon.

Zvi suggested that in the case of 64 bit implementation of Erlang, a "String as list" representation is wasteful.

Richard A. O'Keefe seems to be annoyed by this suggestion (and other comment on Lisp machine), and advocated that if space is a concern, the programmer can use an alternative representation such as binary.

Robert Virding clarify the leex (function token/2 and token/3) is re-entrant. However, yecc is not and must be fed with a completed list of token.

Dmitrii 'Mamut' Dimandt gave an example of why "string as list" is bad idea, because:

"This is only true for ASCII text. Non-ASCII gets screwed up badly.

lists:reverse("text") %% gives you "text"
lists:reverse("текст") %% Russian for text becomes [130,209,129,209,186,208,181
,208,130,209] which is clearly not I wanted"

Christian S has a solution to this problem:

"This is what you should have in your list:
1> Text = [16#442, 16#435, 16#43a, 16#441, 16#442].
[1090,1077,1082,1089,1090]

You can convert it to utf8 for output

2> xmerl_ucs:to_utf8(Text).
[209,130,208,181,208,186,209
,129,209,130]

And you can reverse it and convert that to utf8.

3> xmerl_ucs:to_utf8(lists:reverse(Text)).
[209,130,209,129,208,186,208,181,209,130]"

A positive message from Bjorn Gustavsson. He confirmed that is possible to use lists of Unicode characters easily. In Wings 3D, he have implemented a limited support for Unicode.

Joe Armstrong weighted in on 19 Feb. He suggested "One problem with strings unicode, regexps etc. is how you input the string.". He proposed several new syntax to capture regex or xml string.

Basically from this point onward the thread has shifted gear into forward looking mood. The discussion now focused on the best way to represent a string in Erlang.

Erlang Mailing List - String as List 2

2008-02-19T04:09:00.012+11:00

Zvi responded to Christian S's "recommended large text mass handling modules". He said, if for efficiency we represent a string as binary, the code will become too verbose. For example,

<<"ABC">>, instead of "ABC"
<< S1 / bytes, S2 / bytes >> instead of S1++S2
using file:delete(binary_to_list(Filename)) instead of file:delete(Filename)
xmerl and erlsom parse into lists and not binaries

Dustin Whitney concurred the verboseness, and recommend a new string type.

Bjorn Gustavsson responded to eariler Kevin Scaldeferri's opinion on list inefficiency. He suggested, in the case of appending:

"You can append by building a deep list and only flatten it at the end.

NewString = [AListOfChars|AnotherListOfChars]

or
NewString = [AListOfChars,ACharacter]

Or you can simply do a recursion (not tail-recursion) and use
the '++' operator. That will be efficient, because the recursion will
ensure that the '++' operators are executed in a right-to-left order."

Christian S suggested an alternative to one of Zvi's string-as-binary example (" << S1 / bytes, S2 / bytes >> instead of S1++S2"):

"[S1,S2] and then do iolist_to_binary/1 if you need it flat."

Then focus of discussion shifted to a tool called Leex for a while.

Richard A. O'Keefe weighted in and expressed his opinion on a number of issues.

First of all, the String as list should not be dismissed as "historical reason" only:

"it is simplicity (the preferred
sequence type in Erlang is lists, and strings are just sequences of
characters), power (because any time someone defines a function on
lists you get to use it on strings, and there are *lots* of useful
list functions), and processing efficiency (because working down
one character at a time doesn't require allocating *any* new storage,
not even for slices)."

He suggested the following rule of thumb for text handling

"The guiding rule is
- if you just want to hold onto a string for a while, use a binary
- if you want to build or process a string, use a list (possibly in
Erlang a deep list).
- if you want to represent something that has structure, and you want
your program to be aware of that structure, turn it into a
structured
data value and work with it in that form."

and some myth-busting on appending string performance issue:

"Right, this is not efficient. But it is spectacularly
inefficient in programming languages with more conventional
representations.
It is O(n**2). For example,
x = ""
for (i = 1; i <= 100000; i++) x = x "a" just took 30.5 seconds in awk on my machine, 62.2 seconds in Perl, and a massive 631 seconds in Java. That was using gcj; I lost patience with the Sun SDK and killed it. (AWK faster than Java? Yes, it often is.) Building the same string in Erlang using loop(100000, "") where loop(0, S) -> lists:reverse(S);
loop(N, S) -> loop(N-1, "a"++S).
takes 0.15 second on the same machine."

Masklinn pointed out later that Java benchmark is off because the example is not using StringBuffer.

End of Part 2

Erlang Mailing List - String as List 1

2008-02-19T03:30:00.006+11:00

A discussion named "String as List" has been running, at the time of writing, for 6 days and 56 posts already. A lot of interesting idea and insight into Erlang were poured into this discussion. I simply want to write down some interesting technical points in this blog as a digest, as a reference. *

It all started with a question from tsuraan:

"Why does erlang internally represent strings as lists?"

First response from Masklinn, and actually many other contributors share the same idea:

"A lot of functional languages represent strings as lists rather than
arrays because lists are their basic collection datatype, and this allows the use of all the list-related functions on strings."

Christian S put it in a shorter phrase: "historical reason". As he pointed out, "internal" is not right word in the question because string was not a special type or abstraction built on top of list. A string is a list.

He then suggested the following module for handling large text:

"- binaries (features representation that is 1:1 with the character
encoding itself, now also (R12B) with efficient scanning and
tail-construction)
- iolists (features cheap concatenation of large texts)
- list of words and a word-dictionary (features quicker scanning of words, efficient storage too)"

Then Kevin Scaldeferri throws in a different point: list is not a good representation because

"First off, I append to strings a lot more than I prepend to them. Yeah, I
could work with reversed strings, but that's a hack to deal with using the
wrong data type. Plus, I probably prefix match more often than suffix matching
(although this is less lopsided than append vs. prepend) ..."

Now we have a diversion, Lev Walkin responded to earlier Robert's post about that list is an ideal string representation because it can easily accommodate UTF-16 and UTF-32.

"Small correction: UTF-16 and UTF-32 are practically dead, you certainly
need to think in terms of UTF-8 nowadays."

Now we are going to have several threads going on under the same thread subject. Let's get to it in my next blog. But for now I will ignore UTF-8 vs UTF16/32 discussions in order to focus on Erlang features.

End of Part 1

* It is about summarization, so quote will be edited liberally for clarity, rather than reproduced word for word.

Why I choose to learn Erlang?

2008-02-06T06:02:00.011+11:00

Just think it may be worthwhile to commit it in writing for sharing.

In summary, my decision is only partially based on the technical merit or language features.

First take a look back at year 2001. Motivated by the desire to find a better, more reliable way to develop software, I learned and switched to Linux platform in this year. For anyone serious in learning unix family OS, bash, awk, sed and perl scripting are literally the "basic dance steps".

Then I moved on to Python (see my first blog if you have plenty of time to waste :-) ).

Now fast forward a few years. From Python, I soon learn about these big names such as Guido van Rossum and Peter Norvig etc, and for some reasons, stumbled upon Paul Graham and his famous essays.

One of his famous idea on computer language is: there are reasons why some languages are superior than other languages, and Lisp is the most powerful among them. (Alright, I made the assertion for him, he probably never really put it exactly this way. Did he?)

So, convinced by the argument that a language is key to a programmer's productivity, I decided to give Lisp a try. The syntax, or the lack of it, is indeed a challenge, but the concept of "code is data, data is code" is very powerful. Macros and CLOS are effective techniques in Lisp programming.

Fortunately there are a lot of resource.

Actually I should put it this way: "too much resource".

Indeed, if you look at variety in the implementations of mainstream Lisp, and its derivative, Scheme, you will find these choices: Common lisp (clisp), CMUCL (CMU lisp), Kawa (Scheme on JVM), PLT Scheme, Scheme 48 etc... The list goes on and on.

It is the common phenomena of *nix world: the Fragmentation.

As a result, for any partitioner in commercial software world, it becomes a hard problem: given limited free time for self-study, we are confronted with these choices:

which language (Lisp or Scheme)?
which version (R5RS or R6RS or some subset, in the case of Scheme)?
which implementation of the language (the usual portability vs power/library issue)?

It makes my research long and tedious. If I bet on a wrong horse, I will lose a lot of valuable time, right? What if I am in a middle of a project and encounter a bug in the lisp/scheme interpreter I am using, will there be adequate community support? What if...

Does the risks justify the potential gain from the use of Lisp/Scheme?

Then I discovered Erlang.

The following reasons make me think, form my particular situation and career need, Erlang is probably the safest bet (or most cost-effective investment):

It has all the beauty and expressiveness of a functional language
You gain concurrency for free (built-in support in syntax and kernel)
You gain fault tolerance for free
You gain distributed processing for free
The language and library are robust and battle-tested in demanding Telecom industry.
It does not suffer from the implementation fragmentation of Lisp/Scheme.
The language evolution is well controlled (by Ericsson)

It is a pragmatic choice from a software builder's point of view.

Little Erlang Exercise 6

2008-02-02T17:56:00.001+11:00

Problem Definition: Euler Problem 6

This problem is very straight-forward.


"""
The sum of the squares of the first ten natural numbers is,
1+ 2^2 + ... + 10^2 = 385

The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)^2 = 55 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 - 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
"""

if __name__ == "__main__":
  Max = 100
  SumOfSquare = sum([pow(X, 2) for X in xrange(1, Max + 1)])
  SquareOfSum = pow(sum([X for X in xrange(1, Max + 1)]), 2)
  print "%d" % (SquareOfSum - SumOfSquare)

Here is the corresponding erlang version.


-module(p6).
-export([find_diff/1]).

find_diff(Max)->
  SumOfSq = lists:foldl(fun (X, Y) -> X + Y end, 0, [X*X || X <- lists:seq(1, Max)]),
  SqOfSum = math:pow(
              lists:foldl(fun (X, Y) -> X + Y end, 0, [X || X <- lists:seq(1, Max)]),
              2),
  SqOfSum - SumOfSq.

Basically, both python and erlang offer very powerful list comprehension syntax.

Little Erlang Exercise 5

2008-02-01T23:17:00.001+11:00

Problem Definition: Euler Problem 5

I am rather happy with this python version because I can basically get it done in about 15 min in total. Some useful primitives have been developed in module p3 (See my previous post, little erlang exercise 3)


"""
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?
"""


from p3 import isprime, factorise

def product(x, y):
 return x * y

if __name__ == "__main__":
 factors = dict()
 for l in [factorise(i) for i in xrange(2, 21)]:
     tmp = dict()
     # count them
     for n in l:
         tmp[n] = 1 + tmp.get(n, 0)
     # reguster the max frequency of factor
     for k, v in tmp.items():
         factors[k] = max(factors.get(k, 0), v)

 print reduce(product, [pow(k, v) for k,v in factors.items()])

However, the erlang version took me a considerable time to complete. The problem is mainly to switch from a procedural mindset to a functional mindset.



-module(p5).
-import(p3).
-export([main/0, get_factor_freq_lst/1]).

%% run this to print the result
main() ->
  L = [ p3:factorise(X) || X <- lists:seq(1, 20)],   
  io:format("~f~n", [product(get_factor_freq(L))]).   

get_factor_freq(L) ->
  Dict = dict:new(),
  get_factor_freq(L, Dict).

%% spec: H, T are list of list of number
%% e.g. [ [N1, N1, N2...], [N1, N2...], ...]
get_factor_freq([H|T], Dict) ->
  Dist = get_factor_freq_lst(H),
  D1 = dict:from_list(Dist),
  D2 = dict:merge(fun(K, X, Y) -> update_if_bigger(K, X, Y) end, D1, Dict),
  get_factor_freq(T, D2);
get_factor_freq([], Dict) ->
  dict:to_list(Dict).  %% has to convert to list

%% Aux function
update_if_bigger(_, Initial, NewValue) when Initial < NewValue ->
  NewValue;
update_if_bigger(_, Initial, _) ->
  Initial.

%% This function assumes the list is sorted
%% This function is to delinate a list of number
%% into a list of {Key, Frequency}
get_factor_freq_lst([A|T]) when is_integer(A) ->
  get_factor_freq_lst([{A, 1}|T]);
get_factor_freq_lst([{A, N}, A|T]) when is_integer(A) ->
  get_factor_freq_lst([{A, N + 1}|T]);
get_factor_freq_lst([{A, N}, B|T]) when is_integer(A), is_integer(B), A /= B ->
  get_factor_freq_lst([{B, 1}|T] ++ [{A, N}] );
get_factor_freq_lst(L) ->
  L.

%% find the product of a list of tuple {Base, Power)
product(L) ->
  product(L, 1).
product([], Sum) ->
  Sum;
product([{Base, Power}|T], Sum) ->
  product(T, Sum * math:pow(Base, Power)).

Little Erlang Exercise 4

2008-01-31T21:37:00.000+11:00

Problem Definition: Euler Problem 4

Through this exercise, I realised that I can reverse a string using a [::-1] operator. Really cryptic, but yet handy.


"""
A palindromic number reads the same both ways. The largest palindrome
made from the product of two 2-digit numbers is 9009 = 91 x 99.

Find the largest palindrome made from the product of two 3-digit numbers.
"""

def isPalindromic(Num):
  """
    For string reversal, pls check this url:

      http://www.python.org/doc/2.3.5/whatsnew/section-slices.html

  """
  N = str(Num)
  l = len(N)
  div, mod = divmod(l, 2)
  if mod == 1: # odd
    fh = N[0:l/2]
    sh = N[1+l/2:]
    # print "%s %s" % (fh, sh)
  else:
    fh = N[0:l/2]
    sh = N[l/2:]
  return fh == sh[::-1]


if __name__ == "__main__":
  g = [ x * y for x in xrange(100, 999) for y in xrange(100, 999) ]
  print max(filter(lambda x: isPalindromic(x), g))

Here comes an erlang version. In this rare occasion, erlang runs faster than python. It is probably because, first of all, the list comprehension I used in erlang produces a smaller list. Secondly the test of palindromic is more straightforward in the erlang version.

I will revisit the python version, later, when I get a bit more time.



-module(p4).
-export([findLargestProduct/0]).

isPalindromic(N) when is_list(N) ->
  N == lists:reverse(N).

findLargestProduct() ->
  List = [X * Y || X <- lists:seq(100, 999),
                   Y <- lists:seq(100, 999),
                   isPalindromic(integer_to_list(X * Y))],
  lists:max(List).

Little Erlang Exercise 3

2008-01-29T22:09:00.001+11:00

Problem Definition: Euler Problem 3

Obviously, these scripts did not actually implement the solution. The problem statement required to pick the largest factor, but I just realized I had not done it.


"""

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 317584931803?

"""

import sys

primes = []

def isprime(N):
  """
    Original version use xrange, but caused

    "OverflowException: long int too large to convert to int"

    when taking in a large number
   
    So, I have to use while loop to replace "for i in xrange(2, N):"

    And in order to speed up the process, the prime calculation result
    is cached
  """
  global primes

  # we have already tested it
  if N in primes:
    return True

  # use the prime results first 
  for i in primes:
    if (N % i) == 0:
      return False

  # now computation is required
  maxprime = 2
  if len(primes) > 0:
    maxprime = primes[-1]

  i = maxprime + 1
  while i < N:
    if (N % i) == 0:
      return False
    i = i + 1

  primes.append(N)
  return True


def factorise(N):
  """
    to factorise a integer
    
  """
  # short cut
  global primes
  res = []

  if N in primes:
    res.append(N)
    return res

  # original algorithm
  idx = 2
  while idx <= N:
    if isprime(idx):
      div, mod = divmod(N, idx)
      if mod == 0:
        res.append(idx) 
        res.extend(factorise(div))
        break
    idx = idx + 1
  return res      

if __name__ == "__main__":  
  print factorise(int(sys.argv[1]))

Here comes the erlang version. There is some performance issue with this version. hopefully I would have some free time soon to improve the algorithm.



-module(p3).
-export([isprime/1, factorise/1]).

%%
%% prime means it is not divisible by any numbers other than 1 and itself.
%%
isprime(1) ->
 false;

isprime(2) ->
 true;

isprime(N) when N > 2 ->
 Pid = self(),
 C = lists:seq(2, N - 1),
 process_flag(trap_exit, true),
 lists:map(fun(Div) ->
               spawn_link(fun() ->
                   test_if_divisible(Pid, N, Div)
                   end)
               end, C),
 isprime_poll(length(C)).


%%
%% Message loop: to listen and receive message from voters
%%
isprime_poll(0) ->
 true;
isprime_poll(NumVote) ->
 receive
   {nondivisible, _} ->
       isprime_poll(NumVote - 1);
   {divisible, _} ->
       clean_mailbox(),
       false
 end.

%%
%% To clear away any messages in mailbox
%%
clean_mailbox() ->
 receive
   _ ->
     clean_mailbox()
   after 0 -> ok
 end.

%%
%%
%%
test_if_divisible(Pid, N, Div) ->
 case N rem Div of
   0 -> Pid ! {divisible, Div};
   _ -> Pid ! {nondivisible, Div}
 end.

%%%
%%% To factorise an integer - wrappers
%%%
factorise(N) when is_list(N) ->
   N1 = string:to_integer(N),
   factorise(N1, 2, []);

factorise(N) ->
   factorise(N, 2, []).

%%%
%%% To factorise an integer
%%%
factorise(N, Factor, Result) when Factor < N+1  ->
 case isprime(Factor) of
   true ->
     if
       (N rem Factor) == 0 ->
         %% io:format("Residual is 0 by Factor ~p~n", [Factor]),
         factorise(N div Factor, 2, [Factor|Result]);
       true ->
         factorise(N, Factor + 1, Result)
     end;
   false ->
       factorise(N, Factor + 1, Result)
 end;

factorise(_, _, Result) ->
 R = lists:reverse(Result),
 %% io:format("~p~n", [R]),
 R.

Little Erlang Exercise 2

2008-01-26T14:22:00.000+11:00

Problem Definition: Euler Problem 2

In order to solve this problem in python, I have used the yield keyword to implements a generator to provide a sequence of Fibonacci's numbers. I think I can do a better work in using list comprehension in the main routine to filter and add up the even numbers, but the current version is basically good enough.

"""

Euler 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms.
By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which
do not exceed one million.


"""
def gen_fib_seq():
a = 1
b = 2
yield a
yield b
try:
 while 1:
   c = a + b
   a, b = b, c
   yield c
except StopIteration:
 pass


if __name__ == "__main__":
b = 0
onemillion = 1000000
for x in gen_fib_seq():
 if x % 2 == 0:
   if b + x < onemillion:
     b = b + x
   else:
     break
print b

The erlang turns out to be even simpler than I thought. First of all, because every object or operation can be abstracted as a process, I do not need special keyword 'yield' to create a special object - generator. Furthermore the guard clause of function acc remove the need to put in any 'if' or 'break' to do, for example, the even number testing as in the python version.

-module(p2).
-export([main/0]).

start() -> spawn(fun() -> fib(0, 1) end).

fib(N, M) ->
receive
 {Pid, next} ->
   Pid ! {self(), N + M},
   fib(M, N+ M)
end.

get_next_fib(Pid) ->
Pid ! {self(), next},
receive
 {_, N} ->
   %% io:format("~p~n", [N])
   N
end.

%% accumulator
acc(N, Pid, Acc) when (N rem 2) =:= 1 ->
 N1 = get_next_fib(Pid),
 acc(N1, Pid, Acc);
acc(N, Pid, Acc) when N + Acc < 1000000 ->
 N1 = get_next_fib(Pid),
 acc(N1, Pid, Acc + N);
acc(_, _, Acc) ->
 Acc.


%%%
%%% Program main()
%%%
main() ->
 Pid = start(),
 Acc = acc(1, Pid, 0),
 Acc.

Little Erlange Exercise 1

2008-01-11T13:05:00.000+11:00

Problem definition: Euler Problem 1

Python version


print reduce(lambda x, y : x + y,
 filter(lambda x: x % 3 == 0 or x % 5 == 0,
 range(1, 1001)))

Erlang version



-module(p1).
-export([pr_sum/0]). %% print sum

pr_sum() ->
      L = lists:seq(1, 1000),
      L1 = [ X ||X <- L, (X rem 3) == 0 orelse (X rem 5) == 0],
      sum(L1). 

sum(L) -> sum(L, 0).
sum([], Acc) -> Acc;
sum([H|T], Acc) -> sum(T, Acc + H).

Erlang syntax 2 - Pattern matching and assignment

2007-09-14T17:45:00.001+10:00

I think it is probably a typical experience for any beginner of Erlang: The equal sign in Erlang actually works differently comparing most other imperative mainstream application. I were a little bit surprised when I first realized the subtle difference.

In erlang, the equal sign is actually an pattern matching operator. For example,

[H|T] = [0, 1, 2, 3, 4]

In the case, H is actually matched with the head of the list [0..4]. Although it effectively initialised the values of variable H and T, it is fundamentally a different concept.

Another application of this language feature is that it serves as a mean to enforce assertion. For example,

ok = module:func().

If func return an atom failure instead of ok, an exception will be automatically generated.

Isn't it neat?

Erlang Syntax 1

2007-09-14T17:44:00.000+10:00

1> (list_to_atom("erlang")):(list_to_atom("now"))().

{1189,752160,276431}

This is equivalent to

1> erlang:now().

Very interesting syntax.

Prologue

2007-08-12T23:27:00.001+10:00

The last time I got excited about a programming language was around 5 years ago when I started to learn a scripting language called Python. At that point of time, I were looking for a language that is easier to use than Perl. Don't get me wrong: Perl is still great for throw-away scripting. Its regular-expression is indispensable tool. But to do OO development in perl is simply too painful for me.

To me, Python is 'Perl done right'. It has the power of Perl, yet more readable and programmable. The use of space to indicate scope is simply a brilliant idea, despite feels a bit odd to begin with. By taking away some individual 'freedom' in this regard, it gives the whole community the advantage of uniformity of coding style. This actually makes Python an ideal language for enterprise environment, because, unlike other scripting languages, Python programmers tends to write code in consistent Pythonic style. No more unmaintainable cryptic Perl or Tcl scripts.

Python also introduces the idea of Lambda Function and Closure to me. Without me knowing, I have picked up some functional programming concept!

Functional programming is no alien to me. I have done Miranda in my first year of computer science, but I were not impressed at that time. I simply did not get it then. (Besides, it seemed to me that none got paid for doing FP professionally, so there is even less incentive to master the concepts)

Now, I have come a full cycle. This year I "discovered" the language Erlang. After reading the concepts behind the language design and implementation, I am totally in awe. The impact is as if some mystical figure suddenly showed up and told me the answer of a riddle of which I have searching for an answer for years in wilderness.

So, hopefully in this blog I can share with the public my (hopefully weekly) progress in mastering this new language, erlang, and along the way, my feeling/idea about Erlang, Python and Java. (Hence the title of this blog)