C. Keith Ray

C. Keith Ray is developing software for Sizeography and Upstart Technology. He writes code for multiple platforms and languages, including iOS® and Macintosh®.
Go to Sizeography and Upstart Technology to join our mailing lists and see more about our products. Keith's Résumé (pdf)

Tuesday, January 28, 2014

myGraph Initial View

Let this picture serve as a 1000 words. More to come...




Thanks to a lot of hard work

Thanks to a lot of hard work, Sizeography's first iOS app, myGraph, is now live in the app store. This app allows you to print completely customized grid or graph paper from your iPhone or iPad to any compatible AirPrint printer. For a 99¢ one-time purchase (no ads, ever), you will have as many or as few sheets of graph paper to your exact specifications, at home or away. 

You can also use myGraph to send a pdf of your custom or predefined grid or graph paper to:
  • AirDrop
  • DropBox
  • Evernote
  • Message
  • Mail
  • Save an image to your photo library.
  • Copy an image to be pasted in another app.
  • myGraph can send pdf files to apps that accept pdf files.
  • and, myGraph can send png files to apps that accept png files.


We're working on a list of 101 uses for this app. Here are a few we have thought up so far:
  1. Planning and designing woodworking projects.
  2. Print a grid to help with sewing patterns.
  3. Tailoring.
  4. Scrap-booking.
  5. Science class: plotting lab results.
  6. Math class: graphing equations.
  7. Geometry class.
  8. Trigonometry class.
  9. Practicing writing Chinese, Japanese, Korean, and other languages.
Have another use for custom graph paper in mind? Comment here or on our sizeography.com site.


Monday, January 27, 2014

Some thoughts on C, OO, ObjC, C++

C allows structs to be copied "by value" but C doesn't allow array types to be copied—directly. The following code will not compile:

typedef int FiveIntsArray[5];

FiveIntsArray function5ints( FiveIntsArray arrIn )
{
    FiveIntsArray ret:
    ret = arrIn;
    return ret;
}

int main(int argc,char*argv[])
{
    FiveIntsArray arr = {1,2,3,4,5};
    FiveIntsArray bar;
    bar = function5ints(arr);
    printf("%d, %d, %d, %d, %d\n", bar[0], bar[1], bar[2], bar[3], bar[4]);
}

Yes, it does not compile:



But put all this inside a struct, and it all works!

typedef struct FiveIntsStruct {
    int arr[5];
} FiveIntsStruct;

FiveIntsStruct function5ints( FiveIntsStruct arrIn )
{
    FiveIntsStruct ret;
    ret = arrIn;
    return ret;
}

int main(int argc,char*argv[])
{
    FiveIntsStruct arr = {{1,2,3,4,5}};
    FiveIntsStruct bar;
    bar = function5ints(arr);
    printf("%d, %d, %d, %d, %d\n", bar.arr[0], bar.arr[1], bar.arr[2], bar.arr[3], bar.arr[4]);
}

And I get this output:

1, 2, 3, 4, 5
Program ended with exit code: 0

Ta-da!

However, struct-copying, at least in the early days of C, was thought to be not very efficient, and was often avoided in C code. This tradition is so ingrained in C programmers that I have met 
some programmers who didn't know that struct-copying is allowed in C.

For small structs, and under modern compilers, struct-copying can be just as efficient as passing a single value, and more efficient than passing a pointer to a struct, which requires dereferencing the pointer to access its members. A 64-bit CPU can hold an entire FiveiIntsStruct in a single register.

If you want to do object-oriented programming in C, one way to do that is to start with structs. We can associate functions and structs, and we already have an example of something object-like in the C standard library: the file io functions.

typedef struct FILE { 
    // we don't care what's in here--consider it private.
} FILE;

FILE * fopen(const char *restrict filename, const char *restrict mode);
// fopen allocates & initializes, kind of like a C++ constructor.

int fprintf(FILE * restrict stream, const char * restrict format, …);
// functions taking a FILE* arguments are methods of the FILE "class".

int fclose(FILE *stream);
// cleans up and deallocates, kind of like a C++ destructor.

But a big part of OO is polymorphism. How can we accomplish that? Let's say we want a file-writer, and a network-writer, but the majority of the code should work with both kinds of writer. We can do it a bit like this:

struct Writer;

typedef int (* PrintFunc)(struct Writer * w, char const * format, ...);
// pointer to function that returns int
// and has Writer* as the type of its first argument.

typedef void (* CloseWriterFunc)(struct Writer * w);
// close and de-allocate

typedef struct Writer {
    PrintFunc Print;
    // ...other function pointers
    CloseWriterFunc Close;
} Writer;

Writer * NewFileWriter(const char *restrict filename);
Writer * NewNetworkWriter(const char *restrict serverName);

