June 2010

# Static Code Analysis

[updated 1.6.2024 to fix the nodes in the C code]

This post will tie together
problem representation, the power of Lisp, and the fortuitous application of the solution of an AI exercise to a real world problem in software engineering.

Problem 3-4b in
Introduction to Artificial Intelligence is to find a path from Start to Finish that goes though each node only once. The graph was reproduced using OmniGraffle. Node t was renamed to node v for a reason which will be explained later.

The immediate inclination might be to throw some code at the problem. How should the graph be represented? Thinking in one programming language might lead to creating a node structure that contained links to other nodes. A first cut in C might look something like this:

#define MAX_CONNECTIONS 6
typedef struct node
{
char *name;
struct node *next[MAX_CONNECTIONS];
} NODE;

extern NODE start, a, b, c, d, e, f, g, h, i, j, k;
extern NODE l, m, n, o, p, q, r, s, u, v, finish;
NODE start = {"start", {&a, &f, &l, &k, &s, NULL}};
NODE a = {"a", {&d, &h, &b, &f, NULL, NULL}};
NODE b = {"b", {&g, &m, &l, &a, NULL,NULL}};
...

Then we'd have to consider how to construct the path and whether path-walk information should be kept in a node or external to it.

If we're lucky, before we get too far into writing the code, we'll notice that there is only one way into
q. Since there's only one way in, visiting q means that u will be visited twice. So the problem has no solution. It's likely the intent of the problem was to stimulate thinking about problem description, problem representation, methods for mapping the "human" view of the problem into a representation suitable for a machine, and strategies for finding relationships between objects and reasoning about them.

On the other hand, maybe the graph is in error. After all, the very first paragraph of my college calculus textbook displayed a number line where 1.6 lay between 0 and 1. Suppose that
q is also connected to v, p, m, and n. Is there a solution?

Using C for this is just too painful. I want to get an answer without having to first erect scaffolding. Lisp is a much better choice. The nodes can be represented directly:

