print "Me" - Home

Using Scala with Google App Engine

2009-04-09T16:20:00Z

I just got access yesterday to the new Google App Engine for Java SDK, and I thought it would be fun to check if Scala works on it.

Well, it does.

Fow what is worth, I followed the standard procedure outlined in the google documentation and I was able to run my small servlet from eclipse, in java.

Simple steps to get your scala app on google app engine

download the GAE plugin for ecplise
download, if necessary, the scala plugin
create a new Google Web app project
add "scala nature" to the project
define a new Scala class as an ancestor to the existing servlet, letting the former implement the servlet behaviour

After this the basic servlet that was managed as the main run configuration from eclipse still worked correctly, meaning I could run it, stop it and deploy everything correctly. Adding a few other Scala classes still let the thing work nicely.

At this point, I'd have loved to build a tiny online REPL (at least I know that nothing bad will happen as google took care of the sandboxing) but while I was trying to use the existing scala.tools.nsc.Interpreter class I hit a problem causes by that same sandbox: it seems that the Scala code accesses the file system (mostly calls to File.isDirectory and similar), and those are caught by the SecurityManager who raises an AccessControlException. Eh, just what I asked for :)

Probably it is possible to work around this issue somehow, but it seems It would require more knowledge than that I currently have, so I'm leaving it until I have more time and experience.

For those not interested in using eclipse a nice writeup of the steps necessary to use Scala with GAE are here, it is again pretty simple, and it is probably a better approach.

Seeking Rockstar Programmers

2009-03-18T08:02:00Z

Premise: I just graduated (yay), and so did a friend of mine. The only difference is I already have a job while he's looking for it. I never had to look for a job lately, but I did remember some online thingies existed. What I did not remember was the amount of rockstar programmers required.

I am linking some offers, cause if I did not you may get a wrong picture. I am not questioning the job offer per se, they may be good and I am in no position to judge. I just wonder what the hell rockstar means.

the leading website builder for bands, is looking for a rockstar RoR developer to join our team on a freelance basis.

(here)

They seem to be a music-related company. Oh, I get the joke.

company seeking a freelance, part-time, highly productive, jack-of-all trades "rock-star" developer, software architect, systems engineer and DBA to run all of our development, including client-side, server-side, databases and infrastructure.

(here)

In this other case though.. I do not? It seem to me massively qualified in everything.

.. is seeking a rockstar Interaction Designer to join our growing UX/Product Strategy department

(here)

Here again.. what does rockstar mean in this context? Heavy on drugs? Biting off bats' heads? Having a mass of followers?

It seems that other job boards also have these kind of proposal, for example on career builder

Software Product Comp seeks Sr. .NET Rockstar!

(here)

Hell, yeah! I love the bang.

On monster.com, you can get even more

Rockstar Developers (Java/C++ or .NET!) Sought!!!

(here)

three bangs, this is what rock is all about!

Anyway, not only programming jobs in fact. I noticed a "rockstar secretary". I thought for a moment it meant being a secretary for a rockstar, but no, it actually means being able to juggle appointments and phone calls like Mick Jagger.

At some point, companies that were young, fun and creative (or at least felt so) must have thought that to attract similarly talented people they should use these kind of expressions.

Well, my tiny suggestion is: please don't. If you are cool you don't usually need an extra step to look so.

Life polyglot (ruby,python)

2009-01-16T20:14:00Z

dblack recently published a nice article about things rubyists need to think about when the long awaited 1.9 release finally appears (plus, a follow up).

Of course I'm happy of the changes, but I'd like to point out that as of today, 16 january 2009, we are still allowed to play with ruby in a way that is not going to be possible again in the future. For example, the following code implements a tiny game of life engine:

#! dunno how to [python,ruby].pick(random) in sh

ON = 1
OFF= 0
WIDTH          = 40    # WIDTH of "board"
HEIGHT         = 20    # HEIGHT of "board"


"""
# " 
def range(a,b) a...b end
def len(x) x.size end
def sum(x) x.inject{|a,b|a+b} end
def init() Array.new(HEIGHT){[0]*WIDTH} end
def spawn(board, left, top, shape)
"""
end=0
def gets(): raw_input()  
init=lambda :[[0 for x in range(WIDTH)] for x in range(HEIGHT)]
def spawn(board, left, top, shape):
  """
  "
  """
  # puts a new thingy on  board, at position (left, top),
  for y in range(0,len(shape)):
      for x in range(0, len(shape[0])):
          board[top + y][left + x] = shape[y][x]
      end
  end
end

t=init()
n=init()

