Marieke J.H. Devillers-van Agtmaal (1943-2007)

My mother unexpectedly passed away this morning after a life of struggling with her mental illness. Above a piece of art from her.

On One-Pass CPS Transformations

I don't like my stack based interpreter anymore. Possibly, I should go for CPS too?

Convergent Anycast

Convergent Anycast is a protocol which avoids the need for all nodes in a network to synchronize duty cycles in order to communicate [Kai-Wei Fan, Sha Liu, and Prasun Sinha from the Computer Science & Engineering department of Ohio State University].

Software Radio Implementation for Sensor Networking

Software Radio Implementation of Short-range Wireless Standards for Sensor Networking by Thomas Schmid (demo abstract).

Lectures on Types and Programming Languages

Somehow it helps when you are from Glasgow, or go to lectures there.

Lecture Times

• Monday 11.00 Boyd Orr LT B (until 30th October), then F121,
  17 Lilybank Gardens


• Wednesday 9.00 2 University Gardens (209)


• Friday 10.00 Maths 214

Simon Gay's lectures on Types and Programming Languages are a great resource.

Eriks SunSPOT Adventures

We are using the TinyNodes from ShockFish in our curriculum, which are excellent. This new platform from Sun really is beautiful though.

Short informal battle list, some figures are guessed.

Feature	TinyNode	Sunspot
Power Consumption	very low, 20mA, 6microA	100 mA, 32 microA
Language	NesC	Java (not realtime)
Radio	yes	yes
Leds	red (red, yellow, green)	8 tri-color LEDs
Power	adapter or two AAs	3.7V rechargeable, 750 mAh, USB
Light Sensor	yes	yes
Accelero Meter	no	3-axis
Temperature Sensor	yes	yes
Simulator	Mature	Under Development
Pricing	Euro 600,-	to be announced

A cool and fun device, maybe not particularly well-suited for embedded extremely low-power applications, but damned ... cool and fun.

Why do they need all that memory?

Medics Allegedly Sneak Peek at George Clooney's Private Records

Another slow day, some people -yeah, even me, it seems- just have to read up on celebs.



Twenty-seven employees at Palisades Medical Center have reportedly been suspended for a month without pay for allegedly accessing George Clooney's medical records after the actor/director was hospitalized with injuries from a motorcycle crash in September. The investigation reportedly is continuing, with more than 40 employees under the crosshairs.

Through eWeek

Thin Clients

I want to buy an inexpensive thin client and am looking at a number of options now, listed below for further reference:

1. Koolu


2. Fit-PC


3. Linutop

Hughes on Testing

Quickcheck is a marvelous spin-off of Haskell. John Hughes has started a company Quviq which now markets the technology behind it.

Classes

Comic 202 of xkcd.

Stuff I've seen my students looking at the last weeks in class: YouTube, games, poker, MSN, community sites, blogs, and Pr0n.

Counting in Tossim

Just a silly application I wrote. A very naive approach to counting in a small sensor network. Programmed in NesC under TinyOS 1.0 and tested under tinyviz.

Since my students might read my blog, and this is an assignment for them, no source code but a simple description.

The network builds a small spanning tree in which a node continuously broadcasts the total of the branch of which it is the root.

All nodes run the same application, node 0 starts as the root of the tree. All nodes remain silent until they receive a broadcast message, node 0 initiates the algorithm.

A node alternatingly broadcasts an AskTotal() to everybody or an AnswerTotal(id,total) message to it's parent. The parent of a node is the first node from which it received an AskTotal().
Nodes store (id,total) pairs in a set. The total send by a node is the sum of the totals in this set plus one. (I guess I should restrict the protocol to just one message.)

The result is a pretty robust algorithm for static networks of a fixed maximal size and fixed maximal degree on the nodes. The algorithm gives the correct total in twice the depth of the tree time. For the shown network of 30 nodes, it calculates a correct answer in about 20 seconds.