(defparameter start '(a f l k s))
(defparameter a '(f b h d))
(defparameter b '(a l m g))
(defparameter c '(d o i g))

...

The code maps directly to the problem. Minor liberties were taken. Nodes, such as
a, don't point back to start since the solution never visits the same node twice. Node t was renamed v, since t is a reserved symbol. The code is then trivial to write. It isn't meant to be pretty (the search termination test is particularly egregious), particularly efficient, or a general breadth-first search function with all the proper abstractions. Twenty-three lines of code to represent the problem and twelve lines to solve it.

One solution is (START K E S V U Q P M B L F A H G C D J O R I N FINISH).

The complete set of solutions for the revised problem is:

(START K E S V U Q P M B L F A H G C D J O R I N FINISH)
(START K E S V U Q P M B L F A H D J O R I C G N FINISH)
(START K E S V U Q P L F A H D J O R I C G B M N FINISH)
(START K E P M B L F A H G C D J O R I N U Q V S FINISH)
(START K E P M B L F A H D J O R I C G N U Q V S FINISH)
(START K E P L F A H D J O R I C G B M N U Q V S FINISH)

This exercise turned out to have direct application to a real world problem. Suppose threaded systems
S1 and S2 have module M that uses non-nesting binary semaphores to protect accesses to shared resources. Furthermore, these semaphores have the characteristic that they can time out if the semaphore isn't acquired after a specified period. Eventually, changes to S1 lead to changing the semaphores in M to include nesting. So there were two systems, S1 with Mn and S2 with M. Later, both systems started exhibiting sluggishness in servicing requests. One rare clue to the problem was that semaphores in Mn were timing out. No such clue was available for M because M did not provide that particular bit of diagnostic information. On the other hand, the problem seemed to exhibit itself more frequently with M than Mn. One problem? Two? More?

Semaphores in
M and Mn could be timing out because of priority inversion. Or maybe there was a rare code path in M where a thread tried to acquire a semaphore more than once. That would explain the prevalence of the problem in S2 but would not explain the problem in S1.

This leads to at least two questions:
1. What change in S1 necessitated adding support for nesting to the semaphores in Mn?
2. Is there a code path in M where a semaphore tries to nest?
Using a representation similar to the one used with the AI problem makes finding these answers somewhat easy. Suppose we define three keywords: acquire, release, and demand. Then a function which acquires one or more semaphores and calls other functions might look like:

(defparameter func_1 '(func_2 acquire sem_1 acquire sem_2
func_10 func_4 release sem_2 release sem_1))

A function that requires a semaphore be held could be described by:

(defparameter func_4 '(demand sem_2))

The description of a benign function:

(defparameter func_7 '())

It's then easy to write code which walks these descriptions looking for pathological conditions. Absent a C/C++ to Lisp translator, the tedious part is creating the descriptions. But this is at least aided by the pathwalker complaining if a function definition isn't found and is far less error prone than manual examination of the code paths. Would I have used this method to analyze the code if I hadn't just done the AI problem? I hope so, but sometimes the obvious isn't.

After completing the descriptions for
S1, the addition of one function call to an existing function in M was the basis for changing the semaphores so that they nested. The descriptions for S2 are not yet complete.

# Variation on a Theme

Q: How many programmers does it take to change a lightbulb?
A: None. It's a hardware problem.

Light out.
Hardware not functional.
Software relocated to cloud.

# Rite of Passage

The book begins with Mia Havero, a 19 year old woman, wife, and resident of a star faring craft, recounting the formative events of her life starting when she was twelve. "Rite of Passage" is a coming of age story in a society which must, by necessity, carefully control its birthrate since a starship has limited resources against which population must be carefully balanced. In her culture, when children are 14 they must undergo "Trial" where they are placed alone on a planet for thirty days to test their survival skills. If they come back, they are fully accepted as adults.

Undergoing a physical ordeal is only one aspect of her transformation from child to woman; she must also undergo a moral transformation and ends up opposing her father on an issue that effects a world.

As part of her attempts to grapple with morality, she has to prepare a paper for school on the subject. She wrote:

Ethics is the branch of philosophy that concerns itself with conduct, questions of good and evil, right and wrong--and there are a great many of them, because even people who supposedly belong to the same school don't agree a good share of the time and have to be considered separately--can be looked at as a description and as a prescription. Is this what people actually do? Is this what they should do?

What I find interesting is that she uses the "is-ought" definition for morality. I first read this book in high school, yet I didn't remember this part (cf. here).

She goes on to critique several ethical systems. First, utilitarianism:

Skipping the development and history of utilitarianism, the most popular expression of the doctrine is "the greatest good for the greatest number," which makes it sound like its relative, the economic philosophy communism which, in a sense, is what we live with in the Ship. The common expression of utilitarian good is "the presence of pleasure and the absence of pain."

Speaking descriptively, utilitarianism doesn't hold true, though the utilitarian claims that it does. People do act self-destrucively at times--they know the pleasureful and chose the painful instead. The only way that what people do and what utilitarianism says they do can be matched is by distorting the ordinary meanings of the words "pleasure" and "pain." Besides, notions of what is pleasurable are subject to training and manipulation. The standard is too shifting to be a good one.

I don't like utilitarianism as a prescription, either. Treating pleasure and pain as quantities by which good can be measured seems very mechanical, and people become just another factor to adjust in the equation. Pragmatically, it makes sense to say One hundred lives saved at the cost of one?--go ahead! The utilitarian would say it every time--he would have to say it. But who gave him the right to say it? What if the one doesn't have any choice in the matter, but is blindly sacrificed for, say, one hundred Mudeaters whose very existence he is unaware of? Say the choice was between Daddy or Jimmy and a hundred Mudeaters. I wouldn't make a utilitarian choice and I don't think I could be easily convinced that the answer should be made by the use of the number of pounds of human flesh. People are not objects.

Next, she questions the philosophy of "might makes right."

In effect, the philosophy of power says that you should do anything you can get away with. If you don't get away with it, you were wrong.

You can't really argue with this, you know. It is a self-contained system, logically consistent. It makes no appeal to outside authority and it doesn't stumble over its own definitions.

But I don't like it. For one thing, it isn't a very discriminating standard. There doesn't seem to be any difference between "ethically good" and "ethically better." More important, however, stoics strap themselves in ethically so that their actions have as few results as possible. The adherents of the philosophy of power simply say that the results of their actions have no importance--the philosophy of a two year old throwing a tantrum.

She summarizes:

My paper was a direct discussion and comparison of half-a-dozen ethical systems, concentrating on what seemed to me to be their flaws. I finished by saying that it struck me that all the ethical systems I was discussing were after the fact. That is, that people act as they are disposed to, but they like to feel afterwards that they were right and so they invent systems that approve of their dispositions. This was to say that while I found things like "So act as to treat humanity, whether in your person or in that of another, in every case as an end and not as a means merely," quite attractive principles, I hadn't run into any system that exactly fitted my disposition.

Of course, she would need to examine whether or not an ethical system should fit one's disposition. When should one cede one's moral authority, if ever? Why?

This is an addendum to The Myth of the Super Programming Language.

In
Introduction To Artificial Intelligence, Philip Jackson wrote:

One final thing to note on the subject of reasoning programs is that the language used by an RP will typically be changed with time by the RP. We should expect in general that a reasoning program will find it necessary to define new words or to accept definitions of new words; some of these words will denote new situations, actions, phenomena, or relations--the RP may have to infer the language it uses for solving a problem. Our most important requirement for the initial language is that any necessary extensions to it be capable of being easily added to it.

One of the things I never liked about Pascal was that the writeln function couldn't be written in Pascal. C is deficient in that, unlike Pascal, functions cannot be nested. And so it goes.

# On Stilled Wings, Soar

I was getting ready to mow the lawn and my wife was going to go to the grocery store. She came back inside to tell me that a baby bird was in the yard. It had fallen from its nest and was on the ground with its mouth open waiting to be fed. Using our stepladder, I placed it back in its nest and we hoped for the best. While mowing the lawn I noticed that there was a dead bird by our air conditioner. A few minutes after that, I saw that the baby bird had again fallen out of its nest. This time it was still.

on stilled wings soar in skies
you could never imagine.

"Are not two sparrows sold for a penny? Yet not one of them will fall to the ground apart from your Father." [Mt. 10:29]

# Proud Father, VI

My son is one of 150 students, out of over 3,200 applicants, who received a Department of Energy Science Graduate Fellowship.