Autonomes Säulenblog

Klatschbase 0.7 with Persistence and Generics Parameters

I did not really need persistence in Klatschbase, because I never restarted the Lisp image Klatschbase was running in since version 0.2. The only reason I used a different Lisp image in 0.2 than in 0.1 was due to the fact that I moved Klatschbase to another server. Being able to deploy a new version without stopping your application is really a nice feature of Common Lisp.

However, an unexpected reboot of my virtual root server made it clear, that persistence would be a nice thing to have. The machine was rebooted again a few days later. Hence, I decided to do it. It was on my list, anyway.

So I reevaluated the options. I keep on looking at CouchDB. There are two Common Lisp libraries for it. I also played on connecting to it with simple-http directly. This works good.

I also had a brief look at Elepahnt. There was not a lot to see the last time I checked it out, but now it seems to have some good documentation. It is definitely worth a shot if you have to persist something.

But in the end, I decided that my persistence needs are quite basic. I just want to store the clients and their options and the rooms that the server has. I ended up also storing the current messages in the system. Lisp already has a fairly simpl way to store such things: writing s-expressions with write and reading them with read.

I have to admit that the approach that I used does not scale to well, because the whole state is written every n seconds (or minutes). But this is OK in the given context. The plus side is that it gave me persistence with under 100 lines of code.

Another thing I fixed in this version are the parameter names of the generic functions. For some reason I always thought that the names of the generic function parameters must be the respective class. Which means I ended up with generic function definitions like these:

(defgeneric poll-msgs-wait (msg-store t t))

This, of course, is not the case. While in sbcl the above code compiles, other Common Lisp implementations choke on them. The following, more readable version, should work fine:

(defgeneric poll-msgs-wait (msg-store start-key timeout))

The Visitor Pattern in Differen Languages

In this post I want to explore the usage of the visitor pattern in different programming languages.

The goal is always to represent expression trees, i.e., to have the abstract syntax tree (AST) of an algebraic expression like 2 * 5 - 3.

Let us start with a simple implementation in Java:

import java.util.HashMap;
import java.util.Map;

public class ExpressionTree {
    
    public static interface Operator {
        int eval(int ... args);
    }
    
    public static Map<String, Operator> OPERATOR_MAP
    = new HashMap<String, Operator>();
    
    static {
        OPERATOR_MAP.put("+", new Operator() {
            public int eval(int ... args) {
                int result = 0;
                for (int i : args) {
                    result += i;
                }
                return result;
            }
        });
        OPERATOR_MAP.put("*", new Operator() {
            public int eval(int ... args) {
                int result = 1;
                for (int i : args) {
                    result *= i;
                }
                return result;
            }
        });
        OPERATOR_MAP.put("-", new Operator() {
            public int eval(int ... args) {
                if (args.length != 2) {
                    throw new IllegalArgumentException("wrong arity");
                }
                return args[0] - args[1];
            }
        });
        OPERATOR_MAP.put("/", new Operator() {
            public int eval(int ... args) {
                if (args.length != 2) {
                    throw new IllegalArgumentException("wrong arity");
                }
                return args[0] / args[1];
            }
        });
    }
    
    public static interface Visitor {
        void apply(Node node);
    }
    
    public static class Node {
        public void visit(Visitor visitor) {
            visitor.apply(this);
        }
    }
    
    public static class Literal extends Node {
        private int value;
        public Literal(int value) {
            this.value = value;
        }
        public int getValue() {
            return value;
        }
    }
    
    public static class Operation extends Node {
        private Node[] children;
        private String name;
        public Operation(Node[] children, String name) {
            this.children = children;
            this.name = name;
        }
        public String getName() {
            return name;
        }
        public Node[] getChildren() {
            return children;
        }
    }
    
    public static class EvalVisitor implements Visitor {
        private int value;
        public int evaluate(Node node) {
            apply(node);
            return this.value;
        }
        public void apply(Literal node) {
            value = node.getValue();
        }
        public void apply(Operation operation) {
            Node[] children = operation.getChildren();
            int[] values = new int[children.length];
            for (int i=0; i<children.length; i++) {
                EvalVisitor visitor = new EvalVisitor();
                children[i].visit(visitor);
                values[i] = visitor.getValue();
            }
            String name = operation.getName();
            Operator op = OPERATOR_MAP.get(name);
            if (op == null) {
                throw new RuntimeException("unknown operation " + name);
            }
            this.value = op.eval(values);
        }
        public void apply(Node node) {
            if (node instanceof Literal) {
                apply((Literal) node);
            }
            else if (node instanceof Operation) {
                apply((Operation) node);
            }
            else {
                throw new RuntimeException("unknown node instance");
            }
        }
        public int getValue() {
            return value;
        }
    }

