Databases, Part 1: Components

1. Overview. So I've been using databases recently, and wanted to write a series of notes on them.

1.1. Warning: We will NOT talk about:

1. What's going on "under the hood" in a database
2. Compare various engines (SQL vs. NoSQL vs. etc.)
3. How to code a database engine from scratch
4. How to optimize a given database engine (e.g., "How do I tune MySQL?")

1.2. Topics Discussed in the Series. We will review a database agnostic pseudocode for queries, data definition, data manipulation. We will introduce the basic concepts, using black boxes along the way (e.g., "The database typically has a storage engine translating the data to the machine" and specify it no further!).

1.3. Topics Discussed in this post. We will discuss the components of a database, namely: a database record, record's field, query, table, and views.

1.4. Intended Audience. If you're a programmer, have not learned databases, but need to learn how to use them, then this article is for you! If you are trying to write a database in, say, C...this isn't for you.

Remark. It dawns on me others have pointed out SQL is a DSL [andrejkoelewijn.com]; this is true, but we need to abuse language when working with full generality. (Say what? We need to pretend the terms are not "strict" and "loose", e.g., weakening the demand that all entries in the database have identical format.)

Database Components

2.Terminology. So, suppose we're programmers for a library. They want a program to keep track of their books. What do we do?

2.1. Records. Well, each book is represented by some "Record" (also called a row or, in CS theory, tuple) which is like a plain old data structure.

I think theoretical computer scientists would want me to say "A record is a well-defined, ordered, finite list of heterogeneous fields" or something similar.

At any rate, returning to the library example, our records would be the books.

We call a record's components its "Fields" (or Columns). For a book, its fields would be the author, the title, the publisher, the year published, etc.

Right, so far a Database Record is just a composite data structure, and a Field is an entry in a record.

2.1.1. Pseudocode Conventions. I try to adhere to CLRS' pseudocode conventions (according to their third edition). So foobar.spam accesses the field spam of the variable foobar, a composite data structure. (This is eerily similar to JSON in JavaScript.)

So if hamlet represents a record, then the field hamlet.author should be the string "William Shakespeare".

2.1.2. Conventions. All records have some default fields: id (which is assigned by the engine "under the hood" to keep track of records). More may be added later, for now id is all that's needed.

2.2. Queries. A database is great because we can look stuff up. For libraries, we can find all books within a given subject, or find all the books one given author wrote, or...

Each of these are a "Query" which retrieve records from the database based on specific criteria (e.g., year published, author, subject, etc.).

2.3. Tables, Views. We usually stick these records into a file (or sometimes several files). The technical term for such a file is a "Table".

One may be tempted to ask "For our library example, what are the tables?" Good question!

The answer is non-unique: i.e., we have many different acceptable answers! We could have one giant file containing all the books, we could have one file per subject, or have each file correspond to the books published in different years, or...

Sometimes it's useful to do all of these! Why? Because they are the results of queries, and it may be faster to pre-store the results rather than dynamically generate it at runtime.

When we store in a table the results of a query for future use, we call this table a "View".

2.4. Future Directions: Modus Operandi. We have just introduced the components for a database, but there are four aspects the programmer needs to know about: (1) Queries, (2) Data manipulation, (3) Transaction controls, (4) Data definition.

We will begin discussing queries next time.

Custom Stacktrace/Logging Function for Clojure

1. I've been learning Clojure, and sometimes I need to know what my functions are doing. To do this, I usually use some format:

file.clj:<lineno> <message>

Where the message could be notifying me some line is being evaluated, or printing the value of some variable.

1.1. I prefer writing <file-name>:<lineno>, in a nod to grep -n output.

2. I know, this is bad form, inelegant, whatever. But it is useful...and that's why I do it!

2.1. To pre-emptively answer criticisms, I know there are precisely one million and one different logging, debugging, stack-tracing libraries. They are all quite heavy weight and complicated.

For these reasons (too complicated and too heavy-weight), I prefer writing my own.

3. What code can do this? Well, the code I typically use is a couple of simple macros:

(defmacro dbg [x]
  `(do (printf "%s:%s> %s\n"
               ~*source-path* 
               ~(:line (meta &form))
               ~x)
       (flush)))

(defmacro dbg-eval [x]
  `(do (printf "%s:%s> %s \n;=> %s\n"
               ~*source-path*
               ~(:line (meta &form))
               ~(pr-str x)
               ~x)
       (flush)))

3.1. So writing (dbg "foo() is starting"), I can tell when the function foo is being called.

Stylistic Problems

4. This is based on the Java stacktrace/logging format class.methodName(file.java:lineno) <message>, and namely takes advantage using method calling syntax: method().

4.1. It'd be nice if there were a LISP-y way to do likewise, but for now...it works.

Perhaps write (filename.clj:lineno/function-name <message>)? Or some appropriate variation.

What else is wrong with Code Academy?

I had posted a number of missing topics on Code Academy's curriculum last time.

Since then I was asked if I could prepare some material for Ruby or Python. After carefully inspecting the terms of agreement:

You hereby grant us the right to own all right, title and interest (including patent rights, copyright rights, trade secret rights, mask work rights, trademark rights, sui generis database rights and all other rights of any sort throughout the world) to any and all Curriculum Contributions you make to the Website, and you hereby make all assignments necessary to accomplish the foregoing ownership. To the extent allowed by law, you also agree to waive all rights of paternity, integrity, disclosure and withdrawal and any other rights that may be known as or referred to as “moral rights,” “artist’s rights,” “droit moral,” or the like with respect to any Curriculum Contributions you make.

