Stacks and Queues in Prolog

Stacks and queues are basic bread and butter data structures, so I figured why not implement them in Prolog.

First, the stack.  A lot of the time you can get away with using the call stack as a stack.  Of course, this might not be the best idea if the stack is large, and depending on the problem it might be awkward.  Stacks are particularly easy to implement in Prolog, requiring just two predicates:

% item to add; original stack; new stack

add_stack( Item, Stack, [Item|Stack] ).
% original stack; item to take; new stack

remove_stack( [Item|RestStack], Item, RestStack ).

Pretty simple.  By merely utilizing a list and manipulating the first element, one can make a simple stack.  "remove_stack" is particularly simple; it will return false on an empty stack, which can lead to more natural solutions than those that explicitly must check for an empty stack.

Now for queues.  This is also pretty straightforward:

add_queue( Item, Queue, NewQueue ) :-

   append( Queue, [Item], NewQueue ).

remove_queue( [Item|RestQueue], Item, RestQueue ).

Again, a simple list is used.  The only difference is that added elements go to the end of the list, instead of the front.  However, there is a problem with this.  Generally, queue implementations are assumed to offer queue and dequeue operations in O(1).  This one achieves an O(1) dequeue, but an O(n) queue because of the append operation.  We want to put an item at the end of the list, but in order to do that, we need to traverse the entire list.

For trivial things, or where it can be guaranteed that n is small, this is probably not a problem.  However, for real applications, this is definitely an issue.

We want to be able to add things to the back of the list, while taking things from the front of the list, both in constant time.  The problem is that we can't do that with just a plain old list.

Think outside of Prolog a bit.  Imagine this were C++ code.  Each element of the list would likely be implemented as a node in a linked list.  The way to get O(1) access for both the first and last nodes would be to store pointers to both the front and back.  Prolog gives you the front for free, but not the back.  You would like to store a pointer to the back, but Prolog doesn't let you do that.

At least not as a pointer.  Prolog lets you do something much cooler: variables.  Logical variables have seemingly magical properties to someone that is used to more traditional languages.  The most magical bit is that they can be uninstantiated, to be instantiated at some later time (or not).  With that in mind, consider the following:
?- Test = [1, 2, X, 3, 4], X = 10.
Test = [1, 2, 10, 3, 4],
X = 10.

The variable "X" is instantiated after it was put in the list.  Now, normally X = 10 would be a constant time operation, but in this case...it's a constant time operation!  With this simple example, one has a pointer to the middle of the list.  So why not put the variable X at the end?

This is exactly how one can accomplish the trick of adding to the end in O(1).  It does, however, require a more complicated queue definition.  Queue operations must return both the queue and the variable at the back of the queue.  Additionally, since the two terms are very closely related to each other, splitting them into two separate terms isn't advisable.  Fortunately, Prolog's pattern matching makes this trivial.  The power of pattern matching can be seen with the following example:
math( X-Y, Z ) :-
        Z is X - Y.
math( X+Y, Z ) :-
        Z is X + Y.
math( X*Y, Z ) :-
        Z is X * Y.
math( X/Y, Z ) :-
        Z is X/Y.
?- math( 2 + 5, X ).
X = 7.
?- math( 2 - 5, X ).
X = -3.
?- math( 2 * 5, X ).
X = 10.
?- math( 2 / 5, X ).
X = 0.4.

For this example, one essentially provides 3 parameters in one term: two numbers and an infix operator.  Pattern matching allows this to be specified in a far more natural way.

Using this same technique, we can define a queue of the form [x1, x2, x3, ..., xn, X]-X, where X is the logical variable at the end of the queue.  Using this form, we can then define operations that manipulate this form of queue, like so:
add_queue2( Item, Queue-X, Queue-Y ) :-
        X = [Item|Y].
remove_queue2( [Item|Queue]-X, Item, Queue-X ).

