netzstaub

Ich weiss immer noch nicht so recht, in welcher Sprache ich hier bloggen soll. Deswegen blogge ich jetzt abwechselnd auf deutsch, englisch und französisch. So wird jeder irgendwas nicht verstehen können

I’m still not sure about which language to use for this blog. I’ll blog in three languages for the next few posts: german, english and french. This way, everybody will be missing something. I’ll write a few technical postings in english though, to satisfy the new readers that slashdot has given me

Je ne sais pas trop quelle langue utiliser pour ce blog (en fait, je crois que je peux oublier le français, il y a quasi aucun lecteur ou lectrice francais qui me lit :). Je vais donc changer de langue au gré de mes humeurs dans les prochains temps. Comme ça, il y aura toujours quelqu’un qui ne comprendra pas les posts que je vais écrire, et je pouvoir me marrer en secret. Haha

Ich checke regelmässig meine Emailbox. Das ist also der ideale Ort, um dort meine Termine zu kennzeichnen. Dazu habe ich mir ein kleines Shellscript gebaut, das at und mail verwendet, also auf ziemlich jedem Unix tun sollte.

I regularly check my email INBOX. This makes it the ideal place to store meeting reminders. I wrote a small shell script to schedule meeting reminders. The script uses at and mail, and thus should work on most Unix platforms.

Poller le contenu de ma boîte mail est sans doute l’activité la plus regulière que j’ai C’est donc un endroit idéal pour stocker les notes qui me rapellent mes rendez-vous. Pour envoyer une note, j’utilise un petit script shell qui utilise at et mail, et devrait donc tourner sur la plupart des plateformes unix actuelles.

manuel@siff:~/siff-svn/misc $ cat reminder.sh
#!/bin/sh

echo -n "Reminder Subject: "
read subject
echo -n "Date: "
read date

echo "mail -s \"$subject - $date\" \"$USER\"" | at "$date"

Der Javascript-Compiler ist fertig, HTML kann ich aus dem Lisp auch generieren. Um eine halbwegs komplette Webseitenlösung zu bauen braucht jedoch eine weitere “Sprache”: CSS. Natürlich ist CSS keineswegs irgendwie kompatibel mit dem Rest, was die Syntax angeht. Und der Emacs-Mode, den ich finden konnte, passt mir überhaupt nicht. Was bleibt einem also übrig, als ein LISP nach CSS Formattierer zu bauen? Kann sein, dass ich an dem NIH-Syndrom leide, aber ich kann ziemlich gut damit leben

Zum Glück ist CSS “einfach”, was die Syntax und Struktur einer Datei angeht. Mittels “Selektoren” werden Knoten aus dem HTML Dokument ausgewählt, und ihnen werden dann “Properties”, die jeweils einen Namen und einen Wert haben, zugewiesen. Zum Beispiel:

* {

background-color: black;

}

Dieses CSS Konstrukt weist allen Knoten (der Selektor “*” selektiert alles) die Property “background-color” mit dem Wert “black” zu. Es gibt eine ganze Reihe an Properties, die von dem CSS 1 Standard festgelegt werden (es gibt auch CSS 2, aber das kenn ich jetzt nicht so wirklich). Viele von diesen Properties haben auch eine feste Anzahl an möglichen Werten. Das ist so ein bisschen wie eine Enumeration in C. Zum Beispiel unterstützt die Property “font-style” die Werte “normal”, “italic” oder “oblique”. Andere Properties unterstützen numerische Werte, unter Umständen gefolgt von einer Einheit. Grössen kann man z.B. in Pixel angeben (z.B. “10px”), oder als grössen von einem “m” (z.B. “10em”). Man kann sie auch als Prozentangaben der übergeordneten Element angeben (z.B. “10%”). Andere Werte, wie Farben, können entweder Farbnamen oder hexadecimal-Darstellungen der Farben in RGB annehmen. Also ein recht unübersichtliches Gewächs.

Die Frage stellt sich, wie man diese CSS-Struktur jetzt in Lisp darstellen soll. Dafür bin ich dem selben Ansatz gefolgt wie bei meinem Javascript-Compiler: im Zweifelsfall alles lasch handeln, der Programmierer wird schon wissen, was er tut. Ein Selektor kann also ein Symbol sein, ein String, oder eine Liste. Wenn es eine Liste ist, dann werden die einzelnen Element mit “,” zusammengebunden, es ist also eine Oder-Verknüpfung. Es gibt aber bei Selektoren auch die Möglichkeit, eine Hierarchie anzugeben. Wenn man z.B. die Kinder von dem Element P mit Id “foobar ansprechen will: “p#foobar *”. Diese hierarchischen Selektoren muss man in meinem CSS Generator ausschreiben. Ist nicht so ganz schick, aber fürs erste tut. Jetzt als erstes ein Beispiel, damit ich nicht ins Leere blogge, und damit ihr euch vorstellen könnt, was ich meine.

Unser CSS:

body,td,p {

font-family:Verdana, “Trebuchet MS”, Trebuchet, Arial, sans-serif;

font-size:11px;

line-height:16px;

color:#666666;

}

li {

margin:3px 0px;

padding:0px 0px;

}

a:link,a:visited {

color:#989833;

text-decoration:none;

}

a:hover,a:active {

text-decoration:underline;

}

Jetzt die LISP-Darstellung:

(css-file

;; general tags

((:body :td :p)

:font-family “Verdana, \”Trebuchet MS\”, Trebuchet, Arial, sans-serif”

:font-size “11px”

:line-height “16px”

:color “#666666″)

(:li

:margin “3px 0px”

:padding “0px 0px”)

((”a:link” “a:visited”)

:color “#989833″

:text-decoration :none)

((”a:hover” “a:active”)

:text-decoration :underline))

Die CSS-Regeln sind jetzt also… Listen (!). Das erste Element einer CSS-Regel-Liste ist der Selektor. Der Rest sind dann die Properties. Die Namen der Properties sind eigentlich im CSS Standard festgelegt, und bestehen alle aus lowercase-Strings. Man kann sie also durch Keyword-Symbole darstellen. Damit ergibt sich für die CSS-Regel auch eine Struktur, die Lisp-Programmierern geheuer ist. Man kann z.B. auf die Property einer CSS-Regel mit (GETF (CDR RULE) PROPERTY) zurückgreifen. In bestimmten Fällen (Browserspezifische Extensions z.B.) will man auch “komisch” geformte Properties angeben wollen, Strings gehen also immer noch. Hier sind alle Property-Werte Strings, es gehen aber auch wieder Symbole (die nach lowercase-Strings konvertiert werden) oder Nummern.

In dem obigen Beispiel sieht man auch, was für Selektoren möglich sind. Um Tags zu selektieren kann man einfach das Keyword verwenden. Das ist dann ein bisschen so wie bei dem HTML-Generator. Man kann aber auch Strings angeben. Z.B. kann man nicht A:HOVER als Symbol hinschreiben, weil der LISP-Reader das als “das Symbol HOVER im Package A” interpretiert. Deswegen also “a:hover”. Die erste CSS-Regel soll auf BODY, TD und P Elemente zugleich angewendet werden, ich hab daraus also eine Liste gemacht.

Jetzt aber genug an dem Beispiel rumerklärt, hier der Lisp Code. Als erstes brauchen wir eine Funktion, die aus unseren Werten (Symbol, String oder Wasauchimmer) ein String generiert. Diese Funktion wird dann sowohl auf die Selektoren als auch auf die Propertynamen als auch auf die Propertywerte losgelassen.

(defun val-to-string (val)
  (cond ((stringp val) val)
	((symbolp val) (string-downcase (symbol-name val)))
	(t (princ-to-string val))))

Die Funktion ist weitgehend selbsterklärend. Interessant ist, dass die meistens Funktionen die wir jetzt geschrieben haben sind stark ähneln. Sie laufen sozusagen einen Baum ab, und machen auf dem Baum Pattern-Matching. Wenn der Wert hier ein String ist, wird er als solcher zurückgegeben. Das gibt dem Programmier alle Freiheiten, die er braucht, um das Output zu tweaken. Wenn ihm Lustig ist kann er hier komplette CSS-Regeln auch übergeben, oder CSS-Kommentare. Der CSS-Generator ist also “Zukunftssicher” (*hust* *hust*).

Als nächstes brauchen wir einen Datentyp für unsere CSS-Rules (als interne Darstellung). Natürlich verwenden wir dazu auch wieder Listen, und bauen die passenden Funktionen als Abstraktionen dazu.

(defun make-css-rule (selectors properties)
  (list (mapcar #'val-to-string
		(if (atom selectors)
		    (list selectors)
		    selectors))
	properties))

(defun css-rule-selectors (css-rule)
  (first css-rule))

(defun css-rule-properties (css-rule)
  (second css-rule))

(defmacro css-rule (selectors &rest properties)
  `(make-css-rule ',selectors ',properties))

MAKE-CSS-RULE erleichtert uns schon die Arbeit, indem es die Selektoren schon zu Strings konvertiert. Es konvertiert auch einen einzelnen Selektor zu einem OR-Ausdruck mit einem Element (also eine Liste mit einem Element). Dadurch haben wir später weniger Spezialfälle zu berücksichtigen. Das Makro CSS-RULE ist nur da, weil ich faul bin, und nicht immer quoten will.

CSS kann man auch inline als Attribut eines HTML Elements angeben. Da werden aber keine Selektoren mehr angegeben, weil der Knoten ja schon ausgewählt wurde. Für diesen Minimalfall brauchen wir also eine Funktion, die eine Property nach String konvertiert. Diese ist erstaunlich kompliziert:

(defun propval-to-string (propval)
  (format nil "~A:~A" (val-to-string (first propval))
	  (val-to-string (second propval))))

Das passende Makro zum Einsetzen in dem HTML Generator ist auch nicht wesentlich schwieriger:

(defmacro css-inline (&rest propvals)
  `(concatenate 'string ,@(loop for propval on propvals by #'cddr
				collect (propval-to-string propval))))

Mit diesem Grundbaustein können wir jetzt die Funktion CSS-RULE-TO-STRING bauen, die noch die Selektoren davor packt:

(defun css-rule-to-string (css-rule)
  (format nil "~A {~%~{~A;~%~}}~%~%"
	  (string-join (css-rule-selectors css-rule) ",")
	  (loop for propval on (css-rule-properties css-rule) by #'cddr
		    collect (concatenate 'string "   " (propval-to-string propval)))))

Das ist wie immer Hack-Code, deswegen auch die vielen Loops (ich kann damit besser Prototypen). Wo wir jetzt eine Regel zu einem String konvertieren können ist der Rest nur noch formalkrams:

(defmacro css (&rest rules)
  `((:style :type "text/css")
    (:princ #\Newline "<!--" #\Newline)
    (:princ ,@(mapcar #'(lambda (rule) `(css-rule-to-string (css-rule ,@rule))) rules))
    (:princ "-->" #\Newline)))

(defmacro css-file (&rest rules)
  `(html
    (:princ
     ,@(mapcar #'(lambda (rule) `(css-rule-to-string (css-rule ,@rule))) rules))))

Zum Schluss ein paar Anwendungsbeispiele:

;;; generate a CSS file
#+nil
(html-stream *standard-output*
      (css-file (* :border "1px solid black")
	    (div.bl0rg :font-family "serif")
	    (("a:active" "a:hoover") :color "black" :size "200%")))

;;; generate an inline CSS spec in a HTML head element
#+nil
(html-stream *standard-output*
  (html
   (:html
    (:head
     (css (* :border "1px solid black")
	  (div.bl0rg :font-family "serif")
	  (("a:active" "a:hoover") :color "black" :size "200%"))))))

;;; generate a style attribute for a DIV element
#+nil
(html-stream *standard-output*
      (html (:html (:body ((:div :style (css-inline :border "1px solid black"))
			   "foobar")))))

Das wars, jetzt haben wir alle Werkzeuge, um Webseiten kompletten aus dem Lisp zu generieren.

700 Series Design Manual

Designing Analog Chips

Building a modern computer from first principles

Fischerspooner Bootlegs

So, nachdem der Slashdotsturm vorbei ist, ein paar Links (hauptsächlich Webkram):

Hakim Bey and Ontological Anarchy

QuirksMode - for all your browser quirks

The Linux-PAM Module Writers’ Guide

Unobtrusive Javascript

(In der Kategorie merken damit nicht nerven). Um CL-GD mit GIF Support unter Debian, Ubuntu oder was auch immer zum Laufen zu kriegen.
In die apt-sources.list folgendes:

deb http://www.mstucki.net/debian/ woody all

Dann apt-get install libgd2-dev && cd cl-gd && make und dann (asdf:oos ‘asdf:load-op :cl-gd :force t), Et voila, an der Nase der Opensourcelizensenverfechter vorbei GIF support.

Flow-Based Programming (noch nicht gelesen)

Kam jetzt über Lispmeister

Damit ich das hier bloss nicht vergesse:

• Automatisches Indenting fuer spezielle Lispfunktionen. Entweder Zeile in die .emacs packen, oder als automatische Variable in das Lisp-File selber packen. Wenn der Emacs das File laedt fragt er dann ob der Code ausfuehren soll. Also, in .emacs:

  (put 'html-search 'lisp-indent-function 1)
  

  In dem Lisp-File:

  ;;; Local Variables:
  ;;; eval: (put 'html-search 'lisp-indent-function 1)
  ;;; End:
  