#blinker
spawn(t,20,12,[[1,1,1]])
#glider
spawn(t,9,3,[[0,0,1],[1,0,1],[0,1,1]])
while 1:
  for y in range(1,HEIGHT-1):
    for x in range(1,WIDTH-1):
      c=sum([t[y-1][x-1],t[y-1][x],t[y-1][x+1],
            t[y][x-1],           t[y][x+1],
            t[y+1][x-1],t[y+1][x],t[y+1][x+1]])
      n[y][x]=OFF
      if c== 2:
        n[y][x]=t[y][x]
      end
      if c== 3:
        n[y][x]=ON
      end
    end
  end
  line = ""
  for y in range(0, HEIGHT):
      for x in range(0, WIDTH):
          if t[y][x]==0:
            line += '-'
          end
          if t[y][x]==1:
            line += 'O'
          end
      end
      line = line + "\n"
  end
  print line, "Life - press button for next generation\n"
  gets()
  t,n=n,t
end

Admittedly, the two effect are not 100% compatible, because python's print behaves differently from ruby's.

Why does it work?

Few reasons:

Ruby and python syntax are really similar
Even if nobody uses it, ruby allows a colon after if, while and for statements. Yet, it is forbidden after a function signature definition, so I have to conditionally define the function signature line
The top block is parsed differently from ruby and python: the latter sees a triple-quoted string, while ruby sees a sequence of normal strings, which are implicitly concatenated. In both cases the other language's code is inside a non used string
Some additional function definitions, some reordering (no else is possible) and everything works.

Well, works for some values of the word, since it executes correctly with ruby 1.8.7 and python 2.5, which are the two interpreters I have on my box, and it should work with any ruby 1.8.x and python 2.x.

But this code will not work with either python 3 or ruby 1.9. Well, just enjoy this tiny spot in time when we still were allowed to have multilingual code :)

Writing a Shakespeare interpreter with Parrot

2009-01-12T15:53:00Z

During the winter holidays I thought it would be fun to start learning something more about Parrot, and see how hard it would be to write an interpreter using it.

I thought that it could been nice to try implementing something simple but fun, and so I decided to try with the Shakespeare Programming Language (SPL).

Shakespeare is a beautiful language, as you can see from the code for printing fibonacci's numbers and the task proved interesting. Since parrot provides tools to generate a language skeleton it was damn fast to be up and running.

Parsing

Writing the grammar with PGE is pretty easy, for example this is the code to parse constants in the form "a pretty lady"

rule immediate {
  <article>? [<adjective> ]* <noun> {*} 
}
token noun {
  |<positive_noun>
  |<negative_noun>
  |<neutral_noun> 
  |<nothing>
}

token adjective {
  |<positive_adjective>
  |<neutral_adjective>
  |<negative_adjective>
  |<first_person_possessive>
  |<second_person_possessive>
  |<third_person_possessive>
}

(the grammatical parts (nouns, adjectives etc) were easily generated from a script and some wordlists)

The only problem was understanding that rules and tokens in PGE have the "ratchet" property of never backtracking and that longest-token-matching is (still?) not working in PGE. This mean that for example the string "an empty house" would not parse correctly when the adjective rule is ['a' | 'the' | 'an'] because 'a' would match and the rule would never backtrack. Some reordering fixed the issue.

Generating the AST is again pretty easy: you basically associate a callback method in the actions file to each rule that you want to transform and use the standard PAST::* classes to generate it, which can be as simple as this

# generating constants
method immediate($/) {
  my $value := 1;
  if $<noun><negative_noun> {
    $value := -1;
  }
  elsif $<noun><nothing> {
    $value := 0;
  }
  for $<adjective> {
    # "your" and "my" ignored
    unless $_<first_person_possessive> || 
       $_<second_person_possessive> || 
       $_<third_person_possessive> {
      $value:= $value*2;
    }
  }
  make PAST::Val.new( :value( $value ) );
}

method test($/, $k) {
  my $test := PAST::Var.new(:name('condition'));
  make PAST::Op.new( $test, 
                 $($<sentence>),
                 :pasttype($k)); # $k = "if" or "unless"
}

The actions file is written in Not Quite Perl which is a pretty basic language although it lacks sme things that would be useful in general IMHO, such list flattening. If needed though they can be used by associating the NQP classes with classes of another parrot language, such as perl6's or ruby's or lua's.

Another small issue I had was trying to conflate capture of single and multiple occurrences of a string, such as

|'exit'  <character>**{1} {*} #= exit
|'exeunt' <character> ['and' <character>]+ {*} #= exit

without explicit quantification (**{1}), the action method would get a scalar reference for the first case and a list reference for the second, and since I cannot write @($character) (NQP does not know about this) I needed an additional conditional in the action code. By explicitly quantifying I always get a list and everything is nice.

The runtime

