Thursday, March 31, 2016

Recompiling can be excessive

Recompiling can make me uncomfortable

Computer programs often involve encoding some assumptions especially at the top of the program and then go on to exploit those assumptions, either at compile-time or at run time.

Compile-time assumptions often use macros.

Computations in macros

In one of my image processing programs I had the following macros:

#define IMAGE_WIDTH 320

#define IMAGE_HEIGHT 480

#define IMAGE_NB_PIXELS IMAGE_WIDTH*NB_HEIGHT

The program was meant to be used on pictures coming from a specific fingerprint scanner. The idea of hard-wiring the size was useful in that there could be a hard-wiring of a lot of constants in the program that would result in a very fast program. Few people would complain that the calculation IMAGE_WIDTH*IMAGE_HEIGHT would be recomputed every time the program was modified, since recomputing the same constant over and over again is such a small part of the overall time.

Include files

Let’s now consider a slightly less innocuous practice in C++: the use of include files.

It’s quite common to have an occurrence of a call to an include preprocessor directive such as

#include <stdio.h>

#include “header1.h”

#include “hearer2.h”

(for example) inside a program when in fact we do not know whether this leads to an implicit include of the same include file twice. It’s generally considered harmless because of a directive like for example

#pragma once

inside each of one’s headers. There is alternate trick to avoid “double inclusion” which uses something like

#ifndef HEADER_H

#define HEADER_H

#endif

In this case however there is a slightly greater compile-time cost for not paying attention to the dependencies.

An example involving music notation

This one is something that came to mind, and I have not implemented. It is far more sophisticated.

It is not really about C++ programming but about maintaining assumptions in a program.

The above programs have an implicit primitive handling of assumptions.

Suppose we are writing a music notation program.

One might want to be “declarative” and this means that one might want to describe the different note values that are involved in music. One way of going about it is to state that there is unit note value (a duration of one note) and that for each power of two P up to a certain power there is a note value of duration 1/P, and that for each such note value there is a distinct symbol (they are the conventional symbols for minim, crotchet, quaver, semiquaver and so on).

This is a typical statement one might make during an explanation. If I were listening I might ask “what is the highest power for which there is a symbol?”. So we would have an illustration of teacher-disciple interaction I want to repeatedly allude to.

Then I as the disciple might request that the teacher give me a graphical description of the symbols that correspond to each note duration.

This request might be followed by a later request to provide a better graphical description (for example SVG replacing raster images).

The symbols need to be ready for use in a running musical notation program. It is hopefully clear that rerunning the initial description about the different notes and the supply of various graphical descriptions is somewhat unnatural, not to say ludicrous!

In fact in this case it comes to mind for my AI background that a reason maintenance system could be of help.

Sometimes one statement can change your behaviour

One statement can change change your behaviour

The expert system dogma

When I was a student following some courses on AI and expert systems, our professor used to insist on the idea that any statement concerning a corpus of knowledge could be just translated into one or more rules, and then an inference engine would take this body of rules (the “rule base”) and the combination would have the appropriate behaviour. What’s more he used to insist on the idea that statements came as an unordered collection.

It was appealing but never convinced me.

It doesnt always work in practice

That professor got a few contracts working with big players, and in one of them he was required to work with a real world problem in which it was practically mandatory to work with sorted data. So he tried to sort the data with some inference rules. It did not work well enough, it was too cumbersome.

As a way of cognitive modelling

Here are some examples where it’s you the human that is doing the inference:

1)You get an electronic device and you read that it has been designed to turn itself off if there is no user interaction with it for a period of more than 10 minutes. This is a battery-saving feature of course. It might take a little time to assimilate but it changes your behaviour with respect to that device, in that you stop worrying about how long it has been turned on. This is a rather deep ramification of the statement that it has this battery-saving feature. I really don’t see that as at all something that would fall out of a rule and an inference engine.

2)When you know that you can undo any action in a text editor, it frees up a good deal of your thinking and changes your behaviour.

Stepwise construction of concepts

Constructing concepts

An example from a research paper

There is a paper concerning the vectorization of raster images of (black and white) line drawings by Dov Dori and Liu Wenyin. Before they get into the pseudo-code of their algorithm they present a sort of step by step construction of concepts that are used to explain the algorithm.

Here is an excerpt (via copy and paste)

