Monday, June 15, 2009

Embedded OpenGL

OpenGL is a graphics library that has provided a foundation for many other high-level graphics libraries built on top of it. Because it is so versitle and low-level, it has been proven to stand the test of time, and has evolved to handle the changing demands that library authors have been placed on it. As demands have changed, new functions are added, and one trend between all versions of OpenGL is that more specific functions are being replaced by more general functions. For example, the functions glColorPointer, glNormalPointer, and glTexCoordPointer have been augmented with glVertexAttribPointer, which can be used to replace all of the previous functions. This has led to a completely different view of OpenGL that has led to the development of smaller profile of OpenGL functions called the Embedded Specification, or OpenGL-ES for short. One side effect of this is that the more abstract functions are increasingly similar to an object-oriented library, which means there are fewer and fewer functions that do not fit into an object model of OpenGL. If we partition the functions found in OpenGL-ES 2.0 into an object-oriented hierarchy, then we arrive at the following classes:

  • Blend
  • Buffer -- pixel buffers, vertex buffers, and index buffers
  • Capability -- abstract class with glEnable and glDisable
  • Clear -- clearing the background to a solid color
  • Color
  • CullFace -- consists of glCullFace and glFrontFace
  • Depth
  • FrameBuffer
  • Get -- reading global state with functions like glGetString etc.
  • Mipmap -- utilities for the Texture class
  • Program
  • RenderBuffer
  • Shader -- vertex and fragment shaders
  • Stencil
  • Texture
  • Uniform -- uniform variables
  • VertexAttrib -- vertex attributes

after removing these functions from the OpenGL-ES 2.0 API, we are left with the miscellaneous functions:

  • glDrawArrays(mode, first, count)
  • glDrawElements(mode, count, type, indices)
  • glFinish()
  • glFlush()
  • glLineWidth(width)
  • glPolygonOffset(factor, units)
  • glSampleCoverage(value, invert)
  • glPixelStorei(name, param)
  • glReadPixels(x, y, width, height, format, type, pixels)
  • glScissor(x, y, width, height)
  • glViewport(x, y, width, height)

This says a lot about OpenGL-ES, especially the fact that glDrawPixels has been removed. This means the only way to copy pixels into an OpenGL-ES context is to apply a texture with the pixel data to a rectangle. However, OpenGL-ES forbids GL_QUADS, so you have to use GL_TRIANGLE_FAN to accomplish the same result. glReadPixels, glScissor, and glViewport can be related in that they all accept a rectangle as an argument.

Although OpenGL-ES allows one to do everything that can be done in OpenGL 2.0, there is more of a suggestion to use more general interfaces, like shaders and buffer objects, since all of the fixed functionality has been removed. This means that it is possible to reimplement all of OpenGL in OpenGL-ES. However, since ES is still rather new, there have not been any such implementations of fixed functionality in terms of shaders or the like. There are some tutorials that show how to duplicate such simple functionality as colors in terms of shaders, but a complete reimplementation is still nowhere to be found.

Monday, June 8, 2009

Semantic MathML

I don't know what they were thinking, but there is a much better way to encode MathML in RDF. One can be tempted to assign an RDF property to every element in MathML, but that wouldn't be the OpenMath way. Since MathML3 is getting more and more dependent on OpenMath, it seems appropriate to encode as much as possible using this combined system. MathML3 is split up into several sections: Presentation, Pragmatic Content, and Strict Content. The last one requires only 10 XML Elements to be understood by MathML3 processors, namely: m:apply, m:bind, m:bvar, m:csymbol, m:ci, m:cn, m:cs, m:share, m:semantics, m:cerror, and m:cbytes. This provides for a great economy of thought, and a chance to easily define a total mapping from MathML to RDF. MathML3 already defines a mapping from MathML2 to Strict Content MathML3, so this is the only set of Elements we need to consider. These are the prefixes we will use:

@prefix ari: <> .
@prefix fns: <> .
@prefix sts: <> .
@prefix sm: <> .
@prefix m: <> .

These are the rdfs:Class's we will define:

  • sm:Content (all MathML Content)
  • sm:Number (for <cn/>, subclass of sts:NumericalValue)
  • sm:String (for <cs/>, subclass of xs:string)
and these are the rdf:Property's we will define:
  • sm:apply :: Property * sm:Content
  • sm:applyTo :: Property * (List sm:Content)
  • sm:bind :: Property * (List sm:Content)
  • sm:bindOp :: Property * sm:Content
  • sm:bindIn :: Property * sm:Content
  • sm:error :: Property sm:Error sm:Content
  • sm:errorWas :: Property sm:Error (List sm:Content)
Strict Content MathML3 can be translated with the following algorithm:
  • <m:cn> NUM </m:cn>
  • "NUM"^^sm:Number
  • <m:cs> TEXT </m:cs>
  • " TEXT "^^sm:String
  • <m:ci> Name </m:ci>
  • Use blank node identifier (like _:Name)
  • <m:csymbol> Symbol </m:csymbol>
  • Use URIs ( for <m:csymbol cd="arith1">plus</m:csymbol>, or the value of the definitionURL for MathML2)
  • <m:share/>
  • Use URIs
  • <m:cbytes> DATA </m:cbytes>
  • " DATA "^^xs:base64Binary
  • <m:cerror> Symbol Content* </m:cerror>
  • [] rdf:type sm:Error ;
    sm:error Symbol ;
    sm:errorWas LIST(Content) .
  • <m:apply> Symbol Content* </m:apply>
  • [] sm:apply Symbol ;
    sm:applyTo LIST(Content) .
  • <m:bind> Symbol Vars* Content* </m:bind>
  • [] sm:bindOp Symbol ;
    sm:bind LIST(Vars) ;
    sm:bindIn LIST(Content) .

This allows all of Strict Content MathML to be encoded in a set of RDF triples. In order to have the full semantics of MathML and OpenMath there would have to be an OM-interpretation, OM-entailment, and so on, just as there is with every other application of RDF. Although I have not worked out the details of this, an OM-interpretation of an RDF graph that contains these properties would have to treat sts:mapsTo special, and maybe map it to an appropriate rdfs:Class. As an example of how this might be used, this is how the Haskell code (\x -> x + 2) would be translated into RDF using the properties listed above as follows:

_:f sm:bindOp fns:lambda ;
sm:bind LIST(_:x) ;
sm:bindIn LIST(
[ sm:apply ari:plus ;
sm:applyTo LIST(_:x "2"^^sm:Number) ]).

Now that RDF has lambdas, the possibilities are endless!

Sunday, June 7, 2009

Subtly Different Linked Lists

If you don't know what a linked list is, then you probably shouldn't be reading this. However, the idea is very simple: a linked list is a list constructed from smaller lists of length two. So a list of length 3 would be constructed as (A, B, C) = (A, (B, (C, Nothing))), where Nothing would indicate that we have reached the end of the list. Most programming languages have some kind of linked list datatype. C++ has the list<T> type in STL, Lisp has the 'list type, Haskell has the [T] type, and RDF has the rdf:List type. We will not consider sequences here, so C types will be left for a future article.

Without any type restrictions, such a pair need not be required to make a list. For example, we could make the structure ((A, B), C), but we could not interpret it as a list. This is exactly how the Common Lisp cl:cons constructor works. The Common Lisp HyperSpec calls anything constructed with cl:cons a list. The special case where the second element of cl:cons is either another cl:cons or a cl:nil is called a proper list. This restriction makes a subtype which can always be interpreted as a list. This subtype corresponds to the lists found in scripting languages such as Perl, Python, and Ruby. RDF lists can also be described as proper lists, since an RDFS-interpretation requires that the range of rdf:rest is rdf:List, so any attempt to make an improper list with rdf:rest will result in an inconsistent RDF graph.

