DON'T PANIC: 2017

2017년 6월 7일 수요일

Ontology Engineering

1. When to Use an Ontology
- Knowledge management
1) control vocabulary
2) making domain assumptions more explicit
3) separate the metadata structure from the data itself
4) change in metadata does not necessarily require change in the data

- Knowledge sharing
1) the clear model of your data enables other machines and people to understand it, and thus and reuse it

- Knowledge integration
1) ontologies can bridge between several data sources

- Knowledge analysis
1) using a rich data model enables more complex analysis to be made on the data

- Type of Ontologies
1) Representation ontologies
* describe low-level primitive representations
e.g. OWL, RDF, RDF Schema (language itself)

2) General or upper-level ontologies
* describe high-level, abstract, concepts
e.g. Cyc (Commonsense ontology)

3) Domain ontologies
* describe a particular domain extensively
e.g. GO (Gene Ontology), CIDOC CRM (for cultural heritage)

4) Application ontologies
* mainly designed to answer to the needs of a particular application
e.g. FOAF(Friend Of A Friend)

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

http://owl.cs.manchester.ac.uk/about/ontology-engineering/

2. Ontology Building Methodologies
: no standard methodology for ontology construction
- Ontology Development Life-Cycle
1) Specification: specifying the ontology's purpose and scope
* why are you building this ontology?
* what will this ontology be used for?
* what is the domain of interest?
* how much detail do you need?
* Competency Questions: what are some questions you need the ontology to answer?

2) Conceptualisation: identifying the concepts to include in your ontology, and how they relate to each other
* what can you reuse?
* ontologies are meant to be reusable!

3) Formalisation: moving from a list of concepts to a formal model
* define the hierarchy of concepts and relations: top-down/bottom-up / middle-out
* class or relation? : if the subclass doesn't need any new relations (or restriction), then consider making it a relation
* class or instance? : if it can have its own instances or subclasses, then it should be a class

4) Implementation: choosing a language and implementing it with an ontology editor

5) Evaluation: implementing the ontology in an ontology editor helps to get syntax correct
* check the ontology against your competency questions
* W3C RDF validator: http://www.w3.org/RDF/Validator/

6) Documentation: documenting the design and implementation rational is crucial for future usability and understanding of the ontology

http://wiki.opensemanticframework.org/index.php/Ontology_Development_Methodologies

3. Conceptual modelling
- Conceptualisation (1): Vocabulary
1) what are the terms we would like to talk about?
2) what properties do those terms have?
3) competency questions provide a useful starting point
4) investigating homonyms and synonyms

- Conceptualisation (2): Classes
1) select the terms that represent objects having independent existence rather than terms that describe these objects
2) classes represent concepts in the domain and not the words that denote these concepts
3) typically nouns and nominal phrases, but not restricted to them

- Conceptualisation (3): Class hierarchy
1) a subclass represents a concept that is a 'kind of' the concept that the superclass represents
2) Roles are not subclasses
3) application dependent or subjective

- Conceptualisation (4): Properties
1) for each property in the list, we must determine which class it describes
* attributes: measurable properties of a class
* relationships: inter-entity connections

- Conceptualisation (5): Domain and range
1) refine the semantics of the properties
2) when defining a domain or a range for a slot, find the most general classes or class that can be respectively the domain or the range of the slots

- Conceptualisation (6): Inverse properties
1) modelling with inverse properties is redundant, but allows acquisition of the information in either direction

- Conceptualisation (7): Instances
1) entities of a certain type

Web Ontology Language

1. Introducing Web Ontology Language (OWL)
- OWL has more expressive formalism than RDF Schema
1) instance classification
2) consistency checking
3) subsumption reasoning

- two versions of OWL
1) OWL 1.0: different subsets of OWL features give rise to the following sublanguages (colloquially known as species)
* OWL Lite: SHIF(D)
! less complex reasoning at the expense of less expressive language
* OWL DL: SHOIN(D) + complete and decidable + higher worst-case complexity than OWL Lite
! supports all OWL constructs, with some restrictions
* OWL Full: no restrictions on use of language constructs
! potentially, undecidable (you can still receive some answers but not for all questions)
http://www.cs.man.ac.uk/~ezolin/dl/

2) OWL 2.0: more expressive than OWL 1.0, and takes advantage of developments in DL reasoning techniques in the intervening time

2. OWL 1.0 Features and Syntax
- Ontology header
<owl:Ontology rdf:about="">
<owl:versionInfo>1.4</owl:versionInfo>
<rdfs:comment>An example ontology</rdfs:comment>
</owl:Ontology>

- Versioning support
1) owl:versionInfo: version number etc
2) owl:priorVersion: an ontology is a previous version of this
3) owl:backwardCompatibleWith: the specified ontology is a previous version of this one, and this is compatible with it
4) owl:incompatibleWith: the specified ontology is a previous version of this one, but this is incompatible with it

- OWL class types
1) owl:Class: distinct from rdfs:Class
2) owl:Thing: the class that includes everything
3) owl:Nothing: the empty class

- OWL property types
1) owl:ObjectProperty: the class of resource-valued properties
2) owl:DatatypeProperty: the class of literal-valued properties
3) owl:AnnotationProperty: used to type properties
!! OWL versus RDF Schema
* reflexive definitions of RDF Schema means that some resources are treated as both classes and instances, or instances and properties
=> ambiguous semantics for these resources
can't tell from context whether they're instances or classes
can't select the appropriate interpretation function
* the introduction of owl:Class, owl:ObjectProperty and owl:DatatypeProperty eliminates this ambiguity

- OWL local cardinality constraints
1) owl:minCardinality: property R has at least n values
2) owl:maxCardinality: property R has at most n values
3) owl:cardinality: property R has exactly n values

<owl:Restrictions> 
<owl:onProperty rdf:resource="#distilledBy"/>
<owl:cardinality>1</owl:cardinality> 
</owl:Restriction>

- OWL local range constraints
1) owl:someValuesFrom: there exists a value for property R of type C
2) owl:allValuesFrom: property R has only values of type C

<owl:Class rdf:about="#Vegetarian">
<owl:equivalentClass>
<owl:Restrictions>
<owl:onProperty rdf:resource="#eat"/>
<owl:allValuesFrom rdf:resource="#Plant"/>
</owl:Restriction>
</owl:equivalentClass>
</owl:Class>

- OWL local value constraints
1) owl:hasValue: property R has a value which is X
<owl:Restrictions>
<owl:onProperty rdf:resource="#hasColour"/>
<owl:hasValue rdf:resource="#Green"/>
</owl:Restriction>

