tag:blogger.com,1999:blog-91618867918062338692024-03-14T03:38:56.406-07:00What A Stray Mind Coughed UpAndrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.comBlogger29125tag:blogger.com,1999:blog-9161886791806233869.post-87538520569427370492019-06-11T16:58:00.000-07:002019-06-11T16:58:12.276-07:00Early Boot is a Lie<em>Everything you know about early boot is a lie.</em> The classic introduction to IBM PC compatible (x86, x64) startup sequence goes as follows. Read-only memory (Boot ROM) loads the Master Boot Record (MBR) from the first Peripheral Component Interconnect (PCI) Device. MBR loads the rest of the Operating System (OS). Everyone should write an MBR bootloader (it's fun!), but there is a glaring constraint that is a hold-over from the old days, which is that you have 512 bytes (about 400 available to use for machine code). Here is an example MBR bootloader that closely resembles the "Standard MBR", traditionally written in assembly, but for clarity we have rewritten it in <b>pesudo-Rust</b>.
<pre>
// Oversimplified Legacy Standard MBR
pub unsafe fn <b>mbr_main</b>() {
const SECTOR: usize = 0x200;
// Pointer to Master Boot Record (MBR)
// This is empty before shadowing, MBR after shadowing.
let mut mbr = <a href="https://doc.rust-lang.org/std/vec/struct.Vec.html#method.from_raw_parts">Vec::from_raw_parts</a>(
0x0600 as *mut u8, SECTOR, SECTOR);
// Pointer to Volume Boot Record (VBR)
// This is the MBR before shadowing, VBR after shadowing.
let mut vbr = <a href="https://doc.rust-lang.org/std/vec/struct.Vec.html#method.from_raw_parts">Vec::from_raw_parts</a>(
0x7c00 as *mut u8, SECTOR, SECTOR);
// Chainload/Underlay/Shadow Master Boot Record (MBR)
// This program started running from 0x7c00, but the
// instruction pointer has moved since then, so we need to
// jump to here + 0x0600 - 0x7c00, represented by asm_shadow!().
<a href="https://doc.rust-lang.org/std/ptr/fn.copy.html">ptr::copy</a>(vbr.as_ptr(), mbr.as_mut_ptr(), SECTOR);
<b>asm_shadow!</b>(mbr.as_ptr() as usize - vbr.as_ptr() as usize);
// Find first bootable partition entry (oversimplified!)
let bootable = <b>MbrTable::from</b>(mbr).partitions[0];
// Chainload/Overlay/Fetch Volume Boot Record (VBR)
<b>csm::ChsReader::from</b>(bootable).<a href="https://doc.rust-lang.org/std/io/trait.Read.html#tymethod.read">read</a>(vbr.as_mut_ptr());
// Tail call the Volume Boot Record (VBR)
let vbr_main = vbr.as_ptr() as *const Fn();
vbr_main();
unreachable!();
}
</pre>
The first thing to realize is that since this is the first 512 bytes on the hard drive, that people have written many versions of this. There are MBR bootloaders found in Windows, macOS, Linux, SYSLINUX, GRUB, CoreBoot, SeaBios, EDK2, and many others. There are far too many versions of this to discuss here, and so I will move on to more interesting things. Let's go in the other direction. What loads the MBR? What jumps to the MBR? Enter the reset vector. The code that goes in the the reset vector is called the Volume Top File (VTF). The reset vector is physical address 0xfffffff0 (-16), which has a jump to physical address 0x00007c00 (31744). Sounds like a dream. Here is some equivalent pseudo-Rust:
<pre>
// Oversimplified Boot Device Selection (BDS)
pub unsafe fn <b>bds_main</b>() {
const SECTOR: usize = 0x200;
// Pointer to Master Boot Record (MBR)
let mbr = Vec::from_raw_parts(
0x7c00 as *mut u8, SECTOR, SECTOR);
// Load first sector from first hard drive
<b>csm::ChsReader::default</b>().read(mbr.as_mut_slice());
// Tail call the Master Boot Record (MBR)
let mbr_main = mbr.as_ptr() as *const Fn();
mbr_main();
unreachable!();
}
</pre>
I put my compiled binary code in the first sector of the hard drive, which gets loaded at 0x7c00, and I never have to worry about anything else. Perhaps if you've heard about the <a href="https://en.wikipedia.org/wiki/Power-on_self-test">Power-On Self-Test (POST)</a>, then you may say to yourself, even if there are processes before the MBR, then I don't have to worry about them because they're in ROM, and therefore read-only.
</p><p><em>That's not true.</em></p><p>
The 16 bytes at the top of memory is where all of UEFI takes place. How is this even possible? UEFI is beyond the scope of this article, but to overview, here is some psuedo-Rust:
<pre>
pub unsafe fn <b>vtf_main</b>() {
// There is only enough room for a jump, so imagine
// that this is what the top of memory jumps to.
// Security (SEC)
sec_main();
// Pre-EFI Initialization (PEI)
pei_main();
// Driver eXecution Environment (DXE)
dxe_main();
// Tail call Boot Device Selection (BDS)
bds_main();
unreachable!();
}
</pre>
If we had the source code to the final stages of the Boot ROM, then it might look something like this pesudo-Rust:
<pre>
pub unsafe fn <b>rom_main</b>() {
const SECTOR: usize = 0x200;
// Pointer to Volume Top File (VTF)
let vtf = Vec::from_raw_parts(
0xfffff000 as *mut u8, 8*SECTOR, 8*SECTOR);
// Copy 8 sectors from SPI flash to memory
<b>rom::SpiReader::default</b>().read(vtf.as_mut_slice());
// Tail call the Volume Top File (VTF)
let vtf_main = 0xfffffff0 as *const Fn();
vtf_main();
unreachable!();
}
</pre>
That seems a bit unfair. The modern UEFI runtime environment gets 8 sectors (about 4 <a href="https://en.wikipedia.org/wiki/Binary_prefix#kibi">KiB</a>), and the legacy MBR environment gets 1 sector (512 bytes? If I were a bootloader, I would ask for a refund. So let us overview the process:
<ul>
<li><samp>rom_main()</samp>, presumably still read-only...</li>
<li><samp>vtf_main()</samp>, writable (HW)</li>
<li><samp>sec_main()</samp>, writable (HW)</li>
<li><samp>pei_main()</samp>, writable (HW, or PEI modules)</li>
<li><samp>dxe_main()</samp>, writable (HW, or DXE modules)</li>
<li><samp>bds_main()</samp>, writable (SW, or NVRAM)</li>
<li><samp>mbr_main()</samp>, writable (SW)</li>
<li><samp>vbr_main()</samp>, writable (SW)</li>
<li><samp>boot_loader()</samp></li>
<li><samp>oper_system()</samp></li>
</ul>
We have certainly skipped a few steps, for example, the Compatibility Support Module (CSM), System Management Mode (SMM), and the Trusted Platform Module (TPM). These three are all critical parts of the startup process, but are too complex to get into detail here. There really is no such thing as "Early Boot" anymore, because what we think of as early, is very <em>late</em> in the process now. Suffice it to say that there is an entire ecosystem of companies and hackers trying to squeeze ever more out of those 16 bytes at the top of memory.Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com0tag:blogger.com,1999:blog-9161886791806233869.post-77764774637952984752015-01-27T17:33:00.000-08:002015-06-15T11:03:11.974-07:00Hardware accelerated SHA-1<p>There are many articles out there describing hardware accelerated AES, which has been out for a few years now, but SHA instructions are not out yet, but should be appearing in ARM and x86 instruction sets sometime this year. So I figure it's time to start talking about them now. The first and formost standard for the SHA-1 algorithm is NIST's current <a href="http://csrc.nist.gov/publications/fips/fips180-4/fips-180-4.pdf">FIPS-180</a> document, specifically section 6.1.2 "SHA-1 Hash Computation" part 3, which says:</p>
<blockquote style="font-style: italic;">T = <span style="font-style: normal;">ROTL</span><sub>5</sub>(a) + f<sub>t</sub>(b, c, d) + e + K<sub>t</sub> + W<sub>t</sub></blockquote>
<p>This formula (which I call the T-formula) is probably the most computationally intensive part of SHA-1, and one of the most surprising things about my research into the ARM NEON and x86 SHA instruction sets is that neither of them implement this formula exactly as is.</p>
<h4>SHA-1 Instructions</h4>
<table border="1" style="font-size: small;">
<thead>
<tr><th>ARM</th><th>x86</th><th>Comment</th></tr>
</thead>
<tbody>
<tr><td><code>sha1h a</code></td><td></td><td>Rotate left 30</td></tr>
<tr><td><code>sha1su0 a, b, c</code></td><td><code>sha1msg1 a, b</code></td><td>Message schedule part 1</td></tr>
<tr><td><code>sha1su1 a, b</code></td><td><code>sha1msg2 a, b</code></td><td>Message schedule part 2</td></tr>
<tr><td><code>sha1c hash, e, msg</code></td><td><code>sha1rnds4 hash, msg, 0</code></td><td>Rounds 0 to 20</td></tr>
<tr><td><code>sha1p hash, e, msg</code></td><td><code>sha1rnds4 hash, msg, 1</code></td><td>Rounds 20 to 40</td></tr>
<tr><td><code>sha1m hash, e, msg</code></td><td><code>sha1rnds4 hash, msg, 2</code></td><td>Rounds 40 to 60</td></tr>
<tr><td><code>sha1p hash, e, msg</code></td><td><code>sha1rnds4 hash, msg, 3</code></td><td>Rounds 60 to 80</td></tr>
<tr><td></td><td><code>sha1nexte hash, msg</code></td><td>Invisible e operand</td></tr>
</tbody>
</table>
<p>As you can see, ARM and x86 are a bit different. From my research, it seems that ARM omits "<i>K<sub>t</sub></i>" from the T-formula, and x86 omits "<i>e</i>" from the T-formula. These implementation choices imply that SHA-1 optimizations on each architecture will use these instructions very differently. x86 has a publication documenting the <a href="https://software.intel.com/en-us/articles/intel-sha-extensions">SHA instruction set</a> extensions, and if there are any conflicts with this article, then the final word is there. X86 omits "<i>e</i>" in the T-formula, so it must be calculated with the <code>sha1nexte</code> instruction. In pseudo-code, a representative sample of 4 SHA-1 rounds on x86 can be computed by:</p>
<blockquote style="font-size: small;">
<code>work18 = sha1msg2(sha1msg1(work14, work15) ^ work16, work17);</code><br/>
<code>hash19 = sha1rnds4(hash18, sha1nexte(hash17, work18), 3);</code>
</blockquote>
<p>ARM on the other hand, has absolutely no documentation about their SHA instruction set, except how to determine if the processor supports it. While this is handy, it does very little to describe the inner workings of each instruction. So the following is just a guess on my part, but given that the inputs to (<code>sha1c</code>, <code>sha1p</code>, and <code>sha1m</code>) are two vectors, there is enough information to compute 4 rounds of SHA-1, just like the x86 <code>sha1rnds4</code> instruction. ARM omits "<i>K<sub>t</sub></i>" in the T-formula, so it must be added to the work vector. In pseudo-code, a representative sample of 4 SHA-1 rounds on ARM can be computed by:</p>
<blockquote style="font-size: small;">
<code>work18 = sha1su1(sha1su0(work14, work15, work16), work17);</code><br/>
<code>hash19 = sha1p(hash18, sha1h(hash17[0]), work18 + SHA1_K3V);</code>
</blockquote>
<p>where <code>SHA1_K3V</code> is a vector of 4 uint32's all of which are <code>SHA1_K3</code>.</p>
<p>For more information see also: <a href="https://github.com/andydude/rust-sha/blob/master/src/sha1.rs">sha1.rs</a></p>Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com2tag:blogger.com,1999:blog-9161886791806233869.post-51571417412810140012014-11-24T06:55:00.000-08:002014-12-16T22:33:21.198-08:00Programming Struggles<p>Software is <a href="http://www.softwareishard.com/blog/">hard</a>. Lots of programmers out there are constantly searching for new solutions to old problems, and sometimes they find something that works well. It seems that many recent languages (e.g. Dart, Scala, Groovy, Vala, Hack, Swift) are simply syntax sugar for existing programming languages. Are we ever going to make any progress? I know this question has been rehashed a million times, but I'm going to ask it again anyway.</p>
<h3>What makes a good programming language?</h3><ol>
<li><b>Algebraic Data Types</b> - includes sum types (open and closed), and product types (open and closed); too many languages miss these.</li>
<li><b>Generics, Parameterized Types</b> - includes arrays, vectors, lists, hash tables, trees, parsers, I/O streams, pointers</li>
<li><b>Reflection, Metaprogramming</b> - includes macros, annotations, doc parsers, syntax highlighting, coverage tools, static analysis tools, serialization, etc.</li>
<li><b>Memory Pool Management</b> - this is different from memory management, but it refers to the ability to manage the pools themselves, such as the ability to switch between Gc (garbage collected) and Rc (reference counted) memory pool models.</li>
</ol>
<p>There are probably countless other conditions that I can't think of right now, but if you can think of them for me and leave your comments below, perhaps I will make this article longer.</p>
<h3>Algebraic Data Types</h3>
<p>What is an <a href="https://en.wikipedia.org/wiki/Algebraic_data_type">algebraic data type</a>? Fundamentally it is a way of combining existing types. For two types, there are two fundamental options for a new type, the new type can store both types (ProductType), or either type (SumType). However, it can get more complicated than that. The way that algebraic data types are implemented in most languages differ by how extensible the resulting types are. I call them <b>open</b> if they can be extended after definition, and <b>closed</b> if they cannot. So to give some examples from existing languages:</p>
<ol>
<li><b>closed product types</b> - usually called structures, classes, records, tuples, etc.</li>
<li><b>closed sum types</b> - usually called enumerations, or tagged unions. Most languages get these wrong because C got them wrong by making them equivalent to integers (which are an example of an open sum type).</li>
<li><b>open product types</b> - usually called arrays, vectors, or lists. These can always store more data by appending. Adding fields in a subclass can also be an example of this kind of construction.</li>
<li><b>open sum types</b> - usually called objects, dynamics, variants, etc. These can always be extended by inheritance or by subclassing this type.</li>
</ol>
<p>There are usually <i>too many</i> ways of performing one of these type definitions. For example Haskell has a Dynamic type, which can be used as a variant type for every type in the language, but it also provides type classes, which also allow open sum type definition.</p>
<p>In Java, and most other OOP programming languages, classes perform most of the above kinds of definitions. Final class fields are an example of closed product type definition. Abstract classes can be used for open sum type definition. Class fields added to a subclass that inherits from a superclass is an example of open product type definition.</p>
<h3>Generics</h3>
<p>Common generic types include Optional (Maybe in Haskell), List, Array, Pointer, GcPointer (Gc in Rust, ^ in C++/CLI), RcPointer (Rc in Rust, shared_ptr in C++), Box (Box in Rust, unique_ptr in C++), HashTable, etc. Some language don't have generics, but end up expressing concepts with special syntax, for example, * for pointers (in C and Go), and [ ] for arrays (in C and Go).</p>
<h3>Reflection</h3>
<p>One prerequisite for reflection is that the language must expose the parser used in the compiler (or interpreter, although I cannot think of any language that still uses an interpreter these days). If it does not expose the same parser the compiler uses, then the language must be <b>easy to parse</b>. Too many languages miss this. If people are going to write tools for your language (and they will), then they might not use a fancy parsing framework to help, they might only look for documentation strings or lines that start with an @ symbol. C/C++ is one of the most difficult languages to parse, and yet it makes up most desktop software in use today.</p>
<h3>Memory Pool Management</h3>
<p>Most languages pick one memory pool model and stick with it. C does not provide any, except for malloc/free, and so reference counting (Rc) emerged as a common solution to this problem. Many scripting languages have opted for garbage collection (Gc) for every single object, which makes it impossible to opt-out. For a general-purpose programming language, it is unacceptable to require that users are forced into one model or another.</p>
<h3>Conclusion</h3>
<p><a href="http://www.rust-lang.org/">Rust</a> has all of these features.</p>
<p><b>Update</b>: Since the time of this writing, <code>#rust</code> has since informed the author that <code>Gc</code> has been removed from the roadmap, and the standard library. <code>Gc</code> was also not implemented as a garbage-collected pointer, it was more of an auto-reference-counted pointer type.</p>
Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com0tag:blogger.com,1999:blog-9161886791806233869.post-36014953213782414442013-06-08T17:51:00.002-07:002013-06-08T17:51:53.856-07:00Rust wc<p>So in my attempt to practice writing POSIX command-line tools in Rust, the next tool I tried to rewrite was <tt>wc</tt> (or word count). This is a simple tool that counts 4 things:</p>
<ul>
<li>lines (separated by U+0D, LINE FEED)</li>
<li>words (separated by any whitespace)</li>
<li>characters (multibyte encoded, probably UTF-8)</li>
<li>bytes</li>
</ul>
<p>In the interest of brevity, I'm going to refer the reader to <a href="https://gist.github.com/andydude/5711998">this link</a> for the source code. One thing I learned is that the current <tt>std::getopts</tt> library doesn't have many features, e.g., it doesn't link short options and long options, so you have to check each separately. While I was writing this, some people in #rust on irc.mozilla.org suggested that I look at <a href="http://docopt.org/"><tt>docopt</tt></a> which has not been ported to Rust yet, still mostly a Python library, but if ported would make a great addition to the language.</p>Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com1tag:blogger.com,1999:blog-9161886791806233869.post-18724455334712768302013-06-01T22:40:00.002-07:002013-06-08T17:52:05.041-07:00Rust echo<p>I recently found the Rust programming language, and I've been having a blast of a time learning it. So far, it seems like a mixture of 50 different languages, most notably C++ and Haskell.</p>
<p>To help myself learn it, I decided a good place to start was with command-line utilities, the most basic of which are defined by POSIX. POSIX echo does not have any parameters, it just prints all of its arguments back to the user. BSD echo takes one parameter '-n' and if it's not given, then it prints a newline after all arguments are printed.</p>
<p>This seemed like a good example to learn a language so this was my <a href="https://gist.github.com/andydude/5682918/3b2840dfd9930c535760066137edb9b8dcad4bbb">first attempt</a>:</p>
<pre>fn main() {
let mut newline = true;
let mut arguments = os::args();
arguments.shift();
if arguments[0] == ~"-n" {
arguments.shift();
newline = false;
}
for arguments.eachi |argi, &argument| {
print(argument);
if argi == arguments.len() - 1 {
if newline {
print("\n");
}
} else {
print(" ");
}
}
}
</pre>
<p>I talked about this on #rust at irc.mozilla.org and <a href="https://gist.github.com/bjz/5682965">bjz</a> and <a href="https://gist.github.com/huonw/5683000">huonw</a> recommended:</p>
<pre>
fn main() {
let args = os::args();
match args.tail() {
[~"-n",..strs] => print(str::connect(strs, " ")),
strs => println(str::connect(strs, " ")),
}
}
</pre>
<p>which had some issues with it, so I refactored it to be <a href="https://gist.github.com/andydude/5682918">more functional</a>:</p>
<pre>fn unwords(args: &[~str]) -> ~str {
return str::connect(args, " ");
}
fn echo(args: &[~str]) {
match args.tail() {
[~"-n", ..strs] => print(unwords(strs)),
strs => println(unwords(strs)),
}
}
fn main() {
echo(os::args());
}
</pre>
<p>which defined a Haskell-like unwords function to help. I am quite pleased with how supportive Rust is to approaching the problem from a procedural paradigm or a functional paradigm. Hooray for multi-paradigm programming!</p>
Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com1tag:blogger.com,1999:blog-9161886791806233869.post-79517751402713436742013-06-01T19:03:00.001-07:002013-06-01T21:05:14.555-07:00Review of previous posts<p>In this post, I'm going to be reviewing my old posts with what I've learned over the past few years. The purpose behind this analysis is to consolidate my ideas into fewer ideas and hopefully come up with some new insights along the way.
</p><p>
<a href="http://straymindcough.blogspot.com/2009/04/xml-entity-references.html">This</a> was my first post about XML entity references. The goal was to restrict the DTD grammar to only entities so facilitate usage in other applications that have no concern about elements and attribute lists. Now I would recommend using only DTD since its usage is widespread. I was considering folding this into a macro system I was planning to write, so that one could replace <tt>&copy;</tt> with <tt>&#169;</tt> just as easily as it could replace <tt>sqrt(4)</tt> with <tt>2</tt>. I've come to the conclusion that this post was premature, and needs to be included in a more detailed discussion about macro systems, and templating systems such as M4, Genshi, Mustache, and many others.
</p><p>
<a href="http://straymindcough.blogspot.com/2009/05/haskell-exi-and-utf-8-encodings.html">This</a> was an example of binary parsing, which is still not possible in many languages, but a topic more suited to C structs. GCC has a large number of attributes and packing parameters that accomplish some of the goals of binary parsing, but I still haven't found a good binary parsing framework to date.
</p><p>
<a href="http://straymindcough.blogspot.com/2011/01/golang-proposals.html">This</a> was a bunch of things trying to make <a href="http://straymindcough.blogspot.com/2012/04/golang-highlights.html">Go</a> something that it wasn't. I have since found the Rust programming language, which has all the features I was looking for in this post and more. So, now I would recommend using Rust.
</p>
<p>
<a href="http://straymindcough.blogspot.com/2009/06/embedded-opengl.html">These</a>
<a href="http://straymindcough.blogspot.com/2009/05/webizing-common-lisp.html">posts</a>
<a href="http://straymindcough.blogspot.com/2009/05/set-exponentiation.html">were</a>
<a href="http://straymindcough.blogspot.com/2012/03/godel-and-powerbooleans.html">just</a>
<a href="http://straymindcough.blogspot.com/2012/05/byte-swap.html">crazy</a>
<a href="http://straymindcough.blogspot.com/2011/01/tetrational-point.html">comments</a>.
</p>
<h3>The following posts were all about RDF:</h3>
<p>
<a href="http://straymindcough.blogspot.com/2009/06/subtly-different-linked-lists.html">This</a> was a comment primarily intended to allow for arbitrary Common Lisp lists to be represented in RDF.
</p><p>
<a href="http://straymindcough.blogspot.com/2009/08/fuzzy-scrollbars.html">This</a> was a comment as well, and I still haven't found a datatype URI for this, perhaps something for a future article.
</p><p>
<a href="http://straymindcough.blogspot.com/2012/01/on-int128t.html">This</a> is interesting because there isn't an XSD datatype associated with large finite-size integers, although you could define it as xsd:integer, then restrict the domain until it matches int128_t. I have since defined a URI for this on my <a href="http://drosoft.org/cd/typename128">other website</a>.
</p><p>
<a href="http://straymindcough.blogspot.com/2012/02/survey-of-divmod.html">This</a> was fun. I have since written about these algorithms on my <a href="http://drosoft.org/cdgroup/rounding">other website</a>.
</p><p>
<a href="http://straymindcough.blogspot.com/2012/07/on-binary-search.html">This</a> is a type of post I'd like to write more of. You know, explaining the pros and cons of certain implementation techniques and why one is better or worse than the other.
</p><p>
<a href="http://straymindcough.blogspot.com/2009/06/xml-infoset-models.html">This</a> was attempting to illustrate the inconsistencies that I found between different XML standards.
</p>
<p>
<a href="http://straymindcough.blogspot.com/2009/05/models-web-metasystem.html">This</a> and <a href="http://straymindcough.blogspot.com/2009/05/web-metamodel.html">this</a> were comments about The Web. I would like to add that I've started to use unqualified identifiers to refer to RDF and OWL core concepts in my private notes:
</p>
<ul>
<li>Type = rdfs:Class</li>
<ul>
<li>ObjectType = owl:Class</li>
<li>DataType = rdfs:Datatype</li>
</ul>
<li>Property = rdf:Property</li>
<ul>
<li>ObjectProperty = owl:ObjectProperty</li>
<li>DataProperty = owl:DataProperty</li>
</ul>
</ul>
<h3>The following posts were unintentionally about Data URIs:</h3>
<p><a href="http://straymindcough.blogspot.com/2009/06/html-script-datatypes.html">This</a> was attempting to solve a problem that Data URIs already solve. Now I recommend using Data URIs instead.
</p><p>
<a href="http://straymindcough.blogspot.com/2009/05/nonstandard-namespaces.html">This</a> was a good comment, but I don't recommend these namespaces anymore. Now I recommend using Data URIs instead, for example:</p>
<blockquote><tt><data:text/x-scheme;version=R5RS,vector-length></tt></blockquote>
<p>
<a href="http://straymindcough.blogspot.com/2009/05/semantic-binary-data.html">This</a> mentions a problem regarding <tt>xsd:hexBinary</tt> and <tt>xsd:base64Binary</tt>, which can be solved in several ways:
<ol>
<li><a href="http://www.candlescript.org/doc/candle-data-model-reference.htm">Candle</a> assigned the type identifier "<tt>binary</tt>" to the combined value space.
</li><li> The MediaType "<tt>application/octet-stream</tt>" is naturally isomorphic to the <tt>binary</tt> datatype.
</li><li> The Data URI <tt><data:application/octet-stream,DATA></tt> may be used to represent data of type <tt>binary</tt>.
</li><li> The URI
<blockquote><tt><http://www.iana.org/assignments/media-types/application/octet-stream></tt></blockquote>
may also be used to represent the <tt>binary</tt> datatype itself.
</li>
</ol>
</p>Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com0tag:blogger.com,1999:blog-9161886791806233869.post-85937529627874613922012-07-29T16:36:00.000-07:002012-07-29T16:36:29.219-07:00On binary search<p> There are many articles about the pedagogical benefits of writing a binary search algorithm. Instead of just implementing binary search, I wanted to take it one step furtuer. Is is possible to write a standards compliant, formally correct, and beautiful implementation of bsearch() in C? </p>
<pre><span style="color: #666">// This type simplifies the
// argument list of bsearch.</span>
typedef int (*compare_f)(
const void *x,
const void *y);</pre>
<pre>void *
<b style="color: #FFF">bsearch</b>(
const void *<b style="color: #9FF">key</b>,
const void *<b style="color: #FF9">base</b>,
size_t <b style="color: #FDB">nel</b>,
size_t <b style="color: #FBD">width</b>,
compare_f compar)
{
size_t k;
size_t lo = 0;
size_t hi = <b style="color: #FDB">nel</b> - 1;
const void *<b style="color: #BBF">mid</b>;
while (lo <= hi) {
<span style="color: #666">// If we used (lo + hi)/2, then it
// would overflow for large integers.
// The following formula prevents that.</span>
k = lo + (hi - lo)/2;
<b style="color: #BBF">mid</b> = <b style="color: #FF9">base</b> + k*<b style="color: #FBD">width</b>;
<span style="color: #666">// If we used compar(mid, key), then it
// would violate POSIX, which specifies
// that key must be the first argument.</span>
int cmp = compar(<b style="color: #9FF">key</b>, <b style="color: #BBF">mid</b>);
if (cmp < 0) hi = k - 1;
if (cmp > 0) lo = k + 1;
if (cmp == 0)
return (void *)<b style="color: #BBF">mid</b>;
}
return NULL;
}</pre>
<p> Note that not every argument and variable have been colorized, just the ones that usually give people the hardest time when reasoning about this function. The average <tt>(k)</tt> can be reduced to <tt>(lo + hi)/2</tt> if the array you are handling is less than 2<sup>63</sup> elements long, but since it isn't technically correct, I didn't write it that way. </p>Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com0tag:blogger.com,1999:blog-9161886791806233869.post-77262447082828559382012-05-12T01:02:00.000-07:002012-05-12T01:03:33.337-07:00Byte-swapToday I want to take a brief look at <a href="http://en.wikipedia.org/wiki/Endianness#Endianness_in_files_and_byte_swap">byte swapping</a> 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?
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgWdaFXQTH3TApbvBQI3W_Ybfwmi9nJzcMCwMHjNh-MpX7DOVNefdmgfYJ3PVGhk5mKfDMujnFC2GUaBcJARUr36sa8lVMseeBDmeDzidbjx3hFuFoAGyudQ4MirKh4twyLJKAh4uGcCzw/s1600/bswap32.png" imageanchor="1" style="margin-left:1em; margin-right:1em"><img border="0" height="54" width="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgWdaFXQTH3TApbvBQI3W_Ybfwmi9nJzcMCwMHjNh-MpX7DOVNefdmgfYJ3PVGhk5mKfDMujnFC2GUaBcJARUr36sa8lVMseeBDmeDzidbjx3hFuFoAGyudQ4MirKh4twyLJKAh4uGcCzw/s320/bswap32.png" /></a></div>
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!Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com0tag:blogger.com,1999:blog-9161886791806233869.post-42398722891473455482012-04-30T20:50:00.001-07:002012-04-30T20:58:29.350-07:00GoLang Highlights<p> I have been using Go quite frequently lately, and I would like to talk about the experience. There are several introductions to Go floating around, and reactions to its different conventions and ways of doing things than some people are used to. First, I would like to make it clear, though, that I have only used the <tt>gc</tt> compiler, as it was impossible to install <tt>gccgo</tt> on Mac OS X at the time of this writing. </p><p> <b>What makes Go similar to X?</b> <ul><li>garbage collection</li><li>interface embedding</li><li>struct embedding</li></ul> <b>What makes Go better than X?</b> <ul><li>type syntax (backwards = fowards)</li><li>typed channels (no serialization)</li><li>implicit interfaces</li><li>segmented stacks</li></ul></p><h4>Similarities</h4><p> Every scripting language has some form of garbage collection, so Go is not unique in that respect. Interface embedding is when you used a named interface type instead of a method when defining an interface type. It is similar to Haskell's => when constraining a type class. Struct embedding is when you use a named struct type instead of a field declaration when defining a struct type. This is very similar to inheritance in OOP languages, and it also gives the method sets of those child structs to the parent struct. Both of these are called embedding because they are syntactically similar, you just list the typename. However, they mean different things, and it's important to remember this. </p><h4>Type Syntax</h4><p> One of the distinguishing features of Go is its beautiful type syntax. Many programmers have noticed that writing types in C can be a headache, because when you read the type aloud, you have to read backward, or sometimes you have to skip around, back and forth in order to read the type properly. In Go there is no such problem, because the types are written <b>exactly</b> how you would say them in English. While this may be an issue in other languages, most speakers of languages of languages with SVO (Subject-Verb-Object) structure would be happy to see this change. It makes programming in Go a pleasure, and contributed greatly to my own productivity in my Go projects. </p><h4>Typed Channels</h4><p> Another Go feature is channels. Go channels are different from most other forms of I/O found in other languages because they are not based on bytes or characters, but data. Typed data. Which means instead of being required to serialize and deserialize your data when communicating between threads, or parts of a larger design, you can send them over a channel as is, knowing that you can use the data immediately instead of validating it first. Serialization is also a big issue with large software projects, since they may be written in many languages, which requires serialization in order to get data from one component to another. Go also has a serialization format, called <b>gob</b>, which can be considered a codec for most major types in the language. So you don't have to serialize, but if you want to, then it's available. </p><h4>Implicit Interfaces</h4><p> Another distinguishing feature of Go is implicit interfaces. Most languages with interfaces require explicit statements of implementation, such as Java and Haskell (for type classes). Go has no such requirement (and no such syntax). An interfaces is a collection of methods. A named type has an associated set of methods attached to it, called its <b>method set</b>. A named type implements an interface iff the methods it requires are a subset of the named type's method set. That's it! It's that simple. And because you don't have to make it explicit, it allows you to focus on more important things. </p><h4>Segmented Stacks</h4><p> The first and foremost under-appreciated and under-documented feature found only in Go is that of <b>segmented stacks</b>. Segmented stacks is what Go developers call the combination of implementation choices that led to the Go calling convention. It is an intersection of many features, such as: dynamic stack allocation, runtime checks, variable arguments, and deferred functions. Simply put, there is so much that happens between 'return' the statement, and 'RET' the instruction. First, the Go runtime has to check to see if there are any deferred functions to run, then it has to see if it allocated any stack space for the current function, and if it did and it isn't required anymore, then it frees the stack. Similarly, when a function is called, one of the first things that happens is the Go runtime checks to see if more stack space is required. What this means is that - in Go - there are no stack overflows! </p><p> Since segmented stacks are such an interesting feature, I suspect that I will revisit them in the future with a more in-depth discussion than I can ever hope to achieve in one paragraph. </p>Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com0tag:blogger.com,1999:blog-9161886791806233869.post-83877072940885221152012-03-02T23:49:00.009-08:002012-03-06T08:09:38.393-08:00Gödel and powerbooleans<h4>What is a <a href="http://en.wikipedia.org/wiki/Boolean_algebra">boolean</a>?</h4><p>A <b>boolean</b> is either <i>true</i> or <i>false</i>.</p><h4>What is a <a href="http://en.wikipedia.org/wiki/Many-valued_logic">powerboolean</a>?</h4><p>A <b>powerboolean</b> is a subset of the booleans (<b>B</b>):</p><ul><li><b>True</b> = {<i>true</i>}</li><li><b>Both</b> = {<i>true</i>, <i>false</i>}</li><li><b>False</b> = {<i>false</i>}</li><li><b>Null</b> = {}</li></ul><p>This set is equivalent to 2<sup><b>B</b></sup> (the powerset of the booleans), hence the name. The powerboolean operations are simply defined as the image of the normal boolean operations over <b>B</b>. The truth tables are as follows:</p><table class="center" border="1"><thead><tr><td>AND</td><th>T</th><th>B</th><th>F</th><th>N</th></tr></thead><tbody><tr><th>T</th><td>T</td><td>B</td><td>F</td><td>N</td></tr><tr><th>B</th><td>B</td><td>B</td><td>F</td><td>N</td></tr><tr><th>F</th><td>F</td><td>F</td><td>F</td><td>N</td></tr><tr><th>N</th><td>N</td><td>N</td><td>N</td><td>N</td></tr></tbody></table><table class="center" border="1"><thead><tr><td>OR</td><th>T</th><th>B</th><th>F</th><th>N</th></tr></thead><tbody><tr><th>T</th><td>T</td><td>T</td><td>T</td><td>N</td></tr><tr><th>B</th><td>T</td><td>B</td><td>B</td><td>N</td></tr><tr><th>F</th><td>T</td><td>B</td><td>F</td><td>N</td></tr><tr><th>N</th><td>N</td><td>N</td><td>N</td><td>N</td></tr></tbody></table><table class="center" border="1"><tbody><tr><td>NOT</td><th></th></tr><tr><th>T</th><td>F</td></tr><tr><th>B</th><td>B</td></tr><tr><th>F</th><td>T</td></tr><tr><th>N</th><td>N</td></tr></tbody></table><p>These truth tables should not be confused with <a href="http://en.wikipedia.org/wiki/Many-valued_logic#Belnap_logic_.28B4.29">Belnap logic</a> (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.</p><h4>Who is <a href="http://en.wikipedia.org/wiki/Kurt_G%C3%B6del">Gödel</a>?</h4><p>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 <a href="http://straymindcough.blogspot.com/2009/08/fuzzy-scrollbars.html">before</a>, but this time I'd like to talk about <a href="http://en.wikipedia.org/wiki/T-norm#Prominent_examples">Gödel fuzzy logic</a>. The operations are as follows:</p><ul><li>(x AND y) = min(x, y)</li><li>(x OR y) = max(x, y)</li><li>NOT(x) = 1 - x</li></ul><p>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.</p><h4>What do they have to do with each other?</h4><p>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:</p><ul><li><b>True</b> = 1</li><li><b>Both</b> = 1/2</li><li><b>False</b> = 0</li><li><b>Null</b> = -1/2</li></ul><p>then Gödel fuzzy logic and powerboolean operations are the same.</p>Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com2tag:blogger.com,1999:blog-9161886791806233869.post-68535739832038363112012-02-16T19:34:00.000-08:002012-02-16T22:02:13.512-08:00A survey of 'divmod'<p>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 <tt>divmod</tt>:</p><pre> <b>divmod</b>(917, 4) = (229, 1)</pre><p>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.</p><p>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 <tt>rtn=rtz</tt> and <tt>rtp=rta</tt>) 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, <tt>rtn</tt> is the same computationally on <tt>int32_t</tt> and <tt>uint32_t</tt>, as is <tt>rtp</tt>, but <tt>rtz</tt> and <tt>rta</tt> produce a different computational algorithms on signed and unsigned types. Regardless of the rounding mode chosen, the <tt>divmod</tt> axiom states:</p><pre> <b>divmod</b>(<i>dividend</i>, <i>divisor</i>) = (<i>quotient</i>, <i>remainder</i>)</pre><p>implies</p><pre> <i>dividend</i> = <i>divisor</i>*<i>quotient</i> + <i>remainder</i></pre><p>or put in other words, <tt><i>quotient</i></tt> is approximately (<tt><i>dividend</i>/<i>divisor</i></tt>), but which way it is rounded is up to the rounding mode. This is true for every variant in this article except for <tt>divmod_euc</tt>, which we will discuss later.</p><p>This brings us to our analysis of the most common variants, which are usually called <b>truncated</b> division (also called <tt>quo-rem</tt>), and <b>floored</b> division (also called <tt>div-mod</tt>). 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), </p><pre><b>divmod_rtz</b>(a,b)<br /> • "round towards zero"<br /> • 'rtz' suffix (OpenCL)<br /> • x86:idiv (CPU instruction)<br /> • c99:% (C operator)<br /> • c:mod[fl]? (POSIX)<br /> • c:trunc[fl]? (POSIX)<br /> • c:FE_TOWARDZERO (POSIX)<br /> • c:MPFR_RNDZ (libMPFR)<br /> • rnrs:truncate (Scheme)<br /> • r5rs:quotient (Scheme)<br /> • r5rs:remainder (Scheme)<br /> • r7rs:truncate/ (Scheme)<br /> • "rem() has same sign as dividend"<br /><br /><b>divmod_rtn</b>(a,b) <br /> • "round towards negative infinity"<br /> • 'rtn' suffix (OpenCL)<br /> • c:floor[fl]? (POSIX)<br /> • c:FE_DOWNWARD (POSIX)<br /> • c:MPFR_RNDD (libMPFR)<br /> • rnrs:floor (Scheme)<br /> • r5rs:modulo (Scheme)<br /> • r7rs:floor/ (Scheme)<br /> • "mod() has same sign as divisor"</pre><p>The problem with these two variants being so common is that it is easy to misuse them. It is quite common to use (<tt><i>A</i> % <i>B</i></tt>) as an index of an array of <i>B</i> elements, without checking if <i>A</i> 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 <tt>rtz</tt> and <tt>rtn</tt> rounding modes is that they may give negative remainders. However, there is less possibility of errors with <tt>mod_rtn</tt> when <i>B</i> is positive, because <tt>mod_rtn</tt> gives a positive remainder in that case. C99 was the first version of C that actually specified that <tt>"%"</tt> was <tt>mod_rtz</tt>, but before the 1999 version, that operator could also be <tt>mod_rtn</tt>, in which case the operator would be safe. Since C99 standardized on <tt>mod_rtz</tt>, however, now we know that <tt>"%"</tt> is unsafe, and therefore, we should always test if <i>A</i> is positive first. Another option would be to use <tt>mod_euc</tt>, which is discussed later in this article.</p><p>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.</p><pre><b>divmod_rtp</b>(a,b) <br /> • "round towards positive infinity"<br /> • 'rtp' suffix (OpenCL)<br /> • c:ceil[fl]? (POSIX)<br /> • c:FE_UPWARD (POSIX)<br /> • c:MPFR_RNDU (libMPFR)<br /> • rnrs:ceiling (Scheme)<br /> • r7rs:ceiling/ (Scheme)</pre><p>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:</p><pre><b>divmod_rta</b>(a,b)<br /> • "round away form zero"<br /> • c:MPFR_RNDA (libMPFR)<br /><br /><b>divmod_rnz</b>(a,b)<br /> • "round to nearest, ties towards zero"<br /> • (no examples)</pre><p>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 <tt>rn_</tt> (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.</p><pre><b>divmod_rtd</b>(a,b)<br /> • "round ... default behavior"<br /> • c:nearbyint[fl]? (POSIX)<br /><br /><b>divmod_rnd</b>(a,b)<br /> • "round to nearest, ties ... default behavior"<br /> • c:l?l?rint[fl]? (POSIX)<br /><br /><b>divmod_rna</b>(a,b)<br /> • "round to nearest, ties away from zero"<br /> • c:l?l?round[fl]? (POSIX)</pre><p>The next variants are vary rare, because they cannot be found in C:</p><pre><b>divmod_rnn</b>(a,b)<br /> • "round to nearest, ties towards negative infinity"<br /> • "Round half down" (Wikipedia)<br /> • r6rs:div0, r6rs:mod0 (Scheme)<br /><br /><b>divmod_rnp</b>(a,b)<br /> • "round to nearest, ties towards positive infinity"<br /> • "Round half up" (Wikipedia)<br /> • elementary school rounding (in the U.S.)</pre><p>The next variant, known as <tt>rte</tt> (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.</p><pre><b>divmod_rte</b>(a,b)<br /> • "round to nearest, ties to even"<br /> • "Round half to even" (Wikipedia)<br /> • 'rte' suffix (OpenCL)<br /> • c:remquo[fl]? (OpenCL & POSIX)<br /> • c:remainder[fl]? (OpenCL & POSIX)<br /> • c:FE_TONEAREST (POSIX)<br /> • c:MPFR_RNDN (libMPFR)<br /> • r7rs:round/ (Scheme)</pre><p>The next variant is by far the most advanced <tt>divmod</tt> 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 <tt>div_?(a,b) = round_?(a/b)</tt> where the ? are replaced with a rounding mode, but not the next one. Its definition would be <tt>div_euc(a,b) = sign(b)*floor(a/abs(b))</tt>, but that doesn't even begin to describe it's awesomeness. The reason why <tt>div_euc</tt> is so amazing is that <tt>mod_euc</tt> is <b><i>always</i></b> nonnegative. <b>Period</b>.</p><pre><b>divmod_euc</b>(a,b)<br /> • r6rs:div, r6rs:mod (Scheme)<br /> • r7rs:euclidean/ (Scheme)<br /></pre><p>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.</p><h4 style="margin-bottom:0">Bibliography</h4><ul style="margin-top:0"><li>OpenCL 1.1 Section 6.2.3.2 Rounding Modes.</li><li>C99/POSIX <fenv.h> and <math.h>.</li><li>Revised (5|6|7) Report on Scheme.</li><li>The libmpfr documentation.</li><li>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.</li></ul>Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com0tag:blogger.com,1999:blog-9161886791806233869.post-26724936460548070252012-01-14T14:14:00.000-08:002012-01-14T14:35:54.809-08:00On 'int128_t'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 <tt>'unsigned long long'</tt>, and have a nasty habit of changing the sizes (and meanings) of these types on different platforms. The C type <tt>'short'</tt> is usually 16 bits, <tt>'int'</tt> either 16 or 32 bits, and <tt>'long'</tt> either 32 or 64 bits, depending on platform. This eventually led to the <tt>'stdint.h'</tt> header in C99, which provides exact-size types which can be used accross platforms. These are named <tt>'int32_t'</tt>, <tt>'int64_t'</tt>, <tt>'uint32_t'</tt>, <tt>'uint64_t'</tt>, and so on.<br /><br />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 <tt>'int128_t'</tt> and <tt>'uint128_t'</tt> 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.<br /><br />First, you might say we could just make an array type:<br /><pre> typedef int32_t int128_as_int32x4_t[4];<br /> typedef int64_t int128_as_int64x2_t[2];</pre>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:<br /><pre>typedef struct int128_s {<br /> union int128_u {<br /> int8_t as_int8[16];<br /> int16_t as_int16[8];<br /> int32_t as_int32[4];<br /> int64_t as_int64[2];<br /> } value;<br />} int128_t;</pre>and wrap this type in a typedef. But how do we use these new integers? First of all we need some way of constructing <tt>'int128_t'</tt>s, and in the spirit of <tt>'stdint.h'</tt> we can make a <tt>'INT128_C()'</tt> macro which expands to a constructed object of type <tt>'int128_t'</tt>. We'll need a few functions for this:<br /><pre>int128_t int128_from_int(int from);<br />int128_t int128_from_str(char *from);<br />int int_from_int128(int128_t from);<br />int str_from_int128(char *to, int to_size, int128_t from);</pre>and we can use the second one to define the macro as:<br /><pre>#define INT128_C(x) int128_from_str(#x)</pre>because <tt>'(#x)'</tt> indicates to the preprocessor to turn x into a string before compile-time, which is then passed to <tt>int128_from_str</tt> which then returns an object of type <tt>'int128_t'</tt>. For compilers that do not support compile-time constant expressions involving function calls, we can also define simpler macros as follows:<br /><pre>#ifdef BIG_ENDIAN<br />#define INT128_C64(a,b)\<br /> (int128_t){.value = {.as_int64 = {a, b}}}<br />#define INT128_C32(a,b,c,d)\<br /> (int128_t){.value = {.as_int32 = {a, b, c, d}}}<br />#else<br />#define INT128_C64(a,b)\<br /> (int128_t){.value = {.as_int64 = {b, a}}}<br />#define INT128_C32(a,b,c,d)\<br /> (int128_t){.value = {.as_int32 = {d, c, b, a}}}<br />#endif</pre>Note that because we use designators (value and as_int##) this part requires a C99 compiler<br /><h4>Conclusion</h4>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 <tt>'int128_t'</tt> such as UUID's and IPv6 addresses. We may need this sooner than we think.Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com0tag:blogger.com,1999:blog-9161886791806233869.post-29196652865515164972011-01-28T14:38:00.000-08:002011-01-28T18:59:56.097-08:00Tetrational-point<p> 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, <a href="http://en.wikipedia.org/wiki/Scientific_notation">scientific</a>, and <a href="http://en.wikipedia.org/wiki/Tetration">tetrational</a> representation in unison to achieve greater accuracy, precision, <i>and</i> dynamic range. </p><p> 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.</p><p> The most recent edition of IEEE-754 introduced a 16-bit floating point format, called '<a href="http://en.wikipedia.org/wiki/Half_precision_floating-point_format">binary16</a>' 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:</p><table border="1" style="text-align: center;"> <thead> <tr> <th></th> <th>s</th> <th colspan="5">exponent</th> <th colspan="10">significand</th> </tr> </thead> <tbody> <tr> <th>bin</th> <td>0</td> <td>0</td> <td>1</td> <td>1</td> <td>1</td> <td>1</td> <td>1</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> </tr> <tr> <th>hex</th> <td colspan="4">3</td> <td colspan="4">E</td> <td colspan="4">0</td> <td colspan="4">0</td> </tr> <tr> <th>value</th> <td colspan="16">= 1.5</td> </tr> </tbody></table><p> and this is how the standard binary16 format represents infinity:</p><table border="1" style="text-align: center;"> <thead> <tr> <th></th> <th>s</th> <th colspan="5">exponent</th> <th colspan="10">significand</th> </tr> </thead> <tbody> <tr> <th>bin</th> <td>0</td> <td>1</td> <td>1</td> <td>1</td> <td>1</td> <td>1</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> </tr> <tr> <th>hex</th> <td colspan="4">7</td> <td colspan="4">C</td> <td colspan="4">0</td> <td colspan="4">0</td> </tr> <tr> <th>value</th> <td colspan="16">= Infinity</td> </tr> </tbody></table><p> 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 <a href="http://en.wikipedia.org/wiki/Most_significant_bit">MSB</a> 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.</p><p> 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:</p><div style="text-align: center;"> (-1)<sup><var>s</var></sup><b>exp</b><sub>2</sub><sup>h+5</sup>(0.tetrand) -- HTML</div><div style="text-align: center;"> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mrow> <msup> <mfenced><mn>-1</mn></mfenced> <mi>s</mi> </msup> <msubsup> <mi>exp</mi> <mn>2</mn> <mrow> <mi>h</mi> <mo>+</mo> <mn>5</mn> </mrow> </msubsup> <mfenced> <mn>0.tetrand</mn> </mfenced> </mrow> </math> -- MathML</div><p> 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:</p><table border="1" style="text-align: center;"> <thead> <tr> <th>binary16:</th> <th>s</th> <th colspan="5">exponent</th> <th colspan="10">significand</th> </tr> <tr> <th>tetra16:</th> <th>s</th> <th colspan="5">exponent</th> <th>q</th> <th>h</th> <th colspan="10">tetrand</th> </tr> </thead> <tbody> <tr> <th>bin</th> <td>0</td> <td>1</td> <td>1</td> <td>1</td> <td>1</td> <td>1</td> <td>1</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> </tr> <tr> <th>hex</th> <td colspan="4">7</td> <td colspan="4">E</td> <td colspan="4">0</td> <td colspan="4">0</td> </tr> <tr> <th>value</th> <td colspan="16">≈ 65536</td> </tr> </tbody></table><p> 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</p><table border="1" style="text-align: center;"> <thead> <tr> <th>binary16:</th> <th>s</th> <th colspan="5">exponent</th> <th colspan="10">significand</th> </tr> <tr> <th>tetra16:</th> <th>s</th> <th colspan="5">exponent</th> <th>q</th> <th>h</th> <th colspan="10">tetrand</th> </tr> </thead> <tbody> <tr> <th>bin</th> <td>0</td> <td>1</td> <td>1</td> <td>1</td> <td>1</td> <td>1</td> <td>1</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> <td>1</td> </tr> <tr> <th>hex</th> <td colspan="4">7</td> <td colspan="4">E</td> <td colspan="4">0</td> <td colspan="4">1</td> </tr> <tr> <th>value</th> <td colspan="16">≈ 71036</td> </tr> </tbody></table><p> and perhaps another interesting representation is that of googolplex:</p><table border="1" style="text-align: center;"> <thead> <tr> <th>binary16:</th> <th>s</th> <th colspan="5">exponent</th> <th colspan="10">significand</th> </tr> <tr> <th>tetra16:</th> <th>s</th> <th colspan="5">exponent</th> <th>q</th> <th>h</th> <th colspan="10">tetrand</th> </tr> </thead> <tbody> <tr> <th>bin</th> <td>0</td> <td>1</td> <td>1</td> <td>1</td> <td>1</td> <td>1</td> <td>1</td> <td>1</td> <td>1</td> <td>0</td> <td>1</td> <td>1</td> <td>0</td> <td>0</td> <td>1</td> <td>0</td> </tr> <tr> <th>hex</th> <td colspan="4">7</td> <td colspan="4">F</td> <td colspan="4">B</td> <td colspan="4">2</td> </tr> <tr> <th>value</th> <td colspan="16">≈ googolplex = 10^(10^100)</td> </tr> </tbody></table><p> 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.</p><p> Here is an overview of the extensions to the binary16 format:</p><pre style="background-color: #222; font-size: 10px;">#x0000 = +0<br />#x0001 = 5.960464477539063e-8<br /> ... (standard binary16 floating-point) ...<br />#x7BFF = 65504.<br />#x7C00 = +Infinity<br />#x7C01 = +sNaN<br /> ... (standard binary16 signaling NaN) ...<br />#x7DFF = +sNaN<br />#x7E00 = 65536 = 2^2^2^2^2^(0)<br />#x7E01 = 71036.<br /> ... (new tetrational-point) ...<br />#x7E?? = 2^2^2^2^2^(0.??_16)<br /> ...<br />#x7EFE = 8.9423389054e+15721<br />#x7EFF = 6.2622606021e+17594<br />#x7F00 = 2^65536 = 2^2^2^2^2^2^(0) = 2^2^2^2^2<br />#x7F01 = 6.8504792165e+21383<br /> ... (new tetrational-point) ...<br />#x7F?? = 2^2^2^2^2^2^(0.??_16)<br /> ...<br />#x7FFE = 10^(2.69191e+15721) which is < 2^(2^65536)<br />#x7FFF = +qNaN (unique)<br />#x8000 = -0<br />#x8001 = -5.960464477539063e-8<br /> ... (standard binary16 floating-point) ...<br />#xFBFF = -65504.<br />#xFC00 = -Infinity<br />#xFC01 = -sNaN<br /> ... (standard binary16 signaling NaN) ...<br />#xFDFF = -sNaN<br />#xFE00 = -65536<br />#xFE01 = -71036.<br /> ... (new tetrational-point) ...<br />#xFE?? = -2^2^2^2^2^(0.??_16)<br /> ...<br />#xFEFE = -8.9423389054e+15721<br />#xFEFF = -6.2622606021e+17594<br />#xFF00 = -2^65536<br />#xFF01 = -6.8504792165e+21383<br /> ... (new tetrational-point) ...<br />#xFF?? = -2^2^2^2^2^2^(0.??_16)<br /> ...<br />#xFFFE = -10^(2.69191e+15721) which is > -2^(2^65536)<br />#xFFFF = -qNaN (unique)</pre><p> 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. </p>Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com3tag:blogger.com,1999:blog-9161886791806233869.post-77775740670710150562011-01-03T17:59:00.000-08:002011-01-03T19:09:26.339-08:00GoLang Proposals<p>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.</p><p>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.</p><p>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.</p><p>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.</p><p>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. </p><hr/><h4 style="font-weight:bold;color:#AD9">Proposal #1: Add first-class types</h4><p>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:</p><pre>func Map(KeyT .(type), T .(type)) .(type) {<br /> type mapT []struct{<br /> hash int<br /> key KeyT<br /> value T<br /> }<br /> return mapT<br />}</pre><p>Using this proposal, we can simulate <tt>map[KeyT]T</tt> with <tt>Map(KeyT, T)</tt>. As you can see, type parameters are indicated with the <tt>".(type)"</tt> token as is found in Go type-switch statements. One advantage of this system would be that it could be used to define <tt>Array(n, T)</tt> and <tt>Matrix(m, n, T)</tt> which would be impossible to define using more restrictive generics. Other functions that could defined using this proposal are <tt>new</tt> and <tt>make</tt>, which take a type as their first parameter. Here is a summary of the related changes to the Go specification:</p><pre><b>Result</b> |= ".(type)"<br /><b>ParameterDecl</b> |= TypeName ".(type)"<br /><b>Expression</b> |= TypeName</pre><p>In addition to these syntactic changes, a few paragraphs of rules and discussion maybe required.</p><hr/><h4 style="font-weight:bold;color:#AD9">Proposal #2: Add <tt>'generic'</tt> (or <tt>'_Generic'</tt>) keyword</h4><p>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 <tt>.(type)</tt>, 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.</p><pre>generic Map[KeyT]T []struct{<br /> hash int<br /> key KeyT<br /> value T<br />}</pre><p>Using this proposal, we can simulate <tt>map[KeyT]T</tt> with <tt>Map[KeyT]T</tt>. 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:</p><pre><b>TypeLit</b> |= GenericType<br /><b>TopLevelDecl</b> |= GenericDecl<br />GenericType = "generic" GSignature Type<br />GenericDecl = "generic" identifier GSignature Type<br />GSignature = GParameters identifier<br />GParameters = "[" [ GParameterList [ "," ] ] "]"<br />GParameterList = GParameterDecl { "," GParameterDecl }<br />GParameterDecl = identifier</pre><p>Having considered adding generic syntax to <tt>LiteralType</tt>, 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.</p><p>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.</p><hr/><h4 style="font-weight:bold;color:#AD9">Proposal #3: Add <tt>'attrib'</tt> (or <tt>'_Attrib'</tt>) keyword</h4><p>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 <tt>__attribute__((id))</tt> 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: <tt>_Attrib(id)</tt>, 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:</p><pre>generic attrib(public) map[KeyT]T []struct{<br /> hash int<br /> key KeyT<br /> value T<br />}</pre><p>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 <tt>cap</tt> and <tt>len</tt> to a library implementation.</p><p>The syntax was designed to force the <tt>attrib</tt> specifier immediately before the identifier, to make it clear which identifier it is referring to. The changes to the <tt>MethodDecl</tt> production are questionable, and require more consideration and discussion. I have also considered moving <tt>AttribSpec</tt> to before the keywords which would simplify the grammar significantly. This is the summary of all the required extensions to the Go specification.</p><pre><b>ConstSpec</b> |= AttribSpec IdentifierList <br /> [ [ Type ] "=" ExpressionList ]<br /><b>TypeSpec</b> |= AttribSpec identifier Type<br /><b>VarSpec</b> |= AttribSpec IdentifierList <br /> ( Type [ "=" ExpressionList ] <br /> | "=" ExpressionList )<br /><b>MethodDecl</b> |= "func" Receiver AttribSpec <br /> MethodName Signature [ Body ]<br /><b>FunctionDecl</b> |= "func" AttribSpec identifier <br /> Signature [ Body ]<br />GenericDecl |= "generic" AttribSpec identifier <br /> GSignature Type<br />AttribSpec = "attrib" "(" identifier <br /> [ "(" ExpressionList ")" ] ")"</pre><hr/><h4 style="font-weight:bold;color:#AD9">Proposal #4: Add <tt>'pragma'</tt> (or <tt>'_Pragma'</tt>) keyword</h4><p>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:</p><pre>pragma("GCC poison strdup")<br />pragma("DSGO prefix pthread_")</pre><p>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:</p><pre><b>TopLevelDecl</b> |= PragmaDecl<br />PragmaDecl = "pragma" "(" string_lit ")"</pre><hr/><h4 style="color:#AD9">Conclusion</h4><p>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.</p>Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com3tag:blogger.com,1999:blog-9161886791806233869.post-73897777209719192222009-08-16T06:56:00.000-07:002009-08-16T06:58:15.703-07:00Fuzzy Scrollbars<p>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 <a href="http://en.wikipedia.org/wiki/T-norm#Prominent_examples">product fuzzy logic</a> for the remainder of this post.</p><h4>Product Fuzzy Logic</h4><p>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 <code>Clamp</code> datatype. There are obvious mappings to and from <code>Clamp</code> and <code>Bool</code>: 0 maps to <code>False</code>, 1 maps to <code>True</code>, and the in betweens can be handled on a case-by-case basis (possibly to throw and error or something).</p><p>The operations on the <code>Clamp</code> 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</p><ul><li><b>not</b>(x) = 1 - x</li><li><b>and</b>(x, y) = xy</li><li><b>or</b>(x, y) = x + y - xy</li><li><b>implies</b>(x, y) = 1 - x(1 - y)</li></ul><p>One interesting thing about product fuzzy logic is that there are multiple ways of defining <b>equiv</b>, depending on what properties you are looking for. One possibility is that <b>equiv</b>(x, y) = <b>and</b>(<b>implies</b>(x, y), <b>implies</b>(y, x)), which would mean that it would have to be defined as <b>equiv</b>(x, y) = (1 - x - y + 3xy - yx<sup>2</sup> - xy<sup>2</sup> + x<sup>2</sup>y<sup>2</sup>). This is quite a mess, and the same effect (in terms of mapping to <code>Bool</code>) can be accomplished by the definition <b>equiv</b>(x, y) = (1 - x - y + 2xy).</p><p>Other considerations for operations on the <code>Clamp</code> 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 <code>Clamp</code> datatype are excplicit, then this is not a problem.</p><h4>Scrollbars</h4><p>Just as the <code>String</code> is the basis for the text field widget, the <code>Clamp</code> 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 <code>Clamp</code> datatype provides.</p><h4>Colors</h4><p>Why is it that such a fundamental datatype like <code>Clamp</code> is not found in more programming languages? Usually it is defined as equivalent to <code>Float</code> or <code>Double</code>, 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 <code>GLclamp</code> 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 <code>GLclamp</code>s.</p><p>With so many applications, the <code>Clamp</code> 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 <i>few</i> abstractions, and using them is <i>easy</i>. I think <code>Clamp</code> datatype meets both of these requirements.</p><p>From fuzzy logic to colors to scollbars, <code>Clamp</code> seems to form the basis of an unrecognized basis for computation that may be useful in the future.</p>Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com0tag:blogger.com,1999:blog-9161886791806233869.post-72008098588783047272009-06-15T14:13:00.000-07:002009-06-15T14:15:21.957-07:00Embedded OpenGL<p>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 <code>glColorPointer</code>, <code>glNormalPointer</code>, and <code>glTexCoordPointer</code> have been augmented with <code>glVertexAttribPointer</code>, 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:</p><ul><li><b>Blend</b> </li><li><b>Buffer</b> -- pixel buffers, vertex buffers, and index buffers</li><li><b>Capability</b> -- abstract class with glEnable and glDisable</li><li><b>Clear</b> -- clearing the background to a solid color</li><li><b>Color</b> </li><li><b>CullFace</b> -- consists of glCullFace and glFrontFace</li><li><b>Depth</b> </li><li><b>FrameBuffer</b> </li><li><b>Get</b> -- reading global state with functions like glGetString etc.</li><li><b>Mipmap</b> -- utilities for the Texture class</li><li><b>Program</b> </li><li><b>RenderBuffer</b> </li><li><b>Shader</b> -- vertex and fragment shaders</li><li><b>Stencil</b> </li><li><b>Texture</b> </li><li><b>Uniform</b> -- uniform variables</li><li><b>VertexAttrib</b> -- vertex attributes</li></ul><p>after removing these functions from the OpenGL-ES 2.0 API, we are left with the miscellaneous functions:</p><ul><li>glDrawArrays(mode, first, count)</li><li>glDrawElements(mode, count, type, indices)</li><li>glFinish()</li><li>glFlush()</li><li>glLineWidth(width)</li><li>glPolygonOffset(factor, units)</li><li>glSampleCoverage(value, invert)</li><li>glPixelStorei(name, param)</li><li>glReadPixels(x, y, width, height, format, type, pixels)</li><li>glScissor(x, y, width, height)</li><li>glViewport(x, y, width, height)</li></ul><p>This says a lot about OpenGL-ES, especially the fact that <code>glDrawPixels</code> 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 <code>GL_QUADS</code>, so you have to use <code>GL_TRIANGLE_FAN</code> to accomplish the same result. <code>glReadPixels</code>, <code>glScissor</code>, and <code>glViewport</code> can be related in that they all accept a rectangle as an argument.</p><p>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.</p>Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com0tag:blogger.com,1999:blog-9161886791806233869.post-51547718649213929162009-06-08T18:23:00.001-07:002011-01-28T18:48:49.419-08:00Semantic MathML<p>I don't know <a href="http://semanticweb.org/wiki/Semantic_MathML">what they were thinking</a>, but there is a much better way to encode <a href="http://www.w3.org/TR/MathML2/">MathML</a> in RDF. One can be tempted to assign an RDF property to every element in MathML, but that wouldn't be the <a href="http://www.openmath.org/">OpenMath</a> 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 <i>Strict Content</i>. The last one requires only 10 XML Elements to be understood by MathML3 processors, namely: <code>m:apply</code>, <code>m:bind</code>, <code>m:bvar</code>, <code>m:csymbol</code>, <code>m:ci</code>, <code>m:cn</code>, <code>m:cs</code>, <code>m:share</code>, <code>m:semantics</code>, <code>m:cerror</code>, and <code>m:cbytes</code>. 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:</p><pre>@prefix ari: <http://www.openmath.org/cd/arith1#> .<br />@prefix fns: <http://www.openmath.org/cd/fns1#> .<br />@prefix sts: <http://www.openmath.org/cd/sts#> .<br />@prefix sm: <http://example.com/SemanticMath/> .<br />@prefix m: <http://www.w3.org/1998/Math/MathML> .</pre><p>These are the <code>rdfs:Class</code>'s we will define:</p><ul><li><code>sm:Content</code> (all MathML Content)</li><li><code>sm:Number</code> (for <cn/>, subclass of <code>sts:NumericalValue</code>)</li><li><code>sm:String</code> (for <cs/>, subclass of <code>xs:string</code>)</li></ul>and these are the <code>rdf:Property</code>'s we will define:<ul><li><code>sm:apply</code> :: Property * sm:Content</li><li><code>sm:applyTo</code> :: Property * (List sm:Content)</li><li><code>sm:bind</code> :: Property * (List sm:Content)</li><li><code>sm:bindOp</code> :: Property * sm:Content</li><li><code>sm:bindIn</code> :: Property * sm:Content</li><li><code>sm:error</code> :: Property sm:Error sm:Content</li><li><code>sm:errorWas</code> :: Property sm:Error (List sm:Content)</li></ul>Strict Content MathML3 can be translated with the following algorithm:<ul><li><code><m:cn> NUM </m:cn></code></li><code>"NUM"^^sm:Number<li><code><m:cs> TEXT </m:cs></code></li><code>" TEXT "^^sm:String</code><li><code><m:ci> Name </m:ci></code></li>Use blank node identifier (like _:Name)<li><code><m:csymbol> Symbol </m:csymbol></code></li>Use URIs (http://www.openmath.org/cd/arith1#plus for <m:csymbol cd="arith1">plus</m:csymbol>, or the value of the <code>definitionURL</code> for MathML2)<li><code><m:share/></code></li>Use URIs<li><code><m:cbytes> DATA </m:cbytes></code></li><code>" DATA "^^xs:base64Binary</code><li><code><m:cerror> Symbol Content* </m:cerror></code></li><pre>[] rdf:type sm:Error ;<br /> sm:error Symbol ;<br /> sm:errorWas LIST(Content) .</pre><li><code><m:apply> Symbol Content* </m:apply></code></li><pre>[] sm:apply Symbol ;<br /> sm:applyTo LIST(Content) .</pre><li><code><m:bind> Symbol Vars* Content* </m:bind></code></li><pre>[] sm:bindOp Symbol ;<br /> sm:bind LIST(Vars) ;<br /> sm:bindIn LIST(Content) .</pre></code></ul><p>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 <code>sts:mapsTo</code> special, and maybe map it to an appropriate <code>rdfs:Class</code>. As an example of how this might be used, this is how the <a href="http://www.haskell.org/">Haskell</a> code (<code>\x -> x + 2</code>) would be translated into RDF using the properties listed above as follows:</p><pre>_:f sm:bindOp fns:lambda ;<br /> sm:bind LIST(_:x) ;<br /> sm:bindIn LIST(<br /> [ sm:apply ari:plus ; <br /> sm:applyTo LIST(_:x "2"^^sm:Number) ]).</pre><p>Now that RDF has lambdas, the possibilities are endless!</p>Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com1tag:blogger.com,1999:blog-9161886791806233869.post-6771376189276881852009-06-07T13:48:00.000-07:002009-06-07T13:52:52.682-07:00Subtly Different Linked Lists<p>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 (<i>A</i>, <i>B</i>, <i>C</i>) = (<i>A</i>, (<i>B</i>, (<i>C</i>, 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 <code>list<<i>T</i>></code> type in STL, Lisp has the <code>'list</code> type, Haskell has the <code>[<i>T</i>]</code> type, and RDF has the <code>rdf:List</code> type. We will not consider sequences here, so C types will be left for a future article.</p><p>Without any type restrictions, such a pair need not be required to make a list. For example, we could make the structure ((<i>A</i>, <i>B</i>), <i>C</i>), but we could not interpret it as a list. This is exactly how the Common Lisp <code>cl:cons</code> constructor works. The <a href="http://www.lispworks.com/documentation/HyperSpec/Front/index.htm">Common Lisp HyperSpec</a> calls anything constructed with <code>cl:cons</code> a list. The special case where the second element of <code>cl:cons</code> is either another <code>cl:cons</code> or a <code>cl:nil</code> is called a <b>proper list</b>. 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 <code>rdf:rest</code> is <code>rdf:List</code>, so any attempt to make an improper list with <code>rdf:rest</code> will result in an inconsistent RDF graph.</p><p>With the restriction that the second part of a pair is a list, we obtain so-called <b>heterogeneous lists</b>, 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 <b>homogeneous lists</b> for obvious reasons. This subtype is what is found in more strict languages, such as <code>list<<i>T</i>></code> in C++ and <code>[<i>T</i>]</code> in Haskell. This is an overview of the different kinds of lists we have talked about:</p><ul><li>Improper list (a, (b, c))</li><li>Proper list (a, (b, (c, ())))</li><ul><li>Heterogeneous list [1, "message"]</li><li>Homogeneous list [1, 2, 3]</li></ul></ul><p>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 <code>cl:Cons</code> the Class and <code>cl:cons</code> the constructor. First we need <code>rdf:List rdf:subClassOf cl:Cons</code> so that they can work together, and then <code>cl:Cons</code> will represent both improper lists and proper lists, and <code>rdf:List</code> will represent proper lists only. To represent an improper list, would would have to be an instance of <code>cl:Cons</code> but not <code>rdf:List</code>. For a heterogeneous list, one would have to be missing the <code>ex:listType</code> property, and for a homogeneous list, one would require the presence of the <code>ex:listType</code> property. This covers all the different list types discussed above.</p>Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com0tag:blogger.com,1999:blog-9161886791806233869.post-34814522336391596112009-06-06T18:01:00.000-07:002009-06-06T18:13:28.784-07:00HTML Script Datatypes<p>While wandering through the W3C specification for <code><a href="http://www.w3.org/TR/rdf-text/">rdf:text</a></code>, 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. <a href="http://www.w3.org/TR/html401/">HTML 4.01</a> defines multiple datatypes, some of which are redefined by <a href="http://www.w3.org/Style/CSS/">CSS</a>, such as Color and Length. The one that cought my attention was <a href="http://www.w3.org/TR/html4/types.html#type-script">Script</a>, which could be used to represent scripts written in different languages.</p><p>UNIX has long since had this datatype built in to almost every Shell interpreter. The so-called <a href="http://en.wikipedia.org/wiki/Shebang_(Unix)">Hash-Bang</a> 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:</p><pre> @prefix hdt: <http://www.w3.org/TR/html4/types.html> .<br /> @prefix js: <urn:ecmascript:> .<br /><br /> _:f rdf:type js:Function .<br /> _:f js:Call """<br /> function () {<br /> this.done = true;<br /> } @<a href="http://www.ietf.org/rfc/rfc4329.txt">application/ecmascript</a>"""^^<a href="http://www.w3.org/TR/html4/types.html#type-script">hdt:Script</a> .</pre><p>Here you can see the <code>@</code> notation is used to separate the script data from the media type, just as it is in the <code>rdf:text</code> datatype. This would allow a mixture of data (RDF graphs) and code (JS scripts), which are the beginnings of a full-fledged programming language.</p>Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com0tag:blogger.com,1999:blog-9161886791806233869.post-38962097595078938412009-06-03T11:45:00.000-07:002009-06-03T11:47:43.323-07:00XML Infoset Models<p>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. </p><table border="0" cellspacing="5" cellpadding="0"><thead><th style="text-align: left;">Class Name </th><th><a href="http://www.w3.org/TR/REC-xml/">XML</a></th><th><a href="http://www.w3.org/TR/REC-DOM-Level-1/">DOM</a></th><th><a href="http://www.w3.org/TR/exi/">EXI</a></th><th><a href="http://www.w3.org/TR/xml-infoset/">Info</a></th><th><a href="http://www.w3.org/TR/xpath-datamodel/">Path</a></th></thead><tbody><tr><td><b>Attribute</b></td><td>Y</td><!--XML--><td>Y</td><!--DOM--><td>Y</td><!--EXI--><td>Y</td><!--IS--><td>Y</td><!--XQ--></tr><tr><td>CDATASection </td><td>Y</td><!--XML--><td>Y</td><!--DOM--><td>N</td><!--EXI--><td>N</td><!--IS--><td>N</td><!--XQ--></tr><tr><td>CharacterData </td><td>Y</td><!--XML--><td>Y</td><!--DOM--><td>Y</td><!--EXI--><td>Y</td><!--IS--><td>N</td><!--XQ--></tr><tr><td>Comment </td><td>Y</td><!--XML--><td>Y</td><!--DOM--><td>O</td><!--EXI--><td>Y</td><!--IS--><td>Y</td><!--XQ--></tr><tr><td><b>Document</b></td><td>Y</td><!--XML--><td>Y</td><!--DOM--><td>Y</td><!--EXI--><td>Y</td><!--IS--><td>Y</td><!--XQ--></tr><tr><td>DocumentFragment </td><td>N</td><!--XML--><td>Y</td><!--DOM--><td>Y</td><!--EXI--><td>N</td><!--IS--><td>N</td><!--XQ--></tr><tr><td>DocumentType </td><td>Y</td><!--XML--><td>O</td><!--DOM--><td>O</td><!--EXI--><td>Y</td><!--IS--><td>N</td><!--XQ--></tr><tr><td><b>Element</b></td><td>Y</td><!--XML--><td>Y</td><!--DOM--><td>Y</td><!--EXI--><td>Y</td><!--IS--><td>Y</td><!--XQ--></tr><tr><td>Entity </td><td>Y</td><!--XML--><td>O</td><!--DOM--><td>O</td><!--EXI--><td>Y</td><!--IS--><td>N</td><!--XQ--></tr><tr><td>EntityReference </td><td>Y</td><!--XML--><td>O</td><!--DOM--><td>O</td><!--EXI--><td>Y</td><!--IS--><td>N</td><!--XQ--></tr><tr><td><b>Namespace</b></td><td>Y</td><!--XML--><td>O</td><!--DOM--><td>O</td><!--EXI--><td>Y</td><!--IS--><td>Y</td><!--XQ--></tr><tr><td>Notation </td><td>Y</td><!--XML--><td>O</td><!--DOM--><td>N</td><!--EXI--><td>Y</td><!--IS--><td>N</td><!--XQ--></tr><tr><td>ProcessingInstruction </td><td>Y</td><!--XML--><td>O</td><!--DOM--><td>O</td><!--EXI--><td>Y</td><!--IS--><td>Y</td><!--XQ--></tr><tr><td><b>Text</b></td><td>Y</td><!--XML--><td>Y</td><!--DOM--><td>Y</td><!--EXI--><td>Y</td><!--IS--><td>Y</td><!--XQ--></tr></tbody></table><p>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. </p><p>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 <i>required</i> by all W3C models are: Attributes, Elements, Documents, Namespaces and Text. Why all the bloat?</p>Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com1tag:blogger.com,1999:blog-9161886791806233869.post-55367068056041862082009-05-30T22:50:00.000-07:002009-05-30T22:53:42.019-07:00Set Exponentiation<p>Exponentiation is the operation of multiplying the same element by itself a given number of times. Defined by the relation <var>y</var><sup><var>x</var></sup> = <var>y</var>⋅<var>y</var><sup><var>x</var> − 1</sup>, it can be evaluated by multiplication until <var>y</var><sup>1</sup> is encountered, which is just <var>y</var>. 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.</p><p>Exponentiation can even be extended to matrices with the help of the equation <var>Y</var><sup><var>X</var></sup> = exp(log(<var>Y</var>)<var>X</var>) 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 |<var>X</var>| and codomain |<var>Y</var>| of a function, give |<var>Y</var>|<sup>|<var>X</var>|</sup> = |<var>Y</var><sup><var>X</var></sup>| when exponentiated. This is the idea behind the notation of a power set (denoted 2<sup><var>X</var></sup>), which can be thought of as the set of all functions from <var>X</var> to a boolean (which represents whether or not it is contained). This is illustrated by the following maps in <a href="http://json.org/">JSON syntax</a>:</p><ul><li>{"a": 0, "b": 0, "c": 0}</li><li>{"a": 0, "b": 0, "c": 1}</li><li>{"a": 0, "b": 1, "c": 0}</li><li>{"a": 0, "b": 1, "c": 1}</li><li>{"a": 1, "b": 0, "c": 0}</li><li>{"a": 1, "b": 0, "c": 1}</li><li>{"a": 1, "b": 1, "c": 0}</li><li>{"a": 1, "b": 1, "c": 1}</li></ul><p>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<sup>3</sup> is 8. Following this to its logical conclusion, we arrive at a justification for <a href="http://en.wikipedia.org/wiki/Currying">currying</a>. 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 <var>Z</var><sup><var>X</var>×<var>Y</var></sup> = (<var>Z</var><sup><var>Y</var></sup>)<sup><var>X</var></sup>, and in Haskell notation this would be <var>X</var> -> <var>Y</var> -> <var>Z</var>. 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 <a href="http://portal.acm.org/citation.cfm?id=61690">Z notation</a> specification language, because it defines functions as equivalent to their relations. In other words <var>f</var>(<var>x</var>) = <var>y</var> iff (<var>x</var>, <var>y</var>) is a member of <var>f</var>. To illustrate how set exponentiation characterizes many concepts in programming languages, here is a list of common structures:</p><ul> <li>2<sup><var>X</var></sup> - <b>Predicates</b> - functions that return a boolean.</li> <li><var>X</var><sup>2</sup> - <b>If/Then/Else</b> - functions from booleans to a value.</li> <li><var>X</var><sup><var>n</var></sup> - <b>Switch/Case</b> - functions from an enumeration to a value.</li> <li><var>Y</var><sup><var>X</var></sup> - <b>Unary Functions</b> - functions from any value to any value.</li> <li><var>X</var><sup><var>X</var></sup> - <b>Unary Operations</b> - functions from a value to a value.</li> <li><var>X</var><sup><var>X</var><sup>2</sup></sup> - <b>Binary Operations</b> - functions from two values.</li> <li><var>X</var><sup><var>X</var><sup><var>n</var></sup></sup> - <b><i>n</i>-ary Operations</b> - functions from many values.</li> <li>2<sup><var>X</var><sup>2</sup></sup> - <b>Binary Relations</b> - also called multi-functions. <li>2<sup><var>X</var><sup><var>n</var></sup></sup> - <b><i>n</i>-ary Relations</b> - also called multi-functions.</ul><p>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: <var>X</var><sup><var>X</var><sup><var>X</var></sup></sup>. What does this stand for? Well, conceptually, it takes a Unary Operation over <var>X</var>, and gives a value from <var>X</var>. This is exactly what happens when you evaluate a function at a value, which means the "evaluate at 0" function is in <var>X</var><sup><var>X</var><sup><var>X</var></sup></sup>. What's more, is that this is the beginnings of a set-theoretic <a href="http://tetration.itgo.com">Tetration</a> (my other website), which I could talk about for hours, but I will save it for another time.</p>Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com0tag:blogger.com,1999:blog-9161886791806233869.post-37863442624143732412009-05-30T11:20:00.000-07:002009-06-03T11:45:34.558-07:00Nonstandard Namespaces<p>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.</p><dl><dt><code>r6rs</code> (Scheme R6RS)</dt><dd>http://www.r6rs.org/final/html/r6rs/r6rs.html</dd><dt><code>r5rs</code> (Scheme R5RS)</dt><dd>http://www.schemers.org/Documents/Standards/R5RS/</dd><dt><code>cl</code> (Common Lisp)</dt><dd>http://www.lispworks.com/documentation/HyperSpec/</dd><dt><code>cs</code> (<a href="http://crystal.svn.sourceforge.net/viewvc/crystal/CS/trunk/scripts/xml/cs_world.xsd">CS</a>, <a href="http://www.crystalspace3d.org/main/CEL_XML_syntax_guide">CEL</a>)</dt><dd>http://www.crystalspace3d.org/2000/cs_world</dd><dt><code>x3d</code> (X3D, VRML)</dt><dd>http://www.web3d.org/specifications/x3d-namespace</dd><dt><code>pl</code> (Apple PList)</dt><dd>http://www.apple.com/DTDs/PropertyList-1.0.dtd</dd></dl><p>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.</p>Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com0tag:blogger.com,1999:blog-9161886791806233869.post-33355183405217035702009-05-30T10:36:00.000-07:002009-05-30T10:40:09.922-07:00Webizing Common Lisp<p>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 <a href="http://www.lispworks.com/documentation/HyperSpec/Front/index.htm">Common Lisp</a> has vastly more features. However, to make a true comparison, we have to <a href="http://www.w3.org/DesignIssues/Webize.html">webize</a> Lisp. At the very least, this requires a URI for every symbol. We can start by giving a namespace to all symbols in the <a href="http://www.lispworks.com/documentation/HyperSpec/Body/01_i.htm">COMMON-LISP</a> package.</p><pre>http://www.lispworks.com/documentation/HyperSpec/</pre><p>For convinience, we will use the <code>cl</code> prefix for this namespace. We can now start relating Web standards and Lisp, or even writing ontologies using Lisp functions.</p><p>Lets compare lists, which are a fundamental part of Lisp. In Lisp, a cons <code>(x . y)</code> would correspond to the RDF graph given by <code>[ a rdf:List ; rdf:first _:x ; rdf:rest _:y ]</code> and <code>cl:nil</code> would correspond to <code>rdf:nil</code>. We can do this with almost all Lisp syntax, except perhaps for the syntax based on the hash (#) symbol. For example, <code>#c(3 4)</code> would correspond to the MathML <code><cn type="complex-cartesian">3<sep/>4</cn></code>, so the mapping can get complicated.</p><p>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 <a href="http://en.wikipedia.org/wiki/Bijection">bijection</a>...</p>Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com0tag:blogger.com,1999:blog-9161886791806233869.post-23826563729503725682009-05-22T18:06:00.000-07:002009-05-23T09:18:23.730-07:00The Web Metamodel<p>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 <a href="http://www.w3.org/">W3C</a>'s standard only take up roughly 3-levels (much like <a href="http://www.lispworks.com/documentation/HyperSpec/Front/index.htm">Lisp</a>). 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 <a href="http://www.w3.org/TR/rdf-schema/#ch_subclassof"><code>rdf:subClassOf</code></a> relationship, and the arrows indicate a <a href="http://www.w3.org/TR/rdf-schema/#ch_type"><code>rdf:type</code></a> relationship.</p><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgnf6W3nbZE5yUqYDr3HSXCdA-wSunVF_nkfK5JtVyBwL5roGOPzltyDp2kI71UtgEWo0WBfnE_m9x-UGInFYWIhspHhl4Ppz47FhNVZIGR-vPqqDpoavrMCQ4rKMTznKzURuJQKlFZZVM/s320/web_metamodel.png" border="0" alt="" /><p>Although there was no indication in the standards that <a href="http://www.w3.org/TR/2004/REC-owl-guide-20040210/#owl_Class"><code>owl:Class</code></a> is an instance of <a href="http://www.w3.org/TR/rdf-schema/#ch_class"><code>rdfs:Class</code></a>, it is a logical consequence, because <code>owl:Class</code> is a subclass of <code>rdfs:Class</code>, and <code>rdfs:Class</code> is an instance of itself. However, the same could be said of <code>rdfs:Datatype</code>, for which there is an explicit mention that <code>rdfs:Datatype</code> is both a subclass <em>and</em> an instance of <code>rdfs:Class</code>. There was also <a href="http://www.w3.org/2001/sw/WebOnt/webont-issues.html#I5.22-owl:Class-still-needed">an issue about this</a>, which decided the reason for <code>owl:Class</code> was to be distinct from <code>rdfs:Datatype</code>, not because of some cyclic dependancy stuff. So to keep the model simple, and to minimize cycles, we can ignore the fact that <code>rdfs:Datatype</code> is an instance of <code>rdfs:Class</code>, because this is implied by the fact that <code>rdfs:Class</code> is an instance of itself.</p><p>To overview some of the triples in this model, the standards say</p><ul><li><code>rdfs:Class rdf:type rdfs:Class .</code></li><li><code>owl:Class rdf:subClassOf rdfs:Class .</code></li><li><code>rdfs:Datatype rdf:subClassOf rdfs:Class . </code></li><li><code>rdfs:Class rdf:subClassOf rdfs:Resource .</code></li><li><code>rdfs:Resource rdf:type rdfs:Class .</code></li></ul><p>Notably, we have ignored the <code>rdf:Property</code> 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: <a href="http://www.w3.org/TR/rdf-schema/#ch_resource"><code>rdfs:Resource</code></a>, <a href=""><code>rdfs:Datatype</code></a>, <a href="http://www.w3.org/TR/rdf-schema/#ch_class"><code>rdfs:Class</code></a>, and <a href="http://www.w3.org/TR/2004/REC-owl-guide-20040210/#owl_Class"><code>owl:Class</code></a>. Aside from <a href="http://www.w3.org/TR/2004/REC-owl-ref-20040210/#EnumeratedDatatype"><code>owl:DataRange</code></a>, 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.</p>Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com0tag:blogger.com,1999:blog-9161886791806233869.post-73096660337322812962009-05-18T22:10:00.000-07:002009-05-18T22:23:28.499-07:00Semantic Binary Data<p>There seems to be quite a few quite a few things missing from <a href="http://www.w3.org/XML/Schema">XML Schema</a>, <a href="http://www.w3.org/TR/rdf-schema/">RDF</a> and <a href="http://www.w3.org/2007/OWL/wiki/OWL_Working_Group">OWL</a>, 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 href="http://www.w3.org/TR/2009/WD-owl2-syntax-20090421/#Binary_Data">a note in OWL 2</a> which talks about the consequences of the distinction between <a href="http://www.w3.org/TR/xmlschema-2/#base64Binary"><code>xs:base64Binary</code></a> and <a href="http://www.w3.org/TR/xmlschema-2/#hexBinary"><code>xs:hexBinary</code></a>. 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).</p><p>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 <a href="http://www.w3.org/TR/2004/REC-owl-ref-20040210/#unionOf-def"><code>owl:unionOf</code></a> type that combined the two. Or another option would be to define an <a href="http://www.w3.org/TR/rdf-schema/#ch_list"><code>rdf:List</code></a> 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.</p><p>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 <a href="http://www.w3.org/TR/rdf-schema/#ch_property"><code>rdf:Property</code></a> called <code><b>ex:listType</b></code>. 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 <a href="http://www.haskell.org/onlinereport/">Haskell</a>-like syntax, this would mean (<code>x :: Property a b</code>) would correspond to the triples</p><pre>_:x rdf:type rdf:Property .<br />_:x rdfs:domain _:a .<br />_:x rdfs:range _:b .</pre><p>which means the appropriate way to encode list types in RDF, such as (<code>x :: List a</code>), would be with the triples</p><pre>_:x rdf:type rdf:List .<br />_:x <b>ex:listType</b> _:a .</pre><p>With this new construct, a unified <code><b>ex:binary</b></code> type could easily be defined as (<code>List xs:unsignedByte</code>). Or in simpler terms, the triple (<code>_:x rdf:type <b>ex:binary</b></code>) would be equivalent to the triples</p><pre>_:x rdf:type rdf:List .<br />_:x <b>ex:listType</b> xs:unsignedByte .</pre><p>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 <a href="http://www.omg.org/gettingstarted/corbafaq.htm">CORBA</a>, <a href="http://www.w3.org/TR/WebIDL/">IDL</a> and <a href="http://www.uml.org/">UML</a>. The fact that they allow expressing higher-order types such as those found in Haskell is promising. Perhaps the goal of model compilation (the <a href="http://www.omg.org/">OMG</a> kind), is much closer than we think. However, the <a href="http://www.uml-forum.com/FAQ.htm#What_are_the_outstanding_issues">bloat of UML</a> does more to complicate model translation than to simplify it.</p><p>Perhaps the simplicity of RDF is all we need.</p>Andrew Robbinshttp://www.blogger.com/profile/09074689878199168258noreply@blogger.com0