Arduino hello world

Using an Arduino board with a GNU/Linux personal computer has become pretty straightforward. The following command will install the required software:

sudo aptitude install arduino-mk

In order to get the file-system permissions to use the USB-serial it is necessary to add the current user to the dialout group. It is necessary to log out and back in after this.

usermod $USER -a -G dialout

For the Arduino Diecimila you then create a Makefile with the following content (see /usr/share/arduino/hardware/arduino/boards.txt for other supported boards).

ARDUINO_DIR = /usr/share/arduino
BOARD_TAG    = diecimila
ARDUINO_PORT = /dev/ttyUSB0
ARDUINO_LIBS =
include /usr/share/arduino/Arduino.mk

Make sure that /dev/ttyUSB0 is the right device! You can do this by inspecting the output of dmesg after plugging in the Arduino device.

Now you can create a sketch file (ino file extension) for programming the micro controller. E.g. a file Blink.ino with the following content:

int led = 13;

void setup() {
  pinMode(led, OUTPUT);
}

void loop() {
  digitalWrite(led, HIGH);
  delay(50);
  digitalWrite(led, LOW);
  delay(50);
}

Finally compile and upload the code:

make
make upload

The source is available on Github: github.com/wedesoft/arduino-hello-world

Update:

It is also possible to switch the LED according to instructions send over the USB serial channel. The following program facilitates this:

int led = 13;

void setup() {
  Serial.begin(9600);
  pinMode(led, OUTPUT);
}

void loop() {
  char c;
  if (Serial.available()) {
    c = Serial.read();
    if (c == '1') {
      digitalWrite(led, HIGH);
      Serial.write("LED on\r\n");
    } else if (c == '0') {
      digitalWrite(led, LOW);
      Serial.write("LED off\r\n");
    } else
      Serial.write("Switch LED on/off using keys '1' and '0'\r\n");
  };
}

After opening screen as a serial terminal, the LED can be controlled using keys '1' and '0':

screen /dev/ttyUSB0 9600

Exit with *Ctrl-A \*

See also:

Graph colouring

