Meta-Circular Adventures in Functional Abstraction – Challenging Clojure in Common Lisp

TABLE OF CONTENTS
Day 1 – Motivation
Day 2 – The Essence of Functional Programming
Day 3 – Setup
Day 4 – A Programmable Programming Language
Day 5 – Putting it All Together
Day 6 – Actor Model
Day 7 – Taking It All For a Spin
Conclusion
Improvements – Setting the Stage for More
Epilogue – Algebraic Sum Types
Postscript – Exhaustive Pattern Matching
Abacus – A Unified Syntax for Pattern Matching
References
Reader Comments

 

Go to Top

Day 1 – Motivation

 

Clojure is a dialect of the Lisp programming language created by Rich Hickey [Clojure]. According to Wikipedia, Mr. Hickey created Clojure “because he wanted a modern Lisp for functional programming, symbiotic with the established Java platform, and designed for concurrency.[Clojure]. Since then, Clojure has gathered somewhat of a following in the functional programming community, the other chief contender for functional programming on the JVM being the Scala programming language. This blog will attempt to document my quest to achieve two of Mr. Hickey’s goals using straight-up Common Lisp: idiomatic functional programming & concurrency. Why am I doing this? I tried Clojure and was disheartened by two aspects of the language: lackluster performance and the constant resurfacing of the Java and the JVM in error messages and other aspects of working with Clojure. I know of ClojureScript and the ability to run it on Google V8, but I suppose I really wanted a non-hosted language where I can intuitively map abstractions to assembler code by calling something like (disassemble … ) on a simple function. I tried Scala and missed homoiconic macros. Somehow I could not shake the feeling that homoiconic macros were intimately tied to the very essence of functional programming. I was also puzzled by the suggestion that Lisp, in its current form, somehow lacked modernity. Popularity, yes, modernity I wasn’t sure of… We will add one twist to the story. With Lisp being a programmable programming language, I can surely re-engineer any design goals of Clojure using Common Lisp by way of macros — but the challenge here is to do without such an effort. Therefore there are two rules in this game: 1) I am not allowed to write the keyword “defmacro” 2) I must rely on stock libraries / frameworks. “Stock” will be defined as installable via Common Lisp’s package manager Quicklisp [QuickLisp]. The “long and short of it is” that I want the utility of Clojure with the performance of Common Lisp. As Dough Hoyte points out in the book Let Over Lambda [Let-Over-Lambda], Lisp is not precisely a functional programming language, not in the the sense that Haskell and ML are functional programming language. I aim to challenge that. In http://chriskohlhepp.wordpress.com/convergence-of-modern-cplusplus-and-lisp/ [Lisp-Converge-C++] we showed how to bring Lisp close to C in performance by matching the generated Assembler code.  In this blog we aim to “bring Lisp in line” with idiomatic functional programming concepts. With our two rules in mind, let us see how far we can travel on this road…

The Birthday Cake Recipe

See also http://chriskohlhepp.wordpress.com/functional-programming/functional-programming-concepts/ We will start with the functional birthday cake recipe.

Functional Birthday Cake

Functional Birthday Cake

  • Let  batter = 400g flour + 2 eggs + 200ml milk
  • Let dough =  knead batter for 10 minutes
  • Let cake = bake dough for 30 minutes at 180o
  • Let iced_cake = cake + sugar coating
  • Let birthday_cake = iced_cake + candles

The emergent behaviour of this solution is transparent! Now contrast an imperative, object-oriented recipe.

  • BakingForm container
  • Container.Add (400g flour)
  • Container.Add(2 eggs)
  • Container.Add(200 ml milk)
  • Container.Knead(10 minutes)
  • Container.Bake(30 minutes,180o)
  • Container.AddCoatingToContents(sugar)
  • Container.Add(Candles)

Questions :

  • When does the dough emerge ?
  • When does the cake emerge ?
  • Does a cake emerge ?

The emergent behaviour of the imperative solution is entirely opaque! We will use the idea of the functional birthday cake for our little game. Before we embark on this game, let us first embark on a detour.


Go to Top

Day 2 – The Essence of Functional Programming

The essence of functional programming, in broadest terms, may be said to be in functions as first class citizens — a rather vague definition by any standard. The Wikipedia article on functional programming is quite lengthy and there is little point in repeating it. A few points are worth repeating.

  1. Functional programming aims for compositionality. By this we mean mathematical composition along the lines of f (g(x)).  Object orientation falls short here in that it does readily permit mathematical composition. Function composition is one reason for the brevity of functional programs. But there is another reason:
  2. First class functions [first-class] enable higher order functions [higher-order]. Higher order functions have an interesting impact on the powers of abstraction offered by a programming language.

Traditionally, code in a computer program is viewed separately from the data on which it operates. Wikipedia states that “A computer program in execution is normally treated as being different from the data the program operates on.”  The same article states that “A computer program is a sequence of instructions” and thatA collection of computer programs and related data is referred to as the software[computer-program]So a computer program may be said to be a sequence of instructions (code) operating on data.  In functional programming, the unit of sequences of instructions (code) is the function. What does it mean then if a higher order function, takes functions as arguments and returns functions as values? Strictly speaking it means we have diverged from the separation of code and data. We have created a paradigm in which function (sequences of code ) computes not only data but computes other function (sequences of code). Here lies the true power of abstraction in functional programming languages: higher order functions are in essence meta-circular.  Code that computes code is the basis of the power of abstraction of Lisp. In that respect higher order functions and Lisp macros are two sides of the same coin. Wikipedia states that “macros can also be used to achieve some of the effects of higher order functions. “ [higher-order]  Where the unit of organization in functional programming is the function, the unit of organization in Lisp macro programming is simply “the form.” The two approaches are different in many ways, treatment of types being one, but the commonality is that both permit creating abstraction by computing function. Here lies the source of the power of abstraction and brevity of both functional programming and Lisp. The functions as first class citizens concept also paves the road to an algorithm first approach. See http://chriskohlhepp.wordpress.com/convergence-of-modern-cplusplus-and-lisp/. There are other aspects of functional programming, such as the emphasis on representing function as expressions rather than imperative procedures and the emphasis on side effect freedom — these have an impact on the ability to write scalable concurrent applications. Other aspects of modern functional programming include type inference, algebraic data types and associated pattern matching. [ADT]  These concepts are central to OCaml and Haskell. The algebraic type aspect emerged within functional programming rather than being the basis of it. Yet it is increasingly seen as an integral part of functional programming because of the benefits it bestows. Equally, the models of concurrency that have emerged in functional programming are increasingly seen as “core” aspects — one such model is the Actor Model popularized by Erlang and adopted by Scala. Clojure similarly adopted software transactional memory. It is these aspects of modern functional programming that are seen as having been left behind in Common Lisp and which we will attempt to bring together in a coherent fashion — much the same as Rich Hickey has done for Clojure on the JVM. Functional programming exhibits a predisposition towards recursion over  iteration. This allows representing many problems without intermediate state. But what happens to that state ?  Let us examine the OCaml implementation of the factorial algorithm.

OCaml Factorial

OCaml Factorial