It is assumed that X is at the end of Queue in these predicates.  The whole "-X" part is just a way to keep the end of the queue in the same term, as described above.  When we add to the queue, we replace the old logical variable X with a new one, Y, in addition to appending the given item.  This achieves constant time for both operations.

Note that an empty queue is represented as X-X, not [X]-X.  In the definition of add_queue2, with a base case of X-X to add to, a list is created.  If there is already a list as in [X]-X, then this list ends up getting nested inside the initial list.  To illustrate this, here is an example with the different base cases:

% empty queue: X-X

?- add_queue2( 1, X-X, NewQ ), add_queue2( 2, NewQ, NewQ2), add_queue2( 3, NewQ2, NewQ3 ), remove_queue2( NewQ3, Item, NewQ4 ).
X = [1, 2, 3|_G1416],
NewQ = [1, 2, 3|_G1416]-[2, 3|_G1416],
NewQ2 = [1, 2, 3|_G1416]-[3|_G1416],
NewQ3 = [1, 2, 3|_G1416]-_G1416,
Item = 1,
NewQ4 = [2, 3|_G1416]-_G1416.

% empty queue: [X]-X

?- add_queue2( 1, [X]-X, NewQ ), add_queue2( 2, NewQ, NewQ2), add_queue2( 3, NewQ2, NewQ3 ), remove_queue2( NewQ3, Item, NewQ4 ).
X = [1, 2, 3|_G1422],
NewQ = [[1, 2, 3|_G1422]]-[2, 3|_G1422],
NewQ2 = [[1, 2, 3|_G1422]]-[3|_G1422],
NewQ3 = [[1, 2, 3|_G1422]]-_G1422,
Item = [1, 2, 3|_G1422],
NewQ4 = []-_G1422.

It *almost* works with [X]-X, and the other definitions could be tweaked so that it will work, but doing that skirts around the problem.  X-X is just cleaner.

There is, however, one problem.  In the original remove_queue definition with O(n) enqueue,  the call simply failed on an empty queue.  In this definition, this doesn't happen:
?- remove_queue2( X-X, Item, Q ).
X = [Item|_G1221],
Q = _G1221-[Item|_G1221].

Not only did this call succeed, it ended up placing the variable Item within the new queue.  The easiest way to fix this is with an additional predicate.  One might be tempted to add the following before the current definition of remove_queue2:

remove_queue2( X-X, _, _ ) :- !, fail.

Simple idea.  When we explicitly see the form of an empty queue, fail with no chance of backtracking.  At first, this appears to work:

?- remove_queue2( X-X, Item, Q ).

false.

However, a little extra testing reveals that something horribly wrong is occurring:
?- add_queue2( 1, X-X, Q ), remove_queue2( Q, Item, NewQ ).
false.

The new predicate is matching everything that takes the form of this queue, empty or not!  The reason for this is unfortunately quite low-level for my taste.  It has to with how Prolog unifies terms.  The short answer is that, likely for performance reasons, a certain check that would fix this is bypassed.  A more detailed explanation can be found in John Wickerson's explanation of difference lists at www.cl.cam.ac.uk/~jpw48/difflists.pdf(note that a great deal of this post is based on that document!)

The solution is to explicitly perform this check, like so:
remove_queue2( X-Y, _, _ ) :-
        unify_with_occurs_check( X, Y ), !, fail.

This acts to cut execution once the end of the queue is encountered.  As long as this predicate is asserted before the predicate to actually remove items, this will work.  A quick demonstration:
?- add_queue2( 1, X-X, NewQ ), add_queue2( 2, NewQ, NewQ2), add_queue2( 3, NewQ2, NewQ3 ), remove_queue2( NewQ3, Item, NewQ4 ).
X = [1, 2, 3|_G1419],
NewQ = [1, 2, 3|_G1419]-[2, 3|_G1419],
NewQ2 = [1, 2, 3|_G1419]-[3|_G1419],
NewQ3 = [1, 2, 3|_G1419]-_G1419,
Item = 1,
NewQ4 = [2, 3|_G1419]-_G1419.

