venerdì 29 gennaio 2016

Marvin Minsky, one of the early pioneers of neural networks and frame language, died on Sunday at the age of 88

What can I say?
Minsky was friends with Richard Feynman, Isaac Asimov, Arthur C. Clarke, and Stanley Kubrick. He studied under Claude Shannon, worked with Alan Turing, had frequent conversations with John Von Neumann, and had lunch with Albert Einstein.

R.I.P.

martedì 9 dicembre 2014

Frame language: the knowledge based computer aided design (KBCAD) example (part 2)

To obtain the graphics rendering we have seen in Fig. 2 of my previous post on KBCAD we need to :

  1. define 2D rendering functions for the prototype frames;
  2. modify the prototype frames' structure;
  3. get a graphics library for Clojure standalone application;

1.  2D rendering functions for the prototype frames

We have 3 metaframes or prototypes:
  • Building units
  • Space units
  • Building elements
The simple code I wrote to graphically  render these prototypes is the following 
Loading ....

The graphical representation of Building and Space units is simply the drawing of the string of their names at the snap points. The stored functions render2dbu and render2dsu, will see very soon how these functions are "stored" and used, do two things:

  • call drawcolostring, we'll see soon its implementation, passing the string to be drawn from the :name slot of f; 
  • invoke the execution of the procedure stored in the slot :render2d and facet :proc of all the components (found in the :cof slot) of f. 
For what concern the 2d rendering of the "be" or building unit prototype, since in our KB we have only walls as building elements, the function render2dbe is a simple function that draws a colored line segments of variable width between the two snap points of each wall.
Note that the render2dbe get color and width from the isa frame of the current frame and obtains the snap points from the current frame.

2.  The prototype frames' structure

To add the rendering capabilities to our KB we need to:

modify the  ako frames "bu", "su" and "be" adding a :render2d slot with a :proc facet containing the rendering function render2dbu, renderd2dsu and render2dbe respectively;
add the slot :color and :width to the isa frame "sw" (structural wall) and populate with (0 0 255) (= blue color in rgb code)  and 10 (the width of a structural wall is set to 10 pixels);
add the slot :color and :width to the isa frame "pw" (structural wall) and populate with (100 100 255) (= light blue color in rgb code)  and 5(the width of a partition wall is set to 5pixels).

Loading ....

3.  Graphics library for Clojure 

Even if there are already many Clojure wrappers for graphics library, I found that a real graphics library in clojure is still missing.
I'm not so presumptuous to start from scratch a real graphics library by myself. Nevertheless, I did my best to write a simple wrapper around Java swing that will eventually grow in a real graphics library. For the moment, only few simple graphics primitive has been implemented and there is a first very spartan draft of a window to viewport transformation .

Loading ....

To play with what we have seen until here and something more that we'll see in future posts you can clone the repo https://github.com/capitancook/clj-fl-examples.git and follow the instruction in the readme.
In the repo you'll find the implementation of some query of the KB to get calculated property of the building frames such as the area.
Hope you'll enjoy playing with this example of the Frame Language library for the Clojure ecosystem.
Comments, opinions and suggestions are greatly appreciated :)

giovedì 4 dicembre 2014

Frame language: the knowledge based computer aided design (KBCAD) example (part 1)

Create a new project with

lein new app kbcad

Modify the project.clj file so that it contains at least the following dependencies:

[clj-fl "0.1.0-prealfa9"]               ;1
[adamclements/vijual "0.3.0-SNAPSHOT"]] ;2

Where, the first dependency is the Frame language library and the second is Vijual, a graph layout engine.

Start the repl in the project directory with:

lein repl

Create a new namespace called clj-fl-e and "require" the necessary namespaces:

(ns clj-fl-e
  (:require  [clj-fl.core :refer :all]
             [vijual :as v]))

This use case,  inspired to this paper "Constraint-bounded design search", is based on the knowledge base (KB) stored in the following gist:

Loading ....

To feed the FL system with the previous KB you can download the gist and load it at th REPL with the following function:

(load-kb-vec "filename")

Or you can load the raw gist in one shot giving the address of the raw gist to the load-kb-vec function:

(load-kb-vec "https://gist.githubusercontent.com/capitancook/da8ff741afa4734dd7b9/raw/d05a4c4db676c295cfc3ed405448373342e4b3c0/kb-kbcad1.clj")

At the beginning of this KB we have the definition of the metaclasses or "ancestor" frames:

;------ AKO frames