- OWL set constructs
1) owl:intersectionOf
2) owl:unionOf
3) owl:complementOf

- Equivalence and identity relations
1) owl:sameAs
2) owl:equivalentClass
3) owl:equivalentProperty
<owl:Thing rdf:about="#MorningStar">
<owl:sameAs rdf:resource="#EveningStar"/>
</owl:Thing>

- Non-equivalence relations
1) owl:differentFrom: can be used to specify a limited unique name assumption
2) owl:AllDifferent / owl:distinctMembers
<owl:AllDifferent>
<owl:distinctMembers rdf:oarseType="Collection">
<rdf:Description rdf:about="#John"/>
<rdf:Description rdf:about="#Paul"/>
<rdf:Description rdf:about="#Ringo"/>
</owl:distinctMembers>
</owl:AllDifferent>
3) OWL (and DLs in general) make the Open World Assumption

- Necessary Class Definitions
1) If we know that something is a X, then it must fulfil the conditions ...
2) defined using rdfs:subClassOf

- Sufficient Class Definitions
1) if we know that something has this property, then it belongs to this class ...
2) defined using rdfs:subClassOf - in the other direction

- Necessary and sufficient Class Definitions
1) if something fulfils the conditions ..., then it is an X
2) defined using owl:equivalentClass

- Inverse: defines a property as the inverse of another property
<owl:ObjectProperty rdf:about="#hasAuthor">
<owl:InverseOf rdf:resource="#write"/>
</owl:ObjectProperty>

- Symmetric: P(x, y) iff P(y, x)
<owl:SymmetricProperty rdf:about="#hasSibiling"/>

- Transitive: P(x, y) and P(y, z) implies P(x, z)
<owl:TransitiveProperty rdf:about="#hasAncestor"/>

- Functional: P(x, y) and P(x, z) implies y = z
<owl:FuntionalProperty rdf:about="#hasBirthdate"/>

- Inverse Functional: P(y, x) and P(z, x) implies y = z
<owl:InverseFunctionalProperty rdf:about="#hasFingerPrint"/>

- Disjoint classes: members of one class cannot also be members of some specified other class
<owl:Class rdf:about="#MaleHuman">
<rdfs:subClassOf rdf:resource="#Human"/>
<owl:disjointWith rdf:resourcce="#FemaleHuman"/>
</owl:Class>

- Ontology modularisation
1) owl:imports mechanism for including other ontologies
2) also possible to use terms form other ontologies without explicitly importing them
3) importing requires certain entailments, whereas simple use does not require those entailments

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

https://www.w3.org/TR/owl-guide/

3. OWL 2
- From OWL 1 to OWL 2: changes between 1 and 2 fall into the following categories
1) syntactic sugar
* owl:AllDisjointClasses : allows to define a class as the union of a number of other classes, all of which are pairwise disjoint
* owl:NegativePropertyAssertions : lets us assert that an individual does not have a particular property value

2) constructs for increased expressivity
* owl:hasSelf: defines a class of individuals which are related to themselves by a given property
* qualified cardinality: lets us specify both the local range of a property and the number of values taken by the property
<owl:Restriction>
<owl:onProperty rdf:resource="#hasPart"/>
<owl:onClass rdf:resource="#Wheel"/>
<owl:cardinality rdf;datatype="&xsd;integer">4</owl:cardinality>
</owl:Restriction>

* owl:ReflexiveProperties: allows to assert that a property is globally reflexive (relates every object to itself)
* owl:IrreflexiveProperties: allows to assert that a property relates no object to itself
* owl:AsymmetricProperties: allows to assert that a property is asymmetric - If p(x, y), then not p(y, x)
* owl:propertyDisjointWith: allows to state that two individuals cannot be related to each other by two different properties that have been declared disjoint

* property chain inclusion: defines a property as a composition of other properties
<owl:ObjectProperty rdf:about="#hasUncle">
<owl:propertyChainAxiom rdf:parseType="Collection">
<owl:ObjectProperty rdf:about="#hasParent"/>
<owl:ObjectProperty rdf:about="#hasBrother"/>
</owl:propertyChainAxiom>
</owl:ObjectProperty>

* owl:hasKey: let's define uniquely identifying keys that comprise several properties
* owl:onDatatype: allows to define subsets of datatypes that constrain the range of values allowed by a datatype

3) datatype support

4) metamodelling
* Punning: OWL 1 required the names used to identify classes, properties, individuals and datatypes to be disjoint but OWL 2 relaxes this (the same name can be used for both a class and an individual>
https://www.w3.org/2007/OWL/wiki/Punning

5) annotation

https://www.w3.org/TR/owl2-primer/

http://semanticweb.org/wiki/OWL_2.html

SPARQL Protocol and RDF Query Language

1. RDF Triplestores
- Specialised databases for storing RDF data
- Can be viewed as a database containing a single table
1) table contains subject/predicate/object as minimum
2) many triplestores store quads to maintain provenance

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

http://www.krisalexander.com/uncategorized/2013/07/16/the-difference-between-a-triplestore-and-a-relational-database/

- Querying Triplestores
1) the ranges of the subjects, predicates and objects define a space
2) a triple is a point within this space
3) query patterns define regions within this space
* (s p ?), (s ? o), (? p o) define lines
* (s ? ?), (? ? o), (? p ?) define planes
4) answering queries = finding points in these regions

- RDF Query Languages
1) Typical query structure: <list of variables to be bound and returned> <list of triple patterns and constraints>
2) W3C specified a single query language which combines the best features of its predecessors: SPARQL

2. SPARQL Query Language
- SPARQL
1) SQL-like syntax:
PREFIX foaf: <http://xmlns.com/foaf/0.1/> // need to define namespaces for vocabulary terms used
SELECT ?name ?mbox // variables prefixed with '?'
WHERE {
?x foaf:name ?name . // triple patterns expressed in N3-like syntax
?x foaf:mbox ?mbox . // intersection is defaulted between triple patterns
}

PREFIX xsd: <http://www.w3.org/2001/XMLSchema#>
SELECT ?v
WHERE {
?v ?p "cat"@en . // literal strings must have language tag, as in graph
?x ?q 42 . // integers in SPARQL queries are implicitly typed as xsd:integer
}

2) Blank nodes
! no guarantee that blank node labels will be unchanged over repeated queries

