Question-answering robot

Continuing my exploration of meaning and reference. Some of the following repeats what I’ve already written in this blog, sorry. I’m using the blog as a way to work out the exposition, which is still too long and too abstract.

TL;DR You can’t independently specify or test the meanings of sentence parts. Specifying and testing meaning always reduces to specifying and testing the meanings of complete sentences.

Propositions again

When an agent A sends a message to an agent B, one or both of the following should hold:

  • there is a correlation between what holds (what the world is like) before generating the message and A’s choice of message to generate,
  • there is a correlation between the message that B receives and what holds after interpreting the message.

Without at least one of these, nothing has been communicated.

By “correlate” I mean that the message and what holds vary together. E.g. as the color of a disk varies between green, red, and blue, the message might vary between “the disk is green”, “the disk is red”, and “the disk is blue”.

I’ll call what holds before generating a precondition (of message generation), and what holds after interpreting a postcondition (of message interpretation). When I use these words I really mean least inclusive precondition and most inclusive postcondition, since otherwise the terms are not helpful.

The precondition case covers messages that are simple declarative sentences (“it is raining”). I’ll call such messages “p-messages”. (Being a p-message is not an inherent property of a message. To classify a message as a p-message you have to know something of the sender’s and receiver’s behavior.)

We can experimentally test any candidate proposition for whether it is the precondition of some message being sent. Just vary the agent’s circumstances (i.e. state) and watch what messages the agent sends. If the given message is sent if and only if the proposition holds, then the proposition is the precondition of sending that message.

Imperative sentences (“please close the window”) can be treated in a dual manner; one might call them s-messages and say that the postcondition of interpretation is a specification. Again, the claim that a particular proposition is the postcondition can be tested.

You might ask: Well, what if the precondition of the generated message isn’t met (the system “lies”), or the postcondition of interpretation isn’t met (it “betrays” us)? How can you call something a postcondition of interpretation, when success is not guaranteed? You could say a specification isn’t met, or that a theory is wrong. But in any engineered success is never guaranteed. Things go wrong. Perhaps some constituent part does not live up to its specification, or the system is operating outside of its specified operating zone. You could put the qualifier “unless something goes wrong” in front of everything we say about the system, but that would not be very helpful.

Questions and answers

It’s less clear what to say about interrogative sentences (“what color is the disk?”) and responses to them (“green”).

For the sake of neutrality, and to emphasize their syntactic nature, I’ll call interrogative sentences “q-messages” and their responses “a-messages”, q and a being mnemonic for “question” and “answer” respectively.

Consider a scenario in which a q-message is sent to a question-answering robot, and an a-message is sent in response. To apply the pre- and post-condition framework given above, we need to consider the postcondition of interpreting the q-message, and the precondition of generating the a-message. (I’ll only consider what it takes to specify or describe the question-answering robot, not the agent that communicates with it, to which I grant total freedom.)

What needs to be the case after the q-message is received? Well, an a-message must be sent; but not just any a-message. As with p-messages, for any a-message, a certain precondition must be met. But crucially, the precondition, and therefore the choice of a-message, depends what the q-message is. The question is, what is the precondition of sending a-message ax, given that the preceding q-message was qx? (‘x’ is for ‘syntax’)

If we’re trying to specify the behavior of the robot, we need to specify, for each q-message, what the allowable a-messages are, as a function of the agent’s current state. The robot can choose among these a-messages.

One way to do this is by brute force enumeration. For each qx, write down the function (perhaps nondeterministic) from circumstances to answers ax. The size of the specification is going to be proportional to m*n where m is the number of possible q-messages qx and n is the number of possible a-messages ax.

A better way is to exploit the structure of the robot’s world. When we ask what the color of the disk is, and what the color of the square is, we’re asking similar questions. Each color-inquiring q-message can be associated with a ‘spot’ in the world that can have its color sensed. When the q-message is received, the color state of the spot that it designates can be sensed and an appropriate a-message can be chosen.

Interpretation

It is natural to interpret q-messages as questions, and a-messages as answers, just as p-messages can be interpreted as propositions. This may be difficult or impossible for a particularly perverse robot, but if we are designing one ourselves, our ability interpret messages is something we can control.

The proposition corresponding to a p-message can be inferred by studying the conditions under which the p-message is sent. Things are trickier regarding interpretation of q-messages and a-messages. For a q-message, we can look at how the resulting a-message varies with aspects of the world. If we can find a variable in the world that varies along with the a-message (correlates with it), and doesn’t vary otherwise [except within spans in which a single a-message covers many values – think about this], then we can say that the question is the one that asks what the value of that variable is.

Similarly, we can interpret an a-message as an answer: it is the answer that says that the variable that the preceding question (whatever it is) asks about takes on a value that can elicit the a-message, given that the preceding q-message is interpreted to be that question.

Formalism

There is a tidy way to look at questions and answers using a simple formal veneer.

Any proposition p induces a function pf from world states to {true, false}, defined so that pf yields true when p holds in that world state, and false otherwise. (To spice things up I sometimes say “what holds” or “circumstances” instead of “world state.”) Call such a function a “p-function”.

Similarly, a question q induces a “q-function” qf from world states to values, and an answer a induces an “a-function” af from values to {true, false}. qf determines the value corresponding to a world state, and af tells whether an answer a is acceptable for a given value.

Consider the proposition that q has a as an answer. Call this proposition z. Let qf be the function induced by q, af be the function induced by a, and zf be the function induced by z. Then the following holds:

  zf = af o qf

i.e.

  zf(ws) = af(qf(ws))

Interpreting this, it says a question/answer pair is (like) a factorization of a proposition.