We have a queue with O(1) enqueue and dequeue.

BFS in Prolog (AI)

I've mentioned elsewhere that I recently had to write a BFS in LISP.  Well, this is kinda a follow up to that.  Kinda.


I thought it made for a nice toy problem, and I wanted to learn some real Prolog, so I put the two together.  It worked, but it was a tad quirky, mostly in the way it stored the solution paths.

In an odd twist of fate, someone on Stack Overflow wanted to see an AI search like BFS implemented in Prolog.  I didn't want to post the solution to what originated as an assignment, so I changed the problem.  Like Knuth's conjecture, which is what the original solver solved, it has a given starting integer and a given goal integer.  However, the operations are simpler: increment, decrement, and multiply by +2 (no negative 2).  Additionally, I'm allowing for any starting integer, instead of positive four as in Knuth's conjecture.  The quirkiness is gone as well (which is why my bfs definition is slightly different from the original).

Without further ado, I post the code.  I'm sure that there are better ways to do certain things, especially if I had used some of SWI-Prolog's higher order predicates, but I think I learned more with the given definition.

% given a goal integer, it tries to determine the shortest
% series of actions needed to get to this integer given any other
% integer.  The actions allowed are increment, decrement, and
% multiply by two

% states are represented as two element lists
% the first is a number, and the second is a path

% gets the successors of the given state
% note that it must be redone via backtracking in order to
% get all of the successors
successors( [N,Path], [NewN, [Function|Path]] ) :-
        ( Function = increment, NewN is N + 1 ;
            Function = decrement, NewN is N - 1 ;
            Function = multiply, NewN is N * 2 ).

% gets all successors as a list
successors_list( State, Result ) :-
        findall( X, successors( State, X ), Result ).

% records results that have already been seen
:- dynamic seen/1.

% given a list of states, it will add each state to the table
% of states that have already been seen
add_to_seen( [] ).
add_to_seen( [[N|_]|Rest] ) :-
        assertz( seen( N ) ),
        add_to_seen( Rest ).

% removes all states that have already been seen
% returns a new list
remove_seen( [], [] ).
remove_seen( [[N|_]|Rest], Result ) :-
        seen( N ), !,
        remove_seen( Rest, Result ).
remove_seen( [State|Rest], [State|Result] ) :-
        !, remove_seen( Rest, Result ).

% performs a BFS, with the given goal and queue
bfs( Goal, [[Goal|[Path]]|_], FinalPath ) :-
        % note that operations are added from the front, and it's
        % more natural to read them left to right
        !, reverse( Path, FinalPath ).
bfs( Goal, [State|Rest], Result ) :-
        successors_list( State, Successors ),
        remove_seen( Successors, NewStates ),
        add_to_seen( NewStates ),
        append( Rest, NewStates, Queue ),
        bfs( Goal, Queue, Result ).

% runs the BFS for the given start integer and goal integer
% returns the path to reach the goal in "Path"
go( Start, Goal, Path ) :-
        retractall( seen( _ ) ),
        bfs( Goal, [[Start,[Start]]], Path ).


?- go( 4, 7, X ).
X = [4, multiply, decrement].

4 * 2 = 8; 8 - 1 = 7.  Cool.

Glow in the Dark Scorpions

Under UV light, scorpions are known to fluoresce. A few compounds have been identified in scorpions that are the root of this florescence, but it is not known why exactly the scorpions produce these compounds. Presumably, there is some sort of selective advantage to this florescence, or it is at least a byproduct of something else that confers a selective advantage.

Based on the work of Kloock et. al. (link to paper), it appears that this fluorescence has something to do with low-level UV light detection. Scorpions that underwent a treatment to remove the fluorescence properties seemed unable to detect the light. Individuals with the treatment were observed to behave differently under the same low UV light conditions as untreated scorpions, although curiously enough the type of behavior wasn't consistent between scorpions. In other words, ones with the treatment did different things than those without the treatment, but these things differed between individuals with the treatment (whew!).

