DocBook Sigplan Stylesheets

I am happy to announce that the DocBook Sigplan stylesheets are nearly feature complete and ready for use by a wider audience.

DocBook-Sigplan Repository on GitHub

Many conferences utilize the ACM SigPlan Proceedings style of article, but unfortunately, those who wish to author articles in a semantic, well structured manner have had almost no options. The default and de facto standard format comes from a LaTeX class file, which defines through implementation the specific style desired. An additional Word document exists which allows one to utilize Word for writing these articles, but this seems more a step backwards than forwards.

DocBook-Sigplan attempts to alleviate this need by delivering an open source, compatible stylesheet for processing DocBook v5 documents into SigPlan style through FOP using FO-XSL. Users of this style sheet have access to the full range of DocBook’s benefits, including rigorous semantic markup and clearer solutions for common article writing needs, without as much copy and paste involved in the authoring of specific elements of your article. It uses a completely open-source stack for this, and also allows better automatic processing and output formats than LaTeX.

Information on writing and using DocBook can be found at the DocBook website.

Please support my work through GitTip.

My Top Firearms Wish List

Here’s my list of firearms related goodies I wish I had. :-)

  • Trigger job for S&W 686
  • HiViz or Night Sights (I can’t decide which one) for the same
  • S&W J-Frame Model 360PD
  • S&W Model GOVERNOR
  • Beretta Px4 Storm Compact or Full-sized in .40 S&W

I mean, does it get any better than that?

APL a Day #5: Indexing into Arrays

By now, clearly a shape and vector of values precisely determines an array. All APL functions operate over arrays; they describe new arrays in terms of its arguments. What about describing a sub-array of another array? Indexing provides a means of identifying specific elements of an array. Some people might call this addressing elements of the array.

Given an array A with shape ⍴A and elements ,A, a valid index I into array A is a vector whose length matches ⍴A, stated formally as follows:

⍴I ←→ ⍴⍴A ⍝ Shape of Index matches rank of A

An index describes the location of an element when arranged according to the shape. That is, an index encodes the position of an element according to the shape. Consider a matrix of shape 5 3 filled with the first 15 natural numbers:

    5 3⍴⍳15
 0  1  2
 3  4  5
 6  7  8
 9 10 11
12 13 14
    ⍳15
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Notice that the elements of ⍳15 correspond to their position in the element vector of 5 3⍴⍳15, expressed notationally as ⍳15 ←→ ,5 3⍴⍳15. It feels awkwards to refer to the element in the third row and second column of a matrix as the 7th element of the matrix. True, the element in row 3 and column 2 does indeed correspond to the 7th element of the array as counted by its ravel (recall that the term ravel means the element vector), but no one wishes to do the necessary mental computation to make this happen. A key advantage to multi-dimensional arrays begins with the ability to reference elements relative to their arrangement according to shape, rather than positionally in the ravel.

Instead of referring to the 7th element in a matrix of shape 5 3, the index 2 1 means the same thing. All indexing and counting in Co-dfns and this blog begins with zero, rather than 1. (A long standing debate concerning the origin of counting, be it 1 or 0, continues to gently ruffle programmer feathers within the APL community, but zero-based indexing holds the crown for most modern computer science concerns, and this series uses an index origin of 0.) Thus, the index 2 1 refers to the element at the third row and second column of the matrix.

All elements of an index must fall within the range described by the corresponding dimension of the shape of the array indexed. That is, the index 2 1 means something for an array of shape 5 3, but refers to a non-existent element in an array of shape 2 2. Such invalid indexes trigger INDEX ERROR in the APL interpreter. The following equivalence formalizes the requirement for elements of an index to fall within valid ranges, where ∧/ means “for all”:

∧/(0<I)∧I<⍴A ⍝ Index between 0 and shape of array indexed

Certain APL functions allow an array and valid index into that array to describe the corresponding element indexed in the array. Writing I⌷A gives the scalar element of A indexed by I. To understand this relationship, the following picture helps:

┌→─────────┬─────────────┐
│┌→─┬──┬──┐│┌→──┬───┬───┐│
│↓0 │1 │2 ││↓0 0│0 1│0 2││
│├~→┼~→┼~→┤│├~─→┼~─→┼~─→┤│
││3 │4 │5 │││1 0│1 1│1 2││
│├~→┼~→┼~→┤│├~─→┼~─→┼~─→┤│
││6 │7 │8 │││2 0│2 1│2 2││
│├~→┼~→┼~→┤│├~─→┼~─→┼~─→┤│
││9 │10│11│││3 0│3 1│3 2││
│├~→┼~→┼~→┤│├~─→┼~─→┼~─→┤│
││12│13│14│││4 0│4 1│4 2││
│└~→┴~→┴~→┘↓└~─→┴~─→┴~─→┘↓
└─────────→┴────────────→┘