Ah, here's another thing wrong: I do your work and you get the credit for it. Well, not credit, but the "patent rights, copyright rights, trade secret rights, mask work rights, trademark rights, sui generis database rights and all other rights of any sort throughout the world".

I wonder why that doesn't work in school...?

Ruby Koans

If anyone is learning Ruby, and wants to become more familiar with various nuances, go download the Ruby Koans.

There are about two dozen files, each discussing a specific topic. You go through each file, looking for __ segments and replace them with statements which would result in true assertions.

After completing a few, you can run ruby path_to_enlightenment.rb and you get the following prompt:

user:~/koans$ ruby path_to_enlightenment.rb 
AboutNil#test_nil_is_an_object has expanded your awareness.
AboutNil#test_you_dont_get_null_pointer_errors_when_calling_methods_on_nil has 
expanded your awareness.
AboutNil#test_nil_has_a_few_methods_defined_on_it has expanded your awareness.
AboutObjects#test_everything_is_an_object has damaged your karma.

The Master says:
  You have not yet reached enlightenment.
  You are progressing. Excellent. 8 completed.

The answers you seek...
  <"FILL ME IN"> expected but was  <true>.

Please meditate on the following code:
  /home/alex/local/ruby/koans/about_objects.rb:5:in `test_everything_is_an_object'

when you lose, don't lose the lesson
your path thus far [.X________________________________________________] 8/280
user:~/koans$

This really helps understand some of the nuances underpinning Ruby.

Code Academy: What's Missing?

Recently, Code Academy launched with the intention to teach computer programming to "the masses".

I'd like to discuss a short-coming in their material (I won't discuss the method used currently).

Someone in their forums has asked^[deadlink] "What topics need new courses the most?"

[NB: apparently code academy has taken down their forums...I guess they couldn't stand the complaints about their EULA.]

I gave a short answer, but it gave me something to think about: what should a programmer know?

Compounding the problem, the material a working coder should know differs from the material constituting an programmer's education.

I'm just going to rattle off items belonging to both categories...

Programmer's Education

The education includes stuff that may or may not be useful when working.

0. Difference between Expressions and Statements. This important distinction is never taught, so students never figure why foo = function() { ... } differs from function bar() { .... }.

1. Algorithms. This topic is not discussed thus far in any course on Code Academy. Being more specific, I mean CLRS-level stuff, not rudimentary "make a loop, do stuff, blah".

Specifically, algorithms that should be covered:

1. Sorting Algorithms
• Bubblesort, as an example of a bad idea;
• Insertion sort
• Mergesort
• Quicksort
• Heap sort
2. Searching Algorithms
• Linear search
• Binary search
• A* search algorithm (and other graph search algorithms)
• etc.

2. Data Structures. Although discussed a little, the Academy does not discuss linked lists, stacks, queues, binary trees, etc.

Advanced data structures might include, but not limited to, Fibonacci heaps, B-trees, van Emde Boas Trees, etc.

3. Dynamic Programming. Both the "Bottom-Up" and "Top-Down" approaches should be discussed; memoization ought to be covered, etc.

4. Greedy Algorithms. This, I feel, is important for pedagogical purposes...greedy algorithms can fail in practice, but it is important to expand your mind.

5. Algorithm Analysis. I learned this in numerical analysis, where we say "Stop: Why does this algorithm work? How can we make it better?"

This cannot be taught on Code Academy, since it would require a nonlinear framework...i.e., actually taking the user's response and generating questions/problems/exercises based off of it.

Think of it as the Socratic method applied to programming. Code Academy cannot handle the Socratic method (perhaps it would not be too far to suggest they are...sophists?).

But seriously: nurturing curiosity in a way specific to the pupil, that's the mark of a good teacher. Code Academy currently cannot facilitate this.

6. Various Rites of Passage. It seems computer science majors have certain "rites of passage": writing an operating system from scratch (or implementing their own file system, process manager, etc., for *nix); writing their own compiler or interpreter; understanding the networking stack; etc.

These should be included in any coder's education...but they require low level languages to do it (assembly or C). Code Academy cannot handle this, at the present moment...

Working Coder's Knowledge

Perhaps one should consult What every CS majors should know...

1. AJAX. Certainly, the most glaring feature missing is AJAX, which I think any browser can handle (the XMLHttpRequest...does it depend on a library?).

2. Runtime, Parse Time, etc. Code Academy does not mention these distinguished times. Nor is there any discussion of "server-side" vs. "client-side", what the difference is, etc.

3. Debugging Techniques. Really, this is most useful, when you run code and cannot figure out what the problem is. What to do?

Well, insert console.log(...) calls indicating what is happening. "I am doing this", "function blah() has been called", etc.

4. How to Optimize Code. I have just written a JavaScript program. Wonderful. It's slow as death. What do I do to make it faster?

Final Thoughts

Certainly many things are missing, but these are my thoughts on the matter of Code Academy and a programmer's pedagogy.

Pseudocode in HTML

So I've been typing up my own notes in html, by hand (like in the bad old days of the internet), and I've discovered some rather interesting behaviour of CSS2.

My pseudocode conventions have composite data structures resemble C's struct, so for example:

struct myDataStructure {
    // code not shown
}

Comments are done in traditional C method too. How to accomplish this using <span> classes? Well, we first specify a class pseudo for pre denoting our pseudocode:

pre.pseudo { } /* pre's pseudocode class */

Now we will investigate each part of pseudocode we want to implement!

Data Structures

I use Plain Old Data Structures in my pseudocode, often writing <span class="struct">myStructName</span> and formatting it as struct myStructName...

/* write a structure as <span class="struct">myStructName</span> */
pre.pseudo span.struct:before {
    content:"struct ";
    font-weight:bold;
}

Functions

My shorthand for the word "function" is always "fn", so this is the class I created. The pseudocode conventions used is simply function doSomething(...), and to implement this:

pre.pseudo span.fn:before {
    content:"function ";
    font-weight:bold;
}

This is my personal convention, but there is also the C-style convention which I'll discuss.

Alternative Function Pseudocode

Some people like writing their function pseudocode to resemble C's ret-type function-name (arg-list), and it is possible to do this:

/* <span class="function" ret="void">foobar</span>() produces "void foobar()" */
pre.pseudocode span.function:before {
    content:attr(ret) " ";
/*
    font-weight:bold;
*/
}

If you prefer the function's ret-type to be bold, you can uncomment the second line.

For Loops

Our trusty for(...) construct is readily implemented:

/* for-loop formatting to write 
   <span="for">i=1; i<j; i++</span>
   be formatted as
   for(i=1; i<j; i++) */
pre.pseudo span.for:before {
    content:"for (";
    font-style:normal;
}
pre.pseudo span.for:after {
    content:") ";
    font-style:normal;
}

It would be nice if I could write <span class="for>...</span> to produce for(...), but I cannot think of a way to do so.

Comments

I end up using the comment convention // my comment which works well on paper, but due to html resizing...it can be problematical. So here's the CSS implementation of the paper-way, and commented out is the traditional C way /* writing a comment like this */.

/* comments are italicized texts beginning with a double slash // */
pre.pseudo span.comment {
    font-style:italic;
}
pre.pseudo span.comment:before {
    content:"// ";
    font-style:normal;
}
/* alternatively uncomment the following to have C++ like comments */
/*
pre.pseudo span.comment:before {
    content:"/* ";
    font-style:normal;
}
pre.pseudo span.comment:after {
    content:" */";
    font-style:normal;
}
*/

Constants

What about constants? For example, I like referring to the null object as NULL, can we do it?

pre.pseudo span#NULL:before {
    content:"NULL";
}

This would require us to write <span id="NULL"/>. This may seem like a waste of time and energy, but when you decide lowercase "null" looks prettier...you have to change only one line of css to get it!

Flaws

None!

No, I'm just kidding, the only problems I can think of is that these <span> classes work only within the <pre class="pseudo"> environment.

So if you were working in the <code> environment...you'd have trouble!

Of course, my pseudocode listings provided are incomplete (conditionals and while-loops are omitted, among other things), but you get the idea how to take advantage of CSS when "typesetting" pseudocode in html.

Lectures on Algorithms

Although I'm devoted to Knuth, CLRS' Introduction to Algorithms is a good read.

Leiserson (the "L" in CLRS) has his lectures [youtube.com] free online. Caution: skip the first 16 or 17 minutes of the first lecture, it's administrative stuff.

The course website is available [mit.edu] thanks to MIT's OpenCourseWare.

The pseudocode appears a little foreign for neophytes (e.g. writing foo←bar instead of foo=bar for assignment). The assignment pseudocode operator actually remains the same across the board...at least, among theoretical computer scientists.

CLRS fixes their pseudocode conventions in their third edition, however; which was published after these lectures were Youtubed.

A personal quibble: array indices for CLRS begin at 1. This annoys me. But it is a misdemeanor, not a felony.

Also, if you are wondering about the difference between big-O notation and big-Theta notation: suppose some algorithm for a computer were Θ(n), then it is O(n). But not all O(n) algorithms are Θ(n) --- there are some rare instances when this is true.

So Θ(n) gives a more strict criteria than O(n), but in practice it's "ok" to mix up notations (since we usually examine worst-case scenarios anyways!).

Addendum: when is it not ok to make this mistake that [f(n)=Θ(g(n))]==[f(n)=O(g(n))] for some f(n), g(n)?

When f(n)<g(n).

However, if g(n)<f(n)<c*g(n) for every n and for some fixed positive integer c, then [f(n)=Θ(g(n))]==[f(n)=O(g(n))]

So if we study the worst case situations, it's okay to mix up big-O and big-Θ notation. The difference occurs when we study the best-case behaviour (which Leiserson calls "bogus"), and possibly when we study the average-case behaviour.

Punch-line: the big-Θ convention is "stronger" than (i.e., implies) the big-O notation, but big-O notation does not imply big-Θ in general.

For studying worst-case behaviour, they are equivalent.

When studying average-case behaviour, we do not know if they are equivalent (it needs to be proven for each algorithm).

When studying best-case behaviour, you are committing fraud: best-case scenarios are bogus.

Ruby on Rails Resources for Beginners

I'll give my overview of "Ruby on Rails" then list off resources for beginners.

Caution: I'm a student, like anyone else, so do not take my notes as the Gospel.

Overview of Ruby on Rails

So the three languages of the internet are: Ruby, Python, and JavaScript. But if you know Ruby on Rails, you will always have a job.

Ruby on Rails is peculiar to get started with (well, for me anyways). What's the basic idea?

Most people end up introducing Rails with some jargon about "MVC" (Model-View-Controller), Don't Repeat Yourself, Convention over Configuration...and from those three slogans alone, you should be able to program Rails applications.

Unfortunately, I am not that smart. So these are some notes to myself as far as what some of these slogans mean!

Imagine a car. People are concerned about how it looks, what color it is, etc. (the "View"). Others are concerned with what's going on under the hood (the "model"), and others worry about how the driver interfaces with the car and the car responds (the "controller").

For us, the Model usually is the data structures used. This is some flavor of ActiveRecord (the API is available online [rubyonrails.org] for the "Base" class).

Great, now what's an "Active Record" and why should anyone give a damn? It's a way of describing the Object-relation mapping (ORM), i.e., encode a SQL database inside a Ruby object. For more about this, see Active Record [rubyonrails.org] for more details.

Lets be clear about this: the model is specified by active records. That's why we care. Got it? Good.

The view is much easier to understand: it's just a chunk of html. That's what the user views.

The controller is more-or-less taken care of, all thanks to the rails library. This is my understanding, at least. I may be completely wrong...

Resources

Several Screencasts [rubonrails.org] are available, and they are quite decent introductions!

You should first Try Ruby before doing rails; since rails is a ruby library...

The best walkthrough describing rails appears in a mere ten step program [tutsplus.com], and I must agree this is the best approach.

I found this YouTube Video (showing how to make a blog under ten minutes) quite enlightening, perhaps you might like it as well?

JavaScript Object Oriented Technique #0 Common Object Methods

Whenever we define a JavaScript class, there are three methods we should immediately define.

toString()

We should be able to return a string representation useful enough for debugging purposes.

We might want to consider adding a static parse() method to our class, parsing a string output from toString() back to object form.

The usual conventions, for objects, is to surround the string by brackets [...] and describe the object's properties within it.

Polygon.prototype.toString = function() {
    return "[Polygon with perimeter "+this.perimeter+", with area "
        + this.area+", centered at ("+this.x+", "+this.y+").]";
}

valueOf()

Typically, we write an valueOf() method to give us a number form of our object.

The textbook example is, since JavaScript number objects are supposedly "real" numbers, then for a complex number object the valueOf() should return the real part. Why? Because it lets us do the following:

var foo = new Complex(1,2);
var bar = new Complex(3,4);
var spam = Complex.sum(foo,bar); // spam is the complex number (4,6)
var eggs = foo + bar; // eggs is the number 4

Also note that the valueOf() method is called when concatenating a string with your object. So continuing from the previous example:

console.log("foo = " + foo); // uses valueOf(), displays "foo = 1"
console.log("foo = " + foo.toString()); // displays "foo = {1,2}"

You have been warned!

Comparison Methods

It's useful to sort objects, and creating comparison methods allows us to do this.

The first one we should consider is equals(), which tests if two objects are equal in some sense. Usually it's if the properties are the same.

Next we need to test for inequalities. We implement a compareTo() method, which should behave as follows:

foo.compareTo(bar)>0; // foo > bar
foo.compareTo(bar)==0; // foo == bar
foo.compareTo(bar)<0; // foo < bar

I suppose the best implementation might have the following skeleton:

MyClass.prototype.compareTo = function(that) {
    if(this.equals(that))
    {
        return 0;
    }
    // else return something like "this.valueOf() - that.valueOf()"
}

Again, it depends on the circumstances...

JavaScript Object Class

JavaScript Object Oriented Framework

JavaScript is fairly quirky (you can learn it at the code academy). It is object oriented, but its a sort of duck typed version.

Every object is really an associative array, so writing foo.bar is the same as foo["bar"]. They are synonymous.

Curiously enough, JavaScript's object oriented framework has a base class called Object. Lets discuss its properties.

Object Properties

What properties does a generic object have?

1. It keeps track of its own constructor, for example:

var foo = new Array();
console.log(foo.constructor === Array); // prints "true"

The instanceof operator checks the value of the constructor property.

2. We can also convert an object to a string by a toString() method.

This does the obvious thing: returns a string representation of the object.

(Actually, if you're a mathematician, you might want to make a toTeX() method...)

3. What about converting an object to a primitive type (well, a primitive type except a string)? We have the valueOf() method.

4. Since we're duck typing objects, we might want to check the properties an object has. We can do this with the hasOwnProperty() method.

It's a function that takes a string, for example "toString", then checks to see if our object has it or not. If our beloved object has it, then foo.hasOwnProperty("toString") returns true.

5. The object base class has a method testing a given property if it's enumerable or not. In other words: it tests if we can use it in a loop construction. This method is called propertyIsEnumerable(). For example:

var foo = { bar:0 };
foo.propertyIsEnumerable("x"); // returns true
foo.propertyIsEnumerable("spam"); // returns false, since foo.spam is undefined
foo.propertyIsEnumerable("valueOf"); //returns false for inherited properties

6. The last method I'll discuss is kind of tricky. The isPrototypeOf() method is similar to the instanceof operator discussed above (see this discussion [StackExchange.com] for more details).

Object.prototype.instanceOf = function( iface )
{
    return iface.prototype.isPrototypeOf( this );
};

Addendum: to find all the properties of the Object class on YOUR system, run the following in your browser's javascript console (however you find that...on Mozilla, it's in the "Tools" part of the browser):

function getAllProperties(object){
    return Object.getOwnPropertyNames(object);
}
console.log(getAllProperties(Object));

/* prints out
[ 'prototype',
  'getPrototypeOf',
  'getOwnPropertyDescriptor',
  'keys',
  'defineProperty',
  'defineProperties',
  'create',
  'getOwnPropertyNames',
  'isExtensible',
  'preventExtensions',
  'freeze',
  'isFrozen',
  'seal',
  'isSealed',
  'length',
  'name',
  'arguments',
  'caller' ] */

Metanotes on C# with Ubuntu Linux

This is a "note-to-self" type blogpost, but some other people might find it useful.

How to install the C# compiler on Ubuntu (Linux)? There are several possibilities.

The first: use Mono. This is an open-source version of Microsoft's .NET framework.

Compiling things on the command line is simple, merely use gmcs when calling the compiler.

There are some idiosyncrasies unique to Mono, however. For example, you'll need to install (for Ubuntu 12.04) the gtk-sharp2 package for GUI programming.

There are difficulties with this (I never got it to work!). Consider the following program:

/* begin hello.cs */
using Gtk;
using System;
 
class Hello {
 
        static void Main()
        {
                Application.Init ();
 
                Window window = new Window ("helloworld");
                window.Show();
 
                Application.Run ();
 
        }
}
/* end hello.cs */

There is an error:

$ gmcs hello.cs -pkg:gtk-sharp-2.0
alex@tomato:~/app/cv$ ./hello.exe
Missing method System.Type::op_Inequality(Type,Type) in assembly /usr/lib/mono/2
.0/mscorlib.dll, referenced in assembly /usr/lib/mono/gac/gtk-sharp/2.12.0.0__35
e10195dab3c99f/gtk-sharp.dll

Unhandled Exception: System.MissingMethodException: Method not found: 'System.Ty
pe.op_Inequality'.
  at Gtk.Window..ctor (System.String title) [0x00000] in :0 
  at Hello.Main () [0x00000] in :0 
[ERROR] FATAL UNHANDLED EXCEPTION: System.MissingMethodException: Method not fou
nd: 'System.Type.op_Inequality'.
  at Gtk.Window..ctor (System.String title) [0x00000] in :0 
  at Hello.Main () [0x00000] in :0

Quite tragic, yes yes. Aside from this, very basic C# program appears to work on Ubuntu.

Next time I'll examine how Mono handles C# programs involving LINQ [wikipedia.org].

OpenCL (Part 1)

So suppose you had a fancy multicore processor and a fancy GPU...what can you do with them? How to take advantage of the parallelism?

It seems OpenCL and friends (e.g., CUDA) deal with this.

You've got kernels which intuitively is like a C function, but serves as the basic unit of executable code. It can be either data-parallel or task-parallel. In any event, kernels are parallel.

The Program Object then consists of kernels and other functions (analogous to a dynamic library).

More precisely, we have application queue kernel execution instances, which queues kernel objects in order. But it may execute kernel objects either in-order or out-of-order.

Since we are working with a graphics chip, we can process vectors, images, or volumes. These are 1-dimensional, 2-dimensional, and 3-dimensional domains, respectively.

Each independent element of execution in an N-dimensional domain is called a work-item; the N-dimensional domain defines the total number of work-items that execute in parallel.

Parallelization demands concern for synchronization, viz. synchronizing either data [i.e., memory] or execution.

Although OpenCL does not permit global synchronization, we can have "local" synchronization. What does this mean? Well, consider some image processing problem. We can make the image into a "quilt" of "patches" where each patch is, e.g., 128×128 pixels...this "patch" is called a workgroup, and we may synchronize within each workgroup.

Note we must be clear if we synchronize memory or execution.

We cannot synchronize between different workgroups.

We use "barriers" to synchronize execution; and "memory fences" to synchronize memory accesses.

Sadly, alas, this may require using multipass algorithms for global synchronization (e.g., between kernels). Alas, alas, multipass!

So How to Program in OpenCL?

Well, there are five things we work with: cl_device_id, cl_kernel, cl_program, cl_command_queue, and cl_context.

We already discussed kernels and programs, which are like functions (kernel) and a collection of functions (program).

So what's the other guys...bonus parts?

No! The Host is your computer, and it's connected to one or more Devices (e.g., CPU, GPU, DSP, etc.). A device is anything providing processing power.

The Device receives kernels from the host. A cl_device_id represents a device.

We have two things left: the command queue, and the context.

The device receives its kernels through a Command Queue.

OpenCL contexts enables devices to receive kernels and transfer data.

Further Reading

1. A Gentle Introduction to OpenCL, Dr Dobbs Journal.
2. OpenCL Presentation [pdf]
3. OpenCL by Example [ucdavis.edu] discusses...OpenCL...by...example...
4. Getting started with OpenCL and GPU computing

Lectures on the Metacircular Evaluator

I have been struggling with the notion of a "metacircular evaluator" for a while. Then I stumbled upon the MIT lectures for it.

The lectures are quite beautiful, and should be watched!

MIT's 6.001 Lecture 7A YouTube clip

MIT's 6.001 Lecture 7B YouTube clip

Bear in mind, these "clips" are roughly an hour long...but they will solve all problems involving the metacircular beast!

Learning Lua

So I have learned about LuaTeX, which basically implements TeX in Lua and thus enables Lua scripting inside a TeX document. Thus I want to learn Lua!

Hello World!

I installed the basic lua50 package on ubuntu, so let me write my first program.

-- begin hello.lua

-- This is a comment

print("Goodbye, Cruel World!")

-- end hello.lua

One runs it on the *nix command line by $ lua hello.lua

However, we can use write(...) instead of print(...), the difference is that print() automatically adds a new line.

Getting User Input

We can ask for user's information:

-- begin name.lua 

io.write("What's your name? ")
name = io.read()
print("Why, '"..name.."' is a stupid name!")

-- end name.lua

We start using the io module's functions. We need to indicate this by calling io.read() and io.write()

Unique Aspects of Lua

Lua is unique in that everything is-a table. That's how you implement classes, data structures, and so on. (Think how LISP has everything is-a list.)

Even operator overloading is handled through tables...well, "metatables".

There are many examples of advanced table usage on Lua's wiki. So next time, we'll start considering examples involving tables.

CWEB, Part 2: Hello World returns!

Continuing from our previous post on CWEB, we will take the time honored example:
lets consider a more complicated "Hello World!" Program.

\def\title{Hello World, Reloaded}

@*A Simple Example.
This is a trivial example of a \.{CWEB} program.
It is, of course, the classic "hello, world"
program we all know and love:

@c
@<Header files needed by the program@>@;
@#
main(void)
{
   @<Print the message |"hello, world"|@>@;
}

@ Naturally, we use |printf| to do the dirty work:

@<Print the message |"Hello, World!"|@>=
printf("Hello, World!\n");

@ The prototype for |printf| is in the standard
header, \.{<stdio.h>}.

@<Header files needed by the program@>=
#include <stdio.h>

@*Index.

This is perhaps the simplest example demonstrating how to use chunk identifiers (those @<...@> things) in CWEB.

Note that \.{CWEB} typesets CWEB using typewriter font.

Also note that we don't have to define a chunk before we use it. That's what we did in this example, all the chunks were defined after they were used.

What are those @; symbols used for? Well, they're for formatting, and they don't do anything other than prettyprint the TeX output.

CWEB

It turns out there is some interesting stuff to do with CWEB.

First off, you program in chunks/modules called "sections". Each section contains either code or documentation. Each section begins with @.

The skeleton of a CWEB program might look like:

% this is a comment
\def\title{My awesome program!!!!} % this sets the title
\datethis % this sets the date
@*Introduction. % create the introduction section
This program will solve all my problems.

[Code not shown]

@*Index.

The line of code @*Introduction. will create a section with a title, it would look like "1. Introduction. ". It's TeX equivalent would be \medbreak\noindent{\bf 1.\quad Introduction.\quad}, and yes those \quad spacings are correct.

The first line of code puts a time stamp between the first section and the title.

The last line produces an index of all the variables.

The Code

How do we actually write code in CWEB?

We can use @c to start writing code, just as @ is used to write documentation.

And just as we had @*[title]., we have something analogous for code @<[title]>

However, the first time we use @<section name>, we are defining it. When we use it later on, we are calling it. Note the difference!

Comments

A simple comment is formatted by @q ... and it is not printed to the TeX file.

Write to Different Files

If one writes @(foo>, then the contents of the section (onwards?) is written to the file foo.

Macro Definitions

Instead of that ungodly #define ..., we write @d ... to do the same thing.

Some example code (from string.w):

@s string int
@s Xstring int @q -- a hint for the typesetter -- @>
@(xstring.h@>=
#ifndef XSTRING_H
#define XSTRING_H // prevent multiple inclusions
@#
class Xstring {
 @<private |Xstring| members@>@;
public:@/
 @<public |Xstring| members@>@;
};
@#
#endif

What does the @# line do? Well, it forces a line break, and that's all.

Similarly, the @/ line forces CWEAVE to put a line break in the C code.

But what do those @>= lines mean? We are initializing and declaring an identifier for a section. For us, that is xstring.h, and since we have prefaced it with @( it means we are working with the code in a separate file.

Observe that @<public |Xstring| members@>@; simply loads the code defined in section public |Xstring| members since the section ended without an equal sign, i.e. @> instead of >=.

More notes to come, but one might also be interested in Knuth's straighten.w program for computing irreps of the symmetric group.

Addendum

Here is the obligatory "Hello World!" type program:

@*Introduction.
This is a simple ``Hello World!'' program using literate
programming. I hope it works! (It does work!)

@c
#include <stdio.h>

int main(int argc, char** argv)
{
 printf("Hello world! I am literate programming?\n");
 return 1;
}

@*Index.

Learning Assembly Language, Part 2: Little Man Computer

Last time we discussed the CARDIAC assembly language. We did everything by hand. It was also incredibly limited.

This time, we will introduce a more comprehensive assembly language which is also done completely by hand.

The architecture is known as the "Little Man Computer", it too is in decimal (base-10).

The little man computer is a model designed to assist in the understanding of the fetch/execute cycle, through the visualization of elements of the computer architecture that would normally remain hidden.

The story is the suppose we have a "little man" trapped in a room with 100 mailboxes.

We also have two mailboxes at the other end labelled INBOX and OUTBOX which are used for receiving and outputting data to the outside world.

In the center of the room, there is a work area containing a simple two function (addition and subtraction) calculator known as the Accumulator and a reset-able counter known as the Program Counter.

Architecture Specifications

So, we have 100 memory cells (the mailboxes) each can contain 3-digit numbers from -999 to +999.

The basic algorithm for the instruction cycle is given by:

1. check the Program Counter for the mailbox number that contains a program instruction
2. fetch the instruction from the mailbox with that number
3. Increment the Program Counter (so that it contains the mailbox number of the next instruction)
4. decode the instruction (includes finding the mailbox number for the data it will work on)
5. fetch the data from the mailbox with the number found in the previous step
6. execute the instruction
7. store the new data in the mailbox from which the old data was retrieved
8. Repeat the cycle or halt

Now what are the instructions?

As with the CARDIAC system, an instruction looks like OAA where the first digit specifies the opcode (the operation to be carried out) and AA contain the address which we need to work with.

There are roughly 10 operations for the little man computer, similar to the CARDIAC system.

In general, any assembly language will have a similar grouping of instructions into several families:

1. Arithmetic: arithmetic instructions may operate on all registers or on just a special register (e.g. accumulator).
2. Control: stuff like "copy contents of register 1 into register 2", loading to and storing from the accumulator, "jumps" like "goto", etc.
3. Register-addressing method: these are indirectly loading values into registers, very important for theoretical computer scientists...not so important a distinction for the working coder.
4. Input-output: usually present in all models.

Now, let us list off the instructions for the little man computer (taken from wikipedia).

Table of Little Man Instructions

Numeric code	Mnemonic code	Instruction	Description
1xx	ADD	ADD	Add the value stored in mailbox xx to whatever value is currently on the accumulator (calculator). Note: the contents of the mailbox are not changed, and the actions of the accumulator (calculator) are not defined for add instructions that cause sums larger than 3 digits.
2xx	SUB	SUBTRACT	Subtract the value stored in mailbox xx from whatever value is currently on the accumulator (calculator). Note: the contents of the mailbox are not changed, and the actions of the accumulator are not defined for subtract instructions that cause negative results - however, a negative flag will be set so that 8xx (BRP) can be used properly.
3xx	STA	STORE	Store the contents of the accumulator in mailbox xx (destructive). Note: the contents of the accumulator (calculator) are not changed (non-destructive), but contents of mailbox are replaced regardless of what was in there (destructive)
5xx	LDA	LOAD	Load the value from mailbox xx (non-destructive) and enter it in the accumulator (destructive).
6xx	BRA	BRANCH (unconditional)	Set the program counter to the given address (value xx). That is, value xx will be the next instruction executed.
7xx	BRZ	BRANCH IF ZERO (conditional)	If the accumulator (calculator) contains the value 000, set the program counter to the value xx. Otherwise, do nothing. Note: since the program is stored in memory, data and program instructions all have the same address/location format.
8xx	BRP	BRANCH IF POSITIVE (conditional)	If the accumulator (calculator) is 0 or positive, set the program counter to the value xx. Otherwise, do nothing. Note: since the program is stored in memory, data and program instructions all have the same address/location format.
901	INP	INPUT	Go to the INBOX, fetch the value from the user, and put it in the accumulator (calculator) Note: this will overwrite whatever value was in the accumulator (destructive)
902	OUT	OUTPUT	Copy the value from the accumulator (calculator) to the OUTBOX. Note: the contents of the accumulator are not changed (non-destructive).
000	HLT	HALT	Stop working.
	DAT	DATA	This is an assembler instruction which simply loads the value into the next available mailbox. DAT can also be used in conjunction with labels to declare variables. For example, DAT 984 will store the value 984 into a mailbox.

Mnemonics

In the Little man computer, there are these exotic things called "mnemonics". It works sort of like macros in C/C++...but not really.

For example, we could refer to data locations using mnenomics:

INP
STA FIRST 
INP
STA SECOND 
LDA FIRST 
SUB SECOND
OUT
HLT
FIRST DAT
SECOND DAT

The STA FIRST uses FIRST as-a mnenomic, and it is defined as-a DAT.

In short, a mnemonic is a short sequence of characters (e.g. FIRST or SECOND) that are an alias for an opcode (e.g. DAT).

Labels

This is the last innovative feature which differentiates Little Man from CARDIAC. We use labels to indicate portions of our program...you could think of this sort of like defining procedures.

Well, to be more precise, a label can be used to identify a particular instruction as a target for a BRANCH instruction ("where the procedure begins").

We can do more! We can also have "variables", that is associate data to a sequence of characters. We have seen this with the FIRST and SECOND example code.

An example program:

     INP
LOOP SUB ONE  // This address will be called LOOP, 
              // Subtract the value stored at ONE
     OUT
     BRZ QUIT // If we are at 0, then jump to the location QUIT
     BRA LOOP // We are not at 0, go back to the start of LOOP
QUIT HLT
ONE  DAT 1    // Put the value 1 in this mailbox,
              // and call it ONE (variable declaration)

Now what are some exercises?

Exercises

1. Write a program that finds the first 100 prime numbers.
2. Modify this program to take a positive number from the user n, and find the first n prime numbers.
3. Implement a mul procedure to multiply integers together.
4. Write up code to implement a floating point arithmetic division procedure (see Donald Knuth's Art of Computer Programming vol. 2 for details).
5. Write a procedure to write a given number in a given base (e.g. write 720 in base 3).

Future Directions

Maybe next time I will begin discussing the MIXAL, the MIX assembly language designed by Donald Knuth.

Studying FreeBSD, Part 0: Preparatory Materials

So, I am disappointed with Ubuntu's Unity interface, and immediate switch to Gnome 3. Out of disgust, I am switching to FreeBSD.

However, I would like to study the source code to be prepared for anything! How do this? I outline my thoughts in this post...

In the Beginning, there was Unix 6 (And it WAS Good!)

So FreeBSD traces its roots back to V6. Today, there is a modern version of V6 for the x86 machine: xv6 [mit.edu].

Some may find Lions' Commentary [lemis.com] to be useful as well.

This is a little bit dated, but fortunately the xv6 team has decent documentation [mit.edu] which explains a lot regarding operating systems.

One may be tempted to refer to Maurice J. Bach's excellent text Design and Implementation of the Unix System, but resist this urge! Bach's text discusses UNIX System V (1986 version), whereas V6 is a decade older.

FreeBSD derives from BSD-lite, which is in turn based on V6 not SysV!

On the second day, there was the SHELL (and it was GOOD!)

FreeBSD comes with the Almquist Shell, and the C-shell.

Should we worry about the C-shell, which is a preloaded shell used in FreeBSD? There are 10 reasons not to use the C-shell [grymoire.com]:

1. The Ad Hoc Parser
2. Multiple-line quoting difficult
3. Quoting can be confusing and inconsistent
4. If/while/foreach/read cannot use redirection
5. Getting input a line at a time
6. Aliases are line oriented
7. Limited file I/O redirection
8. Poor management of signals and sub-processes
9. Fewer ways to test for missing variables
10. Inconsistent use of variables and commands.

So...perhaps it is best to use something like ASH. This is the default shell for root, and it is a clone of the original Bourne shell.

The positive aspects to it: it's minimal, lightweight, doesn't consume a lot of memory.

The negative aspects to it: because it's so Spartan, it has no bells or whistles to speak of.

Perhaps I will eventually write up something on advanced ASH scripting one day...

Scheme course

I found the course page for MIT's 6.001 back in the day when they used SICP, like real programmers.

Well, here's the homepage [mit.edu] and particularly interesting are the quizzes [mit.edu].

The projects are worth looking at too...I may end up getting distracted doing one or two!

Learning Assembly Language

Underlying Pedagogical Philosophy.
Recently in the New York Times, there was an article [nytimes.com] talking about the Waldorf School system which discourages the use of technology when teaching. I am sympathetic to this point of view, and believe (as a mathematician) that most subjects should be taught without technology.

What about computer science? Yes, to a degree, I believe so. What about learning assembly language...?

CARDIAC

The CARDboard Illustrative Aid to Computation (CARDIAC for short) was initially created at Bell labs to help understand programming in assembly language. It was also done "by hand": you are the computer!

It is done in base 10, and the computer has 100 memory cells. Each cell can hold signed numbers from ±0 to ±999.

You can download pdfs to print out and start computing here [kylem.net].

Each 3-digit number represents some instruction. It should be read as OAA where O is the digit referring to the instruction to carry out, and AA refers to the address of the memory cell involved.

Just some quick terminology, an "Accumulator" is a special memory cell (a CPU register, actually) where intermediate results of a calculation are held.

To keep track of which cell we are computing, one uses a "Program Counter". Originally it was a butterfly pin in the Bell Labs CARDIAC kit, but one could use anything.

Now, let us run quickly through the opcodes:

0	INP	Input	take a number from the input card and put it in a specified memory cell.
1	CLA	Clear and add	clear the accumulator and add the contents of a memory cell to the accumulator.
2	ADD	Add	add the contents of a memory cell to the accumulator.
3	TAC	Test accumulator contents	performs a sign test on the contents of the accumulator.
4	SFT	Shift	shifts the accumulator x places left, then y places right, where x is the upper address digit and y is the lower.
5	OUT	Output	take a number from the specified memory cell and write it on the output card.
6	STO	Store	copy the contents of the accumulator into a specified memory cell.
7	SUB	Subtract	subtract the contents of a specified memory cell from the accumulator.
8	JMP	Jump	jump to a specified memory cell. The current cell number is written in cell 99. This allows for one level of subroutines.
9xx	HRS	Halt and reset	halt the machine and move the program counter to xx.

Note that cell 0 was "read only memory" (I guess one could write in pen to indicate that it won't ever change) and was 001.

Basic Algorithm

The basic algorithm to using the CARDIAC system is as follows:

1. Begin with a clean output card, set the accumulator to 0.
2. Set the program counter to memory cell 0.
3. Read the opcode and the address from the cell.
4. Look up the opcode, perform the operation using the address given.
5. If the opcode is jump, set the current address to the address given; otherwise increment the program counter by 1 and go back to step 3.

Some Exercises

1. Consider the numbers 1, 1+2, 1+2+3, etc. These are triangular numbers. Write a program that prints out the first 100 triangular numbers.
2. How can we implement a loop in CARDIAC?
3. Implement Euclid's algorithm in CARDIAC.
4. Implement the Sieve of Eratosthenes in CARDIAC.

Final Remarks

This gives us some idea of how assembly language works, but it is also limited. Perhaps next time (if there is a next time!) we will look into the Littleman computer architecture.