Personally, I'm not 100% convinced of the results. The paper noted that the presented results were different from those of another paper, where the amount of UV light was so high that it likely caused the scorpions to avoid it altogether. Additionally, although it is completely possible that individuals with the treatment would exhibit different behavior, it seems odd to me that the behaviors differed.

Most importantly, the treatment itself, which batters the scorpions with light for weeks at a time, could be to blame for the differences. The authors acknowledged this, and presented an experiment to show that the eyesight of the scorpions was unaffected. This experiment showed there were no differences between treated and untreated scorpions in response to normal light as opposed to UV light. However, there still seems a possibility to me that there could have been retinal damage, but damage specific to the detection of UV. If a different protein or set of proteins is specifically responsible for detecting UV in the eye as opposed to normal light, then this is feasible. One of these proteins could have been degraded by the treatment, which would produce the same kind of results seen by the authors.

If time and money were not an issue, I think that a gene-knockout approach would be superior to the method used by the authors. By genetically preventing the scorpions from ever fluorescing, instead of relying on a post-fluorescence treatment, then it would be possible to make stronger conclusions about the results. However, this assumes that we understand at least part of the metabolism pathway involved in the production of the fluorescing compounds. Given that these compounds were all discovered within the decade (according to the paper), I might be getting ahead of myself here. It's one thing to know that an organism produces a given compound, and it's a whole other thing to know exactly how that organism produces the compound.

Even with all my criticism, I do think that the authors are on to something. They have provided enough evidence for me to think that their hypothesis is correct, though I would like to see additional experiments to help bolster it.

State

State is one of those funny things in programming. It is both wonderful and a curse, depending on the context. In my experience, moreso a curse.

First, a quick definition. By state, I mean a change occurs to some portion of a program, usually by assignment. A very simple example in C:

for( int x = 0; x < 10; x++ );

This has state, because the value of x changes by executing this loop.

The imperative paradigm views state as almost an end-all be-all. If you've ever worked in assembly language, which is essentially purely imperative, you know what I'm talking about. Technically, there are no functions, only subroutines, as functions return something. Machine languages typically have no way of "returning" something. Instead, there is some programming convention that certain changes to state are indicative of a function returning something. In MIPS, the convention is to put return values in certain globally available registers, or the stack.

Assuming the programmer knows EXACTLY what he or she is doing, this is great. This is typically the fastest way of doing something in terms of execution speed, and it can be efficient on memory as well. The problem is that most programmers don't completely know what they are doing. This isn't a bad thing, and I don't mean it offensively. In a good abstraction, the programmer shouldn't have to worry about everything. Do you really know and understand ALL of the software between a print statement and your monitor? I hope not. (If you do...well I tip my hat to you).

Things can get complicated fast in a purely imperative model. This is why there are all sorts of assembly conventions which attempt to limit the amount of state changes one can make. One could probably write marginally faster code, but it would take an enormous amount of time just to read the resulting nightmare. Humans can only really understand a few things at once, and this works contrary to a completely imperative model.

At the opposite end of the spectrum of the imperative paradigm is the purely functional paradigm. In a purely functional paradigm, there is no state. Everything is represented as a series of function calls. What may be surprising to the typically imperative programmer is that it's possible to achieve quite a bit in this model. Programs tend to be shorter, and easier to understand. Debugging time tends to be shorter, as well. Individual functions can be tested independently. Without state, the same function is guaranteed to return the same outputs on the same inputs under all conditions, barring some catastrophic hardware failure.

There is an added bonus of removing state: parallelism. In parallel code, the areas that need locks typically modify state. These areas can introduce sequential dependencies. Taken together, these regions result in code that is harder to produce, less clear, more prone to deadlock, and is slower. Without state, such regions don't exist. It's much easier to write parallel code. In fact, since purely functional programs can be broken down into a single expression with a multitude of subexpressions, it's possible to automatically achieve parallelization!