With the restriction that the second part of a pair is a list, we obtain so-called heterogeneous lists, because the members of the list (encoded as the first part of each pair) can be of any type. If we also enforce the restriction that each member of the list is of the same type, then we obtain what is called homogeneous lists for obvious reasons. This subtype is what is found in more strict languages, such as list<T> in C++ and [T] in Haskell. This is an overview of the different kinds of lists we have talked about:

  • Improper list (a, (b, c))
  • Proper list (a, (b, (c, ())))
    • Heterogeneous list [1, "message"]
    • Homogeneous list [1, 2, 3]

While we have talked about lists before, restricting RDF's heterogeneous lists to obtain homogeneous lists. However, in this article we are going to consider generalizing RDF's proper lists to obtain improper lists as well. In order to do this, we will make a distinction between cl:Cons the Class and cl:cons the constructor. First we need rdf:List rdf:subClassOf cl:Cons so that they can work together, and then cl:Cons will represent both improper lists and proper lists, and rdf:List will represent proper lists only. To represent an improper list, would would have to be an instance of cl:Cons but not rdf:List. For a heterogeneous list, one would have to be missing the ex:listType property, and for a homogeneous list, one would require the presence of the ex:listType property. This covers all the different list types discussed above.

Saturday, June 6, 2009

HTML Script Datatypes

While wandering through the W3C specification for rdf:text, I realized a similar notation could be used for script objects, but there were too many pieces missing from the standards to connect everything together. So I will try to connect these ideas as best I can. HTML 4.01 defines multiple datatypes, some of which are redefined by CSS, such as Color and Length. The one that cought my attention was Script, which could be used to represent scripts written in different languages.

UNIX has long since had this datatype built in to almost every Shell interpreter. The so-called Hash-Bang system allows you to have programs written in any language that do not need to be compiled, but are passed to the appropriate program for interpretation. While RDF has two types that are very similar, it doesn't have a type for scripts or functions. Using a mixture of JavaScript and HTML datatypes, we can express a function definition in RDF as follows:

 @prefix hdt: <> .
@prefix js: <urn:ecmascript:> .

_:f rdf:type js:Function .
_:f js:Call """
function () {
this.done = true;
} @application/ecmascript"""^^hdt:Script .

Here you can see the @ notation is used to separate the script data from the media type, just as it is in the rdf:text datatype. This would allow a mixture of data (RDF graphs) and code (JS scripts), which are the beginnings of a full-fledged programming language.

Wednesday, June 3, 2009

XML Infoset Models

The XML Information Set (Infoset) defines a number of classes that can be used to model XML documents, and to some extent, this is exactly the model used in other W3C specifications. However, some specifications use less or more than this set of classes, and it is insightful to compare them in order to find common subsets, and exhaustive supersets. In the comparison below "Info" means XML Infoset and "Path" means the XPath/XQuery Data Model. Also, the abbreviations (Y = yes/required, N = no/unspecified, O = optional) are used.

Class Name XMLDOMEXIInfoPath
CharacterData YYYYN
Comment YYOYY
DocumentFragment NYYNN
DocumentType YOOYN
Entity YOOYN
EntityReference YOOYN
Notation YONYN
ProcessingInstruction YOOYY

Technically, XML Infoset does not include a CharacterData class, but includes a Character class that can be made into a list, which would be isomorphic to the CharacterData class. DOM only requires the optional classes if hasFeature("XML", "1.0") is implemented, so for all XML DOM implementations, these are not optional. Also, EXI requires the Namespace class, even though preserving the namespace prefix strings is optional. XPath has the smallest model, which only supports 7 of the above classes.

It is also interesting to note that Comments, Namespaces and ProcessingInstructions are not forbidden by any of the standards considered above. Also, as you can see, the only classes required by all W3C models are: Attributes, Elements, Documents, Namespaces and Text. Why all the bloat?