The factorial function is composed entirely of expressions free of intermediate state. All state resides on the stack. The important point is that stacks can be separately reasoned about and proven correct in their own right.  Thus state is managed separately from the algorithm. A function implementing an algorithm in this manner is said to be pure. This in turn leads to provably correct software. This is another core aspect of functional programming. Haskell achieves this via monads which are another vehicle to manage state in isolation. This point is worth repeating. State exists, but it is managed separately from algorithm. Monads and stacks are not  the only vehicles that enable this separate treatment of algorithm and state. A third vehicle is Functional Reactive Programming or FRP. [FRP]

Target Features

The list of target features is somewhat subjective in that features were chosen for the sake of the benefit they purport to bestow. Since we will aim to create something concrete, we will want to chose a sensible combination of features. There is the temptation to cram in every feature one may think of, but this make for an awkward setup. So what follows is necessarily a limited feature set.

  • FRP – to separate algorithm from state
  • Actor Model – for scalable, message passing based concurrency
  • Pattern Matching – for its expressiveness and promotion of correct code

There are other features which are desirable but we won’t be including them in our example project. Rather we will defer to the relevant QuickLisp project as reference implementation. These include:

  • Immutable Collections
  • Algebraic Types & Exhaustive Pattern Matching
  • Communicating Sequential Processes

 


Go to Top

Day 3 – Setup

We will be using the following platform:

  • Steel Bank Common Lisp 1.1.16.
  • ASDF 3.0.2
  • QuickLisp 2014-01-30

If you are not familiar with these, ASDF is a Common Lisp “Systems Definition Facility.” It may be thought of as a package manager for your local installation of Lisp.  QuickLisp is a repository that makes packages available to your local ASDF. Installing an using QuickLisp is easy. Simply follow the instructions at http://www.quicklisp.org/beta/#installation. At the time of writing there are some 900 libraries and frameworks. Loading a new library or framework is achieved thusly. If, for example, you wanted to install the latest JSON library, you would issue the ql:quickload command.

QuickLisp Load Package

QuickLisp Load Package

cl-json will subsequently be available for use. As with any set of libraries and frameworks, these will be in varying states of development, some more or less mature or more or less maintained than other. It therefore pays to consult the Common Lisp Wiki “Current Recommended Libraries” page at http://www.cliki.net/Current+recommended%20libraries.  At any point in time this will have suggestions for currently recommended packages according to the relevant domain. For example, we have identified pattern matching as a point of interest. The Common Lisp Wiki catalogs no less than 21 packages for pattern matching at http://www.cliki.net/pattern%20matching.  In general, the Common Lisp Wiki is an excellent information repository. [CL-WIKI]


Go to Top

Day 4 – A Programmable Programming Language

When I started on this experiment, I was truly skeptical. I know that language designers slave over the composition of features in a programming language. Each trade-off must be carefully balanced. One mistake has the potential of locking out a whole class of features some time in the future as users demand backwards compatibility for their code base. Wrong design choices cannot simply be backtracked, patched and fixed in release version n+1. This, more than anything is probably the reason for the development of new programming languages. Some survive, like C++. But as they absorb more features and even new paradigms, they become increasingly awkward. See also http://chriskohlhepp.wordpress.com/convergence-of-modern-cplusplus-and-lisp/.  So my suspicion was that, yes, I would be able to use each of the libraries and packages from QuickLisp and it looked as though the feature areas I sought to address had ample coverage, but I also suspected I would not be able to blend them into a coherent functioning whole. I was wrong. I underestimated how malleable Lisp is.

.sbclrc

The configuration file .sbclrc in your $HOME folder can be used to run Lisp at startup of Steel Bank Common Lisp. Since Lisp is configured, programmed and re-programmed in Lisp, we will use .sbclrc to customize our Lisp image.  My personal .sbclrc is shown below. Hint: Scroll to the right to reveal long lines


;;; The following lines added by ql:add-to-init-file:
#-quicklisp
(let ((quicklisp-init (merge-pathnames
                      "quicklisp/setup.lisp"
                      (user-homedir-pathname))))
  (when (probe-file quicklisp-init)
    (load quicklisp-init)))