Basic runtime functions can be written using the PIR intermediate representation, a form of high level assembly that knows about objects, namespaces, exceptions and more. Some of the code is slightly involuted because of the shakespeare language nature: most operations actually refer to both the speaker and the other character currently on stage, but it is usually quite simple to follow

.sub 'enter'
    .param string char
    get_global $P0, char
    unless null $P0 goto fin
    die "no such character in the cast!"
  fin:
    $P0['onstage'] = 1
.end

I also tweaked a little the main routine (autogenerated) to add an additional stage to the compiler. Namely, since I could not set a global "case insensitive" flag for the grammar, I introduced a pre-parsing pass to transform the input in lower case. There are probably better ways to do this, but it seems to work.

Testing

Obviously, I needed to test this. Parrot provides some tools to manage this, namely checking that the compiler outputs the right things at each stage, or that the program output is the one expected. I decided to go through another route, again wonderfully supported, of supporting TAP natively in the language.

This means you have test support builtin in the shakespeare language, bringing it up to date to the best software engineering practices.

This was admittedly extremely easy: I just added some syntax and a couple of runtime functions to print the plan ("1...10") and the test result ("ok 2", "ok 3" etc). Parrot's test harness knows how to manage that and so everything works fine.

Since I did not want to copy the existing source code I wrote everything from scratch (bar the wordlists) and used the supplied examples as reference. So I also added those to the test suite.

It seems, though, that parrot's Parrot::Test does not manage program input, so I used a ruby script as a driver. Which gets actually executed from perl, who knows about the "#!/usr/bin/env ruby" header better than me.

I was trying to port it to perl, but I'm not satisfied with the outcome, I must investigate a bit more

Conclusions

You can get the code through bitbucket, and it should work with today's (january '09) Parrot. All in all this was fun, people in #parrot and #perl6 are nice and helpful, parrot already offers great support for writing your own language and, well, you should try it too :)

Oh, and I passed my last university exam. too :D

Leaving in 3,2,1 (again)

2008-02-22T10:16:00Z

So, your host in this place is going to leave you for a while, again.

Two years ago, it was to move to Hungary, best time of my life.

This time, it's to move to Galway, Ireland where I'll be working with this people on some cool stuff.

I'm a bit afraid about finding a home, and I wish I'll not be completely useless in the project, but well, better to try and fail then never try.

See you, Dear Reader, I can't understand why you're still around this place, but thank you for doing so.

Both my languages suck

2008-02-18T21:04:00Z

Over at desperately unenterprise there is a nice article about the things the author dislikes about haskell, and an invitation to share your own quirks about your favourite language. Well, I almost equally like ruby and python. so here is a double rant.

Why ruby sucks

First, i can reopen classes but so can the others. It's all nice, and the usual idea that this will make development impossible is dumb, but it's true that it can get annoying. Matz once used to say this could be fixed by namespaces in ruby2 but I haven't heard anything about it in years and I'm not sure it will happen. Meanwhile, I still got the occasional oh, damn why isn't this working? moments, and it sucks. People may remember that nice chainsaw infanticide logger maneuver.

Modules as namespaces also suck. They rely on a wrong assumption, that everyone else will use modules as namespaces, which of course is not always true, so if you happen to use something poorly designed you may end hupo with their User class conflicting with your. Python got it right, namespaces are implicitly defined by files/directories and you have to explicitly import stuff in the current one.

But not just that, you can also import a single name from a python module. Try that with ruby's require if you can. You're either forced to split every single method in it's own file, like facets does or you impose on the end user namespace pollution.

And it's not even that namespaces are cheap to define. The usual way is

create a foo.rbmain file
create a foo/ directory
create many foo/xyz.rb files
in every single file define the module And it gets much worse with nested namespaces. And yeah I know I can do class Module::ClassName except that then I can't load that single file separately.

(I also dislike the thing about constants being lexically scoped to be fair, but probably it's just my disliking of class variables and the fact that I'd like to use constants for that)

What is nice about ruby modules is their usage as mixins, and even though I'd like them a bit different they are cool. But so under used.

The core classes in ruby are so fat that they are almost impossible to subclass. Have you ever tried subclassing String so that you can, for instance have a TextileString where you can do substitution without considering the markup? You'll never get it right enough, just String#[] has 7 different behaviors depending on th arguments, and String#[]= has 8 of them.

The Comparable mixin rocks, everybody loves Enumerable but go figure how to make an Hash-like or File-like object without subclassing

Why python sucks

The problems with python are, well, what makes it pythonesque. Yeah, I understand why you need to explicitly define self in a function, I just believe it's dumb and too verbose. But why can't I have a bit of syntax sugar ? Make .foo be a shortcut for self.foo ? At least that would also enforce the convention!