Any formalism is likely to drop the some of the richness of what it models. Real propositions, questions, and answers probably have more structure to them than functions do. Whether enough structure is captured depends on how the formalism is applied. In this context we’re concerned with specification and prediction, and functions may work fine.

questions2

Specifying and testing

It makes sense to specify that a p-message MUST “mean” a particular proposition p – you are just saying that the robot must generate the p-message if and only if p. We can test to see whether the robot satisfies this condition.

Suppose we tried to specify that a q-message MUST “mean” a particular question q. A specification must be testable. How would a claim that qx means q (when the robot interprets qx) be tested? We’d have to see what a-messages were generated in response to qx – they would have to be the ones that “mean” correct answers to q. But to say this, we need to specify that a set of a-messages MUST “mean” a corresponding set of answers. Then, to test whether an a-message “means” a particular answer a, you’d have to send a bunch of q-messages, and for each one, check whether the a-message that comes back is or is not generated, depending on whether the answer a is an answer to the question that q-message “means”. But then you’d have to specify what each q-message “means”. This is circular.

This is therefore not the way to specify the behavior of a question-answering robot. What you have to do is to define a correspondence between q-messages and questions, and a second correspondence between a-messages and answers. Because we’re writing the specification we can simply do so by fiat, by way of exposition, just as in a specification for motor oil you might say ‘define v = 0.0114′ and then use ‘v’ elsewhere in the specification. Simply defining correspondences does not by itself say anything about what the robot has to do. Then, we specify that when a q-message is received, the a-message generated MUST be one with the property that the corresponding answer is an answer to the question corresponding to the q-message that was received.

An alternative, fully equivalent approach would be to specify the behavior of the robot using the formalism. You could define a correspondence between q-messages and q-functions, and between a-messages and a-functions, and say that the generated a-message MUST be one that makes the composition of the q-function and the a-function evaluate to true when applied to the world state. These correspondences give a interpretation of the q- and a-messages that is just as effective as the interpretation where they are questions and answers.

Going in the other direction, when we reverse engineer a question-answering robot, we have to come up with a theory that explains the data. The data consists of q-message/a-message pairs. As we develop our theory, the correspondences of q-messages and a-messages to meaning-like entities (question/answers or q-functions/a-functions) have to be hypothesized and tested in tandem; we cannot understand q-messages in isolation, or a-messages in isolation.

Compositional languages

Given an understanding of question answering, it is very easy to imagine, or design, a language of p-messages that have two parts, one part being a q-message and the other an a-message. (Perhaps some punctuation or other trivial change sneaks in there, but that’s not to the point.) The meaning of the p-message – i.e. the precondition (proposition) that holds when it’s generated – is that the a-message is a correct response to the q-message. The analysis works exactly as it does for question answering.

This particular compositional message formation is an instance the principle of compositionality, which holds when the meaning of a compound phrase (such as a p-message) is nontrivially determined by the meanings of its parts (in this case a q-message and a-message). I say “nontrivially” because in any language where phrases have parts you can always come up with some trivial definition of part meaning and composition – essentially a table lookup – that makes the phrase meaning the same as the composed meaning. Compositionality means that there is some compression going on, and you’re not quadratically just listing all the cases.

Example: q-message “Which way is Lassie running?” + a-message “South.” => p-message “Lassie is running south.”

See also

  • Horwich, Truth Meaning Reality, of course…
  • Yablo, Aboutness, of course…
  • Carpenter, Type-Logical Semantics
  • Wittgenstein, Tractatus Logico-Philosophicus
  • Jeffrey King, The Nature and Structure of Content
  • Gopnik and Meltzoff, Words, Thoughts, and Theories

Afterthought: When reverse engineering there are always multiple theories (or should I say ‘models’ like the logicians) that are consistent with the data; even when you account for isomorphisms. This is certainly true when the world state space is incompletely sampled, as it would be if it were continuous. But I think this holds even when everything is known about the robot’s world and behavior. It is customary, if you have your hands on multiple theories, to choose the simplest one in making predictions (Occam’s razor). (At this point I want to point you at the work of Noah Goodman…)

Afterthought: There’s a book that argues that young children are scientists developing and testing theories of the world. When I remember the name I’ll add it to the list

Categories: Uncategorized

Specifying meaning, part 2

Followon to specifying meaning

Specifications are often written as if they communicate social norms: the diameter of the nail’s shaft must be 4 mm plus or minus .01 mm. This is not to say the nail has taken on a moral obligation, but rather is shorthand for saying that before you claim that X meets specification Y, you must make sure that the must conditions of the specification are met by X.

Last time I talked about specifications for communicating agents. One is tempted to say that the meaning of a message is a property of the message, which is part of the agent (before it is sent at least), in the same way that the diameter of a nail is a property of the shaft, which is part of the nail. So if it is possible to specify that (a) the nail’s shaft diameter must be 4mm, then it should be possible to specify that (b) the agent’s message’s meaning must be that the battery is charged.

There is something funny about putting “meaning” in a position like this. One can measure a nail’s shaft diameter, and as there is general agreement on how to take such measurements, it is unlikely that two parties (say, a supplier and a buyer) will disagree. The specification (a) is objective and actionable. But what about (b); is there a way to make “the meaning of M is P” objective and actionable the way “the diameter of the shaft it 4mm” is? (Remember that P is a proposition such as the proposition that the battery is charged.) Probably not in the sense of “what does agent A mean by message M”. Here “mean” has the sense of “intend” and intention is subjective, i.e. unfalsifiable. The agent could mean X and do Y. What it means (intends) doesn’t matter in an engineering context; only observable behavior such as action or speech matters.