- SPARQL Constraints: constraints can be applied to variables
SELECT ?title
WHERE {
?x dc:title ?title .
FILTER regax(?title, "^SPARQL")
}

- Optional Graph Patterns
SELECT ?name ?mbox
WHERE {
?x foaf:name ?name .
OPTIONAL {
?x foaf:mbox ?mbox .
}
}
=> I'm interested in mbox, but it doesn't matter to be at first part

- Union Graph Patterns
PREFIX dc10: <http://purl.org/dc/elements/1.0/>
PREFIX dc11: <http://purl.org/dc/elements/1.1/>
SELECT ?title
WHERE {
{ ?book dc10:title ?title }
UNION
{ ?book dc11:title ?title }
}

- Default Graph / Named Graphs
SELECT ?who ?g ?mbox
FROM <http://example.org/dft.ttl> // the default graph. unless otherwise specified, all triples are taken from that graph
FROM NAMED <http://example.org/alice>
FROM NAMED <http://example.org/bob>
WHERE {
?g dc:publisher ?who .
GRAPH ?g { ?who foaf:mbox ?mbox }
}

- Ordering
SELECT ?name
WHERE {
?x foaf:name ?name ; :empId ?emp .
} ORDER BY ? name DESC(?emp) // order results by ?name, and the by ?emp in descending order
// ASC() sorts in ascending order

- Limit and Offset
SELECT ?name
WHERE {
?x foaf:name ?name .
}
ORDER BY ? name
LIMIT 5
OFFSET 10 // returns five results, after skipping the first then results

- Distinct
SELECT DISTINCT ?name // removes duplicate results
WHERE {
?x foaf:name ?name .
}

- CONSTRUCT: returns an RDF graphs, specified by a graph template
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX vcard: <http://www.w3.org/2001/vcard-rdf/3.0#>
CONSTRUCT {
?x vcard:FN ?name .
?x vcard:EMAIL ?mail .
}
WHERE {
?x foaf:name ?name .
?x foaf:mbox ?mail .
}

- ASK: checks whether a query pattern has a solution

- DESCRIBE: returns a single graph containing information about a resource or resources
1) nature of description left unspecified: black node closure / concise bounded description
2) structure of returned data is determined by the SPARQL query processor

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

https://www.w3.org/TR/rdf-sparql-query/

https://jena.apache.org/tutorials/sparql.html

http://www.cambridgesemantics.com/semantic-university/sparql-by-example

3. SPARQL Protocol
: defines the method of interaction with a SPARQL processor

- SPARQL over HTTP
1) HTTP GET
* query encoded as HTTP requested URI
* limitation on query length
GET /sparql/?query=EncodedQuery HTTP/1.1
HOST: www.example.org
User-agent: my-sparql-client/0.1
2) HTTP POST
* query encoded in HTTP request body
* no limitation on query length

- SPARQL results format : based on Standard XML format
<?xml version="1.0" ?>
<sparql xmlns="http://www.w3.org/2005/sparql-results#">
<head>
<variable name="book" /> 
<variable name="who" />
</head>
<results distinct="false" ordered="false"> 
<result> 
<binding name="book"> 
<uri>http://www.example.org/book/book5</uri>
<binding>
<binding name="who">
<bnode>r29392923r2922</bnode>
</binding>
</result>
...
</results>
</sparql>

https://w3c.github.io/rdf-tests/sparql11/data-sparql11/protocol/index.html

4. SPARQL 1.1
: extending SPARQL

- INSERT DATA
PREFIX dc: <http://purl.org/dc/elements/1.1/>
INSERT DATA {
<http://example.org/book1> dc:title "A new book" ;
dc:creator "A.N.Other" .
}

- DELETE DATA
PREFIX dc: <http://purl.org/dc/elements/1.1/>
DELETE DATA {
<http://example.org/book2> dc:title "David Copperfield" ;
dc:creator "Edmund Wells" .
}

- UPDATE: DELETE/INSERT
PREFIX foaf: <http://xmlns.com/foaf/0.1>
DELETE DATA {
?person foaf:givenName "Bill" .
}
INSERT DATA {
?person foaf:givenName "William" .
}

- Aggregates
PREFIX : <http://books.example.org/>
SELECT (SUM(?lprice> AS ?totalPrice)
WHERE {
?org :affiliates ?auth .
?auth :writesBook ?book .
?book :price ?lprice .
}
GROUP BY ?org
HAVING (SUM(?lprice) > 10)

* other aggregate functions: COUNT, MIN, MAX, GROUP_CONCAT, SAMPLE

- Subqueries
PREFIX : <http://people.example.org/>
SELECT ?y ?minName
WHERE {
:alice :knows ?y .
{
SELECT ?y (MIN(?name) AS ?minName)
WHERE {
?y :name ?name .
}
GROUP BY ?y
}
}

- Alternatives: sugared syntax for UNION
PREFIX dc: <http://purl.org/dc/elements/1.1/>
SELECT ?displayString
WHERE {
:book1 dc:title|rdfs:label ?displayString .
}

- Sequences: sugared syntax for bnode
SELECT ?name
WHERE {
?x foaf:mbox <mailto:alice@example.org> .
?x foaf:knows/foaf:name ?name .
}
=> ?x foaf:knows [ foaf:name ?name ]

- Arbitrary Sequences
SELECT ?name
WHERE {
?x foaf:mbox <mailto:alice@example.org> .
?x foaf:knows+/foaf:name ?name .
}

* repeat operators: * (zero or more occurrences) / + (one or more occurrence)
{n} (exactly n occurrences) / {n,m} (between n and m occurrences)

- Inverses
SELECT ?name
WHERE {
<mailto:alice@example.org? ^foaf:mbox ?x .
?x foaf:knows/^foaf:name ?name .
FILTER(?x != ?name)
}

https://www.w3.org/TR/sparql11-protocol/

Description Logic

1. Description Logics
: A family of knowledge representation formalisms
- a subset of first order predicate logic (FOPL)
- decidable: trade-off of expressivity against algorithmic complexity

- Description logics restrict the predicate types that can be used
1) Person(x): unary predicates denote class membership
2) hasChild(x, y): binary predicates denote relations (roles) between instances

- Defining ontologies with Description Logics
1) describe classes (concepts) in terms of their necessary and sufficient attributes (roles)
* A is a necessary attribute of C: If an object is an instance of C, then it has A
* A is a sufficient attribute of C: If an object has A, then it is an instance of C