Python has such a big set of conventions that are not supported by the language. Do not use global variables, but look, there is a useful global keyword, even though you have nested namespaces.

On the other hand, it enforces some ugly conventions, suchs as the avoidance of assignments in conditionals by splitting statements and expressions. That distinction is so annoying that as time passes more and more things become both. Conditions are statements, so here is also the expression version. Functions are statements so here is the crippled lambda expression. Assignment is a statement so here are a handful of setters that avoid using the evil = symbol.

update: sorry, this got published by error, it was still largely incomplete, so I'll juust add some more comments

A lot of things that I dislike are in the "kernel library" design, and not syntax. len, map and so do not make the language less OO, I know, but they are ugly and polluting the top namespace, why can't they be made part of proper abstractions? And I hate not being able to use mutable values as key for dictionaries, even java manages to do that, it should not be that hard.

Something that I miss syntax wise instead is the lack of a case statemente, especially of a destructuring/pattern matching one. Python people will usually tell you that you just use a dictionary. Yeah, but why I have to? I can remove else-if from the language too, but it does not mean it makes sense. case/switch statements are actually a place where the language can provide very useful behaviours once someone get past the C/Java versions of it. Take a look at ruby, SML or Scala.

And, pet peeve: why I have to type ":" in definitions? the parser does not need that, and come on, it adds nothing readibility-wise.

ActsAsAuthenticated, insecure by default?

2007-12-22T12:20:00Z

ActsAsAuthenticathed is probably the most widely used (and deployed) plugin for managing user registration/authentication in a rails application.

As everything coming from Rick Olson it's great, giving you a complete authentication system in few steps, with a lot of tweaking points that allows you to make it suitable to your setup.

But I think the default configuration is a bit insecure.

Point is, the default encryption routine (done in #encrypt in model.rb) uses a SHA1 digest to cypher the password. But SHA1 is designed to be a fast digest function, not a password cypher. Moreover, the default password length is restricted in the 4..40 range.

Thus, supposing a user has a password with the standard characters in the [_-a-zA-Z0-9] range, the number of different combination for an acceptable password is 64^4< 17 milions.

This may seem a lot, but if you think about it is not so much, using a dumb ruby script on my old box I can find all the hashes for this kind of password in about three minutes. Yeah, in ruby, with gc kicking in and everything. Having a salt is of no importance, it just avoids finding multiple passwords at once.

Now, if you think that there are things like NSA@Home that will try all the possible passwords of 8 characters in one day (64^8 =~ 3e14), this does not sound really secure.

I'm not a security expert, but I believe this should not be like that. I'd say that to make it a bit more secure you could change the Model#encrypt method to do multiple iterations, say

def self.encrypt(password, salt)
  cypher = password
  1000.times do 
    cypher= Digest::SHA1.hexdigest("#{salt}#{cypher}")
  end
  cypher
end

But even there, I'm not a cryptanalist so I don't know if there is something like "the n iteration of SHA1(string of k elements) may be computed in time O(log(n*k))". Cryptopeople may do stuff like that, all the time, for what I know.

So this is basically a question: is AAA slightly insecure by default? If that is true, what would you use as the encrypt function?

ECMAScript 4, the fourth system syndrome

2007-10-25T19:55:00Z

The second system syndrome is that evil effect that often happens when redesign a small, working system so that it becomes a huge leviathan built by piling new features over new features.

Today I was reading the overview of ECMASCript 4 from ecmascript.org, and I got this very bad feeling that maybe the fourth version of ES, is suffering of an extremely strong case of this problem.

I believe that part of the success of ES in its current incarnation is that it is quite simple. Yeah, it has its shortcomings and oddities, but in general it is simple enough that everyone can learn it in no time.

ES4, on the other hand, seems to have included almost everything that came out from programming languages in the last 50 years, save Prolog and APL.

For example, it has prototypes, interfaces, classes, metaclasses, higher order types and generic functions, which for what I can tell entails all the work ever done on object-orientation (maybe predicate classes are missing, but they may be there too).

The argument list of a function may have named arguments, rest/variadic arguments, optional arguments, optional types including: non-nullable arguments, like arguments (this seems the same as in Eiffel, used to link the type of an object to another), wrap arguments that perform automatic conversion of an object of type X into another of type Y,

Whereas many languages I know provide a concept of Module or Package to handle namespacing issues, ES4 provides packages and namespaces and program units to support name hiding and modularity. Not only this, but you can introduce variables with var to have it in the object scope or with let to have it in a block, so even more namespace separation :-)