• DVDs brenn0rn unter Linux (danke Neingeist):

  growisofs -use-the-force-luke -Z /dev/scd0 -R -J $dirs

I discovered Protothreads through a link in Chris Double’s weblog on Saturday. This is a fascinating tiny library, written by Adam Dunkels, a researcher at the Swedish Insitute of Computer Science. The Protothreads library implements user-level in threads in portable ANSI C in a mere 20 lines of code, and each thread uses only 2 bytes of RAM! While having a few important limitations, this comes in handy for a lot of problems, especially when writing single-threaded network servers (using Protothreads, you don’t have to use state machines to do protocol handling). While checking out Protothreads, I stumbled across the very interesting link list that Adam Dunkels compiled while writing his library. From there, I got hooked and browsed the rest of Adam’s website.

He has written two incredible TCP/IP stacks aimed at embedded systems. The first one, uIP, is targeted at 8bit microcontrollers, and has a very low RAM usage (it runs with as few as 128 bytes RAM for full TCP/IP support). The development version of uIP uses Protothreads to offer a BSD-style socket interface while maintaining its low RAM usage. The second stack, lwIP, is targeted at bigger embedded systems, and offers a BSD-style API.

Adam is a computer scientist working in the field of sensor networks, which are a part of the research field of ubiquitous computing. Sensor networks consist of a myriad of little embedded systems gathering environmental data through a set of sensors. However, the real value of sensor networks stems from the communication between all these systems. As Adam put it, “the nodes are interchangeable: it is the data generated by the sensors that are the primary interest”. Besides uIP, which he uses as a mean to communicate between the sensor nodes, Adam works on Contiki, an embedded operating system. Contiki allows the dynamic loading of code on sensor nodes, which proves to be very useful when deploying sensor networks.

I emailed Adam a few questions about his software, embedded programming and sensor networks. He was very kind to provide exhaustive and very interesting answers. Enjoy the interview

Protothreads

These first three questions are about Protothreads, the minimal threading library Adam has written for his embedded platforms. Protothreads are inspired by coroutines, which can be sort of implemented in C using a neat little trick.

Question: Adam, what was your motivation to write protothreads?

Answer: The driver behind the development of protothreads was many years of writing event-driven code. After a while, one sees the need to have a nicer abstraction than finite state machines. Ordinary threads have many of the good properties of such an abstraction, but they have two problems: the RAM overhead is prohibitive on systems with very small memory resources —the typical target system for uIP—, and they require a fair amount of platform specific code. As I wanted to keep both uIP and Contiki as portable as possible, this was definitely a problem.

After thinking long and hard about this, as well as reading lot of papers on the subject of concurrency, the protothreads concept dawned on me. Very simple, yet powerful. Very little RAM overhead and possible to

implement in pure C. Perhaps the nicest thing is the extremely small size of the implementation. With all comments removed, the entire library can be reduced to 20 lines of code (that goes into a header file, no less!).

Question: What kind of software uses Protothreads currently?

Answer: Currently, the Contiki OS and the development version of the uIP TCP/IP stack are using protothreads. Among other things, they are used to implement a network API called “protosockets”, which are similar to the BSD socket API but based on protothreads. This means that they can be used without underlying full multithreading, which subsequently means less RAM overhead.

Question: What kind of software do you think will use Protothreads in the future?

Answer: I would expect that protothreads would find its biggest use in embedded systems, since that’s where the really tough memory constraints are. But you never know where this kind of software will end up. That’s the real beauty of releasing open source software: it might turn up in the most unexpected places.

lwIP and uIP

Adam Dunkels is working on the integration of TCP/IP with sensor networks, and has written two embedded TCP/IP stacks. uIP is aimed at very small embedded platforms, while lwIP is more similar to a BSD IP stack.

Question: What were the main problems you faced while developing uIP?

Answer: The biggest challenge of uIP is flushing out bugs in TCP. Every now and then a new weird corner case in TCP turns up. Typically, these bugs have a pretty lengthy sequence of events that has to be followed in order to reproduce the bug. Weird corner case bugs seem to be an inherent property of TCP; there was a working group in the IETF (Internet Engineering Task Force, the standardization body of the Internet’s communication protocols) that worked on this. They produced an RFC on the topic: RFC2525, “Known TCP Implementation Problems”, Paxson (editor).

Question: How did you structure your development cycle? For example, did you write a prototype following a certain approach, then discard it and rewrite, or did you work on the same “stack” throughout the project?

Answer: I am a proponent of the “discard and rewrite” principle, but I seldom manage to follow it myself… The base of uIP has been the same since the very first release. Perhaps this is a sign of a good design: it managed to capture the basic flow of control and structure of the code while being flexible enough to allow later enhancements such as protosockets and multiple network interfaces (which were not present in the first versions).

Question: What was you development setup while developing uIP? Did you test it on embedded devices directly? What kind of development tools did you use (for example, did you debug the stack directly on embedded devices?)

Answer: I do all code development under FreeBSD, running uIP as a user process. I almost never develop code high level code like a networking stack on a target device, but only verifies that everything works as expected. Of course, low level code such as device drivers cannot be developed without doing parts of the development on the target device.

In fact, I was not even the first person to run uIP on an embedded device - that was done by others that I was in email contact with. After a while, one gets a feeling for what kinds of problems that can arise when running on a target device and takes special care to tend to the “sensitive” parts of the code.

All in all, this development philosophy works surprisingly well.

Question: What kind of applications are using your embedded stacks lwIP and uIP? Which ones do you think are the most interesting?

Answer: lwIP and uIP are used in so many applications that I’ve lost track of most of them. I recently wrote down a list of companies and academic institutions that I know are using either lwIP or uIP and ended up with a list of 60 items - and this was purely from memory. And that’s just the applications that *I* know about.

Some of the more notable recent uIP applications are the CubeSat kit that uses uIP to communicate with so-called pico-satellites in space, and a container tracking and security system in which uIP is used to communicate with wireless reader terminals on cranes at ports and on ships at sea. Other uses include remote monitoring for waterworks, instruments used in bore holes, in weather stations, and in development kits for embedded devices. lwIP is also being used in a bunch of interesting applications such as TV transmission equipment used by BBC and CNN among others, and in devices that were used for the post production of the second Lord of the Rings films. lwIP is also used in numerous system development kits from e.g. Xilinx, Altera, and Analog Devices.

Question: Could you tell us something about the CubeSat?

Answer: From my point of view, the most interesting thing with uIP in theCubeSat kit is the extremely small packet buffer that is used. The RAM footprint for the entire uIP stack is as small as 128 bytes, where something like 96 bytes was used for the packet buffer. I never thought that such a small RAM configuration would ever be used in a real system. In their system, however, the space-to-earth communications link is not fast enough to warrant a larger buffer anyway.

