Byte-swap

Today I want to take a brief look at byte swapping from a different point of view. Many algorithms take mathematical concepts and turn them into a step-by-step process, but what if we turn it around, and mathematize a process that originates from computer science?

The idea of mathematizing computer programs is generally done within the context of the design of high-reliability systems and formal methods, which provide a way to prove that a program is correct. Perhaps if we took the time to ensure the correctness of the programs we write, then there wouldn't be so many bugs!

Gödel and powerbooleans

What is a boolean?

A boolean is either true or false.

What is a powerboolean?

A powerboolean is a subset of the booleans (B):

• True = {true}
• Both = {true, false}
• False = {false}
• Null = {}

This set is equivalent to 2^B (the powerset of the booleans), hence the name. The powerboolean operations are simply defined as the image of the normal boolean operations over B. The truth tables are as follows:

AND	T	B	F	N
T	T	B	F	N
B	B	B	F	N
F	F	F	F	N
N	N	N	N	N

OR	T	B	F	N
T	T	T	T	N
B	T	B	B	N
F	T	B	F	N
N	N	N	N	N

NOT
T	F
B	B
F	T
N	N

These truth tables should not be confused with Belnap logic (which is another 4-valued logic) because there are different definitions for (N AND B), (B AND N), (N OR B), (B OR N). Also, In Belnap logic, B and N can be swapped, and the same rules apply, so they are not unique. In the powerbooleans, B and N cannot be swapped in a similar way, because if you do swap them, the truth tables would have to change. So the powerbooleans have unique values, they aren't just repetitions of some third truth value found in most 3-value logics. The 4-values of the powerbooleans are truely unique.

Who is Gödel?

Gödel is best known for his incompleteness theorems, but he is also known for the fuzzy logic named after him: "Gödel–Dummett" logic (also known as superintuitionistic, intermediate, or minimum t-norm logic). I've talked about product fuzzy logic before, but this time I'd like to talk about Gödel fuzzy logic. The operations are as follows:

• (x AND y) = min(x, y)
• (x OR y) = max(x, y)
• NOT(x) = 1 - x

These operations are defined over a continuous interval from 0 to 1, so I can't really give truth tables for these, but to cut to the chase, they would look very similar to the tables above.

What do they have to do with each other?

If we let NOT(x) = (if x < 0, then x, else 1 - x), extend the interval of Gödel fuzzy logic below zero (which forces OR to be redefined in terms of our new NOT), and assign the following fuzzy values to each powerboolean:

• True = 1
• Both = 1/2
• False = 0
• Null = -1/2

then Gödel fuzzy logic and powerboolean operations are the same.

A survey of 'divmod'

Rounding happens, and it happens far more than most people are aware of. As your web browser tries divide a web page (say, 917 pixels across) into 4 equal parts it uses rounding to find how many pixels each column is. Most of the time it is of little importance which direction numbers are rounded, but in some applications, it can be very noticeable. The solution to this problem is a simple calculation involving divmod:

  divmod(917, 4) = (229, 1)

which means a web page which is 917 pixels across can be divided into 4 columns, each of which is at least 229 pixels across, with 1 pixel left over. This concludes our example.

If the numbers being divided are real numbers or integers then there are many, many ways to round the division. If the numbers being divided are positive or unsigned integers, then there are fewer rounding modes (because rtn=rtz and rtp=rta) but there are still many ways. Despite how these modes may seem equivalent for mathematically positive numbers, they are different for fixed machine-size integers. For example, rtn is the same computationally on int32_t and uint32_t, as is rtp, but rtz and rta produce a different computational algorithms on signed and unsigned types. Regardless of the rounding mode chosen, the divmod axiom states:

  divmod(dividend, divisor) = (quotient, remainder)

implies

  dividend = divisor*quotient + remainder

or put in other words, quotient is approximately (dividend/divisor), but which way it is rounded is up to the rounding mode. This is true for every variant in this article except for divmod_euc, which we will discuss later.

This brings us to our analysis of the most common variants, which are usually called truncated division (also called quo-rem), and floored division (also called div-mod). The systems surveyed are: C (POSIX), OpenCL (a variant of C), libMPFR (the R stands for rounding), and Scheme (R5RS, R6RS, and a R7RS draft),

divmod_rtz(a,b)
  • "round towards zero"
  • 'rtz' suffix (OpenCL)
  • x86:idiv (CPU instruction)
  • c99:% (C operator)
  • c:mod[fl]? (POSIX)
  • c:trunc[fl]? (POSIX)
  • c:FE_TOWARDZERO (POSIX)
  • c:MPFR_RNDZ (libMPFR)
  • rnrs:truncate (Scheme)
  • r5rs:quotient (Scheme)
  • r5rs:remainder (Scheme)
  • r7rs:truncate/ (Scheme)
  • "rem() has same sign as dividend"

divmod_rtn(a,b) 
  • "round towards negative infinity"
  • 'rtn' suffix (OpenCL)
  • c:floor[fl]? (POSIX)
  • c:FE_DOWNWARD (POSIX)
  • c:MPFR_RNDD (libMPFR)
  • rnrs:floor (Scheme)
  • r5rs:modulo (Scheme)
  • r7rs:floor/ (Scheme)
  • "mod() has same sign as divisor"