But “the meaning of M is P” could be objective if interpreted as

  1. the meaning of A sending M is P, or
  2. A’s sending M correlates with P, or
  3. P determines whether A sends M, or
  4. A sends M if and only if P.

which are all mostly equivalent. (Correlation is not causation, but it’s hard to tell them apart, and the difference may not matter if your goal is engineering.) Instead of M being the bearer of meaning, the act of sending M is the bearer.

Reporting is now a clear, testable property of the agent in question. You can check for 4. as follows: If A transmits M when P, and does not transmit M when not P, then the meaning of [A sending] M is P.

(This test has to be modified if there is competition between M and other messages for use of the communication channel; failure to send M might just mean that the channel or the agent is preoccupied with other things. But I hope you get the idea.)

If there are too many states to test exhaustively, sample the state space. If this is a seller/buyer situation, the buyer ought to be very skeptical, performing a wide variety of clever tests to ensure that A meets the specification (that it sends M if and only if P). (Perhaps the seller could provide a warrantee, or a mathematical proof, to reassure the buyer.)

Any of the interpretations 2, 3, 4 eliminates the word “meaning” without sacrificing what was originally expressed using that word. All suggestion of intent and propositional attitudes (belief, intent, truth, fidelity) has gone away. We are left with a clearer, more actionable specification.

Compositional semantics

Of course this is the simplest kind of communication: a single message whose meaning is independently specified and testable. More general scenarios have parts: either there are multiple coordinated messages, or there is a single message that has parts. The messages or parts combine somehow to form behavior that can be tested. For example, the correctness of an answer depends on what the question was, and the correctness of the predicate (in a sentence) depends on what the subject is. Parts that can’t necessarily be tested in isolation can combine to form wholes that can be.

Consider the problem of specifying a question-answering robot. Suppose the robot ‘understands’ (accepts, responds to) two ‘question’ messages, DZ and QS, and it can answer each question in any of three ways, RD, GE, or UL, with the correct choice depending on its circumstances. Suppose that the robot has a camera, and in its visual field are a disk and a square; that the disk and square can independently be either red, green, or blue; and that the robot can sense the color of the disk and square.

We want to specify the following:

question answer if and only if …
DZ RD the disk is red
DZ GE the disk is green
DZ UL the disk is blue
QS RD the square is red
QS GE the square is green
QS UL the square is blue

That is, the answer in the answer column is the correct (specified) one, if the question is the one in the question column and the condition in the third column holds.

The claims (that the disk is red etc.) and therefore the correctness of an answer can be verified through testing or through other objective, skeptical means, as above. Color is notoriously difficult to pin down, and if “is red” is too vague for one of the negotiating parties, a more precise condition can be negotiated, such as a function of the readout of a sensor operating under controlled conditions; and the better condition can be recorded as part of the specification.

We can enumerate all possible question/answer pairs like this, giving the necessary and sufficient condition for each pair, although it gets tedious if there are more than a few questions and answers. Looking at this list it is much more appealing to take the questions and answers as having meaning in themselves. It appears that DZ asks what the color of the disk is, QS asks what the color of the square is, and RD, GE, UL express that the color (of whatever is in question) is the corresponding color.

Folk semantics says that the questions and answers have meanings, and that the sender and receiver should know these meanings. One might say that the meaning to the sender is (one hopes) the same as the meaning to the receiver. But statements like these are impossible to assay and of little use in a specification. How do you test to see whether a robot gives any particular meaning to some question?

I’ve suggested a way to specify the meaning of a complete message – give the preconditions for generation, or postconditions for interpretation. Maybe we can reduce the question of the meaning of message parts, or dialog parts (such as a question/answer pair), to the case that’s already been solved.

Remember that a specification is part of a negotiation between two parties, say a seller and a buyer. The seller and buyer are the ones that have agreed, or hope to agree, on whether the question-answering artifact (robot) meets the specification. This boils down to agreeing on how to evaluate the robot for conformance. They need to have a shared method to go from a question and an answer, to a test that helps determine whether or not the answer is the correct answer to the question. (As before this is a simplification, since we have guarantees and so on, but the idea of objectivity remains no matter how complicated things get.)

One way is for the two parties to agree between them on the meanings of questions and answers, and then to agree that a question/answer scenario is tested in given circumstances by combining the question with the answer in some agreed manner, yielding a test (or a testable proposition).

That is, they agree that DZ “means” to ask what is the color of the disk (and so on), RD “means” that the color under consideration is red (and so on), and the method of the combination of Q with A is the obvious one: the proposition to test is the proposition that the answer that A “means” is true, given that what Q “means” (e.g. what the color of the disk is) is something the answer applies to.

I use “means” here but this is only to play with your mind; it could be any placeholder relationship, since its only purpose is to be introduced (by the spec) and then discharged (in an application of the combination rule in the spec). We could just as well have said DZ “is associated with” what the color of the disk is, and RD “goes along with” that the color is red. There is no objectivity to these relationships; they are just local definitions within the specification, obtaining their truth and legitimacy only by private agreement among users of the specification, and meaningful only in the context of the specification. And importantly they only address evaluations of the behavior of the robot, not the robot’s implementation. There is no need to appeal to “representations” or “intent”.

question is associated with
DZ what color the disk is
QS what color the square is
answer goes along with
RD the color is red
GE the color is green
UL the color is blue

Now we have two tables with a total of five entries, instead of one table with six entries, that is, M+N things to explain in the spec rather than M*N. Not only does this yield economies in implementation and verification but it means that question/answer pairs that have never been seen before in design or training can have agreed semantics – which I take to be the heart of compositional semantics.

