More info on Rich Hickeys ideas on Map types from "Maybe Not"

[Henning Sato von Rosen]

Hi all,

(I have googled for information on the below, but come up empty)

I am looking for the most authoritative written sources, usable as references in a bachelor thesis on an idea/principle/data type that Rich Hickeys talks about e.g. in the talk Maybe Not:

https://github.com/matthiasn/talk-transcripts/blob/master/Hickey_Rich/MaybeNot.md

The idea is to represent data by maps while observing the following two principles:

1. Keywords have type declarations for their values, not maps:
   The types of the values of the keys are defined per keyword, no per map type
   Advantage: This turns keywords into reusable components in their own right
2. Non-existence expressed by omisson of keyword. Non-existence of a value in a key/value-pair must be expressed by omission of the whole key/value pair, not by `null` as a value.
   Advantage: This makes it possible to observe the informational status of a map by observing it's shape, (what key/value pairs are present), thus exposing the shape as something that can be reasoned about, type-checked and expressed in function signatures. This makes it possible to keep the conceptual meaning of the map orthogonal from it's shape or completeness of information, thus uncomplecting the aspects.
   

The above description is my interpretation of what Rich says in the talk. I am thankful for correction, if I have misunderstood something!

I (my project group) will be using these two principles when we design a specific domain model in our bachelor thesis/programming project, and the opposition will probably give us a hard time if our only source is a talk on YouTube ;-)

1) Is this data type described in a research paper? Or Maybe Rich have written a more precise description than given in "Maybe Not"?

2) Does it have an established name, that can be search for on the web? The combination of the two principles above seems very appropriate for modelling certain domains, so it certainly deserves a name, don't you think? Hickey Types anyone? Or Component/Shape Map Types?

3) Is Rich the first one to combine these two principles or are there prior art?

4) Is the second principle covered somewhere in the clojure/spec documentation.

Thanks for any info on this!

Regards/Henning Sato von Rosen

(I study CS at CSE Chalmers University of Technology/Gothenburg University)

[Ben Sima]

I guess I'll take a crack at this...

I think generally, core.spec is an implementation of contracts, so you
could look at the literature around contracts for some sources. Racket
is (afaik) most integrated contract language, there are some references
here to start with: https://docs.racket-lang.org/reference/contracts.html

This data type you are asking for is not really a data type in how
Clojure understands data types. It's more like a functor. One example
from Rich's slides involves changing a function from

foo :: x -> y

to

foo :: Maybe x -> y

This will break existing callers because they need to supply a different
first argument. But this can be sort of smoothed over using fmap

fmap :: (a -> b) -> Maybe a -> Maybe b

So instead of changing the type of foo, you would change the caller to
use (fmap foo) :: Maybe x -> Maybe y. But you can't do set operations on
functors, so you kinda lose a lot. You could get some of it back by
introducing category theory operations, as Haskell does, but then you
have to deal with category theory.

I suppose that would be a great place to start, looking at the limits of
set theory and category theory. Lots of literature there...

Also, what's wrong with citing a presentation or an implementation as a
reference? It's as valid as any other publication.

[Henning Sato von Rosen]

Hi Ben,

Thanks for answering!

Sorry if I'm wrong here, but I'm not sure we are talking about the same data-type; I'm not referring to the Rich's examples with Maybe, but his examples with records/maps, where some fields may or may not be present.

Example: Multiple functions manipulate the same datatype, e.g. a map containing name and address etc, and  a given function might need only  the street address and postal code, and this is usage/context dependent, so you shouldn't have to hide optionality by declaring that attributes need to be present but might contain null. In stead you should just leave out the attributes that are not given. So this givenness/or not of attributes becomes an actual signature of the data-types informational status, that can be used to decide e.g. what functions are applicable, what buttons to enable in the UI etc etc.

Sorry if I'm missing something here!

Regards/Henning

[Jesús Gómez]

