Rules Engine or Event Collaboration

Models of Computation

Some examples of models of computation include General Recursive Functions, Turing Machines, Lambda Calculus, Finite State Machines, and Production Systems. These are only some models of computation.

Martin Fowler has a pretty good post on rules engines (production system). “… providing an alternative computational model.”

Wikipedia’s definition is “A model of computation is the definition of the set of allowable operations used in computation and their respective costs.” I myself like the definition provided by “The Computational Beauty of Nature” [p27]. “… a model of computation describes how to build recipes or, if you like , a recipe for recipes.”

Both definitions seem to define two different things. The first definition describes programming languages. The second describes meta programming. These two definitions are not mutually exclusive. All programming languages have some form of meta programming. Just some languages have more powerful meta programming facilities.

In Common Lisp the most common way for the usage of meta programming is through the use of defmacro. Bill Clementson’s Blog post covers Joswig’s use of an embedded DSL in Lisp. Guess what allows him to make such a compact DSL? defmacro of course. Another nice Joswig post on comp.lang.lisp goes through an iterative cycle of design using defmacro.

Test Driven Development As an Introduction

I recommend Clarke Ching’s TDD Test Drive for an introduction for TDD.

It is pretty good.

Have Fun!

An Object in Lisp. Part 2

*****************************************************************************************************************

WARNING

DO NOT USE THIS EXAMPLE! THE MACROS DO NOT IMPLEMENT PARAMETERS PROPERLY. I WILL BE ADDING AN ADDENDUM TO SUPPLEMENT THIS POST WITH-IN THE WEEK

GUTZOFTER

11/21/2008

*****************************************************************************************************************

In Part 1, we described different implementations of objects in lisp. In this part we will delve into creating an abstraction so that we don’t have to deal with repetitive code.

Here is the abstraction I want for creating an object:

(defobj counter-obj
  (:members
    ((counter 0)))
  (:methods
    (:increment-counter (lambda () (incf counter))
      :get-counter (lambda ()counter))))

So the defobj will hold three items, a name, a list for the encapsulated variables, and a list for the methods that we want to create. I think this is pretty well cut and dry.
To create an instance all we will then need is this:

(defmacro defobj (name &rest class-data)
  (let ((members (getf (first class-data) :members))
        (methods (getf (second class-data) :methods)))
    `(defun ,(intern (concatenate 'string "MAKE-" (symbol-name name))) ()
       (let ,members
         (list ,@methods)))))

The first part of the macro extracts out the first list (members) and the second list (methods) and stores them into temporary variables.

The second part of the macro is the expansion. This expansion creates a function with the prefix of “make-” and the object name. (defun make-<name> …). The members are spliced into a let and the methods are spliced into the let. (See Part 1 make-counter3).

The macro-expansion generated from the macro is:

(DEFUN MAKE-COUNTER-OBJ ()
  (LET ((COUNTER 0))
    (LIST :INCREMENT-COUNTER
          (LAMBDA ()
            (INCF COUNTER))
          :GET-COUNTER
          (LAMBDA ()
            COUNTER))))

So far we have created a macro that creates the object for us, but we still are dependent on the implementation details of the object to access the behavior of the object:

(defparameter counter (make-counter-obj))
(funcall (getf counter :increment-counter))
(funcall (getf counter :increment-counter))
(funcall (getf counter :increment-counter))
(funcall (getf counter :get-counter))

The next step is to expand (pun intended!) on our defobj macro to abstract out those access functions. Here is how we want to access the counter-obj:

(defun increment-counter (obj)
  (funcall (getf obj :increment-counter)))
(defun get-counter counter ()
  (funcall (getf obj :get-counter))

So the total output of the macro will be:

(defun make-counter-obj ()
  (let ((counter 0))
    (list :increment-counter
          (lambda ()
            (incf counter))
          :get-counter
          (lambda ()
            counter))))

(defun increment-counter (obj)
  (funcall (getf obj :increment-counter)))

(defun get-counter (obj)
  (funcall (getf obj :get-counter))

Here are the macros:

(defmacro make-make-property (name members methods)
  `(defun ,(make-name name) ()
     (let ,members
       (list ,@methods))))

(defmacro make-property (name)
  `(defun ,(new-symbol (symbol-name name)) (obj)
    (funcall (getf obj ,name))))

(defmacro make-properties (property-names)
  `(progn
     ,@(loop for name in property-names collect `(make-property ,name))))

(defmacro defobj (name &rest class-data)
  (let ((members (getf (first class-data) :members))
        (methods (getf (second class-data) :methods)))
    `(progn
       (make-make-property ,name ,members ,methods)
       (make-properties ,(property-names methods)))))

There are some helper functions:

(defun group (source n)
  (if (zerop n)
      (error "zero length or source is nil"))
  (labels ((rec (source acc)
             (let ((rest (nthcdr n source)))
               (if (consp rest)
                   (rec rest (cons (subseq source 0 n) acc))
                   (nreverse (cons source acc))))))
    (if source (rec source nil) nil)))

(defun new-symbol (&rest args)
  "Concatenate symbols or strings to form an uninterned symbol"
  (intern (format nil "~{~a~}" args)))

(defun make-name (name)
  (new-symbol "MAKE-" (symbol-name name)))

(defun list-properties (property-list)
  (group property-list 2))

(defun property-names (properties)
  (let ((names))
    (dolist (property (list-properties properties))
      (push (first property) names))
    (nreverse names)))

Two of the functions I borrowed. “group” is taken from OnLisp and “new-symbol” is taken from Paradigms of AI Programming.

In evaluating this implementation of objects so far we see that we still have to do some typing beyond what we really want to do:

(defobj counter-obj
  (:members
    ((counter 0)))
  (:methods
    (:increment-counter (lambda () (incf counter))
      :get-counter (lambda ()counter)))

(test-fixture object-tests
    (:setup
      ((counter-obj (make-counter-obj))))

  (:tests
    (should-allways-make-object-be-true-with-implemented-functions
     (assert-true counter-obj)
     (assert-equal 0 (get-counter counter-obj))
     (assert-equal 1 (increment-counter counter-obj))
     (assert-equal 1 (get-counter counter-obj))
     (assert-equal 2 (increment-counter counter-obj))
     (unintern 'get-counter)
     (unintern 'increment-counter)
     (unintern 'make-counter-obj))))

Looking at the unit tests we see that in order to use an object we have to use “make-counter-obj” to generate the list and also store it into a refence variable ‘counter-obj’ now we have to enter ‘counter-obj’ as a parameter to our access functions. As a programmer I then need to remember that reference variable.

I’m thinking that maybe it might be better to do this:

(defobj counter
  (:members
    ((counter 0)))
  (:methods
    (:increment
      (lambda () (incf counter))
      :count
      (lambda ()counter))))

(test-fixture no-reference-to-object
    (:setup
      ((make-counter 'obj)))

  (:tests
    (should-use-obj-functions
     (assert-equal 0 (obj-count))
     (assert-equal 1 (obj-increment))
     (assert-equal 1 (obj-count))
     (assert-equal 2 (obj-increment)))))

Hmmm… til part 3

---

Syntax hi-lighting <tohtml.com>

An Object in Lisp. Part 1

I’ve had a long road to understanding Lisp and OOP. Closures are the key. Closures allow variables to be encapsulated.

(let ((counter 0))
  (defun inc-counter ()
    (incf counter)))

This code encapsulates a variable such that every time the function inc-counter is used it will increment the value stored in the variable counter. The function inc-counter would be considered global.

If we want to create individual instances of the counter incrementer we could then write something like this:

(defun make-counter ()
  (let ((counter 0))
    (lambda ()
      (incf counter))))

Now all we have to use the increment count is assign the object then make a funcall on it.

(setf count1 (make-counter))
(setf count2 (make-counter))

(funcall count1)
(funcall count1)
(funcall count1)

(funcall count2)

Count1’s counter variable will contain 3 and count2’s counter variable will have a value of 1.

Wohoo! Big deal you say. Well it is a big deal becuase now we can extend this concept to creating a more robust object. Right now this object only gives us state information when we incrementer the counter. This won’t do any good if we use it and then store it in a local variable everytime we invoke an increment. Why have encapsulation? We need to have some way to get access to state information without actually incrementing the counter.

Looking at make-counter we see that we returned a lambda expression. Let us expand on this idea of utilizing a lambda expression for incrementing a counter and also returning it’s state ref [1].

(defun make-counter1 ()
  (let ((counter 0))
    (lambda (cmd)
      (case cmd
        (:increment
          (incf counter))
        (:state
          counter)))))

A single lambda expression that takes a command as a parameter to access which function we want to execute.

(defparameter count3 (make-counter1))

(funcall count3 :increment)
(funcall count3 :increment)
(funcall count3 :increment)
(funcall count3 :state)

Now there is another way to do this (where in lisp is there not another way to do this?) ref[2].

(defun make-counter2 ()
  (let ((counter 0))
    (list (lambda()
            (incf counter))
          (lambda ()
            counter))))

A list of lambda expressions that we will need to access individual lambdas.

(defparameter count4 (make-counter2))

(funcall (first count4))
(funcall (first count4))
(funcall (first count4))
(funcall (second count4))

The source for code and data is the same. Code is comprised of s-expressions and data is comprised of s-expressions. This allows the lambdas to be stored in a list.

There is a third way to this. This will use a property list to get access to the lambdas.

(defun make-counter3 ()
  (let ((counter 0))
    (list
     :increment
     (lambda()
       (incf counter))
     :state
     (lambda ()
       counter))))

(defparameter count5 (make-counter3))
(funcall (getf count5 :increment))
(funcall (getf count5 :increment))
(funcall (getf count5 :increment))
(funcall (getf count5 :state))

So we have discussed several ways to implement an object. All four objects implement a mechanism to execute on closures. The underlying structure in which we implement the counter object would be a matter of taste!

The only problem with this type of object creation is it will be implementation specific , but also a lot of redundancy in coding.

In Part 2, we will get into this idea of using macros to create our own objects with minimal coding.

---

syntax highlighted by Code2HTML, v. 0.9.1