There is a downside of completely removing state, however. For one, all I/O is based on state. A program without I/O capabilities cannot take in any inputs or give any outputs, which is fairly worthless. Purely functional languages perform tricks to do I/O, which is technically impure by its very nature.

There is another downside: algorithmic complexity. Without state, certain problems cannot be represented efficiently. I've started to read Chris Okasaki's "Purely Functional Data Structures", which makes clear that even on a purely theoretical basis it's impossible for certain purely functional algorithms to be as efficient as equivalent imperative implementations. (Note that "certain" is an important word here; you can usually do as well.)

State just plain makes certain things easier to represent. Arguably, this is the main reason why many functional languages are impure, meaning they do allow for state.

Between these two extremes of purely imperative and purely functional programming are object oriented programming and logical programming. In the object oriented model, computation is represented in terms of objects. These objects have specific state and behavior. State is modified through well-defined channels which are typically integrated into the behavior of objects.

This is an interesting middle ground. It allows for state, but in a way that hides most of the complexity. In a well-written object-oriented program, changing the state in one object will not effect the state or behavior of a completely unrelated object. In the imperative model, there is no such enforcement of this. (Note that the aforementioned assembly conventions share a resemblance to the object oriented model, by allowing only certain side effects to occur. However, these are merely convention; your code does not enforce that these conventions are followed.)

Like object-oriented programming, logical programming has an interesting, partially restricted way of allowing state. The entire database, which holds both the program and the data, can be modified. Items can be added or removed, and the behavior of the program can change based on this. This is extremely powerful, but it can also be just as dangerous as in the imperative paradigm. Typically, programs change the database as little as possible, but this is more of a convention than anything else. It's possible to truly have a program write and execute itself with this model, in a way that is unparalleled in other paradigms.

A major downside of this is that changes are usually global. There is only one database, accessible to everything. I suspect that there are logical programming systems that allow for more restrictions to be placed on modifications, but this is true for ISO-standard Prolog.

So why did I just blab on about state? The code I'm looking at uses it...a lot. It's Java, but it's written in more of an imperative style. Oh boy...

Recursion

In my personal experience, recursion is a topic that takes many students aback. It certainly knocked me over at my first few goes at it. Why?

Of course, this portion is a monologue, so such questions are purely rhetorical. I'll answer it for myself. For all these reasons, I learned recursion to be an evil thing:
1.) It's more complicated to understand than iteration.
2.) Anything recursive can be expressed iteratively with a stack, so there isn't any point.
3.) It uses more memory than iteration, to the point where you can eat the entire stack.
4.) It's slower than iteration.


Wow. What a useless feature. The original FORTRAN got it right when it didn't allow it. What? There are entire paradigms that discourage iteration in favor of recursion? They must be awful.

Ahhh! This was seriously the type of instruction I've received from three different instructors. I've heard similar experiences from other CS students. It seems the CS people tend not to like recursion.

But then, one fine day, a math professor of mine decided to explain recursion. In 20 minutes. I didn't think it was possible. Past instructors of mine typically spent a week on the subject, and even then no one understood it. I prepared for the worst.

The professor began by writing down the first few terms of the Fibonacci sequence. He talked about it a bit, then wrote down how to arrive at any term:
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

That was it. There was no writing out a call stack to get the correct sequence to generate F(5), or explanation of how the functions are exactly are going to return their values. It's math; what's a call stack?

With this example, I got recursion. There are one or more base cases, and a recursive case. As long as you can reach a base case from the recursive case, it will eventually terminate. The problem with all my previous instruction is that it absolutely focused on the nitty-gritty, all the tiny details needed to arrive at a solution. Of course recursion sounded terrible in this construct. When you get that low level, you completely take away the declarative nature of recursion, reducing it to something imperative. Worse yet, all my CS instructors would explicitly go through every recursive call. This is tantamount to needing twice as much time to explain "for 0 to 10" as opposed to "for 0 to 5".