Question: What is the advantage of using TCP/IP as a communication protocol between sensor nodes, instead of, say, a custom “over the wire” or “over the air” protocol, and then add maybe a TCP/IP gateway so that “normal” nodes can access the sensor network?

Answer: Most people working with sensor networks have designed custom protocols for the sensor network, but we’ve decided to go the other way and investigate if TCP/IP can be used even inside wireless sensor networks.

There is really only one advantage of using TCP/IP inside the sensor networks: ease of connectivity to IP networks. With a TCP/IP sensor network, any node can connect to outside networks without special proxies or protocol converters. The challenge lies in making TCP/IP as efficient as custom protocols. I don’t think we’ll be able to make it 100% as efficient, but if we can get it to be, say, 95% as efficient, then the extra advantage of connectivity may be worth it. Many applications of sensor networks require some form of external connectivity, and may therefore benefit from this work.

We are looking into five techniques that are intended to make TCP/IP viable for sensor networks:

• Spatial IP addressing. Normal IP addresses are based on network topology and each host has its own unique address. With spatial IP addressing, each sensor node constructs its own IP address from its spatial location. If two nodes get the same address, it does not really matter because the sensors’ identities are not particularly important: it is the data that is important.
• Application overlay routing. Routing in IP network is based on addresses and network topology, whereas routing in sensor networks is more effective if based on sensor data and interests. We implement data-centric routing by using an application overlay on top of TCP/IP.

• Shared context header compression. TCP/IP headers are large compared to what can be achieved with custom protocols. We note, however, that header compression works exceptionally well in sensor networks because all nodes already know each other - they share the same context. This enables headers to be compressed from 28 byted (UDP/IP headers) down to 1-3 bytes.

• Distributed TCP Caching (DTC). It is well-known that TCP performs poorly in wireless networks. With DTC, we let sensor nodes cache TCP segments for each other in order to perform localized retransmissions. This helps reducing the energy consumption of TCP.

• The uIP TCP/IP stack, which shows that TCP/IP can be efficiently implemented even on the severely constrained sensor nodes.

Embedded development

An Embedded Sensor Board.

Question: You said that after a while, one gets a feeling for what kinds of problems can arise when running on a target device. Could you summarize what the most important kinds of problems are, and how you go about working around them? I know this is a very general question

Answer: When working with embedded networking, there are a few issues that typically arise (from the top of my head): memory alignment, ROM vs RAM pointers, near/far pointers, byte order, stack size. Some platforms cannot read memory from addresses that are not nicely aligned and this typically becomes a problem when an application passes a misaligned pointer to the networking stack. If the network stack tries to read data in chunks of two or four bytes (i.e., using shorts or longs) the whole program will crash. Also, some platforms are of the “Harvard architecture” kind, where ROM and RAM have different address spaces. Usually a special instruction must be used to translate between the two. Again, the problem is when an application passes a pointer to the protocol stack and the protocol stack does not know if the pointer points to ROM or RAM. Issues are similar for near/far pointers.

Byte order is a problem, albeit a much smaller one. It basically boils down to always converting 16-bit quantities into host byte order when they are read from network data, and convert data back into network byte order when it is written to the network.

Stack size problems are typically much harder to find. They usually manifest themselves by simply crashing the device, without much evidence of why the system crashed. The problem is that the CPU stack for the application was under-provisioned and the stack would overwrite other sensitive memory.

Question: Do you have a favourite embedded platform, and in case you do, which one and why?

Answer: No, I don’t have any favorite platform

Sensor networks

The sensors Adam Dunkels is working with.

They are called “Embedded Sensor Board” and come from the FU Berlin.

Question: You are currently working on sensor networks. Could you briefly describe what your special area of interest is?

Answer: My main research interest in wireless sensor networks is trying to bring together TCP/IP (the Interent protocol suite) and sensor networks. The challenge is that the networks for which TCP/IP was designed are so essentially different from wireless sensor networks. Wireless sensor networks are based on low bandwidth radio communication channels with potentially high error-rates, whereas the Internet have high bandwidth

links with virtually no bit errors. The nodes in a sensor network are severely resource constrained (energy, memory, CPU), where as Internet nodes (PCs, workstations, routers) are high performance machines. And so

forth. But the most interesting thing is that the applications running on top of the networks are so completely different: in sensor networks, in most cases it is not even meaningful to talk about the individual node’s addresses because the nodes are interchangeable: it is the data generated by the sensors that are the primary interest. This is in stark contrast to the Internet, where it is of primary interest that data gets to or comes from a particular host. In order to bring TCP/IP into wireless sensor networks, there are a bunch of interesting problems that needs to be solved. (See my licentiate thesis for details).



Question: What do you think is going to be the future of sensor networks, which is a “hot” topic of research at the moment?

Answer: The area of sensor networks has grown tremendously over the last few years. I would say that one of the current trends is that sensor networks are getting mature enough to allow people to make real deployments and experiments with them. Also, there are numerous companies that have been formed around these concepts.

As part of this trend, I am on the organization committee for the REALWSN’05 workshop on real-world issues with wireless sensor networks. The workshop is focused on things like software development, experimentation, and applications of real-world sensor networks. There are also a few other workshops around similar topics (e.g. IEEE EmNetS-II and SIGCOMM E-WIND).

Contiki OS



Question: You developed an operating system for sensor devices named Contiki, which allows dynamic loading of code in a sensor network. I must admit I have never seen a sensor network at work, so I am very interested in hearing about how you use dynamic loading of code in day-to-day operation.



Answer: Traditionally, operating systems for tiny embedded systems and for sensor networks (e.g. TinyOS) have required that a single monolithic binary of the entire system (OS + applications) is built and downloaded into each device. When developing software for wireless sensor networks, which may be composed or large numbers of nodes, this is not very practical. If we need to manually collect the nodes in order to download a new binary image, it takes hours to reprogram even a small network (20 nodes). There are ways to download the monolithic binary to sensors using the radio, however.

What Contiki does is that it allows us to dynamically load and unload individual applications running in the wireless sensor nodes. That is, we can leave the OS running on the nodes and only replace a small application program. The application program is broadcast to all nodes using the radio. I am attaching a few photos from my office just to get a feeling of the amount of sensor nodes we have in prototype networks.

When we were developing a prototype sensor networks together with Saab Technologies, we initially did not have the dynamic loader working and were forced to manually collect and reprogram the nodes using a parallel cable attached to a PC. With 20 nodes, just downloading new code onto them took a very long time. When we got the dynamic loader working, we could cut down the reprogramming time from hours to seconds.

(See Adam Dunkels, Thiemo Voigt, Niclas Bergman, and Mats Jönsson. “The Design and Implementation of an IP-based Sensor Network for Intrusion Monitoring“. In Swedish National Computer Networking Workshop, Karlstad, Sweden, November 2004.) Later this year, we will be deploying a sensor network in the Gulf of Bothnia that will be used to monitor the water temperature. Being able to remotely reprogram the network will be great for this network: we don’t really want to swim out and dive down to the nodes in order to reprogram them

