PAIP in Clojure Challenge Chapter 3

August 22, 2016

The Chapter of Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp (PAIP) that dives into Common Lisp syntax.

Summary for Chapter 3: Overview of Lisp

The chapter starts with a quote by Guy L. Steele, Jr.:

No doubt about it. Common Lisp is a big language.

There is a lot to Common Lisp. In this chapter we will learn the subset of Lisp Norvig uses in his book.

There are six maxims every programmer should know about:

  • Be specific. (Use when instead of if if there is only one clause.)
  • Use abstractions. (Provide a first-name method when dealing with a list names, even if it is implemented as first.)
  • Be concise.
  • Use the provided tools.
  • Don't be obscure.
  • Be consistent. (Sometimes principles are in conflict with each other, then choose one and stick with it.)

Exercise 3.1 [m]

(let [x 6
      y (* x x)]
  (+ x y)) ; => 42

Show a lambda expression that is equivalent to the above let* expression. You may need more than one lambda.

((fn [x]
   ((fn [y] (+ x y))
    (* x x)))
 6) ; => 42

Exercise 3.2 [s]

The function cons can be seen as a special case of one of the other functions listed previously. Which one?

list*. See:

(= (list* 1 '(2 3 4)) 
   (cons 1 '(2 3 4))) ; => true

Exercise 3.3 [m]

Write a function that will print an expression in dotted pair notation. Use the built-in function princ to print each component of the expression.

Note: princ prints suitable output without escape characters and binds some values to special Common Lisp parameters. I use print.

Dotted pair notation is used in Lisps to show we are dealing with an improper list: a linked list where the second element of a cell is not a list. This is notated with a dotted pair. E.g., (cons 1 2) ; => '(1 . 2).

Clojure has no dotted pair notation since it avoids the linked list data structure and uses the abstraction of the sequence. See sequences:

A seq is a logical list, and unlike most Lisps where the list is represented by a concrete, 2-slot structure, Clojure uses the ISeq interface to allow many data structures to provide access to their elements as sequences.

For a list (special type of sequence) we can introduce dotted pair notation. To do so we need a method that can check for elements that have a single value (e.g., 1, :a). Elements which are therefore not a sequence.

I used the following method from an answer on Stack Overflow to check if a method is single-valued (or an atom in other Lisps than Clojure).

(defn single-valued?
  "Checks if value is single-valued."
  [x]
  (not (or (nil? x)
           (.. x getClass isArray)
           (some #(instance? % x) [clojure.lang.Counted
                                   clojure.lang.IPersistentCollection
                                   java.util.Collection
                                   java.util.Map]))))

Next we can create a case analysis and recursively generate a dotted-pair representation of a sequence.

(declare create-dotted-pair)
(defn create-dotted-pair-rest
  "Creates dotted pair string representation for the rest of a list."
  [lst]
  (str " . " (create-dotted-pair lst)))

(defn create-dotted-pair
  "Creates dotted-pair string representation of list."
  [lst]
  (cond (single-valued? lst) (str lst)
        (empty? lst) (str "'()")
        (seq? lst) (str "("
                        (create-dotted-pair (first lst))
                        (create-dotted-pair-rest (rest lst))
                        ")")
        :else (str lst)))

(defn print-dotted-pair
  "Prints dotted-pair string representation of list."
  [lst]
  (print (create-dotted-pair lst)))

This works as follows for a list created by a chain of cons cells, the shorter notation for a list, and for a nested list:

(print-dotted-pair (cons 1 (cons 2 (cons 3 (cons 4 '())))))
; => (1 . (2 . (3 . (4 . '()))))
(print-dotted-pair '(1 2 3 4))
; => (1 . (2 . (3 . (4 . '()))))
(print-dotted-pair '(1 2 (3 4)))
; => (1 . (2 . ((3 . (4 . '())) . '())))

Exercise 3.4 [m]

Write a function that, like the regular print function, will print an expression in dotted pair notation when necessary but will use normal list notation when possible.

Dotted pair notation is only necessary when the rest of a list is not a list. To implement this we have to make changes to the create-dotted-pair-rest method. Unfortunately it is impossible to create an improper list with native Clojure data structures.

(cons 2 3) ; => IllegalArgumentException (because 3 is not a sequence)

This makes it impossible to write a test without implementing a linked list data structure in Clojure (like Max Countryman did). Therefore I'll skip this exercise.

Now the first hard exercise:

Exercise 3.5 [h]

(Exercise in altering structure.) Write a program that will play the role of guesser in the game Twenty Questions. The user of the program will have in mind any type of thing. The program will ask questions of the user, which must be answered yes or no, or "it" when the program has guessed it. If the program runs out of guesses, it gives up and asks the user what "it" was. At first the program will not play well, but each time it plays, it will remember the user's replies and use them for subsequent guesses.

The idea seems to be that the program has a tree of questions and remembers the answer for each node.

To solve it we need state. For mutable state we create a map which we hold in an atom.

I use the following map to build a tree of questions and answers:

(def questions-and-answers
  "Questions and answers database atom.
  Keywords are used to traverse the tree.
  An answer needs to be non-existent (nil) or in the form of a string."
  (atom
   {:is_it_a_programming_language?
    {:yes
     {:is_it_statically_typed?
      {:yes
       nil
       :no
       nil}}
     :no
     {:ca_va?
      {:yes
       nil
       :no
       nil}}}}))

The program could be made more interesting if it was possible to add new questions and answers. This way the database of questions and answers can keep growing. For now, we just ask the questions and update if the user has an answer.

(defn get-remaining
  "Gets the remaining questions and answers from the questions-and-answers database.
  previous should be a vector of the previous questions and answers."
  [previous]
  (if (empty? previous) @questions-and-answers
      (get-in @questions-and-answers previous)))

(defn get-next-question
  "Gets the next question from questions-and-answers
  previous should be a vector of the previous questions and answers."
  [previous]
  (-> previous get-remaining ffirst))

(defn further-questions?
  "True if there is an answer for a question. False if not."
  [previous]
  (if (empty? previous) true
      (not (nil? (get-remaining previous)))))

(defn found-answer?
  "True if we have found the answer."
  [previous]
  (string? (get-remaining previous)))

(defn set-answer!
  "Sets the answer to the value provided.
  previous should be a vector of the previous questions and answers."
  [previous answer]
  (swap! questions-and-answers assoc-in previous answer))

(defn key->string
  "Create a string of the answer of question key."
  [key]
  (-> (name key) (clojure.string/replace "_" " ") clojure.string/capitalize))

(defn string->key
  "Create a key of the answer string."
  [answer]
  (-> answer (clojure.string/replace " " "_") clojure.string/lower-case keyword))

(defn driver-loop
  "Asks the questions, updates the answers.
  previous is vector containing the previous questions."
  ([] (driver-loop [])) ; Start with no previous provided answers.
  ([previous]
   (let [question (get-next-question previous)
         ask-it (println (key->string question)) ; ask-it is dummy variable to not create nested lets
         answer (read)
         print-answer (println answer) ; dummy, idem
         previous (conj previous question (string->key answer))]
     (cond (found-answer? previous)
           (let [found-answer (get-remaining previous)]
             (println (str "The answer is: " found-answer)))
           (not (further-questions? previous))
           (do (println "What was it?")
               (let [given-answer (str (read))]
                 (println given-answer)
                 (set-answer! previous given-answer)
                 (println "Thank you.")))
           :else (recur previous)))))

; (driver-loop)

Usage of the program looks like this:

Interacting with the program via the REPL.

The node in the tree is updated after an answer is given. The next time the same sequence of questions are answered the program responds with the answer the user added earlier. The representation is shown by dereferencing the atom.

Exercise 3.6 [h]

Given the following initialization for the lexical variable a and the special variable *b*, what will be the value of the 1st form?

Initialization is translated to Clojure:

(def a 'global-a)
(def ^:dynamic *b* 'global-b)
(def f (fn [] *b*))

(let [a   'local-a
      *b* 'local-b]
  (list a *b* (f) (var-get #'a) (var-get #'*b*)))

This returns `(local-a local-b global-b global-a global-b).

I hoped to see the dynamic scoping at work in (var-get) #'b so that the showed version was returned, this did not work like this.

Exercise 3.7 [s]

Why do you think the leftmost of two keys is the one that counts, rather than the rightmost?

Quicker search to argument list and easier to cons up new value to the beginning of a list (in Common Lisp). The latter is not the case in Clojure with its vector argument lists.

Exercise 3.8 [m]

Some versions of Kyoto Common Lisp (KCL) have a bug wherein they use the rightmost value when more than one keyword/value pair is specified for the same keyword. Change the definition of find-all so that it works in KCL.
(defn llast
  "Gets second to last value."
  [coll]
  (-> coll butlast last))

(defn get-value
  "Finds the value for a key from right to left. Returns value or nil if key not found."
  [key coll]
  (cond (< (count coll) 2) nil
        (= key (llast coll)) (last coll)
        :else (recur key (drop-last 2 coll))))

(defn find-all
  "Find all those elements of sequence that match item, according to the keywords.
  Doesn't alter sequence."
  [item coll & options]
  (let [test-fn (or (get-value :test-fn options) '=)
        key-fn (or (get-value :key-fn options) 'identity)
        result (remove #(not (test-fn % item)) coll)
        final-result (map key-fn result)]
    final-result))

(find-all 1 '(1 1 2 3 4 5 6) :test-fn = :key-fn inc :test-fn >) returns '(3 4 5 6 7). The rightmost key-fn: is used (>).

Exercise 3.9 [m]

Write a version of 1ength using the function reduce.
(defn length
  "Finds the length of coll using the function reduce."
  [coll]
  (reduce (fn [acc e] (inc acc)) coll))

Exercise 3.10 [m]

Use a reference manual or describe to figure out what the functions lcm and nreconc do.lcm finds the lowest common denominator and nreconc does some sort of reversing. The first is available in Clojure contrib library, the second is not available in Clojure.

Exercise 3.11 [m]

There is a built-in Common Lisp function that, given a key, a value, and an association list, returns a new association list that is extended to include the key/value pair. What is the name of this function?

Clojure's assoc does this:

(assoc {:other-key 'other-value} :key 'value) ; => {:other-key other-value, :key value}

Exercise 3.12 [m]

Write a single expression using format that will take a list of words and print them as a sentence, with the first word capitalized and a period after the last word. You will have to consult a reference to learn new format directives.

I think this cannot be done by format. It can for example be done via clojure.string methods:

(defn as-sentence
  "Takes a list of words and creates a sentence with first word capitalized and period at end."
  [word-list]
  (str (clojure.string/capitalize (clojure.string/join " " word-list)) "."))

That's it. In Chapter 4 we will built a General Problem Solver.

Discussion→

PAIP in Clojure Challenge Chapter 2

August 11, 2016

After some vacation and working on other things I finally got round to Chapter 2 of Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp (PAIP).

Summary for Chapter 2: A Simple Lisp Program

The chapter starts with a quote by the Italian royal historiographer Giovanni Battista Vico (1668-1744):

Certum quod factum.

For those that do not speak Latin, this is the rough translation: "One is certain only of what one builds."

In this chapter we build a more elaborate Lisp program and therefore live a more certain life. The program we will build generates random English sentences. In fancy terms we call the program generative syntax for a context-free phrase-structure grammar.

The original Common Lisp code from the book can be viewed here. First I translated this code to Clojure below.

(ns paip.simple
  (:gen-class))

; Clojure translation of the Common Lisp code in Chapter 2.
; Original: http://norvig.com/paip/simple.lisp

;;; Code translated from Paradigms of Artificial Intelligence Programming
;;; Copyright (c) 1991 Peter Norvig

(defn one-of
  "Pick one element of set, and make a list of it."
  [set]
  (-> set rand-nth list))

(def simple-grammar
  "A grammar for a trivial subset of English"
  {:sentence    [[:noun-phrase :verb-phrase]]
   :noun-phrase [[:article :noun]]
   :verb-phrase [[:verb :noun-phrase]]
   :article     #{"the" "a"}
   :noun        #{"man" "ball" "woman" "table"}
   :verb        #{"hit" "took" "saw" "liked"}})

(def bigger-grammar
  "A somewhat bigger grammar for a trivial subset of English"
  {:sentence    [[:noun-phrase :verb-phrase]]
   :noun-phrase [[:article :adj* :noun :pp*] [:name] [:pronoun]]
   :verb-phrase [[:verb :noun-phrase :pp*]]
   :pp*         [[] [:pp :pp*]]
   :adj*        [[] [:adj :adj*]]
   :pp          [[:prep :noun-phrase]]
   :prep        #{"to" "in" "by" "with" "on"}
   :adj         #{"big" "little" "blue" "green" "adiabatic"}
   :article     #{"the" "a"}
   :name        #{"Pat" "Kim" "Lee" "Terry" "Robin"}
   :noun        #{"man" "ball" "woman" "table"}
   :verb        #{"hit" "took" "saw" "liked"}
   :pronoun     #{"he" "she" "it" "these" "those" "that"}})

;;; ==============================

(def grammar
  "The grammar used by generate.  Initially, this is
  simple-grammar, but we can switch to other grammars."
  simple-grammar)

;;; ==============================

(defn rule-lhs
  "The left hand side of a rule."
  [rule]
  (->> rule keys (apply concat)))

(defn rule-rhs
  "The right hand side of a rule."
  [rule]
  (->> rule vals (apply concat)))

(defn rewrites
  "Return a list of the possible rewrites for this category."
  [category]
  (rule-rhs (select-keys grammar [category])))

;;; ==============================

(defn generate
  "Generate a random sentence or phrase"
  [phrase]
  (cond (vector? phrase)
        (mapcat generate phrase)
        (not (empty? (rewrites phrase)))
        (generate (rand-nth (rewrites phrase)))
        :else
        (list phrase)))

(generate :sentence)
; => (One example)
;    ("Kim" "saw" "Pat")

;;; ==============================

(defn generate-tree
  "Generate a random sentence or phrase,
  with a complete parse tree."
  [phrase]
  (cond (vector? phrase)
        (map generate-tree phrase)
        (not (empty? (rewrites phrase)))
        (cons phrase
              (generate-tree (rand-nth (rewrites phrase))))
        :else (list phrase)))

(generate-tree :sentence)
; => (one example)
;    (:sentence (:noun-phrase (:Article "the")
;                             (:Adj*)
;                             (:Noun "ball")
;                             (:PP*))
;               (:verb-phrase (:Verb "liked")
;                             (:noun-phrase
;                              (:Name "Robin"))
;                             (:PP*)))

;;;; ==============================

(defn combine-all
  "Return a list of lists formed by appending a y to an x.
  E.g., (combine-all '((a) (b)) '((1) (2)))
  -> ((A 1) (B 1) (A 2) (B 2))."
  [xlist ylist]
  (mapcat (fn [y]
            (map (fn [x] (concat x y)) xlist))
          ylist))

;; TODO: There is a bug in generate-all. For sentences that are constructed out of noun-phrase
;;       or verb-phrases the resulting sentences are displayed in characters.
(defn generate-all
  "Generate a list of all possible expansions of this phrase.
   Only works for non-recursive grammars."
  [phrase]
  (cond (vector? phrase)
        (combine-all (generate-all (first phrase))
                     (mapcat generate-all (rest phrase)))
        (not (empty? (rewrites phrase)))
        (mapcat generate-all (rewrites phrase))
        :else
        (list phrase)))

The translation between the different built-in methods and difference in behavior between Clojure and Common Lisp cost me quite some time, but it was worth it: I know more about Clojure than I did before, and I have a working sentence generator.

The lessons from the chapter are:

  • data-driven programming (where data drives what a program does next) makes it easy to extend functionality of a program just by adding new input data.In the parser above simple-grammar and bigger-grammar both work without having the program to change).
  • Code is also data, in what Norvig calls the one-data/multiple-program approach we can create slightly different versions of the same program which accomplish different tasks using the same data. generate-tree and generate-all programs are example of one-data/multiple-program: slight changes lead to different related functionality.

generate-all is not fully functional since somehow the words are cut down into characters when they are created by a verb-phrase or noun-phrase. Perhaps that problem will somehow be solved in the exercises.

Exercises

The source code with unit tests is available at https://www.github.com/erooijak/paip.

Exercise 2.1 [m]

Write a version of generate that uses cond but avoids calling rewrites twice.

Instead of checking it the rewrites are non-empty, in our way of defining the grammar (using the native Clojure map) we can perform the same check by checking if the phrase is a keyword:

(defn generate
  "Generate a random sentence or phrase"
  [phrase]
  (cond (vector? phrase) (mapcat generate phrase)
        (keyword? phrase) (generate (rand-nth (rewrites phrase)))
        :else (list phrase)))

Exercise 2.2 [m]

Write a version of generate that explicitly differentiates between terminal symbols (those with no rewrite rules) and non-terminal symbols.

Just extract a method and provide it with a meaningful name.

(defn non-terminal?
  "Determines if a phrase is non terminal."
  [phrase]
  (keyword? phrase))

(defn generate
  "Generate a random sentence or phrase"
  [phrase]
  (cond (vector? phrase) (mapcat generate phrase)
        (non-terminal? phrase) (generate (rand-nth (rewrites phrase)))
        :else (list phrase)))

Exercise 2.3 [m]

Write a trivial grammer for some other language. This can be a natural language other than English, or perhaps a subset of a computer language.

A subset of "Clojure":

(def simple-clj-grammar
  "A grammar for a trivial subset of Clojure"
  {:code                [[:definition-phrase :function-definition]]
   :definition-phrase   [[:definition :names :docstring]]
   :function-definition [[:library-definitions :parameter-types]]
   :definition          #{"defn"}
   :docstring           #{"wtf?" "TODO"}
   :names               #{"my-method" "awesome?" "change-it!"}
   :library-definitions #{"map" "mapcat" "inc" "dec"}
   :parameter-types     #{"string" "int" "long" "bool"}})

Exercise 2.4 [m]

One way of describing combine-all is that it calculates the cross-product of the function append on the argument lists. Write the higher-order function cross-product, and define combine-all in terms of it. The moral is to make your code as general as possible, because you never know what you may want to do with it next.

It is possible to write cross-product using a for-comprehension:

(defn cross-product
  "Calculates the cross product."
  [f coll1 coll2]
  (if (empty? coll1)
    '(())
    (for [x coll1
          y coll2]
      (f x y))))

(defn combine-all
  [xlist ylist]
  (cross-product concat xlist ylist))

The cross-product function in use:

(cross-product + '(1 2 3) '(10 20 30))
; => '(11 21 31
;      12 22 32
;      13 23 33)))

(cross-product list '(a b) '(1 2))
; => '((a 1) (a 2) (b 1) (b 2))))))

That was a full day of work. I will start with Chapter 3 tomorrow.

Discussion→

PAIP in Clojure Challenge Chapter 1

July 13, 2016

From my parents I received the book Paradigms of Artificial Intelligence Programming by Peter Norvig for my 28th birthday.

PAIP is a classic with high standard Common Lisp code to solve problems in artificial intelligence. My goal is to have read this book and finished a selection of the exercises in Clojure within a year.

There are 25 chapters and there are 52 weeks till 13 july 2017. This means I have to finish a chapter every two weeks.

The PAIP Clojure Challenge is reading PAIP and doing as much exercises as you can handle within a year.

Summary for Chapter 1: Introduction to Lisp

The chapter starts with a quote by Alan Perlis:

You think you know when you learn, are more sure
when you can write, even more when you can teach,
but certain when you can program.

The rest of the chapter explain the fundamentals of programming in Lisp and why it is awesome.

Exercises

I will do a selection of the exercises in this book. I assume that you as a reader have not read the book, so I'll explain the exercises if necessary. The source code with unit tests is available at https://www.github.com/erooijak/paip.

Exercise 1.1 [m]

Define a version of last-name that handles "Rex Morgan Md," "Morton Downey, Jr.," and whatever other cases you can think of.

In the book we had a function first-name to retrieve the first names from a list of names, where a name is a list of strings like ("Robert" "Downey" "Jr."). The first-name method first checked if the first element of the name existed in the parameter list *titles*. If it did first-name invoked itself recursively with the rest of the name.

We have to do the same, but instead of looking for the first element, we have to look for the last. And instead of validating the element does not exist in *titles*, we look in a parameter called suffixes.

(def suffixes '("Jr." "Md"))

(defn last-name
  "Select the last name from a name represented as a list."
  [name]
  (if (some #(= (last name) %) suffixes)
    (last-name (drop-last name))
    (last name)))

The library functions drop-last and last are convenient.

Exercise 1.2 [m]

Write a function to exponentiate, or raise a number to an integer power. For example: (power 3 2) = 32 = 9.

With the use of an iterative loop:

(defn power
  "Exponentiate a base to a power"
  [base power]
  (loop [b base 
         n power 
         result 1]
    (if (= 0 n)                   
      result                    
      (recur b (dec n) (* b result)))))

Exercise 1.3 [m]

Write a function that counts the number of atoms in an expression. For example: (count-atoms '(a (b) c)) = 3. Notice that there is something of an ambiguity in this: should (a nil c) count as three atoms, or as two, because it is equivalent to (a () c)?
(defn count-atoms
  "Counts the number of elements in an expression. nil is considered an atom.
   Clojure does not have true atoms, so better to call this method count-elements"
  [expression]
  (->> expression
       flatten
       count))

Exercise 1.4 [m]

Write a function that counts the number of times an expression occurs anywhere within another expression. Example: (count-anywhere 'a '(a ((a) b) a)) ; => 3.
(defn count-anywhere
  "Counts the number of times an expression occurs anywhere within another
   expression"
  [expression-to-search expression]
  (->> expression
       flatten
       (filter #{expression-to-search})
       count))

Exercise 1.5 [m]

Write a function to compute the dot product of two sequences of numbers, represented as lists. The dot product is computed by multiplying corresponding elements and then adding up the resulting products. Example:

(dot-product (10 20) '(3 4)) = 10 x 3 + 20 x 4 = 110`

(defn dot-product
  "Calculates the dot product. Assuming vectors are of even length and consist of numbers."
  [coll1 coll2]
  (if (empty? coll1) 0
    (+ (* (first coll1) (first coll2))
       (dot-product (rest coll1) (rest coll2)))))
Discussion→

How a Petri net can help you simplify your business logic

June 2, 2016

In enterprise organizations it is bound to occur that different teams are building similar software independently of each other. For example, multiple teams write code which interacts with various services and performs some business logic in a similar manner. The complexity of creating software is usually not in creating components which interacts with external software itself (e.g., connecting with a RESTful API via a service client class). The complexity resides in the means of combination of these various components. I.e. the modeling of the business process (the flow of work through an organization).

A Petri net is a mathematical modeling language which is particularly suited to model business processes. In the foreword of Modeling Business Processes: A Petri Net-Oriented Approach by Aalst & Stahl (2011) it is stated that:

Petri nets provide the foundation of the graphical notation and the basic primitives for modeling concurrency, communication, and synchronization. The extension of these basic primitives with data (color) ... makes it possible to model and analyze complex artifacts. (p. iv).

To facilitate flexibility in the face of changing requirements, to encapsulate the business rules in one central place, and to possibly tackle the problem of re-usability described above, a Petri net can be used to model a business process. Below I will show an example of using a Petri net using a domain specific language (DSL) which we have started creating at work. From this DSL which describes a business process an event-driven Petri net representation can be generated. All that is left of complex business logic in an application is the need to send the right events (with data) to the Petri net representation.

In this article I will elaborate on Petri nets, the DSL created and an event-driven Petri net representation.

Petri nets

In 1939 Carl Adam Petri was only 13 years old when he invented the Petri net with the goal of describing a chemical process. A Petri net is a directed bipartite graph consisting of places and transitions, where every place only connects with transitions and every transition only connects with places.

Below a visualization of a Petri net is provided. Transitions are visualized as rectangles and places as circles.

Petri net trajectory from Wikipedia
(Source: Wikipedia)

In the places tokens can exist (the dots that appear in the image above). Once all in-adjacent places towards a transition are filled, the transition can fire and consume the tokens, and thereby produce new tokens in the out-adjacent places out of the transition. Parallelism is supported (e.g., multiple places next to each other coming out of a transition or multiple places leading to one transition).

There are various extensions to the Petri net. A colored Petri net is a special type of Petri net where the tokens can also have data. A colored Petri net is particularly suited for modeling business processes.

Especially in Europe much research has been done on Petri nets and certain properties can be proven about them. It is possible to mathematically reason about reachability ("can we reach a certain state?"), liveness ("can a transition fire?") and boundedness ("how many tokens can there be?"). Reasoning about such properties is useful for example for:

  • Showing how much memory or disk space a process will consume.
  • Checking the validity of a business process.
  • Analyze bottle necks in the flow.

By using Petri Net Markup Language (PNML) to describe the Petri net analysis can be done via existing tools.

DSL

When a chef cooks a recipe she combines various ingredients. When certain events happen, or when ingredients are ready, a chef knows what action(s) to execute next. E.g., when a chef receives an event WaterBoiling she knows that she can start cooking the pasta. And once the chef has a knife and tomatoes she will start cutting them. If the chef is skilled, this results in pasta sauce when finished.

In the DSL below a similar recipe can be provided to a chef – only the chef is an execution engine written in Scala. Ingredients do not consist of edible substances but of software components. Actions to be executed are not certain kitchen skills, but instead methods on these software components. The preconditions for these actions are data or events that are provided.

The chef is all that is needed to handle flows through our business process.

Event-driven Petri net representation

In the current setup the recipe is represented as a Java map where the keys are the interfaces of the components and the values a representation of the actions. The representation of the action has properties to specify which methods are needed and which preconditions they have. These preconditions are specified as events or data.

Once the chef received the recipe it can start cooking a Petri net topology. The chef "cooks" by using reflection to get all the information out of the recipe and the ingredients. This topology is shared with various states of the Petri net (a state describes in what place which data/tokens are).

The chef can listen for events that are happening. Once it processes an event it knows to which Petri net state it belongs by looking at the process identifier, and it will perform the action specified in the recipe and update the state accordingly with the results.

The Petri net is modeled in-memory via the Kagera library which is maintained by one of my team members at work (who happens to be really enthusiastic about Petri nets). In the future it will be possible to store the state on disk using event sourcing – with the added benefit that all historical flows can be replayed and analyzed.

The chef has the following abilities:

  • It can be provided with real or stub implementations of the ingredients in its constructor.
  • It must be told what events are used.
  • It is possible to retrieve all state which belongs to a certain process.
  • It provides some more methods to get a GraphViz or PNML representation of the recipe for visualization and analysis purposes.

Below we see the interface of the chef:

class Chef(recipe: Map[Class[_], Seq[Action]],
           ingredientImpls: Map[Class[_], AnyRef],
           events: Set[Class[_]]) {

  /* Cook the recipe for a specific process id */
  def cook(processId: UUID): Unit = /* (...) */ 

  /* Get all accumulated state from the Petri net marking */
  def getAccumulatedState(processId: UUID): Map[String, Optional[Any]] = /* (...) */ 

  /* Tell the chef an event has happened for a specific process id */
  def tellEventHappened(processId: UUID, event: AnyRef): Unit = /* (...) */ 

  /* Get the GraphViz (graph visualization software) implementation of the recipe */
  def getVisualRecipe: String = /* (...) */ 

  /* Get the PNML (Petri Net Modelling Language) representation of the recipe */
  def getPnmlRecipe: String = /* (...) */ 
}

When getVisualRecipe is called the following GraphViz visualization of the recipe describing a simple cooking process is returned:

GraphViz visualization of recipe

Here events are modeled as blue diamonds, red circles represent data (places in Petri net terminology), and grey rectangles are the actions on the ingredients (transitions in Petri net terminology).

In the code of your application only the user-facing parts need to be created. Here the chef can be notified by events via the tellEventHappened method.

For example in a Java API, an instance of the Chef is provided in the classes providing API endpoints. This can look roughly as follows:

@Autowired
private JChef chef;

@POST
@Path("pastaSauce")
public Response waterBoiling(UUID processId, Sauce sauce) {
    chef.tellEventHappened(processId, new PastaSauceReady(sauce));

    return Response.ok().build();
}

Once the API is called on the pastaSauce resource there is no complex if-then-else business logic. The chef is just told whom it is that is calling our API, that it is the PastaSauceReady event that has happened and what sauce data was provided. All logic on what to do with this information is provided by the recipe and encapsulated in the chef.

Closing remarks

By using the modeling language of Petri nets and by creating a DSL it is possible to facilitate reuse, flexibility and encapsulation of complexity in the modeling of a business process. Changing the business logic has become as easy as changing the recipe. Business analysts can read or view the recipe and see if it adheres to their ideas. The chef should even be able to tell if it can cook a specific recipe. In theory, it is possible to share the ingredients and the chef with other teams and let them create new recipes reusing the components. And where in classically build APIs it can be difficult to trace where things went wrong, because of the properties of Petri nets it is possible to thoroughly analyze flows taken through the application.

If you want to read more:

Discussion→

Programming and meditation

May 17, 2016

Our minds jump from past memory to future fantasy and are extraordinarily out of control. Buddhism provides a technique which helps us to tame our wild minds: meditation.

Meditation is sitting down quietly and being aware of all that goes on, without comment. In meditation (Vipassana) the goal is to stay with reality as it is experienced in this very moment. It brings about a sense of calm insight.

I learned the technique of meditation at a 10-day retreat of dhamma.org. Last year I went to Thailand and I have lived 10 days in a similar manner as Buddhist monks and nuns at Wat Ram Poeng.

Blending in at the Vipassana meditation retreat at Wat Ram Poeng
Blending in at a meditation retreat at Wat Ram Poeng

This has led to me appreciate this wonderful technique for feeling at ease and dealing with the vicissitudes of life even more.

Where meditation helps me to stay grounded, programming, on the other hand, can be an activity which moves me away from everyday reality. As a programmer I work with abstractions.

As Fred Brooks writes in The Mythical Man-Month:

The programmer, like the poet, works only slightly removed from pure thought-stuff. He builds castles in the air, from air, creating by exertion of the imagination.

Meditation can not only provide a welcome counterweight to this work with abstractions, it also cultives 10 qualities of character (Pali: paramis) that are useful during the practice of programming.

Below I will list these 10 qualities and explain how they might benefit the programmer.

Dana – Generosity

Meditation teaches you to give freely without expecting anything in return. Won't be surprised when you start coding for others for the sheer joy of giving.

Sila – Morality

Meditation helps you to speak properly, perform good actions and have a right means of livelihood. Software engineering involves communication with others and is a way to sustain yourself. Cultivating the urgency to do or say the right thing will help you with this.

Nekkhamma – Renunciation

By renouncing the thoughts of for example sensual pleasures you become more adequate at dealing with that what is actually going on. When you code you code. Nothing else.

Panna – Wisdom/understanding

Meditation makes you realize on a fundamental level that everything is impermanent (Anicca) and that because we as human beings cling to and identify with (Anatta) this changing reality we suffer (Dukkha). One thing to learn from this is that you are not your code. This helps when receiving feedback.

Viriya - Effort

Mindfulness trains the mind to not procrastinate. It leads to prolonged periods of focus. Focus comes in handy during programming.

Khanti – Patience / tolerance

Meditation gives you the patience and tolerance to just fill in that Excel sheet for the next hour.

Sacca – Truthfulness

You will tell your boss the true state of affairs: the software will not be finished before the deadline.

Adhitthana – Strong determination

Just like the Buddha did not leave the tree till he was enlightened, you will not stand up from your chair till you have finished that piece of code.

Metta – Loving-kindness

Meditation teaches you to love what you do and the people you do it with. Enjoying what you do and cultivating good relationships with colleagues or friends helps with programming just as much as everything else.

Upekkha – Equanimity

Sitting through (enjoying even) hours of pain in your legs without responding to it has taught you to stay calm in the face of adversity. These 20 more use cases that you had initially overseen that will need to be implemented? No problem.

As a bonus, what I love of meditation is how aware you become of bodily sensations. For example: you notice earlier that your body is aching and that it is time to walk and stretch. It also helps with creativity. It's impressive how ideas start to flow when you watch your belly go up and down 30 minutes in the morning.

Interested? A good way to learn the technique of Vipassana meditation and experience its beneficial results is at a 10-day retreat at dhamma.org. Alternatively you can go to a country like Thailand and learn the technique at one of the meditation centers there.

Shameless plug:

No Nonsense Meditation Timer in Windows Phone Store

Discussion→