In this way, I feel that my first point is just plain completely untrue. This feeling is an artifact of how it has been taught. Personally, I feel that recursion tends to be easier to understand, and often requires less code. The base case often doubles as a catch for edge conditions, such as an empty list or null (which are common base cases). Additionally, recursion tends to flow more naturally with my thought process. Take the car-cdr design pattern, wherein one processes the head of a list, then recursively processes the rest of the list. With recursion, I first write out my processing logic, then pass off the rest to a recursive call. With iteration, I first have to worry about setting up a loop to go over the list, then write the processing code. I have the short-term memory of a goldfish, and halfway through writing the loop syntax I often forget about what processing I need to do.

Now for point #2. It's absolutely true. Recursion uses the call stack as an implicit stack, as opposed to an explicit stack. However, keep in mind that if iteration is used instead of recursion, one must then manipulate the stack. There must be extra code for a stack somewhere, and processing logic is going to be cluttered up with push/pop calls. The recursive version will almost assuredly be less code, and require less mental overhead to understand. There is just plain something elegant about a recursive DFS on a tree.

Ahh yes, points #3 and #4. Performance is the mind killer (no, I have no read Frank Herbert's Dune, but I hear it's excellent). This is a definite maybe. A maybe elucidated via a cute little exercise/tangent.

Consider the factorial function (!). As a reminder, 4! = 4*3*2*1 = 24. Consider the following iterative implementation, where N is the number to get the factorial of:

int result = N;
for( int x = N - 1; x > 1; x-- ) {
result *= x;
}
return result;

This seems to work. Except for one little bug: 0! = 1, and this will return 0 on that input. Drat. You could probably rewrite the code a bit to make this slip through ok, but the simplest thing to do is to check for it like so:
int result = ( N == 0 ) ? 1 : N;

Darn edge cases. But wait, recursion can actually use edge cases as part of the main logic. So here we have a recursive definition, in LISP:

(defun factorial (N)
(if (= N 0 ) 1
(* N (factorial (- N 1 )))))

Cool. That's a bit shorter, and it actually uses that pesky edge case as a base case. This take advantage of the fact that N! is really N*((N-1)!). Eventually, N-1 will be 0, which is the base case.

But the careful reader notices that this isn't the same as the iterative definition. The iterative definition uses a constant amount of memory. However, this uses an amount of stack space linearly proportional to N. N must be decremented until 0 is reached, at which point all the multiplications occur as individual calls return. Not only does this eat up stack, it's going to take time to unwrap all those calls. Recursion sucks!

