How do systems which process information - either brains or computers - represent that information? This review draws together many approaches to representating information under the conceptual umbrella of knowledge representation.

Knowledge representation is a very wide and general area of research, approached in an interdisciplinary manner by several different fields. The brain sciences, including psychology, neuroscience and cognitive science, study how the brain represents knowledge. The computer sciences, sometimes influenced by discoveries about the brain, invent ways to encode knowledge digitally. And industry, driven towards what will work or what will be funded, converts these research efforts into larger, working systems which are usually more efficient and correspondingly more restricted.

Language, whether it consists of gestures or grammatical utterances, is the oldest and most natural method of knowledge representation available to us.

Parsing a sentence means breaking it down into component parts of speech and formalising the relationships between them. What is parsing but generating a knowledge map from a sentence? There have been various attempts to merge parse trees into larger data structures. Richardson et al. used a parser and a fixed set of semantic relationships (like hypernym, part, purpose and location) to convert dictionary definitions into graphs like the following: These approaches have met with limited success, since language is adapted to serialised communication rather than long-term representation of a knowledge base. It can be argued that books are an effective long-term knowledge base - however, they still need to be processed serially. There is no random access to the concepts inside. The index allows occurrences of concepts to be found - but if an idea is not already understood, the reader must start at the beginning in order to be able to follow.

Language gives us a natural way to express messages, often with a pragmatic purpose. There has always been a parallel search for a way to express concepts, knowledge, and points of view.

Formal logic goes back at least to Aristotle, who defined the syllogism, which deduces a conclusion from two premises. Later work added variables, the existential quantifier $$\exists$$ ("something like this is real") and the universal quantifier $$\forall$$ ("this is always true") and the element symbol $$\in$$ ("which belongs to this set"). This allows us to say things like Before this, statements about existence or universality were difficult to encode: Here Peirce says that when some $a$ is $b$, it is not the case that all $a$s are not $b$; and when some $a$ is not $b$, it is not the case that all $a$s are $b$.

There are many types of formal logic:

• Aristotelian logic is a primitive logic consisting of terms (like "man" or "mortal"), propositions ("all men are mortal") and syllogisms (inferences which conclude one proposition from two others, the premises).
• Propositional logic or zeroth-order logic allows propositions to be built using logical connectives (and, or, etc). There are no quantifiers or non-logical symbols.
• First-order predicate logic, a key tool for computer science, uses variables and quantifiers and permits non-logical symbols like $man(x)$.

Formal logic can express very complex situations and its constraints make it reasonably computationally tractable. However, like language, it compresses information into a one-dimensional sequence. In a 5-page logical proof, a connection between the first and last pages must use a variable: the connection is not directly expressed in the model. In other words, it is not iconic.