- Description Logic Reasoning Tasks
1) satisfaction: can this class have any instances?
2) subsumption: is every instance of class A necessarily an instance of class B?
3) classification: what classes is this object an instance of?

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

2. Syntax
- Concept Constructors

Boolean class constructors	￢C, C ∩ D, C ∪ D	Child ∩ Happy => the class of things which are both children and happy
Restrictions on role successors	∀R.C, ∃R.C	∀hasPet.Cat => the class of things all of whose pets are cats or, which only have pets that are cats ! includes those things which have no pets ∃hasPet.Cat => the class of things which have some pet that is a cat ! must have at least one pet
Number restrictions (cardinality constraints) on roles	≤n R, ≥n R, =n R	≥2 originCountry => the class of things with more than one country of origin
Nominal (singleton concepts)	{x}
Universal class, top	Τ
Contradiction, bottom	⊥

- Role Constructors

Inverse roles	R-
Transitive roles	R+
Role composition	R ° S

- OWL and Description Logics
1) Not every description logic supports all constructors
2) More constructors = more expressive = higher complexity
3) OWL DL is equivalent to the logic SHOIN(D)
http://www.cs.man.ac.uk/~ezolin/dl/

- Knowledge Bases
1) TBox terminology: a set of axioms describing the structure of the domain (concepts, roles)

Concept inclusion	C ⊆ D
Concept equivalence	C ≡ D
Role inclusion	R ⊆ S
Role equivalence	R ≡ S
Role transitivity	R+ ⊆ R

2) ABox terminology: a set of axioms describing a concrete situation (instances)

Concept instantiation	x:D
Role instantiation	<x, y>:R

3. Semantics
- Description Logics and Predicate Logic
1) Description Logics are a subset of first order Predicate Logic
2) Every DL expression can be converted into an equivalent FOPL expression

- Every concept C is translated to a formula ΦC(x)
1) Boolean class constructors
￢ΦC(x) = Φ￢C(x)
ΦC∩D(x) = ΦC(x) ∩ ΦD(x)
ΦC∪D(x) = ΦC(x) ∪ ΦD(x)

2) Restrictions
Φ∀R.C(y) = ∀x.R(y,x) ⇒ ΦC(x)
Φ∃R.C(y) = ∃x.R(y,x) ∧ ΦC(x)

3) Concept inclusion
C ⊆ D = ∀x.C(x) ⇒ ΦD(x)

4) Concept equivalence
C ≡ D = ∀x.C(x) ⇔ ΦD(x)

- Interpretation function : ext()

Syntax	Semantics	Notes
ext(￢C)	△\ext(C)	Complement
ext(C ∩ D)	ext(C) ∩ ext(D)	Conjunction
ext(C ∪ D)	ext(C) ∪ ext(D)	Disjunction
ext(∀R.C)	{x\| ∀y.<x,y> ∈ ext(R) ⇒ y ∈ ext(C)}	Universal
ext(∃R.C)	{x\| ∃y.<x,y> ∈ ext(R) ∧ y ∈ ext(C)}	Existential
≤n R	{x\| #{y\| <x,y> ∈ ext(R)} ≤ n }	Max Cardinality
≥n R	{x\| #{y\| <x,y> ∈ ext(R) ≥ n }	Min Cardinality
=n R	{x\| #{y\| <x,y> ∈ ext(R) = n }	Cardinality
ext(Τ)	△	Top
ext(⊥)	Ø	Bottom

https://arxiv.org/pdf/1201.4089.pdf

Ontologies

1. Knowledge Representation
- Knowledge representation is central to the Semantic Web
- Long-standing concern in Artificial Intelligence
- Most AI systems (and therefore the Semantic Web systems) consist of ...
1) a knowledge base (KB): structured according to the knowledge representation approach taken
2) an inference mechanism: set of procedures that are used to examine the knowledge base to answer questions solve problems or make decisions within the domain

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

2. Ontologies
- An ontology is a specification of a conceptualisation
1) specification: a formal description
2) conceptualisation: the objects, concepts, and other entities that are assumed to exist in some area of interest and the relationships that hold among them

- Ontology in Computer Science
1) constituted by a specific vocabulary used to describe a certain reality
2) a set of explicit assumptions regarding the intended meaning of the vocabulary
3) benefits: shared understanding / facilitate communication / inter-operability

- Ontology Structure: typically have two distinct components
1) Names for important concepts in the domain
2) Background knowledge/constraints on the domain

3. Informal Usage
: Informally, 'ontology' may also be used to describe a number of other types of conceptual specification

- Controlled Vocabularies
1) An explicitly enumerated list of terms, each with an unambiguous, non-redundant definition
2) no structure exists between terms - a flat list
e.g. Library of Congress Subject Headings (LCSH)

- Taxonomies
1) a collection of controlled vocabulary terms organised into a hierarchical structure
2) each term is in one or more parent-child relationships
e.g. Library Classification schemes(Library of Congress, Dewey Decimal, UDC)

- Thesauri
1) a taxonomy with additional relations showing lateral connections: Related Terms (RT) and See Also
2) parent-child relation usually described in terms of Broader Terms (BT) and Narrower Terms (NT)

- Ontology
1) an ontology further specialises types of relationships (particularly related terms)
2) typically includes class definitions and hierarchy, relation definitions ad hierarchy
3) may also include constraints, axioms and rule-based knowledge

- Summary
1) Controlled Vocabulary + Hierarchy = Taxonomy
2) Taxonomy + later relations = Thesaurus
3) Thesaurus + typed relations + constraints + rules + axioms = Ontology

http://www-ksl.stanford.edu/kst/what-is-an-ontology.html

http://protege.stanford.edu/publications/ontology_development/ontology101-noy-mcguinness.html

RDF Schema

1. Using RDF to define RDF Schema
- RDF Schema (RDFS) is an RDF vocabulary which contains ...
1) Classes for defining classes and properties
* class definitions
<rdf:Description rdf:about="#Person">
<rdf:type rdf:resource="&rdfs;Class"/>
</rdf:Description>
↓
<rdfs:Class rdf:about="#Person"/>

* Employee is a subclass of Person
<rdfs:Class rdf:about="#Employee">
<rdfs:subClassOf rdf:resource="#Person"/>
</rdfs:Class>

* rdfs:subClassOf is transitive: (A rdfs:subClassOf B) and (B rdfs:subClassOf C) implies (A rdfs:subClassOf C)
* rdfs:subClassOf is reflexive: All classes are subclasses of themselves
* rdf:type distributes over rdf:subClassOf: (A rdfs:subClassOf B) and (C rdf:type A) implies (C rdf:type B)