(1) Black pixel—a foreground pixel of graphic objects in the image.

(2) Black pixel area—the foreground area of graphic objects in the image.

(3) Bar—a straight line segment with non-zero width, which occupies a (possibly slanted) black pixel area in the drawing image. The ideal area is an oval consisting of a rectangle and two semi-circles, as shown in Figure 111(a).

(4) Arc—a circular line segment with non-zero width, which occupies a (possibly closed) black pixel area in the drawing. The ideal end points are also round capped, as shown in Figure 111(b).

(5) Polybar—a chain of two or more equal width bars linked end to end. Bar widths are considered equal if they are within a prescribed tolerance.

(6) Polyline—a polybar resulting from approximating an arc or a free curve by a crude vectorization procedure.

(7) Wire—a generalization of bar, circular arc and polybar, which is used to denote any line-like graphic object in the drawing image.

(8) Scan Line—a one-pixel-wide horizontal line that crosses the drawing image from left to right, used to find the first black pixel of a black pixel area. Scan lines are spaced vertically every n pixels, where n is smaller than the minimal anticipated line width.

(9) Current Pixel—the pixel at which the tracking has arrived at a given point in time.

(10) Pixel Visiting Direction—one of the four directions left, right, up or down, to which the pixel following the current pixel is visited.

(11) Directed Run—a sequence of consecutive horizontal or vertical black pixels in the pixel visiting direction from the first encountered black pixel to a stop pixel (defined below).

(12) Directed Run Sign—a sign which is negative when the pixel visiting direction of the directed run is left or up, and positive when it is right or down.

(13) Stop Pixel—the first pixel along a directed run which either encounters a white pixel or exceeds a predefined maximal directed run length.

(14) Run—the undirected, unsigned sequence of consecutive black pixels formed by linking two directed runs with opposite directions that start from a common point.

(15) Middle Run Point—the middle point of a run. If the run length is even it is taken as the left or top of the two middle points.

(16) Length Direction—a pixel visiting direction whose associated run is longer than the corresponding run in the orthogonal direction. The length direction is horizontal if the slant of the line at the current point is up to 45 degrees and vertical otherwise.

(17) Width Direction—the pixel visiting direction orthogonal to the length direction of the associated run.

(18) Tracking Step—a directed run of a specified length in the length direction. A tracking step is taken to search for the next medial axis point from the current medial axis point.

(19) Width Run—a run in the width direction.

(20) Length Run—a run in the length direction.

(21) Tracking Cycle—a cycle of finding the next middle run point, which consists of taking a tracking step, making the width run, and then obtaining the middle point of the width run.

Remarks

Let’s make several remarks

It’s rather rare to have such a presentation of concepts before an algorithm is detailed!
The presentation is more or less step by step and assertions are based on the concepts described in previous points.
However the statements refer to background assumptions that the reader is supposed to be able to fill in, given his/her general understanding.
The presentation is nevertheless informal, and an improvement might well be possible.
I can imagine that there is a formal construction that could be fed to a computerized “disciple” or “assistant” that could be inspired from the above natural language construction. However, an important point I don’t have time to go into here is that simple predicate calculus is not going to be sufficient.
A formal construction could be checked. I am not very familiar with systems that do so, but maybe something like the calculus of constructions by Thierry Coquand is worth looking at here. However I think that there is an aspect of disambiguation to investigate.
The above construction is one sided: there is no hint of a disciple asking the teacher questions.

This is one of the sources for the research by Dori and Wenyin

http://Research.Microsoft.com/Pubs/68811/Sparse_Pixel_vectorization.doc

Friday, March 25, 2016

First followup on macros and resource management

It's been a while since I wrote Macros and Resource Management in this blog. I've been busy.
I guess that what I was wanting is a macro that can be called like the C preprocessor (CPP for short) to do the job.
It seems almost certain that CPP cannot do the job. I'm not sure about the alternatives at the present time like m4. It looks like a template engine like Jinja2 cannot do the job (or at least the basic features don't allow for it). If you want to correct me on this that's more than fine.
So would I have to write my own preprocessor?

Another idea is to write a program in a language that looks a lot like C, but is really something else
(like Lisp or Prolog) and write a preprocessor in the language to do the preprocessing.

