What A Stray Mind Coughed Up

On 'int128_t'

2012-01-14T14:14:00.000-08:00

Every programming language has built-in integer types, both signed (representing mathematical integers) and unsigned (representing mathematical nonnegative integers). C compilers usually give these types fancy names like 'unsigned long long', and have a nasty habit of changing the sizes (and meanings) of these types on different platforms. The C type 'short' is usually 16 bits, 'int' either 16 or 32 bits, and 'long' either 32 or 64 bits, depending on platform. This eventually led to the 'stdint.h' header in C99, which provides exact-size types which can be used accross platforms. These are named 'int32_t', 'int64_t', 'uint32_t', 'uint64_t', and so on.

With stuff getting bigger, it's natural to ask the question: "Why 64?" and the answer is generally because the highest integer type most hardware can deal with is 64 bits. Can we go higher? Of course! but how? In this article, I will show you how to define 'int128_t' and 'uint128_t' in C without any compiler hacks. They can be used as parameter types and return types from functions, and they don't require any special memory management or allocation, because they're not pointer types.

First, you might say we could just make an array type:

 typedef int32_t int128_as_int32x4_t[4];
 typedef int64_t int128_as_int64x2_t[2];

but which one to we pick? What we really need is a union of each of these, so we can decide later which array type to use. However, neither arrays nor unions can be used as return values from functions, only struct's can be used as return values. So in order to have a type that can be used as a return value we need to make a struct of a union of array types, as follows:

typedef struct int128_s {
    union int128_u {
        int8_t  as_int8[16];
        int16_t as_int16[8];
        int32_t as_int32[4];
        int64_t as_int64[2];
    } value;
} int128_t;

and wrap this type in a typedef. But how do we use these new integers? First of all we need some way of constructing 'int128_t's, and in the spirit of 'stdint.h' we can make a 'INT128_C()' macro which expands to a constructed object of type 'int128_t'. We'll need a few functions for this:

int128_t int128_from_int(int from);
int128_t int128_from_str(char *from);
int int_from_int128(int128_t from);
int str_from_int128(char *to, int to_size, int128_t from);

and we can use the second one to define the macro as:

#define INT128_C(x) int128_from_str(#x)

because '(#x)' indicates to the preprocessor to turn x into a string before compile-time, which is then passed to int128_from_str which then returns an object of type 'int128_t'. For compilers that do not support compile-time constant expressions involving function calls, we can also define simpler macros as follows:

#ifdef BIG_ENDIAN
#define INT128_C64(a,b)\
    (int128_t){.value = {.as_int64 = {a, b}}}
#define INT128_C32(a,b,c,d)\
    (int128_t){.value = {.as_int32 = {a, b, c, d}}}
#else
#define INT128_C64(a,b)\
    (int128_t){.value = {.as_int64 = {b, a}}}
#define INT128_C32(a,b,c,d)\
    (int128_t){.value = {.as_int32 = {d, c, b, a}}}
#endif