2) Properties for defining basic characteristics of classes and properties
* property definitions
<rdf:Description rdf:about="#worksFor">
<rdf:type rdf:resource="&rdfs;Property"/>
</rdf:Description>
↓
<rdf:Property rdf:about="#worksFor"/>

* The property worksFor relates objects of class Employee to objects of class Company
<rdf:Property rdf:about="#worksFor">
<rdfs:domain rdf:resource="#Employee"/> /* the class that the property runs from */
<rdfs:range rdf:resource="#Company"/> /* the class that the property runs to */
</rdf:Property>

* worksFor is a subproperty of affiliatedTo
<rdf:Propertyrdf:about="#worksFor ">
<rdfs:subPropertyOf rdf:resource="#affiliatedTo"/>
</rdf:Property>

* rdfs:subClassOf is transitive and reflexive

3) Some ancillary properties
* rdfs:label is used to give a human readable name for a resource
* rdfs:comment is used to give a human readable description for a resource
* rdfs:seeAlso is used to indicate a resource which can be retrieved to give more information about something

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

https://www.w3.org/TR/rdf-schema/

Linked Data

1. Linked Data
: how do we publish the Semantic Web Data?
: what identifiers do we use?

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

http://linkeddata.org/

2. Semantic Web Principles
- Anyone can make assertions about anything

- Entities are referred to using Uniform Resource Identifiers
1) a resource can be anything that has identity
2) the resource is the conceptual mapping to an entity or set of entities, not necessarily the entity which corresponds to that mapping at any particular instance in time
3) httpRange-14: "What is the range of the HTTP range dereference operation?"
=> HTTP URIs (without "#") should be understood as referring to documents, not cars
4) Information Resource
* resources, identified by URIs and whose essential characteristics can be conveyed in a message
* If dereferencing the URI results in a 200 OK response code, the resource is an information resource
* If it results in 303 See Other response, the resource could be any resource

- Based on XML technologies

- Formal semantics

3. The Linked Data Principles
: Set of publishing practices for the Semantic Web data
- Use URIs as names for things
1) don't use bNodes, always give URIs as you can
2) use a unique identifier to denote things

- Use HTTP URIs so that people can look up those names
1) enables "lookup" of URIs via Hypertext Transfer Protocol
2) piggy-backs on hierarchical Domain Name System to guarantee uniqueness of identifiers
3) connect logical level (thing) with physical level (source)

- When someone looks up a URI, provide useful information
1) when somebody looks up a URI, return data using the standards (RDF*, SPARQL)

- Include links to other URIs, so that they can discover more things

4. Publishing Semantic Web Data
- Defining RDF Vocabularies
1) the Semantic Web Best Practice Recipes for Publishing RDF Vocabularies
* distinguishes between 'hash' and 'slash' namespaces
* uses content negotiation (HTTP Accept: header) to serve different representations of resources

https://www.w3.org/TR/swbp-vocab-pub/

5. Cool URIs
: URIs should be designed with three things in minds; simplicity, stability and manageability

https://www.w3.org/TR/cooluris/

https://www.w3.org/Provider/Style/URI

Resource Description Framework

1. What is the Resource Description Framework?
- a standard data model for the Semantic Web
1) data model: statements about resources in the form of S-P-O triples
2) Collection of RDF statements represents a labelled, directed graph

- a knowledge representation language
1) RDF is used as the foundation for the other knowledge representation and ontology languages on the Semantic Web

- a family of data formats and notations
1) RDF/XML: the normative (standard) syntax
2) RDF/N3 family: compact, human-friendly, non-XML syntax (N3, Turtle, Ntriple)

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

https://www.w3.org/RDF/

https://jena.apache.org/tutorials/rdf_api.html

2. RDF Requirements
- A means for identifying objects and vocabulary terms (URIs)
1) URI: Uniform Resource Identifier
2) URIrefs: URI references are URIs with optional fragment identifiers

https://lists.w3.org/Archives/Public/www-rdf-comments/2002OctDec/0043.html

- A means for distinguishing between terms from different vocabularies (XML namespaces and qualified names)
1) RDF uses XML namespaces to refer to elements of domain vocabularies
2) Namespaces used to abbreviate URIrefs to qualified names (QNames)

- A means for serialising triples (XML)

3. RDF/XML
: an XML-based format for expressing a collection of RDF triples (an RDF graph)

https://www.w3.org/TR/rdf-syntax-grammar/

https://www.w3schools.com/xml/xml_rdf.asp

- The anatomy of an RDF/XML file

<?xml version="1.0" ?>
<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:dc="http://purl.org/dc/elements/1.1"
xmlns:ex="http://example.org/ontology#">
<rdf:Description rdf:about="http://www.example.org">
<dc:title>Example Inc.Homepage</dc:title>
<dc:creator rdf:resource="mailto:amy@example.org"/>
<dc:creator>
<rdf:Description rdf:about="mailto:john@example.org">
<ex:name>John Smith</ex:name>
</rdf:Description>
</dc:creator>
</rdf:Description>
<ex:Website rdf:about="http://www.example.org"/>
</rdf:RDF>

1) Resource-valued predicates use the rdf:resource attribute
2) can have multiple predicates within an rdf:Description element
3) class membership: an object's membership of a class is indicated using the rdf:type and can be replaced with QName of class

<rdf:Description rdf:about="http://www.example.org">
<rdf:type rdf:resource="http://example.org/ontology#Website"/>
</rdf:Description>

xmlns:ex="http://example.org/ontology#"
<ex:Website rdf:about="http://www.example.org"/>

4) the striped syntax: graph could be serialised using two rdf:Description elements and the second statement could be inserted within the predicate element of the first

<rdf:Description rdf:about="http://www.example.org">
<dc:creator rdf:resource="mailto:john@example.org"/>
</rdf:Description>
<rdf:Description rdf:about="mailto:john@example.org">
<ex:name>John Smith</ex:name>
</rdf:Description>

<rdf:Description rdf:about="http://www.example.org">
<dc:creator>
<rdf:Description rdf:about="mailto:john@example.org">
<ex:name>John Smith</ex:name>
</rdf:Description>
</dc:creator>
</rdf:Description>