This “association” approach to meaning may sound completely vacuous, and it is meant to sound that way. But going this route is very different from the folk semantics I gave above. In the folk semantics, meaning resides in the robot or in what it says. But in the preceding treatment, meaning (of questions and answers, or of message-parts) is only part of the dialog between the users of the specification (seller and buyer, or whatever). Meaning is taken up, in a controlled way, in the specification, not in the robot.

Notes

Here are three wonderful references for all you fellow meaning skeptics:

The idea of equivalence of question/answer pairs and declarative sentences is from Yablo (Aboutness, section 2.2).

Horwich (Truth, Meaning, Reality) inspired me to look for a deflationist treatment of compositional semantics.

I cheer when I read Reddy’s article “The Conduit Metaphor”, which argues that the widespread metaphor of messages as carriers of meaning is not helpful.

To be written: what all this has to do with vocabulary specifications, IAO, linked data, and httpRange-14.

Categories: Uncategorized

Specifying meaning

Specifications

A specification articulates a property or constraint that an artifact may or may not satisfy. That is, you have some class of artifacts, like screws, to which a given specification might apply, and you can ask whether or not any particular artifact meets the specification. A specification could cover physical objects (like screws) or substances (motor oil), pieces of software, or even a process carried out by people (as in ISO 9000).

A specification may be used as a guide in choosing or constructing an artifact, can be used in an offer to sell something, and so on.

The key idea is spec as class or category: a given artifact meets the spec or doesn’t. There may be effective tests for whether something meets a specification. If a spec says that a steel rod has to last for ten years, it is neither practical nor sensible to wait ten years to see if a given rod meets that spec. But perhaps the test has been performed on identical rods, or maybe there are proxy tests that we can perform, such as accelerated aging, that will give a good indication as to whether the spec will be met by the instance in hand.

In engineering the purpose of a spec is to allow us to combine parts to yield systems that have predictable and useful properties. To put it somewhat tautologically, if X meets spec A, and Y has the property that combining it with something meeting spec A yields a complex having property P, then we can predict that combining Y with X will yield something with property P.

Standards bodies like IETF and W3C exist to cause specifications to be created. They facilitate social interactions in which people, often representing competing companies, can come to agreement to give a name (such as ‘SAE 20′) to a particular specification. This allows anyone to say things like “the thing I manufacture meets SAE 20″ or “I would like to buy something that meets SAE 20″. This shorthand reduces transaction costs (time taken negotiating specifications) and creates markets (by enabling choices among providers).

Communication

W3C and IETF are specifically involved in developing specifications that apply to communication between computers. Communication involves two or more agents playing the roles of sender and receiver, connected by a communication channel that carries messages. So any specification that has to do with communication necessarily constrains some part of a sender-channel-receiver complex: the sender, or the channel, or the receiver, or an agent/channel complex.

A syntactic constraint is a constraint on what messages are or aren’t generated by a sender or interpreted by a receiver. A pragmatic constraint is one that relates what is generated or interpreted to the circumstances (state) of the sender or receiver. (The word “pragmatic” is used in all sorts of ways by various writers. This is how I’m using it.)

For example, a specification document such as that for SVG implicitly bundles two specifications, one for senders and one for receivers. An SVG sender is one that obeys syntactic constraints in what it sends. An SVG receiver is one that interprets SVG documents in a manner consistent with the specification. A receiver that draws a square when a circle is called for would not meet the specification. Since this constraint relates messages to behavior (‘circumstances’), it’s a pragmatic constraint.

Pragmatic constraints on receivers (interpretation) are common in document type specifications, such as those for image formats or programming languages. But specifications involving pragmatic constraints on senders also exist, especially in protocol specifications where a sender may be responding to a request. A weak example of a sender constraint is that an HTTP GET request must not be answered with a 411 Length Required response (since nothing requires a GET request to specify a content-length). A better example is the SNMP protocol. A device that is sent a request using the SNMP protocol (such as ‘when did your operational status last change’), and gives a syntactically correct response containing blatantly untrue information (‘two hours ago’ when actually it was five minutes ago), would not be said to be compliant with the SNMP specification.

Where constraints are not given, designers will exploit the fact to do interesting things. That SVG doesn’t tell senders which syntactically correct messages they can or should generate is the whole point of SVG: you’re allowed, and expected, to use it to express whatever graphics you want to.

In sum, we can specify:

  • syntactic constraints on senders (what’s not generated)
  • pragmatic constraints on senders (preconditions of generation)
  • pragmatic constraints on receivers (postconditions of interpretation)

Languages and meaning

Descriptions of constraints on senders and receivers are usually bundled; a single document describes them together. Comparing a given sender or receiver against constraints means paying attention to certain parts of the description, and ignoring others. This is particularly natural in the case where two agents carry on a dialog; if you are engineering a sender it’s useful to know how a matching receiver might respond to messages. A constraint bundle that applies to both senders and receivers might be called a ‘language’ or ‘protocol’.

One can speak either of the constraints met by a particular sender or receiver, or of constraints prescribed by some documentation; it’s constraints either way, retrospective in one case and prospective in the other.

Communication constraints are message dependent. That is, the constraint on an agent is that its circumstances and state should be a certain way as a function of the message on the channel: for every message M, if M is on the channel, then some constraint C_M depending on M should apply to the agent. If the agent is a sender, the constraint is on states or events leading up to the message being on the channel – what the world has done to the agent. If it’s a receiver, the constraint is on states or events following the message being on the channel – what the agent will do to the world.

(The constraint on a sender could also be on a future state of the sender, in which case the message is a promise.)

The pair of constraints (S_M, R_M) on sender and receiver agents, specific to a message, is a good candidate for the ‘meaning’ of a message relative to a language. It appears, then, that it is possible to specify, or reverse engineer, the meaning of a message when it appears on a particular channel.