El vie., 19 abr. 2019 a las 13:25, Henning Sato von Rosen (<henning....@gmail.com>) escribió:

...

1. Non-existence expressed by omisson of keyword. Non-existence of a value in a key/value-pair must be expressed by omission of the whole key/value pair, not by `null` as a value.
   

1. ...
   

Just to add that I understand null should be interpreted as "I don't know the value", and not as the non-existance of a value. "I don't know" is a superset that includes the non-existance.

In that sense, omitting the keyword could be interpreted as "I don't know" instead of "omission" only. Yet, not sure if it was Ritchie intention.

[dus...@hyperfiddle.net]

A lot of the attribute-centric thinking is inspired by RDF and linked-data

[Ben Sima]

Henning Sato von Rosen <henning....@gmail.com> writes:

> Sorry if I'm wrong here, but I'm not sure we are talking about the same
> data-type; I'm not referring to the Rich's examples with Maybe, but his
> examples with records/maps, where some fields may or may not be present.

Right, and in most other type systems, the only way to indicate
field presence is with a Maybe type:

data MyData = MyData
{ oneField = Maybe Int
, twoField = Maybe String
}

So to convey that these fields don't exist, we have to explicitly say
"Nothing":

instance Monoid MyData where
mempty = MyData { oneField = Nothing, twoField = Nothing }

which, in GHC, is known and enforced at compile-time. In lisp, if a
field isn't present in a record, you get nil:

(get {:a 1} :b) ;;=> nil

but this is only decidable at runtime. So core.spec takes this "tooling"
around typechecking and exposes it to the user so they could do program
analysis (like seeing what functions are applicable, etc) at
runtime. Racket's contract system does the same, afaik.

Presumably you could implement a Hindley-Milner type system using
core.spec. That would be cool. E.g. Shen is a lisp with a type system in
which you could implement HM in just a few pages of code.

Not sure if this is helpful, hope you get something out of it.

[Henning Sato von Rosen]

On Thu, Apr 25, 2019 at 2:32 AM <dus...@hyperfiddle.net> wrote:

A lot of the attribute-centric thinking is inspired by RDF and linked-data

Yes! Rich mentions that as well. So I tried to look into RDF, but it is huge! If anybody has a good link to material relevant to this discussion, I'm thankful, but at the time being we will likely not have time to dig into RDF.  Rich's explanation is by far the most relevant andaccessible I've come across.

Regards/Henning

 

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to a topic in the Google Groups "Clojure" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/clojure/Dbh-5kNYKgE/unsubscribe.
To unsubscribe from this group and all its topics, send an email to clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Henning Sato von Rosen]

Thanks again for your comments! They are absolutely very helpful!

I feel I'm trying to free-my-mind here; still working on losing the idea that type-checking is magic done by the system/language, and instead something the programmer can use at will, and creatively, and in unexpected ways. Not only to check that code is not wrong, but to drive progression in a multi-stage evaluation; choose among specific implementations that are doing work that is conceptually the same, but implementation-wise different, reflect the state of the evaluation and possible interactions as user UI on a web page etc etc.

Regards /Henning

[Henning Sato von Rosen]

...

1. Non-existence expressed by omisson of keyword. Non-existence of a value in a key/value-pair must be expressed by omission of the whole key/value pair, not by `null` as a value.
   ...
   

Just to add that I understand null should be interpreted as "I don't know the value", and not as the non-existance of a value. "I don't know" is a superset that includes the non-existance.

Yes! You are absolutely right. That is a very important distinction. Thanks for pointing it out!

Regards /Henning

PS In our evaluator, it means simply "not calculated yet". But in other data it means "not given".  What this does, if I observe correctly, is to free up the data to convey just that information that is present, but yet to keep the perspective/framing/conceptual meaning the same as if additional data were present! That is a very powerful concept, I think. I am also starting to consider the possibility that it is a pervasive principle in Natural Language (that makes word classes possible etc), although that is yet to be explored. 

 