- Common RDF/XML idioms
1) XML entities are defined for the XML namespaces URI prefixes
<?xml version="1.0" ?>
<!DOCTYPE rdf:RDF [
<!ENTITY rdf 'http://www.w3.org/1999/02/22-rdf-syntax-ns#'>
<!ENTITY dc 'http://purl.org/dc/elements/1.1'>
<!ENTITY ex 'http://example.org/ontology#'>
]>
<rdf:RDF xmlns:rdf="&rdf;"
xmlns:dc="&dc;"
xmlns:ex="&ex;">
2) used to abbreviate long URIrefs in attribute values (because QNames can't be used there)

- Common RDF idioms
1) Assertions about the null URIref are about the RDF file itself

- Blank nodes (bNodes): a node in an RDF graph representing a resource for which a URI or literal is not given
1) the striped syntax simplifies the RDF/XML serialisation -> remove the rdf:about attribute
=> we don't know two nodes are same or different...
<rdf:Description rdf:about="http://www.example.org">
<dc:creator>
<rdf:Description>
<ex:name>John Smith</ex:name>
</rdf:Description>
</dc:creator>
</rdf:Description>
<rdf:Description rdf:about="http://test.example.org">
<dc:creator>
<rdf:Description>
<ex:name>John Smith</ex:name>
</rdf:Description>
</dc:creator>
</rdf:Description>
https://en.wikipedia.org/wiki/Blank_node

- Node IDs: identifiers which are local to a given serialisation of an RDF graph
1) ambiguities resulting from blank nodes are resolved by using node IDs
2) not guarantee to remain unchanged when an RDF file is parsed and serialised
<rdf:Description rdf:about="http://www.example.org">
<dc:creator rdf:nodeID="foo23" />
</rdf:Description>
<rdf:Description rdf:about="http://test.example.org">
<dc:creator rdf:nodeID="foo23" />
</rdf:Description>
<rdf:Description rdf:nodeID="foo23">
<ex:name>John Smith</ex:name>
</rdf:Description>
https://www.w3.org/wiki/NodeId

rdf:about	rdf:nodeID
to specify the subjects of triples	to declare a new URIref within a document

- Datatypes: literal values presented so far are plain and do not have a type
=> RDF uses XML Schema datatypes

- Containers
1) RDF provides means for describing groups of objects
2) containers are mutable: a third party could add new members to a container
3) three types of container are available in RDF:
rdf:Bag (an unordered group), rdf:Seq (an ordered group), rdf:Alt (a group of alternative)
<rdf:Description rdf:about="http://www.example.org">
<ex:members>
<rdf:Bag>
<rdf:li rdf:resource="mailto:john@example.org"/>
<rdf:li rdf:resource="mailto:sally@example.org"/>
<rdf:li rdf:resource="mailto:bill@example.org"/>
</rdf:Bag>
</ex:members>
</rdf:Description>

- Collections
1) a different way of expressing ordered finite groups in RDF
2) collections are immutable: cannot be altered without rendering the collection ill-formed
3) similar to linked list
<rdf:Description rdf:about="http://www.example.org">
<ex:members rdf:parseType="Collection">
<rdf:Description rdf:about="mailto:john@example.org"/>
<rdf:Description rdf:about="mailto:sally@example.org"/>
<rdf:Description rdf:about="mailto:bill@example.org"/>
</ex:members>
</rdf:Description>

4. The RDF/N3 Family
- Ntriples, N3 and Turtle
1) Simpler syntaxes than RDF/XML
* Ntriples is the simplest (a subset of Turtle)
* N3 and Turtle are more concise
* Turtle is the standard version of N3

2) General syntax for a triple
* <subject> <predicate> <object> .
* Resources are indicated <like this>
* Literals are indicated "like this"

https://www.w3.org/2000/10/swap/Primer.html

- The anatomy of an Ntriples file
<http:www.sciam.com/> <http://purl.org/dc/elements/1.1/title> "Scientific American" .

- The anatomy of an Turtle/N3 file
1) ";" allows grouping of triples with common subject
<http:www.example.org>
<http://purl.org/dc/elements/1.1/creator> <mailto:john@example.org> ;
<http://purl.org/dc/elements/1.1/title> "Example Inc. Homepage" .

2) "," allows grouping of triples with common subject and predicate
<http:www.example.org>
<http://purl.org/dc/elements/1.1/creator> <mailto:john@example.org> , <mailto:amy@example.org>

- Common RDF/N3 idioms
1) @prefix used to introduce QName abbreviations to N3 and Turtle
@prefix rdf:<http://www.w3.org/1999/02/22-rdf-syntax-ns#>
@prefix rdf:<http://purl.org/dc/elements/1.1>
@prefix rdf:<http://example.org/ontology#>
<http://www.example.org> dc:creator <mailto:john@example.org> ;
rdf:type ex:Website .

2) @base used to introduce a base URI relative to which all URI fragment identifiers are expanded
@base <http:example.org/data>
@prefix foaf: <http://xmlns.com/foaf/0.1/>
<#john> foaf:name "John Smith"

- bNodes in N3 and Turtle
1) uses []
<http://www.example.org> dc:creator [ ex:name "John Smith" ] .
2) with nodeIDs
<http://www.example.org> dc:creator _:foo23 .
<http://test.example.org> dc:creator _:foo23 .
_:foo23 ex:name "John Smith" .

Introduction to the Semantic Web

1. What is the Semantic Web?
: an extension of the current Web in which information is given a well-defined meaning, better enabling computers and people to work in cooperation.

- The annotated Web
1) Enrich existing web pages with annotations
2) Annotations enable enhanced browsing and searching

- The Web of Data
1) Expose existing databases in a common format: it allows the integration of data in unexpected ways
2) Express existing database schemas in a machine-understandable form: it allows reasoning about data

https://www.w3.org/standards/semanticweb/

2. The Origins of the Semantic Web
- Interwoven themes: Knowledge Based Systems + Hypertext/Hypermedia + Library and Information Science
1) Knowledge representation
* Long-standing discipline within Artificial Intelligence
* Knowledge representation languages should handle qualitative knowledge
e.g. RDF, RDF Schema and OWL
2) Hypertext/Hypermedia
* Links: essence of hypermedia is connection
* Open hypermedia makes links between different bits of knowledge but Network knowledge representation makes links that are knowledge
3) Library and Information Science
* Library cataloguing = metadata
* Metadata: data about data

http://artint.info/html/ArtInt_8.html

3. Basic Concepts

The World Wide Web	The Semantic Web
the web for people	the web for machines
machine readable: information needs humans to give it interpretation	machine understandable: information is structured so that it can be interpreted by machines
technologies include URI, HTTP, XML and HTML	technologies include RDF, RDFS and OWL