But wait! What if this definition were tweaked a bit, like so:
(defun factorial (N)
(factorial-rec N 1)
(defun factorial-rec (N accum)
(if (= N 0) accum
(factorial-rec (- N 1) (* N accum))))

This accomplishes the same thing, but there is a twist now. The decrementing and multiplications occur before the recursive call is made. Each call doesn't need to store any local variables, because they will not be used after the recursive call is made. This is called tail recursion, where the last call made by a function is the recursive call. In the previous implementation, the multiplication was the last call. By utilizing an accumulator that stores the answer as it is processed, one can achieve this.

If your language is smart, it will notice this, and perform a tail recursion optimization on it. (By smart, I mean read the manual. Most functional and logical languages support it, including ANSI-compliant Common LISP implementations, Scala, and Prolog.) This means that internally the code will perform an imperative style goto to the top of the function, as opposed to an actual call. This causes the function to use a constant amount of stack space, although it looks and feels like recursion. If this happens, then points #3 and #4 are null.

"But that used just as much code as the imperative definition!". Yeah, it did. Plus, the imperative definition is a tad easier to read. I said tends to be more elegant, not always.

I'm not saying that recursion should be used for everything, I'm saying that it tends to be underutilized due to improper instruction. In a language that doesn't support tail recursion optimizations, anything that can be made tail recursive should be expressed iteratively anyway. Points #3 and #4 are big, and if your language can't do it for you then usually you're out of luck. (One exception to this is amazingly FORTRAN; see http://www.esm.psu.edu/~ajm138/fortranexamples.html.) Understanding and using recursion is vital for anyone who does a significant amount of programming, and it's not really possible to get into functional or logical programming without it.

Code Line Numbers and Productivity

What sparked this post was a homework assignment of mine for a class on artificial intelligence.  We were instructed to write a program that could solve instances of Knuth's conjecture (more info at: http://www.perlmonks.org/?node_id=443037).  That is, given a certain positive integer, it would produce the series of mathematical operations necessary to transform 4 into that integer.  We were to use breadth first search, and had our choice of Lisp, Scheme, and Python.

Initially, this sounded like a lot of work.  I have implemented solvers like this for similarly simple problems like this in both C++ and MIPS assembly.  In C++, given a good design, the problem takes several hundred lines.  I assume it would be shorter in a language with a garbage collector, perhaps Java, as a lot of the trickiness had to do with memory management.  With MIPS...well, ouch.  That was over 1,000 lines of C that I hand translated into about 3,200 lines of assembly.  Plus, the MIPS was actually only a very simple DFS as opposed to a BFS.  My hands were cramping before I even started to write anything.

I'm way more familiar with Lisp than Python, so I went ahead with that language.  To my surprise, I went from design to completely working code in about two hours.  Stripping out whitespace and comments, it was only 52 lines in the end.  Not only that, the solution it printed was actual Lisp code, which could then be executed to verify that it was indeed correct (it was).

"But it's slow!"  Hmm...not really.  For every number I gave it, it had a solution within a second.  Because of the factorials involved, numbers tended to quickly overflow, which my design would treat as a dead search path.  I'd have to do this in C++ or anything else.  Perhaps I should have used a special data type that can handle arbitrarily large numbers, but this was just a toy.  Plus, I could have improved its performance significantly if I had used destructive list operations as opposed to nondestructive ones.

I would really hate to implement this in a more traditional language.  Printing out actual executable code would require much more work than in Lisp.  (For comparison, in LISP, say there is an expression E that has generated the previous number.  Say that square root is used to get the next number.  Adding square root to the previous expression is simply `(sqrt ,E), which returns a new expression that is square root tagged on to the old one.)  Let me translate: more code.  More code is more lines.  People often somehow translate this to better or more productive.  It's not.  It's just foolish.

I have two projects that have my name tagged on them that have passed the 10,000 line mark (note that my code/comment ratio is around 50/50, so 5,000 is a better estimate).  One is in Perl, and the other in Scala (a functional language with striking similarity to Java).  Without going into detail with what they are, rest assured that the Scala project is far more complicated, and it does far more.  (A little more detail is that the Perl project is a Web interface over a database, and that the Scala project is an implementation of my own programming language).  With the Perl project, a significant amount of my time consists of actual coding.  There is very little thought involved; much of it is self-explanatory.  The limiting factor of that project is how fast I type.

The Scala project is the complete opposite.  For that, I have dozens of pages of notes describing design and thought processes.  The limiting factor for that project is my imagination.  For example, I spent two days trying to come up with a routine that ended up being around 100 lines.  After I wrote the code for it, I stared aback at it for 10 or 20 minutes, flabbergasted at what just happened.  I exploited multiple language features of Scala that are just plain not often seen, both in terms of traditional languages and traditional thought.  I took full advantage of recursion, anonymous functions, closures, and pattern matching in addition to the more traditional objects.  The code was clean, made sense, and it worked the first time.  The difficult part was not the code, but the ideas that went into it.  I was making the language do the work that normally my fingers would have.  100 lines in two days?  It can be a lot more than you think.

Don't fall into the trap of equating line numbers with effort!  If I had a job that I was paid by the line, I would implement everything in assembly.  I'd be rich, without having much of anything to show for it.

Arsenic(?) Bacteria

Recently, a strain of bacteria was identified in Mono Lake, CA that could supposedly use arsenic instead of phosphorous.  The media immediately jumped on this, reporting all sorts of miraculous sounding things.  I start this off with a list of things that the media misreported or misinterpreted:

1. The discovery wasn't an accident. It has been previously theorized that arsenic could be used. To test it, they found an environment with a lot of naturally occurring arsenic, scooped some stuff out, and looked to see if anything could grow on an arsenic diet.
2. Arsenic and phosphorous behave very similarly chemically. Arsenic compounds just tend to be less stable than the phosphorous ones.
3. It grows much faster with phosphorous than with arsenic. In other words, it prefers phosphorous.
4. It does not appear to be able to differentiate between arsenic and phosphorous.
5. It appears to create an internal microenvironment in which arsenic just happens to be more stable than it usually is. This microenvironment is characteristic of this bacterial species, including strains that are not known use arsenic. In other words, the arsenic usage ability is tagging along with something else it needs, so it's not all that different.

Assuming the bacteria really do use arsenic, I'm just not too impressed.  A quick glance at Wikipedia shows that Mono Lake formed about 760,000 years ago.  The lake has no outlet to the ocean, which has allowed dissolved materials to remain trapped in the lake.  This normally refers to salts and alkaline compounds, but the same goes for arsenic.  This bacterium did not suddenly grow accustomed to arsenic over a course of mere decades due to human pollution, but rather it was gradually exposed to slowly increasing levels of arsenic over a long period of time.  I'd be impressed if it were only such a short period, but given the amount of time this adaptation is not unreasonable. 

Again, this is all assuming that the bacteria really do use arsenic.  Quite frankly, the evidence is not too convincing, which has been pointed out elsewhere.  I don't have a deep background in chemistry, but I am familiar with a few of the techniques that were used in determining if the bacteria use arsenic.  One of these techniques is a phenol-chloroform extraction, which is commonly used to separate out different parts of cells based on polarity characteristics.  Portions with certain characteristics congregate into one of three portions of a solution.  It looks much like a mixture of oil and vinegar that has been allowed to sit for some time; there will be a distinct separation of the two.

After performing this separation on cells, they determined how much arsenic was in each portion (well, sort of.  More on this below).  Table 2 of the paper confidently says "Chloroform (lipids)", and says how much arsenic is in this portion.  However, many more things than lipids can dissolve in the chloroform layer.  Additionally, some of the numbers have extremely high standard errors, as with 1.5 +- 0.8 for the aforementioned value.  The use of this simple technique along with such high error suggests to me that the paper was rushed out the door, and further examination could reveal otherwise.

There is an additional problem with the phenol/chloroform extraction.  There is nothing to compare these values to.  These values measure the percentage of arsenic found in the given portion, not the actual amount.  Being that my own body contains trace amounts of arsenic, my own cells could very well have the same percentages.  In fact, being that both my own cells and these bacterial cells cannot differentiate between arsenic and phosphorous, they likely do have similar values!  It would be nice to have these values compared to some sort of control to see if there really is anything special going on.  There are some bacteria which can live in arsenic-contaminated environments by actively pumping out arsenic or otherwise detoxifying it, which would have made great candidates for controls.  After all, with such behavior one would expect different percentages for arsenic.

In conclusion, I'm just not impressed with either the bacteria or the paper's methods.  I can understand the need to publish a discovery like this ASAP, but I fear that someone jumped the gun before we can say for sure.  If these bacteria are not actually using arsenic but are merely very tolerant of it, then this could become a major embarrassment.  For such dramatic findings I would expect dramatically conclusive data, and I'm just not seeing it.