A screenshot of the Contiki simulator.

Question: In a similar way, how do you develop, test and deploy the software you are working on? Do you simulate the network? Do you have an army of deployed sensors? How do test the function of you software in case of sensor/hardware failure?

Answer: I do most of the software development in a small network simulator I have written. It runs each Contiki node as a separate process and has a very simple radio simulation model. The network is displayed in a window and radio communication is shown as circles. The simulator allows me to debug individual nodes with gdb, and to get a feeling for the traffic patterns in the network. I am attaching a screenshot.

As for debugging a deployed network, I personally don’t have a good solution. I know, however, that there are researchers working on this problem and hopefully their work will lead to better ways to develop and test software running inside wireless sensor networks.

General

And last but not least, a few general questions about the books Adam reads, and what he thinks about Opensource.

Question: What books, papers or articles were the most influential for your work and the way you program?

Answer: I don’t have any particular book or paper that I consider to be the most influential for my work. I read a lot of papers and follow conferences in the general networking area, but on wireless sensor networks in particular, and I also try to keep up with operating systems research and related areas.

Question: As an open-source developer, how do you find the time to develop open-source software? I think that as a computer science researcher, this is going to be easier than for other programmers, but did you encounter any problems when releasing your software? Did you have to make any compromises? How did you choose the license you release uIP, lwIP, Protothreads and Contiki?

Answer: Yes, I am one of the lucky few that are able to develop open-source software as part of my profession. My lab at SICS (the Computer and Network Architectures laboratory) are very open to open source software. Most of us run FreeBSD, and when I started at SICS back in 2000 at least two of us were actively working on the system and one was a FreeBSD committer. So releasing my software as open source have never been a problem.

When I first was planning on releasing the first version of lwIP I didn’t know that much about open source and free software. I initially wanted to release the lwIP code under the GPL but after talking about this with my lab manager, we decided to release it under the BSD license instead. This has turned out to be a really good decision: the BSD license have allowed people to use the code without being forced to open up their entire source code. This has led to a lot of people using the software, which in turn has led to a lot of people contributing a lot of both good patches and entire modules of code.

Question: How do you feel about software patents? Did software patents change the way you write and release sourcecode?

Software patents seem to do more harm than good.

Ich bin in letzter Zeit dabei, Struktur aus HTML Seiten zu gewinnen. Ich habe eine grosse Sammlung an HTML Dateien, die aus einer Datenbank generiert wurde. Leider habe ich keinen Zugriff auf die Datenbank selber, so dass ich die unterliegenden Metadaten aus dem HTML gewinnen muss. In Perl gibt es für sowas zum Beispiel das nette Modul HTML::TreeBuilder, in Lisp habe ich leider nichts dergleichen gefunden. Es blieb also nichts anderes üblich, als was eigenes zu entwerfen. Wie in den anderen Lisp-Artikeln werde ich hier ausführlich meine Gedankengänge niederschreiben. D.h., dass in diesem Posting auch viele Codebeispiele vorgestellt werden, die nicht zur eigentlichen Lösung gehören. Ich denke jedoch, dass es relativ interessant ist, zu sehen, wie jemand probiert und versucht, bis er was Einsetzbares programmiert

Parsen von HTML

Der erste Teil, der wohl am anstrengendsten zu programmieren ist, war zum Glück schon vorhanden. Um aus der HTML-Datei einen HTML-Baum zu generieren, verwende ich das XMLUtils Modul, dass von der Lisp-Firma Franz als Opensource zur Verfügung gestellt wird. Mit XmlUtils, bzw. mit dem Teilpaket PHTML kann man einen HTML-Buffer in die HTML-Darstellung von Franz verwandeln. Hier zum Beispiel, wie man die Apache-Default-Seite parst:

CL-USER> (net.html.parser:parse-html
          (net.aserve.client:do-http-request "http://localhost"))