4. Semantic Web Technical Architecture
- Fundamental Principles
1) Anyone can make assertions about anything
2) Entities are referred to using Uniform Resource Identifiers
3) Based on XML technologies
4) Formal Semantics

- The Semantic Web layer cake: https://en.wikipedia.org/wiki/Semantic_Web_Stack

- The triple: underlying model of triples used to describe the relations between entities in the Semantic Web
(subject) -- [predicate] --> (object)

- RDF: Resource Description Framework
1) a framework for representing information about resources on the WWW and beyond
  http://melancholy8914.blogspot.co.uk/2017/06/resource-description-framework.html

- RDF Schema: RDF Vocabulary Description Language
1) an RDF vocabulary which we can use to define other vocabularies
  http://melancholy8914.blogspot.co.uk/2017/06/rdf-schema.html

- OWL: Web Ontology Language
1) OWL provides more expressive features than RDF Schema
  http://melancholy8914.blogspot.co.uk/2017/06/ontologies.html

  http://melancholy8914.blogspot.co.uk/2017/06/web-ontology-language.html

- SPARQL: the SPARQL Protocol and RDF Query Language
http://melancholy8914.blogspot.co.uk/2017/06/sparql-protocol-and-rdf-query-language.html

5. Vocabularies and Applications
- Social Networking
1) FOAF
* Friend Of A Friend
* a machine readable ontology describing persons, their activities, and their relations to other people and objects
http://www.ldodds.com/foaf/foaf-a-matic.html

2) SIOC
* Semantically-Interlinked Online Communities
* ontology for describing interconnecting discussion methods like wikis, bulletin boards, blogs etc
http://sioc-project.org/

- Bibliographic Metadata
1) Dublin Core
* A standard set of 15 metadata elements for cross-domain information resource description
* possibly the most widely used Semantic Web vocabulary
http://dublincore.org

- Cultural Heritage
1) CIDOC CRM
* ICOM's International committee for DOCumentation Conceptual Reference Model
* ontology for heterogeneous cultural heritage information
http://www.cidoc-crm.org/

- Knowledge Organisation
1) SKOS
* Simple Knowledge Organisation System
* standard vocabulary to support thesauri, classification schemes, subject heading lists, taxonomies, and other types of controlled vocabulary
* semantic relationships: broader, narrower, related terms
https://www.w3.org/2004/02/skos/

- Web Annotation
1) Annotea
* shared annotations for the Web
* Annotea-enabled browsers can query server to obtain annotations for pages
* Open Annotation Data Model: a framework for creating associations between resources
http://www.openannotation.org/spec/core/

- Commerce
1) Good Relations
* standardised vocabulary for product, price, and company data

Meta-AspectJ

1. Meta-AspectJ
: a language tool for generating Java and AspectJ programs using code templates
: meta-programming language
: built on top of AspectJ (hence Java)
: guarantees syntactic hygiene
=> use of typed syntax trees
=> SafeGen extension guarantees referential hygiene
http://yanniss.github.io/maj/

2. Meta-programming requires representing programs as data objects
: A meta-program is a program that represents and manipulates programs as data objects at its run-time
: A meta-programming language provides language support to represent programs as data objects (reflection)

- Program representation methods:
1) text => bad
2) objects => better but still clumsy: typically as abstract syntax tree(AST)
3) AST with quote/unquote

3. Quote/unquote representation of programs as data objects
- Let the compiler build the AST!
1) use concrete syntax instead of AST constructors
2) tell the compiler to return AST (instead of compiling): quote program text
VarDec v = `[ int i; ];

- Splice meta-level values into AST!
1) turn meta-language computation results into objects
2) tell the compiler to copy AST: unquote expressions (vars)
VarDec v = `[ int i; ];
Class cl = Foo.class;
ClassDec = `[ class #[cl.getName()]{ #v } ];

- Additional operations:
1) emit: turn data object into source code (program code)
2) eval: turn data object into object code
3) run: execute data object (runtime code generation)

4. Quote/unquote in Meta-AspectJ
- More complicated in languages with richer syntax
1) quote must parse program text
infer v = `[ int x = 0 ; ];