    public static void main(String[] args) {
        System.out.println(
                new EvalVisitor().evaluate(
                        new Operation(new Node[] {
                                new Operation(new Node[] {
                                        new Literal(2),
                                        new Literal(5)},
                                        "*"),
                                new Literal(3)},
                                "-")));
    }

}

Two things can be observed here: 1) The base class Node has a method visit() which simply calls the visitor with itself as the argument. 2) The visitor uses instanceof to delegate to the according apply() methods. Hence, run time type information is used. Java’s OO system uses single dispatch. Multiple dispatch would make this delegation apply() method superfluous, as we shall see later.

Not all languages allow us to use run time type information and we can get rid of it by modifying the the Visitor interface as follows:

    public static interface Visitor<T> {
        T apply(Literal node);
        T apply(Operation node);
    }

This, however, forces us to make the visit() method in Node abstract and to implement it in Literal and Operation. The code is always exactly the same. Thus, we have the same method in every concrete subclass of Node instead of having it just once. The approach would be required in OCaml if you want to use objects. Another option would be to use algebraic data structures, which are very well supported in OCaml.

Let’s move on to a language that has multiple dispatch: Groovy.

def OPERATOR_MAP = [
    "+": { args ->

        int result = 0;
        for (int i : args) {
           result += i;
        }
        return result;
    },
    "*": { args ->
        int result = 1;
        for (int i : args) {
            result *= i;
        }
        return result;
    },
    "-": { args ->
        if (args.length != 2) {
            throw new IllegalArgumentException("wrong arity");
        }
        return args[0] - args[1];
    },
    "/": { args ->
        if (args.length != 2) {
            throw new IllegalArgumentException("wrong arity");
        }
        return args[0] / args[1];
    }]

public interface Visitor {
    void apply(Node node);
}

public class Node {
    public void visit(Visitor visitor) {
        visitor.apply(this);
    }
}

public class Literal extends Node {
    private int value;
    public Literal(int value) {
        this.value = value;
    }
    public int getValue() {
        return value;
    }
}

public class Operation extends Node {
    private def children;
    private String name;
    public Operation(def children, String name) {
        this.children = children;
        this.name = name;
    }
    public String getName() {
        return name;
    }
    public def getChildren() {
        return children;
    }
}

public class EvalVisitor implements Visitor {
    private int value;
    private def operatorMap;
    public EvalVisitor(def operatorMap) {
        this.operatorMap = operatorMap;
    }
    public int evaluate(Node node) {
        apply(node);
        return this.value;
    }
    public void apply(Literal node) {
        value = node.getValue();
    }
    public void apply(Operation operation) {
        Node[] children = operation.getChildren();
        int[] values = new int[children.length];
        for (int i=0; i<children.length; i++) {
            EvalVisitor visitor = new EvalVisitor(operatorMap);
            children[i].visit(visitor);
            values[i] = visitor.getValue();
        }
        String name = operation.getName();
        def op = operatorMap[name];
        if (op == null) {
            throw new RuntimeException("unknown operation " + name);
        }
        this.value = op(values);
    }
    public void apply(Node node) {
        throw new RuntimeException("unknown node instance");
    }
    public int getValue() {
        return value;
    }
}

println(new EvalVisitor(OPERATOR_MAP).evaluate(
    new Operation([
        new Operation([ new Literal(2), new Literal(5)], "*"),
        new Literal(3)],
        "-")));

The Java code was taken as the basis for the Groovy code, as one can clearly see. As mentioned before, the method apply() of the visitor that delegated.

The method visit() is not really needed, since we use run time type information, anyway. But let us first look at an implementation in Common Lisp.

(defpackage :expression-tree
  (:use :common-lisp))

(in-package :expression-tree)

