Modelling the atom

Introduction

We shall discuss an example of representing some high-school science statements about electron layers. Of course this is not directly about metaprogramming, but it is a fairly well known subject, a fun subject (in my opinion) and the questions asked could have analogues in metaprogramming.
So let us start with a natural language description of the "knowledge" we are trying to represent and then we comment as we go along what representational issues might arise. Please do not pick on the scientific accuracy of the statements below.

The statements

1. There is a finite set called the chemical elements
2. Each chemical element has a unique name (which is a string).
3. There is a certain set of physical objects called atoms.
4. Every atom belongs to a unique chemical element.
5. An atom can be in a ionized or non-ionized state.
6.  For each chemical element, any non-ionized atom that belongs to it has a finite set of electrons whose cardinality (count) is a function of the chemical element. This number is called the atomic number. 
7. Below we only deal with non-ionized atoms.
8. The set of electrons in an atom is partitionned into subsets called layers.
9. One of the layer is called the base layer.
10. Each layer has a different energy level, a non-negative real number measured in electron volts.
11. The base layer has an energy level of zero. 
12. Sorting layers by energy level is the way we will adopt to index them. The first index is 1.
13. If an electron is a member of a layer, its energy level is the energy level of the layer.
14. Each layer has a number called a capacity. 
15. The capcity is independent of the chemical element to which the atom belongs. 
16. No layer can contain more electrons than its capacity.
17. The capacity is in fact equal to 2n² where n is the index of the layer. 
18. A layer is said to be filled if it has as many electrons as its capacity. 
19. If a layer of index n has an electron, then all layers of lower index are filled.

Where the statements might be used

We can imagine that something with a structure like the list of above statements is given in a high school comprehension test. Then the student has to answer questions. For example:

• An atom a belongs to a chemical element called Chlorine, whereas an atom b belongs to an element called Tin. Could they have the same number of electrons?
• An atom has 60 electrons. Does the layer of index 2 have any electrons? If so, how many?

Replacing the terms by unfamiliar ones and the effect on legibility

Suppose we change much of the terminology above to some that are not part of the usual vocabulary: we replace "chemical elements" by "fargizles", atoms by "meditrons", layers by "compartments" and so on. Then all of a sudden we might notice that some things are not at all clear in the above description. It's an experiment worth carrying out.
It's a bit like the idea of renaming the identifiers in the source code of a program. All of a sudden it becomes extremely hard to read. This analogy does not go very far though.

Dependencies, order and permutation

Another interesting aspect of the statements is that there are obvious dependencies between them; line 4 depends on line 1 to make sense, for example. This raises a reasonable general question:

If we permute the order of the above statements can we necessarily make sense of the set of statements, and reconstruct the dependencies? I'm not sure this is obvious, but when I was a student, our teacher on expert systems insisted on the fact that the "rules" in an expert system were not ordered. If permutation of a large set of statements can make the reconstruction of the dependencies unworkable is this a defect that should be got rid of, or it just something we have to live with?

Non-monotonic reasoning

Here's another point. Anybody who reads the above makes inferences while reading the statements, and we may ask if some of the inferences are going to be invalidated and reconsidered. This is the problem of non-monotonic reasoning.

Attempts at formalisation and pitfalls

Formalisation evokes the choice of data structures or the use of well-established representational relations like "part-of", "instance-of". These are representational commitments, and I think I should stress that I think (paraphrasing Knuth) that premature formalisation is the root of all evil. At the very least we should not discard the original natural language statements.

The set of electrons

Concerning statement 6 above: every atom has a finite number of electrons. We have some formalisation concepts to bear on this, namely that electrons are part-of atoms. If electrons are part-of atoms, and there are a finite number of them, one might be tempted to create an atom object with a list-of-electrons field, but this turns out to be completely wrong here, for several reasons:

One of which is that electrons are not named, and we have no need for such a list in the reasoning.

The collection of layers

On the other hand having a list of the "layers" might seem ok, but the readed might wonder what the ordering of the layers would mean. It is not immediately obvious that it has any ordering at all from 8, but when we come to 10, we can deduce that if each layer has a different energy level, then the energy level can be used to order the layers.
Finally this is done at statetement 12.At this point it is like the person who has written the statements down has imposed "the" ordering of the layers.

 It could be thought that some of the statements like 8 are therefore redundant and should be eliminated, I retort that it would add cognitive strain to the person entering the ordered set of statements for one, and that it should not cost anything in the long run anyway, and there might even be some less obvious advantages because it might make it easier to revise the sequence of statements.

The rules of filling have representational consequences

The fact that layers are filled with electrons from the lowest level upwards makes it simpler for us to think about the state of the collection of layers. In particular, only the number of electrons needs to be stated -from there we can instantly tell how many electrons there are in each layer. In traditional formalisation practice this is something that is left entirely up to the designer of the data structures. I want to suggest that leaving it entirely up to the human is probably not a good idea in the long run.

A next step

  The next step would be to build a system and try to teach it the above statements, with a formalisation that tries to stick as closely as possible to the above statements. Then we could add further statements (for example concerning the emission of light when electrons change layers) and we could see if it would be hard to extend the system, or would it break down when trying to extend it. 

I can think of two kinds of extensions:

• add new scientific information (which might be unknown to a high school student)
• try to make and replace the above statements by richer and more realistic ones, using "common knowledge": like talking about the shape and size of an atom.

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

<body of header here>

#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

1. It’s rather rare to have such a presentation of concepts before an algorithm is detailed!
2. The presentation is more or less step by step and assertions are based on the concepts described in previous points.
3. However the statements refer to background assumptions that the reader is supposed to be able to fill in, given his/her general understanding.
4. The presentation is nevertheless informal, and an improvement might well be possible.
5. 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.
6. 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.
7. 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

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.

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.