Currently I am looking into register allocation using graph colouring (also see Chaitin's paper on the subject). The graph colouring problem also occurs when trying to colour countries in a political world map where adjacent countries must have different colours. I thought it would be interesting to try a minimal implementation in Scheme. Feel free to suggest improvements in the comment section below .

A (undirected) graph is usually represented by a list of nodes (vertices) and a list of edges. If there are no insular nodes, a list of edges is sufficient. In Scheme (here GNU Guile implementation) one can do this as follows.

'((b . a) (a . c) (d . c))

The graph can be visualised on the command line using Graphviz and ImageMagick as follows.

echo 'graph test { b -- a; a -- c; d -- c; }' | dot -Tpng | display -

The following helper function graphviz uses a system call to display a graph from within the REPL.

(define (dot graph colors)
  (apply string-append
         (append (list "graph g {")
                 (map (lambda (color) (format #f " ~a [style=filled, fillcolor=~a];" (car color) (cdr color))) colors)
                 (map (lambda (edge) (format #f " ~a -- ~a;" (car edge) (cdr edge))) graph)
                 (list " }"))))
(define (graphviz graph colors) (system (format #f "echo '~a' | dot -Tpng | display -" (dot graph colors))))
(graphviz '((b . a) (a . c) (d . c)) '())

One can get the nodes of the graph by extracting all elements and suppressing any duplicates. The definition of delete-duplicates is part of SRFI-1 (Scheme Request for Implementation 1).

(use-modules (srfi srfi-1))
(define (nodes graph) (delete-duplicates (append (map car graph) (map cdr graph))))
(nodes '((b . a) (a . c) (d . c)))
; (b a d c)

The adjacency list of a node is simply the list of nodes of the sub-graph obtained by filtering for edges connecting to this node.

(use-modules (ice-9 curried-definitions))
(define ((has-node? node) edge) (or (eq? (car edge) node) (eq? (cdr edge) node)))
(define (adjacent graph node) (nodes (filter (has-node? node) graph)))
(adjacent '((b . a) (a . c) (d . c)) 'c)
; (a d c)

Chaitin's graph coloring algorithm works by successively removing nodes with a low adjacency count from the graph. Removing a node from our graph can be done as follows.

(define (remove-node graph node) (filter (compose not (has-node? node)) graph))
(remove-node '((b . a) (a . c) (d . c)) 'c)
; ((b . a))

Using the argument of the minimum one can determine the node with lowest adjacency count.

(define (argmin fun lst)
  (let* [(vals   (map fun lst))
         (minval (apply min vals))]
    (list-ref lst (- (length lst) (length (member minval vals))))))

Now one can recursively remove the node with lowest adjacency count and then assign colours starting with the last node and working backwards. If an adjacent node has a colour already, another colour must be used.

(use-modules (srfi srfi-26))
(define (assign-colors graph nodes colors)
  (if (null? nodes) '()
    (let* [(target    (argmin (compose length (cut adjacent graph <>)) nodes))
           (coloring  (assign-colors (remove-node graph target) (delete target nodes) colors))
           (blocked   (map (cut assq-ref coloring <>) (adjacent graph target)))
           (available (lset-difference eq? colors blocked))]
      (cons (cons target (car available)) coloring))))
(define (coloring graph colors) (assign-colors graph (nodes graph) colors))
(coloring '((b . a) (a . c) (d . c)) '(red green blue))
; ((b . red) (a . green) (d . green) (c . red))
(let [(graph '((b . a) (a . c) (d . c)))] (graphviz graph (coloring graph '(red green blue))))

And here is an example of coloring a graph with a few more nodes.

(let [(graph '((run . intr)
               (intr . runbl)
               (runbl . run)
               (run . kernel)
               (kernel . zombie)
               (kernel . sleep)
               (kernel . runmem)
               (sleep . swap)
               (swap . runswap)
               (runswap . new)
               (runswap . runmem)
               (new . runmem)
               (sleep . runmem)))]
  (graphviz graph (coloring graph '(red green blue yellow))))

OOP with GNU Guile and GOOPS

Having worked with the Ruby programming language for many years I started to get interested in Scheme. The Scheme programming language has a small and powerful core supporting closures, hygienic macros, first-class continuations, and of course the famous interpreter functions eval and apply.

How a Common Lisp programmer views users of other languages

However one thing I don't like about Scheme is that there are different function names for each type of arguments. E.g. adding numbers is done with +, adding lists is done with append, and adding strings is done with string-append.

(+ 2 3)
; 5
(append '(1) '(2 3))
; (1 2 3)
(string-append "a" "bc")
; "abc"

The same program would be much less verbose if + was extended to work with strings and lists, too:

(+ 2 3)
; 5
(+ '(1) '(2 3))
; (1 2 3)
(+ "a" "bc")
; "abc"

GOOPS: The Guile extension for object-oriented programming

GNU Guile It turns out that GNU Guile (the Scheme interpreter of the GNU project) has a mature extension which facilitates this. GOOPS is inspired by the Common Lisp Object System (CLOS). GOOPS not only provides polymorphic methods, it even lets you replace existing functions with polymorphic ones:

(use-modules (oop goops))
(define-method (+ (a <list>) (b <list>)) (append a b))
(define-method (+ (a <string>) (b <string>)) (string-append a b))
(+ 2 3)
; 5
(+ '(1) '(2 3))
; (1 2 3)
(+ "a" "bc")
; "abc"

The define-class method is the normal way to define a class. GOOPS requires you to define the instance attributes when defining the class. The following example defines a class <a> with attribute x and a + method. The make method is used to create the instance a of the class <a>.

(use-modules (oop goops))
(define-class <a> ()
  (x #:init-value 0 #:init-keyword #:x #:getter get-x))
(define-method (+ (u <a>) (v <a>))
  (make <a> #:x (+ (get-x u) (get-x v))))
<a>
; #<<class> <a> 2103c30>
(define a (make <a> #:x 123))
a
; #<<a> 22a2440>
(get-x a)
; 123
(+ a a)
; #<<a> 23713e0>
(get-x (+ a a))
; 246

Constructors and the next method

God uses Lisp

One can define a shorthand for instantiating objects. E.g. one can define a method which sets the attribute #:x to the argument multiplied by two.

(use-modules (oop goops))
(define-class <a> ()
  (x #:init-value 0 #:init-keyword #:x #:getter get-x))
(define (make-a x2) (make <a> #:x (* 2 x2)))
(define a2 (make-a 123))
; #<<a> 1689740>
(get-x a2)
; 246

IMHO it is better though to define a modified constructor directly. This is more involved but also possible.

(use-modules (oop goops) (ice-9 optargs))
(define-class <a> ()
  (x #:init-value 0 #:init-keyword #:x #:getter get-x))
(define-method (initialize (self <a>) initargs)
  (let-keywords initargs #f (x2)
    (next-method self (list #:x (* 2 x2)))))
(define a3 (make <a> #:x2 123))
(get-x a3)
; 246

Note the call to next-method. This essentially calls the next less specialized method for that generic function. Here is another example using an inheriting class <b> to illustrate the concept.

(use-modules (oop goops))
(define-class <a> ())
(define-class <b> (<a>))
(define-method (test (self <a>)) "a")
(define-method (test (self <b>)) (string-append (next-method) "b"))
(test (make <a>))
; "a"
(test (make <b>))
; "ab"

Metaclasses

Metaprogramming

Note that GOOPS does not implicitly create a metaclass. The following example shows how to define a metaclass <m<c>> with a class method.

(use-modules (oop goops))
(define-class <m<c>> (<class>))
(define-method (test <m<c>>) "m")
(define-class <c> ()
  (x #:init-keyword #:x #:getter get-x) #:metaclass <m<c>>)
(define o (make <c> #:x 5))
o
; #<<c> 2825d40>
(test (class-of o))
; "m"

Inspection

Inspection

One can also use GOOPS to change the way how objects get displayed and what the REPL writes to the terminal. E.g. one can define the method write for the class <a> to change the way the Guile REPL displays objects of that class.

(use-modules (oop goops))
(define-class <a> ()
  (x #:init-value 0 #:init-keyword #:x #:getter get-x))
(define a (make <a> #:x 5))
a
; #<<a> 2c64140>
(define-method (write (self <a>) port)
  (format port "(make <a> #:x ~a)" (get-x self)))
a
; (make <a> #:x 5)

Furthermore one can implement the method display to define the way objects get displayed in formatted output.

(define-method (display (self <a>) port)
  (format port "*~a*" (get-x self)))
(format #t "~a~&" a)
; *5*

Conclusion

I have now used GOOPS for a little while. Coming from Ruby there are a few gotchas when using GOOPS and Guile's module system. For example one needs to use a #:re-export statement when using a module to replace the core binding for the + operator.

All in all GOOPS makes quite a mature impression and I think it makes Scheme much more amenable to developers who are used to thinking in terms of objects and classes.

To quote Guile's foreign function interface documentation:

The more one hacks in Scheme, the more one realizes that there are actually two computational worlds: one which is warm and alive, that land of parentheses, and one cold and dead, the land of C and its ilk.

Any comments and suggestions are welcome

Further remarks

If necessary it is also possible to create objects, classes, and metaclasses dynamically. The following example instantiates the object v of class <v> of metaclass <m<v>>. Furthermore the generic test is implemented for <v>.

(use-modules (oop goops))
(define-generic test)
(define <m<v>> (make <class>
                     #:dsupers `(,<class>)
                     #:slots '()
                     #:name "<m<v>>"))
(define <v> (make <m<v>>
                  #:dsupers `(,<object>)
                  #:slots '()
                  #:name "<v>"))
(add-method! test (make <method>
                        #:specializers `(,<v>)
                        #:procedure (lambda (self) "v")))
(define v (make <v>))
v
; #<<v> 2d5a750>
(test v)
; "v"

Update:

I tweeted about the article and submitted it to Hackernews and the GUILE user list.

I have reduced the use of slot-ref during a discussion on the GUILE user list.

See also:

Implement an Interpreter using Bison, Flex, and Automake

This is a small example on how to implement an interpreter using Flex, Bison (formerly known as Yacc), and the Autotools. The example is based on Ben Reichard's course material.

Dependencies

First you need to install the C compiler, the lexer, and the LALR parser generator for this project. It also helps to install the readline wrapper utility.

sudo aptitude install build-essential bison flex rlwrap

Build system

You need to create the file Makefile.dist with the folowing content.

all:
    aclocal
    autoheader
    libtoolize --force
    automake -a --foreign
    autoconf

configure:
    ./configure

Then you create the file configure.ac with the following content.

AC_INIT(aclocal.m4)
AM_INIT_AUTOMAKE([calculator], [1.0.0])
AC_CONFIG_MACRO_DIR([m4])
AC_PROG_CC
AC_PROG_INSTALL
AC_PROG_LN_S
AC_PROG_YACC
AC_PROG_LEX
AM_PROG_LIBTOOL
AM_CONFIG_HEADER(config.h)
AC_CHECK_HEADERS([stdio.h])
AC_OUTPUT(Makefile)

Finally you create the file Makefile.am with the following content.

SUFFIXES = .c .h .y .l

ACLOCAL_AMFLAGS = -I m4

AM_YFLAGS = -d

bin_PROGRAMS = calculator

calculator_SOURCES = calculator.c calc_bison.y calc_flex.l
calculator_LDFLAGS = 
calculator_LDADD =

noinst_HEADERS = calculator.h

BUILT_SOURCES = calc_bison.h

EXTRA_DIST = Makefile.dist configure.ac

CLEANFILES = *~

MAINTAINERCLEANFILES = aclocal.m4 config.guess config.sub configure \
    install-sh ltmain.sh Makefile.in missing mkinstalldirs stamp-h.in \
    libtool config.cache config.h config.h.in acinclude.m4 depcomp \
    ylwrap

maintainer-clean-local:
    -rm -rf m4

This completes the setup of the build system.

Implementation

First create the file calc_bison.y with the implementation of the parser.

%{
#include <stdio.h>

void yyerror(char *s) {
  fprintf(stderr, "%s\n", s);
}

int sym[26];
%}

%union {
  int number;
  int var;
};

%type <number> expression
%token <var> VAR
%token <number> NUMBER

%%

start: expression '\n' { printf("%d\n\n", $1); } start
     | /* NULL */
     ;

expression: NUMBER
          | VAR                       { $$ = sym[$1]; }
          | '-' expression            { $$ = -$2; }
          | expression '+' expression { $$ = $1 + $3; }
          | expression '-' expression { $$ = $1 - $3; }
          | expression '*' expression { $$ = $1 * $3; }
          | '(' expression ')'        { $$ = $2; }
          | VAR '=' expression        { sym[$1] = $3; $$ = $3; }
          ;

Then create the file calc_flex.l with the implementation of the lexer (tokenizer).

%{
#include "calc_bison.h"
%}

%option noyywrap
%option always-interactive

%%

[0-9]+     { yylval.number = atoi(yytext); return NUMBER; }

[a-z]      { yylval.var = *yytext - 'a'; return VAR; }

[-+()*\n=] { return *yytext; }

[ \t]      ;

.          yyerror("Unknown character");

%%

Then create the header file calculator.h for the parser.

#ifndef CALCULATOR_H
#define CALCULATOR_H

int yyparse(void);
extern int sym[26];

#endif

Finally create the file calculator.c with the main program.

#include "calculator.h"

int main(void)
{
  int i;
  for (i=0; i<26; i++) sym[i] = 0;
  yyparse();
  return 0;
}

Compiling and running it

Above program is built using the following steps.

make -f Makefile.dist
./configure
make

You can run the calculator as follows.

./calculator

Alternatively you can run the interpreter with rlwrap to get command line history.

rlwrap ./calculator

Here is a sample session using the calculator program.

1
1

1 + 2
3

a = 1 + 2
3

b = a * 3
9

(1 + 2) * 3
9

(x = b) + 1
10

x
9

The code is also available on Github. You can get a copy using Git:

git clone https://github.com/wedesoft/calculator.git

Enjoy!

See also

Developing machine vision software with Ruby instead of C/C++

When I started doing a PhD in machine vision in 2004 I didn't know what I was in for. I thought I would learn about various object recognition algorithms, implement them in C++, and then try to come up with something new. I was motivated to implement 2D object recognition and tracking algorithms and I was hoping to eventually get into 3D object recognition/tracking and/or Visual SLAM (simultaneous localisation and mapping).

The trouble started when I started to realise how many representations of images there are. I am not even talking about colour spaces or compressed images/videos. It is already sufficient to just consider one-channel grey images. Virtually every C/C++ library for handling images comes with its own data structures for representing images. I.e. when trying to use more than one C/C++ library at a time, one ends up writing a lot of code for converting between different representation of images.

It get's worse. CPUs usually offer arithmetic using 8-bit, 16-bit, 32-bit, and 64-bit integers which can be signed or unsigned. Also there are single-precision and double-precision floating point numbers (i.e. 10 or more different native data types). When implementing a C/C++ library which just wants to support basic binary operations (addition, subtraction, division, multiplication, exponent, comparisons, ...) for array-scalar, scalar-array, and array-array combinations, one quickly ends up with literally thousands of possible combinations. This leads to a combinatorial explosion of methods as one can see in the Framewave library for example.

In the end I wrote a thesis about a different way of implementing machine vision systems. The thesis shows how one can implement machine vision software using a popular dynamically typed programming language (i.e. the Ruby programming language).

The listing below shows an IRB (Interactive Ruby) session to illustrate the result. Comment lines (preceded with '#') show the output of the IRB REPL (read-eval-print loop). The session first opens a video display showing the camera image. After closing the window it shows a video display with the thresholded camera image.

require 'rubygems'
require 'hornetseye_v4l2'
require 'hornetseye_xorg'
include Hornetseye
input = V4L2Input.new
# #<Hornetseye::V4L2Input:0x7fbad6151a38>
X11Display.show { input.read }
# Frame(YUY2)(640,480,0x3fdd6b1972a0)
X11Display.show { (input.read.to_ubyte >= 128).conditional 255, 0 }
# MultiArray(UBYTE,2):
# [ [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, .... ],
#   [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, .... ],
#   [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, .... ],
#   [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, .... ],
#   [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, .... ],
#   [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, .... ],
#   [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, .... ],
#   [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, .... ],
#   [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, .... ],
#   [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, .... ],
#   ....

See the picture below for an example of a thresholded image.

The example has just 7 lines of code. The REPL furthermore facilitates experimentation with machine vision software in an unprecedented way. The system achieves real-time by generating C-programs for the required operations, compiling them to Ruby extensions, and linking them on-the-fly.

I released the software as software libre under the name Hornetseye. My thesis is available for download now, too: Efficient Implementations of Machine Vision Algorithms using a Dynamically Typed Programming Language (Bibtex).

Here's the abstract:

Current machine vision systems (or at least their performance critical parts) are predominantly implemented using statically typed programming languages such as C, C++, or Java. Statically typed languages however are unsuitable for development and maintenance of large scale systems.

When choosing a programming language, dynamically typed languages are usually not considered due to their lack of support for high-performance array operations. This thesis presents efficient implementations of machine vision algorithms with the (dynamically typed) Ruby programming language. The Ruby programming language was used, because it has the best support for meta-programming among the currently popular programming languages. Although the Ruby programming language was used, the approach presented in this thesis could be applied to any programming language which has equal or stronger support for meta-programming (e.g. Racket (former PLT Scheme)).

A Ruby library for performing I/O and array operations was developed as part of this thesis. It is demonstrated how the library facilitates concise implementations of machine vision algorithms commonly used in industrial automation. That is, this thesis is about a different way of implementing machine vision systems. The work could be applied to prototype and in some cases implement machine vision systems in industrial automation and robotics.

The development of real-time machine vision software is facilitated as follows

  1. A just-in-time compiler is used to achieve real-time performance. It is demonstrated that the Ruby syntax is sufficient to integrate the just-in-time compiler transparently.
  2. Various I/O devices are integrated for seamless acquisition, display, and storage of video and audio data.

In combination these two developments preserve the expressiveness of the Ruby programming language while providing good run-time performance of the resulting implementation.

To validate this approach, the performance of different operations is compared with the performance of equivalent C/C++ programs.

I hope that my work has shown that the choice of programming language plays a fundamental role in the implementation of machine vision systems and that those choices should be revisited.

See also

  • HornetsEye: Ruby computer vision library (developed as part of this thesis)
  • OpenCV: C/C++ real-time computer vision library
  • NumPy: Python numerical arrays
  • NArray: Ruby numerical arrays
  • Lush: Lisp dialect for large-scale numerical and graphic applications
  • Halide: a language for image processing and computational photography
  • Maru: a symbolic expression evaluator that can compile its own implementation language

Update

The thesis is now also available on Figshare.com.