2) unquote must ensure well-formed syntax-trees
infer c = `[ class C { #v } ];

3) Meta-AspectJ supports type inference of quotations

https://wiki.hh.se/wg211/images/f/f5/Yannis-smaragdakis-ifip06.pdf

5. Meta-programming requires manipulating programs as data objects
- quote/unquote is representation mechanism only
- meta-programming needs support for
... parsing existing programs
... traversing ASTs
... pattern matching over ASTs
... manipulating ASTs
=> accidental complexity: not original purpose

6. Meta-AspectJ builds on AspectJ to avoid accidental complexity
: Generate Aspects!
- generated aspects implement a generator functionality
- AspectJ implements generator mechanism

A Trivial Meta-AspectJ Example

void generateTrivialLogger(String cn, String mn){
infer aspectCode = '[
package MyPackage;
aspect #[cn + "_" + mn + "Logger"] {
before : call(* #cn.#mn(..)){
out("calling method " + #mn + " in class " + #cn);
}
}
}];
System.out.println(aspectCode.unparse());
}

7. Encoding meta-programming as meta-programming language constructors
- Observation: most meta-programming iterates over lists in AST and checks AST types
=> accidental complexity
- Solution: new meta-programming language (SafeGen)
#defgen makeInterface (Class c){
interface I {
#foreach(Method m : MethodOf(m, c)) {
void #[m] ();
}
}
}

Template meta-programming in C++

1. C++ templates are parameterized declarations
- class templates (struct similar)
template<class T> // template parameter declaration
class stack {
std::vector<T> s; // parameter used as template argument
public:
void push(const T& t); // template parameter usage
T pop();
bool is_empty() { ... }
};

- function templates: parameterises concrete function on argument type
template<class T>
T min(const T& a, const T& b){
if(a < b) return a;
else return b;
}

http://www.cplusplus.com/doc/oldtutorial/templates/

https://msdn.microsoft.com/en-us/library/y097fkab.aspx

2. Templates and Polymorphism
: Templates implement parametric polymorphism: (almost) no assumptions about template parameter

3. Template Parameters
- types / classes: most common cases
1) usually denoted by class keyword
2) alternative syntax: typename

- non-types: can have (integral type) value arguments but class templates only
template<class T, int Max>

- templates: type parameters can be class templates
template<template <class T> class TT>

- all parameter classes can be defaulted:
struct nil {};
template<class T = nil, int Max = 10>
class tuple;
tuple<int, float, char> a;
tuple<std::string> b;

4. Template instantiation is syntactic macro expansion
: instantiation of (non-default) parameters with arguments triggers expansion by compiler
: fully expanded template is like normal type
- function templates can be implicitly instantiated
int smaller = ::min(1,2);
std::string a("Cat"), b("Hat")l
std::string first = ::min(a, b);
- Template instantiation and Code bloat
=> Implementation usually follows instantiation model
=> for each template instance, a separate piece of code is generated, and compiled: no sharing between different template instrances

http://www.cplusplus.com/forum/articles/14272/

http://stackoverflow.com/questions/24333345/how-does-template-cause-the-code-bloat-in-c

5. Template Specialization
- a program can provide specialised versions of templates
- specialisation redefines entire templates: no "inheritance" of member functions
- a compiler must select the most specialised instance
! T1 more specialised than T2 ( T1 > T2 )
iff "every template argument list that matches T1 also matches T2, but not vice versa"
!! T1 is maximally specialised (wrt. T)
iff it matches T and there is no more specialised T2 matching T
!!! compile-time error if no matching instance at all / no unique maximally specialised template for instance

- specialisation is allowed for all template parameters
- requires compile-time expression evaluation
- selection of most specialised instances can encode conditionals
http://www.cprogramming.com/tutorial/template_specialization.html

6. Template meta-functions can mix compile-time and run-time arguments
template<int n>
int power(int m){
return power<n-1>(m) * m;
}
template<> int power<0>(int m){ return 1; }

7. Template meta-programming
: template meta-programming is partial evaluation
https://en.wikipedia.org/wiki/Partial_evaluation

: no binding time analysis but staging
=> turning function arguments into template arguments

8. Concepts of the Template Meta-programming Language
- Class templates as functions
1) input: integers or types (realised by template parameters)
2) output: integers or types (realised by enum or typedef called RET)

- Integers and types as data
- Symbolic names instead of variables
1) constant initialization / typedef instead of assignment
2) no update
- Lazy evaluation: template only instantiated if struct accessed (via ::)

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

https://www.codeproject.com/Articles/3743/A-gentle-introduction-to-Template-Metaprogramming

Template IF<>	Template WHILE<>
IF<> as "syntactic sugar" for specialisation	WHILE<> as "syntactic sugar" for recursion
template<bool Cond, class Then, class Else> struct IF { typedef Then RET; }; // only specialisation for Cond==false required template<class Then, class Else> struct IF<false, class Then, class Else> { typedef Else RET; }; // usage IF<1==0, int, double>::RET f; // double f; const static int g = IF<1==0, Zero, One>::RET; // g = One::RET;	template<class Stmt> struct STOP { typedef Stmt RET; } template<class Cond, class Stmt> struct WHILE { typedef IF<Cond::template Code<Stmt>:: RET, WHILE<Cond, typename Stmt::Next>, STOP<Stmt> >::RET::RET RET }

Fibonacci via Templates

template<int n>
struct Fibonacci {
enum { RET = WHILE<FibCond<n>,
FibStat<1, 1, 0>
>::RET::x
};
};

template<int i_, int x_, int y>
struct FibStat {
enum { i = i_, x = x_ };
typedef FibStat<i+1, x+y, x> Next;
};

template<int n>
struct FibCond {
template<class Memory>
struct Code {
enum { RET = Memory::i < n };
};
};

Loop Unrolling via an (inlined) function templates

template<int n>
inline void addVect(double* c, double* a, double* b){
*c = *a + *b'
addVect<n - 1>(c + 1, a + 1, b + 1);
}
template<>
inline void addVect<0>(double* c, double* a, double* b){ }

Loop Unrolling via Templates

template<int n, class B>
struct FOR {
static void loop(int m){
for(int i = 0 ; i < m/n ; i++){
UNROLL<n, B>::iteration(i * n);
}
for(int i = 0 ; i < m%n ; i++){
B::body(n * m/n + i);
}
}
};

template<int n, class B>
struct UNROLL {
static void iteration(int i){
B::body(i);
UNROLL<n-1, B>::iteration(i + 1);
}
};

template<class B>
struct UNROLL<0, B> {
static void iteration(int i) { }
};

class AddVecBody {
private double *a, *b, *c;
inline void body(int i){
*(c+1) = *(a+1) + *(b+1);
}
};

// Add two 1000-element vectors in chunks of 4
FOR<4, AddVecBody>::loop(1000);

Encoding Abstract Data Types

1) use class templates as constructor functions
2) represent fields via
- enum (== values)
- typedef (== pointers)
- copy constructor arguments into local fields
3) use class templates to implement methods
https://en.wikipedia.org/wiki/Abstract_data_type

struct Nil {
enum { head = ERROR };
typedef Nil Tail;
};

template<int head_, class Tail_ = Nil>
struct Cons {
enum { head = head_ };
typedef Tail_ Tail;
};

// recurse over lists, stop via specialisation
template <class List>
struct Length {
enum { RET = Length<typename List::Tail>::RET + 1 };
};
template <>
struct Length<Nil> {
enum { RET = 0 };
};

template <class L1, class L2>
struct Append {
typedef Cons<L1::head,
typename Append<typename L1::Tail, L2>::RET
> RET;
};
template <class L2>
struct Append<Nil, L2> {
typedef L2 RET;
};

Expression Templates

Template meta-programming can implement domain-specific languages
1) Expression template represents AST
2) class templates implement AST transformations
3) eval method links syntax (AST) to semantics (C++): inline trick allows code generation
4) function templates using overloaded operations provided syntactic sugar
https://en.wikipedia.org/wiki/Expression_templates

https://www.codeproject.com/Articles/998366/Gentle-introduction-into-expression-templates

// General expression template: scalar with eval
template <class L, class BinOp, class R>
class Expr {
L &l_; R &r_;
public:
Expr(const L &l, const R &r) : l_(l), r_(r) {};
double eval(){
return BinOp::apply(l_, r_);
}
// vector with index
double operator[](uint i){ return BinOp::apply(l_[i], r_[i]); };
};

// operator tags; similar for minus, times, ...
class plus {
inline double apply(double a, double b){ return (a+b); }
};

// additional operator; similar for minus, times, ...
template<class L, class R>
Expr<L, plus, R> operator+(const L &l, const R &r){ return Expr<L, plus, R>(l, r); };