int main(int argc, char*argv[])
{
    Writer * w;
    int useFile = 1;
    
    if ( useFile )
        w = NewFileWriter("someFile.txt");
    else
        w = NewNetworkWriter("someServer");

    w->Print(w, "etc.");
    w->Close(w);
    w = NULL;
}

Implementing this in one or more .c files:

typedef struct {
    Writer wpart;
    // file-writer specific data members go here.
} FileWriter;

typedef struct {
    Writer wpart;
    // network-writer specific data members go here.
} NetworkWriter;

// must match function-pointers...

static int FileWriterPrint(Writer * w, char const * format, ...)
{
    FileWriter * fw = (FileWriter *) w;
    // real code goes here.
    return 0;
}

static void FileWriterClose(struct Writer * w)
{
    FileWriter * fw = (FileWriter *) w;
    // real code goes here.
    free(fw);
}

static int NetworkWriterPrint(Writer * w, char const * format, ...)
{
    NetworkWriter * fw = (NetworkWriter *) w;
    // real code goes here.
    return 0;
}

// other NetworkWriter functions...

static void NetworkWriterClose(struct Writer * w)
{
    NetworkWriter * fw = (NetworkWriter *) w;
    // real code goes here.
    free(fw);
}

Writer * NewFileWriter(const char *restrict filename)
{
    FileWriter * fw = malloc( sizeof( FileWriter) );
    fw->wpart.Print = FileWriterPrint;
    fw->wpart.Close = FileWriterClose;
    // real code goes here.
    return (Writer *) fw;
}

Writer * NewNetworkWriter(const char *restrict filename)
{
    NetworkWriter * nw = malloc( sizeof(NetworkWriter) );
    nw->wpart.Print = NetworkWriterPrint;
    nw->wpart.Close = NetworkWriterClose;
    // real code goes here.
    return (Writer *) nw;
}

The syntax isn't that nice, but a preprocessor could automate much of this.

And, in fact, both Objective-C and C++ started out as preprocessors generating C code.

There is one problem with this implementation besides its awkward syntax. Each instance of this struct contains copies of the function-pointers. This overhead can be eliminated by another level of indirection.

// there will be one instance of this struct per "class"
typedef struct WriterFunctions {
    PrintFunc Print;
    // ...other function pointers
    CloseWriterFunc Close; // close and de-allocate
} WriterFunctions;

typedef struct Writer {
    // writer data
    WriterFunctions* methods;
} Writer;

static WriterFunctions FileWriterFunctions = {
    FileWriterPrint, FileWriterClose
};

static WriterFunctions NetworkWriterFunctions = {
    NetworkWriterPrint, NetworkWriterClose
};

Writer * NewFileWriter(const char *restrict filename)
{
    FileWriter * fw = malloc( sizeof(FileWriter) );
    fw->methods = FileWriterFunctions;
    // real code goes here.
    return (Writer *) fw;
}

Writer * NewNetworkWriter(const char *restrict filename)
{
    NetworkWriter * nw = malloc( sizeof(NetworkWriter) );
    nw->methods = NetworkWriterFunctions;
    // real code goes here.
    return (Writer *) nw;
}

This is probably not that far from the implementation that C++ uses, where polymorphic ("virtual") function-pointers are kept in "vtables".

C++ contorts the C language into pretending classes are just "special" structs. But a C++ class or struct may have many hidden things: a vtable pointer, an implicitly-defined default constructor calling constructors on its member variables, an implicitly-defined copy constructor calling copy constructors of its member variables, an implicit-defined assignment operator calling assignment-operators on its member variables, and an implicitly-defined non-virtual destructor calling the destructors of its member variables.

And C++ has some gotchas: if the base class in a class hierarchy has an implicitly-defined non-virtual destructor, calling delete on a pointer of the base-class type (but it is pointing to a derived-class object), the derived-class destructor does not get called, which may destroy the correctness of the system.