The array above shows the correspondence between positions in the element vector and the indexes that refer to these positions in a 5 3 matrix. See how the elements are arranged by position in row-major order on the left. Notice the row-major order evident in the progression of the indexes on the right. The upper left hand corner of the matrix is 0 0 while the lower right hand corner will always be (⍴A)-1. In this case, the shape is 5 3 so 4 2≡(⍴A)-1.

The power to generate the right hand side of the above picture rests firmly in your hands already. While ⍳N serves as a nice method for generating natural numbers, the monadic function actually accepts any valid shape as an argument. Given a shape S, the expression ⍳S describes an array of shape S whose elements are the indexes corresponding to the element position. Thus, the above right hand side is a picture displayed by the APL session for ⍳5 3:

    ⍳5 3
┌→──┬───┬───┐
↓0 0│0 1│0 2│
├~─→┼~─→┼~─→┤
│1 0│1 1│1 2│
├~─→┼~─→┼~─→┤
│2 0│2 1│2 2│
├~─→┼~─→┼~─→┤
│3 0│3 1│3 2│
├~─→┼~─→┼~─→┤
│4 0│4 1│4 2│
└~─→┴~─→┴~─→┘

So, indexing into the array 5 3⍴⍳15 using 2 1 should give 7:

    2 1⌷5 3⍴⍳15
7

You now know how to reference any element in an array based on that element’s index into the array. Furthermore, a simple exploration of this reveals how to extract the Nth element from any array:

    N⌷,A ⍝ The Nth element of array A

In the above example, it holds that 7⌷,5 3⍴⍳15 ←→ 2 1⌷5 3⍴⍳15. Clearly, now, the expression ⍳S degenerates into ⍳N when S describes a vector. A vector’s indexes are natural numbers.

The next session with further explore the interesting relationship between an index and the element corresponding to it.

Please support my work via GitTip.

Slackware DVD Boot Problems on Macbook

The other day a friend of mine wanted to see if I could install Slackware64 14.1 on a MacBook that he received. It was an older model, and the previous owner had wiped out the disks trying to get various Linuxen installed.

My friend already had a freshly minted copy of the DVD ready for us, but when we tried to boot it up, all we say was this message:

1.

2. 

    Select CD-ROM Boot Type:

Of course, it didn’t help that the keyboard did not respond. Looking around, I noticed some advice on fixing this in various forums, but it didn’t quite work, because none of these options was available in building my own custom ISO image. I had also considered getting reFind installed on the system, but I realized that installing reFind on a MacBook without Mac OS X installed is really hard. :-)

After some thinking and pondering about the message, I stared at the command to build a Slackware ISO for a while. It hit me then that the normal command used to build the ISO creates two boot paths, one for traditional systems, and one for EFI. Here’s the normal boot command:

mkisofs -o /tmp/slackware-dvd.iso \
  -R -J -A "Slackware Install" \
  -hide-rr-moved \
  -v -d -N \
  -no-emul-boot -boot-load-size 4 -boot-info-table \
  -sort isolinux/iso.sort \
  -b isolinux/isolinux.bin \
  -c isolinux/isolinux.boot \
  -eltorito-alt-boot -no-emul-boot -eltorito-platform 0xEF \
  -eltorito-boot isolinux/efiboot.img \
  -m 'source' \
  -V "SlackDVD" .

The eltorito lines here cause the problem. Specifically, the MacBook doesn’t seem to be able to figure out how to boot from the CD given two different options.

The solution to this problem is easy: remove the alternative boot images and boot using the traditional methods. In that case, the new command to build the ISO looks like this:

mkisofs -o /tmp/slackware-dvd.iso \
  -R -J -A "Slackware Install" \
  -hide-rr-moved \
  -v -d -N \
  -no-emul-boot -boot-load-size 4 -boot-info-table \
  -sort isolinux/iso.sort \
  -b isolinux/isolinux.bin \
  -c isolinux/isolinux.boot \
  -m 'source' \
  -V "SlackDVD" .