When the sender is pragmatically unconstrained (it can send what it likes) and the receiver is constrained (has to do what it’s told), a message or language is ‘imperative’. When the sender is pragmatically constrained (must give information about its circumstances) and the receiver is not (can do as it likes with that information), a message or language is ‘declarative’.

‘Knowledge representation’

The official W3C specifications for RDF are very weak and impose no pragmatic constraints. An agent that sends RDF messages (‘graphs’) is not out of spec for sending any syntactically correct RDF under any circumstances; nor is an agent that consumes RDF constrained in what it does having received it.

(There are so-called semantic constraints for RDF and OWL: every graph is supposed to be “consistent.” But this is effectively a glorified syntactic constraint, since it can be decided without touching pragmatics.)

The are some pragmatic constraints around SPARQL, but these only dictate that a SPARQL server should act properly as a store of RDF graphs – if something is stored, it should be retrievable.

The interesting thing that RDF (and OWL) do is to suggest that RDF users may create secondary specifications to apply to senders of RDF. Such constraint sets are called “vocabularies” or “ontologies”. An agent conforming to a vocabulary will (by definition) not generate RDF messages at variance with that vocabulary. If we take RDF and further constrain agents by a set of vocabularies, what we get is a declarative language, something much more like SNMP than it is like SVG.

For example, the specification for the Dublin Core vocabulary effectively says that if [dc:title “Iron”] is in the message/graph, but the resource to which this applies does not have “Iron” as its title, then the sender of the message is not in conformance with the vocabulary. (I’m taking a notational liberty here for the benefit of people who don’t know RDF, and I beg you not to ask what “the resource” is, since the answer is difficult and irrelevant to the example.)

Unlike SNMP, whose pragmatic constraints can be satisfied by a mechanism, it is usually impossible to use an RDF vocabulary correctly without human intervention. A vocabulary-conforming RDF sender almost always obtains information from a human source, either from form input, text mining, or manual curation. In these cases an automaton is only conforming if the human input is correct, so it is the human + automaton complex that should be judged against the specification. By the same token, interpretation, while unconstrained by the vocabulary specification, in most use cases requires human intervention for any useful pragmatic effect. Thus most involvement of computers with RDF is for those applications not requiring generation or interpretation according to vocabularies: storage, search, translation between formats, and inference.

(I say “usually” impossible because it is certainly possible to use RDF in a manner similar to SNMP, where automaton-generated graphs are vocabulary-conforming without human input. But this is not how RDF is ordinarily used in practice.)

So there are three funny things about the “semantic web” languages that make them misunderstood outliers in the world of W3C/IETF specifications.

  1. Unlike nearly every other artificial language (XML and JSON excepted), they have no meaning – no pragmatics are defined by the core specifications. All pragmatics comes from layered specifications.
  2. As practiced, i.e. subject to vocabulary specifications, they are declarative, not imperative; pragmatic constraints from vocabularies are on senders (similarly to SNMP servers), not receivers (as in SVG, C, …).
  3. Meeting the pragmatic constraints of vocabularies typically requires human involvement, meaning that vocabulary specifications are meaningfully applied not to automata but to automata/human complexes.

Reference

I wanted to write about the question of whether reference could be specified, but needed the above by way of introduction. More later perhaps.

Oh, maybe you wanted to know what sources I would want to refer you to as background to this piece of writing. Philosophical Investigations is a propos. And I acknowledge the influence of Larry Masinter and Gerald Jay Sussman, but have nothing of theirs specifically to refer you to.

Categories: Uncategorized

Yablo Aboutness

“Aboutness” – that is, the question of whether, for given X and Y, X is about Y – is interesting in its own right, and is of interest technically, for example in understanding the foundations of web architecture and the semantic web, and of the engineering of tools such as the information artifact ontology. Stephen Yablo’s book on the subject is a delight to read. He takes quirky examples from his personal life and from literature, and he avoids unnecessary jargon. And it provides plenty of useful insight into the question.

Here is how I understand his model:

The world changes, i.e. there are many different conditions or states it might be in. Borrowing language from dynamical system theory we consider a world state space, whose points are all the potential states of the world. As time advances, the actual world traces out some path through this space.

The notions of subject matter, aboutness, and parthood can be modeled using a lattice of partitions of the world state space. Consider some object X. Ignoring all of the world other than X, X has its own states, in its own state space. X is part of the world, though, so its states are determined by the states of the world – a sort of simplification or projection. Recall that a partition of a set S is a set of nonempty sets (called ‘blocks’) such that (a) distinct blocks are disjoint and (b) the union of all the blocks is S. We can take X’s state space to be a partition of the world state space, and its states to be blocks, as follows: Two world states are in the same X-block (they are X-equivalent) iff they differ only in ways that make no difference as far as X is concerned. When X changes, the world moves from one X-block to another, and when X doesn’t change, the worlds stays in its current X-block.

To help grasp the formalism I like to think of the simple case where the world state space is R3. The world state traces out a path in R3. We may sometimes care only about one of the coordinates, say y but not x or z. y is an ‘object’ with a state space isomorphic to R, but we model it as the partition of R3 with one block of world states (points in R3) for each possible state of y. That is, each y-block is a plane parallel to the xz-plane.

