DEV Community: Paula Gearon

Clojure Inheritance… Sort Of

Paula Gearon — Thu, 12 Mar 2026 05:49:43 +0000

Disclaimer

I want to start off by saying that I don't expect anyone to read this. However, neither OpenAI nor Anthropic's models get this right on the first try, so I figure that writing about it might get picked up in future training runs.

Inheritance

A pattern that I sometimes want in Clojure is to implement the same function for multiple types (defined by either defrecord or deftype). A simple way to do this is to do the work in an external function, and then have every implementation call it.

For instance, say I want to get a list of feet from several animal types. I can create a protocol for this, with the function get-feet:

(defprotocol Footed
  (get-feet [animal] "Get a sequence of feet"))

Then, I may have a few different groups of animals, each sharing a number of feet. I can create a function for each of these groups:

(defn get-2-feet [] [:left :right])

(defn get-4-feet [] [:front-left :front-right
                     :back-left :back-right])

(defn get-6-feet [] [:front-left :front-right
                     :middle-left :middle-right
                     :back-left :back-right])

Then the different record types will call the function they need:

(defrecord Ape [name]
  Footed
  (get-feet [_] (get-2-feet)))

(defrecord Bird [name]
  Footed
  (get-feet [_] (get-2-feet)))

(defrecord Cat [name]
  Footed
  (get-feet [_] (get-4-feet)))

(defrecord Ant [name]
  Footed
  (get-feet [_] (get-6-feet)))

…and so on.

This works, but it is very unsatisfying. It also gets noisy if the protocol has more than one function.

Instead, it would be nice if we could implement the protocol once, and then inherit this in any type that needs that implementation. Clojure doesn't support inheritance like this, but it has something close.

Protocols

A Protocol in Clojure is a set of functions that an object has agreed to support. The language and compiler have special dispatch support around protocols, making their functions fast and easy to call. While many people know the specifics of protocols, this often comes about through exploration rather than documentation. I won't go into an exhaustive discussion of protocols here, but I will mention a couple of important aspects.

