Rules Engine or Event Collaboration

January 9, 2009

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.

Read the rest of this entry »


Dog-fooding a Domain Specific Language (DSL); creating an extension to Lisp-Unit

July 20, 2008

The code for lisp-unit-fixture is in my link in the side panel.

The reasons for me wanting to use a dsl to run unit tests created with lisp-unit is because of duplication:

  1. Having to write (define-test …) for every test.
  2. having to use setup ‘let’s in every test.

An example is like this:

(define-test adder
(let ((zero 0)
(one 1))
(assert-equal 1 (adder zero one))))

(define-test subtractor
(let ((zero 0)
(one 1))
(assert-equal -1 (subtractor zero one))))

See the duplication?

What I wanted to do is remove the duplication. The is the language I came up with:

(test-fixture match-operations

(setup
((zero o) (one 1)))

(should-test

(adder
(assert-equal 1 (adder zero one)))

(subtractor
(assert-equal -1 (subtractor zero one)))))

Much more encapsulated and it removes the duplications.

A. Initial Steps

The way I did this was to use macros. Since I’ve just started using Lisp I thought it would be best If I took baby steps.

All the authoritative authors ;) recommend starting with the macro signature and then coming up with the expanded form:

(create-test
((zero 0)(one 1))
(math-operation-adder
(assert-equal 1 (adder zero one))))

This is the expanded form and this is the macro:

(defmacro create-test (setup test)
(let ((test-name (first test))
(test-code (rest test)))
`(define-test ,test-name
(let (,@setup)
,@test-code))))

This macro will extract test-name and test-code form from the test. The backqoute generates the define test and splices in the rest of the variable; test-name, setup and test code. The expanded code is this:

(define-test adder
(let ((zero 0)
(one 1))
(assert-equal 1 (adder zero one))))

B. Handling multiple tests

Language:

(create-tests
(setup ((true t) (false nil)))
(should
(test-b (assert-true true) (assert-false false))
(test-c (assert-true true) (assert-false false))))

Macro:

(defmacro create-tests (setup test-list)
(let ((test-collection (loop for i in (rest test-list)
collect `(create-test ,@(rest setup) ,i))))
`(values-list (list ,@test-collection))))

Expanded form:

(VALUES-LIST
(LIST
(CREATE-TEST ((TRUE T) (FALSE NIL))
(TEST-B (ASSERT-TRUE TRUE) (ASSERT-FALSE FALSE)))
(CREATE-TEST ((TRUE T) (FALSE NIL))
(TEST-C (ASSERT-TRUE TRUE) (ASSERT-FALSE FALSE)))))

Viola` multiple tests. Real simple huh? Well let me tell you this wasn’t so easy. Trying to get the loop to work right was crazy. I tried ‘do and ‘dolist. Nothing I did seem to work. I needed to unwrap each test from the collection. Cargo Cult to the rescue. I accidentally hit upon the idea of unwinding the collection with a value-list. i was still getting problems so I remember reading somewhere about splicing and then putting the splice in a list within the backquote. Woo Hoo! it worked. This area needs some research on my part.

Now on to…

C. Final Macro

Language:

(test-fixture run-two-test
(setup ((true t) (false nil)))
(should
(test-d (assert-true true) (assert-false false))
(test-e (assert-true true) (assert-false false))))

Macro:

(defmacro test-fixture (name setup &body body)
(setf name nil)
(if (not body)
`(create-tests ,(create-default-setup (gensym)) ,setup)
`(create-tests ,setup ,@body)))

Expanded form:

(CREATE-TESTS (SETUP ((TRUE T) (FALSE NIL)))
(SHOULD (TEST-D (ASSERT-TRUE TRUE) (ASSERT-FALSE FALSE))
(TEST-E (ASSERT-TRUE TRUE) (ASSERT-FALSE FALSE))))

Alternate language:

(test-fixture run-two-test-no-setup
(should
(test-h (assert-true t) (assert-false nil))
(test-i (assert-true t) (assert-false nil))))

Alternate expanded form:

(CREATE-TESTS (LISP-UNIT-FIXTURE::SETUP ((#:G1764 0)))
(SHOULD (TEST-H (ASSERT-TRUE T) (ASSERT-FALSE NIL))
(TEST-I (ASSERT-TRUE T) (ASSERT-FALSE NIL))))

Before we get started on some analysis, notice on the alternate expanded form you will see that setup is interned in lisp-unit-fixture package [NOTE: personally warned about this in private correspondence]. The alternate language doesn’t need to include setup code for inserting into each individual tests, but the macro will include the default. If a setup is not included in the test-fixture, that means the tests will be inserted into the setup variable.

Originally while writing this macro I used (if (equal ‘setup (first setup))) to find out if setup was in the test-fixture code. My original tests were also in the same package. The all would pass. I then used the test-fixture in some new code. Some of my new tests failed. 2 hours later I finally tracked it down. I moved my tests into it’s own package and then changed the implementation of the macro test-fixture.

Some references for this are here:

[ The Common Lisp Cookbook – Macros and Backquote ]

[ comp.lang.lisp ]

If you look at the code you will see that setup and should are just syntactic sugar placeholders. you can replace these markers with anything you want. Here is an example:

(test-fixture match-operations
(setup-for-all-tests ((zero o) (one 1)))
(should-test
(adder (assert-equal 1 (
adder zero one)))
(subtractor (assert-equal -1 (
subtractor zero one)))))

D. Design decisions

One of the major problems that doesn’t sit well with me is the redundant let if no setup is included. But it works for now.