The partitions of the world state space form a lattice, so we can speak of the ordering of partitions (called finer-than or coarser-than depending on which direction it’s written), and of meets and joins and all the usual lattice theoretic stuff. For every entity there is a partition, and if X is part of Y, then X’s partition is coarser than Y’s partition. (Intuitively: smaller things have smaller state spaces / bigger blocks.) So coarser-than models parthood. Coarser-then also models “inherence” of a quality in the thing that has that quality: that Fido’s weight “inheres” in Fido means that Fido’s weight’s partition is coarser than Fido’s partition. (I’m using ‘quality’ in the BFO sense, although I probably really mean ‘dependent continuant’.) Similarly, observe that any proposition (e.g. “Fido weighs 10 pounds”) partitions the world into two blocks: one consisting of states in which the proposition is true, and the other those in which it is false. When a proposition is “about” an entity, its partition is coarser than the entity’s.

I find this uniform treatment of objects, parts, qualities, and propositions to be appealing. It helps explain my discomfort with conventional ontologies like SUO. Consider the following four entities:

  1. Fido
  2. Fido’s tail
  3. Fido’s weight
  4. That Fido weighs ten pounds

The SUO top level would say that 1 and 2 are Physical, that 4 is Abstract (because it’s a Proposition), and that 3 doesn’t exist. To me they are all the same kind of thing, just some more “part-like” than others. They ought to be either all Abstract or all Physical. By Yablo’s programme they are just entities with partitions of varying fineness.

Although I’m not always a fan of BFO, it is closer to a uniform treatment. 1, 2, 3 are all continuants. BFO has no propositions (4) but it is not difficult to imagine adding them, and it is pretty clear where they would fit (they would be a particularly “atomic” kind of dependent continuant).

Categories: Uncategorized

bit interleaving

Find the pattern.

   0   2   8  10  32  34  40  42 128 130 136 138 160 162 168 170 
   1   3   9  11  33  35  41  43 129 131 137 139 161 163 169 171 
   4   6  12  14  36  38  44  46 132 134 140 142 164 166 172 174 
   5   7  13  15  37  39  45  47 133 135 141 143 165 167 173 175 
  16  18  24  26  48  50  56  58 144 146 152 154 176 178 184 186 
  17  19  25  27  49  51  57  59 145 147 153 155 177 179 185 187 
  20  22  28  30  52  54  60  62 148 150 156 158 180 182 188 190 
  21  23  29  31  53  55  61  63 149 151 157 159 181 183 189 191 
  64  66  72  74  96  98 104 106 192 194 200 202 224 226 232 234 
  65  67  73  75  97  99 105 107 193 195 201 203 225 227 233 235 
  68  70  76  78 100 102 108 110 196 198 204 206 228 230 236 238 
  69  71  77  79 101 103 109 111 197 199 205 207 229 231 237 239 
  80  82  88  90 112 114 120 122 208 210 216 218 240 242 248 250 
  81  83  89  91 113 115 121 123 209 211 217 219 241 243 249 251 
  84  86  92  94 116 118 124 126 212 214 220 222 244 246 252 254 
  85  87  93  95 117 119 125 127 213 215 221 223 245 247 253 255 

The entry for the mth row and nth column (zero-based) is given by:

(define (pair m n)
  (if (and (= m 0) (= n 0))
      0
      (+ (remainder m 2)
         (* 2 (pair n (quotient m 2))))))

Of course the isomorphism (of natural numbers with pairs of natural numbers) won’t be new to anyone (cf. Cantor); I’m just having a bit of fun with the demonstration.

Categories: Uncategorized

On the proposed data-linking 2NN status code

Eric Prud’hommeaux, apparently on behalf of Tim Berners-Lee (see here), is spearheading a drive for a puzzling and peculiar extension to the HTTP protocol (“2NN”). This is the latest move in the agonized httpRange-14 thread started by Tim twelve or so years ago.

This is all about how we are to read, write, and deploy linked data using RDF. (The issue pretends to go beyond RDF but I don’t see any consequential sense in which it does.) Remember that RDF is a language of URIs (I sometimes call it URI-ese), and there are three main kinds of URIs in RDF: those with # in them, those without # but deployed using GET/200, and those without # but deployed using GET/303. (Forget about URNs and so on for now.) It’s agreed that the use of hash and 303 URIs is unconstrained in RDF. The question is whether GET/200 behavior imposes (or should impose) constraints on interpretation of 200 URIs.

If there is debate over whether GET/200 imposes a constraint, and debate over what the constraint would be, and debate over whether the constraint is at all useful – and all three debates are real – the prudent RDF practitioner will simply stay away from GET/200 URIs altogether. And that is what many of them do.

But this is not a very happy situation, because the community seems to hate both hash URIs and 303 URIs. Hash URIs are ugly, and 303 URIs are inefficient (extra HTTP round trip to get the “data”) and hard to deploy. [so they say.] What’s the point of reserving 200 URIs? Why not just forget about GET/200 as a constraint, and use 200 URIs the same way hash and 303 URIs are used?

The W3C Technical Architecture Group, of which Tim is a member, spent many expensive hours of discussion time on this issue over many years. I personally made many attempts to formulate and avocate for what I thought was a reasonable position, and failed. (This is not to say it’s impossible to do, just that I didn’t.) In the end a subcommittee (after discussion with Tim) settled on a version of a proposal by Sandro Hawke, which Jeni Tennison rendered as URIs in Data. The new memo met with general approval (or perhaps resignation) within the TAG and received very little comment outside the TAG. The memo makes peace between the two sides in the debate by saying it’s all a matter of interpretation, and that you can shift between vocabulary interpretations without a change in overall meaning. It’s only the overall meaning that matters. You can use 200 URIs in RDF pretty much the way you use hash and 303 URIs, and here are some suggestions on how to express the way in which your use of them relates to GET/200. No awkward deployment, no extra round trip, no conflict with any prior GET/200 constraint. Problem solved.