Finally, ES4 incorporates some cool features such as list comprehensions, a kind of destructuring assignment/pattern matching, python-like slicing, triple-quotes and generators (~~though AFAICT this are only one way generators like in older python releases, where you can yield but you can't receive values~~ Thanks to Neil Mix for pointing out that they are complete coroutines, and support bidirectional value passing).

And operator overloading, program pragmas, required tail call elimination, a host of interesting keywords suchy as intrinsic to reify operators, dynamic to have classes that allow adding of new fields, static to have class-level functions, final to avoid inheritance and override to use it, internal, public and so on. And of course, 6 different values of falsity, with NaN, "", 0, false, null and undefined, but not {} and [].

ECMAScript 4 seems cool, I want to use a lot of those things (yay for multi method dispatch!), but maybe it is changing the language a little bit too much .

How many of the current user of ES in one of its incarnations have ever heard of product types? Will they grasp at once the logic behind the subtyping relation between functions, with all that covariant and contravariant stuff? Will they need it at all?

I hope the internet pipes will resist to the number of "metaclass vs meta namespace vs prototype vs superclass" questions on usenet.

More Obscure Features of Ruby

2007-10-07T15:08:00Z

First go look at Nick Sieger's post about strange perlisms in ruby, cause it may be interesting for you. But talking about strange features in ruby, I believe there are some that may result even stranger, cause they are not even inherited from other languages, but are matz' own creation, I believe.

super on builtin methods

if you're redefining a builtin method you can use super to access the original one:

>> def puts(*args)
>>  super(*args)
>>  super(*args)
>> end
=> nil
>> puts 123
123
123

yet if you try with your own:

>> def foo() puts "foo" end
=> nil
>> def foo() super end
=> nil
>> foo
NoMethodError: super: no superclass method `foo'
        from (irb):8:in `foo'
        from (irb):10

super without arguments

I knew this feature for long, but never used it in real coding, even if I keep thinking it's handy. super, when used without arguments, passes all the arguments, so the above example would become:

>> def puts(a,b)
>>  super
>>  super
>> end
=> nil
>> puts 345, 567
345
567
345
567
=> nil

The evil context-sensitive while and until modifiers:

Can you tell the difference between this two lines?

 puts 'hello' while false
 begin puts 'hello' end while false

Well, the difference is that the latter will print "hello", because the while modifier always does at least one evaluation of the expression when preceded by a begin..end block. The same happens with the until modifier. Luckily, this evil behaviour is supposed to disappear.

do something, handle exceptions.. or else?

Did you know that ruby's begin allows the definition of an else clause? The else clause is actually part of the rescue part of the block,. and is executed whenever an exception is not raised:

>> def check(x)
>>  begin
?>   raise if x==2
>>  rescue
>>   "error"
>>  else
?>   "ok"
>>  end
>> end
=> nil
>> check(1)
=> "ok"
>> check(2)
=> "error"

..and of course, you do not need begin..

because, I believe you know this, you can write:

>> def check(x)
>>   raise if x==2
>>  rescue
>>   "error"
>>  else
?>   "ok"
>> end
=> nil
>> check(1)
=> "ok"
>> check(2)
=> "error"

methods with whitespace, yay!

I find this quite useful, actually. If you define a method bypassing the ruby parser with define_method you can give it any name you want.

>> class K
>>  define_method("method: hard to get") { 'got!' }
>> end
=> #<proc:0xb768d1b8>
>> K.new.send 'method: hard to get'
=> "got!"

You won't be able to call the method with normal ruby syntax, which makes it less or more useful depending on your problem space.

And finally, there is a whole slant of strange things that I believe are remnants of matz' experimenting with the language (is alias $global $other_global used somewhere outside of english.rb?), and even if some of them are quite frightening (if /regex/ anyone?) they will be phased out, so it's ok. If I recall correct ruby also had a glob operator ( <*.c> ) that was killed in the early days, so I trust matz to fix the oddities of the language sooner or later :)

Spell Corrector in AliceML

2007-09-19T21:56:00Z

It seems that writing a spell correcor is becoming my new post hello world program, so well, after having this in my hard disk for a while I thought I would publish my new solution, wrote using AliceML.

I'm really not good at ML, so this code must not be considered a good example of how to code, but I thing it's a good thing to keep track of my learning :)


import structure MkRedBlackSet  from "x-alice:/lib/data/MkRedBlackSet";
import structure MkRedBlackMap from "x-alice:/lib/data/MkRedBlackMap";

structure Set = MkRedBlackSet String;
structure Map = MkRedBlackMap String;

val wordlist = "/home/rff/wordlist.txt";
val alphabet = String.explode "abcdefghijklmnopqrstuvwxyz";

open List;

fun take2(i1,i2) = (fn cl => (take (cl,i1), drop (cl,i2)))