After using this new ISO, the MacBook builds and boots and installs without a hitch. Happy slacking!

Please consider supporting my work through GitTip.

APL a Day #4: Arrays have elements

An array that only describes a box which may contain elements, but that does not contain any elements, does not mean much. While shapes help to clarify the APL language, when doing any work, they really only describe how to arrange the elements of an array. The monadic ravel function (written as the comma ,) describes a vector of all the elements of an array taken from the array in row major order. Thus, the following property holds:

A ←→ (⍴A)⍴,A ⍝ A is the reshape of the elements of A with the
             ⍝ shape of A.

That is, the shape of an array, together with its elements, fully describes an array.

Given the ravel of an array, how does the shape of an array describe the arrangement of those elements? The official computer science term for this is row major order. To understand how row major order works, consider a matrix, that is, an array of two dimensions. Supposing that the matrix has no non-zero dimensions, the shape of that matrix will be some positive integers N M. Since APL uses row major order, the N is said to be the number of rows in the matrix, while M is said to be the number of columns. Notice that the “most major” dimension appears first in the vector N M; the dimensions of an array are arranged in the array’s shape from most to least major. That is, the first element in the shape is the most major dimension, the second element the second most major, and so forth.

The monadic function “Index” () helps to illustrate these concepts. The notation ⍳N where N is a natural number, describes a vector of the first N natural numbers.

    ⍳7
0 1 2 3 4 5 6

The index function helps provide a set of sample values from which to describe arrays of various shapes. The following examples illustrate how the shape of an array arranges elements of an array:

    ⍬⍴⍳9   ⍝ An empty shape gives a scalar
0
    3⍴⍳9   ⍝ A vector fills from the elements as needed
0 1 2
    8⍴⍳4   ⍝ An array fills repeatedly from its elements
0 1 2 3 0 1 2 3
    2 3⍴⍳9 ⍝ Matrices fill rows at a time
0 1 2
3 4 5
    3 3⍴⍳4 ⍝ Matrices also fill repeatedly
0 1 2
3 0 1
2 3 0

Notice that matrices fill from the elements repeatedly starting a row at a time. This explains the term row major. When arranging elements according to the shape, the first index of the most major dimension fills before the second most major index. In the examples above, the row was the most major dimension, so each row filled before the next row.

This process generalizes to any number of dimensions. To give an intuition to this, consider a 3-dimensional array with shape 2 3 3 fill from the elements ⍳4.

    2 3 3⍴⍳4
0 1 2
3 0 1
2 3 0

1 2 3
0 1 2
3 0 1

In this case, APL needs to represent a 3-dimensional array on a two-dimensional grid of characters. To do this, it arranges each sub-matrix as normal, but then separates each sub-matrix with a blank line. Thus, for a shape of 2 3 3, APL displays such an array as two matrices separated by a blank line. Notice what happens if the shape changes to 3 2 3.

    3 2 3⍴⍳4
0 1 2
3 0 1

2 3 0
1 2 3

0 1 2
3 0 1

See how the elements continue to be arranged in the same way, but the size of the first dimension (the most major one) increased, while the second dimension size decreased. Now, instead of having two 3 3 matrices, APL displays three 2 3 matrices.

Play with using different elements in the array and using different shapes, with both the same and different elements. Gaining a good intuition for the concept of elements and shape together and how they work can take a little time. Don’t worry.

As a final note, the astute reader will realize that the number of elements given as the right argument to the reshape () function do not necessarily need to match the number of elements that the reshape function describes, as given in the left argument corresponding to the shape of the described array. Indeed, reshaping an array will continue to pull elements from the ravel of that array, as many as needed, repeatedly, without complaint. As a parting gift, spend some time pondering these properties, which speak more about this unique feature and others.

×/S ⍝ The product of the elements of shape S
    ⍝ also known as the number of elements in an array 
    ⍝ of shape S

S⍴A ←→ S⍴,A ⍝ Reshaping any array is the same as reshaping its
            ⍝ ravel

(×/S)⍴A ←→ ,S⍴A ⍝ The ravel of a reshaped array is the same as 
                ⍝ the reshape of that array with the product 
                ⍝ of all the dimensions in the shape

S⍴A ←→ S⍴(×/S)⍴A ⍝ Reshaping an array A is the same as reshaping 
                 ⍝ the ravel of A replicated to match the product 
                 ⍝ of the dimensions of the shape