10/30/07

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.

10/29/07

On One-Pass CPS Transformations



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

10/24/07

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].

10/23/07

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.

10/18/07

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.












FeatureTinyNodeSunspot
Power Consumptionvery low, 20mA, 6microA100 mA, 32 microA
LanguageNesCJava (not realtime)
Radioyesyes
Ledsred (red, yellow, green)8 tri-color LEDs
Poweradapter or two AAs3.7V rechargeable, 750 mAh, USB
Light Sensoryesyes
Accelero Meterno3-axis
Temperature Sensoryesyes
SimulatorMatureUnder Development
PricingEuro 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?

10/14/07

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

10/13/07

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

10/10/07

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.

10/7/07

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...

10/5/07

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)

10/3/07

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."

10/2/07

Parallel Haskell in EETimes


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

10/1/07

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.