Not much changed - "one of the more remarkable facts of the history of science", according to Kamp & Reyle - until 1879, when Gottlieb Frege published "perhaps the most important single work ever written in logic"¹: (the first incarnation of predicate logic.

The importance of the Begriffsschrift was not realised for some time, partially due to its complex 2D notation:

This notation, however, has been called "a well thought-out and carefully crafted notation that intentionally exploits the possibilities afforded by the two-dimensional medium of writing like none other." They turn out to be very similar to rotated syntax trees.

Frege's later work Grundgesetze (ground-laws) der Arithmetik, was famously torpedoed by Bertrand Russell, who in 1902 discovered a fatal contradiction which Frege was not able to repair.

It is difficult to code easy sentences in formal logic. Take "donkey sentences", first analysed by Geach:

These are sentences involving a pronoun whose role, while clear to us, is difficult to define in formal logic.

This turns out to be coded thus in formal logic:

Essentially: for every farmer x and donkey y where x owns y, x also beats y.

Discourse representation theory, proposed in the 1980s by Kamp, deals with this anaphora (long-distance connections between parts of a sentence) by modelling mental representations more closely. Here the donkey sentence is encoded with the help of the variables x (the farmer), y (the donkey), and z (the "it" that is beaten): y and z are also set equal.

Peirce was one of the first to encode logic using 2D diagrams with his existential graphs. His early attempts used letters to symbolise logical propositions (here $b$ for benefactor of and $l$ for loves) and lines connecting them to symbolise individuals, with a bar meaning "all individuals": His early work was complicated, producing the following diagram encoding "every mother loves some child of hers": This is quite difficult to understand compared to the English sentence, and is not concise enough to be a useful tool. eventually, inspired by diagrams of chemical bonds, he introduced the relation as a diagrammatic element. This diagram encodes "John gives John to John": Another innovation was to use shared space to indicate the or operation. This is how we assert that Rover is a good dog: We can negate a proposition by giving it a black border ("Rover is not a good dog"): We encode or very simply by writing two propositions next to each other on the same surface ("either Rover is a good dog or Larry is a good dog"): Using just these notations, we can encode implication ("if litmus paper is placed in acid, it will turn red"): This will be familiar to logicians as "either it turns red, or it hasn't been placed in acid". To encode and, Peirce makes use of or and not. We can write "it's warm and it's sunny" by writing "it's not the case that it's not warm or not sunny": So far, these statements are universal: there are no relative propositions (which relate to particular individuals or variables). Peirce used the same line introduced earlier to represent both of the two quantifiers. To see which, we look at how the concepts are nested. A line whose least enclosed part is on the outermost level (or inside an even number of circles) means all ("everything good is ugly"): A line whose least enclosed part is once enclosed (or inside an odd number of circles) means some ("something is good and not ugly"): The system is difficult to understand intuitively, as shown by the following two diagrams: and not ugly"): Peirce called this system entitative graphs, but soon replaced it with the more complex system of existential graphs. He extended it by adding further notations called alpha, beta and gamma, including using dotted lines to draw attention to parts of the diagram: and colours ("tinctures") to express propositional attitudes: Although Peirce's existential graphs appear rather clumsy and difficult to interpret, but we must view them in the context of his prolific interdisciplinary output and remember that at the time, there were no efficient symbol-processing machines.

Peirce's existential graphs were drawn by hand and also processed by hand. Very soon afterwards, machines (programmable or not) took over the job of computation. Computing machines began as special-purpose devices, then became gradually more extensible and programmable. The languages used to program them also became gradually higher-level, more expressive, and closer to natural language. It was, however, some time until computers became fast enough, and programming languages sufficiently high-level, to take on knowledge representation.

Some time after Ada Lovelace realised that Babbage's Analytical Engine could calculate Bernoulli numbers (widely regarded as the first computer program) and a little after Konrad Zuse built the first programmable computer, it became clear that computers excel not just at representing knowledge but at processing information - generating new knowledge. Much of computer science focusses on resolving problems which are easy to state but difficult to compute, such as sorting or route planning. Cognitive problems such as "how do I work out what John believes" are difficult to state and even harder to compute.

Since the 1950s, a wide range of increasingly high-level programming languages have appeared. Programming began in machine code entered in binary, expressing basic processor instructions by which the programmer was more or less directly responsible for switching electric currents. Machine code grew into a dense tree of higher-level languages, such as C or Fortran (where the programmer is still responsible for managing memory and handling pointers to variables) and later Python or Javascript (where the virtual machine manages memory and deals with pointers).

Should programming languages be considered as part of knowledge representation? The Church-Turing thesis tells us that any language can compute the same things as any other language, but this is not practically true, since an ill-fitting language may take a very long time to compute a problem, and (perhaps more importantly) may take a long time to program. Any knowledge representation system must also of course be programmed in an underlying language.

However, most programming languages are not intended to represent knowledge, but to get stuff done.

The relational paradigm, introduced in the 1960s by British computer scientist Edgar F. Codd, sees the world as tables (relations) which contain rows (records) and columns (attributes). Rows are uniquely identified by certain attributes (keys) and non-key attributes may point to rows in other tables (acting as foreign keys). Although relational databases certainly represent facts, they are not generally considered to do knowledge representation, because their ability to express is so restricted. Information must be encoded in records with rows and columns, and the only way to connect tables is with foreign keys (numbers or strings).

However, the language used to query relational databases, Structured Query Language (SQL) is the only widely-used declarative programming language. Operations such as JOIN (finding matching rows across two tables) and GROUP BY (count or analyse rows after sorting them into different categories, the same operation as Excel pivot tables) are planned out and executed by the SQL server, hiding the details from the programmer. This makes SQL closer to a knowledge representation language than the imperative programming languages, because its primitives are higher-level and clever operations are taking place behind the scenes.

The most significant bifurcation in the family tree of programming languages was the division into procedural languages (those which directly specify the operations a program should perform, using explicit control flow) and functional languages (which express programs as compositions of functions). Procedural languages directly drive machines and come from thinking about the Turing machine. Functional code requires translation from functions to instructions and comes from thinking about the lambda calculus. The first functional language was Lisp, introduced by McCarthy in 1958.

Lisp and its descendants played a central role in knowledge representation, as functional languages have great expressive power and are highly extensible.

One of the most popular programming paradigms, object-oriented programming (OOP), allows the programmer to define a class and then to instantiate many objects of that class. These objects all have the same interface and contain the same variables and member functions. OOP is extremely popular because it matches the way we think: human cognition is very good at classifying objects as belonging to a particular class, then assuming that all objects of that class can be used in the same way.

Does OOP constitute knowledge representation? Certainly, the division into objects and classes has been carried forwards by many KR systems, importantly (as we will see later) the semantic web. However, I note that the cognitive division between objects and classes is more complex. In cognition, something can be both a member of a class, and a class; for example, Dog is a member of the class Mammal, but Rover is also a member of the class Dog. Dog is therefore both a member and a class. Cognition can also sometimes consider something as a plain object, and sometimes as a class. It seems therefore that in cognition, classness is a particular way of seeing an object, a particular approach to the object. On the other hand, in object-oriented programming language, something is either an object or not. There may be several levels of class inheritance, but they are all classes - only the lowermost is an object. Objects cannot change class on the fly and we cannot temporarily treat a Dog as a Person, for example, with which human cognition has no problem.

The relational paradigm, introduced in the 1960s by British computer scientist Edgar F. Codd, sees the world as tables (relations) which contain rows (records) and columns (attributes). Rows are uniquely identified by certain attributes (keys) and non-key attributes may point to rows in other tables (acting as foreign keys). Although relational databases certainly represent facts, they are not generally considered to do knowledge representation, because their ability to express is so restricted. Information must be encoded in records with rows and columns, and the only way to connect tables is with foreign keys (numbers or strings).

We now begin to examine systems which definitely do constitute knowledge representation, starting with linguistics and AI research in the 1950s.

A semantic network is a graph whose vertices represent concepts and whose edges represent semantic relations. Although early semantic networks were proposed by Alfred Bray Kempe in 1886 and studied by Peirce, they were not further developed until 1956, when they were applied to machine translation in early computational linguistics. The Nude project used semantic networks as an interlingua.

Frames are a data structure proposed by Minsky which aim to represent stereotyped situations. Frames are basically semantic networks in which nodes contain named "slots" storing particular stereotyped associations. Slots can be equipped with default values, range restrictions, and type restrictions. Special slots include instance-of (pointing to the node's kind, or superclass). Frames are closely related with grammar. Slots can play roles similar to the cases of Fillmore's case grammar (Agent, Experiencer, Instrument, Object, Source, Goal, Location, and Time). Fillmore's frame semantics theory of language draws closely on work on frames in AI, and the database FrameNet indexes a large number of frames and their relationships.

Frames provide a very appealing picture of how a mind might attend to a situation and fill in the blanks. However, they did not prove useful for solving computational problems. I

Boxes show concepts and circles represent relations. Here we model the sentence "the cat chased the mouse". The agent relation links the chase to the cat; the patient (passive participant) relation links the chase to the mouse. A box represents the entire situation, and is tagged with the past relation.

Semantic networks and frames allow small chunks of knowledge to be expressed and for commonalities to be drawn among different frames (for example, many different frames can include a "location" slot specifying where the action is taking place).