fun delete cl i = 
  let
    val (first, second) = take2 (i,i+1) cl
  in
    String.implode (first @ second)
  end

fun deletions cl = tabulate ((length cl), (delete cl));


fun substitute cl i = 
  let 
    val (first,second) = take2 (i, i+1) cl
    fun sub_char c = String.implode (first @ [c] @ second)
  in  
    map sub_char alphabet
  end 

fun substitutions cl =  concat( tabulate ((length cl), (substitute cl)));

fun insert cl i = 
  let 
    val (first, second) = take2 (i,i) cl
    fun ins_char c = String.implode (first @ [c] @ second)
  in  
    map ins_char alphabet
  end 

fun insertions cl =  concat( tabulate ((length cl)+1, (insert cl)));

fun transpose cl i = 
  let 
    val (first,second) = take2 (i,i+2) cl
    val c1 = nth (cl,i)
    val c2 = nth (cl,i+1)
  in  
    String.implode (first @ [c2] @[c1] @ second)
  end 

fun transpositions cl =  tabulate ((length cl)-1, (transpose cl));


fun edits1 word = 
  let 
    val w = String.explode word 
    val ws = deletions w @ transpositions w @ insertions w @  substitutions w
  in 
    foldl (Fn.flip Set.insert) (Set.empty) ws
  end 

fun insertOrUpdate map key = 
  case Map.lookup (map, key) of
     NONE => Map.insert (map, key, ref 1)
    |SOME value => (value := (!value +1) ; map)


(* train *)
fun train io =
  let 
    val chop = fn str => String.substring (str, 0, (String.size str) - 1)
  in
    case TextIO.inputLine io of
       NONE => Map.empty
      |SOME line => insertOrUpdate (train io) (chop line)
    end  

val nwords = train ( TextIO.openIn wordlist);

fun known_edits2  word = 
  let 
    fun set_edits set = Set.fold (fn (str,set) => Set.union (set, known (edits1 str))) Set.empty set
  in
    set_edits (edits1 word)
  end

fun look k = !(valOf (Map.lookup  (nwords, k)));


fun correct word =
  let 
    val candidates = find (not o Set.isEmpty) 
                           [ known (Set.fromList [word]),
                             known (edits1 word),
                             known_edits2 word]
     val sort = sort (fn (a,b)=>Int.compare ((look b), (look a))) o Set.toList
   in
     case candidates of
       SOME words => hd(sort words)
      |NONE     => word
   end  

correct "ciao" (*ciao match*);
correct "cao"  (*ciao edit 1*);
correct "mioo" (*miao edit 1*);
correct "miaoo"(*miao edit 1*);
correct "mooo" (*mao  edit 2 max value*);
correct "quux" (*quux no match*);

The worse part is the string manipulation, I think, and maybe the fact that I use references (aka mutable variables) when building the frequency count Map, but in the end I'm quite satisfied. Feel free to point out obvious errors, if you see them.

darcs pull vs git pull

2007-09-15T09:42:00Z

I mean, I'm not going to say that you should use $VCS1 over $VCS2, I'm not proficient enough with either. I just think that:

rff@ut:~/ramaze$ darcs pull
Pulling from \"http://manveru.mine.nu/ramaze\"...

Wed Sep 12 14:52:55 CEST 2007  Michael Fellinger <mail@foo.com>
  * Adding path for OSX to tool/tidy and improve readability of the spec for it a bit.