((:!DOCTYPE " html PUBLIC \"-//W3C//DTD XHTML 1.0 Transitional//EN\"
    \"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd\"")
 ((:HTML :XMLNS "http://www.w3.org/1999/xhtml")
  (:HEAD (:TITLE "Test Page for Apache Installation"))
  (:COMMENT
   " Background white, links blue (unvisited), navy (visited), red
(active) ")
  ((:BODY :BGCOLOR "#FFFFFF" :TEXT "#000000" :LINK "#0000FF" :VLINK
    "#000080" :ALINK "#FF0000")
   (:P "If you can see this, it means that the installation of the "
    ((:A :HREF "http://www.apache.org/foundation/preFAQ.html")
     "Apache web
server")
    " software on this system was successful. You may now add
content to this directory and replace this page.")
   ((:HR :WIDTH "50%" :SIZE "8"))
   ((:H2 :ALIGN "center") "Seeing this instead of the website you
expected?")
   (:P "This page is here because the site administrator has changed the
configuration of this web server. Please "
    (:STRONG "contact the person
responsible for maintaining this server with questions.")
    "
The Apache Software Foundation, which wrote the web server software
this site administrator is using, has nothing to do with
maintaining this site and cannot help resolve configuration
issues.")
   "

" ((:HR :WIDTH "50%" :SIZE "8"))
   (:P "The Apache " ((:A :HREF "manual/") "documentation")
    " has been included
with this distribution.")
   (:P "You are free to use the image below on an Apache-powered web
server. Thanks for using Apache!")
   ((:DIV :ALIGN "center") ((:IMG :SRC "apache_pb.gif" :ALT ""))))))
CL-USER>

Rudimentäres Suchen

Als Lisp-verwöhnter Mensch würde man jetzt fröhlich anfangen, nach Knoten zu suchen. Angenommen, wir würden aus der Seite alle Links extrahieren, dann könnte man eine Art rekursiven Knoten-Matcher bauen, der für alle gematchten Knoten eine Callbackfunktion aufruft. Das sieht z.B. so aus:

(defun node-match (node-name tree callback)
  (when (consp tree)
    (when (or (eql (first tree) node-name)
              (and (consp (first tree))
                   (eql (caar tree) node-name)))
      (funcall callback tree))
    (map nil #'(lambda (child)
                 (node-match node-name child callback))
         (cdr tree))))

Angewandt auf unsere Apache-Beispielsseite kommt folgendes Ergebnis zustande:

CL-USER> (node-match :a *html* #'(lambda (tree) (format t "matched ~A~%" tree)))
matched ((A HREF http://www.apache.org/foundation/preFAQ.html)
         Apache web
server)
matched ((A HREF manual/) documentation)
NIL
CL-USER>

Jedoch ist so eine Matchfunktion sehr lästig, sobald man Knoten und ihre Kinder z.B. matchen will. Kompliziert wird es auch, wenn man Attribute eines Knoten matchen will, dann muss eine spezielle Matchfunktion her, denn das EQL aus dem obigen Beispiel reicht nicht mehr aus. Weiterhin müssen in der Callbackfunktion die relevanten Daten aus dem gematchten HTML-Knoten wieder extrahiert werden. Wenn wir zum Beispiel die URL eines Links bearbeiten wollen (also das HREF Attribut eines A Knoten), dann müssen wir diese aus der Attribut-liste des Knotens hervorzaubern. Diese ganzen Schritte wollen wir jetzt extrahieren, und in einen HTML-Matcher verpacken.

Pattern Matcher aus PAIP

Als Vorlage für diesen HTML-Matcher habe ich den Pattern Matcher aus dem Buch “Paradigms of Artificial Intelligence Programming” von Peter Norvig verwendet. Der Pattern Matcher von Norvig kann ein Pattern, das natürlich in Listenform vorliegt, gegen eine andere Liste matchen. Dazu werden spezielle Symbole als “Variablen” verwendet, die ein Teil der Liste binden können. Eine Anwendung des Pattern Matchers von Norvig sieht z.B. so aus:

CL-USER> (match '((:a :href ?href) ?link) '((:a :href "foobar") "blorg"))
((?href . "foobar") (?link . "blorg"))
CL-USER>

Diese Ergebnisliste sind Bindings, also die Zuweisung von Variablen an die Knoten, die gematcht wurden. Diese Bindings kann man mit einer ganzen Reihe von Funktionen abfragen und bearbeiten. Der Vollständigkeit halber gebe ich sie hier wieder. Diese Funktionen kommen alle direkt aus dem Buch von Norvig, der Quellcode zu dem Buch kann man auf der Webseite zum Buch runterladen.

(defconstant fail nil
  "Indicates pat-match failure")

(defconstant no-bindings '((t . t))
  "Indicates pat-match success, with no variables")

;;; variable handling
(defun variable-p (x)
  "Is x a variable (a symbol beginning with '?')?"
  (and (symbolp x) (equal (char (symbol-name x) 0) #\?)))

(defun get-binding (var bindings)
  "Find a (Variable . value) pair in a binding list."
  (assoc var bindings))

(defun binding-var (binding)
  "Get the variable part of a single biding."
  (car binding))

(defun binding-val (binding)
  "Get the value part of a single biding."
  (cdr binding))

(defun make-binding (var val)
  (cons var val))

(defun lookup (var bindings)
  "Get the value part (for var) from a binding list."
  (binding-val (get-binding var bindings)))

(defun extend-bindings (var val bindings)
  "Add a (var . value) pair to a binding list."
  (cons (make-binding var val)
	;; Once we add a "real" binding,
	;; we can get rid of the dummy no-bindings
	(if (eq bindings no-bindings)
	    nil
	    bindings)))

(defun match-variable (var input bindings)
  "Does VAR match input? Uses (or updates) and returns bindings."
  (let ((binding (get-binding var bindings)))
    (cond ((not binding) (extend-bindings var input bindings))
	  ((equal input (binding-val binding)) bindings)
	  (t fail))))

Erweiterung auf einen HTML Matcher

Dieser Pattern-Matcher ist allerdings auf Listen zurechtgeschnitten, und kommt mit den speziellen Eigenschaften von HTML-Dokumenten nicht zurecht. So berücksichtigt z.B. der Pattern-Matcher von Norvig die Reihenfolge der Knote. In unserem Fall ist aber z.B. die Reihenfolge der Attribute eines Knotens irrelevant. Wir wollen mit ‘((:a :href ?href :target ?target)) genauso <a href=”foobar” target=”_blank”></a> wie auch <a target=”_blank” href=”foobar”></a> matchen. Weiterhin wollen wir ungematchte Attribute am besten gleich ignorieren. Wenn wir einen Link extrahieren wollen, interessieren wir uns nun wirklich nicht für die Style Attribute, die ein Webdesigner da im HTML verstreut hat. Weiterhin wollen wir auch ganze Teile des HTML-Baums ignorieren wollen. Z.B. wollen wir beim Matchen einer Tabelle bestimmte Rows ignorieren können. Dazu leiten wir eine ganz spezielle Variable ein, die Ignore-Variable, die zwar wie eine normale Variable matcht, aber kein Binding erstellt. Diese Variable heisst ?_. Wir wissen bei HTML nie, wieviele Kinderknoten jetzt ein Knoten haben kann. Deswegen ist eine Variable jetzt “greedy”, sie matcht soviele Knoten wie sie kann. Hier ist anzumerken, dass der HTML-Matcher in der jetzigen Form kein Backtracking kann, es ist also nicht möglich Patterns zu schreiben wie ‘((:a :href ?href) ?knoten (:p ?paragraph) ?weitere-knoten). Der Wuergaround ist hier zuerst auf ‘((:a :href ?href) ?knoten) zu matchen, und dann ?knoten nachzubearbeiten. Nicht wirklich schick, aber bis jetzt hat das auch so ganz gut funktionniert. Der letzte Trick bei dem HTML-Matcher ist, dass nicht nur eine Bindingsammlung als Ergebnis geliefert wird, sondern eine Liste aller möglichen Matchings. Wenn wir z.B. nach Links suchen, wäre das Ergebnis eine Listen von den Bindings für jeden einzelnen Link-Knoten.

Was sind nun an Veränderungen erforderlich für unseren HTML Pattern Matcher. Als erstes brauchen wir eine Funktion, mit der wir “Knotenköpfe” matchen können. Als Knotenköpfe bezeichne ich die Listen, in denen der HTML Parser von Franz die Beschreibung der Knoten und ihrer Attribute stehen, also z.B. oder (:A :HREF “foo”). Diese Knotenköpfe können sowohl Atome seine (nur :P), oder Listen. Die Matchingfunktion kommt damit zurecht, in dem es aus Atome einfach eine Liste macht Ganz wie in dem Patternmatcher von Norvig werden hier als Argument das Pattern selbst, der Knotenkopf und Bindings übergeben. Ist das Pattern eine Variable, werden die Bindings erweitert. Sonst werden die Attribute des Patterns mit den Attributen des Knotens gematcht. Fehlt eins der Attribute oder kommt es zu einem Mismatch wie FAIL zurückgegeben, was signalisiert, dass das Matchen nicht funktioniert hat. Hat hingegen alles geklappt, werden die erweiterten Bindings zurückgegeben. Die HTML-NODE-MATCH zum Matchen von Knotenköpfen sieht so aus (man bemerke das ganz hässliche Loop, bei mir meistens das Ergebnis einer nicht gesäuberten wilden Hacksession):

(defun html-node-match (pat node bindings)
  (when (atom node)
    (setf node (list node)))

  (cond ((eq bindings fail)
	 fail)

	((variable-p pat)
	 (match-variable pat node bindings))

	(t (let* ((pat   (if (atom pat) (list pat) pat))
		  (pat-name   (car pat))
		  (node-name  (car node))
		  (pat-attrs  (cdr pat))
		  (node-attrs (cdr node))
		  (bindings   (if (variable-p pat-name)
				  (match-variable pat-name node-name bindings)
				  bindings)))
	     (if (or (variable-p pat-name)
		     (eql pat-name node-name))
		 (loop for (attr val) on pat-attrs by #'cddr
		       for node-val = (getf node-attrs attr)
		       do (cond ((variable-p val)
				 (setf bindings (match-variable val node-val bindings)))
				((not (string-equal val node-val))
				 (setf bindings fail)))
		       until (eq bindings fail)
		       finally (return bindings))
		 fail)))))

Angewendet sieht HTML-NODE-MATCH so aus:

CL-USER> (html-match::html-node-match :a
                                           '(:a :href "foobar")
                                           html-match::no-bindings)
((T . T))

CL-USER> (html-match::html-node-match '(:a :href ?href)
                                      '(:a :href "foobar")
                                      html-match::no-bindings)
((?HREF . "foobar"))

CL-USER> (html-match::html-node-match '(:a :href ?href :class "link")
                                      '(:a :href "foobar")
                                      html-match::no-bindings)
NIL

Matchen von Segmenten

Der nächste Schritt war jetzt das Anpassen des Matcherkerns. Bei einem bin ich mir allerdings nicht so sicher. Ich will durchaus zwischendurch eine Liste von Knoten matchen, die auf der selben Baumebene liegen. Dazu habe ich das spezielle Patternmuster +SEQ eingeführt, mit dem man “Segmente” matchen kann. Segmente matchen ist eigentlich nur das wiederholte Matchen von Knoten, die hintereinander liegen, und das durchreichen der Bindings dieser Matchergebnisse. Das wird durch die Funktion HTML-MATCH-SEGMENT gemacht. Im Gegensatz zu HTML-NODE-MATCH gibt HTML-MATCH-SEGMENT eine Liste von Bindinglisten zurück. Jedes der Bindinglisten ist das Ergebnissen eines gematchten Patterns. Hier die HTML-MATCH-SEGMENT Funktion:

(defun html-match-segment (patterns trees bindings)
  (cond ((null bindings)
	 nil)
	((null patterns)
	 (list bindings))
	((and (= (length patterns) 1)
	      (variable-p (first patterns)))
	 (list (match-variable (first patterns) trees bindings)))
	(t (let ((binds-list (html-match (car patterns)
					 (car trees) bindings)))
	     (when binds-list
	       (mapcan #'(lambda (binds)
			   (html-match-segment (cdr patterns)
					       (cdr trees) binds))
		       binds-list))))))

HTML-MATCH-SEGMENT bekommt eine Liste von Patterns und eine Liste von Knoten, gegen die die Patterns gematcht werden müssen. Besteht die Patternliste aus einem Variablenpattern, wird hier ein Greedymatch gemacht. Das finde ich jetzt überhaupt nicht sauber, mir ist aber auch nicht klar, wie man das schöner bauen könnte, ohne einen gänzlich ineffizienten Backtrackingmatcher zu bauen. Im anderen Fall wird das erste Pattern mit dem ersten Knoten gematcht, aus auch eine Liste von Bindinglisten zurückgibt. Für jedes dieser erfolgreichen Bindinglisten wird dann rekursiv der Rest der Liste abgearbeitet, indem HTML-MATCH-SEGMENT auf dem Rest der Patterns und dem Rest der Knoten aufgerufen wird.

Des Matchers Kern

So, nun aber zum eigentlich Kern des Matchers, der Teil, der ein Pattern mit einem Knoten vergleicht, und eine Liste von Bindinglisten zurückgibt. Hier gibt es mehrere Fälle:

• Der Pattern ist ein Ignore-Pattern, es werden einfach die jetzigen Bindings zurückgegeben.
• Der Pattern ist eine Variable, es werden die geupdateten Bindings zurückgegeben.
• Der Pattern ist ein Or-Pattern. In dem Fall besteht der Pattern aus mehreren möglichen Patterns. Sie werden nacheinander ausprobiert, und wenn der rekursive Matcheraufruf erfolgreich war, wird das Ergebnis in die Bindinglisten-liste aufgenommen. Ich muss zugeben, dass ich das bis jetzt noch nicht getestet habe, aber es “müsste” funktionnieren
• Der Pattern ist ein Segment-pattern. Ein Segment-pattern kann man nicht gegen einen einzelnen Knoten matchen, also wird der Pattern auf die Kinder des jetzigen Knotens gematcht. Und zwar auf den Kindern angefangen mit dem ersten, dann auf den Kindern angefangen mit dem zweiten, usw… Total hässlich, aber es scheint zu funktionnieren
• Der Pattern ist ein Multiple-pattern. Das war so eine Idee von mir, repetitive Patterns matchen zu können, ich weiss aber nicht so wirklich wie ich das angehen soll, deswegen ist das erstmal abgeschaltet.
• Der Pattern ist selber ein Knoten, und es wird der Knotenmatcher aufgerufen. Ist der Knotenmatcher erfolgreich, werden die Kinder des Patterns mit den Kindern des Knotens gematcht.

Hier der Code von HTML-MATCH:

(defun html-match (pattern tree &optional (bindings no-bindings))
  (cond ((eq bindings fail) nil)

	((ignore-p pattern) bindings)

	;; greedy
	((variable-p pattern)
	 (list (match-variable pattern tree bindings)))

	((and (stringp pattern)
	      (stringp tree)
	      (string-equal tree pattern))
	 (list bindings))

	((or-pattern-p pattern)
	 (mapcan #'(lambda (pat) (html-match pat tree bindings))
		 (cdr pattern)))

	((and (segment-pattern-p pattern)
	      (consp tree))
	 (reduce #'nconc
		 (loop for tree on (cdr tree)
		       for binds = (html-match-segment (cdr pattern) tree bindings)
		       when (not (eq binds fail))
		       collecting binds)))

	((and (multiple-pattern-p pattern)
	      (consp tree))
	 (error "multiple pattern not supported for now"))

	((and (consp pattern) (consp tree))
	 (let ((bindings (html-node-match (first pattern)
					  (first tree) bindings)))
	   (html-match-segment (cdr pattern) (cdr tree) bindings)))

	(t nil)))

Angewendet sieht der HTML Matcher so aus:

CL-USER> (html-match::html-match
      '((:a :href ?href) ?link)
      '((:a :href "blorg" :class "link") (:i "hahaha") "foobar") html-match::no-bindings)
(((?LINK (:I "hahaha") "foobar") (?HREF . "blorg")))

CL-USER> (html-match::html-match '(html-match:+seq (:p ?p1) (:p ?p2))
                                 '(:body
                                   (:p "paragraph1")
                                   (:p "paragraph2")
                                   (:p "paragraph3")
                                   (:p "paragraph4"))
                                 html-match::no-bindings)
(((?P2 "paragraph2") (?P1 "paragraph1"))
 ((?P2 "paragraph3") (?P1 "paragraph2"))
 ((?P2 "paragraph4") (?P1 "paragraph3")))

Man beachte hier übrigens das HTML-MATCH:+SEQ, damit +SEQ im richtigen Package ist. Da bin ich schon zweimal auf die Schnauze geflogen, und vielleicht sollte ich daraus eher ein Keyword machen, dann besteht das Problem nicht mehr.

HTML-Pattern Suche

Ganz brauchbar ist unser Matcher jedoch noch nicht, weil er nicht rekursiv nach einem Pattern innerhalb eines Baums sucht. Wenn wir z.B. ‘((:a :href ?href) ?link) auf unser Apache HTML-Dokument loslassen, wird er nicht finden, weil er :A nicht mit :!DOCTYPE matchen kann. Wir brauchen also noch einen Wrapper um den HTML Matcher, der rekursiv in einen Baum suchen wird. Das können wir gleich mit weiterer wichtiger Funktionalität verknüpfen. Wenn ein Pattern erfolgreich gematcht wurde, will ich meistens direkt ein Callback ausführen, um z.B. ein neues Objekt zu erzeugen, oder was auszudrucken. Meistens werde ich in diesem Callback auch auf die erfolgreich gematchten Bindings zurückgreifen wollen (sonst hätte ich keine Variablen in mein Pattern eingebaut). Deswegen habe ich ein Makro implementiert, mit ich bequem HTML-Patterns und ihre Callbacks niederschreiben kann. Das Makro heisst HTML-PATTERN, und angewandt sieht es wie folgt aus:

(HTML-PATTERN ((:A :HREF ?href) ?link)
          (format t "Matched the link with URL ~A and body ~S" ?href ?link))

=>

(LIST '((:A :HREF ?HREF) ?LINK)

      #'(LAMBDA (#:G12273)
          (FORMAT T "Matched the link with URL ~A and body ~S"
                  (HTML-MATCH::BINDING-VAL
                    (HTML-MATCH::GET-BINDING '?HREF #:G12273))
                  (HTML-MATCH::BINDING-VAL
                    (HTML-MATCH::GET-BINDING '?LINK #:G12273)))))

Aus dem Makro HTML-PATTERN wird also ein Liste erzeugt, die aus dem Pattern selbst, und einer Funktion, die als Argument eine Bindingliste annimmt. Der Body des Makroaufrufs wird transformiert, damit alle Symbole, die Variablen sind, in Auflösung der Bindings umgebaut werden. Um diese Transformation durchzuführen wird ein Code-walker verwendet, der dem Kern des Pattern-Matchers, und dem Kern des Javascriptcompilers gleich ist. Sobald er auf ein Symbol trifft, das eine Variable ist (also mit ? anfängt), wird das Symbol durch den Aufruf an GET-BINDING ersetzt. Trifft der Walker auf einen rekursiven Makroaufruf, darf er die neu gebundenen Variablen nicht mehr selber ersetzen, weil sonst das Scoping durcheinander Ein kleines Problem hat der Walker noch, er berücksichtigt QUOTE nicht, mit dem man Listen “as-is” angeben kann. Das heisst, das Variablensymbole auch gequotet ersetzt werden. Das war bis jetzt nicht wirklich dramatisch Hier also der Codewalker:

(defun pattern-vars (pattern)
  (cond ((variable-p pattern) (list pattern))
	((consp pattern)
	 (union (pattern-vars (car pattern))
		(pattern-vars (cdr pattern))))
	(t nil)))

(defun pattern-callback-walker (tree binding-var pattern-vars)
  (cond ((and (variable-p tree)
	      (member tree pattern-vars))
	 `(binding-val (get-binding ',tree ,binding-var)))
	((atom tree) tree)
	((eql (car tree) 'html-pattern)
	  `(html-pattern ,(cadr tree)
	    ,@(pattern-callback-walker (cddr tree) binding-var
				       (set-difference pattern-vars
						       (pattern-vars (cadr tree))))))
	(t (let ((a (pattern-callback-walker (car tree) binding-var pattern-vars))
		 (d (pattern-callback-walker (cdr tree) binding-var pattern-vars)))
	     (if (and (eql a (car tree))
		      (eql d (cdr tree)))
		 tree
		 (cons a d))))))

Die Funktion PATTERN-VARS extrahiert alle Variablen aus einem HTML-Matcher Pattern, damit beim rekursiven Makroaufruf die richtige Variablenliste ermittelt werden kann. Der Walker selber ist nur ein rekursiver Baumwalker. Mit dem Walker ist das Makro HTML-PATTERN kinderleicht zu implementieren:

(defmacro html-pattern (pattern &rest body)
  (let ((bindings (gensym))
	(vars (pattern-vars pattern)))
   `(list ',pattern
     #'(lambda (,bindings)
	 ,@(pattern-callback-walker body bindings vars)))))

Jetzt bleibt uns nur noch eine Funktion übrig, mit der rekursiv in einem HTML Dokument gesucht wird, bis das Pattern matcht. Wenn das Pattern gematcht wurde, werden die Bindings übernommen, und die Callback-Funktion aufgerufen. Die Funktion HTML-SEARCH nimmt ein HTML-Dokument und eine Liste von Patterns. Sei versucht der Reihe nach diese Patterns mit dem übergebenen Knoten zu matchen. Wenn das nicht klappt, ruft es sich rekursiv auf die Kinder des Knotens an. Damit werden dann all Möglichkeiten ausprobiert.

(defun html-search (input &rest html-patterns)
  (dolist (html-pattern html-patterns)
    (let* ((pattern (first html-pattern))
	   (callback (second html-pattern))
	   (bind-lists (html-match pattern input no-bindings)))
      (dolist (bindings bind-lists)
	(funcall callback bindings))))
  (when (consp input)
    (let ((*html-parent* input))
      (dolist (child (rest input))
        (apply #'html-search child html-patterns)))))

Angewandt sieht das dann so aus:

CL-USER> (html-match:html-search *html* (html-match:html-pattern ((:a :href ?href) ?link)
                                           (format t "Link ~S to ~S~%" (car ?link) ?href)))
Link "Apache web
server" to "http://www.apache.org/foundation/preFAQ.html"
Link "documentation" to "manual/"
NIL

So, und das wars für unsere heutige Lisp-Hackerei. Viel Spass beim Matchen, den Matcher-Code findet ihr im BKNR Subversion-Repository unter svn://bknr.net/trunk/bknr/src/html-match/.