I thought the matter was done and the RDF community was then going to do whatever it wanted to, with or without the solution offered by the memo. Then Tim writes that no, the memo’s proposal to use GET/200 to avoid the extra round trip is no good after all. To avoid the extra round trip we need a new HTTP status code that blends a GET/303 with the subsequent GET/200 for the data, but is not 200. It’s still hard to deploy, so not as good as the GET/200 solution from Jeni’s memo in that sense, but at least it fixes the extra round trip problem.

In other words, Time has decided that the memo’s proposal does not work. It would be interesting to know why. My guess is that it is too subtle.

There is no rational way to end this argument. It hinges on the question of finding meaning in GET/200 exchanges. We know that in the wild, GET/200 means nothing at all, at least on the web, other than that some kind of request for some kind of information was satisfied in some way by the provision of some information (as opposed to, say, GET/404, which does not mean that). There is no evidence that URIs “mean” anything on their own to the community of people deploying and using web servers over HTTP. – I’m talking about as a general convention. GET requests for particular URIs certainly do have meaning in many cases to those who make and satisfy them, but the meaning is bespoke to each URI. To find general constraints, you have to look elsewhere.

One place to look would be practice “in the wild” in the RDF community. I have not done a careful study – that would take more time than I have – but my impression is that 200 URIs are used in two ways: as hyperlinks, with their “meaning” or constraint specific to the particular link type (e.g. rdf:seeAlso, owl:imports); and, by certain parties, the same as hash and 303 URIs, i.e. unconstrained, with ‘meaning’ suggested by RDF ‘data’ retrieved from somewhere. So – with regard to Eric’s proposal, we strike out again, since we find no general rule from this source.

A third place to look would be specifications that have some standing in the community. One is the HTTP specification: it says GET/200 means that “an entity corresponding to the requested resource is sent in the response”; an entity is “the information transferred as the payload of a request”…  The requested resource is the one identified by the URI, a resource is anything at all, what a URI identifies is up for grabs. This is a rathole with a dead end. I’ve read this stuff dozens of times and I can only conclude that it is vacuous. There is no use of the HTTP protocol that can possibly fail to conform with all this resource-information-entity-identifies business.

One could look at well-known advisory documents such as Architecture of the World Wide Web and REST. These say that if the server infrastructure is built according to certain principles, then the designers of its various parts will have ‘identified’ one ‘resource’ for each URI. That is, for each URI, there will be something, whose properties are known to someone involved in the design, ‘identifies’, and furthermore, that there is some (unexplained) relationship between the state of that thing and its ‘representations’ (what you get when you GET). But: how would you know whether a site is designed this way? And even if it were, how would you learn any of the properties of the thing the designers ‘identified’ by any URI? Who would you ask, and how, and in what terms would they reply? – So this is not such a useful constraint, in my opinion. It may be that the site is designed beautifully, with nice intuitive URI ‘identification’, but that there is no way a client can, in general, know anything about what is ‘identified’, much less actually know what is ‘identified’.

In any case this doesn’t match how GET/200 URIs are used in RDF. Usually you do some GET requests and look at what comes back, and then do some reverse engineering or apply intuition to guess the properties of whatever responses might come back in the future. You then impute those properties to what the URI refers to in some bit of RDF. This has little to do with what sort of software architecture is employed by those providing the web site – it is about the behavior of the site.

(Tabulator does its own brand of reverse engineering: it assumes that the identified ‘resource’ is the information you get from GET/200 – or at least something with the same properties. This is a useful heuristic and works for static documents, but is unsound in general.)

OK. So some people A believe that some other people B depend on a constraint around GET/200, i.e. that if a 200 URI is used that will  have certain implication for B. But there is no general agreement on what that constraint is, so it can’t be exploited by someone writing a 200 URI, e.g. A. The prudent RDF programmer will therefore program defensively, and just avoid generating RDF containing 200 URIs altogether. Similar someone reading RDF won’t read anything into a 200 URI. If these careful people hate the hash syntax, and can’t tolerate the extra 303 round trip, then I guess 2NN is for them. That’s a lot of ‘ifs’. It all seems a bit silly to me. Good luck getting the IETF reviewers to comprehend all this.

I think that if I ever have to write code that makes use of content deployed using GET/2NN, it will probably treat GET/200 and GET/2NN the same way, and not look too hard at the status code. After all nobody has told me what the GET/200 constraint is, and there may be useful data in the response. That way I’ll also be able to use content deployed using GET/200 by people who don’t think there is any GET/200 constraint.  … if everyone thought like this, then what would be the point of the 2NN response – why not just use 200 ? But I guess not everyone thinks like this.

Appendix: How do you refer, in RDF, to documents, if not using a 200 URI? Well, you can’t reliably use a 200 URI that yields the document, because nobody will be sure which document you mean. Maybe you intend the document you got with some GET of the URI, but a different document might be served on the next GET request; maybe you meant to refer to a “changing document”, maybe you didn’t, there is no way for your interlocutor to tell. So use a hash or 303 URI with metadata – that is, a citation – to refer to the document. As part of the citation you can provide a URI saying, in the usual way, that the document was retrieved using that URI on such and such a date. If there isn’t already an RDF vocabulary (BIBO??) that lets you express a citation to a level of detail that you’re comfortable with, then one can be invented. When you give the retrieved-from URI, provide it as a string literal, not as an RDF URI reference, since what the URI reference refers to is unclear – as I say earlier in this paragraph.  If you really mean “whatever happens to be the latest document retrieved using this URL” then express what you mean, again using a suitable vocabulary. Don’t leave it to chance.

Categories: Uncategorized

Serializational State Transfer?