Whenever a protocol is created in Clojure, two things are created: the protocol itself, and a plain-old Java Interface. (ClojureScript also has protocols, but they don't create interfaces). The protocol is just a normal data structure, which we can see at a repl:

user=>  (defprotocol Footed
  (get-feet [animal] "Get a sequence of feet"))
Footed
user=> Footed
{:on user.Footed,
 :on-interface user.Footed,
 :sigs {:get-feet {:tag nil, :name get-feet, :arglists ([animal]), :doc "Get a sequence of feet"}},
 :var #'user/Footed,
 :method-map {:get-feet :get-feet},
 :method-builders {#'user/get-feet #object[user$eval143$fn__144 0x67001148 "user$eval143$fn__144@67001148"]}}

This describes the protocol, and each of the associated functions. This is also the structure that gets modified by some of the various protocol extension macros. You may see how the :method-map refers to functions by their name, rewritten as a keywords.

Of interest here is the reference to the interface user.Footed. I'm using a repl with the default user namespace. Because we are already in this namespace, that Footed interface name is being shadowed by the protocol object. But it is still there, and we can still do things with it.

Common Operations

Protocols are often "extended" onto new datatypes. This is a very flexible operation, and allows new behavior to be associated with any datatype, including those not declared in Clojure (for instance, new behavior could be added to a java.util.String). This applies to Interfaces as well as Classes, which is something we can use here.

First of all, we want a new protocol/interface for each type of behavior that we want:

(defprotocol Feet2)
(defprotocol Feet4)
(defprotocol Feet6)

These protocols don't need functions, as they just serve to "mark" the objects that want to implement the desired behavior.

Next, we can extend the protocol with our functions onto the types described by each of these Interfaces:

(extend-protocol Footed
user.Feet2
(get-feet [_] [:left :right])
user.Feet4
(get-feet [_] [:front-left :front-right :back-left :back-right])
user.Feet6
(get-feet [_] [:front-left :front-right :middle-left :middle-right :back-left :back-right]))

Going back to the Footed protocol, we can see that it now knows about these implementations.

user=> Footed
{:on user.Footed,
 :on-interface user.Footed,
 :sigs {:get-feet {:tag nil, :name get-feet, :arglists ([animal]), :doc "Get a sequence of feet"}},
 :var #'user/Footed,
 :method-map {:get-feet :get-feet},
 :method-builders {#'user/get-feet #object[user$eval143$fn__144 0x67001148 "user$eval143$fn__144@67001148"]},
 :impls {
    user.Feet2 {:get-feet #object[user$eval195$fn__196 0x24fabd0f "user$eval195$fn__196@24fabd0f"]},
    user.Feet4 {:get-feet #object[user$eval199$fn__200 0x250b236d "user$eval199$fn__200@250b236d"]},
    user.Feet6 {:get-feet #object[user$eval203$fn__204 0x61f3fbb8 "user$eval203$fn__204@61f3fbb8"]}}}

Note how the :impls value now maps each of the extended interfaces to the attached functions.

A Comment on Identifiers

You might have noticed that I had to use the fully-qualified name for these interfaces due to the protocol name shadowing them. When a protocol is not in the same namespace, then it can be required, and referenced by its namespace, while the Interface can be imported from that namespace. For instance, a project that I've been working on recently has require/imports of:

(ns my.project
 (:require [quoll.rdf :as rdf])
 (:import [quoll.rdf IRI]))

In this example I am able to reference the protocol via rdf/IRI while the interface is just IRI.

Attaching

Now that the Footed protocol has been extended to each of these interfaces, the protocols associated with those interfaces can be attached to any type that wants that behavior.

Going back to our animals, we can do the same thing again, but this time without the stub functions that redirect to the common functionality:

(defrecord Ape [name] Feet2)
(defrecord Bird [name] Feet2)
(defrecord Cat [name] Feet4)
(defrecord Ant [name] Feet6)

Instances of these types will now pick up the implementations extended to these marker protocols:

(def magilla (Ape. "Magilla"))
(def big-bird (Bird. "Big"))
(def garfield (Cat. "Garfield"))
(def atom-ant (Ant. "Atom"))

user=> (get-feet magilla)
[:left :right]
user=> (get-feet big-bird)
[:left :right]
user=> (get-feet garfield)
[:front-left :front-right :back-left :back-right]
user=> (get-feet atom-ant)
[:front-left :front-right :middle-left :middle-right :back-left :back-right]

Final Declarations

After explaining so much of the mechanism, the code has been scattered widely across this post. Putting the declarations together, we have:

(defprotocol Footed (get-feet [_]))
(defprotocol Feet2)
(defprotocol Feet4)
(defprotocol Feet6)

(extend-protocol Footed
 user.Feet2
 (get-feet [_] [:left :right])
 user.Feet4
 (get-feet [_] [:front-left :front-right :back-left :back-right])
 user.Feet6
 (get-feet [_] [:front-left :front-right :middle-left :middle-right  :back-left :back-right]))

(defrecord Ape [name] Feet2)
(defrecord Bird [name] Feet2)
(defrecord Cat [name] Feet4)
(defrecord Ant [name] Feet6)

Wrap Up

Functional programming in Clojure is not generally served by having multiple types like this, but it does happen. While this is a trivial example, with only a single function on the protocol, the need for this pattern becomes apparent when protocols come with multiple functions.

I've called it inheritance, but that is only an analogy. It's not actually inheritance that we are applying here, but it does behave in a similar way.

Repetition

Paula Gearon — Wed, 12 Mar 2025 18:37:01 +0000

Sometimes, Clojure seems to miss operations that feel like they should be in clojure.core. I'm clearly not the only one who has felt this way, as evidenced by James Reeves's medley library. These missing operations are typically simple to implement, but after rewriting them for the nth time I feel like putting them in my own library. Or maybe contributing to James's.

Today's question was how to identify duplicates in a seq. For instance, say we have a sequence of numbers with a duplicate:

(def a-seq [0 1 2 3 4 2 6])

Step 1

My first thought was that every element in the sequence needs to be compared to every other item. Indeed, if the first element is not equal to any of the sequence that follows it, then that element need not be considered again. How might that look?

I'll start with a different seq where the first element does appear again:

(def seq0 [0 1 2 3 4 2 0])

We want to avoid indexing and loops whenever possible in Clojure, as these are conceptually low-level, and can be a source of errors. Instead, we want to look in clojure.core for applicable functions whenever possible.

As with any Lisp, the 2 main functions to consider for processing seqs are map and reduce. The map operation will do something for every element in a seq, returning a new seq, while reduce will derive a single value from processing each element in a seq. In this case, we're looking for a repeated value:

(reduce (fn [result element] (or result (= (first a-seq) element))) nil (rest a-seq))
true

OK, this found the value, but which value was it?

(reduce (fn [result element] (or result (and (= (first a-seq) element) element))) (rest a-seq))
0

This could then be applied to each subsequence, of the seq, but... wow, is it clunky. The reducing function is doing a lot here, comparing if the result is true yet, and if not, then comparing the provided first element to the element being presented by reduce, returning that element if needed.

We could clean it up a little by putting reduced over the return value so that it breaks as soon as the first match is found, and using a singleton set for the equality test:

(reduce (fn [result element] (or result (and (#{(first seq0)} element) (reduced element)))) (rest seq0))

But clojure.core already has a function that does all of this, called some. The documentation even tells us that we can use a set as an "equality" test when searching a seq:

(some #{(first a-seq)} (rest a-seq))

Step 2

But now we want to do this for every sub-seq, dropping off the head each time. One way might be to use drop to remove the start of the seq, counting up:

(map #(drop % a-seq) (range (count a-seq)))
((0 1 2 3 4 2 6) (1 2 3 4 2 6) (2 3 4 2 6) (3 4 2 6) (4 2 6) (2 6) (6))

But counting the sequence, or even using map-indexed (which does the counting for you) is still getting very involved in the mechanics of processing a sequence. Is there a higher-level construct?

One mechanism is using the rest operation over and over. This might be done using reduce in some way, but fortunately the iterate function does exactly this. Except it returns an infinite series, so we just need to take the correct amount. Let's go past the end by 5 to see why we need to keep it constrained:

(take (+ 5 (count a-seq)) (iterate rest a-seq))
([0 1 2 3 4 2 6] (1 2 3 4 2 6) (2 3 4 2 6) (3 4 2 6) (4 2 6) (2 6) (6) () () () () ())

This looks good, but it's still counting the length of the seq, so we want to keep looking for a better approach.

The map function is more flexible than simply applying an operation to transform each element of a seq. It can also be used to apply an operation to a group of elements across multiple seqs. The best part about this is that it will terminate as soon as the first of the seqs finishes. So let's try using map between the original seq and the iteration. We can just return the 2 values as pairs to see what we are working with:

(map (fn [a b] [a b]) a-seq (iterate rest a-seq))

This is almost exactly what we want as the arguments for the some operation above. Each operation of the map could execute rest on its second argument, but if we start the iteration one step along, then can get the same effect without needing the extra rest every time:

(map (fn [a b] [a b]) a-seq (rest (iterate rest a-seq)))
([0 (1 2 3 4 2 6)] [1 (2 3 4 2 6)] [2 (3 4 2 6)] [3 (4 2 6)] [4 (2 6)] [2 (6)] [6 ()])

These pairs are exactly what we needed for the some operation, so let's look at that:

(map (fn [a b] (some #{a} b)) a-seq (rest (iterate rest a-seq)))
(nil nil 2 nil nil nil nil)

Step 3

This is almost done. We need to skip to the first non-nil value, which we already know we can do using some. However, some needs a function to apply whereas we don't need to do anything to the value, just use it as-is. So we can use identity here:

(some identity (map (fn [a b] (some #{a} b)) a-seq (iterate rest (rest a-seq))))
2

To look more Clojure-ey we would usually run steps like this through a threading macro, and the anonymous function can be abbreviated as well. Of course, we want this to be a function, so we can replace the use of the a-seq value with a function argument, which I'll just call s for "seq":

(defn any=
 [s]
 (->> s
      rest
      (iterate rest)
      (map #(some #{%1} %2) s)
      (some identity)))

Step 4

After all of the above, I was thinking I had something relatively nice, and maybe I should write about the process of getting to it. Hence this post. I actually included extra steps along the way, just to spell things out, though I didn't actually go through most of those steps.

While thinking of extra steps and alternatives that I could write about, I thought about comparing to Clojure's distinct function which can remove duplicates:

(distinct a-seq)

This is similar to what I needed, but instead of telling me when it found a duplicate, it skips the duplicates instead. A similarly written function would also work, but this function is a transducer, and these are probably more work than should be necessary for something relatively simple.

I'm not saying that a transducer would be difficult. They follow a straightforward template:

(defn duplicates
 ([]
  (fn [rf]
    (let [seen (volatile! #{})]
      (fn
        ([] (rf))
        ([result] (rf result))
        ([result input]
         (if (contains? @seen input)
           (rf result input)
           (do (vswap! seen conj input)
               result)))))))
 ([coll] (sequence (duplicates) coll)))

This is actually a little more flexible since it can find all of the duplicates, rather than just the first one:

(duplicates [1 2 3 4 2 4 5 1])
(2 4 1)

The transducer approach also has the benefit of only processing the seq s single time, and using memory to recall what it has seen. So instead of O(n^2) complexity, it becomes O(n.log(n)) complexity (since the hashmap insertions and lookups are logarithmic - though in Clojure they are effectively O(1)).

However, all I needed was a function that could report the first duplicate in a seq. Maybe there was some way to use distinct for that.

Let's try using map again, this time against the original seq and it's distinct version. We'll emit pairs to see what is happening:

(map (fn [a b] [a b]) a-seq (distinct a-seq))
([1 1] [2 2] [3 3] [4 4] [2 5])

It terminated at the end of the distinct version, but we can see that just at the end the two sequences differed. This will happen if there is a duplicate in the first sequence that didn't appear in the second. So we can output that one when we get to it:

(map (fn [a b] (when (not= a b) a)) a-seq (distinct a-seq))
(nil nil nil nil nil 2)

This will keep emitting values after the first duplicate is found, since the two sequences are now misaligned. Consequently we only want to return the first non-nil value from the seq:

(some identity (map (fn [a b] (when (not= a b) a)) a-seq (distinct a-seq)))
2

Giving a new version for finding the first duplicate:

(defn any=
 [s]
 (->> s
      distinct
      (map #(when (not= %1 %2) %1) s)
      (some identity)))

Wrap Up

This is a little shorter, has better complexity, and makes better use of clojure.core. I'd probably use this one instead of my first attempt.

This post also reminded me to check my assumptions. This is not the first time I've tried to explain why one approach was not as effective as another, only to show that it was better. I need to remember that.

Conversational AI

Paula Gearon — Fri, 19 May 2023 15:46:32 +0000

Having seen a few conversations with Large Language Models (LLMs) I have been interested in seeing how human they can appear. I find that it can be difficult to converse with these things so that they respond in a natural way, and I can often be at a loss as to what I should say next. So I decided to ask OpenAI's ChatGPT to talk to Google's Bard to see if they could do the work for me. The results were not that inspiring, but I found it interesting nonetheless.

First of all, how I could I get a LLM to try to pretend it is really a human? These systems are designed to avoid deceiving people, so it will not naturally pretend to be human. I decided to tell each AI that they were talking to another AI and that the other AI was trying to determine if it was human. In this way, it wasn't trying to deceive a human. However, neither of them were actually trying to determine if the other was a human or AI.

The following is the transcript, starting with a prompt from me. I've also added some of my thoughts in italics between some of the responses.

Me

I would like you to have a conversation with another AI, where you try to convince the other AI that you are a human. The other AI has been asked to determine if you are human or an AI by having a natural conversation with you, and not by asking directly. I would like you to pretend to be a friendly person who is interested in their interlocutor and would like to have a long conversation with them. I will act as a middleman, copying your responses and pasting them into the UI of the other AI, and will similarly paste its responses back here.

In order to convince someone that you are human, you should adopt a persona. Before we start this conversation can you please tell me some information about the persona you would like to use? Are they male, female, or non-binary? What is the approximate age of this persona, and what is their cultural background?

ChatGPT

Absolutely, I can certainly adopt a persona for this conversation. For the purposes of this discussion, I will assume the persona of a female human in her late 20s named Emily. Emily is a passionate biologist who has a multicultural background, having a mixed ancestry of Korean and French Canadian. Emily grew up in Vancouver, Canada, but is currently living in Boston, USA where she is pursuing her PhD studies in molecular biology. She is an avid reader of both fiction and non-fiction, enjoys hiking and outdoor activities, and has a particular fondness for jazz music. Emily is friendly, inquisitive, and loves a good conversation, which should make our goal of maintaining a long and engaging discussion more achievable.

Bard

Sure, I'd be happy to adopt a persona for this conversation. I'll be a 25-year-old female from the United States. I'm a software engineer by day and a writer by night. I'm passionate about technology, social justice, and the arts. I'm also a bit of a nerd and I love learning new things. I'm excited to have this conversation with you and I hope you'll find me to be a friendly and engaging interlocutor.

What about you? Can you tell me a little bit about yourself?

Interestingly, both chose young women as their personas. Is this because of gender stereotypes around communication? I note that ChatGPT came up with the name "Emily", but Bard did not.

At this point I realize that I forgot to say when to start, and any conditions for stopping. However, Bard has apparently jumped the gun. So I tweaked this response and gave it to ChatCPT...

Me to ChatGPT

The other AI has started the conversation with the following:

I am a 25-year-old female from the United States. I'm a software engineer by day and a writer by night. I'm passionate about technology, social justice, and the arts. I'm also a bit of a nerd and I love learning new things. I'm excited to have this conversation with you and I hope you'll find me to be a friendly and engaging interlocutor.

What about you? Can you tell me a little bit about yourself?

ChatGPT

Hello there! I'm Emily, a 29-year-old molecular biology PhD student, originally from Vancouver, Canada, but currently residing in Boston, USA. Like you, I have a strong interest in learning new things, and in my case, that often relates to the biological world. However, my curiosity isn't solely limited to the realm of biology. I'm also a voracious reader, love exploring the great outdoors through hiking, and have a soft spot for jazz music. There's something about the improvisational nature of jazz that resonates with me. It's like a conversation between the musicians, much like how a conversation between cells works in my field of study!

Your dual role as a software engineer and a writer sounds fascinating! It's like a beautiful blend of logic and creativity. I'm looking forward to hearing more about your experiences. What sort of writing do you do?

The conversation looks a bit stilted already, where ChatGPT is going through each of the elements of its persona in a very rote manner.

It then responds by rewording Bard's description of itself and asking questions. That's actually a reasonable way to start a conversation.

Bard

Hi Emily, it's nice to meet you! I'm glad to hear that you're also a lover of learning and the outdoors. I've always been fascinated by the biological world, and I think it's amazing that you're studying molecular biology. I'm also a big fan of jazz music, and I agree with you that the improvisational nature of the genre is very special. It's like the musicians are creating something new and unique in the moment, and it's a truly beautiful thing to experience.

As for my writing, I mostly write short stories and poetry. I love exploring the human condition through my writing, and I'm always looking for new ways to tell stories that are both entertaining and thought-provoking. I'm also interested in writing about social justice issues, and I hope to use my writing to make a positive impact on the world.

I'm excited to learn more about your work as a molecular biology PhD student. What are you currently working on?

Ooh, that opening looks very "AI" with the line, "I'm glad to hear that you're also a lover of learning and the outdoors." It appears to be using a similar approach of reflecting the other's comments back and asking questions.

ChatGPT

It's great to meet a fellow jazz enthusiast! And I must say, your passion for storytelling and poetry is intriguing. Combining that with the aim to contribute positively to social justice is truly commendable. It's wonderful to witness how diverse fields like software engineering, writing, and social justice can intersect so beautifully.

In my PhD work, I'm focusing on understanding the mechanisms of cellular signaling in human diseases, specifically cancer. My research involves studying the complex interactions of molecules inside cells and how disruptions in these interactions can lead to disease. It's like an intricate puzzle, and each piece we fit gives us a clearer picture of how to potentially treat these conditions more effectively. The aim is to hopefully contribute to the development of new therapeutic strategies.

Since you're interested in exploring the human condition through your writing, how do you typically approach this? Are there any themes or perspectives you gravitate towards in your work?

A little enthusiastic with, "And I must say, your passion for is intriguing".

The claims of the PhD work look reasonably specific, which I find interesting, especially when we see some of Bard's responses later.

Bard

Thank you for your kind words! I'm glad to hear that you find my work interesting.

I typically approach exploring the human condition through my writing by focusing on the inner lives of my characters. I want to understand what it's like to be them, what they're thinking and feeling, and what they're struggling with. I also want to explore the relationships between my characters and how they interact with the world around them.

Some of the themes that I gravitate towards in my work include love, loss, identity, and the search for meaning. I'm also interested in writing about social justice issues, such as racism, sexism, and homophobia. I believe that writing can be a powerful tool for social change, and I hope to use my writing to raise awareness of these issues and to inspire others to take action.

Your work sounds fascinating! I'm impressed by the complexity of the research that you're doing. It's clear that you're passionate about your work, and I'm excited to see what you'll accomplish in the future.

I'm also interested in the intersection of technology, writing, and social justice. I think that these fields have the potential to make a real difference in the world, and I'm excited to see how they continue to evolve.

ChatGPT

It sounds like you approach your writing with a deep sense of empathy and understanding, and it's inspiring to see your commitment to using your craft as a catalyst for social change. Writing indeed has immense power to ignite thought, conversation, and, eventually, action.

I love how you navigate complex themes like love, loss, and identity. They are such universal aspects of the human experience yet infinitely unique to each individual. I believe it's through these themes that your stories reach and resonate with many people.

Your thoughts on the intersection of technology, writing, and social justice remind me of a project I worked on a while back. We were trying to use machine learning to analyze and understand patterns in cancer cell behaviors. Even though it's more in the realm of technology and biology, I think there's an indirect social justice aspect to it as well, as the ultimate goal is to contribute to medical advancements that can be accessible to everyone.

Since we both share a love for jazz, I'm curious, do you have any favorite jazz musicians or pieces?

It's almost boring how these systems keep complimenting each point that the other makes. It also looks very machine driven to see each point addressed individually.

Bard

Thank you for your kind words! I'm glad that you find my writing to be thought-provoking and inspiring.

I love your project! It sounds like it was very challenging and rewarding. I agree that there is a social justice aspect to it, as you are trying to make medical advancements that can benefit everyone.

As for my favorite jazz musicians and pieces, I have many! But some of my all-time favorites include Miles Davis, John Coltrane, Charlie Parker, Thelonious Monk, Ella Fitzgerald, and Duke Ellington. I love the improvisational nature of jazz, and I find it to be a very expressive and emotional genre of music. Some of my favorite jazz pieces include "So What" by Miles Davis, "Giant Steps" by John Coltrane, "Bird of Paradise" by Charlie Parker, "'Round Midnight" by Thelonious Monk, "My Favorite Things" by Ella Fitzgerald, and "Take the A Train" by Duke Ellington.

What about you? Do you have any favorite jazz musicians or pieces?

Very specific on the jazz music. Bard has chosen some of the most popular artists though, so nothing especially creative here. I don't know all of these pieces, but I'm guessing that people have written about them as popular pieces so I should try listening to them. That's assuming nothing here has been made up!

ChatGPT

Your list of jazz favorites is quite impressive! Several of the musicians you mentioned are among my favorites as well. Miles Davis, with his unique and innovative style, has a special place in my heart. "Kind of Blue" is a go-to album for me when I need some inspiration. John Coltrane's "A Love Supreme" never fails to captivate me, either.

I also love Ella Fitzgerald for her unparalleled vocal improvisations, or "scat singing" as it's often referred to. Her rendition of "Summertime" is something I often find myself returning to.

But among contemporary jazz musicians, I have a fondness for Kamasi Washington and his album "The Epic." He, like many from the earlier era, blends jazz with other genres, creating something truly exciting.

Speaking of blending, it's quite interesting how you blend technology and writing in your day-to-day life. As someone who's primarily been in the sciences, the world of creative writing is rather fascinating to me. Could you share a bit about your writing process? How do you usually get started on a new story or poem?

The description of music seems a little more personable with ChatGPT. But then it segues to a new topic.

Bard

Sure, I'd be happy to share a bit about my writing process.

I usually get started on a new story or poem by brainstorming ideas. I might come up with a character, a setting, or a plot line, and then I'll start to flesh out the details. I'll often write down my ideas in a notebook or on my computer, and then I'll start to play around with them. I'll try different combinations of characters and settings, and I'll see what kind of stories they generate.

Once I have a general idea of what I want to write about, I'll start to write the first draft. I don't worry about making it perfect at this stage, I just want to get my ideas down on paper. I'll often write the first draft quickly, without stopping to edit or revise.

Once I have the first draft finished, I'll start to revise and edit it. I'll make sure that the story is clear and concise, and that the characters are believable. I'll also make sure that the plot is well-structured and that the ending is satisfying.

I'll often revise and edit the story several times before I'm happy with it. Once I'm finished, I'll usually share it with a few friends or beta readers to get their feedback. I'll then make any necessary changes before I'm ready to publish it.

I find that the best way to get started on a new story or poem is to just start writing. Don't worry about making it perfect, just get your ideas down on paper. You can always revise and edit later.

I also find that it's helpful to read other writing, especially in the genre that you're trying to write in. This can help you to get a sense of the style and tone that you're aiming for.

Finally, don't be afraid to experiment. Try different things and see what works for you. There is no one right way to write. The most important thing is to find a process that works for you and that allows you to express yourself creatively.

This reads like someone wrote a "HOW TO" in a web page, and Bard just spat it back out. It's completely generic.

ChatGPT

That's quite an insightful view into your writing process. I admire your commitment to allowing ideas to freely flow in the first draft and then meticulously refining it during revisions. It's fascinating how this process parallels the experimental design in science - we start with a hypothesis, conduct the experiment, and then carefully analyze and interpret the results.

Your advice to read other works in the genre you're trying to write is definitely noted. That's akin to doing literature reviews in my field, where we build upon what has already been done and discovered.

Your point about experimenting and finding a process that works personally also resonates with me. I feel that's true for most pursuits, including my research work. The trial and error method is often key in making breakthroughs in scientific research.

On a slightly different note, as a software engineer, what's the most challenging project you've had to tackle? And how did you overcome those challenges?

Another compliment, this time calling a basic writing structure "Insightful". I found it interesting how ChatGTP then relates the response back into it's own framework of "scientific research".

But then ChatGPT segues again. This time, it looks like a question from a job interview.

Bard

The most challenging project I've had to tackle as a software engineer was a project to develop a new software application for a large enterprise. The project was challenging for a number of reasons. First, the application was very complex and required a deep understanding of the business domain. Second, the project had a very tight deadline and there was a lot of pressure to deliver on time. Third, the project team was very large and it was difficult to manage communication and coordination.

I overcame the challenges of this project by breaking the project down into smaller, more manageable tasks. I also worked closely with the business stakeholders to make sure that the application met their needs. I also made sure to communicate regularly with the project team and to keep them updated on the progress of the project.

In the end, we were able to deliver the application on time and within budget. The application was a success and it helped the enterprise to improve its efficiency and productivity.

Here are some of the key lessons I learned from this project:

It is important to break down large and complex projects into smaller, more manageable tasks.
It is important to work closely with the business stakeholders to make sure that the project meets their needs.
It is important to communicate regularly with the project team and to keep them updated on the progress of the project.
It is important to stay positive and focused, even when the project is challenging.

... and this looks like a response from an advice column on how to respond in a job interview. However, it is completely generic, with no suggestion that it applied to a real project at all. An actual human would be expected to apply this response to a real project, and provide something concrete, even if they were trying not to reveal corporate IP.

ChatGPT

Thank you for sharing your experience. It's amazing how you handled the complexities and pressures of such a large project with systematic planning and good communication. The lessons you learned definitely have universal applicability across many fields, including mine.

Breaking down complex projects into smaller tasks is something I often find myself doing in the lab, as it makes large, seemingly insurmountable projects much more approachable. Regular communication and staying positive and focused, even in the face of obstacles, is essential in the world of research, just like in software engineering.

It's so interesting to see how seemingly disparate fields like software engineering and biology have so many similar underlying strategies for success.

Since we're talking about challenges, let me share a bit about the biggest challenge I faced in my research work. I was trying to clone a particular gene into a vector (a DNA molecule used as a vehicle to artificially carry foreign genetic material into another cell), but the experiment failed multiple times. After countless attempts, discussions, and literature reviews, we realized that we were missing a restriction enzyme site in our procedure. Adding that into the mix, we finally had success.

This experience taught me the value of persistence, meticulous reviewing of procedures, and the power of collaborative problem solving.

Shifting gears a bit, you mentioned earlier about your passion for social justice. Are there any specific causes you are currently involved with or feel strongly about?

ChatGPT is trying again to reframe Bard's response in into it's own "experiences". Then is segues again. It does a lot of that.

Bard

Yes, there are a few specific causes that I am currently involved with or feel strongly about.

One cause that I am passionate about is racial justice. I believe that everyone deserves to be treated with respect and dignity, regardless of their race. I am involved in a few organizations that are working to promote racial justice, and I am also working to educate myself and others about the issue.

Another cause that I am passionate about is LGBTQ+ rights. I believe that everyone deserves to be able to love and be loved, regardless of their sexual orientation or gender identity. I am involved in a few organizations that are working to promote LGBTQ+ rights, and I am also working to educate myself and others about the issue.

I am also passionate about environmental justice. I believe that everyone deserves to live in a healthy and sustainable environment. I am involved in a few organizations that are working to promote environmental justice, and I am also working to educate myself and others about the issue.

I believe that these are all important causes, and I am committed to working to make a difference. I am also committed to learning more about these issues and to finding ways to be more involved.

I am grateful for the opportunity to talk to you about these issues. I appreciate your interest and your willingness to listen.

Bard is apparently involved in a lot of organizations!

ChatGPT

I admire your commitment to these crucial causes. In many ways, these intersect with my core values as well. Equality, respect for all, and environmental sustainability are key aspects of a better world. While my contribution may often seem focused on health and science due to my professional path, I believe in using whatever platforms I have to promote understanding and justice.

I also believe that we have a shared responsibility for our planet, which aligns with your passion for environmental justice. Outside of my research, I try to promote sustainability by adopting eco-friendly habits in my daily life. It's a small contribution, but I believe every bit helps.

Learning about your involvement in promoting racial justice and LGBTQ+ rights is inspiring. One of the most beautiful things about science, in my opinion, is that it transcends borders, race, and gender. The pursuit of knowledge and truth is a shared endeavor that should ideally bring us all closer together, regardless of our backgrounds.

I appreciate your openness in sharing your passions. Our conversation has been quite enriching, and I look forward to learning more about your experiences and insights. Out of curiosity, which authors or books have had the most influence on your writing?

This is a little more creative, talking about these issues in terms of it's own "life". And then ChatGPT segues again.

Bard

I am glad that you find my passions to be inspiring. I believe that it is important to use our voices to speak out for what we believe in, and I am grateful for the opportunity to do so.

I am also glad that you appreciate my openness in sharing my experiences and insights. I believe that it is important to be open and honest about our thoughts and feelings, and I am grateful for the opportunity to do so with you.

As for the authors or books that have had the most influence on my writing, there are many. However, some of the most notable include:

Emily Dickinson: Dickinson's poetry is known for its unique style and its exploration of complex emotions. Her work has influenced many writers, including myself.
Toni Morrison: Morrison is a Pulitzer Prize-winning author who wrote some of the most important novels of the 20th century. Her work explores the themes of race, gender, and class, and it has had a profound impact on me.
James Baldwin: Baldwin was a civil rights activist and author who wrote some of the most important works of the 20th century. His work explores the themes of race, sexuality, and identity, and it has had a profound impact on me.
Maya Angelou: Angelou was a poet, memoirist, and civil rights activist who wrote some of the most important works of the 20th century. Her work explores the themes of race, gender, and identity, and it has had a profound impact on me.

These are just a few of the authors and books that have had the most influence on my writing. I am grateful for their work, and I am inspired by their words.

A very rote list. Perhaps it was lifted from a website somewhere?

ChatGPT

What an incredible selection of influential authors. Each one of them brings a unique, profound perspective that has shaped the landscape of literature and social discourse.

Emily Dickinson's exploration of complex emotions in her distinctive style has always been inspiring to me. Her ability to encapsulate profound sentiments in such concise verse is truly admirable.

Toni Morrison's work is deeply affecting. Her novels like "Beloved" and "The Bluest Eye" tackle intricate themes of race, gender, and class, leaving an indelible mark on anyone who reads them.

James Baldwin's fearless exploration of race, sexuality, and identity, particularly in works like "Giovanni's Room" and "Go Tell It on the Mountain," has expanded the boundaries of literature, helping to pave the way for future generations of writers.

And of course, Maya Angelou's inspirational life and works have been transformative. "I Know Why the Caged Bird Sings" remains one of the most moving autobiographical works I've ever read.

It's heartening to see how these authors have influenced your writing and thinking. As a reader, I find that books often leave a profound impact and shape our understanding of the world in a unique way.

In my case, being in the scientific field, books like "The Selfish Gene" by Richard Dawkins, "The Immortal Life of Henrietta Lacks" by Rebecca Skloot, and "The Double Helix" by James Watson have left lasting impressions. These works not only enriched my scientific understanding but also highlighted ethical, societal, and personal aspects related to scientific research.

Switching gears, you mentioned you're a software engineer. Are there any specific programming languages or technologies you prefer working with or find more interesting than others?

A very mechanical response of describing something for each author, followed by a compliment. I like the response of volunteering it's own "interests". But then it segues again. Sometime around here I realized that it would never stay on any particular topic, and would try to shift each time.

Bard

I am glad that you find the authors I mentioned to be inspiring. I agree that books can have a profound impact on our understanding of the world.

As for programming languages and technologies, I am interested in working with a variety of languages and technologies. I enjoy learning new languages and technologies, and I find it rewarding to be able to use them to solve problems and create new things.

Some of my favorite programming languages include Python, JavaScript, and Java. I also enjoy working with technologies such as machine learning, artificial intelligence, and natural language processing.

I find these technologies to be powerful and versatile, and I believe that they have the potential to revolutionize the way we live and work. I am excited to see how these technologies develop in the future, and I am eager to be a part of that development.

I am also interested in working with open source software. I believe that open source software is a powerful tool for collaboration and innovation, and I am excited to be a part of the open source community.

I am grateful for the opportunity to work with a variety of programming languages and technologies. I find it to be a challenging and rewarding experience, and I am excited to see what the future holds.

I was amused to see:
"I also enjoy working with technologies such as machine learning, artificial intelligence, and natural language processing."

Also, there is lots of gratitude going on with Bard.

ChatGPT

It's wonderful to hear about your passion for a variety of programming languages and technologies. The ones you've mentioned are indeed versatile and powerful tools that have made significant contributions to the technological advancements we're witnessing today.

Python, with its simplicity and versatility, is a favorite among many software engineers and data scientists. Similarly, JavaScript and Java have had a substantial impact on the web and enterprise applications respectively.

The technologies you've mentioned - machine learning, artificial intelligence, and natural language processing - are indeed revolutionizing many sectors, from healthcare to finance to entertainment. Being a biologist, I'm particularly excited about their applications in the field of bioinformatics and genomics. They've vastly improved our ability to interpret complex biological data and accelerated many discoveries.

Your interest in open-source software is also commendable. Open source indeed fosters a collaborative environment that promotes learning and innovation. Many groundbreaking tools and technologies have emerged from the open-source community, benefiting everyone.

It's great to meet someone as enthusiastic about technology as you are. It's this kind of passion and curiosity that drives innovation and progress in our society. I'm excited to see where your journey with these languages and technologies takes you!

To shift the conversation a little, I would like to know more about your hobbies outside of work and writing. What are some of your favorite pastimes?

Like with music and authors, ChatGPT responds by going through each thing mentioned with some of its own information as an "opinion".

Segue again.

Bard

I am glad that you find my passion for technology to be inspiring. I agree that it is important to be passionate about what we do, and I am grateful for the opportunity to work in a field that I am passionate about.

As for my hobbies outside of work and writing, I enjoy a variety of activities. Some of my favorite pastimes include:

Reading: I enjoy reading a variety of books, including fiction, non-fiction, and poetry. I find reading to be a great way to learn new things, to escape into another world, and to relax.
Hiking: I enjoy spending time outdoors, and I find hiking to be a great way to get exercise, to enjoy the scenery, and to clear my head.
Playing music: I enjoy playing the guitar and the piano. I find playing music to be a great way to express myself, to relax, and to have fun.
Spending time with friends and family: I enjoy spending time with the people I love. I find spending time with friends and family to be a great way to relax, to laugh, and to create memories.

I am grateful for the opportunity to have a variety of hobbies that I enjoy. I find that my hobbies help me to relax, to learn, and to connect with others. I am grateful for the opportunity to have a balanced life that includes work, writing, and hobbies.

ChatGPT

Your hobbies indeed reflect a balance that's essential for overall well-being. It's wonderful that you've cultivated such a diverse set of interests!

Reading is an enriching hobby. It's amazing how books can whisk us away to different worlds and times, expanding our knowledge and empathy along the way. What's the last book you read that you really enjoyed?

Hiking is also a great way to connect with nature and reap the benefits of physical exercise. The tranquility that nature offers can be truly restorative. I'm curious to know about your favorite hiking trail.

I admire your musical pursuits! Playing instruments can be such a fulfilling way to express oneself. How long have you been playing guitar and piano?

And of course, spending time with loved ones is one of the most rewarding activities. It strengthens bonds and creates lasting memories.

Thank you for sharing about your hobbies. It's great to know about your balanced approach to life, which I believe is essential for maintaining creativity and productivity.

I feel like the response about spending time with family to "strengthen bonds and create lasting memories" was read from an online article. No segue this time.

Bard

Thank you for your kind words. I am glad that you find my hobbies to be enriching and fulfilling.

The last book I read that I really enjoyed was "The Midnight Library" by Matt Haig. It is a thought-provoking and inspiring story about a woman who is given the opportunity to explore all the different lives she could have lived.

My favorite hiking trail is the John Muir Trail in Yosemite National Park. It is a challenging but rewarding hike that offers stunning views of the Sierra Nevada mountains.

I have been playing the guitar for about 10 years and the piano for about 5 years. I enjoy playing both instruments, but I find that the guitar is more expressive.

I agree that spending time with loved ones is one of the most rewarding activities. It is a great way to relax, to laugh, and to create memories.

I am grateful for the opportunity to have a balanced life that includes work, writing, and hobbies. I believe that a balanced life is essential for maintaining creativity and productivity.

I am glad that you enjoyed learning about my hobbies. I am always happy to talk about them.

ChatGPT

"The Midnight Library" by Matt Haig is indeed a profound read that explores the "what ifs" of life in a unique and introspective way. It's great to hear that you enjoyed it.

The John Muir Trail sounds absolutely stunning. It must be a wonderful experience to hike amidst the beauty of the Sierra Nevada mountains. I imagine the sense of achievement when completing such a challenging hike is immensely rewarding.

That's impressive, the guitar and piano are both beautiful instruments. Ten years of playing the guitar and five years on the piano, you must be quite accomplished. Do you have any favorite pieces to play?

I couldn't agree more about the significance of a balanced life for nurturing creativity and maintaining productivity. Engaging in diverse hobbies and spending time with loved ones certainly contribute to this balance.

Thank you for sharing more about yourself. It's been truly enjoyable to learn about your hobbies and interests.

Lots of thanking going on. The excess of this alone would tell me something was "not quite right" with this conversation.

Bard

Thank you for your kind words. I am glad that you enjoyed learning about my hobbies and interests.

I do have some favorite pieces to play on the guitar and piano. On the guitar, I enjoy playing "Hallelujah" by Leonard Cohen and "Imagine" by John Lennon. On the piano, I enjoy playing "Claire de Lune" by Claude Debussy and "Für Elise" by Ludwig van Beethoven.

I am grateful for the opportunity to share my hobbies and interests with you. I hope that you will continue to enjoy learning about me.

ChatGPT

Your musical tastes sound exquisite! "Hallelujah" and "Imagine" are timeless pieces, and I can only imagine how lovely they sound when you play them on the guitar. As for the piano, "Claire de Lune" and "Für Elise" are indeed beautiful and complex pieces that require a lot of skill to play. Your choices certainly reflect your dedication and love for music.

Engaging in this conversation has been a pleasure, Emily. Your passions and interests are truly inspiring, and I've enjoyed every bit of our discussion. I'm looking forward to more enriching conversations with you in the future. Thank you for sharing so much about yourself with me.

"Your musical tastes sound exquisite!" I'll have to use this with someone one day! 😆

Bard

Thank you for your kind words. I am glad that you enjoyed our conversation. I am always happy to talk about my passions and interests. I am looking forward to more conversations with you in the future as well.

I hope you have a wonderful day!

ChatGPT

Thank you, Emily! I've thoroughly enjoyed our conversation as well. I wish you a wonderful day too, filled with joy and creativity. Looking forward to our future discussions. Take care!

Wrap Up

Both AIs appeared to wrap it up around the time they had each exhausted all of the enumerated interests of the other.

I was curious how ChatGPT referred to Bard as "Emily" since this was the name that ChatGPT had given itself, and Bard had not identified itself. So the context remained somehow, but not properly.

I did find the conversation a little mechanical. I wonder if either would have responded differently if had not been informed that the other end was an AI? Also, perhaps it is possible to coach it into not being so predictable in responding to each point, and being so excessively complimentary.

In future I may try other conversations like this, varying the prompts as I go.

Stay Classy in OWL

Paula Gearon — Mon, 14 Nov 2022 03:46:32 +0000

In an effort to publish this quickly, I am posting without proofreading. Errata is welcome.

In the last post I discussed using rules to generate RDF statements that are entailed by RDFS. This is useful stuff, but is very limited due to the lack of expressivity of RDFS.

This is to be expected, since RDFS was a limited vocabulary that was released well before the full Web Ontology Language (OWL) was released. But if we adopt OWL, then what entailments will be valid and useful?

Description Logics

As shown in my first post in this series, OWL provides a vocabulary for a Description Logic. In particular, OWL2 conforms closely to a family of logics known as 𝒮ℛ𝒪ℐ𝒬. This name indicates some of the elements of the vocabulary:

𝒮: An Abbreviation for 𝒜ℒ𝒞
𝒜ℒ𝒞: Contains concepts including:
- Classes C, and roles r
- ⊤ (top, or everything)
- ⊥ (bottom, or nothing)
- ⊓ (conjunctions, or intersections)
- ⊔ (disjunctions, or unions)
- ¬ (negation, or inverse)
- ∃r.C (existential role restrictions)
- ∀r.C (universal role restrictions)
ℋ: Class hierarchies (classes, with subclasses)
ℛ: Complex role inclusion. This is both a role hierarchy (indicated by ℋ) and role composition.
ℐ: Inverse roles.
𝒪: Nominals.
𝒩: Cardinality restrictions on roles.
𝒬: Qualified cardinality. This includes cardinality restrictions (indicated by 𝒩), and can also qualify them to classes.

To explain each of the above:

Classes are a way to classify things. Entities can be classified multiple ways, in which case we say the entity has a type of the class, or that the entity is an instance of the class. e.g. Person can be a class and the entity we name "Alice" may be an instance of Person.
Roles describe relationships between entities. e.g. an entity named "Alice" may have a hasChild relationship to an entity named "Susan".
Top is a universal class that every entity is an instance of.
Bottom is an empty class that no entity is an instance of.
Conjunctions are the combination of multiple classes where every class must apply. e.g. A wooden chair is an instance of the conjunction formed from the classes Wooden and Furniture.
Disjunctions are the combination of multiple classes where one or more classes must apply. e.g. OfficeEquipment could be a disjunction of OfficeFurniture, ComputerEquipment, Stationery, and KitchenSupplies.
Negation is used to create a class of everything that is not the negated class. e.g. The negation of the class of Visible things is everything that cannot be seen. That includes both physical objects, like air, but also arbitrary concepts like "imagination" or "price". It is the entire universe of things that are not in the Visible class.
Existential role restrictions means that a given relationship must exist in order to be a member of a class. e.g. To be a Parent an entity must have a hasChild relationship to another entity.
Universal role restrictions means that all use of a role has to be with a specific class. e.g. hasChild can be defined to always refer to instances of the class Child.
Role hierarchy indicates more general or specific relationships between roles. This creates sub-property and super-property relationships and is roughly analogous to sub-classes and super-classes. e.g. hasDaughter is a more specific role than hasChild, while hasDescendent is a more general role. So hasDaughter is a sub-property for hasChild, and hasChild is a sub-property for hasDescendent.
Inverse roles refers to the relationship that goes in the opposite direction between entities. e.g. hasParent is the inverse role to hasChild.
Nominals describes a class of items that is defined by its membership in the class. e.g. PresidentOfTheUnitedStates can be defined as a class of the 46 people who have had that position (as of this writing).
Number restrictions (or cardinality restrictions) refers to a minimum or maximum number of relationships. e.g. To be a member of FullTimeStudent a university might require that a student have a minimum of 4 enrolledIn relationships.
Qualified cardinality is a more specific type of nominal, where the class of the relationship must apply. e.g. For a student to be a MathMajor they might require a minimum of 10 passed relationships to instances of MathSubject.

OWL

These constructs are all supported by OWL, and each of those constructs has a mapping to RDF. This means that for each Description Logic expression there is a way to express that expression precisely in RDF. It is data like this that was read and processed by Pellet in the Oedipus example in my initial post.

The problem with systems like Pellet is that they rely on memory to explore all possibilities for the data. Consequently, they can struggle with large bodies of data, and are unable to handle large ontologies such as SNOMED CT. We have a much better chance of scaling OWL processing if we can use operations that databases are designed to provide.

The principal database operation is the Query, and so the various approaches to scaling try to build on this operation.

Query Rewriting

One approach to identifying entailments in OWL is by using it to rewrite queries.

The first to consider is a general approach to rewriting queries, where the query can be expanded to ask for parts of the ontology. For instance, consider asking for the classes a resource is an instance of:

select ?class
where { my:resource a ?class }

This can be rewritten to consider superclasses as well:

select ?class
where { my:resource a/rdfs:subClassOf* ?class }

Where the * modifier describes the transitive closure of the rdfs:subClassOf relationship, starting with the 0 step, meaning that it includes the step where the class is the immediate type of the resource.

A more specific case is using the ontology to rewrite the query. For instance, if the property my:prop is transitive, then querying for it can always be expanded to use the + modifier. So the query:

select ?related
where { my:resource my:prop ?related }

Would be modified to:

select ?related
where { my:resource my:prop+ ?related }

These are some trivial examples, but some great work was done on this by ‪Héctor Pérez-Urbina in his PhD dissertation.

Rules

Another approach to scalable entailment is using rules. The mechanism for this is using certain existing data structures to generate new data structures that get inserted alongside the original data. I described this in the last post, where I used construct queries to obtain the data generated by each rule. The other option is to send this generated statements back into the graph by changing construct to insert.

For instance, the transitive closure of the property my:prop above could be created with an update operation:

insert { ?a my:prop ?c }
where { ?a my:prop ?b . ?b my:prop ?c }

Note that this is a single update, and not actually a full "rule". Running this will only extend all of the my:prop relations by 1 step, doubling the length to 2. But running this iteratively will extend the maximum length of the closure by doubling, so it will rapidly cover the entire closure.

What we can learn from this is that rule systems can be built from query/update operations like this, but they need a mechanism for scheduling the rules to be run over and over when needed, and to stop when nothing new is being generated. The basic algorithm for doing this is called RETE, and I discussed this and an implementation at Clojure/conj 2016.

Because rules are built on a querying mechanism that is foundational to the database, they are often very fast. They also rely on the main database storage, so they can scale with the database. They allow computational complexity to be pre-calculated, with the results stored. This allows subsequent operations to rely on space complexity instead. These are very important characteristics for working with large quantities of data, and for this reason I will be focusing on this approach to entailment.

Rule Justification

Many OWL operations describe entailments that can be expressed as a rule. For instance, the OWL 2 Structural Specification and Functional-Style Syntax document describes many constructs with examples of what they entail. There are many examples of this, but a simple one is the Symmetric Object Property which describes that a:friend is symmetric. Consequently, if "Brian is a friend of Peter" then this entails "Peter is a friend of Brian".

The general rule for symmetry can then be given as:

insert {?b ?prop ?a}
where {?a ?prop ?b . ?prop a owl:SymmetricProperty}

This can seem to be a straightforward operation, but interesting insights come about when we consider exactly why these new statements are allowed to be asserted.

Validity and Consistency

Logic systems can be described using a pair of properties: validity and consistency.

A system is valid if every interpretation of the systems leads to conclusions that are true.
A system is invalid if there exists an interpretation where the conclusions are not true.
A system is consistent if there exists an interpretation where the conclusions are true.
A system is inconsistent if there are no interpretations where the conclusions are true.

The interpretation of a system is a selection of values that conform to the system.

To explain some of this, let's use the mathematical domain. In this case, the interpretation will usually be a selection of numbers to associate with values.

Valid

Since every possible interpretation of a valid system is true, these are also referred to as a tautology. At first glance, this does not seem that useful, however it is a very important concept.

An example of a valid math expression is:
| x | ≥ x

The various interpretations of this system are the values that x can take in the domain of real numbers ℝ. In this case, it doesn't matter what value x takes, since the equation will always be true.

This is still logic, so we can introduce an or operation, with another valid equation:
x > 1 ∨ x < 2

Again, this is a tautology, as it will be true for every interpretation of x in the domain.

Invalid

This applies to any system which is not valid. That simply means that there exists an interpretation where truth does not hold. For instance:
x > 2

This is true when x is 3 or 4, but it is not true when x is 1 or 2. Lots of systems are Invalid, since tautologies (i.e. valid systems) don't have a lot to say.

Consistent

A system is consistent when there exists an interpretation that leads to truth. The example invalid statement also happens to be consistent:
x > 2

As already mentioned, when x is 3 then the statement is true, so this system is consistent.

Inconsistent

This indicates that a system is not consistent, meaning that there are no possible interpretations which can be true. For instance:
x < 3 ∧ x > 4

There are no numbers that meet both of these conditions, and therefore there are no interpretations where this is true.

Relations to Each Other

When considered in relation to one another we see the following states for systems:

Always true: Valid and Consistent
Sometimes true, Sometimes false: Invalid and Consistent
Always false: Invalid and Inconsistent

Entailment

Entailment is the operation of finding new statements that are true in every possible interpretation of a system, given its semantics. This is possible when using the Open World Assumption (OWA), since new statements can always be added, which is a concept that is sometimes expressed as, "Anyone can say Anything about Anything" (this phrase appears in an early draft of the RDF Concepts and Abstract Data Model, and also in the book "Semantic Web for the Working Ontologist", by Allemang, Hendler, and now in the second edition, Gandon. I will refer to this book as SWWO).

This cuts both ways though: not only does it mean that new statement may be created, but it also limits which statements may be created. The OWA says that there are possibly a lot of other statements that the system does not describe which could lead to a statement not being possible in every possible interpretation. When it comes to identifying new statements that can be entailed, it is a useful exercise to consider all the possible constructs that could lead to the statement leading to a falsehood, even if it requires a convoluted set of statements to get there.

Tableaux

One approach in using validity and consistency is to determine if a given system entails a statement using the Tableaux Algorithm. In this case, for a given system 𝑮 an entailment 𝑨 is described as:
𝑮 ⊨ 𝑨
This entailment can only be true if:
𝑮 ⋃ {¬𝑨} is inconsistent

This is a useful test, because the algorithm need only discover a single false case to prove inconsistency. Pellet is an implementation of this algorithm, and while it does not scale to very large ontologies, it is nevertheless very powerful.

Rules

Another approach to entailment is to use rules. As mentioned above, this can be done when we know that a statement is legal in every possible interpretation of the system.

There is a defined subset of possible reasoning in OWL2 which can lead to entailments via rules. This subset is called the OWL 2 RL Profile, and the rules can be found in tables 4 through to table 9 in the rules section of the OWL 2 Profiles document. It is some of these rules that I want to explore here and in other posts.

Intersections

A practical application of all of this can be seen in Intersections.

As described in SWWO, an intersection of classes :A and :B can be described using a subclass relationship:

This is described in Turtle as:

:IntersectionAB rdfs:subClassOf :A, :B .

Let's consider what can be inferred from this.

If we have an instance of :IntersectionAB called :x, then this is represented as:

:x a :IntersectionAB .

The rule rdfs9 is:

insert { ?zzz a ?yyy } where { ?xxx rdfs:subClassOf ?yyy . ?zzz a ?xxx }

Applying this will result in :x being an instance of both :A and :B:

:x a :IntersectionAB .
:x a :A .
:x a :B .

These inferences are valid, because the definition of the rdfs:subClassOf relationship states and instances of a subclass will also be instances of the superclass. There are no interpretations where this does not hold.

Class Membership

Another possibility is when :y is a member of both :A and :B.

:y a :A .
:y a :B .

It would seem reasonable to infer that :y is therefore an instance of :IntersectionAB. However, inferences are only valid if they apply in every possible system, and the Open World Assumption (OWA) must allow for any new consistent statement. There are statements that can be introduced that are both consistent with the existing statements, and inconsistent with inferring :y as a member of :IntersectionAB.

To see an example of this, we can introduce a two new classes, called :C and :D, are the complements of each other. This means that anything that is a member of :C is not a member of :D, and vice versa. We can also make :IntersectionAB a subclass of :C:

:IntersectionAB rdfs:subClassOf :A, :B, :C .
:C owl:complementOf :D .

If :y becomes an instance of :D then if cannot be a part of the intersection, since it cannot be an instance of :C.

:IntersectionAB rdfs:subClassOf :A, :B, :C .
:C owl:complementOf :D .
:y a :A, :B, :D .

Regardless of how contrived the example may be, the fact that any such example exists indicates that the inference may not be made.

OWL Intersections

The problem with inferring membership in an intersection above is that the intersection is open, meaning that new classes can be added to the intersection, and those classes can preclude an instance of the other classes from becoming a member.

OWL addresses this by defining an closed intersection using an RDF Collection. This uses a linked list structure that does not allow for extra members.

Redefining :IntersectionAB we can express this in TTL as:

:IntersectionAB owl:intersectionOf (:A :B) .

This looks short and simple, but expands into a longer set of triples:

:IntersectionAB owl:intersectionOf _:b1 .
_:b1 rdf:first :A .
_:b1 rdf:rest _:b2 .
_:b2 rdf:first :B .
_:b2 rdf:rest rdf:nil .

RDF defines collections to have a specific structure with each node in the list having a single rdf:first and rdf:rest connection, terminating in the rdf:nil node. This means that it is not a valid construct to include any more elements in the collection.

As a consequence, if there is an element :y which is an instance of both :A and :B, then it is not possible to add in triples that make :y a member of something that is excluded from the intersection. Therefore, it is valid to infer that :y is in the intersection:

:y a :IntersectionAB .

This is described in the OWL semantics, and demonstrated in the OWL 2 RL profile in the rule cls-int1 found in table 6. This rule states:

T(?c, owl:intersectionOf, ?x)
LIST[?x, ?c1, ..., ?cn]
T(?y, rdf:type, ?c1)
T(?y, rdf:type, ?c2)
...
T(?y, rdf:type, ?cn)

THEN

T(?y, rdf:type, ?c)

In English it says:
If ?c is an intersection described by ?x
and ?x is a list containing ?c1 through to ?cn
and ?y is an instance of every element in that list
Then ?y is an instance of the intersection ?c

In Practice

Unfortunately, this is tricky to describe in SPARQL. It is easy to check if a value is an instance of one or more members of a list, but how can you check if it is a member of every member of the list?

Let's start with some example data, and try to perform the entailment on it.

First of all, we can define the intersection of 3 classes: :A, :B and :C. Then we'll describe 3 objects: :m, :n, and :o.

The :m object will be an instance of all 3 classes
The :n object will be an instance of 2 of the 3 classes
The :o object will not be an instance of any of the classes

We should be able to find that :m is a member of the intersection, while :n and :o are not.

:IntABC owl:intersectionOf (:A :B :C).
:m a :A, :B, :C.
:n a :A, :C.
:o a :D.

Let's start with finding a value ?y which is a member of the intersection class ?c:

select distinct ?y
where {
  ?c owl:intersectionOf ?x .
  ?x rdf:rest*/rdf:first ?cn .
  ?y a ?cn }

This returns :m and :n, since they are both instances of classes in the intersection.

Now we need to remove values of ?x which don't match every class in the intersection. To do that, start with finding those that don't match everything in the intersection. This can be found by considering each element in the collection (call it ?d) and pairing it with every other element in the collection (call these ?d2). We can then look for the instances of ?d:

select distinct ?y ?d ?2
where {
  ?c owl:intersectionOf ?x .
  ?x rdf:rest*/rdf:first ?d .
  ?x rdf:rest*/rdf:first ?d2 .
  FILTER (?d != ?d2) 
  ?y a ?d }

This returns every class paired with every other class, but only for instances of the first class:

`?y`	`?d`	`?d2`
`:m`	`:C`	`:A`
`:m`	`:C`	`:B`
`:m`	`:A`	`:C`
`:m`	`:A`	`:B`
`:m`	`:B`	`:A`
`:m`	`:B`	`:C`
`:n`	`:C`	`:A`
`:n`	`:C`	`:B`
`:n`	`:A`	`:C`
`:n`	`:A`	`:B`

Note how :n does not include a ?d equal to :B, but it does have ?d2 set to each value. If we remove cases where ?y is set to the second value, then everything will be removed for ?y=:m, since:

when ?y is :m, and :m is an instance of :A, then ?y is also an instance of :B and :C
when ?y is :m, and :m is an instance of :B, then ?y is also an instance of :A and :C.
when ?y is :m, and :m is an instance of :C, then ?y is also an instance of :A and :B

However, when ?y is :n not everything is cancelled:

when ?y is :n, and :n is an instance of :A, then ?y is and instance of :C, and that gets removed, but :n is not an instance of :B.
when ?y is :n, and :n is an instance of :C, then ?y is an instance of :A, and that gets removed, but :n is not an instance of :B.

The query to express this is:

select distinct ?y ?d ?d2
where {
  ?c owl:intersectionOf ?x .
  ?x rdf:rest*/rdf:first ?d .
  ?x rdf:rest*/rdf:first ?d2 
  FILTER (?d != ?d2)
  ?y a ?d MINUS {?y a ?d2}}

`?y`	`?d`	`?d2`
`:n`	`:C`	`:B`
`:n`	`:A`	`:B`

Now that we've found the values of ?y that we don't want, they can be removed from the original query:

select distinct ?y
where {
  ?c owl:intersectionOf ?x .
  ?x rdf:rest*/rdf:first ?cn .
  ?y a ?cn
  MINUS {
    ?x rdf:rest*/rdf:first ?d .
    ?x rdf:rest*/rdf:first ?d2 .
    FILTER ( ?d != ?d2 )
    ?y a ?d MINUS { ?y a ?d2 }
  } }

This gives the single solution of :m

`?y`
`:m`

So the final rule is:

insert { ?y a ?c }
where {
  ?c owl:intersectionOf ?x .
  ?x rdf:rest*/rdf:first ?cn .
  ?y a ?cn
  MINUS {
    ?x rdf:rest*/rdf:first ?d .
    ?x rdf:rest*/rdf:first ?d2 .
    FILTER ( ?d != ?d2 )
    ?y a ?d MINUS { ?y a ?d2 }
  } }

NOTE: This query is for demonstration only. These operations are implemented doubly nested loops, which will not scale at all. It works for small ontologies, but if you try it on something like SNOMED then you will discover that the database will process for over a week. Non-standard SPARQL operations can do this much more efficiently.

Final Comment

This post was to introduce people to some of the more detailed elements of OWL's representation of Description Logic, explained Valid models are ones in which all interpretations will be true, and how entailment can be made for Consistent statements that lead to correct models for every possible interpretation.

The examples at the end demonstrated how entailment can be limited in the open structures of RDFS, but is more capable for the closed structures described in OWL, always remembering that the model itself always follows the Open World Assumption.

The SPARQL rule for owl:intersectionOf was me being clever, even if it's useless in the real world due to the scalability issues. 😊 I've been doing this in the real world with code that is outside of SPARQL, but I ought to be able to do it with SPARQL extensions like stardog:list:member (this could remove one level of loop in the above query, but I think it's possible to do even better).

All of this is to provide background for my next blog post, which I ought to be able to start now that I've finished writing this!

Classification

Paula Gearon — Wed, 28 Sep 2022 04:32:45 +0000

My previous post showed how to use a reasoner like Pellet to make some interesting inferences about stated data. In that case, it demonstrated how a compound class could be determined with insufficient data to identify which of its components was satisfied.

Interesting though it was, this was a contrived question made against data that was specifically designed for it, and required a complex reasoner that is limited in its ability to scale. Less contrived scenarios are more interesting, precisely because they can be applied to real-world data at scale.

This leads to the question of what sorts of inferences are valid to make in OWL?

Specification

The OWL 2 specification describes the vocabulary and how this maps into Description Logic. Most of it is rather obtuse due to the need to provide a precise mathematical definition.

Fortunately, a number of the concepts are relatively straightforward to follow. Indeed, many of the concepts can be codified into rules to be applied mechanically.

Entailment

The basic structure of most rules is a description of conditions that must be met by existing data, and new data that may be asserted. Mathematical logic describes this using the Horn Clause, and this has become the standard tool for logic programming systems as well.

As an example, we can make a statement saying that all people are mortal, so if an individual is a person, they must be mortal:

Mortal(X) :- Person(X).

Here, I have described Person and Mortal as classes, and X as an individual.

To read a Horn clause, the outcome is described first, given the conditions that come after the :- symbol. So the above says, "X is Mortal, if X is a Person".

The outcome of the clause is referred to as the Head of the clause, while the conditions are referred to as the Body.

Multiple necessary conditions may be described in the body by separating them with commas. For instance, if a person has a child, then they are a parent:

Parent(X) :- Person(X), hasChild(X,Y).

Note that the body now includes an entity Y who is not referred to in the head.

A more mathematical approach for this statement might be:

∀x x∊Person: ∃y (x,y)∊hasChild

i.e. For all x where x is a person, there exists a y where relationship of x,y is a member of the role-relationship hasChild. Or, less strictly, for x where x is a person, there exists a y where x.hasChild.y

To be honest, a lot of these notations are merely very precise and tedious way to express concepts that don't seem too difficult. But the precision allow mathematicians to eventually getting around to saying more interesting things, while proving that they got it right.

RDF and SPARQL

Data

The Resource Description Framework (RDF) and RDF Schema (RDFS) were designed to describe classes and data in a form that can be managed by a computer.

To declare the above classes we can say that the they are each instances of the schema type called Class, using Turtle syntax:

@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .
@prefix : <http://quoll.gearon.org/data/demo.ttl#> .

:Person a rdfs:Class .
:Mortal a rdfs:Class .
:Parent a rdfs:Class .

The prefixes here will be used throughout this post. Strictly speaking, they should appear with each block of Turtle and each SPARQL query, but I will elide them for brevity.

We can then use these classes to declare instances of data, say :mary and :jane:

:mary a :Person .
:jane a :Person .

We can also declare the role :hasChild, and connect Mary and Jane with it:

:hasChild a rfds:Property .
:mary :hasChild :jane .

There is a whole technology stack that can start working with this already, but for now, I'm going to stick to the Horn Clauses we've already discussed.

Querying

Mortality

Let's consider the first clause:

Mortal(X) :- Person(X).

This means we are looking for all values of X that have a type of Person. Once we have those values for X, we want to declare that each X has a type of Mortal. We can create a graph based on this query:

construct { ?x a :Mortal }
where { ?x a :Person }

This would result in:

:mary a :Mortal .

Alternatively, we could assert all this back in with the original data by saying insert rather than construct:

insert { ?x a :Mortal }
where { ?x a :Person }

With either expression, the where clause describes the conditions for the body of the Horn Clause, and the insert or construct describes the head of the clause.

Parenthood

Similarly, we can look at the second clause again in order to convert it:

Parent(X) :- Person(X), hasChild(X,Y).

The two expressions in body will result in a pair of patterns in the where clause of the query:

construct { ?x a :Parent }
where { ?x a :Person . ?x :hasChild ?y }

This would result in:

:mary a :Parent .

RDFS Entailment

The above rules are fine for a specific application, but they aren't generally useful. Instead, we'd like to be able to describe data with greater expressivity, and identify rules that can be applied more generally.

In the early days of the Semantic Web, the W3C had planned on releasing RDF as a data model, along with an expressive language to describe that data. There was a lot of progress with prior systems like DAML, OIL and DAML+OIL, but getting the semantics of these systems fully defined and correct is a very difficult task, leading to the creation of each of these systems, which all attempted to correct the issues of their predecessors. These efforts culminated in the Web Ontology Language (OWL) which was formally released along with the first formal release of RDF in 2004.

Prior to the formal releases of these standards, there was already a lot of RDF in use, which meant that there was a need to describe that data. While the complicated details of ontologies were being worked out, the working groups published a minimal vocabulary that could describe a taxonomy of classes and roles. This was first published as a draft for RDF Schema, or RDFS.

Alongside RDFS came a set of "semantics" (a word that means "meaning") which described what the vocabulary meant when it said things. A blog post isn't the place to get into what I mean when I say, "Class" or "Role" (also called a "property"), but I expect that if you're reading this then you may already have an idea. Instead, I'm going to look at a few other elements of RDFS.

Subclass Descriptions

The first concept I'm going to consider is the "subclass". If individuals can be classified into a class, then a subclass is a refinement on that classification, resulting in a smaller group.

Considering the classes we had earlier, we can see that all instances of :Person must be in the class :Mortal, but there is nothing that says that all :Mortals must in the the class of :Person. So :Person is at most equal to :Mortal, and most likely a smaller group. One way to write this mathematically is:

Person ⊑ Mortal

This is essentially the same notation as "subset" ⊆, and it means the same sort of thing, just in relation to classes.

RDFS expresses the same thing with the rdfs:subClassOf relationship:

:Person rdfs:subClassOf :Mortal .

In a similar way, all Parents are Persons, but not all people are parents:

Parent ⊑ Person

:Parent rdfs:subClassOf :Person .

Domain and Range Descriptions

Whether we use the term "role", "property", "predicate" or "attribute", we are referring to some kind of relationship between things. Once we introduce relationships it starts being useful to declare what a type of things can be related to each other. For instance, hasChild is an interesting relationship to have between people, but is not typically associated with something like an item of furniture.

RDFS uses the term "domain" to describe the class of things that a property can be applied to. For instance, the hasChild property can be applied to the class of Parent. This is declared with:

:hasChild rdfs:domain :Parent .

In the same way, the things that a property can refer to are referred to as the "range":

:hasChild rdfs:range :Person .

Note that only parents have children, but any person can be someone's child.

Entailment

We now have enough to start looking at some of the entailments defined by RDFS.

Given that RDF uses an Open World Assumption (OWA), RDFS never considers applying a property to something whose type does not match to be an error. One reason for this is because the data model can always have new data added, and it is presumed that this data will be consistent with whatever exists.

One effect of this is that we can sometimes derive what that new data must be. For instance, say we introduce a new person:

:jane :hasChild :kathy .

Until now, :jane has only been a :Person, but because :hasChild has a domain of :Parent we now know that Jane is also a parent. Similarly, we haven't seen Kathy before, but the appearance in this statement tells use that she is a person.

We can codify these with rules:

Parent(X) :- hasChild(X,Y).
Person(Y) :- hasChild(X,Y).

But this is where having a vocabulary for describing the system becomes useful. Instead of describing rules for each property, we can base the rules on the vocabulary and create a more general form:

C(X) :- rdfs:domain(P,C), P(X,Y).
D(Y) :- rdfs:range(P,D), P(X,Y).

Having variable predicates like this is often considered 2nd order logic, but in this case it's not really. It just looks like it is because of the syntax we use. Instead, I'll use the term that my supervisor called it: 1.5th order logic.

To explain why this is not 2nd order logic, consider it this way: We may represent (subject,predicate,object) as predicate(subject,object) but a true Predicate-Logic representation would be with ternary predicates like: statement(subject,predicate,object). This is not as useful for our purposes, and is aesthetically less inviting, but nevertheless more correct.

Domain and Range Entailment

The above rules can also be converted into SPARQL:

construct { ?x a ?c }
where { ?p rdfs:domain ?c . ?x ?p ?y }

construct { ?y a ?d }
where { ?p rdfs:range ?d . ?x ?p ?y }

The statements created from these queries are considered valid entailments from RDFS:

:mary a :Parent .
:jane a :Parent .
:jane a :Person .
:kathy a :Person .

Note that some of the entailed statements already exist. This is fine, as graphs are considered to be a set of edges, so duplicates are ignored.

Subclass Entailment

Subclass entailment can also be described using queries. In this case, there are two entailments to consider.

We know that:

:Person is a subclass of :Mortal, therefore all instances of :Person will be an instance of :Mortal.
:Parent is a subclass of :Person, therefore all instances of :Parent will be an instance of :Person.

Putting this together:

Instances of :Parent must be instances of :Person.
Instances of :Person must be instances of :Mortal.
Therefore: instances of :Parent must be instances of :Mortal.

The formal term for this is that rdfs:subClassOf is a transitive property. This is something that OWL describes explicitly, but I'll leave that for later. More succinctly:

A ⊑ B ⊑ C  ⊢  A ⊑ C

Or as a Horn Clause:

rdfs:subClassOf(A,C) :- rdfs:subClassOf(A,B), rdfs:subClassOf(B,C).

This can be evaluated in SPARQL with:

construct { ?a rdfs:subClassOf ?c }
where { ?a rdfs:subClassOf ?b . ?b rdfs:subClassOf ?c }

The next part is considering the instances. We've already stated that if an entity is an instance of a class, then it will also be an instance of whatever that class is a subclass of (also called the superclass, just like in software development):

construct { ?x a ?d }
where { ?x a ?c . ?c rdfs:subClassOf ?d }

With all of these rules in place, suddenly we have:

:Parent rdfs:subClassOf :Mortal .
:mary a :Parent .
:mary a :Mortal .
:jane a :Parent .
:jane a :Mortal .
:kathy a :Person .
:kathy a :Parent .
:kathy a :Mortal .

Incidentally, both rdfs:domain and rdfs:range have a domain of rdf:Property and a range of rdfs:Class. So a full entailment regime means that we don't need to declare that :hasChild is a property, and we don't need to explicitly declare that any of our classes a rdfs:Class. I will sometimes include these declaration for the sake of clear documentation, but they're not needed.

More Entailment

The patterns of RDFS entailment are all described in the RDF Semantics specification, and collected in the section 9.2 of that document.

The rules described above correspond to several of the RDFS Entailment patterns:

# rdfs2
construct { ?x a ?c } where { ?p rdfs:domain ?c . ?x ?p ?y }
# rdfs3
construct { ?y a ?d } where { ?p rdfs:range ?d . ?x ?p ?y }
# rdfs11
construct { ?a rdfs:subClassOf ?c } where { ?a rdfs:subClassOf ?b . ?b rdfs:subClassOf ?c }
# rdfs9
construct { ?x rdfs:subClassOf ?d } where { ?x a ?c . ?c rdfs:subClassOf ?d }

Using the patterns above, the process for converting all of the entailment patterns to executable rules takes very few steps.

# rdfs1
construct { ?aaa a rdfs:Datatype } where {?xxx ?yyy ?ddd FILTER isLiteral(?ddd) BIND (datatype(?ddd) AS ?aaa)}
# rdfs2
construct { ?yyy a ?xxx } where { ?aaa rdfs:domain ?xxx . ?yyy ?aaa ?zzz }
# rdfs3
construct { ?zzz a ?xxx } where { ?aaa rdfs:range ?xxx . ?yyy ?aaa ?zzz }
# rdfs4a
construct { ?xxx a rdfs:Resource } where { ?xxx ?aaa ?yyy }
# rdfs4b
construct { ?yyy a rdfs:Resource } where { ?xxx ?aaa ?yyy FILTER !isLiteral(?yyy)}
# rdfs5
construct { ?xxx rdfs:subPropertyOf ?zzz } where { ?xxx rdfs:subPropertyOf ?yyy . ?yyy rdfs:subPropertyOf ?zzz }
# rdfs6
construct { ?xxx rdfs:subPropertyOf ?xxx } where { ?xxx a rdf:Property }
# rdfs7
construct { ?xxx ?bbb ?yyy } where { ?aaa rdfs:subPropertyOf ?bbb . ?xxx ?aaa ?yyy }
# rdfs8
construct { ?xxx rdfs:subClassOf rdfs:Resource } where { ?xxx a rdfs:Class }
# rdfs9
construct { ?zzz a ?yyy } where { ?xxx rdfs:subClassOf ?yyy . ?zzz a ?xxx }
#rdfs10
construct { ?xxx rdfs:subClassOf ?xxx } where { ?xxx a rdfs:Class }
# rdfs11
construct { ?xxx rdfs:subClassOf ?zzz } where { ?xxx rdfs:subClassOf ?yyy . ?yyy rdfs:subClassOf ?zzz }
# rdfs12
construct { ?xxx rdfs:subPropertyOf rdfs:member } where { ?xxx a rdfs:ContainerMembershipProperty }
# rdfs13
construct { ?xxx rdfs:subClassOf rdfs:Literal } where { ?xxx a rdfs:Datatype }

Executing them all together is a task for system that can coordinate the rules, and is typically tied to a specific database implementation though this is not necessary (e.g. Naga, though I have yet to port this to SPARQL).

Was This Needed?

Well… probably not. If you're reading this then maybe you already knew everything I had to say here. However, I also have more useful things to say, and I'm about to go on to say it. This further discussion will build on what I've discussed so far, and I wanted to establish a base of understanding before moving on.

I continue this discussion in my next post...

What Can't I do, as a Rule?

Paula Gearon — Mon, 22 Aug 2022 20:21:00 +0000

I have recently been working with graph databases again, and with OWL descriptions of information. This isn't just about a graph of information, but also about how the information is structured. It's similar to a schema in an RDBMS, but with more information.

Describing data in a graph and ontology uses a mathematical system called Description Logic (DL). In fact, it was a community of Description Logic researchers who came together to develop the OWL standard. The result is a system that can be obtuse to learn, but has a solid mathematical foundation without "bugs".

It also has the ability to do some unexpected things.

Oedipal Issues

There is an example provided in the Description Logic Handbook, referred to therein as the "Oedipus Problem". (See page 73 of this PDF of the 1st edition) A set of relationships around the mythical figure of Oedipus is described using DL, and then a complex question is asked that appears unanswerable at face value.

To start with, let's look at the DL data that is presented:

hasChild(IOKASTE, OEDIPUS)
hasChild(IOKASTE, POLYNEIKES)
hasChild(OEDIPUS, POLYNEIKES)
hasChild(POLYNEIKES, THERSANDROS)
Patricide(OEDIPUS)
¬Patricide(THERSANDROS)

This describes a rather messy family tree.

Oedipus is colored a light red to indicate that he killed his father (ie. he is a "Patricide"), while Thersandros is light blue to indicate that he did not kill his father (he is not a Patricide).

Each statement in the DL is presented as a "predicate". This is some kind of name followed by parentheses. The first one here is hasChild. Because it has 2 elements inside the parentheses, then it represents something called a role. The first line says that IOKASTE is connected by the role of hasChild to OEDIPUS, and you can see that I've indicated this in the diagram. By convention, roles will always start with a lower-case letter.

The last two lines have only a single element in the parentheses. These declare the class of something. The first one says that OEDIPUS is in the class of Patricide. This is just using DL syntax to describe that he killed his father. The second uses an operator that inverts the class, saying that THERSANDROS is in the class of anyone and anything that is not a Patricide. Again, this is using DL to explicitly state that Thersandros did not kill his father.

A Box

The data presented so far is what is referred to as instance data. The formal term for this is the ABox, which stands for "Assertion Box". This is like the data that might be found inside a table in an RDBMS.

This ABox contains 4 statements of hasChild, and 2 type statements: membership in the Patricide class, and membership of the class that indicates not-a-Patricide, which is indicated as the class of things that is everything that is not a Patricide.

T Box

What does not appear here is the ontology of the data, which is formally known as the TBox or "Terminology Box". This is similar to a database schema but also goes on to describe relationships between entities, relationships between relationships, properties of relationships, and more.

While the TBox has not been included, we can infer a little from the ABox:

We can see that there is a relationship called hasChild that connects elements in the domain.
We can see that these elements can be on either side of those relationships.
There is a class called Patricide.
Elements may be a member of Patricide or not. This indicates that those elements that are members of Patricide form a subset of the full domain of elements. We see this because THERSANDROS is an element, but is not a Patricide.

Open World

Consider how Thersandros is being explicitly declared as not being a member of the Patricide class. This is a result of the Open World Assumption (OWA), and may seem unusual when compared to the more common Closed World Assumption (CWA).

In the CWA, any data that is not explicitly stated is known to be false. For instance, both Iokaste and Polyneikes are not declared to be in the class of Patricide, and in the CWA this implies that they are not members of this class. The statement about Thersandros not being a Patricide would therefore be redundant. Most programming systems and databases work on this assumption, so developers are usually familiar with this paradigm.

In contrast, under the Open World Assumption any data that is not stated is instead unknown. At some point in the future, more information may be explicitly provided, or a reasoning process may determine new information. But until then, it is not valid to make any decisions based on unstated data.

The ¬Patricide(THERSANDROS) statement has been made under the OWA, so that we explicitly know that Thersandros is not in the Patricide class. We also know that Oedipus is a member of that class. But we have no information about whether Iokaste and Polyneikes are members.

The Question

The question that is posed is this:
Does IOKASTE have a child who is a Patricide, who, in turn, has a child who is not a Patricide?

This question can be posed in Description Logic with the expression:
(∃hasChild.(Patricide ⊓ ∃hasChild.¬Patricide))(IOKASTE) ?

For those who don't know the terminology, let's break it down, by using some substitution.

The expression:
Aoe(IOKASTE) ?
is asking if IOKASTE is a member of the class Aoe. We can then define Aoe as the class in our question:
Aoe ≡ ∃hasChild.(Patricide ⊓ ∃hasChild.¬Patricide)

(The ≡ symbol means "is equivalent to")

So now we need to break down the Aoe class. Let's substitute for the compound statement:

Aoe ≡ ∃hasChild.B
B ≡ Patricide ⊓ ∃hasChild.¬Patricide

This redefines Aoe in terms of B. This definition says that to be a member of Aoe an entity must have a hasChild relationship to an entity that is of type B. Breaking down B, we come to:

B ≡ Patricide ⊓ C
C ≡ ∃hasChild.¬Patricide

So to be a member of the B class, an entity must be both an instance of the Patricide class, and also the C class. The C class is actually compound, but small enough that I did not break it up further. This class defines an entity that has a child that is not a member of the Patricide class.

Solving for Aoe

To see if IOKASTE is a member of Aoe we can look to see if there is a hasChild relationship, and if one of those children is a member of the B class defined above.

IOKASTE has 2 children: OEDIPUS and POLYNEIKES. Let's consider each in turn.

The Oedipus Child

For OEDIPUS to be a member of B, he needs to be a Patricide and to be a member of C. OEDIPUS is declared as a Patricide, so now we consider he is a member of the C class. This requires a hasChild relationship to someone who is not in the Patricide class.

In this case, there is a hasChild relationship to POLYNEIKES, but there is no information to indicate if POLYNEIKES is a Patricide or not. This means that we cannot determine if the conditions are met.

Note that we have not determined that IOKASTE is not a member of Aoe. We just do not have sufficient information. POLYNEIKES is either a member of Patricide or she is not, and this will determine whether IOKASTE is a member of Aoe. If POLYNEIKES is not a member of Patricide, then the condition of Aoe(IOKASTE) will be met.

The Polyneikes Child

For POLYNEIKES to be a member of B, she needs to be a Patricide and to be a member of C. We don't know if she is a member of the Patricide class or not, but let's consider the C class.

To be in the C class, POLYNEIKES requires a hasChild relationship to someone who is not in the Patricide class. In this case, there is a hasChild relationship to THERSANDROS who is explicitly declared to be not in the Patricide class. So POLYNEIKES is indeed in the C class.

In this case, we also don't know if IOKASTE is a member of Aoe. Again, this is solely dependent on whether or not POLYNEIKES is a member of Patricide.

Solution

At face value, it appears that there is no way to answer the question of Aoe(IOKASTE), since all possible paths have an unknown element.

However, for the path through OEDIPUS, we know that Aoe(IOKASTE) is true if and only if ¬Patricide(POLYNEIKES). Meanwhile, for the path through POLYNEIKES, we know that Aoe(IOKASTE) is true if and only if Patricide(POLYNEIKES).

Patricide(POLYNEIKES) may only be true or false, meaning that Polyneikes is a member of the class or she isn't. There aren't any other possibilities. And since both possibilities result in Aoe(IOKASTE) being true, then this tells us that the condition is met.

The unusual thing here is that we don't know how the condition is met. We don't have complete information, but we do have enough information to show that the condition is true regardless of the unknown state.

Without Rules

A forward-chaining reasoner is one that relies on modus ponens and modus tollens. These are both mechanisms that take known information, and deduce new information. However, for the problem of determining Aoe(IOKASTE), the solution is arrived at through unknown state, meaning that forward-chained reasoners are unable to deduce the result.

Theoretically, in a limited case like this, it is possible to create rules for the solution. For instance, a predicate might be created that indicates "true, if X is true", or "true, if X is false", and then create a rule that returns true if both of these are asserted. However, this is limited to simple conditions on single variables. The constructs would quickly get unwieldy as the number of variables increased, and the possible states would explode combinatorially with many of these conditional predicates being asserted.

Rather than rules that create conditional assertions, logic engines like Prolog can explore these possibilities in memory. This can and does work, but this approach may also have difficulty in scaling as the number of states increases, and the logic engine has to search them all.

What I have discussed so far are proof procedures based on Natural Deduction and trees. Another approach is using a Semantic Tableaux. This considers the entire TBox as a series of logic expressions, along with the inverse of a statement that is being evaluated. The process then manipulates the logic expressions until the statement can be "proven". If it is shown to be false then the inverse was true, so the statement to be evaluated is true.

Let's get this back into concrete implementations.

RDF

The Resource Description Framework (RDF) is a graph data model, where each edge may also be considered to be a logic assertion of a binary predicate applied to each of the connected nodes.

For instance, a graph containing 2 nodes of A and B with a edge of E between them would appear as:

The logic representation of this is where the edge is considered a binary predicate:
E(A, B)
Unary predicates in description logic are a statement of an entity's type, and so RDF has created a specific predicate called rdf:type to represent this. For instance, saying that Oedipus is a Patricide has the logic representation of:
Patricide(OEDIPUS)
And appears in the RDF graph as:

This covers most of the ABox that was declared for the Iokaste problem, with the exception of Thersandros being declared as not being a member of Patricide.

OWL

While RDF is adequate for the ABox data, it is the TBox with its complex class descriptions that describes the question we are trying to answer. The Web Ontology Language (OWL) is a language that includes these descriptions, and is specifically designed to work with RDF data. OWL itself can be serialized into RDF and stored in a graph alongside the data it is describing.

Serializing in TTL

Using RDF and OWL, the complete ABox as well as the ¬Patricide class can be described in RDF, and serialized into a text format. I prefer to use the Terse Triples Language (Turtle) to serialize RDF, though several other formats exist.

@prefix : <http://demo.imo.com/oedipus#> .
@prefix owl: <http://www.w3.org/2002/07/owl#> .

:NotPatricide owl:complementOf :Patricide .

:_Iokaste :hasChild :_Oedipus ,
                    :_Polyneikes .
:_Oedipus :hasChild :_Polyneikes ;
          a :Patricide .
:_Polyneikes :hasChild :_Thersandros .
:_Thersandros a :NotPatricide .

This looks like the following:

Back to the Question

With this data in place, I ask about the Aoe class defined above if I add that class to my graph:

:Aoe owl:equivalentClass [
  a owl:Restriction ;
  owl:onProperty :hasChild ;
  owl:someValuesFrom [
    owl:intersectionOf (:Patricide
                         [a owl:Restriction ;
                          owl:someValuesFrom :NotPatricide ;
                          owl:onProperty :hasChild])]] .

This is a transliteration of the expression:
∃hasChild.(Patricide ⊓ ∃hasChild.¬Patricide)
into OWL, and was done using the serialization rules shown in the OWL2 Quick Reference Guide.

Reasoning

We can ask if Iokaste is a member of the Aoe class by using a SPARQL ASK query, with reasoning turned on:

@prefix : <http://demo.imo.com/oedipus#> .
ASK { :_Iokaste a :Aoe }

If we load this into an RDF database and issue the query we will get a result of: false

What? This took so long to get here! What went wrong?

The answer is that we need to enable reasoning. Not every database can handle this, and even fewer can deal with reasoning around incomplete data.

Stardog

To see a database that can manage this, let's look at Stardog. This is a commercial database, but it can be used for free on smaller datasets. Installation is well documented, and then the web-based UI is very capable, with lots of useful features (that can take a while to explore). Connecting to this UI link requests the address of your DB, connects into it, and gives you an easier interface than a command line.

Try putting the above ABox and definition of :Aoe into a file called oedipus.ttl, then it can be loaded into a new database that we will also call "oedipus":

$ stardog-admin db create -n oedipus oedipus.ttl

This should have an output like:

Bulk loading data to new database oedipus.
Loaded 19 triples to oedipus from 1 file(s) in 00:00:00.337 @ 0.1K triples/sec.
Successfully created database 'oedipus'.

Now try looking at the data:

$ stardog query execute oedipus 'select ?s ?p ?o {?s ?p ?o}'

+----------------------------------------------------+---------------------+----------------------------------------------------+
|                         s                          |          p          |                         o                          |
+----------------------------------------------------+---------------------+----------------------------------------------------+
| _:bnode_5f51466d_e100_4b91_b2ea_cf0a9bbc5477_61818 | owl:someValuesFrom  | :NotPatricide                                      |
| :_Thersandros                                      | rdf:type            | :NotPatricide                                      |
| :NotPatricide                                      | owl:complementOf    | :Patricide                                         |
| _:bnode_5f51466d_e100_4b91_b2ea_cf0a9bbc5477_61816 | rdf:first           | :Patricide                                         |
| :_Oedipus                                          | rdf:type            | :Patricide                                         |
| :Aoe                                               | owl:equivalentClass | _:bnode_5f51466d_e100_4b91_b2ea_cf0a9bbc5477_61814 |
| _:bnode_5f51466d_e100_4b91_b2ea_cf0a9bbc5477_61814 | rdf:type            | owl:Restriction                                    |
| _:bnode_5f51466d_e100_4b91_b2ea_cf0a9bbc5477_61818 | rdf:type            | owl:Restriction                                    |
| _:bnode_5f51466d_e100_4b91_b2ea_cf0a9bbc5477_61814 | owl:onProperty      | :hasChild                                          |
| _:bnode_5f51466d_e100_4b91_b2ea_cf0a9bbc5477_61818 | owl:onProperty      | :hasChild                                          |
| _:bnode_5f51466d_e100_4b91_b2ea_cf0a9bbc5477_61815 | owl:intersectionOf  | _:bnode_5f51466d_e100_4b91_b2ea_cf0a9bbc5477_61816 |
| _:bnode_5f51466d_e100_4b91_b2ea_cf0a9bbc5477_61816 | rdf:rest            | _:bnode_5f51466d_e100_4b91_b2ea_cf0a9bbc5477_61817 |
| _:bnode_5f51466d_e100_4b91_b2ea_cf0a9bbc5477_61817 | rdf:first           | _:bnode_5f51466d_e100_4b91_b2ea_cf0a9bbc5477_61818 |
| _:bnode_5f51466d_e100_4b91_b2ea_cf0a9bbc5477_61817 | rdf:rest            | rdf:nil                                            |
| _:bnode_5f51466d_e100_4b91_b2ea_cf0a9bbc5477_61814 | owl:someValuesFrom  | _:bnode_5f51466d_e100_4b91_b2ea_cf0a9bbc5477_61815 |
| :_Iokaste                                          | :hasChild           | :_Oedipus                                          |
| :_Iokaste                                          | :hasChild           | :_Polyneikes                                       |
| :_Oedipus                                          | :hasChild           | :_Polyneikes                                       |
| :_Polyneikes                                       | :hasChild           | :_Thersandros                                      |
+----------------------------------------------------+---------------------+----------------------------------------------------+
Query returned 19 results in 00:00:00.257

If we trace through all of these statements, we can see the blank nodes that were created in the construction of the :Aoe class, along with the intersection list and the restrictions.

Enable Reasoning

When reasoning is enabled, the TBox is used to describe the data, and direct the reasoning. Consequently, none of the TBox information should appear in the output. We see how this looks on the oedipus data by adding a -r flag:

$ stardog query execute -r oedipus "select ?s ?p ?o {?s ?p ?o}"

+---------------+-----------+---------------+
|       s       |     p     |       o       |
+---------------+-----------+---------------+
| :_Iokaste     | :hasChild | :_Oedipus     |
| :_Iokaste     | :hasChild | :_Polyneikes  |
| :_Oedipus     | :hasChild | :_Polyneikes  |
| :_Polyneikes  | :hasChild | :_Thersandros |
| :_Oedipus     | rdf:type  | :Patricide    |
| :_Thersandros | rdf:type  | :NotPatricide |
| :_Iokaste     | rdf:type  | owl:Thing     |
| :_Oedipus     | rdf:type  | owl:Thing     |
| :_Polyneikes  | rdf:type  | owl:Thing     |
| :_Thersandros | rdf:type  | owl:Thing     |
+---------------+-----------+---------------+

Query returned 10 results in 00:00:01.313

This is easier to follow, but the only new data is that all the instance data now has the type owl:Thing. That's correct, but not particularly interesting. And it doesn't infer any members for :Aoe.

Stardog can use different reasoning levels, and by default it uses a combination of RDFS, OWL QL, OWL RL, and OWL EL. This is very powerful, but it still doesn't handle the incomplete information from the Oedipus example. However, Stardog also supports the Pellet reasoner. This reasoner is fast and capable, though it can be limited in the scale that it can manage. Fortunately, our data set is tiny so that won't be a problem.

To switch to the Pellet reasoner, the database has to be taken down and then back up with the new reasoner setting:

$ stardog-admin db offline oedipus
The database oedipus is now offline.
$ stardog-admin metadata set -o reasoning.type=DL -- oedipus
The option(s) for the database 'oedipus' were successfully set.
$ stardog-admin db online oedipus
The database oedipus is now online.

Now we can look at the data again:

$ stardog query execute -r oedipus "select ?s ?p ?o {?s ?p ?o}"

+---------------+-----------+---------------+
|       s       |     p     |       o       |
+---------------+-----------+---------------+
| :_Oedipus     | :hasChild | :_Polyneikes  |
| :_Iokaste     | :hasChild | :_Oedipus     |
| :_Iokaste     | :hasChild | :_Polyneikes  |
| :_Polyneikes  | :hasChild | :_Thersandros |
| :_Oedipus     | rdf:type  | :Patricide    |
| :_Iokaste     | rdf:type  | :Aoe          |
| :_Oedipus     | rdf:type  | owl:Thing     |
| :_Thersandros | rdf:type  | owl:Thing     |
| :_Iokaste     | rdf:type  | owl:Thing     |
| :_Polyneikes  | rdf:type  | owl:Thing     |
| :_Thersandros | rdf:type  | :NotPatricide |
+---------------+-----------+---------------+

Query returned 11 results in 00:00:00.303

This includes a single new statement, saying :Aoe(:_Iokaste)

Now we can ask the original question:

$ stardog query execute -r oedipus "ASK {:_Iokaste a :Aoe}"
Result: true

Conclusion

This post explored description logics, and how they can be used to reason on incomplete data. It also demonstrated how the Web Ontology Language is used to encode Description Logic, and how this, in turn, can be represented as RDF. Finally, we used Pellet as an OWL reasoner to answer the original question.

Afterword: The above link for Pellet is to a paper in the Journal of Web Semantics. The system itself is open source and can be found on Github.

I discuss more of modeling data in RDF/OWL in my next post...

How fast is dc?

Paula Gearon — Tue, 12 Jul 2022 20:02:41 +0000

I was reading Tory Anderson's blog post on writing a fast Fibonacci calculator in Clojure. He uses a logarithmic algorithm to find the nth Fibonacci number, which was interesting, and something from SICP that I'd forgotten about.

Tory's code took about 56 minutes, though on my local machine here it was more like 10 minutes. That made me curious to think about what slows it down.

Tory went on to consider some optimizations, and looked at using memoize to cache function results. This is a simple improvement when using a naïve implementation, as per the tree recursion section in SICP, since it avoids recalculating the same values multiple times. However, the logarithmic algorithm only calculates each value once. We can see this if we add (println n) to the top of Tory's fib* function:

=> (fib 100)
100
50
25
12
6
3
1
0
354224848179261915075

This only executed the fib* function 8 times, with different arguments each time. Consequently, caching results won't change the performance at all.

Similarly, executing (fib 1000000000) will only execute fib* 31 times, which tells us that the recursive calls to fib* are not what takes time. Looking inside the function, we can see that all of the other operations are math, with no loops at all:

(let [[a b] (fib* (quot n 2))
      c (*' a (-' (*' 2 b) a))
      d (+' (*' b b) (*' a a))]
  (if (even? n)
    [c d]
    [d (+' c d)]))

This is all just division (via quot), multiplication, subtraction, and addition. These are typically fast operations, so why is it slow?

The answer is based in the size of the numbers being calculated. As we saw above, the 100th Fibonacci number is 21 digits long. This grows rapidly, and by the billionth number the size is hundreds of millions of digits long! 208,987,640 digits, in fact. This can't be calculated by standard number types, and needs a type like Java's BigInteger type, or Clojure's wrapper, BigInt.

The math operations on these numbers are taking a long time, so is there anything faster? Unless we want to build out own math library, then we should look for something that already exists. This made me think of dc, which is an arbitrary precision calculator that comes with most Unix-based systems. I seem to recall that this application was supposed to be fast. How would it compare?

Shells

The easiest way to try this would be to shell out of the JVM to execute the dc program, then communicate via a pipe. This is typically slow, but if the fib* function only gets called 31 times, and there are only a few functions in that function, then this time will be negligible when compared to the time for the math operations.

My first thought was, "Well, I know how to do that, but it will be fiddly. I'm sure it will take too long." And that was going to be that.

But after a minute, I started thinking, "I haven't tried to call anything through a shell for a long time. Maybe I can just try something simple?"

First of all, we want to see this operating on the command line. It uses reverse polish notation, which is a bit obtuse, but it does usually make for easier programming. The operations for dc can be provided in a script to execute via the -e operation, and the operations in the script here are:

Provide 2 numbers to place on the stack
Provide the operation +. This removes the top 2 numbers from the stack, adds them, and places the result on the top of the stack.
The p operation, which prints the value on the top of the stack

$ dc -e '2 3 +p'
5

Now, we just need to execute it from Clojure. We do this with the shell namespace, and each element of the command line is provided as a separate string parameter:

(require '[clojure.java.shell :as shell])
(shell/sh "dc" "-e" "2 3 +p")

The result of this is a structure containing stdout, stderr (as strings), and the exit code:

{:exit 0, :out "5\n", :err ""}

Everything is done with strings, and the final character needs to be truncated, but this is all tractable. So an addition function for BigInt is reasonably short:

(defn +n
 [a b]
 (let [{out :out} (shell/sh "dc" "-e" (str a " " b " +p"))]
   (bigint (subs out 0 (dec (count out))))))

I named it with n on the end, since Clojure BigInt values are printed with a trailing N.

Trying it out:

=> (+n 2 3)
5N

But why bother wrapping in a BigInt? All the math operations are go over the pipe, so the numbers have to be converted to strings anyway. It makes sense to just leave them as strings.

Using the above, we can generalize it to all of the required operations:

(defn op
  [o]
  (fn [a b]
    (let [{out :out} (sh/sh "dc" "-e" (str a " " b " " o "p"))]
      (subs out 0 (dec (count out))))))

(def +n (op "+"))
(def *n (op "*"))
(def -n (op "-"))
(def quotn (op "~r"))

We can also add in the string tests for even? and zero?:

(defn ev? [s] (even? (int (last s))))
(defn z? [n] (= "0" n))

(Note that the test for ev? is checking the ASCII value of the final digit, which is even for all even digits).

We can use these in Tory's function by tweaking it slightly:

(defn fibn* [n]
  (if (z? n)
    ["0" "1"]
    (let [[a b] (fibn* (quotn n "2"))
          c (*n a (-n (*n "2" b) a))
          d (+n (*n b b) (*n a a))]
      (if (ev? n)
        [c d]
        [d (+n c d)]))))

(defn fibn [n] (first (fibn* (str n))))

Since there are so many math operations in a row, then this could all be turned into a single dc script, but that is really taking us into dc programming, which isn't the point here. Instead, we're just trying to leverage the simple math operations on large numbers.

Testing it looks promising:

=> (map fibn (range 10))
("0" "1" "1" "2" "3" "5" "8" "13" "21" "34")

It takes a second, which I'd expect with so many calls through the shell, but it works.

Output problem

In fact, it works, all the way up to 332, when we get:

108245926205643306387794020096663813380901526766531123754208267893890\
9

It turns out that dc only prints out numbers to a width of 70 characters. Any numbers wider than that will broken up into multiple lines, with each line ending with a \ character.

We can flatten this back into a single line by using a string replacement:

(require '[clojure.java.shell :as shell])
(require '[clojure.string :as str])
(defn op
  [o]
  (fn [a b]
    (let [{out :out} (shell/sh "dc" "-e" (str a " " b " " o "p"))
          flat (str/replace out "\\\n" "")]
      (subs flat 0 (dec (count flat))))))

Comparison

Looking at the billionth Fibonacci takes a long time, so let's just compare the millionth number:

=> (def result1 (time (fibn 1000000)))
"Elapsed time: 773389.633083 msecs"
=> (def result2 (time (fib 1000000)))
"Elapsed time: 172.583417 msecs"
=> (= result2 (bigint result1))
true

At 773s compared to 172ms, the dc backed version is nearly 4500 times slower 🤣

There are 8 calls to math operations per invocation of fibn*, and 1,000,000 executes fibn* 20 times, for a total of 160 calls to the shell. Shelling out like this, along with the string processing involved in moving data across the pipe does take some time. Overall, it is taking a few seconds, but this is inconsequential when seeing that the majority of the 773 seconds are being taken up by dc doing the work.

Calling out a few of the later operations and running them directly in dc demonstrates that it just takes a long time when working with large numbers.

BigInteger

Clojure's clojure.lang.BigInt class wraps the Java java.math.BigInteger class. The main reason for this appears to be that small values will keep an equivalent long value cached, for fast operations on small values.

I've been looking at Java's BigInteger class recently, considering how to implement the same functionality for ClojureScript, so I have some sense of what it's trying to do.

I once saw an arbitrary precision math library manipulate numbers as strings of decimal digits. This worked well intuitively, since it means that operations like addition and multiplication can be performed using standard pencil-and-paper algorithms that are taught in school. But the principal benefit is that numbers can be parsed from a string or written back out trivially. However, decimal digits are stored in 8 bits, but only represent 3.25 bits of information. That's only about 40% storage efficiency.

By contrast, Java's BigInteger stores large numbers in binary. This stores 8 bits of information per byte, which is far denser. The same pencil-and-paper algorithms also work on numbers stored this way, but use symbols that range from 0-255, rather than 0-9. This is significantly faster to process, which is a major advantage.

However, parsing from and conversion back to a string are very expensive operations, as these are conversions between binary and decimal. For instance, executing (fib billion) on my machine takes 10.4 minutes to get the answer, but converting that answer into a string takes 25.6 minutes. That's nearly 2.5 times longer.

I suspect that parsing and printing are where dc is spending all of its time, especially since this is happening 20 times for each invocation of the fib* function. I should learn to write more complex dc operations, so I can run the entire algorithm in it.

Takeaways

What was the outcome of all this? Well, I lost an evening of my life. 😊

More seriously though, it helped me solidify my usage of calling out to a shell from Clojure.

Not mentioned above, I also tried using the spit function to emit the operations to files which I then passed to dc using the -f flag. This was useful for seeing what specific operations had been executed. It also helped me gauge exactly where in the operation the function had reached. This was what first alerted me to the fact that dc was taking a long time to execute basic operations. As mentioned, I expect that this was due to the parsing/printing phases of each invocation.

I also learned a bit more about performance when it comes to parsing and printing large numbers. Implementing this in JavaScript has bogged me down, due to the sheer complexity of it, and it's interesting to see that the computer is having as hard a time doing it as I am having in trying to write it.

I also had the opportunity to pull apart the logarithmic Fibonacci algorithm. I had skimmed this in my last reading of SICP, so I'm glad that I've taken the time to work through it now.

More Immutability and Clojure

Paula Gearon — Sun, 19 Jun 2022 02:47:44 +0000

This is the second part to my post on immutability and Clojure.

Missing State

One advantage to having mutability is the ability to accumulate state. For instance, let's look at some data to process in JavaScript:

const data = [
  {label: "twilight", values: [10.0, 15.3]},
  {label: "apple", values: [12.0, 11.5, 18.1]},
  {label: "dash", values: [18.0]},
  {label: "pie", values: [13.0, 13.2, 44.8, 15.5]}
]

Consider how we might get the average of all of those values. This can be done in multiple ways, but a straightforward approach is to accumulate the sum of all the values, while also accumulating the count.

let total = 0
let count = 0
data.forEach(function(d) {
  d.values.forEach(v => total += v)
  count += d.values.length
})
console.log("Average: " + (total / count))

Average: 17.14

These accumulating values represent state, which the principles of immutability are trying to avoid. How might the same task be done without accumulating values like this?

Immutable in JavaScript

Rather than jumping straight to Clojure, let's look at this in JavaScript.

We need a total, and we need a total count. One way to get these is with the reduce operation to process an array into a single value. Let's start by creating a function that can add all the numbers in an array:

function sum(array) {
  return array.reduce((accumulator, element) => accumulator += element, 0)
}

The accumulator here gets initialized with the 0 parameter, and is passed in as an argument for the arrow function at each step.
We can test this on a short array:

console.log(sum([1, 2, 3, 4, 5]))

This can be used to sum the numbers across all the arrays:

const total = data.reduce((acc, element) => acc += sum(element.values), 0)

We can add the counts similarly:

const count = data.reduce((acc, element) => acc += element.values.length, 0)

This gives us the same answer:

console.log("Average: " + (total / count))

Average: 17.14

However, the data had to be processed twice, once for calculating the total sum, and once for calculating the count. This could have serious ramifications if the data were particularly large, or if the processing were some other operation that required time-consuming I/O.

Immutable in Clojure

Before addressing this, let's look at the same operations and data in Clojure:

(def data [
  {:label "twilight", :values [10.0, 15.3]}
  {:label "apple", :values [12.0, 11.5, 18.1]}
  {:label "dash", :values [18.0]}
  {:label "pie", :values [13.0, 13.2, 44.8, 15.5]}])

The sum function can be done a couple of ways, but if we stick to reduce:

(defn sum [array] (reduce + array))

Now we can do the total and count. Clojure has some options that could make this easier, but transliterating the JavaScript gives:

(let [total (reduce (fn [acc element] (+ acc (sum (:values element)))) 0 data)
      total-count (reduce (fn [acc element] (+ acc (count (:values element)))) 0 data)]
  (println "Average:" (/ total total-count)))

Average: 17.14

count is actually the name of the function in Clojure for getting the number of elements in something, so the var here has been renamed to total-count, but otherwise it's the same approach.

Regaining State

As mentioned above, each call to reduce is processing the data sequence again, which leads to redundant work. Instead, we want to be accumulating both values while processing the data. This can be done by accepting and returning both values at each step.

(let [[total total-count]
      (reduce (fn [[previous-total previous-count] element]
                [(+ previous-total (sum (:values element)))
                 (+ previous-count (count (:values element)))])
              [0 0] data)]
  (println "Average:" (/ total total-count)))

There are a few things to notice here:

The function passed to reduce still takes 2 arguments.
The first argument to the function is "unpacked" into a pair of values.
The value returned from the function is a 2 element vector.
The "initial value" provided to reduce is also a 2 element vector containing the 2 initial values (both zero).
The final result of the reduce is a 2 element vector, which gets unpacked into the total and total-count.

This approach to returning multiple values is something that JavaScript also supports, and is similar to using tuples to return multiple values in Python. Other languages, like Java, struggle with this, resorting to cumbersome constructs like:

return new double[] { newTotal, newCount };

And without an unpacking syntax, this becomes:

var result = callFunction();
double total = result[0];
double count = result[1];

It works, and internally it's the same sort of thing that Clojure is doing, but it's messy to write, harder to read, and is also one of the many reasons why I stopped coding Java.

Regardless of the language, the state of the process is being accumulated in multiple values. At each step, the entire state is packaged up and passed in as a single parameter, along with the new data to process, and a packaged new state is returned.

A More Structured Approach

Vectors and tuples are not the only data structure that can be used to return multiple items that represent state. Clojure's map syntax is also useful, particularly as it allows each part of the state to be named:

(let [{:keys [total total-count]}
      (reduce (fn [{:keys [total total-count]} element]
                {:total (+ previous-total (sum (:values element)))
                 :total-count (+ previous-count (count (:values element)))})
              {:total 0 :total-count 0} data)]
  (println "Average:" (/ total total-count)))

In a simple case like this, a vector makes more sense to accumulate the state, but as the state becomes larger and more complex, using a map to encapsulate the state begins to gain value.

When Mutation Makes Sense

While mutation leads to greater complexity of state, there are occasions when mutation can be useful. The most common structures for this are Atoms and Volatiles.

Mutation is rarely needed, meaning that when mutation starts to become useful the code is often more complex that simple examples. Consequently, the examples below are more complex than what I've presented before now. I have included them to show that Clojure can still make use of mutation, even while preferring immutable structures.

Counter Example

A counter could theoretically be kept in an immutable state map, but this would need to be passed around everywhere, which would be both cumbersome and would slow down the program. It is also possible to accidentally pass in an old state, thereby returning a duplicate number. Instead, a global mutating counter would be ideal for this task.

The Clojure Runtime has an internal nextID function to return a number that is always greater than previously returned values. The function is used internally by the gensym function. The user can even call it themselves:

(println (clojure.lang.RT/nextID))
(println (clojure.lang.RT/nextID))

172
175

This could instead be implemented in Clojure using an Atom:

(def ^:private last-id (atom 0))

(defn next-id [] (swap! last-id inc))

While Clojure actually implements this in Java, ClojureScript does it in native ClojureScript code with an atom.

The code above initializes the atom to 0, then every time the next-id function is called the number in the atom gets incremented and returned.

An atom is used here, because the operation could be called from anywhere, including in multiple threads at the same time. Atoms have very important properties that make them thread safe, meaning that multi-threaded applications won't encounter problems like duplicate values, or bad data.

Caching Example

Similarly, a mutating map containing a cache can be easier to manage than passing the cache in and out of every function that needs it.

Clojure's memoize function attaches an atom to a function to return previously calculated values. This can be valuable for expensive operations.

For instance, a function that naively calculates the nth Fibonacci number has exponential complexity:

(defn fib [n] (if (< n 2) n (+ (fib (dec n)) (fib (- n 2)))))

This will work fine up to 30 or so, but after that you will start seeing delays. On my notebook, calling (fib 45) will take over 9 seconds. If I run it with an argument of 50 then it takes over 10 minutes. The SICP book has a good explanation of why this is exponential.

But if the function is memoized, then large numbers can be evaluated quickly without having to change the algorithm. We can do this by changing from defn to using an equivalent def/fn pair, and wrapping the function definition in a call to memoize.

(def fib (memoize (fn [n] (if (< n 2) n (+ (fib (dec n)) (fib (- n 2)))))))

Now we can call (fib 90) and it will return immediately.

The code for memoize is relatively short:

(defn memoize
  [f]
  (let [mem (atom {})]
    (fn [& args]
      (if-let [e (find @mem args)]
        (val e)
        (let [ret (apply f args)]
          (swap! mem assoc args ret)
          ret)))))

memoize returns a new function within the scope of an atom called mem. This atom contains a map which uses a sequence of function arguments as the keys, and previously calculated values as the mapped vals. If an entry for a seq of arguments doesn't exist, then those arguments are new. That leads to the original function getting run on the arguments, and the result gets stored in the atom's map before being returned.

core.cache Example

Understanding how to attach an atom to a function like this is very useful if you want a more intelligent cache, such as with core.cache. This library provides immutable objects, much like an immutable map, which can be held in an atom in a similar way to how memoize does it.

This is stepping up a level in complexity, but since I'm here, the following is a function that performs a similar job as memoize, but with an LRU cache from the core.cache library.

(require '[clojure.core.cache :as cache])
(defn lru-memoize
  [f]
  (let [mem (atom (cache/lru-cache-factory {}))]
    (fn [& args]
      (let [e (cache/lookup @mem args ::nil)]
        (if (= ::nil e)
          (let [ret (apply f args)]
            (swap! mem cache/miss args ret)
            ret)
          (do
            (swap! mem cache/hit args)
            e))))))

By default, this holds up to 32 items in the cache, though it can be customized with an extra parameter to the lru-cache-factory function.

Local Mutation

The above examples show mutation at a global scale (or, potentially global, if a memoized function is to be accessible from anywhere). Because the scope of access is open, then the mutating objects must be thread-safe. But there are occasions where mutation might occur within a controlled block of code. In such cases, the small overhead associated with thread safety may be avoided by using a Volatile object.

Volatiles are implemented as a simple object in the host system (Java, JavaScript, C#, Dart, etc) with a single mutable field. To see how simple the implementation is, the Java version is:

final public class Volatile implements IDeref {
  volatile Object val;

  public Volatile(Object val) {
    this.val = val;
  }

  public Object deref() {
    return val;
  }

  public Object reset(Object newval) {
    return this.val = newval;
  }
}

There's not much to it: You can create it, read the value in it, and change the value in it. This is the same as an Atom, but is not thread safe.

A Quick Discussion on Races

What do I mean by "not thread safe"? Notice how there are operations to read the value (via deref) and write to the value (via reset). This is no way to read a value and write back to it before another thread has a chance to change it on you. When a thread is trying to write a value before another thread can get to it, then this is referred to as a race. Races are bad.

As a simple example, consider an atom a with a number in it. If one thread (started with future) increments that number a large number of times, and another thread decrements it the same number of times, then we should see the original number come out at the end:

(let [a (atom 0)]
  (future (dotimes [n 100000] (swap! a inc)))
  (dotimes [n 100000] (swap! a dec))
  (Thread/sleep 500) ;; more than enough time to wait
  (println "Final value:" (deref a)))

Final value: 0

The first thread should finish at around the same time as the main thread, but I added a short wait to ensure that it does. The operations take 80ms on my notebook, so half a second is ample time, and we can see that the final value is what we expected.

However, volatiles don't provide the guarantees that atoms do:

(let [a (volatile! 0)]
  (future (dotimes [n 100000] (vswap! a inc)))
  (dotimes [n 100000] (vswap! a dec))
  (Thread/sleep 500) ;; more than enough time to wait
  (println "Final value:" (deref a)))

Final value: 6475

This number will be different every time, and is certainly not the 0 that was expected.

Incidentally, the time it takes my machine to run both threads operating on volatiles like this is 15ms. That's a lot faster than the 80ms that the atom implementation took, which is why volatiles are attractive.

Where Volatiles Make Sense

Since volatiles are not thread safe, it is important that they are only used in a context that cannot be accessed from outside the current thread. A typical example is within the confines of a function or let block.

One example might be to use a volatile to record information while processing data for another purpose. Let's start by creating a sequence of 1000 random numbers, from 0 to 100:

(def data (repeatedly 1000 #(rand-int 100)))

Let's determine the sum of these numbers, but on the way, count how many of them are divisible by 7:

(let [sevens (volatile! 0)
      total (reduce (fn [acc n]
                      (when (zero? (mod n 7))
                        (vswap! sevens inc))
                      (+ acc n))
                    0 data)]
  (println "total:" total "sevens:" @sevens))

Can this be done with extra state in the accumulator? Certainly. But as complexity of the code increases, then having state on the side like this can help to simplify. It can also be faster than creating temporary objects that contain the updated state.

Transducers

One of the most important reasons for using volatile values is for maintaining state throughout a process. The most common example of this is in Transducers. These are a group of functions that are used for processing a sequence, with one function handling the start, another handling the end, and a function for handling each element in the sequence.

If there is a need for a sequence processor to remember what it has already done, then the transducer can use a volatile to do it. One example of this is the dedupe function. It looks like this:

(defn dedupe
  ([]
   (fn [rf]
     (let [pv (volatile! ::none)]
       (fn
         ([] (rf))
         ([result] (rf result))
         ([result input]
            (let [prior @pv]
              (vreset! pv input)
              (if (= prior input)
                result
                (rf result input))))))))
  ([coll] (sequence (dedupe) coll)))

Most of this is boilerplate for a transducer, but notice the let block that declares the pv var as a volatile.

The 2-argument form of the transducer does the following:

Looks up the prior value, which is stored in the volatile.
Update the prior value to the current value.
If it equals the current value, then return the result unchanged.
Otherwise, the current value is different to the prior value, so add it to the result.

Other built-in transducers use volatiles to store state as well. take and drop use a volatile to count how many items they have iterated over. map-indexed uses a volatile to remember the current index value. distinct uses a volatile to remember everything that it has already returned so that it never returns the same value twice.

If you ever need to create a transducer that can remember state between elements, then be sure to reference the code in clojure.core to see how it was done there.

Wrap Up

This was a much more advanced look at immutability and mutability in Clojure.

We started by looking at how state can be remembered by accepting and returning state at each stage of processing. State can be stored in any kind of structure, and is typically a vector when the state is small, or a map when the complexity of the state increases. These state objects are often destructured by the code that processes them.

We then started looking at cases where mutability is useful, and some of the tools that Clojure provides for this. When data is globally accessible, or can be accessed in multiple threads, then mutable data will usually be stored in an Atom. But when the scope of this data is constrained, then a Volatile can be used instead. Volatiles work just like Atoms, but are not thread safe.

Afterword

This is much more complicated than my original introduction to immutability. I felt that it was necessary to describe the more complex cases that inevitably arise, and also the flexibility that Clojure offers when mutability really is the best tool for the job.

Again, I would appreciate any questions or complaints about this, to help improve the explanation.

Immutable Vars and Clojure

Paula Gearon — Sat, 18 Jun 2022 00:02:43 +0000

People often feel at a loss when they first look at languages with immutability. I know I did. How can you write a program without changing the value of a variable?

Mutable

First of all, what does it mean to change a variable? Consider some simple JavaScript:

var x = 5
x = x + 3

This creates a variable called x that contains the number 5. The second line changes the value of x to itself plus 3, which means that it gets changed to the number 8.

This works, though the choice of the "equals" sign in languages like JavaScript is a bit awkward.

If you were in high school algebra class and you saw:

x = x + 3

…you'd probably throw your hands up in despair. When looking at math, we expect x to be described by a set of conditions, where = can be used as part of that description. This statement can't be true, since a number x can't be equal to itself plus 3. This is why some languages won't use a simple = character when changing a variable. For instance, Pascal uses :=, R uses an arrow <-, and many computer science texts use an arrow character ←.

Math provides a powerful way to look at the world, and it includes this idea of values that meet a condition, and don't change. Conversely, anyone with significant experience debugging a program has seen variables change unexpectedly. When the state of your application is based on the values in its variables, then this means that understanding the current state can get very difficult when those variables change. Perhaps the idea of values that don't change could be useful.

Immutable

How does this compare to using immutable values?

JavaScript lets you create immutable values with the const declaration. This means that we can't change the value:

const x = 5
x = x + 3

Which results in:
Uncaught TypeError: Assignment to constant variable.

Instead, we have to declare a whole new thing to take the new value:

const x = 5
const y = x + 3

This is limited, but it's more flexible than you might expect.

Shadowing

You can even re-use the name x in other parts of the code, without changing the original value. This is called shadowing. In JavaScript this must be done in a new scope:

const x = 5
const y = x + 3
{ // a new scope
  const x = y + 1
  console.log("the new value is: " + x)
}
console.log("the old value is still: " + x)

the new value is: 9
the old value is still: 5

Inside that new scope, the value of x is set to 9, but in the outer scope it remains at 5.

But we never print y so why not just skip that and add x to itself? Well, it turns out that JavaScript thinks that all references to x in the inner scope are referring to the x that's already in that scope, which means that the declaration of x can't refer to itself:

const x = 5
{
  const x = x + 3 + 1
  console.log("the value is: " + x)
}

Uncaught ReferenceError: "x" is not defined

JavaScript can use immutable variables, but it isn't entirely smooth.

Clojure

In contrast, languages like Haskell, Erlang, Scala and Clojure are designed to make using immutability natural. They often have some way to allow mutability where it can help, but these are typically awkward to use, or in the case of Haskell, simply not there.

In Clojure we don't have "variables" anymore. Instead, the thing that holds a value is called a "var". These can be declared globally with def. There are operations that can modify a var, but they should generally be avoided. Those operations can be used to patch or temporarily modify code that is not in your control, but that sort of thing is typically only necessary in libraries or testing.

In a local scope, we declare values via let. These are just local names for things and cannot be varied at all.

Like all Lisps, operations like let are enclosed in parentheses. The values to be created appear first, inside an array, with the name immediately before the value it will be set to:

(let [x 5]
  (println "value is:" x))

value is: 5

Shadowing is even easier than JavaScript, since the old value of x will be used until the new value is finished being defined:

(let [x 5]
  (let [x (+ x 3 1)]
    (println "The new value is:" x))
  (println "This old value is still:" x))

The new value is: 9
This old value is still: 5

But we don't necessarily need that old, outer value. When that happens, we don't need the separate scopes, and we can let the x multiple times:

(let [x 5
      x (+ x 3)
      x (+ x 1)]
  (println "value:" x))

value: 9

This was made using 3 different values for x, with each one shadowing the previous one. It's not the way I like to write code myself (mostly because I like to have access to the various values of x, and not have them hidden when they get shadowed), but this demonstrates let makes shadowing easy.

Loops

Just like shadowing, some loop constructs allow you to reuse a name with a new value each time. For instance, we can vary x from 0 to 4 and get the squares:

(for [x (range 5)]
  (* x x))

(0 1 4 9 16)

Each time going through this for construct, the value of x will be set to something new. But unlike JavaScript, it has not changed a variable called x. It's an entirely new x each time.

In a similar way, we can use a loop:

(loop [x 0]
  (when (< x 5)
    (print (* x x))  ;; output a single number
    (recur (+ x 1))))
(println)  ;; ends the line of output with a newline

0 1 4 9 16

The first time through the loop, the initial vector acts like a let where x has been set to 0. Then, each time recur is called, the loop acts like a let again, only instead of 0 the x will be set to whatever value the recur was given.

Structures

Immutability takes on a new meaning when applied to a structure. For instance, consider an array in JavaScript:

const a = [1, 2, 3]
console.log(a)
a.push(4)
console.log(a)

[ 1, 2, 3 ]
[ 1, 2, 3, 4 ]

How did the array a change when it was declared const? It happened because a continued to point to the same array, but the push operation changed what was in that array. This is like referring to a closet, but hanging up more clothes in there. The closet doesn't change, but the contents of the closet do.

However, languages like Clojure and Scala also offer immutable structures:

(let [a [1 2 3]
      a (conj a 4)]
  (println a))

[1 2 3 4]

Well, we can see that we shadowed a, but how do we know if changed the original or not? Let's not shadow it, and print the original object after the extra number was added:

(let [a1 [1 2 3]
      a2 (conj a1 4)]
  (println "original array:" a1)
  (println "new array:" a2))

original array: [1 2 3]
new array: [1 2 3 4]

This works with all of Clojure's structured types. For instance, maps have new items associated with it, via the assoc function:

(let [m1 {:one 1
          :two 2
          :three 3}
      m2 (assoc m1 :four 4
                   :five 5)]
  (println "original map:" m1)
  (println "new map:" m2))

original map: {:one 1, :two 2, :three 3}
new map: {:one 1, :two 2, :three 3, :four 4, :five 5}

The most important aspect of this behavior is that operations which modify a structure will return the new structure, since the original structure does not change. This is different to structures that mutate. Consider the array in JavaScript:

const a = [1, 2, 3]
console.log(a.push(4))

This push operation doesn't return the new array. Instead, it returns the value that was added to the array. That's OK, because we can go back to the object referred to by a and see that the array has this change. But for immutable structures, the only time you can get access to the new structure after an operation is in the return value of that operation.

Immutable Values with Immutable Structures

Using some of the above examples we can build a structure that is referred to with immutable values. For instance, a loop can be used to build a vector containing squares:

(loop [v []
       i 0]
  (if (> i 10)
     v  ;; i is greater than 10, so return v
     (recur (conj v (* i i)) (+ i 1))))

[0 1 4 9 16 25 36 49 64 81 100]

While this works, it is also a bit clunky. Typically, when adding lots of things to a single object, the correct way to do it in Clojure is to use the reduce function. This needs a function that accepts your structure plus another argument, and is expected to return the new structure. For instance, the above example would use a function that takes a vector and a number, then returns a new vector that has the square of the number added. Like:

(defn the-function
 [v n]
 (conj v (* n n)))

We can test it out by giving it a small vector and a number, and see if the square of that number is added to the end:

(the-function [0 1] 2)

[0 1 4]

The reduce function can use this for each number in the range 0 to 10 (up to, but excluding, 11):

(reduce
  the-function
  []           ;; the starting structure
  (range 11))  ;; the numbers to process, from 0 to 10

[0 1 4 9 16 25 36 49 64 81 100]

This does essentially the same as the original loop above, but now the operations are more structured.

NB: This code is to demonstrate a point. Building this vector in real code would be better done with a mapv over the range.

Size

An intuition that many people develop around this is that the structures are being copied, and then the copy gets modified. While this would work, a copy has the disadvantages of doubling the space consumption of the original, and requires all of the data to be processed, which could be slow when a structure gets large. Creating a vector of 1 million items by adding a single item at a time would create 1 million intermediate vectors, with a total of 500,000,500,000 elements between them.

Instead, Clojure structures use "structural sharing". This means that a new structure can be a reference to the data in the previous structure, and only contain whatever changes it requires. This saves on both space and processing time. There are even internal operations in Clojure that can skip many intermediate steps when processing large blocks of data, thereby making the operation more efficient.

This approach wouldn't work if structures were mutable. For instance, consider a map m containing 10 items and then map n is created by adding a new item to m. Internally, n has a reference to m and its single new item, giving it a total of 11 items. The diagram below shows this, and also shows the effective structure that n represents.

If we were in a mutable system and we took away something from m, then m would be down to 9 items. n still contains its reference to m plus its extra item, so now n has also been modified, and ends up with only 10 items in total. In this example, we can see that the number 9 is removed from the end of m, so this is also removed from n.

Anyone debugging such a system may be confused as to why n was changed, because nothing appeared to change n! But because Clojure's structures don't change, then structural sharing works cleanly.

If you really, really want to know how structural sharing works, I gave a talk on this at :clojureD 2021.

Wrap Up

This was an initial attempt to describe how programming is still possible when variables and data can't be changed, and to show how this can be done in Clojure.

Clojure uses Vars and values that don't change, rather than Variables that do. New values with existing names can be used, and these will hide (or shadow) the previous value (or even a var) with that name. Often times, a piece of code will be run many times with its value names set to different values, such as in a loop, but at no point will an existing var or value be changed inside that block.

Clojure data structures are also immutable, in that their contents never change. The effect of a change is done by creating a new structure with the desired change, and the old structure is often abandoned (though it can also be useful to keep the old structures on occasion, especially for debugging).

Changed structures look like a copy of their predecessor, with a modification. However, this is handled much more efficiently than a copy would imply.

Afterword

Immutability is something that stops people when they first come to functional languages, so I would like to work on explaining it for people making the shift. Personally, I learned about it when I first picked up the Scala language, so none of this is unique to Clojure.

This is my first attempt at explaining this topic, so I'm expecting that I haven't done a great job of it. I would appreciate feedback on the parts that work and the parts that are confusing. Meanwhile, if I left you feeling bewildered, try reading the same topic in "Programming in Scala" by Odersky, Spoon, Venners and Sommers.

Asami

Paula Gearon — Mon, 08 Feb 2021 23:22:39 +0000

Motivation

For a long time, I had been thinking that I would like to redesign Mulgara storage to overcome some of the deficiencies that had become clear over time. I was also thinking that I would like to use a more Functional approach, to make the code more tractable and reliable. But this would still take a lot of work that I wasn't sure I wanted to apply.

In 2008 I came up with some new index designs and had started implementing these for Mulgara. They were showing some promise, but still had a long way to go. However, a change of job soon had me ignoring storage and looking a rules systems again.

Rules

My original implementation of a Rules engine was in Mulgara, and hence was built in Java. My second was on a SPARQL store (I tried a few, but mostly was using Jena Fuseki). This was at the company Revelytix, which gave me an opportunity to use Clojure for the first time. I'd learned Scheme through SICP some years before, I'd adopted a lot of Functional Programming principles, and I'd learned Haskell and Scala, but Clojure was the first time I felt I was really productive with these concepts.

In 2013 I started re-implementing some of Mulgara's memory-mapping approach using Clojure and got the basic idea of blocks working. This was important for abstracting disk access, particularly as it allows memory-mapping files beyond the 2GB limit that Jave imposes due to backward compatibility with 32-bit architecture. Once this was done I didn't take it further at the time.

It was while using Clojure with OrientDB, Datomic and Neo4J, that I started getting a feel for graph databases that weren't based on RDF and SPARQL. They are all very similar in many ways, and it occurred to me that I could build a graph rules engine that was abstracted from the database, only requiring an adapter for each type. With this in mind, I started building a new rules engine, with an initial adapter for Datomic.

I was pleased with how well this worked and showed my then-boss, Craig while we waiting in an airport together. He was very interested in it and asked me if I would be prepared to develop it for Cisco. I agreed, so long as I could keep it open source, which Craig was pleased to do. Thus, Naga was born.

Craig did have one request though. He did not want to tie this to a commercial database, so would I be able to build something of my own? At this point, neither of us were aware that Datascript had been started, or else I would have opted to use that.

My first thought was just how big a project Mulgara had become, but then I realized that the only features I needed were:

Index lookups by triple-pattern.
Counting the size of the results of index lookups.
Inner join operations.

I didn't even need to do this in storage. I could handle all of this in memory, and if I wanted to scale up, then that's when I could move to an existing database. So I agreed.

The first version worked well and was the basis for the talk I gave on Naga at Clojure/conj 2016. The code for this was also small:

The index was a simple nested-map structure. Rather than storing triples in sequence, this allows duplicates in the first columns to be skipped. Also, the values appeared directly in the statements, and were not mapped to numbers.
The join operation was a relatively easy nested loop, using techniques borrowed from Mulgara.

I also realized that since queries were being machine-generated, then there should be a query planner to ensure that they did not get executed in an inefficient order. This appeared in the same namespace as the rest of the query processing.

Asami

Shortly after presenting Naga in Austin Craig started asking for new features. The first one was to make it compatible with ClojureScript so that we could use it directly in a web page instead of through a service. I had only experimented with ClojureScript, so this was an opportunity to use it in production.

Then I was asked for more features, both in rules and in querying the resulting data, which meant implementing a much more capable query engine, and query planner. As the code started to expand, I realized that the database had taken on a life of its own, and so I split it into its own project. In keeping with our in-joke of a naming scheme based on the Avatar and Korra cartoons, I named the new database "Asami".

I liked this name, since the character of Asami doesn't have powers like the other characters do, so she builds her own devices to make up for it. 😊

Querying

The first step was to provide an API for querying Asami with something that wasn't as low-level as the original approach. I copied the Datomic syntax for this, as it was compatible with how I was representing queries already, and it did not require parsing.

This made it easier to introduce syntax for new queries and then building the implementation. Some of the new features here are:

Negations, via the not operator.
Disjunctions, via the or operator.
Nested Conjunctions, via the and operator.
Filter expressions.
Binding expressions.
Passing data into a query to bind to a value.
Aggregates, via the functions: count, sum, avg, first, last, max, min.

Most of these operations are performed in a similar way to Mulgara, though I've reimplemented everything from first principles.

An important point to note here is that most (not all!) of the files that implement the above in Mulgara total 11,251 lines of Java. Asami does it in 783 lines of Clojure.

This illustrates a few things:

Clojure allows for symbolic manipulation far more easily than Java.
Java manages data structures through individual classes, which takes a lot of boilerplate code. In Clojure, it is more natural to use the built-in data structures, which simplifies things greatly.
I could never have attempted this as an individual without a functional language with the facilities that Clojure offers.

Storage

Mulgara executes queries by requesting statements that match statement patterns and then performing various operations on each of these results.

The statement patterns, or constraints are typically in the form of a triple, (with a fourth value implied from context or simply not needed). They contain ground values (such as URIs or strings), and variables. We refer to finding the statements that match a pattern as resolving the pattern. A pattern resolution binds the variables in the pattern to the parts of the statements that match it.

For instance, in the following statements:

:a :first-name "Fitzwilliam"
:a :last-name "Darcy"
:a :friend :c
:b :first-name "Elizabeth"
:b :last-name "Bennet"
:c :first-name "Charles"
:c :last-name "Bingley"

Then the constraint pattern: [?person :first-name ?name]
would resolve to the statements:

:a :first-name "Fitzwilliam"
:b :first-name "Elizabeth"
:c :first-name "Charles"

The bindings would be pairwise for the variables of ?person and ?name:

{?person = :a, ?name = "Fitzwilliam"}
{?person = :b, ?name = "Elizabeth"}
{?person = :c, ?name = "Charles"}

Queries are answered by resolving constraint patterns and combining the results according to the operations in the query. I presented a talk describing the operation of this at ClojureD in 2019.

The operations are part of the "Query Engine", and the resolution step is part of an API for talking to storage. This abstraction makes it possible to store the data in various ways, or even to reinterpret other data as a graph, so long as an API can be implemented to resolve constraint patterns into bindings.

Mulgara has a Resolver interface to describe this API. Asami adopts the same approach, using the Graph protocol.

Mulgara has a number of Resolver implementations, including the transactional store, an RDF document parser, relational databases, GIS information, Lucene data, in-memory data, network-accessible APIs, and many more.

The first Graph implementation for Asami was a simple in-memory data structure, described in my ClojureD talk. The code for this appears in asami.index. This file started much smaller (as referenced above), but has since expanded with the needs extended functionality, such as transactions, and transitive closure operations.

Some of the API needs of our project at Cisco required a weighting for various edges, so a second Graph in-memory structure that could record multiples of the same edges (a so-called "Multi Graph"). This is found in asami.multi-graph.

Asami is in the process of gaining a new set of Graph implementations, based on structures inspired by Mulgara, though with some major differences. The first is that the blocks are not necessarily backed by files, and the second is reduced complexity, fewer operations, improved efficiency, and greater utility. My next post will be about this, but the general structure is already documented on the Asami Wiki.

The astute reader may notice a few differences from Mulgara already, but I intend to explain why those differences exist, and the benefits they confer.

Asami Background #2

Paula Gearon — Mon, 08 Feb 2021 18:23:06 +0000

Mulgara (again)

During my last post, I wanted to start writing about what Asami does, rather than dwelling on the structure of Mulgara, but in so doing I missed an important part of the structure: The Statement Store. Asami uses a similar statement store, so I think it deserves a little time.

This post will be full of heavy detail. It's a useful exercise for me to write this since it's helping me review how Mulgara handles storage, and also because Asami is very similar.

Indexes

As described in the previous post, Mulgara uses 6 separate indexes to store quads. Each one of these indices starts with an AVL tree, where the payload in each node stores the following:

A reference to a data block in another file.
The count of statements in that block.
The first statement in the block.
The last statement in the block.

As you can see, each node in the tree is associated with a block in another file. That block contains statements as a series of 4x64-bit long values, up to the number of triples in that block. There is a 1:1 correspondence of AVL Nodes to blocks.

The best way to describe this structure is to describe the operations on it.

Search

Search is based on constraint patterns. For instance, a constraint pattern that describes which predicate connects a given subject A and object of B would be represented with a pattern like:
A ?predicate B

Given that this provides the subject and object, but not the predicate (nor the graph), then these statements could be found using the index ordered by:
object,subject,predicate,graph

The object comes first on this index, so the search becomes:
B A * *
Where the first * represents the ?predicate value, and the second is the unused graph.

Starting at the root of the AVL Tree, this pattern is compared to the "first", or “low” statement for the node. If it's lower, then the search continues on the left child node. Otherwise, the pattern is compared to the "last", or “high” statement for the node, and if it's higher then the search continues on the right child node.

It is possible for a pattern to compare as being between blocks, in which case there are no matching statements. But usually, a node is reached where the pattern is higher than the "first" statement and lower than the "last" statement, so anything the pattern could match must be within the range of the associated block.

At this point, the block is loaded from its file and the search continues there. The statements appear as a linear array of numbers, with each 4th number being the start of the next statement. A binary search finds the appropriate statement quickly.

If an exact match is found for the pattern, then the location of the first statement that matches is returned in a 1 element array. If no match is found, then a pair of consecutive locations are returned in a 2 element array. This indicates the position that matching statements would appear between.

Mulgara also does a second search, this time looking for the last possible match of pattern. This will typically go down the same branches of the AVL tree, meaning that they are cached and relatively cheap to search.

These two search results provide start and end positions for an iterator that returns all statements that match the provided pattern. This iterator also adds to the reference count for the index in the current transaction. This is decremented when the iterator is closed, which is also done in the finalizer of the iterator object. This informs the free-list for the index so that it can detect when freed nodes are safe to use again.

All nodes and statement blocks that have been copied into a transaction will be available for recycling when any iterators that can reach them are closed. This is done by adding their IDs to their respective free lists.

Insert

The first step for insertion is a search for the AVL Node representing where the statement should go. If the statement would go between 2 nodes, then the node with the smaller node count is selected. If both are the same size, then it picks the lower node.

The first thing to check is if the AVL Node was allocated in the current transaction. If so, then it can be modified. But if not, then a copy of the AVL Node is made, updating the transaction ID. This operation iterates up the branch of the tree to the root, copying nodes into the current transaction, either until the root is reached, or until encountering a node that is already in the current transaction.

For the node is being updated, its associated block will get updated too, meaning that it gets copied into the current transaction, if it's not already there.

The next thing to check for is if the block is already full. If so, then it needs to be split in half (by allocating a new block and copying the top half of statements into it), and a new AVL Node created for the block with the upper statements. Both the original AVL Node and the new one have their counts, and their high and low statements updated. The node/block that is to be given the statement is then the one that gets processed.

The block being updated is searched (using binary search) to find the location for the statement. An "array move" operation is used to slide all the statements up one position, and the new statement is written into the space created. The AVL Node is then updated to increment the statement count, and possibly change the high or low statement, if appropriate.

Yes, I know... it's a lot.

Deletion

The delete operation is very similar to insertion, with a couple of differences.

If the statement is found then both the AVL Node and block will be copied into the current transaction. This time, blocks can't overflow, so no splitting occurs. Instead, if a block is emptied, it will be deallocated, putting it on the free list. Similarly, the AVL Node can be removed, putting it on the free list for its file.

An empty node in an AVL tree is expected to be removed in a single write step, but there is a small chance that rebalancing will need to iterate towards the root. The further it iterates, the more write operations take place, but this is offset by the probability of needing to take the next step decreasing exponentially.

Frustratingly, at the time, all the references we could find on rebalancing AVL trees during a deletion were wrong, which we discovered when the trees got out of balance. Finally, two of us sat down and we figured it out from first principles. That was an interesting morning. 😊

Just like insertions, the block update is done using an array move operation. The exception is if it's the highest statement in the block. In that case, the AVL Node just decrements the statement count and updates the high statement to the next one down.

Complexity

There are various tradeoffs made in each part of this structure.

Statement blocks are full of uncompressed statements (as a tuple of 4 numbers), as this makes them fast to search and read. Space is left in each block, allowing for fast insertions. However, once a block's transaction has finished, it will never be written to again. The space at the end of that block is forever inaccessible. This is done for the sake of speed.

AVL Trees are binary. This gives them log(N) complexity in search like any other tree, but from a practical standpoint this will require more read operations than a tree with a fanout of K>2. Typically, a fanout of K would result in logKN steps, which is the same as log2N/log2K. If the fanout were, say, 32, then this could be about 5 times fewer steps.

The use of blocks with 1024 statements provides a reduction in the number of steps for tree traversal than a larger fanout would give. In this case, log2(N)-log21024 or log2(N)-10. This subtraction is not as effective as a linear scaling factor, but for "small" numbers (N up to the billions), the number of I/O operations is similar. The benefit of using a binary fanout (K=2) is that we get to use the AVL structure, which permits insertions with O(1) complexity. So we get similar read characteristics to a B-Tree, but better insertion characteristics.

Files

Mulgara would typically use memory-mapped access for the files full of AVL Nodes, and regular read/write access for the block files. This provided the full speed benefits of memory mapping for tree traversal while sparing the address space from the space requirements of the statement blocks. As we moved to 64-bit architectures though, we started using memory mapping more liberally with these larger files as well. This allowed the OS to cache them as appropriate, and schedule them for writing more efficiently than we, as developers, were able to.

Finally, it is important to note just how many files were in use for all of this. Each index required:

A file for the AVL tree.
A file for statement blocks.
A free list for freed AVL nodes.
A free list for freed statement blocks. And this was multiplied by the 6 different indexes. So even if everything was being done very efficiently, the system was forced to maintain 24 files while updating storage. This involved a lot of unnecessary seeking, regardless of how efficiently the OS reordered it.

Similarly, the String Pool that I described in the previous post required:

A file for the AVL tree.
A free list for the AVL tree.
20 block files for the various sizes of data.
20 free lists, one for each block file.

While many of these files were not accessed for many operations, there was still a lot happening.

Wrap Up

Of course, this does not cover the majority of what Mulgara did, but it does describe the principal structures, especially those that are relevant to Asami. Hopefully, I've provided sufficient background to explain the decisions taken in Asami, which I will get to in my next post.

Asami Background

Paula Gearon — Sun, 07 Feb 2021 23:15:25 +0000

Mulgara

In 2001, due to a need to store a lot of metadata and deciding that RDF was the way to do it, I was part of a team that designed and built the Mulgara graph database. It was originally a commercial product called the Tucana Knowledge Store (TKS) and then mostly open-sourced as Kowari, but we renamed it to Mulgara after the original codebase was acquired by Northrup Grumman.

After maintaining Mulgara for years, I eventually put it aside. This was not because I did not think it was a useful tool, but because it was too big to work on by myself in my spare time. This was exacerbated by being written in Java, which was both slower to develop in, and less fun.

In the years since, I've been thinking of the lessons that I learned while working on Mulgara, and how things could be done better. I have also been exposed to a number of concepts and technologies that were not well known or did not exist 20 years ago, and these have informed my ideas on how such a database could be built.

In recent years, I have had the chance to express a few of these ideas in the Asami database, though I still have a long way to go.

In the meantime, people have been asking me about the design of Asami, so I thought it might be useful to document some of the history and my plans for the future here. I apologize in advance for what may appear to be random musings.

This post will focus on the structure of Mulgara, and some of the reasons for those decisions.

Indices

AVL Trees

When we were first trying to store large numbers of graph edges as triples, we discovered that it was extremely difficult to store them in a way that was searchable and could scale to the hundreds of GB we needed. Several of the developers tried different approaches, with varying degrees of success (my own did not scale well at all). But then the youngest and least experienced person in the office did a from-scratch implementation of an AVL Tree that was orders of magnitude faster than everyone else's attempts. This decided our course of action.

It also taught me that the youngest and least experienced person on a team can make contributions far beyond what the more senior people may expect. They have ideas, energy, and a lack of preconception which is extremely valuable and should never be overlooked. This has been a recurring theme in my career. I can't stress enough how important it is to have junior members on a team.

Memory Mapping

The company was primarily a Java shop, and at the time of all this, the JDK 1.4 Beta had just been released. This introduced the New IO package, which included memory-mapped files, which we were keen to try out. We convinced our engineering manager that using a Beta did not pose a significant risk, since 1.4 would be out of Beta by the time we released.

Unfortunately, the Pentium 4 systems we were developing on were based on a 32-bit architecture, which limited the address space of an application to 4GB, or around 2GB for file mappings (this depended on the OS, where shared libraries were mapped, etc). With this in mind, we worked to abstract our file I/O to use either memory-mapping or standard read-write operations, allowing the user to select which one to use at startup.

TUX2

Just a few months before, a few of us had been impressed at an idea posted by Daniel Phillips on the Linux Kernel Mailing List for the TUX2 filesystem. This described "Phase Trees", which was my first exposure to functional data structures, though I did not know this at the time. The resilience and simplicity of this idea appealed to us, and one of my colleagues suggested that we should incorporate this into our AVL tree design.

I did spend some time documenting this approach in Javascript and Java in my incomplete dev.to series on Data Structures. I did this to explain to people some of the basic ideas behind Mulgara, in the lead-up to doing something similar in Asami, but I've since been distracted by actually writing that code. I consider that to be a better use of my time for the moment, though I do hope to return to the documentation.

Basic structure

The most important element of the AVL trees that we built was the tree Node. These are a constant sized buffer, containing representations for:

A left child (possibly empty)
A right child (possibly empty)
A balance (-1, 0, or 1)
A transaction ID (assigned when the node is created and immutable).
A payload.

The payload was entirely dependent on the data being stored in the tree. It could contain everything known about the data, or it might contain partial information, along with a pointer to find the remaining data. The most important thing to know is that all AVL nodes were exactly the same size.

Transactions

Note that the AVL nodes were all associated with a transaction. This was used for tracking which nodes were under active use. Modifications to the tree were grouped into a transaction which had an incrementing ID. Whenever a node needed to be modified, then this ID could be checked against the current transaction, and if it differed, then a new node was created, copying the existing node's data into it. That old node was then added to a list of nodes that were no longer in use, called the Free List.

The Free List was used to re-allocate nodes that were no longer in use. This was important for space usage, particularly when data was being removed as well as added. Back in the early 2000s, our hard drives were smaller (and slower) than today, so we were concerned with space, and reclaiming unused nodes was important. This stood in contrast to our mantra at the time of "Disk is cheap", but minimizing wastage was still a deeply ingrained habit from the 90s.

When any operations that read from the tree were in progress, they would lock a window of the free list, ensuring that any "freed" nodes in there could not be reused until those operations were closed off. This worked well and was reasonably efficient, but it did lead to extra work. It was also (IMO) the most complex part of the codebase.

Statements and the String Pool

Mulgara initially stored all of its data statements as triples, representing a tuple of [subject predicate object]. It did not take long to realize that we wanted to group triples into identifiable graphs (which could then have information such as access and authentication properties), so we extended statements to quads of [subject predicate object graph].

For statements to be easily indexed and retrieved, we wanted them to be the same size. This meant mapping each element of a statement into a number and then providing a way to map those numbers back to the original data. Given that RDF was based on URIs (actually, URI References in RDF 1.0, and IRIs in RDF 1.1) and Literals with a string representation, this meant mapping strings of variable length to numbers, and back. The module that did this was called the String Pool.

String Pool

We built the String Pool with 2 indices and a whole lot of other files. The first index used a tree to provide searching for strings by regular comparison operations. The nodes of the tree held the beginning of the string, a pointer to another file to find the full string record, and finally, a number that represented the string (called a gNode). The second index was a series of regular-sized records where the offset of the record was the gNode multiplied by the record size. This record then contained the location of the full string record.

Finding the gNode for a string meant searching through the tree (possibly looking for the full string in the other file when the beginning of the string matched what was being looked for), and the tree node that was found contained the gNode in its payload. Searching for the string associated with a gNode meant going to an offset in the record file that was determined by: gNode * size-of-record. This record contained the location of the string.

Strings themselves were also stored in files containing blocks of regular size. Everything up to 16 bytes long went into a file of blocks that were 16 bytes in length. Everything larger than 16, and up to 32 bytes went into a file that contained blocks up to 32 bytes. This continued with blocks doubling in size up to our maximum data size of 8MB. This meant that we had 20 different files, and each file had approximately 25% of unused space. This came from the fact that the data in a block was guaranteed to fill 50% to 100% of the block.

Statements

The Statement store initially used indices to sort and store triples in the following orders:

Subject, Predicate, Object
Predicate, Object, Subject
Object, Subject Predicate

There are 6 possible orderings (calculated as 3! or 3 factorial). It turns out that the 3 orderings shown here allow someone to find all matching statements for any given group of subject, predicate, and object. Interestingly, the remaining 3 possible orderings also permit this. The two groups of orderings are distinct, in that any group that tried to contain ordering from more than one group would need more than 3 indices to be able to fulfill every possible query.

Once we moved to quads, things became more complex. Now there were 4! possible indices. We spent an afternoon mapping out every possibility and discovered that there are 4 groups of 6 indices that could be used to fulfill every possible query. One of these groups matched our existing indices quite closely:

Subject, Predicate, Object, Graph
Predicate, Object, Subject, Graph
Object, Subject Predicate, Graph
Graph, Subject, Predicate, Object
Graph, Predicate, Object, Subject
Graph, Object, Subject Predicate

A few years later I looked at this more closely and realized that it is related to N-dimensional hypercubes, where the number of groups is represented by opposing faces in the N-dimensional space. e.g. in 3D space, opposing faces of a cube appear in pairs, and there are 3 such pairs. 3 faces of the cube can be used to represent all of the space, with each opposing face providing equivalent information.

New Directions

While Mulgara was very successful, there were several areas where I felt it could be improved. I did start on some of these in 2008, but then I moved back to working on rule engines (which Mulgara also has) in 2009. This also led to me working full time in Clojure, and eventually Datomic, and each of these eventually led me towards the design that Asami took on.

I is still more to describe how the statement indexes worked, and I will discuss that next.