Of course, you should never do it this way...

Area-Time Complexity of Binary Multiplication

Seems I am getting interested in an old hobby again. Anyway, the following is an interesting result.




"The area-time complexity of binary multiplication," written by R. P. Brent and H. T. Kung.

Three posts on one day. Oops, should get back to work.

Computing Solutions Uniquely Collapses the Polynomial Hierarchy

From siteseer, I am reading this, references the well-known "NP is as easy as detecting unique solutions" by Valiant and Vazirani (I lost my digital copy of that article).

The zoo comes in handy when reading an article like this.

Two for One: Scheme Interpreter in Python

Through this blog, a simple continuation-based scheme interpreter in Python.

#scheme.py
#This is a implementations of an interpreter
#for a small subset of scheme.
#
#What it has:
#Commands
#   Look at the function 'eval'
#Functions
#   look at the dictionary 'predefineds'
#
#Examples:
#1)Fibonacci numbers
#python scheme.py
#>>>(define fibonacci
#...  (lambda (n)
#...    (define fib 
#...      (lambda (n1 n2 cnt)
#...        (if (= cnt n)
#...            n1
#...            (fib n2 (+ n1 n2) (+ cnt 1)))))
#...    (fib 0 1 0)))
#>>>(display (fibonacci 10))
#55
#>>>
#
#2)Coroutines
#python scheme.py
#>>>(define list (lambda l l))
#>>>(define message 
#...  (lambda (cont msg)
#...    (call/cc 
#...     (lambda (newCont) 
#...       (cont (cons newCont msg))))))
#>>>(define f
#...  (lambda (fname cont msg)
#...    (display (cons fname msg))
#...    (define msgList (message cont (+ 1 msg)))
#...    (f fname (car msgList) (cdr msgList))))
#>>>(define msg 
#...    (call/cc (lambda (cont)
#...               (f "f1:" cont 1))))
#>>>(f "f2" (car msg) (cdr msg))
#
#Changes;
#24-Feb-2005 Added quote and the quote symbol '
#25-Feb-2005 Fixed a bug with begin
#25-Feb-2005 Added eval
#25-Feb-2005 Added py-eval and py-exec

#Uncomment the following line if you are using python 2.2
#from __future__ import generators
import re

py_context = {}
py_eval_func = eval

class context:
    def setVars(self, names, values):
        if names == None:
            return
        elif isinstance(names, symbol):
            self.vars[str(names)] = values
        else:
            (name, restNames) = names
            (value, restValues) = values
            self.vars[str(name)]=value
            self.setVars(restNames, restValues)

    def __init__(self, parent, var_names = None, values = None):
        self.parent = parent
        self.vars = {}
        self.setVars(var_names, values)

    def get(self, var_name):
        if self.vars.has_key(var_name):
            return self.vars[var_name]
        elif self.parent != None:
            return self.parent.get(var_name)
        else:
            raise KeyError("Unknown variable "+var_name)

    def set(self, var_name, value):
        if self.vars.has_key(var_name):
            self.vars[var_name] = value
        elif self.parent != None:
            return self.parent.set(var_name, value)
        else:
            raise Key("Unknown variable " + var_name)

    def define(self, var_name, value):
        self.vars[var_name] = value


class symbol:
    def __init__(self, value):
        self.value = value

    def __str__(self):
        return self.value

    def __repr__(self):
        return "symbol('"+self.value+"')"

    def __eq__(self, value):
        if isinstance(value, symbol):
            return self.value == value.value
        else:
            return False

# Predefined Symbols (can't be redefined)
LAMBDA = symbol("lambda")
IF = symbol("if")
BEGIN = symbol("begin")
SET = symbol("set!")
DEFINE = symbol("define")
LOAD = symbol("load")
QUOTE = symbol("quote")

#The tokenizer