In that sense, omitting the keyword could be interpreted as "I don't know" instead of "omission" only. Yet, not sure if it was Ritchie intention.

--

[Rick Moynihan]

Having used both Clojure and RDF extensively I can say that there are many similarities between these two worlds, and the influence of RDF on Clojure isn't just something Rich say's, it's very apparant.

I may be mistaken in some of the details here, but as I understand it in the world of GOFAI (Good Old Fashioned AI) and KR (Knowledge Representation) there were "frame languages" popularised by Minsky:

https://en.wikipedia.org/wiki/Frame_language

where you essentially describe the world in terms of classes, and classes consist of sets of slots or properties, you may have inheritance etc... essentially classical OOP. 

In the other KR camp however you have First Order Predicate Logic (FOL), where the predicates (properties) essentially take centre stage, and describe relations between objects.  This modelling camp is largely where RDF drew its inspiration for modelling from in the form of RDFS and OWL.  I'd argue (with no authority) that FOL is likely the true source of the decomplected properties from maps idea in clojure; which is analagous to what happened in KR.

I mention frame languages, as I suspect there is a lot of academic discourse on the pros and cons of frame based approaches vs FOL, which may be relevant.

In RDFS (RDF Schema: https://en.wikipedia.org/wiki/RDF_Schema) and OWL ( https://en.wikipedia.org/wiki/Web_Ontology_Language )you essentially describe the domains and ranges of properties, and then use properties to tie things together.  In these languages you don't think of classes as constraining the available properties.  Infact properties often let you infer the class of something, for example if you learn that :Rick foaf:friend :Bill you also learn that :Rick and :Bill are foaf:Person's too.  This enables anyone to say anything about anything in RDF which is why it's an open world system, where as frame based systems are typically closed world, as you can't add properties to something without changing the class.

RDF and OWL aren't really constraint languages though, they're description logics; so they don't typically let you restrict the values of things, instead they let you infer new values.  However recently there have been moves to standardise ways to check RDF graphs form a certain well specified shape.  This has been in the form of the languages SheX and SHACL (now a W3C standard: https://www.w3.org/TR/shacl/ ). 

I find it remarkable how similar these languages are to spec; though I don't think spec drew any direct inspiration from them.  I guess you just end up in a similar place if you share a property oriented view of the world.

If you're interested in these languages this is a good online book on the topic:

http://book.validatingrdf.com/index.html

RDF also has a lot in common with Datomic in that you describe data with triples EAV(T) in datomic and SPO(G) in RDF.  Likewise SPARQL and Datomic have a common ancestor in Datalog.

I believe another non RDF influence for spec is this paper:

http://matt.might.net/papers/might2011derivatives.pdf

Please take all of the above with a pinch of salt though, it's at best a crude approximation on the lineage of these ideas...

R.

You received this message because you are subscribed to the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure+u...@googlegroups.com.

[Henning Sato von Rosen]

Thanks a lot for the background on RDF and links, very interesting indeed!

About FOL, you equal the properties that we are talking about to predicates in FOL. I might have gotten it backwards here, but isn't the natural thing to think of our map as the relation (predicate) and our properties as the slots of the predicate (positional arguments being isomorphic (more succinct, but  less readble and less flexible) to named roles of map datastructures)?

Reards/Henning

[Rick Moynihan]

On Sat, 27 Apr 2019 at 10:56, Henning Sato von Rosen <henning....@gmail.com> wrote:

Thanks a lot for the background on RDF and links, very interesting indeed!

About FOL, you equal the properties that we are talking about to predicates in FOL.

Firstly it's important to say that I don't claim they are identical, just analagous, as they have many differences too.  spec isn't realy a logic system, though I guess you could think of it that way, particularly when looking at the generative aspects.

It's perhaps therefore important to clarify which aspects of clojure properties I'm drawing an analogy to. 

My previous claim was this:

>> I'd argue (with no authority) that FOL is likely the true source of the decomplected properties from maps idea in clojure; which is analagous to what happened in KR.

Where I'm really talking about the use of keywords in clojure.spec; which I'd say are similar to (definitely not the same as) binary predicates in FOL.  The similarity I'm alluding to is that in FOL the use of predicates are largely extrinsic to their subjects.  For example  I can make statements today such as "Socrates influenced Rick" where influenced (the predicate), was not intrinsically baked into Socrates at his birth; but was derived independently later.  Likewise with properties in spec the predicate is decoupled from its subjects.

My claim is that this is similar to adding a new spec to some existing data.  And it's also like adding a new property (keyword) to a map in spec, and only handling what you know.

 

I might have gotten it backwards here, but isn't the natural thing to think of our map as the relation (predicate) and our properties as the slots of the predicate

The analogy may break down if you think about it too much; as spec has a different usecase to FOL.  You could probably model things this as you suggest however that isn't how I was thinking of it.  To expand, I'd say that this:

(s/def ::influenced #(instance? Person %))

Is analagous to declaring the meaning of a predicate; e.g. in the prose of a paper you might say "we define influenced as a relation between two people".  Or in RDF this is equivalent to defining the predicate in a vocabulary e.g:

:influenced rdfs:Range foaf:Person .

:influenced rdfs:Domain foaf:Person .

and something like this is roughly equivalent to expressing the relation between Socrates and Rick: i.e. the maps themselves are the subjects and the keyword is the binary relation between them:

(assoc socrates ::influenced rick)

A notable difference here is that spec doesn't let you describe the domain of a keyword in a map; i.e. an `(s/def ::keyword ,,,)` only lets you make a statement about the value of the key, not the map it is part of.  Though you can of course do that with an extra s/keys spec, it's a new spec with a new name and not a property of the initial spec.

Obviously you can also use specs to desribe other things (not just the values of maps), but the primary similarities as I see them are that it is open for extension by virtue of:

1. The predicate/spec is extrinsic to the data/declaration/code itself i.e. they can be coined separately at a different place and time

2. That multiple a single subject/datum can have a plurality of specs

3. That you can't close the world (and prevent others saying things about your data)

In a frame based system Socrates would typically be closed to other people adding new properties... though IIRC there may also have been some hybrid approaches, e.g. I've heard that there were some Common Lisp truth maintainance systems which could dynamically introduce new slots on classes through rules expressed in non-monotonic logics... but this is largely hearsay and likely irrelevant here :-) 

Hope this clarifies things a little...

R.

[Henning Sato von Rosen]

Thanks again for interesting background/links!

On Fri, Apr 26, 2019 at 12:58 AM Rick Moynihan <rick.m...@gmail.com> wrote:

I believe another non RDF influence for spec is this paper:

http://matt.might.net/papers/might2011derivatives.pdf

The paper on derivatives is both beautiful and mind-bending, but I fail to see how it might have inspired spec. Could you please ellborate?

Regards /Henning

 

[Rick Moynihan]

The regex operators in spec are inspired by the implementations in that paper, which I believe lead to guarantees of termination, by handling any left recursion in the grammar...  The spec code also references these links:

http://matt.might.net/articles/implementation-of-regular-expression-matching-in-scheme-with-derivatives/

http://www.ccs.neu.edu/home/turon/re-deriv.pdf

https://github.com/clojure/spec.alpha/blob/master/src/main/clojure/clojure/spec/alpha.clj#L1369-L1372

Similarly SheX the RDF validator I mentioned also appears to be influenced by this area; which finally clarifies a suspicion I'd had for a while... 

Section 9 of this paper also cites some other derivate implementations, e.g. Relax NG for validating XML:

https://pdfs.semanticscholar.org/7b7f/770d2243247688befe98b3aed0ea70b15e15.pdf

R.

 

Regards /Henning