I suppose I should also look at the subject of Multistage Programming to see what has been said on this. I asked an expert on Multi-Stage programming called Charles Consel (from Bordeaux) if there has been any layer on top of C that would allow the generation of C, but he replied that there only have been a few brittle prototypes.

Redundance in API

Redundance in API’s

Look at any reference manual on API’s there is a lot of “redundance”.

Take for example the CImage library documentation of the CImg class which you can find here:

http://cimg.eu/reference/structcimg__library_1_1CImg.html

It is seems clear to me that a good deal of this documentation can be condensed into a small set of general principles from which the existence of the API functions can be deduced.

This is easy to see in an example:

bool	is_sameX (const CImg< t > &img) const
	Test if image width is equal to specified value.

bool	is_sameX (const CImgDisplay &disp) const
	Test if image width is equal to specified value.

bool	is_sameY (const unsigned int size_y) const
	Test if image height is equal to specified value.

template<typename t >
bool	is_sameY (const CImg< t > &img) const
	Test if image height is equal to specified value.

bool	is_sameY (const CImgDisplay &disp) const
	Test if image height is equal to specified value.

bool	is_sameZ (const unsigned int size_z) const
	Test if image depth is equal to specified value.

template<typename t >
bool	is_sameZ (const CImg< t > &img) const
	Test if image depth is equal to specified value.

There is an obvious pattern above: what goes for the X axis also goes for the Y axis and the Z axis.

Yet to try and articulate this principle is very difficult for your average programmer.

Another problem that comes to mind is that we can have a more or less deep explanation for the patterns of the API. A deeper explanation will be able to have a larger “scope” (influence more API functions).

The problem is not at all trivial, and I do not expect any quick solution.

It might be that instead of just generating a set of API’s specifications from a set of basic principles, there are a set of principles that can conflict and that it’s a matter of balancing the forces from various principles: it could be a constraint satisfaction problem under optimizations.

In any case the redundance of API is not a bad thing per se, as the API designer is supposed to make life easy for the API user.

I close this note by stating that I do not expect to see an extremely reductionist solution to the design of API: It might well be that what passes off as a good set of API today looks quite unsatisfactory ten years from now.

Wednesday, March 9, 2016

Macros and resource management

A common problem
A lot of code is rather predictable and is distracting from the main idea of the code.
For example suppose that you have a C function that does a series of allocations (through malloc) and that there are opportunities in the function to raise an error. In that case not only must the function return (perhaps an appropriate code) but also the resources aquired (in this case it is the allocated pointers, but it could be for example FILE pointers) must be freed.
It is easy to make a mistake, either when writing or even more so when modifying the program and
not put in the appropriate calls to free just before the return. This could create a memory leak.
Another concern when landing on an error is to indicate an apropriate error message, although at first blush it's less likely that this will be done wrong, it too can be distracting from the purpose of the code.
All of this is very banal to an experienced programmer. It cropped up particularly strongly for me when developing CUDA code. In fact many of the sample functions I saw in the litterature did not do the freeing of resources correctly, probably because it was just too tedious.
So what might be done to ensure that this can be done will little chance of error?
A runtime solution
One approach is to "let the function manage its allocations".
In this approach the function makes use of a stack-like data structure in which every time an allocation is successfully done (a copy of) the pointer created is pushed onto a stack.
If an error is met then a special error-handling function is called to loop through the stack, with a pop-free pointer action until we come back to the beginning state of the stack when the function was entered.
This is a pretty pragmatic solution (providing of course we do not overflow this stack) and it's a good illustration of "letting the function take care of itself".
A language solution
Some languages adress this kind of problem by creating a language construct that takes care of resource management that works well with errors.
For example Python has a "with" keyword and C# has a using keyword.
To quote from a stackoverlow discussion:

with open('output.txt', 'w') as f:
     f.write('Hi there!')

The above with statement will automatically close the file after the nested block of code.

Could there be a solution by metaprogramming?
I think one can ask whether one could not manage the errors by automatically generating the appropriate calls to free.
I'm not going to argue for the relative merits of one method over the other. In fact I feel that many programmers would find the "runtime solution" to be the one with the most merit.
However I would like to point out that in day to day activity I have rarely seen the use of tools that can accomplish the metaprogramming solution. So the point is that a metaprogramming solution would not even be considered, because we are not used to the tools that can make it it possible.
In a future post I hope to explore a possible metaprogramming approach.