There is this thing called REST, which its authors describe as a software “architecture style” that is a “model of how Web applications work“. The early description of the Web, where ‘universal document identifiers’ name documents, became inaccurate pretty quickly after the Web started, since HTTP didn’t prevent anyone from making web sites where the same UDI could yield different documents at different times. This was extremely useful but led to considerable confusion over the founding theory: what a ‘document’ was and which one was ‘identified’ if you could get different ones at different times, when authenticated differently, etc. So to replace the foundational theory Fielding looked for a better description of how Web applications work, and in particular how they use URIs. It sounds as if he surveyed a number of Web applications, and found something common among them, and he called this common whatever REST.

Under REST a UDI (now called a URI) is no longer associated with a document, but rather with a ‘resource’ or ‘network resource’ or ‘object’. This isn’t really helpful in itself since it just shifts the ontological confusion from one word to another. The only thing we observe in HTTP is message payloads, so the only question to be answered in analyzing communication is, how do message payloads (particularly for GET) relate to these resource-things, and give us information about them (properties)? If there is no relationship, then we know nothing at all about resource-things.

The party line is that the payload is a ‘representation’ of the resource-thing, which is again not at all helpful since it only changes something we didn’t understand and don’t have a name for, to something we don’t understand and do have a name for. The word is evocative, to be sure, but extremely ambiguous. So what, really, was the REST insight, based on empirical study of real Web applications?

I’ve mulled this over for a long time and here is what I’ve come up with. The ‘resources’ or ‘objects’ of REST are data structures or data objects that are stewarded and controlled by computational devices, and the message payloads are serializations of the current state of those data objects. That is, if you read about REST and substitute ‘serialization’ for ‘representation’, it will make a lot more sense.

So the empirical claim, as I interpret it, is that a common pattern among Web applications in the mid 1990s is that payloads (web page instantiations) are associated with single data objects in the memory space (disk or otherwise) of the application. The object could be a database record or table, or a map or image or etc. The data object (that is, its contents, or state) can change over time, in which case you get different serializations at different times, but it’s always the same object being serialized, for each URI.

I don’t know whether this claim is true; I didn’t do a survey of the kind Fielding did. It would be nice to see evidence. My feeling, based on looking at lots of web pages, is that payloads/pages are probably assembled from bits and pieces of many data objects in the application, in addition to simply providing information that’s not stored in a data object, but is just the output of some process such as a calculator, chat, random number generator, webcam, etc. I would be surprised to learn that REST is true of even 25% of web sites or URIs out there.

In addition to the empirical claim there is advice, based on the experience of the authors, that if you create a web site using the REST style, it will be a better site than if you hadn’t. This prescriptive angle is amplified in the W3C Web Architecture recommendation. This is a different claim, and may well be true – certainly if you follow REST style you’ll get URIs that work nicely and intuitively as bookmarks and hyperlink targets, and this is both a social good and should be in the self-interest of site creators.

The thing that I and other people have found confusing is the use of REST language in the HTTP specification. REST is a statement about how the organization of an application relates URIs, message payloads, and its internal data objects, and HTTP does not govern that kind of thing, it only governs the payloads themselves. A web application can be very non-REST and still conform to HTTP. So the spec’s REST language has no normative force. Instead REST has been used as a guide to the design of the HTTP specs; applications that are REST are, by design, going to be a more natural fit to HTTP than other applications (such as streaming video).

But the statement in HTTP that the payload of a 200 response to a GET is a representation of the identified resource, is not true in general, it is just wishful thinking, a vain hope that every web application will use REST style. But it’s there in the spec, so it sounds like it has normative force. The only way I can keep my head from exploding when reading the spec is to tell myself to relax and read something else instead.

Then there’s the awful situation with URIs in RDF. In RDF you want to coordinate agreements over what the properties of the things ‘identified’ by URIs are, so that you can use those URIs in communication. To me it’s clear that if the URI is associated with a REST data object, the REST style advice would be that the URI ‘identifies’ the data object whose serializations we see when we do GETs, so the properties of the thing identified (in RDF) by the URI are the properties of the data object inside the application (field values, size in bits, data type, last modified date/time, current serialization(s), that kind of thing). But this doesn’t help coordinate understanding of the data object by others, since only people with knowledge about how the application operates internally can know any properties these data objects; there’s no standard channel through which this knowledge can be communicated, and nobody would be interested in saying anything on it, if there were. Of course an outside observer doesn’t even know whether it’s a REST URI at all. And if the URI is not associated with a REST data object, anyone can say anything about what it ‘identifies’ – there may sometimes be agreement, or understanding, by luck, but there is no standard or widely used best practice to help out (other than the ‘hash URI’ and ‘303’ cases, where there is coordination, local to the RDF world). Most of the time the ‘I’ in ‘URI’ is mere wishful thinking, not a matter of fact as a naive reading of the acronym would suggest.

To me the REST theory feels like a post hoc attempt to justify calling those strings that start ‘http://…’ ‘identifiers’. In order to be identifiers they have to identify something. There would be no reason to say what the identified thing was, or even that there was such a thing, if all we cared about was a communication and a smoothly working Web; the ‘identified thing’ would have no reason to exist at all. But if you are committed to seeing ‘http://…’ things as identifiers, you are forced to come up with a story about what they identify.

(RDF is a different story, since it works in the other direction: we want to express a statement that X has property Y, so what name should we use for X? Hey, maybe we can use a URI.)

I could go on and on… I haven’t even touched on the context dependence of ‘identification': it only makes sense within some particular language that lets you express claims or commands that have agreed consequences…

Categories: Uncategorized Tags:
Follow

Get every new post delivered to your Inbox.