Objective-C adds classes and objects as something different from structs, adding some pretty self-contained Smalltalk-like syntax to C. Without operator overloading and other contortions of syntax, what you see in Objective-C code is generally what you get. Not much invisible or implicit stuff in the language itself (though the implementation of method-lookup isn't normally invisible). With ARC, retain, release, and autorelease are mostly invisible/implicit, and I'm pretty sure Apple has done some very interesting things at run-time for certain technologies like Core Data.

If you know where the sharp edges are, C++ can be pretty cool. And you can blend C++ and Objective-C if you want to. C++ constructors and destructors will be invoked (invisibly/implicitly) for you in Objective-C's equivalents of constructors and destructors. 

Most of the functionality of ARC could have been implemented with appropriate C++ smart pointer template classes, but I'm sure most Objective-C programmers would not want to sweat the details of the required syntax.

So there it is.

Tuesday, January 21, 2014

FRACTIONS and computers

Fractions and computers: and when I say "computers," I am including the iPad, iPhone, iPod Touch as well as laptop and desktop computers.

If you work in traditional English units—inch, foot, pound, and so on—you are used to working with fractions. Instead of 3.25 inches, you would say 3¼ inches. Computers usually force you to work in decimals, like 3.25 inches, but there are a some issues with decimals, binary, and fractions you should know about.

You should know that computers can handle some fractions very well; these would be the powers-of-two fractions like ½, ¼, ⅛, and so on. This is because the computer represents numbers in a power-of-two fashion we call "binary". In binary there are only two digits: 0, and 1, and we arrange them in columns to make larger numbers. 

(binary) 101 = 1 × 2² + 0 × 2⁰ = 4 + 0 + 1 = 5.

In decimal, we have digits 0-9 and arrange them in columns to make larger numbers. The number 345 has a 3 in the 100's column, a 4 in the 10's column, and a 5 in the 1's column. Each column represents a power of 10.

(decimal) 345 = (3 × 100) + (4 × 10) + (5 × 1)
= (3 × 10²) + (4 × 10¹) + (5 × 10⁰)

On other side of the decimal point, the columns are also powers of ten, but the exponents are negative powers. The number 0.728 has a 7 in the tenth's column, a 2 in the hundreth's column, and an 8 in the thousanth's column.

(decimal) 0.728  = ⁷/₁₀ + ²/₁₀₀ + ⁸/₁₀₀₀
= (7 × 10⁻¹) + (2 × 10⁻²) + (8 × 10⁻³)
= (7 ÷ 10) + (2 ÷ 100) + (8 ÷ 1000)

Here's the scary part. Computers do not handle decimal fractions that are a power of ten very well, like ¹/₁₀ (which is 10⁻¹), ¹/₁₀₀ (which is 10⁻²), or ¹/₁₀₀₀.  (which is 10⁻³.) Because computers think in binary, the fraction one-tenth does not translate well into binary numbers. This is a problem similar to how some numbers are represented in decimal. For example, 1/7 is represented as a series of endlessly repeating digits in decimal: 0.14285714285714…

Similarly, decimal 1/10 in binary is an endlessly repeating sequence of binary digits to the right of the "binary point": 0.000110011….

decimal 1/10 = binary 0.000110011… =
= (0 × 2⁻¹) + (0 × 2⁻²) + (0 × 2⁻³) + (1 × 2⁻⁴) + (1 × 2⁻⁵) 
+ (0 × 2⁻⁶) + (0 × 2⁻⁷) + (1 × 2⁻⁸) + (1 × 2⁻⁹)…
= 0/2 + 0/4 + 0/8 + 1/16 + 1/32 + 0/64 + 0/128 
+ 1/256 + 1/512…
= 0 + 0 + 0 + 0.0625 + 0.03125 + 0 + 0 + 0.00390625 + 0.001953125…
= 0.099609375…

No matter how many binary digits we use to the right of the binary point, we can't get a value that exactly matches the decimal fraction 1/10, though it can get pretty close.


Why should this bother you?

It has to do with adding and multiplying. In many situations while using a computer, if you add the binary equivalent of one-tenth, ten times, you won't get the 1.0 you expect, unless those systems have taken precautions beyond the scope of this essay. 

In some systems, 0.1 translated to binary and back to decimal results in this number: 0.100000001490116119384765625. Add that number to itself ten times and you get approximately 1.0000000149011612. 

A fractional error, added and multiplied many times, can result in numbers being "off" enough to throw off what you want to measure.

What am I going to do about this?

I want, when feasible, to represent numbers as fractions when you enter them into an app that specifically uses fractions in its input, and/or output. When you enter a number like 3¼ into some of my apps, I will actually keep it as three numbers: 3, 1, and 4, and keep those values straight when we add, multiply, or perform other operations on them.

If I represent 0.1 as the fraction ¹/₁₀ , and add that number to itself ten times, should get ¹⁰/₁₀ , and that should compare to the number 1 as exactly equal.


I am using this technique in Sizeography's new iOS app: myGraph. Not just for additional precision, but also to allow the user interface to clearly reflect the user is thinking. If a user wants graph paper with cells that are 1/8 of an inch wide, or 8 cells per inch, that's easier for the user to think about than requiring the user to type in 0.125.



myGraph showing Grid Spacing as 1/8


myGraph represents traditional measures as inches, either in fractions like ¼ or decimals like 0.25. myGraph also works in the metric system using centimeters. Centimeters are only represented as decimals.

When you switch between inches and centimeters, myGraph will convert to the nearest approximately equal value. If you are using inches and swich from fractions to or from decimals, myGraph will convert to the nearest approximately equal value.