Shall I pull this patch? (1/1)  [ynWvpxqadjk], or ? for help: v
[Adding path for OSX to tool/tidy and improve readability of the spec for it a bit.
Michael Fellinger <mail@foo.com>**20070912125255] {
hunk ./lib/ramaze/tool/tidy.rb 18
+        /usr/lib/libtidy.dylib
hunk ./spec/ramaze/tidy.rb 10
-    Ramaze::Tool::Tidy.tidy(\"<html></html>\").should =~ %r{<html>\\s+<head>\\s+<meta name=\"generator\" content=\"HTML Tidy (.*?)\" />\\s+<title></title>\\s+</head>\\s+<body></body>\\s+</html>}
+    Ramaze::Tool::Tidy.tidy(\"<html></html>\").
+      should =~ %r{<html>\\s+<head>\\s+<meta name=\"generator\" content=\"HTML Tidy (.*?)\" />\\s+<title></title>\\s+</head>\\s+<body></body>\\s+</html>}
}

Wed Sep 12 14:52:55 CEST 2007  Michael Fellinger <mail@foo.com>
  * Adding path for OSX to tool/tidy and improve readability of the spec for it a bit.
Shall I pull this patch? (1/1)  [ynWvpxqadjk], or ? for help: y
Finished pulling and applying.

is slightly more clear than:

rff@ut:~/rubinius$ git pull
Fetching refs/heads/master from http://git.rubini.us/code using http
got 2fb92489ed4a0e58ea3d941a6f2ff8c7b8b44c2d
walk 2fb92489ed4a0e58ea3d941a6f2ff8c7b8b44c2d
got 6ae85832a699f3048ee260d9091aacc05c686fe4
got 6c0e0e63c0bb5979e2dd2b3df6e511b031656ef4
walk 6c0e0e63c0bb5979e2dd2b3df6e511b031656ef4
Getting alternates list for http://git.rubini.us/code
Getting pack list for http://git.rubini.us/code
Getting index for pack cf217ebdaa4f745cc827450e9cac23ec258d45f9
Getting pack cf217ebdaa4f745cc827450e9cac23ec258d45f9
 which contains cf987cd736618331bf421603c1491030b0fc8e35

got c77671cc8a43049bd61dd22f13fbbbc1ab4f96ec
... many more.. 
got 933282575047f8924edc6cc426c0a234bdbe16a3
* refs/remotes/origin/master: fast forward to branch \'master\' of http://git.rubini.us/code
  old..new: e85ecf8..2fb9248
Updating e85ecf8..2fb9248

Fast forward
 .gitignore                            |    1 +
 Makefile                              |    2 +-
 bin/sirb.rb                           |    1 -
 compiler/bytecode/compiler.rb         |   22 +-
 compiler/bytecode/primitive_names.rb  |    2 +-
 compiler/bytecode/rubinius.rb         |    1 +
 compiler/bytecode/system_hints.rb     |   20 +-
 compiler/translation/local_scoping.rb |    7 +-
 compiler/translation/normalize.rb     |   24 ++
 compiler/translation/states.rb        |   30 ++-
 kernel/core/compile.rb                |    6 +-
 kernel/core/compiled_method.rb        |    7 +-
 kernel/core/context.rb                |   26 ++-
 kernel/core/io.rb                     |    3 +
 kernel/core/string.rb                 |   91 ++++++--
 lib/bin/compile.rb                    |  176 ++++++++++++---
 lib/bin/sirb.rb                       |   22 +-
 lib/ext/syck/build.rb                 |    6 +
 lib/ext/syck/rbxext.c                 |   12 +-
 lib/stringio.rb                       |  413 +++++++++++++++++++++++++++++++++
 runtime/bootstrap.rba                 |  Bin 29758 -> 29986 bytes
 runtime/compiler.rba                  |  Bin 79208 -> 81314 bytes
 runtime/core.rba                      |  Bin 162952 -> 168854 bytes
 runtime/loader.rbc                    |  Bin 12565 -> 12651 bytes
 shotgun/lib/cpu.h                     |   13 +-
 shotgun/lib/cpu_primitives.c          |   18 ++
 shotgun/lib/cpu_task.c                |   11 +
 shotgun/lib/instructions.rb           |   13 +-
 shotgun/lib/methctx.c                 |    5 +-
 shotgun/lib/methctx.h                 |    2 +-
 shotgun/lib/primitives.rb             |   75 +++----
 spec/mini_rspec.rb                    |    8 +-
 32 files changed, 849 insertions(+), 168 deletions(-)
 delete mode 120000 bin/sirb.rb
 create mode 100644 lib/ext/syck/build.rb
 create mode 100644 lib/stringio.rb

But, hei, maybe it's just me :)

Join the Tetris day

2007-07-28T17:13:00Z

Just a quick note: if you are an italian reader, or if you're in italy in the end of september pick your piece and join us in the tetramine day :)

AliceML concurrency

2007-07-04T08:42:00Z

In these days it seem that Erlang is considered the end of all concurrency debates. and it actually seem to provides a very nice environment for concurrent programming, possibly because it was designed to do so :)

Yet there is another environment that was designed to provide good support for concurrent programming and that I find very interesting, but is not as "hyped". I'm thinking of AliceML.

I'll try to explain the basic concepts, but I'm not really proficient in ML and I may be wrong about something, so please feel free to correct my code.

A simple echo server in Alice is something like this


import structure Socket from "x-alice:/lib/system/Socket"

fun serve (socket, host, port) =
   let 
      val lineOpt = Socket.inputLine socket
   in
      case lineOpt of
          (* read something *)
           SOME(line) => print line
          (* read nothing *)
         | NONE => ()
      ;

      Socket.close socket
   end


val port = SOME 8802;
val (socket, port) = Socket.server (port, serve);

(I know the case line is somewhat strange, but keep in mind that Alice is a completely type safe programming language. Yes, no type declarations in the above code, Yay for type inference!)

Anyway, the above code will impose an ordering on the serving of clients, because client Y will be waiting for client X to finish before the serve function is called for it.

Now, in AliceML to make an expression concurrent you just need to prefix it with spawn, so for example you can write:

spawn print ( complex_calc () )

And you'll have the calculation happen in a concurrent thread.

So, how does this relates to our serve function? Simple, you can declare a function as being always computed in a different thread replacing fun with fun spawn.

By adding one word you have completed your transition from a serial server to a multithreaded uber-responsive concurrent HTTP server that competes with lighttpd, YAWS and ngix. Or, actually, not, but you have a concurrent echo server, which is nice.

Getting values

As of now there is little difference with pthread-style or unix-processes concurrency at all. The real difference is in the presence of a result in the spawned expression. Basically whenever a spawned expression is evaluated it returns a Future value, meaning something that is not yet a real value, but will become soon. It's like your void-ish concurrent stuff in C/Java/Ruby/Python suddenly could return something. the question is: what?

Well, a spawned expression will return something called a Future, that works as a placeholder for the real value.

The main computation will work concurrently with the spawned computation and it will lock just when it needs the actual value of the spawned computation. At that point:

the main computation waits
the concurrent computation finish its work
the Future in the main computation is replaced with the concurrently produced value
the main computation can resume its work and go on

This means that, for example, to concurrently transform a list you may do:


map (fn x => spawn calc x) [1,2,3,4]

And it will not lock as long as you don't access the list elements. Given the ease you can write this stuff, it is also ultra-simple to define your own parallel map like this:


fun pmap f l = map (fn x => spawn f x) l;

When trouble strikes

But wait: what happens if a Thread fails for some reason? Simple, the Future it returns will be a Failed Future and it will do exactly what you expect: it will cause a failure whenever it is accessed. So you have two chances:

the result is actually important, and a failure means the global result is invalid (i.e. using the values in a concurrently computed list). Then you are accessing the Failed Future and the error propagates, as expected.
if a single concurrent computation fails utterly you don't care (i.e. network server), so you just avoid handling the Future object and you will never know anything about the failure, somewhat like erlang's asynchronous message passing.

I like this, it seems like an evolutionary step from old-style concurrency that is not complicated yet works, plus it blurs the line between synchronous and asynchronous message passing, which is a great thing in my opinion.

There is more than this in Alice's concurrency, for example handling shared values, the difference between Thread and OS Processes, atomic state change and so on, but all built on top of this primitives, AFAICT. Take a look at it, it even comes with a GTK gui ;)

My Tiny DocTest for ruby

2007-06-12T09:53:00Z

I believe that doctest for python is one of the best test libraries available, because it pushes the cost to develop functional tests to zero.

While I’m writing a dummy object persistence layer I thought it would have been nice to have something like that, basically seeking some kind of literate testing process.

This is the first attempt at it (warning dirty, slow, duplicated code).

It somehow works, can be run from rcov/rake/ruby, loaded with multiple files, and allows writing nice tests like this one . As you can see in the code, everything that does not look like irb code is ignored, which allows adding comments, leave python code mixed with ruby, write formulas and so on.

The lib is really half-backed, for example you canì’t use multiline declarations in irb or print something to screen, but I think it is a nice small thing.

You can find a different take on sample/doc testing in manveru’s repository

Using darcs with FTP and without SSH

2007-06-05T20:58:00Z

darcs is my favourite Version Control System. I'm not chris and I have not tried a lot of them, but I just love darcs' cherry picking so everything that misses that is out of my list. Maybe monotone or subversion 1.5 would be interesting.

Anyway, my only issue with darcs is that it does not allow pushing changes to a dumb repository, where dumb means ftp.

Since I don't have ssh access on all my hostings I found the solution in sitecopy which is a nifty utility to keep a remote directory in sync with a local one by doing incremental uploads.

To use this simply install sitecopy (which is probably avilable through your linux/bsd flavour package manager) and create a file ~/.sitecopyrc with a content like this:


site myproject
  server  ftp.myserver.com
  remote  /www/darcs.myserver.com/myproject
  local   /path/to/local/repository
  username  joe
  password  123

and to create a directory ~/.sitecopy. The permission mask for the dir must be 0700 and for the rc file it must be 0600, otherwise sitecopy will complain about insecure files.

At this point you just need to init the remote repository by doing sitecopy --init myproject. It may take some time because the first time you'll be uploading all the old patches in the _darcs/ directory, but the next time you will do this, using sitecopy --update myproject it will be quite fast.

Obviously this approach works nicely only in a single-user environment, because if multiple users share the remote directory there will be inconsistencies, but it is useful to keep your copy of a projects' repository where you can have your patches and where you can point people that want them.