#Token Types
OPENBRACKET = 0
CLOSEBRACKET = 2
ATOM = 3
SYMBOL = 4
DOT = 5
SINGLE_QUOTE = 6

tokens_re = re.compile(r'\(|\)|(?:[\w+\-*/<>=!?.]+)|'+
                       r'(?:"(?:[^"]|\\")+")|'+
                       r'(?:#(?:t|f|(?:\\(?:newline|space|.))))|'+
                       r'\'')
def tokenize(code):
    """This is a very simple tokenizer,
    it accepts a string that represents
    the code an returns a list of
    token type, token paris"""

    tokens = tokens_re.findall(code)
    for token in tokens:
        if token == "(":
            yield (OPENBRACKET, token)
        elif token == ")":
            yield (CLOSEBRACKET, token)
        elif token == ".":
            yield (DOT, token)
        elif token == "'":
            yield (SINGLE_QUOTE, token)
        elif token.isdigit():
            yield (ATOM, int(token))
        elif token[0]=='"':
            yield (ATOM, token[1:-1].replace(r'\\', "\\").replace(r'\"', r'"'))
        elif token[0]=="#":
            if token[1]=="\\":
                char = token[2:]
                if char == "space":
                    char = " "
                if char == "newline":
                    char = "\n"
                yield (ATOM, char)
            elif token[1]=="t":
                yield (ATOM, True)
            elif token[1]=="f":
                yield (ATOM, False)
            else:
                raise Exception("Invalid token "+ token)
        else:
            yield (SYMBOL, symbol(token))


#S-Espressions
def process_sexpr(tokens):
    token_type, value = tokens.next()
    if token_type == SINGLE_QUOTE:
        return [QUOTE, [process_sexpr(tokens), None]]
    elif token_type == OPENBRACKET:
        cons = [None, None]
        lst = cons
        token = None
        while True :
            token = process_sexpr(tokens)
            if token not in [")", "."]:
                cons[1] = [token, None]
                cons = cons[1]
            else:
                break
        if token == ".":
            cons[1] = process_sexpr(tokens)
            token_type, token = tokens.next()
        if token == ")":
            return lst[1]
        else:
            raise Exception("expected close bracket for expression "+
                            str(lst)+token)
    else:
        return value

def sexpr(text):
    return process_sexpr(tokenize(text))


def sexprs(text):
    """Build an s-expression from a string"""
    lst = [None, None]
    cur = lst
    tokens = tokenize(text)
    try:
        while True:
            cur[1] = [process_sexpr(tokens), None]
            cur = cur[1]
    except StopIteration:
        pass
    return lst[1]



#Pedefined Functions

#Convert a python function into a form
#suitable for the interpreter
def predefined_function(function):
    def func(continuation, args):
        argList = []
        while args!=None:
            arg, args = args
            argList.append(arg)
        return continuation, function(*argList)
    return func

#Some basic predefined functions

def display(obj):
    print obj

def callcc(continuation, args):
    (func, nil) = args
    def cont_func(cont, (arg, nil)):
        return (continuation, arg)
    return func(continuation, (cont_func, None))

def gen_eval(context):
    def eval_func(continuation, arg):
        expr, nil = arg
        return (eval_continuation(continuation, context, expr), None)
    return eval_func

def py_exec(continuation, arg):
    code, nil = arg
    exec code in py_context
    return (continuation, None)

def py_eval(continuation, arg):
    code, nil = arg
    return (continuation, py_eval_func(code, py_context))


global_context = context(None)

predefineds = {"+":predefined_function(lambda *args:sum(args)),
               "*":predefined_function(lambda *args:reduce(int.__mul__, args)),
               "-":predefined_function(lambda a, b:a - b),
               "<":predefined_function(lambda a, b:a < b),
               ">":predefined_function(lambda a, b:a > b),
               "=":predefined_function(lambda a, b:a == b),
               "cons":predefined_function(lambda a, b:[a, b]),
               "car":predefined_function(lambda(a, b):a),
               "cdr":predefined_function(lambda(a, b):b),
               "display":predefined_function(display),
               "call-with-current-continuation":callcc,
               "call/cc":callcc,
               "eval":gen_eval(global_context),
               "py-exec":py_exec,
               "py-eval":py_eval}