The problem with these two variants being so common is that it is easy to misuse them. It is quite common to use (A % B) as an index of an array of B elements, without checking if A is positive first. This introduces a buffer overflow error when the program tries to get the -4th element of the array, because that memory address may not be allocated yet, and even worse, if it is allocated then it's probably the wrong data! The core issue with both rtz and rtn rounding modes is that they may give negative remainders. However, there is less possibility of errors with mod_rtn when B is positive, because mod_rtn gives a positive remainder in that case. C99 was the first version of C that actually specified that "%" was mod_rtz, but before the 1999 version, that operator could also be mod_rtn, in which case the operator would be safe. Since C99 standardized on mod_rtz, however, now we know that "%" is unsafe, and therefore, we should always test if A is positive first. Another option would be to use mod_euc, which is discussed later in this article.

The next variant doesn't have a name, but it is a division involving the ceiling() function. Maybe someday we'll have a name for it.

divmod_rtp(a,b) 
  • "round towards positive infinity"
  • 'rtp' suffix (OpenCL)
  • c:ceil[fl]? (POSIX)
  • c:FE_UPWARD (POSIX)
  • c:MPFR_RNDU (libMPFR)
  • rnrs:ceiling (Scheme)
  • r7rs:ceiling/ (Scheme)

I couldn't find any implementations of functions for the next two variants, but there is a rounding mode constant in MPFR. Anyways, here they are:

divmod_rta(a,b)
  • "round away form zero"
  • c:MPFR_RNDA (libMPFR)

divmod_rnz(a,b)
  • "round to nearest, ties towards zero"
  • (no examples)

There are also some rounding modes used in POSIX (also known as the Single UNIX Specification (the two standards have been synchronized since 2001), what most C programs use) that appear to depend on the environment for which rounding mode to use. The first is completely dependent on the current rounding mode, and the second is basically rn_ (round to nearest), except that ties are rounded according to the current rounding mode. The third seems uncommon in that C is the only language that uses it.

divmod_rtd(a,b)
  • "round ... default behavior"
  • c:nearbyint[fl]? (POSIX)

divmod_rnd(a,b)
  • "round to nearest, ties ... default behavior"
  • c:l?l?rint[fl]? (POSIX)

divmod_rna(a,b)
  • "round to nearest, ties away from zero"
  • c:l?l?round[fl]? (POSIX)

The next variants are vary rare, because they cannot be found in C:

divmod_rnn(a,b)
  • "round to nearest, ties towards negative infinity"
  • "Round half down" (Wikipedia)
  • r6rs:div0, r6rs:mod0 (Scheme)

divmod_rnp(a,b)
  • "round to nearest, ties towards positive infinity"
  • "Round half up" (Wikipedia)
  • elementary school rounding (in the U.S.)

The next variant, known as rte (round ties to even), is probably the fairest variant, in that it has no bias. Most of the variants above have a bias towards positive numbers or negative numbers, or a bias towards zero. The following variant is probably most well-known as being specified by the IEEE-754 floating-point standard. Its claim to fame is that it is unbiased, and it does not introduce any tendancies towards any particular direction.

divmod_rte(a,b)
  • "round to nearest, ties to even"
  • "Round half to even" (Wikipedia)
  • 'rte' suffix (OpenCL)
  • c:remquo[fl]? (OpenCL & POSIX)
  • c:remainder[fl]? (OpenCL & POSIX)
  • c:FE_TONEAREST (POSIX)
  • c:MPFR_RNDN (libMPFR)
  • r7rs:round/ (Scheme)

The next variant is by far the most advanced divmod on the planet. It is so advanced that it cannot be described by a rounding mode. All of the variants above can be described as div_?(a,b) = round_?(a/b) where the ? are replaced with a rounding mode, but not the next one. Its definition would be div_euc(a,b) = sign(b)*floor(a/abs(b)), but that doesn't even begin to describe it's awesomeness. The reason why div_euc is so amazing is that mod_euc is always nonnegative. Period.

divmod_euc(a,b)
  • r6rs:div, r6rs:mod (Scheme)
  • r7rs:euclidean/ (Scheme)

I am not the first to notice this. There is a paper titled "The Euclidean definition of the functions div and mod" (from 1992) and R6RS Scheme is also very insistant on this algorithm. In the paper, the author mentions how "definitional engineering" is at fault for the difficulties in using other rounding systems and in particular, fields in computer science such as arithmetic coding, arbitrary precision arithmetic, and programming language foundations all would benefit from (or in my opinion: require) the Euclidean definition, and yet there is no programming language (except for Algol and Scheme) that uses it.

Bibliography

• OpenCL 1.1 Section 6.2.3.2 Rounding Modes.
• C99/POSIX <fenv.h> and <math.h>.
• Revised (5|6|7) Report on Scheme.
• The libmpfr documentation.
• The Euclidean definition of the functions div and mod. Raymond Boute. ACM Transactions on Programming Languages and Systems, Vol 14, No. 2, April 1992, Pages 127-144.

Fuzzy Scrollbars

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.

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: <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!

Set Exponentiation

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^X2 - Binary Operations - functions from two values.
• X^Xn - n-ary Operations - functions from many values.
• 2^X2 - Binary Relations - also called multi-functions.
• 2^Xn - 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^XX. 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^XX. 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.