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.