Regularly Expressing

Month: May 2007

  • Regular XML Expressions

    I have been toying with the idea of a specialized regular expression syntax for XML. Often, the regular expression questions that people email to me indicate that they are using them on XML and HTML. There is a very nice discussion of part of the problem here on Joe Gregorio’s blog. On that blog, he considers solving the problem by trying to limit XML, but I think the problem may be that the Regex needs to be adapted.

    Ideally, I’d like to write a pattern as simple as <a>(.*)</a> and match it against an XML document, retrieving the text inside an “a” tag.

    How should this work?

    1. CDATA sections: If we have a Regex parser that works on a stream, the stream reader can disentangle this bit for us
    2. Comments: We don’t want to match on a tag if it is in a comment. The pattern <a>.*</a> should know how to identify and ignore comments. Of course, we might want to match something inside a comment. If that’s the case, then our pattern should explicitly say so. It should look like this: <!--.*<a>.*</a>.-->.
    3. Matching nested blocks: <root><a>bar</a><a><b><a>foo<h;/a></b></a></root>. Obviously neither <a>.*</a> nor <a>.*?</a> is quite the right thing if we expand .* according to standard regex rules. Our xml regex could be taught to understand what tags are, and how they nest.
    4. If I write a regex to match <a>.*</a> I want it to match <a x='smile'>foo</a>. If we want to require that a certain argument be present we could specify as follows: <a x='.*'>.*</a>. If we want an element to not be present, we could write this: <a x != '.*'>.*</a>. If we want the tag to have no elements, we could write this <a '.*'!='.*'>.*</a>
    5. I should not need to specify the quote character. Matches should work regardless of whether single, double, or no quotes (HTML) are used. Escaped quotes could be used to identify the quote character if I do care: <a x=\"foo\">.*</a>
    6. Extra white space should not matter: <a> should be the same as <a >.
    7. Flags could be provided for ignoring prefixes, allowing <a>.*</a> to match on <root:a>narf</root:a>
    8. When searching text, it should be possible to ignore <b>, <i>, <em>, <font> tags that are mixed into the text. I want foo to match against <b>f</b>oo

    What else would a tool like this need?

    Is it necessary? Are existing tools like XQuery and Beautiful Soup sufficient?

  • The Coming Intelligence Explosion

    The Singularity institute has a post describing what it calls the upcoming “inteligence explosion.” The concept is that once we learn to start modifying the brain to make ourselves smarter we get a positive feedback loop — more intelligence gives us the ability to construct a better human/brain interface, which makes us smarter, which makes us able to construct a better human/brain interface, and so on.

    Where will it lead? There is a difficulty here which I can’t help but notice — allow me a digression. An animal like a giraffe does not evolve simply by natural selecting creatures with slightly longer necks. As the neck extends, a number of mechanisms must simultaneously evolve to deal with the increasing blood pressure. I can’t help but wonder if simply extending our intelligence might be as disasterous as simply extending the neck of the giraffe. Will it increase at the expense of our sanity? Will we re-create ourselves as ultra intelligent but psychotic entities — reminiscent of Lovecraft’s Elder Gods? Or will we manage a slow and careful progress that will accomodate the changes. (Of course, there’s at least one sf story idea here, with lots of juicy references to the Tower of Babel)

    All this brings to mind Frank Tipler’s “Cosmological SIngularity,” and will be debating this topic on June 3. I did not realize Tipler was just down the road from me at Tulane. If I weren’t going on vacation that week I would attend.

  • It’s About People, Not Technology!

    I often hear that sf should be about people, not technology. And I don’t disagree. There’s nothing worse than reading page after page of technobable (or watching Trek characters spout it for minutes on end). After all, future technology is really nonsense. But sf/fantasy is not just a story about people with a strange backdrop. I think it is strange kinds of people.

    Sci fi fiction and fantasy present to us characters that have goals and motivations that are unlike any a human would have. The exploration of the psychology of these non-human characters is (for me) one of the most fascinating things about these genres.

    Spock, Data, and Worf are the foundation of the Star Trek empire. The humans, by and large, were far less interesting. Of these three, perhaps Worf was the closest to human — we can all identify with someone who is cranky all the time. These characters alternate between human and alien. This allows you to identify with the character and then makes it possible for you to be carried in to its more alien mind. An episode of TNG, in which Data tries to start dating, draws us in as Data’s motives and actions in seeking romantic companionship seem quite human — but at the end when his girlfriend breaks up with him he is not even bothered.

    Another interesting aspect of sf/fantasy characters is what I call “the hidden character:” a person in a place where you don’t expect one to be. In this regard we have Solaris, the illusory soldiers from John Carter’s Warlord of mars series, the lava creature in episode 26 of TOS, and Professor Moriarty in “Elementary, my Dear Data” from TNG, and probably many others.

    But let’s come back to the idea that it is about “people” not “technology.” Certainly this line is blurred if we are talking about Hal or Data. But this is not the only way that it is blurred.

    Technology, or some relevant bit of magic, can completely transform a society, changing the normal behaviors and motives of people. Indeed, utopias of various sorts are a common theme in sf/fantasy. A big part of sf/fantasy is the exploration of how new technologies and abilities change us. One of my favorite books is “The Mote in God’s Eye” by Larry Niven and Jerry Pournelle. In this book, the Motie race itself is essentially a character.

    So, for all you science fiction and fantasy writers or wanabees out there, it is not enough to remember that it’s about people and not technology, you have to consider how the sf or fantasy elements change your story. That is what the rest of us find the most memorable.

  • Orion’s Twins:

    Recent pictures of Orion with the Spitzer Telescope are telling us more about the science of star formation. I think a region of active star formation might have interesting story possibilities. Imagine two similar star systems, formed at about the same time, from similar materials — possessing a common seed of life carried in the wave of debris from the explosion….

    In evolution and development the races that evolve on the two worlds are similar, but in pschology they take opposite roads: One follows a severe rationalism, the other an elaborate spirituality — each imagines that it should be superior to the other, but each finds a similar amount of bloodshed in its past and each has similarly advanced (but different) technology.

    Each race has also failed in similar ways: The spiritual race has made meager use of its stunning mathematical ability, and the rationalistic race has suppressed and feared its latent psychic ability.

    But when a demonic race attacks the spiritual world the two must work together to fight off an invasion that threatens both of them, they must each look past their own self deceptions for the truth that will enable them to survive.

    Pre-order your copy now! 🙂

  • Proof of God, DNA, and Drake

    A number of proponents of “Intelligent Design” attempt to show, possibly using the Drake equation, that the occurrence of intelligent life anywhere is extremely unlikely, that a miracle would have been required to create us, to explain our existence.

    I can’t help but think this backwards. Doesn’t this argument show that we were not part of the design but something added afterwards?

    Let’s approach the problem from a different direction. What is the mark of intelligence? What is the clearest evidence of its presence? Language. If in future times we explore other stars and chance upon a book we will know with certainty that an intelligent race produced it.

    But there is more than one kind of language. We develop languages for different purposes: speaking, writing, and even communicating with our machines. This last type of language is called a programming language, and at its fundamental level it is a linear sequence of binary data.

    Now consider DNA. It is a programming language for life. It is base 4, not base 2 like our programming languages, but this difference is trivial. (although the density of genetic material is also important) The fact that it comes in strands makes it even more similar to a book or a linear seqence of program instructions.

    Where does DNA come from? While we don’t yet know exactly how it is created, simulations of planetary atmospheres suggest that nucleic acids can be formed there by fairly natural processes. Can these components, and strands of DNA or RNA themselves, can come about on their own as a consequence of the laws of physics themselves? Let us assume that this is so.

    If language signifies intelligence, and DNA is a language written in the very physical laws of the universe, then we argue that there is a primeval intelligence who is the author of those laws: God. I would say that DNA and evolution should form the backbone of the Christian argument for design.

    If this reasoning is correct, life should be relatively common in the universe. Perhaps discoveries like the habitable world Gilese 581c are our first steps to verifying this hope. Of course, we should not be too narrow minded in our consideration of what a habitable world is, as some bacteria can live without water and little oxygen in a tar pit, and some grow faster in the presense of ionizing radiation.

  • Using Brown Dwarfs to Make Smoke Signals

    This article from PhysOrg says that brown dwarfs may be like light houses, emitting beacons of strong radio pulses. An appropriately advanced civilization might be able to manipulate such an object (if it were within its solar system) to send a “we are here” message, getting a tremendous boost in signal strength from such a natural radio powerhouse.

    My first thoughts centered on the use of magnets to deflect the beam, wondering if they could be built to make adequately large deflections in the radio signal to send information to distant stars. A colleague of mine, Dr. Zink, suggested that instead a large net of conducting material could be used to deflect the beam, something where the size of the mesh would be appropriately comparable to the wavelength of the signal. Certainly this net would be much easier to construct, possibly this would not require much more advanced technology than we currently have.

    If such a signal house were constructed by aliens, they could do far more with it than send a “we are here” message. They could use it to send messages to ships taking a long slow journey between the stars, or to communicate with a distant colony.

    On occaision, SETI does find possible signs of alien life. And they are building more and more powerful radio detectors. If there are aliens, and they make use of such a radio light house, we may be able to see them from very far away indeed.

  • Coding Conventions

    It is important to follow standard naming conventions when writing code. It increases clarity and readability. Thus, in the "Elements of Java Style," we are told to capitolize class names but not function names, etc. A recent elaboration on this basic idea was put forward by a colleague of mine (Adam French) and his associate (Andrew France).

    The suggestion is that, in addition to other style considerations, your object oriented code should operate as follows:

    1. All variables should be named after Star Wars characters.
    2. All function names should be named after Star Trek characters.
    3. All classes should be named after Lord of the Rings characters.

    Coding in this fashion will, obviously, require great discipline and nerdity, but in the end the resulting clarity will bring many rewards. And if you are planning to become ISO 9000 certified, remember to document this procedure.

  • The Matrix Refactored

    The first two Matrix movies were quite fun — despite the rather strange and improbable premise that humans make good batteries. However the third movie was quite disappointing. In the software development world, the process of revising your software to make it better is sometimes called “refactoring.” This suggests to me the title of a new Matrix movie, “The Matrix Refactored.”

    The Matrix series raises a number of questions about the borders of reality and machine world, and introduces a number of mysterious entities. By the third movie, I expected some explanations of what was what. Alas, I got none.

    1. Consider the program called “The Merovingian.” Many people currently believe that the Merovingians are the descendents of Christ and Mary Magdalene. Whatever you think of the historical merit of such an idea (I think it is rubbish), the name of this character suggests that he is a child of the One, a program authored by Neo in a previous iteration of the Matrix. In my version of the Matrix, this idea would have been developed.
    2. When Neo confronts the Architect in the second movie, he sees recordings of previous confrontations he has had with that entity. If he always looks the same, then why can’t the Architect and the agents use that to find him? Why is there a “One” in each iteration of the Matrix? What I would suggest is that the Architect and the Oracle are two AI programs that are playing a game against each other. The Oracle decides to seed the vats with DNA, deciding where to hide the One. The Architect uses the agents to try and stop him — sort of a giant shell game. I would have had Neo discover this fact.
    3. Neo is able to use his powers to stop the squids when they are not in the machine world. This suggests that either he did not really leave the Matrix, or that there is a Matrix inside the Matrix, or that reality itself is, at some fundamental level, nothing but a program. Maybe Neo has control over machines through some radio link. I would have tried to preserve the ambiguity here, pointing to “love” as a deeper reality. But “love” becomes it’s own item in this list….
    4. One of the themes of the first two movies was that love conquers all. Both Trinity and Neo were brought back from the dead by love. In the third movie, however, we get the horrible “love is a word, and I have a relationship to it” speech — followed by the death of Trinity. I would have given this speech to the agent, or the Architect.
    5. They could discover a space station, Nirvana, was built before the machines took over, and that it is still functional. Persephone (as her name suggests) would be the one program that spends time on the station and on Earth, and she could arrange a rendezvous by which Neo, Trinity, Morpheus, etc. can escape to Nirvana and escape the cycle of the Matrix.