(defparameter *operator-map*
  `((+ . ,#'+)
    (* . ,#'*)
    (- . ,#'-)
    (/ . ,#'/)))

(defclass visitor () ())

(defgeneric visitor-apply (visitor node))


(defclass node () ())

(defgeneric visit (node visitor))

(defmethod visit ((node node) (visitor visitor))
  (visitor-apply visitor node))


(defclass literal (node)
  ((value :reader literal-value :initarg :value)))

(defclass operation (node)
  ((name     :reader operation-name     :initarg :name)
   (children :reader operation-children :initarg :children)))


(defclass eval-visitor (visitor)
  ((value :accessor eval-visitor-value :initform 0)))

(defmethod visitor-apply ((visitor visitor) (node literal))
  (setf (eval-visitor-value visitor) (literal-value node)))

(defmethod visitor-apply ((visitor visitor) (node operation))
  (let ((operation (cdr (assoc (operation-name node) *operator-map*))))
    (when (null operation)
      (error "unknown operation ~A" (operation-name node)))
    (setf (eval-visitor-value visitor)
          (apply operation
                 (mapcar (lambda (child)
                           (let ((sub-visitor (make-instance 'eval-visitor)))
                             (visit child sub-visitor)
                             (eval-visitor-value sub-visitor)))
                         (operation-children node)))))

(defun expression-evaluate (node)
  (let ((visitor (make-instance 'eval-visitor)))
    (visit node visitor)
    (eval-visitor-value visitor)))

(expression-evaluate
 (make-instance 'operation :name '-
                :children
                (list
                 (make-instance 'operation
                                :name '*
                                :children
                                (list
                                 (make-instance 'literal :value 2)
                                 (make-instance 'literal :value 5)))
                 (make-instance 'literal :value 3))))

The same approach is used here with the visitor class and the visit method. The fact that visit really just calls visitor-apply with swapped arguments, makes it even more obvious that this method is not really needed in dynamic typed languages. So let us get rid of this extra step. And while we are at it, let us define a function sexp-to-ast that transforms an s-expression into a node graph.

(defpackage :expression-tree
  (:use :common-lisp))

(in-package :expression-tree)

(defparameter *operator-map*
  `((+ . ,#'+)
    (* . ,#'*)
    (- . ,#'-)
    (/ . ,#'/)))

(defclass visitor () ())

(defclass node () ())

(defgeneric visit (node visitor))

(defclass literal (node)
  ((value :reader literal-value :initarg :value)))

(defclass operation (node)
  ((name     :reader operation-name     :initarg :name)
   (children :reader operation-children :initarg :children)))


(defclass eval-visitor (visitor)
  ((value :accessor eval-visitor-value :initform 0)))

(defmethod visit ((node literal) (visitor eval-visitor))
  (setf (eval-visitor-value visitor) (literal-value node)))

(defmethod visit ((node operation) (visitor eval-visitor))
  (let ((operation (cdr (assoc (operation-name node) *operator-map*))))
    (when (null operation)
      (error "unknown operation ~A" (operation-name node)))
    (setf (eval-visitor-value visitor)
          (apply operation
                 (mapcar (lambda (child)
                           (let ((sub-visitor (make-instance 'eval-visitor)))
                             (visit child sub-visitor)
                             (eval-visitor-value sub-visitor)))
                         (operation-children node))))))

(defun expression-evaluate (node)
  (let ((visitor (make-instance 'eval-visitor)))
    (visit node visitor)))
    (eval-visitor-value visitor)))

(defclass eval-visitor (visitor) ())

(defmethod visit ((node literal) (visitor visitor))
  (literal-value node))

(defmethod visit ((node operation) (visitor visitor))
  (let ((operation (cdr (assoc (operation-name node) *operator-map*))))
    (when (null operation)
      (error "unknown operation ~A" (operation-name node)))
    (apply operation
           (mapcar (lambda (child)
                     (let ((sub-visitor (make-instance 'eval-visitor)))
                       (visit child sub-visitor)))
                   (operation-children node)))))



(defun sexp-to-ast (sexp)
  (if (listp sexp)
      (let ((children (mapcar #'sexp-to-ast (cdr sexp))))
        (make-instance 'operation :name (car sexp) :children children))
      (make-instance 'literal :value sexp)))

(expression-evaluate (sexp-to-ast '(- (* 2 5) 3)))

Visitors can have state. We exploited that fact, but let us redefine visit to return a value. This way we can get rid of the state and reuse our visitor.

(defpackage :expression-tree
  (:use :common-lisp))

(in-package :expression-tree)

(defparameter *operator-map*
  `((+ . ,#'+)
    (* . ,#'*)
    (- . ,#'-)
    (/ . ,#'/)))

(defclass node () ())

(defgeneric visit (node visitor))

(defclass literal (node)
  ((value :reader literal-value :initarg :value)))

(defclass operation (node)
  ((name     :reader operation-name     :initarg :name)
   (children :reader operation-children :initarg :children)))


(defclass eval-visitor () ())

(defmethod visit ((node literal) (visitor eval-visitor))
  (literal-value node))

(defmethod visit ((node operation) (visitor eval-visitor))
  (let ((operation (cdr (assoc (operation-name node) *operator-map*))))
    (when (null operation)
      (error "unknown operation ~A" (operation-name node)))
    (apply operation
           (mapcar (lambda (child) (visit child visitor))
                   (operation-children node)))))

(defun expression-evaluate (node)
  (let ((visitor (make-instance 'eval-visitor)))
    (visit node visitor)))


(defun sexp-to-ast (sexp)
  (if (listp sexp)
      (let ((children (mapcar #'sexp-to-ast (cdr sexp))))
        (make-instance 'operation :name (car sexp) :children children))
      (make-instance 'literal :value sexp)))

(expression-evaluate (sexp-to-ast '(- (* 2 5) 3)))

This, of course, can also be done in Groovy (and in Java). Here it is (with OPERATOR_MAP omitted):

public interface Visitor {
    Object apply(Node node);
}

public class Node {
}

public class Literal extends Node {
    private int value;
    public Literal(int value) {
        this.value = value;
    }
    public int getValue() {
        return value;
    }
}

public class Operation extends Node {
    private def children;
    private String name;
    public Operation(def children, String name) {
        this.children = children;
        this.name = name;
    }
    public String getName() {
        return name;
    }
    public def getChildren() {
        return children;
    }
}

public class EvalVisitor implements Visitor {
    private def operatorMap;
    public EvalVisitor(def operatorMap) {
        this.operatorMap = operatorMap;
    }
    public int apply(Literal node) {
        return node.getValue();
    }
    public int apply(Operation operation) {
        Node[] children = operation.getChildren();
        int[] values = new int[children.length];
        for (int i=0; i<children.length; i++) {
            values[i] = apply(children[i]);
        }
        String name = operation.getName();
        def op = operatorMap[name];
        if (op == null) {
            throw new RuntimeException("unknown operation " + name);
        }
        return op(values);
    }
    public Object apply(Node node) {
        throw new RuntimeException("unknown node instance");
    }
}


println(new EvalVisitor(OPERATOR_MAP).apply(
    new Operation([
        new Operation([ new Literal(2), new Literal(5)], "*"),
        new Literal(3)],
        "-")));

Here it is in Java (with OPERATOR_MAP omitted):

import java.util.HashMap;
import java.util.Map;

public class ExpressionTree {
    
    public static interface Operator {
        int eval(int ... args);
    }
    
    public static interface Visitor {
        void apply(Node node);
    }
    
    public static class Node {
        public void visit(Visitor visitor) {
            visitor.apply(this);
        }
    }
    
    public static class Literal extends Node {
        private int value;
        public Literal(int value) {
            this.value = value;
        }
        public int getValue() {
            return value;
        }
    }
    
    public static class Operation extends Node {
        private Node[] children;
        private String name;
        public Operation(Node[] children, String name) {
            this.children = children;
            this.name = name;
        }
        public String getName() {
            return name;
        }
        public Node[] getChildren() {
            return children;
        }
    }
    
    public static class EvalVisitor implements Visitor {
        private int value;
        public int evaluate(Node node) {
            apply(node);
            return this.value;
        }
        public void apply(Literal node) {
            value = node.getValue();
        }
        public void apply(Operation operation) {
            Node[] children = operation.getChildren();
            int[] values = new int[children.length];
            for (int i=0; i<children.length; i++) {
                EvalVisitor visitor = new EvalVisitor();
                children[i].visit(visitor);
                values[i] = visitor.getValue();
            }
            String name = operation.getName();
            Operator op = OPERATOR_MAP.get(name);
            if (op == null) {
                throw new RuntimeException("unknown operation " + name);
            }
            this.value = op.eval(values);
        }
        public void apply(Node node) {
            if (node instanceof Literal) {
                apply((Literal) node);
            }
            else if (node instanceof Operation) {
                apply((Operation) node);
            }
            else {
                throw new RuntimeException("unknown node instance");
            }
        }
        public int getValue() {
            return value;
        }
    }

    public static void main(String[] args) {
        System.out.println(
                new EvalVisitor().evaluate(
                        new Operation(new Node[] {
                                new Operation(new Node[] {
                                        new Literal(2),
                                        new Literal(5)},
                                        "*"),
                                new Literal(3)},
                                "-")));
    }

}

For the sake of completeness here is the mentioned variant in Java that does not use dynamic type features (with OPERATOR_MAP omitted):

import java.util.HashMap;
import java.util.Map;

public class ExpressionTree {
    
    public static interface Operator {
        int eval(int ... args);
    }
    
    public static interface Visitor<T> {
        T apply(Literal node);
        T apply(Operation node);
    }
    
    public static abstract class Node {
        public abstract Integer visit(Visitor<Integer> visitor);
    }
    
    public static class Literal extends Node {
        private int value;
        public Literal(int value) {
            this.value = value;
        }
        public int getValue() {
            return value;
        }
        public Integer visit(Visitor<Integer> visitor) {
            return visitor.apply(this);
        }
    }
    
    public static class Operation extends Node {
        private Node[] children;
        private String name;
        public Operation(Node[] children, String name) {
            this.children = children;
            this.name = name;
        }
        public String getName() {
            return name;
        }
        public Node[] getChildren() {
            return children;
        }
        public Integer visit(Visitor<Integer> visitor) {
            return visitor.apply(this);
        }
    }
    
    public static class EvalVisitor implements Visitor<Integer> {
        public Integer apply(Literal node) {
            return node.getValue();
        }
        public Integer apply(Operation operation) {
            Node[] children = operation.getChildren();
            int[] values = new int[children.length];
            for (int i=0; i<children.length; i++) {
                values[i] = children[i].visit(this);
            }
            String name = operation.getName();
            Operator op = OPERATOR_MAP.get(name);
            if (op == null) {
                throw new RuntimeException("unknown operation " + name);
            }
            return op.eval(values);
        }
    }

    public static void main(String[] args) {
        System.out.println(
                new EvalVisitor().apply(
                        new Operation(new Node[] {
                                new Operation(new Node[] {
                                        new Literal(2),
                                        new Literal(5)},
                                        "*"),
                                new Literal(3)},
                                "-")));
    }

}

So, what does all this tell us? Two things are obvious: 1) To get rid of the method visit() in the target object structure we need dynamic typing. 2) To get rid of the manual dispatching we need either multiple dispatch or we have to implement the visit() in every concrete sub-class of the target object structure (here all sub-classes of Node).

But there is still more to it. There is a subtle difference between the Groovy and the Common Lisp version. To emphasise this, in CL the visiting method is visit, but in Groovy it is apply. The method apply belongs to the visitor class. In CL a method does not belong to any class, but it is just a question of specialisation.

Klatschbase Improvements

I just had a chat with a friend using my chat software klatschbase. A few good ideas came up how to improve it. Since I yet have to set up trac, I simply blog about it.

1. Some people were irritated because they saw nothing dirtectly after sending a message. Hence, a special entry for direct feedback was introduced. But this also irritates some people, because in rooms they see their message twice. So this should probably be improved (e.g., by making it configurable by the user).
2. If the interval between message pulls is long, the user has to wait quite some time until they see their just send message. A simple workaround would be to trigger a pull when a message has been send successfully.
3. Messages should have hooks for citation and linking. While direct copying is no problem, linking yields a lot of questions. I’ll get to this later.
4. Different colors in the entries for different people that send the message would be very neat.
5. Timestamps for entries are missing.
6. The client still cannot create rooms (even though the protocol allows it).
7. It would be nice if clients could store options, e.g., the rooms they subscribed to.

I would really like to add some kind of persistence to chat rooms (and maybe also to the chat clients), meaning that the messages are stored somewhere. Right now, they are only kept in memory and only the last few are kept. The messages could be stored in CouchDB (or SimpleDB).

However, there are a lot of open questions. Should every chat room get its messages stored? Should they be visible from the outside world? Or should they only be visible from authorized users? It would probably be nice if this could be set per room, but who should be allowed to set this? Currently, rooms are not owned by anyone.

Regarding the storage of client options: They could either store it on the serverside (persistence on CouchDB?) or on the client side, using cookies. However, cookies have bad Karma.