global_context.vars = predefineds

#Eval

#A continuation for the evaluation of an expression
class eval_continuation:

    def __init__(self, continuation, context, expr):
        self.next = continuation
        self.context = context
        self.expr = expr

    def run(self, val):
        return eval(self.next, self.context, self.expr)

def eval_str(continuation, context, code):
    if isinstance(code, str):
        code = sexpr(code)
    return eval(continuation, context, code)

#The eval method       
def eval(continuation, context,  code):
    if isinstance(code, list):
        if code[0] == LAMBDA:
            return eval_lambda(continuation, context,  code)
        elif code[0] == IF:
            return eval_if(continuation, context, code)
        elif code[0]== BEGIN:
            return eval_begin(continuation, context, code)
        elif code[0] == DEFINE:
            return eval_define(continuation, context, code)
        elif code[0] == SET:
            return eval_set(continuation, context, code)
        elif code[0] == QUOTE:
            return eval_quote(continuation, context, code)
        elif code[0] == LOAD:
            return eval_load(continuation, context, code)
        else:
            return eval_apply(continuation, context, code)
    elif isinstance(code, symbol):
        return (continuation, context.get(str(code)))
    else:
        return (continuation, code)

#Helper to evaluate a list of expressions
class expr_list_continuation:
    def __init__(self, continuation, context, exprs):
        expr, rest = exprs
        self.expr = expr
        if rest == None:
            self.continuation = continuation
        else:
            self.continuation = expr_list_continuation(continuation,
                                                       context, rest)
        self.context = context

    def run(self, value):
        return eval(self.continuation, self.context, self.expr)

def eval_expr_list(continuation, context, exprs):
    return (expr_list_continuation(continuation, context, exprs), None)


#Quote
def eval_quote(continuation, context, code):
    (quote, (item, nil)) = code
    return (continuation, item)

#Load
def eval_load(continuation, context, code):
    (load, (filepath, nil)) = code
    fi = file(filepath)
    exprs =  sexprs(fi.read())
    return eval_expr_list(continuation, context, exprs)

#Begin
def eval_begin(continuation, context, code):
    begin, exprs = code
    return eval_expr_list(continuation, context, exprs)

#Lambda
def eval_lambda(continuation, parent_context, code):
    (lmbda, (params, exprs)) = code
    def func(continuation, args):
        new_context = context(parent_context, params, args)
        return eval_expr_list(continuation, new_context, exprs)
    return (continuation, func)

#Define
class define_continuation:
    def __init__(self, continuation, context, var_name):
        self.continuation = continuation
        self.context = context
        self.var_name = var_name

    def run(self, value):
        self.context.define(self.var_name, value)
        return self.continuation, None

def eval_define(continuation, context, code):
    (define, (var_name, (expr, nil))) = code
    continuation = define_continuation(continuation,
                                       context, str(var_name))
    return eval(continuation, context, expr)

#set!
class set_continuation:
    def __init__(self, continuation, context, var_name):
        self.continuation = continuation
        self.context = context
        self.var_name = var_name

    def run(self, value):
        self.context.set(self.var_name, value)
        return self.continuation, None

def eval_set(continuation, context, code):
    (set, (var_name, (expr, nil))) = code
    continuation = set_continuation(continuation, context,
                                    str(var_name))
    return eval(continuation, context, expr)

#If    
class if_continuation:
    def __init__(self, continuation, context, ifTrue, ifFalse):
        self.continuation = continuation
        self.context = context
        self.ifTrue = ifTrue
        self.ifFalse = ifFalse

    def run(self, value):
        if value:
            return eval(self.continuation,
                        self.context, self.ifTrue)
        else:
            return eval(self.continuation,
                        self.context, self.ifFalse)

