#+TITLE: Tar Pit
#+PROPERTY: header-args :mkdirp yes

* Out of the Tar Pit in Clojure

Bare minimum functional relational architecture in Clojure.

* Architecture
** Essential State

This component consists solely of a specification of the essential state for the
system in terms of base relvars (in FRP all state is stored solely in terms of
relations — there are no exceptions to this). Specifically it is
the names and types of the base relvars that are specified here, not their
actual contents. The contents of the relvars (i.e. the relations themselves) will
of course be crucial when the system is used, but here we are discussing
only the static structure of the system.

FRP strongly encourages that data be treated as essential state only when it has
been input directly by a user.

 1. some means of storing and retrieving data in the form of relations assigned to named relvars
 2. a state manipulation language which allows the stored relvars to be updated (within the bounds of the integrity constraints)
 3. optionally (depending on the exact range of FRP systems which the infrastructure is intended to support) secondary (e.g. disk-based) storage in addition to the primary (in memory) storage
 4. a base set of generally useful types (typically integer, boolean, string, date etc)

An example definition of essential state in an imagined FRP infrastructure, as given in Out of the Tar Pit, is as follows.

#+BEGIN_EXAMPLE
def relvar Offer :: {address: address
                     offerPrice: price
                     offerDate: date
                     bidderName: name
                     bidderAddress: address}
#+END_EXAMPLE

** Distinction between Relvar and Relation

Operations on Relvars return other Relvars ("Derived" Relvars).

Relations are a collection of elements.

The idea behind FRP is that you shouldn't need to do operations on collections of elements. That's accidental logic. So, while you could think of relations as "sets" in the sense that they are collections of unique attr/value pairs, you'll never be wanting to use Clojure's set functions on them. Instead, use the relational algebra functions on the Relvars to give you a derived relvar that you can then access the relation of.

One thing that is missing from the above code snippet is part of requirement \#2, "... (within the bounds of the integrity constraints)". We'll get to that as part of the Essential Logic.

Let's start by imagining a nice syntax for this.

** Example relvar definitions

#+NAME: real estate example relvar definitions
#+BEGIN_SRC clojure :noweb no-export :tangle ../../../../example/real_estate.clj
(ns example.real-estate
  (:require [com.owoga.frp.infrastructure :as frp]))

