archives

A Language-Based Approach to Unifying Events and Threads

A Language-Based Approach to Unifying Events and Threads

This paper presents a language based technique to unify two seemingly opposite programming models for building massively concurrent network services: the event driven model and the multithreaded model. The result is a unified concurrency model providing both thread abstractions and event abstractions.

The implementation uses the CPS monad in such a way that the final result is a trace, that is, an ordered sequence of function calls. Threading is part of the basic monad implementation, and a scheduler is as simple as a tree traversal function over a queue of traces. Once you have a scheduler, events are obvious.

This is quite elegant, I'll start using it for my own applications as soon as I get hold of the source.

By shapr at 2006-04-28 10:43 | Implementation | Software Engineering | 18 comments | other blogs | 29858 reads

Tom 2.3 Released

Tom is a pattern matching compiler developed at INRIA. It is
particularly well-suited for programming various transformations on
trees/terms and XML based documents. Its design follows our research
on the efficient compilation of rule based languages (e.g. ELAN,
developed at INRIA-Loria).

This release continues our work on the integration of pattern matching
and rule based programming facilities into C and Java.

Many applications have been developed in Tom. Among them, lets mention:

  • the Tom compiler itself
  • languages semantics, interpreters and program transformation tools
  • a prover for the Calculus of Structures
  • an interpreter for the Rho Calculus
  • a disunification algorithm

    • Tom is a complex compiler which adds powerful constructs to C and
    Java: non linear syntactic matching, associative matching with neutral
    element (a.k.a. list-matching), XML based pattern matching, string
    matching, and equational rewriting.
    This offers the possibility to analyze and transform any kind of
    data-structure. Tom can be used for large scale developments and
    applications. It comes with documentation, programming, and debugging support.

    This new release contains many improvements and new features:
    - a new generator of abstract data types implementations (Gom) which supports hooks. In practice, this corresponds to private data types of Caml, which ensures that terms are maintained in canonical form

    - a new %strategy construct which allows to easilly define strategies that can be combined using strategy primitives a la Stratego (All, One, Repeat, Choice, Innermost, Mu, etc.)

    - a new %[...]% construct which helps to write cide generators (it is no longer necessary to encode special characters of strings)

    Tom is available, in open source (GPL/BSD License), from the Tom web page

    By Antoine Reilles at 2006-04-28 13:05 | LtU Forum | login or register to post comments | other blogs | 6488 reads

    First-Class Traces

    Some development environments provide a tracer, which allows you to observe the entering and exiting of function calls[1].

    E.g. in Common Lisp you can do: 

    (defun flatten (list)
  (cond
    ((null list) list)
    ((atom list) (list list))
    (t (append (flatten (first list))
               (flatten (rest list))))))
(trace flatten)
(flatten '(a (b c) d))

    which could output 

    0 FLATTEN > ...
  >> LIST : (A (B C) D)
  1 FLATTEN > ...
    >> LIST : A
  1 FLATTEN < ...
    << VALUE-0 : (A)
  1 FLATTEN > ...
    >> LIST : ((B C) D)
    2 FLATTEN > ...
      >> LIST : (B C)
      3 FLATTEN > ...
        >> LIST : B
      3 FLATTEN < ...
        << VALUE-0 : (B)
      3 FLATTEN > ...
        >> LIST : (C)
        4 FLATTEN > ...
          >> LIST : C
        4 FLATTEN < ...
          << VALUE-0 : (C)
        4 FLATTEN > ...
          >> LIST : NIL
        4 FLATTEN < ...
          << VALUE-0 : NIL
      3 FLATTEN < ...
        << VALUE-0 : (C)
    2 FLATTEN < ...
      << VALUE-0 : (B C)
    2 FLATTEN > ...
      >> LIST : (D)
      3 FLATTEN > ...
        >> LIST : D
      3 FLATTEN < ...
        << VALUE-0 : (D)
      3 FLATTEN > ...
        >> LIST : NIL
      3 FLATTEN < ...
        << VALUE-0 : NIL
    2 FLATTEN < ...
      << VALUE-0 : (D)
  1 FLATTEN < ...
    << VALUE-0 : (B C D)
0 FLATTEN < ...
  << VALUE-0 : (A B C D)
(A B C D)

    As you can see, the macro TRACE only enables printing the trace. Printing a trace without having a way to access it directly/programmatically seems rather premature to me. It is evident from the above trace that traces form a recursive tree-like data type, that however is not accessible to the programmer. The entering and the exiting values from a function belong to one node of the tree (even though they are printed far apart), and the subtraces are subtrees.

    Thus, continuing the above example, such a `trace' data structure might roughly resemble 

    (FLATTEN (A (B C) D) (A B C D)
  (FLATTEN A (A))
  (FLATTEN ((B C) D) (B C D)
    (FLATTEN (B C) (B C)
      (FLATTEN B (B))
      (FLATTEN (C) (C)
        (FLATTEN C (C))  ; X
        (FLATTEN NIL NIL)))
    (FLATTEN (D) (D)
      (FLATTEN D (D))
      (FLATTEN NIL NIL))))

    Since I could not find anything about this, I was wondering the following: are there any languages (or easy ways of implementing it yourself) that can reify traces as data structures such as above that you can manipulate? In case you are wondering, there are potentially many reasons why this might be useful. E.g. one might like to compare two traces, or store a trace for later, or even consider the trace itself as a kind of higher-level program (although I have not investigated this idea in depth).

    Note that I am not referring to `stack traces' (a.k.a. `backtraces'). The stack trace at the execution of location X above might be a structure resembling 

    (FLATTEN (A (B C) D)
  (FLATTEN ((B C) D)
    (FLATTEN (B C)
      (FLATTEN (C)
        (FLATTEN C)))))  ; X

    Debuggers usually already provide many ways of manipulating the stack trace after e.g. a exception or breakpoint (although I do not know which ones are able to reify it...). Also, as I recall, one simple way of implementing continuations is copying the stack (which is part of the continuation) to the heap. So stack traces are not the issue here, nor are the `traces' as the word is sometimes used in theoretical computer science (sequences of successive states of some state transition system).

    [1] It is actually an interesting question what it would mean to trace operators other than functions, but I did not go into that here.

    By xyzzy at 2006-04-28 20:45 | LtU Forum | 7 comments | other blogs | 14895 reads