def eval_if(continuation, context, code):
    (If, (predicate, (ifTrue, rest))) = code
    if rest==None:
        ifFalse = None
    else:
        ifFalse = rest[0]
    return eval(if_continuation(continuation, context, ifTrue, ifFalse),
                context, predicate)


#Apply

class apply_continuation:
    def __init__(self, continuation):
        self.continuation = continuation

    def run(self, func):
        return func(self.continuation, self.params)

class param_continuation:
    def __init__(self, continuation, prev):
        self.continuation = continuation
        self.prev = prev
        self.params = None

    def run(self, value):
        self.prev.params = (value, self.params)
        return (self.continuation, None)

class list_param_continuation:
    def __init__(self, continuation, prev):
        self.continuation = continuation
        self.prev = prev
    def run(self, value):
        self.prev.params = value
        return (self.continuation, None)

def construct_param_continuations(continuation,
                                  prev, context, code):
    if isinstance(code, list):
        expr, rest = code
        paramContinuation = param_continuation(continuation, prev)
        continuation = eval_continuation(paramContinuation, context, expr)
        if rest == None:
            return continuation
        else:
            return construct_param_continuations(continuation, paramContinuation,
                                                 context, rest)
    else:
        continuation = list_param_continuation(continuation, prev)
        return eval_continuation(continuation, context, code)



def eval_apply(continuation, context, code):
    (operator, exprs) = code
    apply_cont = apply_continuation(continuation)
    continuation = eval_continuation(apply_cont, context, operator)
    continuation = construct_param_continuations(continuation, apply_cont,
                                                 context, exprs)
    return (continuation, None)

#The read eval loop

class read_eval_continuation:
    def __init__(self, context, reader):
        self.context = context
        self.reader = reader
        self.code = None
        self.continuation = None

    def run(self, value):
        try:
            if self.code == None:
                self.code = self.reader.next()
                self.continuation = read_eval_continuation(self.context,
                                                           self.reader)
        except StopIteration:
            return None, value
        return eval_str(self.continuation, self.context, self.code)


def expression_reader(fi):
    code = ""
    brackets = 0
    while True:
        if code == "":
            prompt = ">>>"
        else:
            prompt = "..."
        ln = raw_input(prompt)
        code+=ln+" "
        brackets+=ln.count("(") -  ln.count(")")
        if brackets == 0 and len(ln.strip())!=0:
            yield code
            code = ""

def read_eval_loop(fi):
    reader = expression_reader(fi)
    continuation = read_eval_continuation(global_context, reader)
    value = "Simple scheme!!!"
    while(continuation!=None):
        (continuation, value) = continuation.run(value)

if __name__=="__main__":
    import sys
    read_eval_loop(sys.stdin)

A Thousand Miles Behind

The new album "A Thousand Miles Behind" from David Gray is coming out next monday, October 8, 2007.





"Please forgive me," a song from his best known album "White Ladder."

Parallel Haskell in EETimes

As the title says: pHaskell in Embedded (EET). (Foto through Lennart Augustsson's page.)

Wisents on the Move

To read: "Embedded WiSeNts Research Roadmap".

According to a market study performed by ON World Inc. on Wireless Sensor Networks called “Wireless Sensor Networks – Growing Markets, Accelerating Demands” from July 2005, 127 million wireless sensor network nodes are expected to be deployed in 2010 and the growth of this market later on is expected to increase in certain application domains.

Wireless Sensor Networks are a canonical example of a wider field dealing with Cooperating Objects that attempts to create the necessary technologies to make Weiser’s vision of the disappearing computer a reality. Cooperating Objects are, in the most general case, small computing devices equipped with wireless communication capabilities that are able to cooperate and organise themselves autonomously into networks to achieve a common task.