(frp/defrelvar Offer
  #(string? (:address %))
  #(number? (:offer-price %))
  #(inst? (:offer-date %))
  #(string? (:bidder-name %))
  #(string? (:bidder-address %)))

(frp/defrelvar Property
  #(string? (:address %))
  #(number? (:price %))
  #(string? (:photo %))
  #(string? (:agent-name %))
  #(inst? (:date-registered %)))
#+END_SRC

** Creating RelVars
This way the relvar and constraints can't easily be evaluated in seperate parts
of the code that might allow relations that violate soon-to-be constraints to be
loaded

#+NAME: defrelvar
#+BEGIN_SRC clojure :noweb no-export
(defmacro defrelvar
  [relvar-name & constraints]
  `(->BaseRelVar '~relvar-name (atom #{}) [~@constraints]))
#+END_SRC

** Definining derived and base relvars

BaseRelVars will have a protocol for loading/deleting/updating elements in the relation.

Both BaseRelVars and RelVars (a.k.a. DerivedRelVars) will have a protocol for relational algebra.

Both types of relvars can be derefed to access the collection of relations.

#+NAME: base relvars
#+BEGIN_SRC clojure
(deftype BaseRelVar [relvar-name store constraints]
  PRelVar
  <<relational algebra>>

  PRelations
  <<relations data manipulation>>

  clojure.lang.IDeref
  (deref [_] @store))
#+END_SRC

#+NAME: relvar protocol
#+BEGIN_SRC clojure
(defprotocol PRelVar
  (extend [this extensions & constraints])
  (restrict [this criteria & constraints])
  (project [this attributes & constraints])
  (product [this relvar & constraints])
  (union [this relvar & constraints])
  (intersection [this relvar & contstraints])
  (difference [this relvar & constraints])
  (join [this relvar & constraints])
  (divide [this relvar & constraints])
  (rename [this renames & constraints]))
#+END_SRC

#+NAME: relations protocol
#+BEGIN_SRC clojure
(defprotocol PRelations
  (load! [this relations])
  (insert!
    [this relation]
    [this & relations])
  (delete! [this & relations])
  (update! [this old-relation new-relation])
  (clear! [this]))
#+END_SRC

The algebraic manipulations of derived relvars are stored as a transform function that is transduced when the relvar is derefed.

#+NAME: derived relvars
#+BEGIN_SRC clojure
(deftype RelVar [relvar xf constraints]
  PRelVar
  <<relational algebra>>

  clojure.lang.IDeref
  (deref [_] (into #{} xf @relvar)))
#+END_SRC

Let's define something simple to test what we have so far.

#+NAME: relations data manipulation
#+BEGIN_SRC clojure
(load! [this relations])
#+END_SRC

#+NAME: test defrelvar
#+BEGIN_SRC clojure
(deftest test-defrelvar
  (testing "failed constraint raises"
    (let [Offer (frp/defrelvar Offer (fn [offers] (map #(> (:price %) 0) offers)))]
      (is (thrown-with-msg?
           Exception
           #"Constraint Exception"
           (frp/insert! Offer {:price -1})))))
  (testing "passed constraint doesn't raise"
    (let [Offer (frp/defrelvar Offer (fn [offers] (map #(> (:price %) 0) offers)))]
      (frp/insert! Offer {:price 20})
      (is (= @Offer #{{:price 20}})))))
#+END_SRC

** Relvar protocols

The PRelVar functions return a RelVar that is not data-modifiable - it doesn't
have the load!, insert!, delete!, etc... functions.

For performance reasons, we do still need a way to persist derived relvars
somewhere. We'll eventually want to define some type of semantics for specifying
that a derived relation be cached rather than requiring it to be recalculated
every time the relations of its base relvar are updated.

#+NAME: relvar protocols
#+BEGIN_SRC clojure :noweb no-export
(defprotocol PRelVar
  (extend [this extensions & constraints])
  (restrict [this criteria & constraints])
  (project [this attributes & constraints])
  (product [this relvar & constraints])
  (union [this relvar & constraints])
  (intersection [this relvar & contstraints])
  (difference [this relvar & constraints])
  (join [this relvar & constraints])
  (divide [this relvar & constraints])
  (rename [this renames & constraints]))

(defprotocol PRelations
  (load! [this relations])
  (insert!
    [this relation]
    [this & relations])
  (delete! [this & relations])
  (update! [this old-relation new-relation])
  (clear! [this]))
#+END_SRC

** Part 1. of Infrastructure for Essential State

The =project= function of a relvar will be returning another relvar. The
implementation might look something like this:

#+BEGIN_SRC clojure
(deftype DerivedRelvar [relvar xf]
  PRelVar
  (project [this attributes] (->DerivedRelvar this (map #(select-keys % attributes)))))
#+END_SRC

I noticed though that an implementation can't refer to the type that it's
defined in. =->DerivedRelvar= isn't yet defined when you try to use it inside
that =project= function.

A workaround I'm using is to declare a =project-= function before the =deftype=
and use that declared function in the implementation. Then implement the
aforementioned declared function after the deftype.

Clojure is still fairly new to me. I'm curious if this "makes sense" as a way of
implementing these types/functions.

=RelVar= will implement =IDeref= which will be a way to access the relation associated with the =RelVar=.

#+NAME: relvar implementations
#+BEGIN_SRC clojure :noweb yes
(declare extend-)
(declare project-)
(declare restrict-)

(deftype RelVar [relvar xf constraints]
  PRelVar
  <<relational algebra for derived relvars>>

  clojure.lang.IDeref
  (deref [_] (into #{} xf @relvar)))

(deftype BaseRelVar [relvar-name store constraints]
  PRelVar
  <<relational algebra for base relvars>>

  PRelations
  <<relations manipulations>>

  clojure.lang.IDeref
  (deref [_] @store))

(defn extend- [relvar extensions constraints]
  (let [xf (map (fn [element]
                  (map (fn [[k f]]
                         (assoc element k (f element)))
                       extensions)))]
    (->RelVar relvar xf constraints)))

(defn project- [relvar attributes constraints]
  (->RelVar relvar (map #(select-keys % attributes)) constraints))

(defn restrict- [relvar criteria constraints]
  (->RelVar relvar (filter criteria) constraints))

<<constraints>>
#+END_SRC

Extend a relvar with an additional key.

#+NAME: extend
#+BEGIN_SRC clojure
(defn extend- [relvar extensions constraints]
  (let [xf (map (fn [element]
                  (map (fn [[k f]]
                         (assoc element k (f element)))
                       extensions)))]
    (->RelVar relvar xf constraints)))
#+END_SRC

#+NAME: test extend
#+BEGIN_SRC clojure
(deftest test-extend
  (testing "extend-"
    (let [Offer (frp/->BaseRelVar 'Offer (atom #{}) '())]
      (frp/load! Offer #{{:price 1e6}})
      (frp/extend- Offer [:price-band (fn [e] (if (> (:price e) 1e6) :high :low))])
      (is (= :low (-> @Offer first :price-band))))))
#+END_SRC

Clojure's core set library includes a =project= function, but I'm not sure if
it returns a transducer. I'll mark that as a todo. Look into whether this
map/select-keys can be replaced by =set/project=.

#+NAME: relational algebra for derived relvars
#+BEGIN_SRC clojure
(extend
 [this extensions & constraints]
 (extend- this extensions constraints))
(project
 [this attributes & constraints]
 (project- this attributes constraints))
(restrict
 [this criteria & constraints]
 (restrict- this criteria constraints))
#+END_SRC

#+NAME: relational algebra for base relvars
#+BEGIN_SRC clojure
(extend
 [this extensions & constraints]
 (extend- this extensions constraints))
(project
 [this attributes & constraints]
 (project- this attributes constraints))
(restrict
 [this criteria & constraints]
 (restrict- this criteria constraints))
#+END_SRC

#+NAME: relations manipulations
#+BEGIN_SRC clojure
(load! [this relations] (reset! store relations))
(insert!
 [this relation]
 (let [new-relation (conj @store relation)]
   (run!
    (fn [constraint]
      (when (not (every? true? (constraint new-relation)))
        (throw (ex-info "Constraint Exception" {}))))
    constraints)
   (reset! store new-relation)))
(insert!
 [this & relations]
 (let [new-relation (set/union @store (into #{} relations))]
   (run!
    (fn [constraint]
      (when (not (every? true? (constraint new-relation)))
        (throw (ex-info "Constraint Exception" {}))))
    constraints)
   (reset! store new-relation)))
#+END_SRC

** Relvar infrastructure

#+BEGIN_SRC clojure :noweb no-export :tangle ../frp/infrastructure.clj
(ns com.owoga.frp.infrastructure
  (:require [clojure.set :as set])
  (:refer-clojure :exclude [extend]))

<<relvar protocols>>
<<relvar implementations>>
#+END_SRC

#+BEGIN_SRC clojure :results pp
(ns example
  (:require [com.owoga.frp.infrastructure :refer [->BaseRelVar project load!]]))

(def Offer (->BaseRelVar 'Offer (atom #{}) '()))
(def OfferPrices (project Offer [:price]))

(load! Offer #{{:address "123 Fake St." :price 2e5}})
(assert (= #{{:price 2e5}} @OfferPrices))
(print @OfferPrices)
#+END_SRC

#+RESULTS:
: #{{:price 200000.0}}
:

** Part 2. of Infrastructure for Essential State

The code above covers requirement 1. from the infrastructure for essential state; namely:

1. some means of storing and retrieving data in the form of relations assigned to named relvars

Now we can load!, insert!, project and restrict. We'll get to adding some other functionality later. Let's explore something more complex: constraints.

This is requirement 2.

2. a state manipulation language which allows the stored relvars to be updated (within the bounds of the integrity constraints)

Instead of definining a RelVar type direcly, like we've done in the examples
above, we can define it inside a macro that handles creating constraints for us.
This way the relvar and constraints can't easily be evaluated in seperate parts
of the code that might allow relations that violate soon-to-be constraints to be
loaded

#+NAME: constraints
#+BEGIN_SRC clojure :noweb no-export
(def *constraints* (atom {}))

(defmacro defrelvar
  [relvar-name & constraints]
  (swap! *constraints* assoc-in [relvar-name :constraints] constraints)
  `(->BaseRelVar '~relvar-name (atom #{}) [~@constraints]))
#+END_SRC

#+NAME: test defrelvar
#+BEGIN_SRC clojure
(deftest test-defrelvar
  (testing "failed constraint raises"
    (let [Offer (frp/defrelvar Offer (fn [offers] (map #(> (:price %) 0) offers)))]
      (is (thrown-with-msg?
           Exception
           #"Constraint Exception"
           (frp/insert! Offer {:price -1})))))
  (testing "passed constraint doesn't raise"
    (let [Offer (frp/defrelvar Offer (fn [offers] (map #(> (:price %) 0) offers)))]
      (frp/insert! Offer {:price 20})
      (is (= @Offer #{{:price 20}})))))
#+END_SRC

#+NAME: namespace and requires
#+BEGIN_SRC clojure :noweb no-export
(ns com.owoga.prhyme.tar-pit
  (require '[clojure.spec.alpha :as s]
           <<requires>>))
#+END_SRC

#+NAME: primatives
#+BEGIN_SRC clojure
(s/def ::address string?)
(s/def ::agent string?)
(s/def ::price number?)
(s/def ::date inst?)
(s/def ::date-registered inst?)
(s/def ::bidder-name string?)
(s/def ::bidder-address string?)
(s/def ::room-name string?)
(s/def ::width number?)
(s/def ::breadth number?)
(s/def ::room-type #{:bed :bath})
(s/def ::area-code #{:local :non-local})
(s/def ::price-band #{:low :high})
#+END_SRC

** Essential Logic

Restrict is a unary operation which allows the selection of a subset of therecords in a relation according to some desired criteria

Project is a unary operation which creates a new relation corresponding to the old relation with various attributes removed from the records

Product is a binary operation corresponding to the cartesian product of mathematics

Union is a binary operation which creates a relation consisting of all records in either argument relation

Intersection is a binary operation which creates a relation consisting of all records in both argument relations

Difference is a binary operation which creates a relation consisting of all records in the first but not the second argument relation

Join is a binary operation which constructs all possible records that result from matching identical attributes of the records of the argument relations

Divide is a ternary operation which returns all records of the first argument which occur in the second argument associated with each record of the third argument
http://users.abo.fi/soini/divisionEnglish.pdf

** Accidental state and control

A declarative specification of a set of performance optimizations for the system.

** Other

A specification of the required interfaces to the outside world.

* Essential Logic

Derived relvar names and definitions.

Integrity constraints.

Infrastructure for Essential Logic

1. a means to evaluate relational expressions
2. a base set of generally useful functions (for things such as basic arithmetic etc)
3. a language to allow specification (and evaluation) of the user-defined functions in the FRP system.  (It does not have to be a functional language, but the infrastructure must only allow it to be used in a  functional way)
4. optionally a means of type inference (this will also require a mechanism for declaring the types of the user-defined functions in the FRP system)
5. a means to express and enforce integrity constraints

#+BEGIN_EXAMPLE
PropertyInfo = extend(Property,
                      (priceBand = priceBandForPrice(price)),
                      (areaCode = areaCodeForAddress(address)),
                      (numberOfRooms = count(restrict(RoomInfo |address == address))),
                      (squareFeet = sum(roomSize, restrict(RoomInfo |address == address))))
#+END_EXAMPLE

#+BEGIN_SRC clojure :eval no
(frp/defrelvar Property
  (fn [properties] (map #(number? (:price %)) properties))
  (fn [properties] (map #(string? (:address %) properties))))

(frp/extend Property
  [:price-band price-band-for-price])

(defn price-band-for-price [property]
  (if (> (:price property) 1e6) :high :low))

(defn area-code-for-address [address]
  (if (re-matches #"(?i).*louisiana.*" address) :local :non-local))


(def room-info-relvar (atom #{}))
(add-watch
 room-relvar
 :room-info
 (fn [key ref old-state new-state]
   (reset! room-info-relvar
           (into #{}
                 (map #(into % {:room-size (* (:width %) (:breadth %))})
                      new-state)))))

(def property-info-relvar (atom #{}))

(add-watch
 property-relvar
 :property-info
 (fn [key ref old-state new-state]
   (reset! property-info-relvar!
           (into #{} (map #(into % {:price-band (price-band-for-price (:price %))
                                    :area-code (area-code-for-address (:address %))
                                    :number-of-rooms (count (filter
                                                             (fn [room-info] (= (:address %) (:address room-info)))
                                                             @room-info-relvar))
                                    :square-feet (->> (filter (fn [room-info] (= (:address %) (:address room-info))) @room-info-relvar)
                                                      (map (fn [room-info] (* (:width room-info) (:breadth room-info))))
                                                      (apply +))})
                          new-state)))))
#+END_SRC

#+BEGIN_SRC clojure
(defn extend
  "Extend a relvar with new attributes.
  The exensions will be functions that receive a relation element as the first argument"
  [relvar & extensions]
  (map (fn [element#]
         (map (fn [extension#]
                (let [k (first extension#)
                      f (list
                         (first (rest extension#))
                         element#
                         (rest extension))
                      f (first (rest extension#))
                      r (rest (rest extension#))
                      fun (list f element# r)]
                  (into element (extension# element#))))))))
#+END_SRC

When thinking about how to implement the derived relation above, it will help to think about how it will be used.

Output from relvars (base and derived) comes from Observers.

* Observers

Observers are components which generate output in response to changes which they observe in the values of the (derived) relvars. At a minimum, observers will only need to specify the name of the relvar which they wish to observe. The infrastructure which runs the system will ensure that the observer is invoked (with the new relation value) whenever it changes. In this way observers act both as what are sometimes called live-queries and also as triggers.

Despite this the intention is not for observers to be used as a substitute for true integrity constraints. Specifically, hybrid feeders/observers should not act as triggers which directly update the essential state (this would by definition be creating derived and hence accidental state). The only (occasional) exceptions to this should be of the ease of expression kind discussed in sections 7.2.2 and 7.3.1

#+BEGIN_SRC clojure :eval no
(add-watch
 property-info-relvar
 :observe-property-info
 (fn [key ref old-state new-state]
   (pprint new-state)))
#+END_SRC

* Tests

#+BEGIN_SRC clojure :noweb yes :tangle ../../../../test/com/owoga/frp/infrastructure-test.clj
(ns com.owoga.frp.infrastructure-test
  (:require [com.owoga.frp.infrastructure :as frp]
            [clojure.test :refer [deftest is testing]]))

(deftest test-project
  (testing "projection"
    (let [Offer (frp/->BaseRelVar 'Offer (atom #{}) '())
          OfferPrices (frp/project Offer [:price])]
      (frp/load! Offer #{{:address "123 Fake St." :price 2e5}})
      (is (= @OfferPrices #{{:price 2e5}})))))

(deftest test-insert!
  (testing "insert!"
    (let [Offer (frp/->BaseRelVar 'Offer (atom #{}) '())]
      (frp/insert! Offer {:address "123 Fake St." :price 1.5e5})
      (is (= @Offer #{{:address "123 Fake St." :price 1.5e5}})))))

<<test defrelvar>>

<<test extend>>
#+END_SRC