{:frame       {:value "bu"}
 :name        {:value "Building Unit"}
 :description {:value "A man-made structure with floors, roofs and walls standing more or

                       less permanently in one place. Can be comprised of other building unit
                       and/or space units"}} 

{:frame       {:value "su"}
 :name        {:value "Space Unit"}
 :description {:value "A space unit is a building unit component. Is composed of building 
                       elements"}}

{:frame       {:value "be"}
 :name        {:value "Building Element"}
 :description {:value "BEs are the physical elements that define the BU and SU. For example,
                      a wall is a BE, a pillar is a BE and so on"}}

Here, a generic building has been modelled with the frame "bu", a building unit, that can be composed of other building unit and/or  "su",space unit, frames.
A "be", building element is any physical element that compose a space unit. For example a perimetral wall, a floor and a pillar are all "be".
Then, we have the definition of the isa frames:

;------ ISA frames

{:frame       {:value "flat"}
 :name        {:value "Flat"}
 :description {:value "A flat"}
 :ako         {:value "bu"}}

{:frame       {:value "room"}
 :name        {:value "Room"}
 :description {:value "A room"}
 :ako         {:value "su"}}

{:frame       {:value "sw"}
 :name        {:value "Structural Wall"}
 :description {:value "A structural wall is schematized as a line thicker than a partition 
                      wall"}
 :ako         {:value "be"}}
{:frame       {:value "pw"}
 :name        {:value "Partition Wall"}
 :description {:value "A partition wall is schematized as a line thinner than a structural 
                      wall"}
 :ako         {:value "be"}}


Here we can see that a "flat" is a "bu", while a "room" is a "su" and a structural wall "sw" and a partition wall "pw" are "be".
Then we have the instances of the isa frames where we can see that our "flat" "flat1" is comprised by the frames "kitchen1", "bathroom1" and "bedroom1". These frames are listed in the :cof, comprised-of, slot of the "flat1" frame.

{:frame {:value "flat1"}
 :name  {:value "Flat 1"}
 :isa   {:value "flat"}
 :cof   {:value ("kitchen1" "bedroom1" "bathroom1")}}


Each space unit is described in terms of the walls that surround the unit and in terms of the building unit that composes.
For example "bedroom1" is comprised of  5 walls ("w5" "w4" "w8" "w7" "w6"), the values of the :cof slot, and compose the "flat1" building unit frame contained in the facet :value of the :isi slot

{:frame {:value "bedroom1"}
 :name  {:value "Bedroom 1"}
 :isa   {:value "room"}
 :cof   {:value ("w5" "w4" "w8" "w7" "w6")}

 :isi   {:value "flat1"}}

The walls are the building elements that physically realise the space units of our knowledge base. There are two kind of walls: perimetral and partition walls. The first is usually thicker and stronger that the latter.
Each wall is defined in terms of the space unit that composes, the :isi slot, and the two snap points, the :sps slot, that define the beginning and the end points of the wall.
The tree diagram of our knowledge base is the following:

Fig. 1 - Tree graph of the KB

At the REPL you can, for example,  query the KB asking what are the snap points of the wall "w1" with the following function:

clj-fl-examples>(fget "w1" :sps :value)
((0 5) (0 0))

But, if you ask the description slot of the same frame you obtain nil. We can try to see if the slot "w1" inherited a slot :description from is :isa or ancestor frame using the following function:

clj-fl-examples>(fget-i "w1" :description :value)
"A structural wall is schematized as a line thicker than a partition wall"

Since "w1" is a "sw" frame,  the system returned the :description slot of the "sw", structural wall, frame.

Let's add some spices to this example.

FL supports the use of stored function (SF).  They are normal Clojure functions that can exploit all the power of the FL and can be activated both directly that indirectly. The former are stored function that can be invoked directly by the user of the KB while the latter are indirectly activated when certains triggers are fired. A simple function showcofs that extracts the tree graph of  the :cof relation for a given frame f and that can be stored in the :shocofs slot of f or in a f's meaframe, is the following:

Loading ....

In 1 the list of the :cof frames is stored in cofslist. In 2, if cofslist is empty, i.e. there are no comprised-of frames of f, f is returned in a vector. In 3, when cofslist is not empty,  step number 2 is "reduced" accumulating the results in a vector of vector. Note that in the generic reducing step, showproc is initialized to (fget-ii currentframe :showcofs :proc). This means that we can have different function stored in different metaframe and that the user doesn't need to know about the function showcofs. In fact, the user can invoke the extraction of the tree graph using:

((eval (fget-ii "flat1" :showcofs :proc)) "flat1")

To test what we have done up to this point you can copy&paste the showcofs function from the above box to the REPL and load the KB kb-kbcad2.clj that contains a modified version of kb-kbcad1.clj with the addition of a :showcofs slot in the metaframes "bu", "su" and "be". To load the new KB copy&paste the following function at the REPL:

(load-kb-vec "https://gist.githubusercontent.com/capitancook/ec3839d32b4d4d33b636/raw/b384ffe5c7e9b781923d3ff87f6bd53152966a5a/kb-kbcad2.clj")

Now, if you type at the REPL

((eval (fget-ii "flat1" :showcofs :proc)) "flat1")

you'll obtain the following representation of the graph tree of the :cof relation in our KB:

["flat1" ["kitchen1" ["w1"] ["w2"] ["w3"] ["w4"]] ["bedroom1" ["w5"] ["w4"] ["w8"] ["w7"] ["w6"]] ["bathroom1" ["w3"] ["w10"] ["w9"] ["w8"]]]

To have more information about this particular format used to represent graphs by means of vectors structure, please go to the lisperati web site.
Anyway, pretty-printing the last result you can easily recognize the tree structure of the result:

(clojure.pprint/pprint *1)
["flat1"
 ["kitchen1" ["w1"] ["w2"] ["w3"] ["w4"]]
 ["bedroom1" ["w5"] ["w4"] ["w8"] ["w7"] ["w6"]]
 ["bathroom1" ["w3"] ["w10"] ["w9"] ["w8"]]]

And you can see a cute ascii art layout of the graph tree typing the following function:

(v/draw-tree *1)

We have already seen the result of this function in the above  Fig.1.

Ascii art is cute but a CAD should be able to graphically render a design like the one in Fig. 2

Fig. 2 - 2d rendering of the "bu" frame "flat1"
Graphic rendering and more on FL stored procedure in the next post.

Hope you enjoyed today's post!Thanks for reading.

mercoledì 19 novembre 2014

Clj-fl is out!

After a lot of fun I had playing with the Frame Language, I decided to put together all the toys I've built in a Clojure library.
Clj-fl is my first Clojure library. It is on github and clojars.

Examples

The repo on github includes two simple knowledge bases as examples you can play with.
Assuming you have Leiningen installed, start a REPL in the example directory with:

lein repl

Then, at the repl prompt, type

(showorgalfa)

to load the OrgAlfa use case, where the frame language is used to model a simple knowledge based ERP. The OrgAlfa  is a hierarchical organisation similar to the European Commission structure.

Or you can type:

(showkbcad)

to load the kbcad use case, a simple knowledge based Computer Aided Design system.

After each of the previous command/function you can play around with the KB you loaded.

Using it

Please note that clj-fl is pre-alpha software!
Even if this library is still not ready for production, to use it, assuming you have Leiningen installed, your project.clj should include something like the following:

(defproject foo "0.1.0-SNAPSHOT"
  ;...
  :dependencies [[org.clojure/clojure "1.6.1"]
                 [clj-fl "0.1.0-prealfa5"] 
; please check on Clojars.org for the latest version
                 ...]
  ;...
  )

venerdì 6 giugno 2014

Frame language in Clojure (part 2)

Prof. Patrick Winston 

As we saw in the previous post  on Frame Language (FL), frames are not only nested associative data structures. but extend the power of a property list adding more sophisticated mechanisms as:
  • default values;
  • demons;
  • inheritance.

Default values

Default value are very useful when you don't have an information (i.e. a slot in FL) about a certain object, but it is somehow known a default value that can be used. 
It is 8:00 a.m and Bob, a freshly recruited emplyee, have to start his first day of work at our organisation. We need to create a new frame for Bob while we don't know yet what will be is role in the organization (that is the :is-a slot). In this case we could leverage the default mechanism and describe Bob as follows:

(def Bob {:is-a {:default 'employee}
          :working-at {:value 'unit-iii} 
          :recruitment-date {:value "20140307"}})

In this way, Bob can get his badge and pass through the security check to start his first day of work.
Since the :value facet is not present in Bob's frame, all the queries on Bob's role, like fget(Bob :is-a :value), would fail. The following function fget-v-d exploit the :default facet to give an answer even in the case the only information we have is the default information:

(defn fget-v-d [frame slot]
  (let [v (fget frame slot :value)]; check if there is a :value facet
    (if v v (fget frame slot :default)))); if not, get :default facet

Now, we can ask our KB about Bob role with (fget-v-d Bob :is-a) and we'll discover that Bob is an employee :).

At 9:00 a.m. when the competent department has established that Bob will work as accountant in the unit-iii, the :default facet into the :is-a slot can be removed and a new :value facet will be added to the :is-a slot. Then, the frame for Bob will be:

{:is-a             {:value 'accountant}
 :working-at       {:value 'unit-iii} 
 :recruitment-date {:value "20140307"}}

After 9:00 a.m. all the queries on Bob's role made with the same function  fget-v-d will give the updated answer (i.e. accountant).

Demons

Demons are functions stored in special facets attached to slots to cause side effects when the slot is accessed. For example, we can have:
  • :range : demons are triggered if a new value is added to the slot, to check that the value added is permissible for this particular slot;
  • :if-new : demons are triggered when a new frame is created;
  • :if-added : demons are triggered when a new value is put into a slot;
  • :if-removed : demons are triggered when a value is removed from a slot;
  • :if-replaced : is triggered when a slot value is replaced.
  • :if-needed : demons are triggered when there is no value present in an instance frame and a value must be computed from a generic frame.
Each demon must follow a certain set of rule to guarantee the robustness and coherence of the Knowledge Base (KB).
A possible general rule is that every demon must accept only two parameters: the frame end the slot that caused its activation. Another rule , this time specific, may be that  :if-needed demons must compute the missing value and, before  return the results of its computation, store it in the facet :value of the frame and slot where it was missing.

Going back to our new employee Bob at his first day of work in our organization, let see an example of :range demon that allows the memorization of a recruitment date only if it is not greater than today:

(defn check-date [frame slot]
   (let [date (fget frame slot :value)]
      (if (after? (parse basic-formatter date ) (now))
         (do
            (alert "Future date are not allowed for the slot" slot " of the frame " frame)
            (fremove frame slot :value))
      nil))

**Note that after? and parse functions are part of the clj-time library.
To store this demon in Bob's frame we can use fput:

(fput Bob :recruitment-date :range 'chek-date)

Since check-date must be activated every time a value is put into the slot :recruitment-date we need a modified version of fput that activate the :range and :if-added demon as soon as it adds a new value for the :recruitment-date slot.
Here come the fput-p function:

(defn fput-p
  [frame slot facet v]
  (assoc-in frame [slot facet] v)  ; "standard" fput
  (if ((fget frame slot :range) frame slot) ; call :range demon
     nil
     ((fget frame slot :if-added) frame slot))) ; call :if-added demon


Inheritance

One of the first requirements that FL was designed to satisfy was multiple inheritance. This was a natural consequence of the desire to model the world the way humans do. In fact, human conceptualizations of the world seldom fall into rigidly defined non-overlapping taxonomies. 
There are two different kind of inheritance: a-kind-of (ako) and is-a (isa) inheritance. The former is a relation between two classes of object (e.g., accountant is a-kind-of employee). While, the latter is a relation between an object and its class (e.g., Bob is-a accountant). Here, in both cases, multiple inheritance is welcome.
Our good friend Bob is at his first day of work and, after all the rumor he has heard about it, he is happy to be finally able to know how much could be the real yearly bonus he can get if he is is a "good" accountant. So, he open his home page on the organization Intranet and discover that the yearly bonus for him is 3000.00 $. Not bad!
Let see how this has been made possible by the inheritance mechanism of the FL. All starts storing the bonus information for accountants in the "abstract" frame accountant:

(def accountant {:ako {:value 'employee}
                 :bonus {:value 3000.00}})

Then we need a modified version of fget that is able to look for a certain facet in all the class frames Bob is an instance of. 
The following fget-i function can do this job quite well:

(defn fget-i [frame slot]
  (if-let [classes (fget frame :isa :value)]
    (if (not(list? classes)) 
       (fget (eval classes) slot :value) 
       (fget-i1 classes slot))
    nil))
(defn fget-i1[frames slot]
   (if (nil? frames)
       nil
       (if-let [value (fget (eval (first frames)) slot :value)]
          value
          (recur (next frames) slot))))
 Note that:
  • fget-i examines only one level of inheritance. This means that (fget-i Bob :bonus) look for the :bonus slot only in the class accountant and don't even try to get it from the employee superclass.
  • in case of multiple inheritance fget-i give stop examining the "mather" class as soon as it gets a non value from one class.
In this gist you'll find all the code I translated in Clojure from chap. 22 of the great book "Lisp" by Prof. Henry Patrick Winston.

Please feel free to comment and suggest improvements.

mercoledì 4 giugno 2014

Frame Language in Clojure (part 1)

Prof. Marvin Minsky
Frames and Frame Language (FL) are components of a framework used in the seventies to represent chunks of knowledge, see Prof. Marvin Minsky seminal paper "A framework for representing knowledge". The first implementations of FL were based on Lisp. The interest about FL survived to all the "fashions of the moment" of the last four decades of AI research. It is actively used in knowledge representation for semantic Web. And, even Clojure has been surely influenced by this paradigm.

Prof. Winston, in his great book  "Lisp", introduced a simple and clear  Lisp formalization of the Frame Language by means of which we could represent knowledge about Henry, a man working at the Unit-I of a certain organization as a System analyst, as follows:

(setf (get 'Henry 'is-a) 'system-analyst)
(setf (get 'Henry 'working-at) 'unit-i)
(setf (get 'Henry 'recruitment-date) "14/03/2010")
(setf (get 'Henry 'gross-salary) 2500,00)

Ok. Nice. But what is a Frame?
Lets have a look at the implementation of a Frame as proposed by Prof. Winston as a simple associative nested  list in LISP:

(Henry (is-a (value system-analyst))
       (working-at(value unit-i ))
       (recruitment-date (value "14/03/2010"))
       (gross-salary (value 3000,00)))

Probably, many Clojurians are now thinking: “Hey! Came on! We can do that using  associative maps. At the end, these Frames are only property lists”.
That’s not wrong. For example, our old fellow Henry can be described using a nested associative map as follows:

(def Henry {:is-a {:value 'system-analyst} 
            :working-at {:value 'unit-i} 
            :recruitment-date {:value "14/03/2010"} 
            :gross-salary {:value 3000,00}})

Please, note that system-analyst is itself a frame containing the FL description of a generic employee that works as a system analyst and, for example, has a certain base salary, health insurance, production bonus and other benefits.

To get Henry’s salary we can simply do:

(-> Henry :gross-salary :value)

But, hold on. Frames are not only associative data structures. For example, if we have another person named John that, at the time we are writing his description in FL, has an unknown salary:

(def John {:is-a {:value 'system-analyst}
           :working-at {:value 'unit-i} 
           :years-in-the-role {:value 5}})

If we try to use the same approach we used for Henry to get the salary information from the John's FL description we'll fail miserably.
We could estimate John's base salary using some general knowledge about the base salary of a System Analyst with 5 years of experience in the role of system-analyst.

If we can get elsewhere what was the average salary for a system analyst, for example 2000,00 EURO, and if it is known that the annual increment is 3%, we could calculate John's base salary as follows:

gross-salary = system-analyst-salary*(1+0,03)^(years-in-the-role) 

And, if we could store somewhere the above formula, when we wont to know John's wage we could, because John :isa 'system-analyst , adopt the the previous formula to estimate his basic wage.
In this case the simple property list we used to represent a person's features is not enough. The FL extend the power of a property list adding more sophisticated mechanisms as: default values, demons and inheritance.
We'll see all these mechanisms in this short series of posts but, I suggest you to read this post by Steve Yegge to open your mind on the  generalized property list pattern.
Before to go to the Clojure implementation details, let me introduce some definitions:

  • A frame is a nested "augmented"  association list;
  • A frame can represent a class of objects or an object; in our example system-analyst is a frame representing a class of employees while Henry frame is representing an instance of system-analyst;
  • A frame is described/composed by one or more facts called slot;  in our example :net-monthly-salary is a slot;
  • A slot is described/composed by one or more information called facet; in our example :value is a facet.

Prof. Winston introduced several function to deal with frames in Lisp, the three basic functions, working on the frames as a simple  nested property list, were:
  • fget: fetches information. The user supplies an access path consisting of a frame, a slot, and a facet .
  • fput:  places information. As with fget the user supplies a frame-slot-facet access path.
  • fremove: removes information. As with fget and fput , the user supplies a frame-slot-facet access path.
The Clojure implementation of these three functions is straightforward:

Loading ....

In the next post I'd like to see how the Frame language paradigm extends the power of a property list adding more sophisticated mechanisms as: default values, daemons and inheritance.