(require 'asdf)    

;; Configure SBCL for Functional & Distributed Programming
;;========================================================

(handler-bind

      ((sb-ext:implicit-generic-function-warning #'muffle-warning)
       (sb-kernel:type-proclamation-mismatch-warning #'muffle-warning)
       (style-warning #'muffle-warning)
       (warning #'muffle-warning))

      ;; Functional programming default packages
      ;;========================================

      ; Pattern Matching
      (asdf:load-system 'optima)                 
      (asdf:load-system 'cl-algebraic-data-type)
      ; (asdf:load-system 'cl-unification)      
                                                
      ; FRP (Functional Reactive Programming Framework)                                                   
      (asdf:load-system 'cells)

      ; Functional Data Structures
      (asdf:load-system 'fset)

      ; Functional Idioms Library
      ;(asdf:load-system 'folio)        

              
      ;; Concurrent Programming
      ;;=======================

      ; Actor Model
      (asdf:load-system 'cl-actors)             

      ; CSP Concurrent Process Algebra
      ; (asdf:load-system 'chanl)
      ; (asdf:load-system 'calispel)              

      ; Software Transactional Memory
      ; (asdf:load-system 'cl-stm)   ; original            
      ; (asdf:load-system 'cl-stmx)  ; high performance              
      

      ; Static Code Analysis
      (asdf:load-system 'lisp-critic)             

      ; Appease Paren Critics
      (asdf:load-system 'readable)             
                                                
      ;; Default Namespaces
      ;;===================
      (use-package :cl-actors)
      (use-package :cells)
      (use-package :optima)                    

      ;; Unit testing
      ;;=============
      (asdf:load-system 'fiveam)
                           
)

This creates a Lisp image pre-configured for Functional Reactive Programming (FRP),  Pattern Matching, Functional Data Structures, the Actor Model, Software Transactional Memory, and the concurrency algebra CSP. FRP, Pattern Matching and the Actor Model are preloaded into the default namespace.


Go to Top

Day 5 and Onward – Putting it All Together

Let us start with the model for the cake. We will try to build up the cake as an FRP model, essentially a computation graph with nodes and edges. We expect to have input nodes, those that accept events and dependent nodes, those that are automatically recalculated when input nodes change. Nodes are connected by edges — these are the functions mapping one node onto another. In keeping with functional programming concepts we expect these functions to be free of state. The cake will have state, but as with our factorial example and the execution stack, we anticipate that that state-change in and of itself will be handled in isolation, so that it can be verified independently. To separate the concerns of state-change and state itself will be our goal. Here is version 1 of our cake model. We begin by identifying the constraints of the model, then the input nodes, followed by the dependent nodes. Version 2 will add auxiliary functions, such as useful predicates. Hint: Scroll to the right to reveal long lines


(defmodel cake ()
  (
   
    ; Constraints
    ; The reader attribute denotes a read-only
    ; accessor or immutable value
    ;------------------------------------------

    ; To have batter we need milk, eggs & flour
    (batter :reader batter :initform '(:milk :eggs :flour))

    ; To have an iced cake we must have sugar topping
    (icing :reader icing :initform '(:sugar))

    ; To have a birthday cake we must have candles
    (decoration :reader decoration :initform '(:candles))

    ; Basic actions that need to be performed
    (todos :reader todos :initform '(:knead :bake :decorate))
    
    ; Events Nodes
    ;-------------

    ; A new ingredient is mixed in
    (mixin  :initform (c-in nil))

    ; A new action is performed
    (action :accessor action :initform (c-in nil))

    ; Dependent Nodes --- initforms represent edges
    ;----------------------------------------------

    ; At any time the total set of ingredients
    ; is the set union of the last mixin and all previous ingredients
    (ingredients     
     :accessor ingredients
     :initform (c? (funcall (allingredientsfu self)  (mixin self))))

    
    ; At any time the set of done actions or "dones""
    ; is the set union of the last action and all previus actions
    (dones
     :accessor dones
     :initform (c? (funcall (alldonesfu self)  (action self))))
  
  )
)

A couple of points are worth noting. Constraints have been implemented via lists using set semantics.  Our FRP model is based on Lisp Cells [CELLS]. As such event-nodes are designated “input cells” identified by the moniker c-in in their respective initforms. In the case of input cells the initforms represent constructors. Dependent nodes are referred to as “ruled cells” and are identified by the moniker c? in their respective initforms. The initforms of ruled cells represent the edges in a computation graph. When an input cell changes, ruled cells are recomputed automatically. So far we have elided definitions for when our batter is done or the cake is done.  We have also elided definitions for two functions we appear to be calling: alldonesfu and allingredientsfu. An apparent incongruity may be perceived here in that the set of done tasks or “dones” is so obviously mutable state but that the initform for “dones” contains no state. This pattern suggests that a closure is involved and indeed alldonesfu and allingredientsfu are closures. Here are our predicates: Hint: Scroll to the right to reveal long lines


    ; Batter predicate "batter-p": At any time batterp is satisfied
    ; if the batter constraint set is a subset of the ingredients.

    (batter-p
     :accessor batter-p
     :initform (c? (subsetp (batter self) (ingredients self))))
    
    ; All done predicate "alldone-p": At any time we are "all done"
    ; if the set difference of todos and the set of dones is an emty set.
    (alldone-p
     :accessor alldone-p
     :initform (c? (not (set-difference (todos self) (dones self)))))</pre>

Note that the predicates too are ruled cells or dependent nodes in our computation graph. Here then are our closures: Hint: Scroll to the right to reveal long lines

; Closures
;-----------
(allingredientsfu :cell nil :accessor allingredientsfu :initform *all-ingredients-fu*)
(alldonesfu :cell nil :accessor alldonesfu :initform *all-dones-fu*)

The closures are initialized from the special variables *all-ingredients-fu* and *all-dones-fu*. If you are unfamiliar with special variables, these are essentially global variables whose state has local scope. We will later make these global to a package we have yet to define. Meanwhile, we need to introduce the meat for our closures. What will instances of *all-ingredients-fu* and *all-dones-fu* be set to?  We need a constructor for our closures. This constructor is shown below. Hint: Scroll to the right to reveal long lines


(defun construct-accumulator ()
  "A closure constructor, lambda-over-let-over-lambda pattern"
  (let ((elements  (list)))
    (lambda (element)
      (setf elements (adjoin element elements))
      elements
    )
  )
)

What does this actually say or do ? Inside our accumulator constructor is a lambda that takes an “element“. That lambda also refers to a list “elements” in its lexical scope.  What the lambda does is to add the element to the list using set semantics by way of the adjoin operator. It then returns the list elements as its return value. Recall that in functional programming the value of the last expression is the return value of the whole expression. But where does elements actually live? In the surrounding let binding. elements is a free variable in that it is not bound in the argument list of the lambda. A closure then is a construct whose state is closed over its free variables — another way of saying this is that the closure remembers its associated list of elements. Note that this is analog to the stack in our factorial example tracking the state surrounding  the recursive factorial function. Our accumulator tracsk We can now direct both our *all-ingredients-fu* and *all-dones-fu* at this accumulator constructor. What we have achieved is that we separated the concerns of  state change ( accumulation of elements in a set ) and the representation of state in our cake model. Shown below is the finished model of the cake. Note that we have made one minor modification to our accumulator to remove any nil elements from the sets . Hint: Scroll to the right to reveal long lines


(defun construct-accumulator ()
  "A closure constructor, lambda-over-let-over-lambda pattern"
  (let ((elements  (list)))
    (lambda (element)
      (setf elements (remove nil (adjoin element elements)))
      elements
    )
  )
)

(defvar *all-ingredients-fu* nil)
(defvar *all-dones-fu* nil)

(defmodel cake ()
  (

    ; Closures
    ;---------
    (allingredientsfu :cell nil :accessor allingredientsfu :initform *all-ingredients-fu*)
    (alldonesfu :cell nil :accessor alldonesfu :initform *all-dones-fu*)  
   
    ; Constraints
    ;------------ 

    ; To have batter we need milk, eggs & flour
    (batter :reader batter :initform '(:milk :eggs :flour))

    ; To have an iced cake we must have sugar topping
    (icing :reader icing :initform '(:sugar))

    ; To have a birthday cake we must have candles
    (decoration :reader decoration :initform '(:candles))

    ; Basic actions that need to be performed
    (todos :reader todos :initform '(:knead :bake :decorate))
    
    ; Events Nodes
    ;-------------

    ; A new ingredient is mixed in
    (mixin  :initform (c-in nil))

    ; A new action is performed
    (action :accessor action :initform (c-in nil))

    ; Dependent Nodes & initforms represent edges
    ;---------------------------------------------

    ; At any time the total set of ingredients
    ; is the set union of the last mixin and all previous ingredients
    (ingredients     
     :accessor ingredients
     :initform (c? (funcall (allingredientsfu self)  (mixin self))))

    
    ; At any time the set of done actions or "dones""
    ; is the set union of the last action and all previous actions
    (dones
     :accessor dones
     :initform (c? (funcall (alldonesfu self)  (action self))))
    
    ; Batter predicate "batter-p": At any time batterp is satisfied
    ; if the batter constraint set is a subset of the ingredients.
    (batter-p
     :accessor batter-p
     :initform (c? (subsetp (batter self) (ingredients self))))
    
    ; All done predicate "alldone-p": At any time we are "all done"
    ; if the set difference of todos and the set of dones is an emty set
    (alldone-p
     :accessor alldone-p
     :initform (c? (not (set-difference (todos self) (dones self)))))
   
  )
)

It is interesting to note that the Cells model derives, as a paradigm, from the Common Lisp Object System (CLOS). This means that all semantics and syntax associated with classes in CLOS also hold for cells. It is an instance of a programming paradigm, here FRP, deriving from another, here CLOS. This struck me as particularly characteristic of Lisp. In C++ or Java, it is possible to derive one class from another. In Lisp, it is possible to derive entire paradigms from another. This truly exhibits how malleable this language is. However, our model has loose ends. At present nothing sets *all-ingredients-fu* and *all-dones-fu*.  Also, there is plenty of room for things to go wrong here: actions on our cake may be performed out of order; ingredients added at the wrong time. But this is the realistic model of a cake. It’s passive. Stick  on candles before baking, and you get a molten mess of wax. However tempting it may be to model desired invariants at this level, we should not. If we do, we will be out of tune with the “problem domain” and as requirements change our model will not evolve in unison. It will lack what is referred to as connascense. connescence. What then is connascent with our cake? The baker. The baker is the actor that enforces the invariants.


Go to Top

Day 6 Actor Model

This is the time to introduce the actor model. If we expect to enforce correctness at this level of abstraction, we might also expect pattern matching to play its part. We would be right. Firstly, the actor model. Hint: Scroll to the right to reveal long lines


(defactor actor-class
         (state)
         (message-vars)
         behavior)

With this definition in mind, we define our baker. It is here, we will define invariants. This will stitch together the three aspects of the actor model, pattern matching and FRP. Hint: Scroll to the right to reveal long lines


(defactor baker 

  ; State Form - let bindings for actor local state
  ;------------------------------------------------
  ((*all-ingredients-fu* (construct-accumulator))
   (*all-dones-fu* (construct-accumulator))
   (mycake (make-instance 'cake)))

  ; Message Form - We match on a single argument
  ;---------------------------------------------
  (message)                          

  ; Behavior Form
  ;-------------
  (match message

    ; match adding batter ingredients only
    ((list :add ingredient)  when
     (member ingredient (batter mycake))
     
     (if (batter-p mycake) ; batter already done ?  
        (format t "~%ERROR: Batter complete. Don't need ~A" ingredient )
        (if (member ingredient (ingredients mycake))
           (format t "~%Error: Already have ~A in batter" ingredient )
           (setf (mixin mycake) ingredient)))) ; update cake here

    ; match adding icing ingredients but only after baking
    ((list :add ingredient)  when
     (and (member ingredient (icing mycake))
          (member :bake (dones mycake)))
     
     (if (member ingredient (ingredients mycake))
        (format t "~%ERROR: Already have ~A on cake" ingredient)
        (setf (mixin mycake) ingredient))) ; update cake here

    ; match adding decoration ingredients but only after baking
    ((list :add ingredient)  when
     (and (member ingredient (decoration mycake))
          (member :bake (dones mycake)))
     
     (if (member ingredient (ingredients mycake))
        (format t "~%ERROR: Already have ~A on cake" ingredient )
        (progn
           (setf (mixin mycake) ingredient) ; update cake here
           (setf (action mycake) :decorate)))) ; update cake here

    ; match actions
    ((list :act todo)  when
     (member todo (todos mycake))
     
     (if (alldone-p  mycake) ; cake already finished?  
        (format t "~%ERROR: Cake is finished. Decline to do ~A" todo )
        (if (member todo (dones  mycake)) ; todo already done?
           (format nil "~%ERROR: Already did  ~A" todo  )
            
           (cond ((equal todo :bake) ; bake only after kneading dough
                  (if (not (member :knead (dones mycake)))
                     (format t "~%ERROS: Knead batter first. Can't do ~A" todo  )
                     (setf (action mycake) todo) ; update cake here
                  )                     
                 )
                 ((equal todo :knead) ; knead dough only after batter complete
                  (if (not (batter-p mycake))
                      (format t "~%ERROR: Batter not ready. Can't knead dough" )
                      (setf (action mycake) todo) ; update cake here
                  )
                 )
                 (t (format t "~%ERROR: Don't know  ~A" todo ))))))
    
    ; fall-through             
    (_
     (format t  "~%ERROR: recipe error"))
    
  )

  ; Match next message
  ;-------------------
  next)

Finally, we prefix everything with our package definition. Hint: Scroll to the right to reveal long lines

(defpackage :bakery
; import namespaces from the following packages
(:use :common-lisp :cl-actors :optima :bordeaux-threads :cells)

; bakery package exported symbols
(:export #:baker
:cake))

(in-package :bakery)

We note that our actor is essentially a pure rule engine without state of its own. We created two closure constructors which we passed to the cake by way of dynamic scope. After that we do not reference these. We create a cake which is an FRP model. To this we defer all state. The baker indeed does not store any information about the cake. All information is about the cake is observed.


Go to Top

Day 7 Taking It All For a Spin

This is where we will find out if the three aspects of actor model, FRP & pattern matching will actually dance together. Before we do, we digress once more. Aside from error messages, our theoretical model does not yield any useful output yet. If we want to see all the pieces dance together, we will want to add to add some useful output. Like any baker, we will want to observe what happens. So let us add some observers. Observers allow us to trigger specific actions in response to a change in state in our model. They also keep the logic for these triggers and consequent events entirely outside of the model being observed. This is a very useful separation of concerns as both concerns tend to evolve independently. They lack, in software engineering terms, connascense. http://www.netobjectives.com/resources/books/design-patterns-explained/cpp-code-examples/chapter18 shows an example of the observer pattern implemented in C++. Ours will be significantly shorter than that. What then might the ideal abstraction of the observer pattern be?  At a minimum we will need to declare our intention to observe something, whom or what we wish to observe, and finally we are probably interested in any new state that arises. Ideally we would like to get both before-state and after-state at once, so as to avoid having to store any state ourselves. This fits nicely with the functional programming model. Here then is our first observer. Hint: Scroll to the right to reveal long lines


(defobserver batter-p ((self cake))
  "An observer on cell batter-p on instances of cake models"
  (if new-value ; new
        (format t "~%CAKE OBSERVER: Batter now complete" )))

In the above we define an observer, defobserver, on our “batter ready” predicate batter-p. Before-state is in the binding old-value. After-state is in the binding new-value.  We are really only interested in when the predicate changes from false, batter not ready, to true, batter ready. As this is a boolean, we can simply say “if new-value.” The simplistic action triggered is to output the string “CAKE OBSERVER: Batter now complete.” The Lisp command format output is equivalent to printf in C. For the sake of completeness, here are the rest of our observers. Hint: Scroll to the right to reveal long lines


(defobserver  alldone-p  ((self cake))
  "An observer on cell alldone-p  on instances of cake models"
  (if new-value ; new
        (format t "~%CAKE OBSERVER: Cake is all done" )))

(defobserver ingredients ((self cake))
  "An observer on cell ingredients on instances of cake models"
  (format t "~%CAKE OBSERVER: Ingredients now ~A" new-value ))

(defobserver dones  ((self cake))
  "An observer on cell dones on instances of cake models"
  (format t "~%CAKE OBSERVER: Completed tasks now ~A" new-value ))

One point is worth repeating here. We have separated the concern of state change from the cake model itself. Dealing with state change has been side-lined to observers. These too store no state. They only look at deltas, the before and after states and trigger some action. There are no call-outs, call-backs or other plumbing. Of course, like the example of the factorial function where state was hidden in the stack, here too the mechanics are hidden, in this case by the FRP model Cells [CELLS]. The observer abstraction is an adjunct to Cells [CELLS]. The point, as before, is that each aspect is separately verifiable and free to evolve independently as requirements in the user domain change. This aims directly at the essence of software engineering — which is to manage complexity.

Roll the dice…

Let’s build our model. The below screen-shot is from the SBCL REPL in Emacs.

Building the Model

Building the Model

Compilation times can be a real refresher if you come from the world of Clojure. Next we pull the bakery package into our current namespace and define an instance of a baker.

Create Baker

Create Baker

Immediately our observers chime in. We have no ingredients in the cake and no tasks are completed. Let’s do something. We have an inherently concurrent actor model, albeit just the one baker. Let’s talk to him and tell him to add flour.

Add Flour

Add Flour

We’re sneaky. Let’s tell him to knead that. He’ll be here for days.

Or maybe not

Or maybe not

Then again, perhaps not. Our rule engine and set of invariants appear to be playing together nicely. Let’s add milk and eggs.

Batter Complete

Batter Complete

Two of our observers have chimed in. The batter is complete. Let’s ruin the recipe and add pepper.

No pepper please

No pepper please

Ok, that didn’t pattern-match. Milk, milk will do it. We’ll make the dough soupy. We’re really mischievous here.

Don't fool me

Don’t fool me

Ok, time to play nice. Our baker is on the ball. We’ll resign to going with the program then since we can’t wreck havoc.

Bake me a Cake

Bake me a Cake

Observers chiming in with completed actions. What’s missing ? Ah, icing and candles. Icing needs sugar on top.

Icing

Icing

Cake all done

Cake all done

We note that each observer is only invoked when its observed value changes. This is intuitive. Our last observer tells us we have finished. It is also worth pointing out that the Cells FRP model will recalculate only relevant parts of the computation graph. Dependent nodes without upstream changes will not be recalculated. Further, it is possible to define nodes as eagerly evaluated ( the default ), lazily evaluated or semi-lazily evaluated. These are high level optimization techniques that improve performance.


Go to Top

Conclusion

We have integrated three paradigms: FRP, the actor model & pattern matching. Perhaps the most striking is that none of the authors of these frameworks worked together to make the features of their frameworks blend. We have just done all the blending. Surely one author might well have had the benefit of hindsight of another’s work. But none note in their examples how their framework achieves interaction with another in our mix. They simply did not design for it. Note how this differs fundamentally from class based interaction in C++ or Java where the target might be to interact with a class or an abstract interface of a particular version. With C++ and Java, most of the time even minor version differences are sufficient to trip up even frameworks that are full well intended to cooperate. Here, by contrast, we have a blending of source code level primitives of dissimilar and otherwise unrelated frameworks. And we have demonstrated that these can be made to cooperate in perfect harmony. We have also achieved this without referring to macros or other forms of meta-programing. These were the rules of our game. The full source code listing follows below.

Hint: Expand via (+) to view source code 
Hint: Scroll to the right to reveal long lines

(defpackage :bakery
  ; import namespaces from the following packages
  (:use :common-lisp :cl-actors :optima :bordeaux-threads :cells)
 
  ; bakery package exported symbols
  (:export #:baker
           :cake))

(in-package :bakery)

(defun construct-accumulator ()
  "A closure constructor, lambda-over-let-over-lambda pattern"
  (let ((elements  (list)))
    (lambda (element)
      (setf elements (remove nil (adjoin element elements)))
      elements)))

(defvar *all-ingredients-fu* nil)
(defvar *all-dones-fu* nil)

(declaim (sb-ext:muffle-conditions style-warning))
(declaim (sb-ext:muffle-conditions sb-kernel:redefinition-with-defmethod))

;; The model defines nodes and how edges connect them to build up a computation graph.
;; Incidentally the model derives from the Common Lisp Object System (CLOS)
;; Hence Common Lisp object-oriented semantics and syntax hold.

(defmodel cake ()
  (

    ; Closures
    ;---------
    (allingredientsfu :cell nil :accessor allingredientsfu :initform *all-ingredients-fu*)
    (alldonesfu :cell nil :accessor alldonesfu :initform *all-dones-fu*)  
   
    ; Constraints
    ;------------ 

    ; To have batter we need milk, eggs & flour
    (batter :reader batter :initform '(:milk :eggs :flour))

    ; To have an iced cake we must have sugar topping
    (icing :reader icing :initform '(:sugar))

    ; To have a birthday cake we must have candles
    (decoration :reader decoration :initform '(:candles))

    ; Basic actions that need to be performed
    (todos :reader todos :initform '(:knead :bake :decorate))
    
    ; Events Nodes
    ;-------------

    ; A new ingredient is mixed in
    (mixin  :initform (c-in nil))

    ; A new action is performed
    (action :accessor action :initform (c-in nil))

    ; Dependent Nodes & inir forms represent Edges
    ;---------------------------------------------

    ; At any time the total set of ingredients
    ; is the set union of the last mixin and all previous ingredients
    (ingredients     
     :accessor ingredients
     :initform (c? (funcall (allingredientsfu self)  (mixin self))))

    
    ; At any time the set of done actions or "dones""
    ; is the set union of the last action and all previus actions
    (dones
     :accessor dones
     :initform (c? (funcall (alldonesfu self)  (action self))))
    
    ; Batter predicate "batter-p": At any time batterp is satisfied
    ; if the batter constraint set is a subset of the ingredients.
    ; This model permits adding other ingredients, such as spices
    ; so the subset relationship is a good fit here.
    (batter-p
     :accessor batter-p
     :initform (c? (subsetp (batter self) (ingredients self))))
    
    ; All done predicate "alldone-p": At any time we are "all done"
    ; if the set difference of todos and the set of dones is an emty set
    ; This essentially says, follow the recipe. If you perform other tasks
    ; we don't warrant the outcome. The cake may be destroyed.
    (alldone-p
     :accessor alldone-p
     :initform (c? (not (set-difference (todos self) (dones self)))))
   
  )
)

(declaim (sb-ext:unmuffle-conditions style-warning))
(declaim (sb-ext:unmuffle-conditions sb-kernel:redefinition-with-defmethod))

(defobserver batter-p ((self cake))
  "An observer on cell batter-p on instances of cake models"
  (if new-value ; new
        (format t "~%CAKE OBSERVER: Batter now complete" )))

(defobserver  alldone-p  ((self cake))
  "An observer on cell alldone-p  on instances of cake models"
  (if new-value ; new
        (format t "~%CAKE OBSERVER: Cake is all done" )))

(defobserver ingredients ((self cake))
  "An observer on cell ingredients on instances of cake models"
  (format t "~%CAKE OBSERVER: Ingredients now ~A" new-value ))

(defobserver dones  ((self cake))
  "An observer on cell dones on instances of cake models"
  (format t "~%CAKE OBSERVER: Completed tasks now ~A" new-value ))
                 

;; An abstraction of RULES/INVARIANTS
;; Only state is cake itself

(defactor baker 

  ; State Form - let bindings for actor local state
  ;------------------------------------------------
  ((*all-ingredients-fu* (construct-accumulator))
   (*all-dones-fu* (construct-accumulator))
   (mycake (make-instance 'cake)))

  ; Message Form - We match on a single argument
  ;---------------------------------------------
  (message)                          

  ; Behavior Form
  ;-------------
  (match message

    ; match adding batter ingredients only
    ((list :add ingredient)  when
     (member ingredient (batter mycake))
     
     (if (batter-p mycake) ; batter already done ?  
        (format t "~%ERROR: Batter complete. Don't need ~A" ingredient )
        (if (member ingredient (ingredients mycake))
           (format t "~%Error: Already have ~A in batter" ingredient )
           (setf (mixin mycake) ingredient)))) ; update cake here

    ; match adding icing ingredients but only after baking
    ((list :add ingredient)  when
     (and (member ingredient (icing mycake))
          (member :bake (dones mycake)))
     
     (if (member ingredient (ingredients mycake))
        (format t "~%ERROR: Already have ~A on cake" ingredient)
        (setf (mixin mycake) ingredient))) ; update cake here

    ; match adding decoration ingredients but only after baking
    ((list :add ingredient)  when
     (and (member ingredient (decoration mycake))
          (member :bake (dones mycake)))
     
     (if (member ingredient (ingredients mycake))
        (format t "~%ERROR: Already have ~A on cake" ingredient )
        (progn
           (setf (mixin mycake) ingredient) ; update cake here
           (setf (action mycake) :decorate)))) ; update cake here

    ; match actions
    ((list :act todo)  when
     (member todo (todos mycake))
     
     (if (alldone-p  mycake) ; cake already finished?  
        (format t "~%ERROR: Cake is finished. Decline to do ~A" todo )
        (if (member todo (dones  mycake)) ; todo already done?
           (format nil "~%ERROR: Already did  ~A" todo  )
            
           (cond ((equal todo :bake) ; bake only after kneading dough
                  (if (not (member :knead (dones mycake)))
                     (format t "~%ERROS: Knead batter first. Can't do ~A" todo  )
                     (setf (action mycake) todo) ; update cake here
                  )                     
                 )
                 ((equal todo :knead) ; knead dough only after batter complete
                  (if (not (batter-p mycake))
                      (format t "~%ERROR: Batter not ready. Can't knead dough" )
                      (setf (action mycake) todo) ; update cake here
                  )
                 )
                 (t (format t "~%ERROR: Don't know  ~A" todo ))))))
    
    ; fall-through             
    (_
     (format t  "~%ERROR: recipe error"))
    
  )

  ; Match next message
  ;-------------------
  next)

            


Go to Top

Improvements

What is not implied is that it is possible to select any two frameworks or libraries in Lisp at random and blend features at will. The combination of FRP, pattern matching and actor model was carefully chosen as a feature set that would indeed cooperate. It would be nice to introduce software transactional memory into the blend if we truly seek to match Clojure. I have not attempted this yet. Also nice to have would be exhaustive pattern matching based on algebraic types. Lisp already has native product types. Hence only need sum types. A quick experiment with these is shown in the epilogue.


Go to Top

Epilogue

The below example illustrated the use of algebraic sum types and exhaustive pattern matching.

Sum Type

Sum Type

Lets us create an instance of type point and check its type predicates.

Sum Type Inheritance

Sum Type Inheritance

Next we define a pattern match, eliding the polar case on purpose.

Exhaustive Pattern Match

Exhaustive Pattern Match

We note that we get a non-exhaustive match warning at compile time, not run time. This is the behaviour we would expect for example from OCaml. Indeed, in our little game we might change the simple use of keyword symbols to algebraic data types and thus add compiler hosted verification of our pattern matches. To bring our exploration of the meta-circular abstraction to a full circle: Abstract data-types are an ideal medium in which to represent Abstract Syntax Trees or ASTs. Indeed the whole of Lisp syntax is itself fundamentally an Abstract Syntax Tree. So let’s see if we can represent trees using the cl-algebraic-datatype package. That would amount to an Abstract Syntax Tree represented inside an Abstract Syntax Tree. We will close with that that little teaser.

Algebraic Sum Type as Tree

Algebraic Sum Type as Tree

voilà


Go to Top

Postscript – Adding Exhaustive Pattern Matching

With the epilogue example in place, the question re-emerged if it would be possible to integrate algebraic types and their exhaustive pattern matching into what we have already. The key issue is that the matching algorithm provided in the algebraic data types package (ADT) is geared specifically towards algebraic data types and that the currently recommended pattern match algorithm in the Optima package is significantly more feature complete and, though I have not proven this, claimed to be more efficient. So ideally we would like to keep Optima’s pattern matching for more complex de-structuring while using ADTs pattern match for any algebraic types we construct. To start with, we avoid a name clash on match itself by not performing a (use-package ‘adt). This means we must refer to ADT package exports explicitly. Firstly, we amend our own package exports: Hint: Scroll to the right to reveal long lines


(defpackage :bakery
  ; import namespaces from the following packages
  (:use :common-lisp :cl-actors :optima :bordeaux-threads :cells)
 
  ; bakery package exported symbols
  (:export #:baker
           :cake
           :batter-ingredient
           :milk
           :flour
           :eggs))

The above means we will be exporting a baker function and cake model but now additionally also a batter-ingredient type (our algebraic type) and the three types milk, flour & eggs. Now to constructing our type for batter-ingredients. In our previous examples, we took oversimplified to exclude amounts. Lets plan to include those in round number 2. We will model units in a type safe manner later. Hint: Scroll to the right to reveal long lines


(adt:defdata (batter-ingredient)
  (milk float)
  (flour float)
  (eggs integer))

Now to integrating this in our pattern match within the baker actor.


  ; Behavior Form
  ;-------------
  (match message

    ; match adding batter ingredients ADT
    ((TYPE batter-ingredient)            
     (adt:match batter-ingredient message  
       ((milk ml)
        (format t "~%Adding ~a milliliters of milk" ml))
       ((flour gr)
        (format t "~%Adding ~a grams of flour" gr)))) 
...

In brief, we have added a type guard from the Optima package match algorithm. Then we refer to ADT’s pattern match to extract amounts. But wait, we have elided the eggs. Let’s see what happens. We expect this to fall over at compile time.

ADT Match Compile Time Check

ADT Match Compile Time Check

The compiler advises us we have missed the case EGGS. Lets put these in.


  ; Behavior Form
  ;-------------
  (match message

    ; match adding batter ingredients ADT
    ((TYPE batter-ingredient)            
     (adt:match batter-ingredient message  
       ((milk ml)
        (format t "~%Adding ~a milliliters of milk" ml))
       ((flour gr)
        (format t "~%Adding ~a grams of flour" gr))  
       ((eggs numeggs)
        (format t "~%Adding ~a egg(s)" numeggs)))) 
...

Now compilation proceeds smoothly. The screenshot below shows in action what he have just constructed.

Exhaustive Pattern Matching Integrated

Exhaustive Pattern Matching Integrated

We have yet to add type safe units of measurement and we have yet to add our various cake model predicates etc., but the point here was to illustrate the blend of two pattern matching algorithms to arrive at both comprehensive de-structuring as well as the narrower feature set around algebraic types.


Go to Top

Abacus – Unified Syntax for Pattern Matching over Algebraic Types in Common Lisp

Abacus is a library to integrate de-structuring pattern matching from  Optima and Algebraic Data Types.  Pattern matching and algebraic data types  are intimately related in functional programming languages like OCaml and Haskell.  As such, this is really a continuation of the above blog post, but now we are moving into an area of changes to  syntax and the compilation process that will indeed require macros. Macros were disallowed in our previous “game” just to see how far we would get.  I wanted to turn this into a deployable package, hence the choice of a name. The ancient calculator Abacus seemed like a fitting name. The full source code for Abacus is available on Github at  https://github.com/chriskmanx/abacus. Just what is the motivation here? Let’s revisit our current syntax.


  ; Behavior Form
  ;-------------
  (match message

    ; match adding batter ingredients ADT
    ((TYPE batter-ingredient)            
     (adt:match batter-ingredient message  
       ((milk ml)
        (format t "~%Adding ~a milliliters of milk" ml))
       ((flour gr)
        (format t "~%Adding ~a grams of flour" gr))  
       ((eggs numeggs)
        (format t "~%Adding ~a egg(s)" numeggs)))) 
...

We observe the Optima TYPE guard that stipulates that message must be of type batter-ingredient. We recall that we defined the latter to be an algebraic data type. We then invoke the match logic in the algebraic data types package ADT. The average Lisper will say, I can write this. I can see what is going one. Good enough. Of course there is plenty of room for mistakes as the code base grows to accommodate more logic and presently co-located forms grow apart in distance from each other. The term message is repeated. The type guard TYPE is assumed to operate on message from this first, Optima match statement. That relationship isn’t obvious by the way. It also does not really “guard” what is happening next. As variable names get changed and perhaps adt:match batter-ingredient isn’t immediately following the clause “match message“, a programmer might change one but not the other. Variable names repeat unnecessarily — these need to be kept in synch for semantics to hold. Further, the Optima TYPE guard does not ensure that what is being matched is indeed an algebraic type. It is up to the programmer to ensure it is, and traditionally in a dynamically typed language the onus has been on the programmer to get types right. But this is Lisp. The same system that is available at runtime is available at compile time. So there is really no reason to delegate this type of check to either the common sense of the programmer or the runtime just to watch it fall over in the hands of the user when the programmer gets it wrong. We further observe overlapping namespaces intersecting on the match statement. There are but a handful of lines of code and more ways than a handful to shoot oneself in the foot. As central as Pattern Matching is to functional programming, it deserves a clean, coherent syntax. This is what we set out to create. Trying to spare the reader a progression of “Day 1″, “Day 2″ & “Day3 “, we skip straight to the end. The syntax we aim to create will closely follow that of Haskell & Ocaml. To revisit…

let is_zero n = match n with
0 -> true
| _ -> false ;;

So the basic construct is an OR symbol followed by a match expression, then an arrow symbol mapping to the match clause to be evaluated when the match expression is true, followed by a sentinel symbol, here ;; Of course this is Lisp so we will want to follow the general principle of start of scope and end of scope. We can make these configurable. We may introduce intermediate symbols where they add clarity. I personally think the -> adds clarity, but this is a preference. Haskell uses =>. Staunch supporters of s-expression syntax will argue for a purist stance using s-expressions only, but witness the syntax of the LOOP macro and you will find promiscuous use of symbols even in standardised Common Lisp. That out of the way, lets see what we can do here.   Below is our actor model refitted with the new syntax using regular s-expression.


  (amatch message

    (all when (algebraic-guard all batter-ingredient)
      (algebraic-match-with
        ((milk ml) ; constructor pattern
            (format t "~%Adding ~a milliliters of milk" ml))
        ((flour gr) ; constructor pattern
            (format t "~%Adding ~a grams of flour" gr))
        ((eggs numeggs) ; constructor pattern
            (format t "~%Adding ~a egg(s)" numeggs)))) 

 

We observe that the main Optima match has been replaced by amatch. This is a macro wrapper around Optima’s match macro.  It enables algebraic pattern matching in code that follows it. As before, we might also match on non algebraic types, but amatch enables a unified syntax for matching on algebraic types.  Next is a construct that is intended to model universal quantification in mathematics: For all where all satisfy the predicate algebraic-guard over a specific type. In our new syntax this is written as “(all when (algebraic-guard all batter-ingredient)”.  Note that the  predicate algebraic-guard won’t  be satisfied if batter-ingredient is not an algebraic data type. This remedies the problem with our earlier TYPE guard. algebraic-guard also makes any necessary bindings for subsequent syntax to work without repetition of any variables . Note that the variable message is no longer referred to.  Overlapping namespaces on the match statement itself have been removed. What follows is a simple constructor pattern on our algebraic sub-types, followed by the appropriate match clause. Let’s try this out.

Algebraic Matching in Action

Algebraic Matching in Action

S-Expression purists can stop here, but for a little syntactic sugar, keep reading.


(use-extended-match-syntax)
...

 (all when (algebraic-guard all batter-ingredient)
   (algebraic-match-with
     | (milk ml) =>
       (format t "~%Adding ~a milliliters of milk" ml)]
     | (flour gr) =>
       (format t "~%Adding ~a grams of flour" gr) ]
     | (eggs numeggs) =>
       (format t "~%Adding ~a egg(s)" numeggs) ] ) )

 

In the above code snippet we introduce a syntax which more closely follows that of Haskell or OCaml, including the use of the OR symbol and the arrow symbol. We use the closing bracket as delimiter. Use of this syntax is enabled, purely optionally of course, by calling (use-extended-match-syntax). There exists a matching (disable-extended-match-syntax). It is hoped that the resulting syntax offers visual clarity similar to that offered by the Ocaml match syntax. One great thing about Lisp macros is that macros allow the user to modify the behaviour of the compiler. It is possible to verify assertions and correspondingly  raise warnings or even errors. Lets watch this in action. Firstly, we uncomment the flour case.


 (all when (algebraic-guard all batter-ingredient)
   (algebraic-match-with
     | (milk ml) =>
       (format t "~%Adding ~a milliliters of milk" ml)]
     ;; | (flour gr) =>
     ;;  (format t "~%Adding ~a grams of flour" gr) ]
     | (eggs numeggs) =>
       (format t "~%Adding ~a egg(s)" numeggs) ] ) )

 

We receive the same familiar message about a non-exhaustive match. Note that this is a compile time message, not a run-time failure.

Non Exhaustive Match

Non Exhaustive Match

Let’s introduce some deliberately malformed expressions to see if we have indeed introduced new syntax with appropriate compiler errors.


 (all when (algebraic-guard all batter-ingredient)
   (algebraic-match-with
     | (milk ml) =>
       (format t "~%Adding ~a milliliters of milk" ml)]
     | (flour gr) => ]
     | (eggs numeggs) =>
       (format t "~%Adding ~a egg(s)" numeggs) ] ) )

 
Compiler Error on Expression

Compiler Error on Expression

Next we will elide the match symbol =>.


 (all when (algebraic-guard all batter-ingredient)
   (algebraic-match-with
     | (milk ml) =>
       (format t "~%Adding ~a milliliters of milk" ml)]
     | (flour gr)
       (format t "~%Adding ~a grams of flour" gr)]
     | (eggs numeggs) =>
       (format t "~%Adding ~a egg(s)" numeggs) ] ) )

 

 

Missing Match Symbol

Missing Match Symbol

How about this ?


 (all when (algebraic-guard all batter-ingredient)
   (algebraic-match-with
     | (milk ml) =>
       (format t "~%Adding ~a milliliters of milk" ml)]
     | ]
     | (eggs numeggs) =>
       (format t "~%Adding ~a egg(s)" numeggs) ] ) )

 
Empty Expression

Empty Expression

So it appears we can both verify the application logic as well as validate the basics of our syntax by modifying the behavior of the Lisp compiler — all with macros directly at compile time. Any feedback on the pattern matching syntax proposed and implemented here is warmly welcome.

Github Repository

https://github.com/chriskmanx/abacus


Go to Top

References

[Clojure]  http://en.wikipedia.org/wiki/Clojure [Let-Over-Lambda] http://letoverlambda.com/index.cl/guest/chap5.html#sec_1 [Lisp-Converge-C++] http://chriskohlhepp.wordpress.com/convergence-of-modern-cplusplus-and-lisp/ [QuickLisp] http://www.quicklisp.org/ [First-Class] http://en.wikipedia.org/wiki/First-class_function [Higher-Order] http://en.wikipedia.org/wiki/Higher-order_function [Computer-Program] http://en.wikipedia.org/wiki/Computer_program [ADT] http://en.wikipedia.org/wiki/Algebraic_data_type [SBCL] http://www.sbcl.org/ [FRP] http://en.wikipedia.org/wiki/Functional_reactive_programming [CL-WIKI] http://www.cliki.net/ [CELLS] http://common-lisp.net/project/cells/ [OPTIMA] https://github.com/m2ym/optima [CL-ADT]  https://bitbucket.org/tarballs_are_good/cl-algebraic-data-type

Go to Top

6 responses to “Meta-Circular Adventures in Functional Abstraction – Challenging Clojure in Common Lisp

  1. Mike S.

    Fascinating post, thanks for writing it. But respectfully I think you gloss over three of the strengths of Clojure. First, data structures are immutable by default and you have to resort to one of the software-transactional-memory constructs to work around it. Of course you can write Common Lisp code without modifying data in-place, but the Clojure creator believes – and I’ve come to think he may be right – that operating with immutable by default and mutability as the exceptional case makes it simpler to reason about your code behavior (concurrently or not). Second, instead of making the list the primary data structure, the central concept is the sequence and the three sequence implementations are lists (as in Common Lisp with the parenthesis), vectors (array based and faster for many classes of operation, with square brackets), and maps (key-value stores, with curly braces). Whether that change is worthwhile I can’t say, but it seems significant to me. Third, the use of the JVM allows people to integrate Clojure with Java and other JVM languages more easily than you can interface Common Lisp with other languages using foreign function interfaces. The hope is that easy integration of existing Java libraries, a simpler transition from Java to Clojure than Java to using SBCL or CLISP, etc… will allow Clojure to become widely used where Common Lisp has not.

    • Hello Mike and the thank you very much for your constructive feedback. Let me take each in turn.

      1) I very much appreciate what amounts to an emphasis on immutability on the part of Clojure. Let’s keep in mind though that we are talking about an emphasis. A purist will argue that, like Haskell, all side effects ought to be isolated – for example by means of monads. I don’t think Clojure fits in that camp, so the difference is one of emphasis, not principle. Mutable state is very much part of Clojure. See http://clojure.org/vars. Perhaps functional data structures in Common Lisp ought to have been part of my first example. I elided these but they do exist. You can read about them here http://common-lisp.net/project/fset/. Maybe what can be said is that Clojure takes a stronger pro-purity stance than Lisp and that these restrictions force people into a paradigm that will keep them from making a type of mistake. However, as demonstrated at http://clojure.org/vars, Clojure didn’t take the purist stance on the purist argument. I am very much trying to get to a point where idiomatic functional programming, and that very much includes purity, is readily supported in Common Lisp. Until now it could be said to be “incoherent” at best. This is precisely at the heart of what I am trying to solve.

      2) You are right in that lists are but one specialization of a sequence. Of course lists are central to Common Lisp mostly in so far as these are the default data structure for representing code. Clojure shares this concept. Representing code in a data-structure understood by the language, is what makes Common Lisp and Clojure homoiconic — a tremendous concept in meta programming that is lost on all C family languages. It is the reason that meta-programming in C family languages is and remains an awkward stilted mess. Few languages got this right. Prolog, Lisp, Scheme, Clojure and Julia are some of the few that do. What it does not mean is that everything is or should be a list. Common Lisp does have native vectors & maps just like C++. See http://www.gigamonkeys.com/book/collections.html. What these collections are not by default, is functional. Yet again, functional data structures do exist. I will make it a point to include these in a follow-up to this article. I am not precious about the square brackets in Clojure vectors. They can be done with reader macros. In fact someone did. In their words, not mine, for edification, not utility. See https://github.com/ayrnieu/disclojure.

      3) I would have been happy with Clojure if it had not been for the JVM, although I appreciate that a subset of Clojure can target JavaScript and therefore Google V8. Fundamentally, Clojure is designed to be a hosted language. Now, this little article and everything in it is unrelated to my current job per say, BUT my overall background is in control systems, ranging from radar-missile systems to electronic trading. I have a keen interest in robotics and therefore embedded systems. What is invaluable to me is the ability to connect and therefore optimize abstractions all the way down to machine code. http://chriskohlhepp.wordpress.com/convergence-of-modern-cplusplus-and-lisp/ demonstrates how to do this. A hosted language, any hosted language, takes that away from me. Abstractions become disconnected from optimization. So while I appreciate what Clojure sets out to do in its integration with the JVM, and it does it well, the use case is simply not everyone’s “cup of tea.”

      As previously noted, what I am trying to do is make idiomatic functional programming coherent in Common Lisp. To this end, I am talking to a number of the authors of various Lisp packages central to this idea to effect a tighter integration that will make that possible. Utimately, I envisage that this will entail lower level changes such as making certain warnings emanating from compile time type inference into errors, precisely to rule out certain types of errors. All of this will need to be pulled together into a coherent package somehow. So stay tuned for version 2 of this article…

  2. Mike S.

    chriskohlhepp, thank you for taking the time to write such a detailed response. I think all of your responses make sense.

    I have only used Common Lisp and Clojure in a few toy projects. I’m a pretty stereotypical software developer that worked in C++ and then Java with a smattering of scripting languages in the mix. Even though Clojure draws on Lisp and not the other way around, Clojure was my gateway to Lisp and I love it for that.

    Working in the embedded space sounds fascinating. I started my formal education with the express purpose of avoiding work close to the bare metal on computers because it was easier. A decade after finishing school I was kicking myself, because now I find the topic interesting and I don’t have the time to pursue it. I’ll put it on the todo list somewhere behind “being able to write non-trivial applications in Lisp”.

    I’ve enjoyed the exchange and your posts, thank you.

  3. Cool. Some notes:

    1. You can dump all the accumulator baggage and just do:

    (c? (adjoin (action self) .cache))

    2. I recommend ephemeral cells for things that are akin to events:
    (action nil :cell :ephemeral)

    -hk

  4. Don Torrido

    Thank you for your article, I like the style of your writing and the way in which you explain concepts clearly. Also, as I am always trying to improve my English I annotate your use of stance, envisage and bestow (new words for me). I am eager to read your next post. Good work, I appreciate it.

  5. Noah

    Thank you for the excellent article. I am very much looking forward to version 2.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s