Note that because we use designators (value and as_int##) this part requires a C99 compiler

Conclusion

In order to use this integer type, we also need dozens of other functions, such as add, mul, sub, div, mod, and, or, xor, lsh, rsh, pow, etc., just to match the functionality usually associated with C integer types, and from there the possibilities are endless. A future article could revisit these functions. For now, though, I just wanted to bring focus to this integer type, especially considering how many common-place datatypes fit into an 'int128_t' such as UUID's and IPv6 addresses. We may need this sooner than we think.

Tetrational-point

2011-01-28T14:38:00.000-08:00

As you might have guessed, most of my posts are a synthesis of two or more ideas. This time, they are IEEE-754 floating point formats and composite arithmetic formats. To provide some overview, IEEE-754 has been the official standard for representing numbers in computers for over 25 years, and is widely deployed in practically every computer architecture. Composite arithmetic on the other hand is a new approach which uses a combination of integer, rational, scientific, and tetrational representation in unison to achieve greater accuracy, precision, and dynamic range.

References for composite arithmetic include: "Beyond Floating Point" (by C.W.Clenshaw and F.W.J.Olver) which focuses on extending floating point with tetration alone, "Composite Arithmetic, a Proposal for a New Standard" and "Composite Arithmetic, A Storage Form" (both by W. Neville Holmes) which both focus on combining all four approaches, "Design of a Composite Arithmetic Unit for Rational Numbers" (by Tomasz Pinkiewicz, W. Neville Holmes, and Tariq Jamil) which focuses on the implementation of these in hardware, "Design of a 32-bit Arithmetic Unit based on Composite Arithmetic and its Implementation on a Field Programmable Gate Array." (by Tomasz Hubert Pinkiewicz) which focuses on the same, and "Lecture notes on: Computer Arithmetic: Principles, Architectures, and VLSI Design" (by Reto Zimmermann) which seems to be an overview of the subject targeted at students.

The most recent edition of IEEE-754 introduced a 16-bit floating point format, called 'binary16' for short. Since this is the smallest standard floating point format, we will use it as an example of how IEEE-754 represents numbers. To begin we will see how it represents 1.5:

	s	exponent					significand
bin	0	0	1	1	1	1	1	0	0	0	0	0	0	0	0	0
hex	3				E				0				0
value	= 1.5

and this is how the standard binary16 format represents infinity:

	s	exponent					significand
bin	0	1	1	1	1	1	0	0	0	0	0	0	0	0	0	0
hex	7				C				0				0
value	= Infinity

As you can see, binary16 uses a 5-bit exponent and a 10-bit significand. One important class of representations which do not represent numbers is known collectively as Not-A-Number (NaN) representations. These are when the exponent is all 1's, regardless of the sign. Infinity is a particular example of this, since the exponent is all 1's and the significand is all 0's. If the significand is nonzero, then the remaining representations fall into two categories: signaling NaNs (sNaN) and quiet NaNs (qNaN). A signaling NaN is traditionally represented with a 0 in the MSB of the significand, and some other bit nonzero. A quiet NaN is traditionally represented with a 1 in the MSB of the significand, with anything in the other bits. Since sNaNs can cause errors and trap handlers to invoke, it is a bad idea to use them to represent numbers, since many architectures will automatically convert sNaNs to qNaNs. So, we will leave sNaNs alone, and replace qNaNs with a tetrational number representation format.

This tetrational format will use the two MSBs to represent quietness (q) and height (h) respectively. The tetrand will become the exponent at the top of the exponential tower. So a height of 0 will indicate a value of 2^2^2^2^2^(0.tetrand), and a height of 1 will indicate a value of 2^2^2^2^2^2^(0.tetrand). In general, the value associated with the tetrational format is:

(-1)^sexp₂^h+5(0.tetrand) -- HTML

{(-1)}^{s} \exp_{2}^{h + 5} (0.tetrand)

-- MathML

We will start at 65536, which is just greater than the largest value represented by binary16 (65504). Extending this to larger formats (like binary32) should probably start here as well, because the next height is too much larger than the largest number represented by binary32. Starting from 65536, we can represent it as follows:

binary16:	s	exponent					significand
tetra16:	s	exponent					q	h	tetrand
bin	0	1	1	1	1	1	1	0	0	0	0	0	0	0	0	0
hex	7				E				0				0
value	≈ 65536

We get this value because 2^2^2^2^2^(0.0) = 2^2^2^2^1 = 2^2^2^2 = 2^2^4 = 2^16 = 65536. The next greater representation is

binary16:	s	exponent					significand
tetra16:	s	exponent					q	h	tetrand
bin	0	1	1	1	1	1	1	0	0	0	0	0	0	0	0	1
hex	7				E				0				1
value	≈ 71036

and perhaps another interesting representation is that of googolplex:

binary16:	s	exponent					significand
tetra16:	s	exponent					q	h	tetrand
bin	0	1	1	1	1	1	1	1	1	0	1	1	0	0	1	0
hex	7				F				B				2
value	≈ googolplex = 10^(10^100)

Note that we only used a single bit for the height of the exponential tower, but we could have used more. I think that 2 bits should be used for height in binary32, and 3 bits should be used for height in binary64 and binary128. All floating point formats would encode the height and tetrand in the extra bits of a qNaN so as to avoid conflicts with hardware arithmetic.

Here is an overview of the extensions to the binary16 format:

#x0000 = +0
#x0001 = 5.960464477539063e-8
       ... (standard binary16 floating-point) ...
#x7BFF = 65504.
#x7C00 = +Infinity
#x7C01 = +sNaN
       ... (standard binary16 signaling NaN) ...
#x7DFF = +sNaN
#x7E00 = 65536 = 2^2^2^2^2^(0)
#x7E01 = 71036.
       ... (new tetrational-point) ...
#x7E?? = 2^2^2^2^2^(0.??_16)
       ...
#x7EFE = 8.9423389054e+15721
#x7EFF = 6.2622606021e+17594
#x7F00 = 2^65536 = 2^2^2^2^2^2^(0) = 2^2^2^2^2
#x7F01 = 6.8504792165e+21383
       ... (new tetrational-point) ...
#x7F?? = 2^2^2^2^2^2^(0.??_16)
       ...
#x7FFE = 10^(2.69191e+15721) which is < 2^(2^65536)
#x7FFF = +qNaN (unique)
#x8000 = -0
#x8001 = -5.960464477539063e-8
       ... (standard binary16 floating-point) ...
#xFBFF = -65504.
#xFC00 = -Infinity
#xFC01 = -sNaN
       ... (standard binary16 signaling NaN) ...
#xFDFF = -sNaN
#xFE00 = -65536
#xFE01 = -71036.
       ... (new tetrational-point) ...
#xFE?? = -2^2^2^2^2^(0.??_16)
       ...
#xFEFE = -8.9423389054e+15721
#xFEFF = -6.2622606021e+17594
#xFF00 = -2^65536
#xFF01 = -6.8504792165e+21383
       ... (new tetrational-point) ...
#xFF?? = -2^2^2^2^2^2^(0.??_16)
       ...
#xFFFE = -10^(2.69191e+15721) which is > -2^(2^65536)
#xFFFF = -qNaN (unique)

In conclusion, we have shown exactly how to increase the dynamic range (quite dramatically) of standard IEEE-754 floating point formats by using a tetrational representation encoded in the unused bits of quiet NaNs. This provides a backwards-compatible hardware-accelerated tetrational floating point format which will encode approximate overflows as precisely as possible. So instead of overflows, you get a number! This makes it possible to be more informative when it comes to mathematical functions such as exp, log, or 1/x. With a bigger dynamic range, many of the outputs of these functions will no longer be indeterminate, but instead, finite.

GoLang Proposals

2011-01-03T17:59:00.000-08:00

Go is a very new programming language, barely a year old. Since its initial release, it has become an instant success, almost overnight. Google designed Go primarily for high-level systems programming. Since then, Google has replaced a few of its internal servers with custom Go servers. I believe this success is driven by the simplicity of Go, and its special features which focus on concurrency.

Compared to C, it has many more features so I consider its features a strict superset of C's features. Compared to C++ however, Go is very different, possibly described by a classic Venn-diagram in which Go's features and C++'s features intersect, but both have features the other doesn't. For example, method overloading can be accomplished in both languages, but in different ways.One feature that C++ has enjoyed is that of templates, which do not exist in Go. This requires that algorithms that can work on multiple datatypes be written out each time, which negatively affects readability and maintainability. While adding full-fledged C++ templates to Go is certainly possible, I believe we need to look at other languages for guidance.

Java started out as a simple language. Java's success is due in part to this simplicity, however, language designers at Sun (now Oracle) decided very late in the process (2004, a full 9 years after its introduction in 1995) to add generics to the language. In addition, they chose to use C++ syntax, which has conflicts with the shift operator (>>). In my opinion, avoiding the introduction of generics has divided the community, effected incompatibilities, and complicated the standard library with multiple versions of the same function.

Depending on your definition of generics, they may have different kinds of parameters. The most intellectually challenging are Agda generics, which imply that generics are just functions which return types, and any function may take types as a parameter. C++ templates are similar to this kind of generics, but make a distinction between usual functions and functions returning types. Since this is a minority when it comes to generics implementations, we will not consider this kind of generics in the remainder of this article.

The most prevalent form of generics are found in Java and Haskell, which only allow types as parameters. From this point of view, the only generic type found in Go today is the map type, so it will be the primary example used.

Proposal #1: Add first-class types

This is doomed for failure, because it requires Agda-like (or C++/RTTI) semantics, but it is worth discussing. It is the proposal which requires the least syntactic changes, even if it might be the most intellectually demanding on semantics and runtime. If Go did have first-class types, then we could define the Map type as follows:

func Map(KeyT .(type), T .(type)) .(type) {
  type mapT []struct{
    hash int
    key KeyT
    value T
  }
  return mapT
}

Using this proposal, we can simulate map[KeyT]T with Map(KeyT, T). As you can see, type parameters are indicated with the ".(type)" token as is found in Go type-switch statements. One advantage of this system would be that it could be used to define Array(n, T) and Matrix(m, n, T) which would be impossible to define using more restrictive generics. Other functions that could defined using this proposal are new and make, which take a type as their first parameter. Here is a summary of the related changes to the Go specification:

Result        |= ".(type)"
ParameterDecl |= TypeName ".(type)"
Expression    |= TypeName

In addition to these syntactic changes, a few paragraphs of rules and discussion maybe required.

Proposal #2: Add `'generic'` (or `'_Generic'`) keyword

This is the crux of this blog article. Since first-class types require that types and objects be intermixed, it requires that every parameter be suffixed with .(type), but with the generic keyword, we can enforce that every parameter be a type parameter (Java/Haskell-style generics). This makes declarations much easier to read, and has provides a much more structured style.

generic Map[KeyT]T []struct{
    hash int
    key KeyT
    value T
}

Using this proposal, we can simulate map[KeyT]T with Map[KeyT]T. As you can see, this is very close to the standard built-in map type, with the obvious case difference. Here is an overview of the associated changes to the Go specification:

TypeLit       |= GenericType
TopLevelDecl  |= GenericDecl
GenericType    = "generic"            GSignature Type
GenericDecl    = "generic" identifier GSignature Type
GSignature     = GParameters identifier
GParameters    = "[" [ GParameterList [ "," ] ] "]"
GParameterList = GParameterDecl { "," GParameterDecl }
GParameterDecl = identifier

Having considered adding generic syntax to LiteralType, I don't think it would work well with literal syntax or semantics. What would such a literal mean? Would it simply be syntactic sugar for the base-type of the generic type with all the free variables filled in? If all that would be gained is syntax sugar, then I don't see the value of adding it to literal syntax.

This generics model also allows more than one parameter inside the brackets, but it also requires at least one parameter after the brackets, which is also very similar to how generic types work in Haskell, since the prevalence of monads has made the last parameter more important than the others. This generics model is also much closer to Go's existing map type, the only problem now is that the first letter is uppercase "M" whereas the built-in map type has a lowercase "m". This leads us to our next section, which discusses another proposal.

Proposal #3: Add `'attrib'` (or `'_Attrib'`) keyword

This proposal combines two issues into a single solution. The first issue is nonessential attributes (such as alignment, packing, etc.) for which GCC uses the __attribute__((id)) syntax. The second issue is the public/private convention in Go which may be an issue in the future if it is used to implement existing APIs such as POSIX, which require lowercase external symbols. The solution I propose to both of these issues are a new syntax: _Attrib(id), which allows simple annotation of declarations in such a way as to override normal Go semantics. Consider two such attributes: public and private, which would allow us to define the built-in map type as follows:

generic attrib(public) map[KeyT]T []struct{
    hash int
    key KeyT
    value T
}

Using this proposal, there would be no difference between this defined type and the built-in map type. This would allow very small Go compilers which need only handle arrays and slices, and leave the map type, and possibly other built-in functions such as cap and len to a library implementation.

The syntax was designed to force the attrib specifier immediately before the identifier, to make it clear which identifier it is referring to. The changes to the MethodDecl production are questionable, and require more consideration and discussion. I have also considered moving AttribSpec to before the keywords which would simplify the grammar significantly. This is the summary of all the required extensions to the Go specification.

ConstSpec    |= AttribSpec IdentifierList 
                [ [ Type ] "=" ExpressionList ]
TypeSpec     |= AttribSpec identifier Type
VarSpec      |= AttribSpec IdentifierList 
                ( Type [ "=" ExpressionList ] 
                | "=" ExpressionList )
MethodDecl   |= "func" Receiver AttribSpec 
                MethodName Signature [ Body ]
FunctionDecl |= "func" AttribSpec identifier 
                Signature [ Body ]
GenericDecl  |= "generic" AttribSpec identifier 
                GSignature Type
AttribSpec    = "attrib" "(" identifier 
                [ "(" ExpressionList ")" ] ")"

Proposal #4: Add `'pragma'` (or `'_Pragma'`) keyword

Another method used for nonessential attributes are top-level pragmas. Using pragmas, you can specify information to be used on a per-file or per-package basis. This could be a useful and simple extension to the language that could bring existing GCC syntax to Go compilers. Here is an example of using pragmas in a Go source file:

pragma("GCC poison strdup")
pragma("DSGO prefix pthread_")

Other possibilities for pragmas are to use Go with OpenMP, even though it might sound funny at first, because most of the features of OpenMP are already in Go! However, we should never underestimate what people will do with compilers, given the chance. Here is a summary of the associated extensions to the Go specification:

TopLevelDecl |= PragmaDecl
PragmaDecl    = "pragma" "(" string_lit ")"

Conclusion

We have reviewed four possible extensions to the Go programming language, which may not seem in the spirit of Go right now, but over time may become necessary. If Go is to be used for serious projects, developers may come to expect these features, rather than hope for them. As we have learned from Java, if we wait for too long to introduce new features to Go, it may polarize the community, which would be an undesirable outcome for everyone.

Fuzzy Scrollbars

2009-08-16T06:56:00.000-07:00

After several weeks away from this blog, I would like to start up again with the exciting field of fuzzy logic. Most introductions to fuzzy logic talk about how everything is different, and overview the three major types: Gödel, product, and Lukasiewicz, but I'm going to take a different approach. I'm going to stick with product fuzzy logic for the remainder of this post.

Product Fuzzy Logic

It is important to discuss domains when regarding operations, and fuzzy logic is somewhat consistent in its use of the domain [0, 1], which includes 0, 1 and all the real numbers in between. Let's call this the Clamp datatype. There are obvious mappings to and from Clamp and Bool: 0 maps to False, 1 maps to True, and the in betweens can be handled on a case-by-case basis (possibly to throw and error or something).

The operations on the Clamp datatype would be both arithmetic and logic operations, which would include addition, subtraction, multiplication, division, conjunction (and), and disjuction (or). How would these be defined in product fuzzy logic? According to the product T-norm (the fancy name for how "and" is defined), the logic operations would be defined as

not(x) = 1 - x
and(x, y) = xy
or(x, y) = x + y - xy
implies(x, y) = 1 - x(1 - y)

One interesting thing about product fuzzy logic is that there are multiple ways of defining equiv, depending on what properties you are looking for. One possibility is that equiv(x, y) = and(implies(x, y), implies(y, x)), which would mean that it would have to be defined as equiv(x, y) = (1 - x - y + 3xy - yx² - xy² + x²y²). This is quite a mess, and the same effect (in terms of mapping to Bool) can be accomplished by the definition equiv(x, y) = (1 - x - y + 2xy).

Other considerations for operations on the Clamp datatype are that when performing arithmetic operations, the output of the normal operation must be minimized or maximized to fall within the range [0, 1]. This may have the unfortunate side effect of many run-time errors, or unexpected mathematical outputs. If all conversions to and from the Clamp datatype are excplicit, then this is not a problem.

Scrollbars

Just as the String is the basis for the text field widget, the Clamp datatype can be thought of as the basis for the scrollbar widget. Scrollbars are usually tied to a viewport, which can contain an image, a document, or a webpage. Usually the viewport has all the information that the scrollbar needs to do its job. It has height and width information of the entire image, and the height and width information of the part that is showing. Using this information, the only additional information that needs to be stored in the scrollbar is the percentage of how far down on the scrollbar you are, which is equivalent to what the Clamp datatype provides.

Colors

Why is it that such a fundamental datatype like Clamp is not found in more programming languages? Usually it is defined as equivalent to Float or Double, and intended to be used with values between 0.0 and 1.0, but no strict validation or bounds checking are done to ensure that this is so. One example where this kind of usage is found is in OpenGL, which we will talk about next.In OpenGL, one of the datatypes that is pervasive throughout the API is the GLclamp datatype. This is also a value between 0 and 1, and also where I got the name from. With this datatype, OpenGL defines some texture and image datatypes as structure with members of this type, for example a color in OpenGL is a structure with 3 GLclamps.

With so many applications, the Clamp datatype is a prime example of a design goal that I've been trying to find a name for. When abstractions are too low-level, then you may have few abstractions (like bit and byte), but using these abstractions is a nightmare (just look at assembly code). When abstractions are too high-level, then you may be able to use them easily (like drag-and-drop database form designers), but the number of abstractions makes a steep learning curve, and a high pressure on the discovery of abstractions other people have made (for example: some game libraries have 3 types of fog, and dozens of types of meshes, depending on whether you want to add skeletons or water ripples, etc.). The design goal I'm trying to acheive is a balance of these two extremes that balances low-level abstraction and high-level abstraction in such a way that there are few abstractions, and using them is easy. I think Clamp datatype meets both of these requirements.

From fuzzy logic to colors to scollbars, Clamp seems to form the basis of an unrecognized basis for computation that may be useful in the future.

Embedded OpenGL

2009-06-15T14:13:00.000-07:00

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.

Semantic MathML

2009-06-08T18:23:00.001-07:00

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: <http://www.openmath.org/cd/arith1#> .
@prefix fns: <http://www.openmath.org/cd/fns1#> .
@prefix sts: <http://www.openmath.org/cd/sts#> .
@prefix sm: <http://example.com/SemanticMath/> .
@prefix m: <http://www.w3.org/1998/Math/MathML> .

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 (http://www.openmath.org/cd/arith1#plus 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!

Subtly Different Linked Lists

2009-06-07T13:48:00.000-07:00

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.

HTML Script Datatypes

2009-06-06T18:01:00.000-07:00

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: <http://www.w3.org/TR/html4/types.html> .
 @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.

XML Infoset Models

2009-06-03T11:45:00.000-07:00

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	XML	DOM	EXI	Info	Path
Attribute	Y	Y	Y	Y	Y
CDATASection	Y	Y	N	N	N
CharacterData	Y	Y	Y	Y	N
Comment	Y	Y	O	Y	Y
Document	Y	Y	Y	Y	Y
DocumentFragment	N	Y	Y	N	N
DocumentType	Y	O	O	Y	N
Element	Y	Y	Y	Y	Y
Entity	Y	O	O	Y	N
EntityReference	Y	O	O	Y	N
Namespace	Y	O	O	Y	Y
Notation	Y	O	N	Y	N
ProcessingInstruction	Y	O	O	Y	Y
Text	Y	Y	Y	Y	Y

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?

Set Exponentiation

2009-05-30T22:50:00.000-07:00

Exponentiation is the operation of multiplying the same element by itself a given number of times. Defined by the relation y^x = y⋅y^{x − 1}, it can be evaluated by multiplication until y¹ is encountered, which is just y. It can then be extended to rational numbers by solving an equation, then to the real numbers by the limit of a sequence, then to complex numbers by Euler's formula. Complex exponentiation is one of the most pervasive operations in all of mathematics. It can express all trigonometric functions such as sin, cos, tan, sec, csc, cot, and so on. It can express powers, polynomials, power series, Fourier series (with the help of addition), and much more. Simply put, it's everywhere.

Exponentiation can even be extended to matrices with the help of the equation Y^X = exp(log(Y)X) for square matrices, where exp and log are defined in terms of the usual power series. Exponentiation can also be extended to sets by noticing that the cardinalities of the domain |X| and codomain |Y| of a function, give |Y|^|X| = |Y^X| when exponentiated. This is the idea behind the notation of a power set (denoted 2^X), which can be thought of as the set of all functions from X to a boolean (which represents whether or not it is contained). This is illustrated by the following maps in JSON syntax:

{"a": 0, "b": 0, "c": 0}
{"a": 0, "b": 0, "c": 1}
{"a": 0, "b": 1, "c": 0}
{"a": 0, "b": 1, "c": 1}
{"a": 1, "b": 0, "c": 0}
{"a": 1, "b": 0, "c": 1}
{"a": 1, "b": 1, "c": 0}
{"a": 1, "b": 1, "c": 1}

Clearly, the number of such functions is 8, the cardinality of the domain is 3, and the cardinality of the codomain is 2, and we all know 2³ is 8. Following this to its logical conclusion, we arrive at a justification for currying. Currying is the concept that a function of two variables that returns a value is the isomorphic to a function of one variable that returns a function of one variable that returns a value. In set-theory notation this would be Z^X×Y = (Z^Y)^X, and in Haskell notation this would be X -> Y -> Z. So just as complex exponentiation is everywhere in Mathematics, so too is set exponentiation everywhere in most computer programming languages, whether or not they recognize the concept of currying. With this in mind, if the theory of algebraic datatypes includes type exponentiation, then pretty much all functions are accounted for. This is the approach that the Z notation specification language, because it defines functions as equivalent to their relations. In other words f(x) = y iff (x, y) is a member of f. To illustrate how set exponentiation characterizes many concepts in programming languages, here is a list of common structures:

2^X - Predicates - functions that return a boolean.
X² - If/Then/Else - functions from booleans to a value.
Xⁿ - Switch/Case - functions from an enumeration to a value.
Y^X - Unary Functions - functions from any value to any value.
X^X - Unary Operations - functions from a value to a value.
X^X² - Binary Operations - functions from two values.
X^Xⁿ - n-ary Operations - functions from many values.
2^X² - Binary Relations - also called multi-functions.
2^Xⁿ - n-ary Relations - also called multi-functions.

This is quite a vast array of functions, which cover most basic structured programming concepts like if/then/else and switch/case. But there is one more: X^{X^X}. What does this stand for? Well, conceptually, it takes a Unary Operation over X, and gives a value from X. This is exactly what happens when you evaluate a function at a value, which means the "evaluate at 0" function is in X^{X^X}. What's more, is that this is the beginnings of a set-theoretic Tetration (my other website), which I could talk about for hours, but I will save it for another time.

Nonstandard Namespaces

2009-05-30T11:20:00.000-07:00

XML namespaces are inherently vendor-neutral, and as such, anyone can define one, even me. So in order to help standardize XML dialects that do not define a namespace, I have put together a list of document types that really should have a namespace, but have not taken the time to define one.

r6rs (Scheme R6RS): http://www.r6rs.org/final/html/r6rs/r6rs.html
r5rs (Scheme R5RS): http://www.schemers.org/Documents/Standards/R5RS/
cl (Common Lisp): http://www.lispworks.com/documentation/HyperSpec/
cs (CS, CEL): http://www.crystalspace3d.org/2000/cs_world
x3d (X3D, VRML): http://www.web3d.org/specifications/x3d-namespace
pl (Apple PList): http://www.apple.com/DTDs/PropertyList-1.0.dtd

There really isn't much to say about these. Some of them are based on resources which describe the XML dialects, whereas others (like x3d-namespace) are a version-neutral namespace (while some X3D implementors have used x3d-3.0.xsd or x3d-3.2.xsd, for which files actually exist). If anyone thinks some of these are poor choices, then let me know, and I'll change it.

Webizing Common Lisp

2009-05-30T10:36:00.000-07:00

Lisp is a very old language, but it is by no means old in the derogatory sense. Being the oldest language (except Fortran) has given it time to mature and grow into a language capable of amazing things. It has been said many places that Lisp and XML are similar in that they are both data (and if you include XAML and XSLT, code too). I would argue, though, that Common Lisp has vastly more features. However, to make a true comparison, we have to webize Lisp. At the very least, this requires a URI for every symbol. We can start by giving a namespace to all symbols in the COMMON-LISP package.

http://www.lispworks.com/documentation/HyperSpec/

For convinience, we will use the cl prefix for this namespace. We can now start relating Web standards and Lisp, or even writing ontologies using Lisp functions.

Lets compare lists, which are a fundamental part of Lisp. In Lisp, a cons (x . y) would correspond to the RDF graph given by [ a rdf:List ; rdf:first _:x ; rdf:rest _:y ] and cl:nil would correspond to rdf:nil. We can do this with almost all Lisp syntax, except perhaps for the syntax based on the hash (#) symbol. For example, #c(3 4) would correspond to the MathML <cn type="complex-cartesian">3<sep/>4</cn>, so the mapping can get complicated.

Considering such a mapping between Lisp and XML has many advantages. One thing they both have in common is the idea of homogenous data, however, when viewed as two separate syntaxes, they are incompatible, because XML would be a string in Lisp, and Lisp would be a string in XML, losing all structure. When considering such a mapping, it may seem equally advantageous to express XML in Lisp, and conversely, Lisp in XML. If only it were a bijection...

The Web Metamodel

2009-05-22T18:06:00.000-07:00

The Object Management Group (OMG) likes to consider classes in a 4-level model, in which there is data, metadata (models), metametadata (metamodels), etc. This is way too confusing, so it is fortunate that W3C's standard only take up roughly 3-levels (much like Lisp). The Resource Description Framework (RDF) defines 3 metaclasses that do not fit nicely into OMG's architecture, so they span several modeling levels. This can be seen in the image below, where containment indicates a rdf:subClassOf relationship, and the arrows indicate a rdf:type relationship.

Although there was no indication in the standards that owl:Class is an instance of rdfs:Class, it is a logical consequence, because owl:Class is a subclass of rdfs:Class, and rdfs:Class is an instance of itself. However, the same could be said of rdfs:Datatype, for which there is an explicit mention that rdfs:Datatype is both a subclass and an instance of rdfs:Class. There was also an issue about this, which decided the reason for owl:Class was to be distinct from rdfs:Datatype, not because of some cyclic dependancy stuff. So to keep the model simple, and to minimize cycles, we can ignore the fact that rdfs:Datatype is an instance of rdfs:Class, because this is implied by the fact that rdfs:Class is an instance of itself.

To overview some of the triples in this model, the standards say

rdfs:Class rdf:type rdfs:Class .
owl:Class rdf:subClassOf rdfs:Class .
rdfs:Datatype rdf:subClassOf rdfs:Class .
rdfs:Class rdf:subClassOf rdfs:Resource .
rdfs:Resource rdf:type rdfs:Class .

Notably, we have ignored the rdf:Property class, which is part of the model level, not the metamodel level. So the image above is an accurate depiction of the Web metamodel, which consists of only four metaclasses: rdfs:Resource, rdfs:Datatype, rdfs:Class, and owl:Class. Aside from owl:DataRange, this is a fairly complete picture of the Web metamodel. For beginners, the distinctions between these five metaclasses are essential before more indepth discussions take place. If one has any confusion about these distinctions, then nothing else about OWL will make any sense.

Semantic Binary Data

2009-05-18T22:10:00.000-07:00

There seems to be quite a few quite a few things missing from XML Schema, RDF and OWL, for example, a single unified type for binary octet-streams. The distinction between the two types used for binary octet-streams has caused more than a few issues during the implementation of these technologies. One indication is that OWL 2.0 is much more complex than the OWL 1.0, and another indication is a note in OWL 2 which talks about the consequences of the distinction between xs:base64Binary and xs:hexBinary. Both of these types are defined to have identical value spaces, but different lexical spaces. Their mutual value space is defined as all finite-length sequences of octets (numbers between 0 and 255).

If the Web metasystem is to understand anything, it must be able to understand octet-streams, since everything else is described in terms of these. Text can be viewed as an octet-stream. Pictures, movies, and music files can all be described as octet-streams, so unless XML, RDF and OWL allow clear expression of the concept of binary data, the application of these technologies will always be limited to vauge and abstract knowledge. There are many ways that a unified binary type could be brought to the XML world. One would be to make a owl:unionOf type that combined the two. Or another option would be to define an rdf:List type, and restrict the types of the members of the list to octets. Since the first option is trivial, and does not provide much structural knowledge about octet-streams, we will not consider it. The second approach does add structural knowledge, and so would be more appropriate for allowing the Web to understand more about octet-streams.

Neither RDF nor OWL allow restricting lists to be of a certain type, so in order to make a class of lists of octets, we must first have the ability to make lists of a type. To this end, we define a new rdf:Property called ex:listType. How would this property be used? To understand this, we must first understand how RDF handles higher-order types. For example, Properties in RDF can be thought of as higher-order types with two parameters. Using a Haskell-like syntax, this would mean (x :: Property a b) would correspond to the triples

_:x rdf:type rdf:Property .
_:x rdfs:domain _:a .
_:x rdfs:range _:b .

which means the appropriate way to encode list types in RDF, such as (x :: List a), would be with the triples

_:x rdf:type rdf:List .
_:x ex:listType _:a .

With this new construct, a unified ex:binary type could easily be defined as (List xs:unsignedByte). Or in simpler terms, the triple (_:x rdf:type ex:binary) would be equivalent to the triples

_:x rdf:type rdf:List .
_:x ex:listType xs:unsignedByte .

This would allow OWL ontologies about file formats, stream protocols, multimedia files, and much more. Using these two higher-order types as examples, it seems all higher-order types can be patterned after these two. Also, since it is abstract enough to represent these higher-order types, it seems that Web technologies are on the right track. RDF and OWL seem to be the most abstract way of expressing modeling ideas, even more abstract than systems like CORBA, IDL and UML. The fact that they allow expressing higher-order types such as those found in Haskell is promising. Perhaps the goal of model compilation (the OMG kind), is much closer than we think. However, the bloat of UML does more to complicate model translation than to simplify it.

Perhaps the simplicity of RDF is all we need.

Water Shortages

2009-05-11T19:41:00.000-07:00

We have water everywhere. Water flows off mountains, collects in lakes, and comprises 70% of the Earth's surface. It is hard to imagine our world without water. So when the idea of it running out is mentioned, it seems so funny that we pay little attention. If we listen, then we find the signs of its disappearance are also everywhere.

Places all across the globe are experiencing short-term water shortages (For example, Putrajaya, Malaysia; Hechi, Guangxi, China; San Diego, California, US; Roane County, West Virginia, US; Montgomery County, Maryland, US; Durham, North Carolina, US). Nations such as Australia and Spain are already noticing significant long-term water shortages, who say

The battles of yesterday were fought over land, they warn. Those of the present center on oil. But those of the future -- a future made hotter and drier by climate change in much of the world -- seem likely to focus on water, they say.

Two great examples of works that discuss a future without water are this Spanish poem (also in English and video), and the legacy of John Titor. While John Titor has made several predictions that turned out to be false (for example, he said Y2K would be devastating), he also predicted that water would become more scarce. This seems to be exactly what we are starting to see in many cities today.

Although a total water shortage is still a very far away, water contamination may be a problem sooner. It is already starting to kill off many spicies to the brink of extinction (for example Fish and Frogs). Modern apathy may compel one to dismiss these, since they're just frogs, but ask yourself: What can we learn from frogs? Frogs (and most amphibians) are both land and water-based creatures, so they represent the future health of both fish and mammals. Since humans are mammals, that means we're next! If that wasn't enough, you might also be interested to know that the science of cryogenics (freezing people and bringing them back to life) rests on the study of tree frogs. Any selfish ego-centric person would love to get frozen when they're 80, and wake up in a hundred years when there's a cure waiting just for them. So regardless of your disposition, selfish or selfless, clean water is important.

We find that there is a growing awareness that water will not be as plentiful as it is now. Lessons given by John Titor and Tree Frogs both indicate we should reevaluate our water situation soon. Avoiding to do so would mean its scarcity would surpass that of both land and oil. Just as oil has been called Black Gold it may be inevitable that in our near future, all power struggles will be for Liquid Gold.

The Web Metasystem

2009-05-09T15:36:00.000-07:00

A recent TEDtalk given by Kevin Kelly came to my attention recently, which has a lot to do with the Web. In it, he gives a very interesting view of the Web, making the analogy that the number of transistors supporting it is about the same number of neurons in the human brain. Kevin Kelly says:

There is only One machine.
The web is its OS.
All screens look into the One.
No bits will live outside the web.
To share is to gain.
Let the One read it.
The One is us.

The most interesting part is when he talks about the complexity of the Web over time. If transistors are akin to neurons, then that means in 10 years the Web will be 2 brains, and in 20 years, the Web will be 4 brains, and so on. The human brain contains about 100 billion neurons, which are much more complex than a transistor in nature. I think that it would take on the order of 10 transistors to approximate a single neuron, making his estimates inaccurate.

In the long run, such an analogy could be viewed in the context of metasystem transition theory, in which evolution is not continuous as it is in Darwinian evolution, but happens in discrete steps marked by a metasystem transition. In this model, regardless of how many transistors there are in the Web at any one point in time, the evolutionary step in which the Web becomes a brain is when a control system emerges. Since the Web was designed by us, and continues to be re-structured by us. There is an obvious answer to what the control system behind the Web is. Everyone. The Web is us.

Haskell - Encodings

2009-05-01T14:45:00.000-07:00

The ASCII character set has withstood the test of time. However, as the use of computers and the internet becomes global, it is only natural that people speak in their native language. To this end, the Unicode character set was developed to meet this need. Since Unicode uses much more than 255 code points to represent these characters, there are many ways of mapping the much larger space of 4-bytes into a sequence of one or more bytes. The two most popular schemes for doing this are UTFs (UTF-8 and UTF-16), and Guóbiāo (GB2312 and GB18030). In particular, UTF-8 is a very organized and methodical scheme, which makes it well suited for purposes other than text encoding.

XML has become terrifyingly popular in acedemic and commercial circles, and while the overhead that it incurs is usually negligible, there are some who want to use an XML model while keeping a small memory footprint. For this, the W3C has designed a binary XML format called EXI for the transmission of XML documents in binary form. Parts of this standard are not very nice (which is out of the scope of this post), whereas some parts are quite ingenious, like the integer and date-time formats.

Here are some examples of EXI (efficient XML interchange) unsigned integers. EXI is little-endian, so the As are the low bits and the Cs are the high bits.

0b0AAAAAAA (EXI encoding for 1-byte)
0b1AAAAAAA,0b0BBBBBBB (EXI encoding for 2-bytes)
0b1AAAAAAA,0b1BBBBBBB,0b0CCCCCCC (3-bytes)

Here are some examples of UTF (Unicode transformation format) characters. UTF-8 is big-endian, so the Cs are the low bits and the As are the high bits.

0b0AAAAAAA (UTF-8 encoding for 1-byte)
0b110AAAAA,0b10BBBBBB (UTF-8 encoding for 2-bytes)
0b1110AAAA,0b10BBBBBB,0b10CCCCCC (3-bytes)

In the C programming language, all structs can be thought of as parsers. In the Haskell programming language, one can write parsers quite easily with the help of a library called Parsec, which stands for parser combinators. Suppose we have a Bit datatype with the constructors On and Off, and suppose we have definitions for the following functions in Haskell:

bit :: Bit -> Parser Bit
bitstring :: [Bit] -> Parser [Bit]
manyBits :: Int -> Parser [Bit]
oneBit :: Parser Bit

These parsers would allow writing versions of EXI and UTF-8 parsers without any knowledge of characters. An EXI parser can be described as follows

exi :: Parser [Bit]
exi = do
  firstBit <- oneBit
  restBits <- manyBits 7
  case firstBit of
    Off -> return restBits
    On -> do 
      highBits <- exi
      return (highBits ++ restBits)

and a UTF-8 parser can be described as

utf8continue = do
  bitstring [On, Off]
  manyBits 6

utf8 :: Parser [Bit]
utf8 =  do bit Off
           manyBits 7

    <|> do bitstring [On, On, Off]
           highBits <- manyBits 5
           restBits <- utf8continue 
           return (highBits ++ restBits)

    <|> do bitstring [On, On, On, Off]
           highBits <- manyBits 4
           rests <- sequence (replicate 2 utf8continue)
           return (highBits ++ (concat rests))

    <|> do bitstring [On, On, On, On, Off]
           highBits <- manyBits 3
           rests <- sequence (replicate 3 utf8continue)
           return (highBits ++ (concat rests))

As you can see, EXI has a much more elegant implementation in Haskell. Although Parsec was designed to be used on characters and strings, similar techniques can be used for byte-parsers and bit-parsers as shown above. Since C structs can be viewed as byte-parsers, it should be possible to build Parsec style parsers for some common C structs and common file formats like JPEG or MPEG. Bringing this to its logical conclusion, most file formats could be described as some kind of bit-parser or byte-parser, so if such parsers were written in Haskell, what would they look like?

XML - Entity References

2009-04-28T16:21:00.000-07:00

When we go about writing a web page, often enough, we like using all sorts of characters in our text, like exclamation points (!), ampersands (&), and less than signs (<). Sooner or later, it becomes obvious that we need a way to put a character in our web pages without using the character itself. For example, the less than sign (<) is part of XML markup, so it cannot be used in the text itself, so to remedy this situation the entity reference < is used. This expands to (<) when the page is viewed in a browser, so the desired effect is achieved.

The concept of XML entities was borrowed from SGML, and so their inner workings are very similar. Another borrowing from SGML is the DOCTYPE declaration. While backwards-compatibility was an important objective for XML 1.0, it is a low priority now that XML processors are ubiquitous, and rarely depend on more general SGML processing. In fact, now that XML Schema has replaced almost every aspect of the Document Type Declaration (DTD), it is likely that the use of DTDs will diminish. Since XML Schema provides a richer environment for declaring elements and defining types, it seems painful to have to use DTDs. This naturally leads to the question of whether or not DTDs can be removed from the XML specification.

Suppose DTDs were removed from the XML specification (perhaps for XML 1.5). What else would have to be changed in order to maintain consistency? Surprisingly, only entities. Everything else can be equivalently (or better) declared in XML Schema, which also provides rich types that can increase validity constraints where DTDs would not. However, XML Schema does not provide a way to define entities. So if a new mechanism for entity definition is required, then it could be one of the following options:

Use a simplified DOCTYPE declaration for compatibility.
Create a new processing instruction to include entities.
Let the user agent handle entities however it wants.

Of these options, the new processing instruction would be the most consistent with W3C's other specifications, such as Associating Style Sheets with XML documents. Also, it would be a chance to codify current best practice. XML allows entities to be defined internally (within the document) and externally (in another file). Most documents that use entities either depend on a standard list of entities (like HTML Entities) or directly include a file which has entity definitions. So while a hypothetical processing instruction <?xml-entity copy "©"?> would do the job, it would go against everything. A hypothetical processing instruction <?xml-entities href="htmllat1.ent"?> would be more in line with current usage. Since this would introduce a new language for this external file, there would have to be at least two parts to a specification of this idea:

```
entSubset  ::= (GEDecl | Comment | S)*
```

EntitiesPI ::= '<?xml-entities' S PseudoAtt S? '?>'

where the allowed pseudo-attributes are:

href    CDATA #REQUIRED
charset CDATA #IMPLIED

Another benefit of using a processing instruction instead of some other method is that you do not have to wait until a new XML processor is implemented. In the worst case scenario, you could pass the document through a tool that understands that processing instruction, and the rest can be handled by a normal XML processor. Thus, you can live in a DTD-free world without waiting for XML 1.5 ... you can have it your way, today.

What A Stray Mind Coughed Up

On 'int128_t'

Conclusion

Tetrational-point

GoLang Proposals

Proposal #1: Add first-class types

Proposal #2: Add 'generic' (or '_Generic') keyword

Proposal #3: Add 'attrib' (or '_Attrib') keyword

Proposal #4: Add 'pragma' (or '_Pragma') keyword

Conclusion

Fuzzy Scrollbars

Product Fuzzy Logic

Scrollbars

Colors

Embedded OpenGL

Semantic MathML

Subtly Different Linked Lists

HTML Script Datatypes

XML Infoset Models

Set Exponentiation

Nonstandard Namespaces

Webizing Common Lisp

The Web Metamodel

Semantic Binary Data

Water Shortages

The Web Metasystem

Haskell - Encodings

XML - Entity References

Proposal #2: Add `'generic'` (or `'_Generic'`) keyword

Proposal #3: Add `'attrib'` (or `'_Attrib'`) keyword

Proposal #4: Add `'pragma'` (or `'_Pragma'`) keyword