Thursday, February 18, 2010

The Not-Understanding Perceptron, and the Grim Shadow of the "Average Man"

... and if you're too intelligent
they'll cut you down to size;
they'll praise you till you're happy,
then they'll fill you full of lies ...


"Cradle to the Grave", album of the same name, Subhumans (1983)




A friend of mine came up to me unexpectedly today, with some obvious concern and agitation. "Can I ask you about something? Could you explain something to me?" he said. I said okay, and he took a piece of paper out of his pocket and began folding it awkwardly back and forth, trying to hide most of the contents while showing me just one small part. Finally, he handed it to me and asked very soberly, "What does this mean?" I looked the paper. It was a score from an IQ test. The score was not good.

It was at that point that I thought about what it must feel like to receive a piece of paper that tells you that you are officially stupid.

I've known this friend for a while. He had a difficult past. He's attending a local community college. He wants to go on to some position where he can counsel troubled kids -- not kids who are troubled about the usual things that trouble kids, but kids who are troubled in a way that's bigger and deeper and harder to articulate, who have been to jail, or will likely end up there soon. He's an honest person. He's a curious person. He works hard. And I could tell that he understood what the paper said, at least in literal terms. I could tell he was hoping, perhaps, that there was some subtle detail of the report that would nullify or at least mitigate the coldly obvious meaning. It was not a question about scales or confidence intervals, even though I explained these ideas at some length so as not to seem flippant or condescending.

There was no way I could just hand the paper back and say, "It means you have a low IQ."

What happened is, I sat back in my chair and said this:

"Look, I don't know much about this sort of thing or about IQ tests or what they're really good for or exactly what they mean. They've been around for a while, and a lot of people have criticized them for a lot of reasons, and they still give them out anyway, but none of that is really the point. The point is that it's all bullshit. The point is that a test score just tells you how well you scored on a test, and nothing more than that. For some reason, we've come to live in a fucked up world where people give us test after test after test to evaluate what use we, as human beings, have to them, as figures of power and authority. It's a bad measure. What's really good and interesting about human beings is how adaptable we are. If we can't do things one way, we can find another. We're never incapable; the only thing we ever lack is persistence or inventiveness. This score doesn't matter. It doesn't tell you what you can or can't do. It doesn't tell you whether or not you'll succeed in life. It doesn't tell you who you are. Those are all things that you determine for yourself. So the meaning is nothing; it's just a test, don't worry about it. Life isn't a test; it's a challenge. It's hard, but there's always another way. There's always a way to live."

Then I handed the paper back, and left.

I sincerely wonder why we insist on so many abstract metrics of people. They may serve an organizational purpose, but they serve no individual purpose, and in some cases even represent and individual harm. Perhaps it's a bit worn and trite to criticize tests and tell people that they can do whatever they want. I acknowledge that not everyone has the same abilities. I acknowledge that some people will try things and succeed, while other people will try things and fail. I acknowledge that we are all stuck playing with the lot we're dealt. What I take exception to is the proposition, implicit in every quantitative metric of a person, that there are only a certain number of clearly circumscribed roles a person may play in life, and all of those can be characterized by a certain number of simple, measurable quantities.

I don't think anyone would dispute the simple proposition that capability is only really proven when the thing is done. Can you write? Write something. Can you fight? Fight someone. Can you think? Come up with an idea. That is all fine and good, but what is often not recognized is that narrow metrics such as standardized questionnaires and puzzles measure only a person's competence in one particular strategy of doing, not that person's overall capacity for thinking, learning, or doing. There is an enormous breadth and variety to the genres of writing, styles of fighting, and certainly to ideas. In the end, the one goal that all of us hold as ultimate is simply to live. As far as I can see, the measure of that is something that we all figure out for ourselves.

I wouldn't be the first person to criticize the IQ test; as far back as Vygotsky and Luria, people were well aware of the influence of a industrialized education on the direction of concept use and formation. The modern practice of measuring by standardized test even resembles, to some substantial degree, the operation of very primitive feature-weighting recognizers (e.g. Rosenblatt's perceptron), which Minksy and Papert famously showed could not even distinguish the presence of such basic relationships as continuity. There is a remarkable synthesis in the way human cognition sees form as function and function as form; one sees it everywhere, in our tools, in our art, in our basic ways of thinking. Batteries of questions aimed at abstracting some particular feature of an individual, however, separate the form of the person from the function being sought. The issue is not one of which kinds of intelligence we should measure, or which quantities are really important in determining health, fitness, or success. The issue is that the measurement of finite quantities is a procedure fundamentally insufficient to the task of determining what we should do with ourselves, or how.

If that sounds like a trope or a triviality, stop and really imagine for yourself how exactly would it feel to receive an scientific report documenting how stupid you are.

One of the really interesting things about being human is that we make purposes and meanings for ourselves. This is not an inspirational appeal that takes us away from the compelling argument that simple biological impulses underly our lives and activities. This is assertion of the brilliant complexity with which those impulses manifest when placed in a brilliantly complex world. What's amazing is that we all end up acting as differently as we do even though we all start with same small handful of biological goals and directives. A clever strategy can turn a weakness into a strength. Sometimes, the meek really do inherit the Earth, and nobody sees it coming.

Sometimes, however, is not the same as always. Sometimes the test speaks the truth. Sometimes might is right. Possibility, however, is an essential organizing principle of how we think about ourselves and the directions of our lives. To borrow notions from the cognitive scientists, our identity is fundamentally tied to a self-ideal, that is, to a persistent thought not just of who we but who we want to be. Without the ability to imagine possible selves and possible futures, the whole sense of self collapses. If tomorrow's outcomes are all completely and fully known today, there is no human sense in bothering to live them all out. (This assertion is pregnant with all kinds of epistemological interpretations.) Of course we need to know, in plain, unsparing terms, how the world is. Of course we need to know, frankly and directly, what our weakness are. But each of us, if we are to go on living at all, also has to be able to imagine better.

I have an above-average IQ. I know this because in fourth grade I went to a quiet, out-of-the-way room in my school and took a strange-looking test, after which they sent me to a so-called "gifted program" once a week. There, we got to do things like tinker with fractal-generating computer programs and assemble-your-own-robot kits. I liked the things we learned, and I liked the absence of the overbearing regimentation that pervades ordinary public schooling, but to tell the truth, I never liked any of the other children there. They all knew that they had taken a test, and that adults approved. They knew that they had been declared officially intelligent. As such, they were all filled with insufferable smugness and self-satisfaction. Knowing that they could do things to please adults, they competed viciously among one another for praise and attention. Based on my later contact with intelligent, talented, and highly educated persons in my adult life, these are features that, I am almost certain, many if not most such children retain for the rest of their lives. Knowing that you have been blessed with "the gift", it is difficult to resist fascination with your own wonderful ability. Having this fascination, it becomes difficult to arouse much interest in what your work means for the other humans you share the world with, what shortcomings or limitations you might have despite your talents, or what people without "the gift" might think or have to say. Having a belief in your own excellent function, you lose the form of yourself as human being, with all the frailties and blights that entails.

Blame or praise only really help when they suggest new directions. There is no "good function" or "bad function", only "good for this" or "bad for that". The only real function is to live out our lives, and that is something we do in whatever way we choose. So what if you have a low IQ? Human chess players are helpless to beat powerful chess playing algorithm, but people still play chess. The joy of a game is just in the playing; in just the same way, the joy of living is not in solving any single problem, or meeting any one goal. So what if you have a high IQ? Your shit still stinks, and somebody still has to clean it up. The world is unimaginably huge and complicated, but everyone has a place in it. Contrary to some opinions, there is no placement test to tell you where.

Saturday, February 6, 2010

Implications of Universality for Computer Security

"In the United States (U.S.), we have items available for all our needs. Many of these items are cheap and easy to replace when damaged. Our easy-come, easy-go, easy-to-replace culture makes it unnecessary for us to improvise. This inexperience in 'making do' can be an enemy in a survival situation. Learn to improvise. Take a tool designed for a specific purpose and see how many other uses you can make of it." (U.S. Army Field Manual FM 3-05.70, "Survival", May 2002)

One of the most noteworthy features of computer security is its overwhelmingly defensive stance. While there are certain programming practices that mitigate threats (e.g. sanitize your inputs, check your array bounds), it is practically impossible to preclude all possible attempts to corrupt or co-opt a system. Granted, there are always a few stubborn hold-outs willing to step forward and claim that the system that they have constructed is constructed in that elusive "right way" that everyone so far has failed at. It's possible that one of these people may be right, but evidence seems to weigh against such claims.

All the way back in 1993, a landmark report from the Naval Research Laboratory [3] found that almost half of 50 serious security breaches involved code that correctly implemented its specification. Of course, that was well over 15 years ago, and so one might protest that perhaps some better model of security has come forward since that time. Even so, one has to take notice when large teams of talented programmers correctly implement a meticulously specified system, and the system nonetheless succumbs to attack. Cases such as this lead illustrious security researcher William Wulf to call for a revolutionized approach to security that abandons the old paradigms of "perimeter defense" [7] as late as last year. Wulf proposes a model of security inspired by the success of the Internet, wherein a small foundation with minimal but very general functionality allows for systems to adapt to localized and quickly evolving conditions as needed and desired. This seems a very pragmatic and promising approach, and the success of the Internet is nothing to sneeze at. Even so, one cannot help but wonder what exactly it is about the traditional way of doing things that leads it to fail.

Let's consider a very intuitive idea from the traditional theory of security. Noninterference is a rather early and very successful idea due originally to J. A. Goguen and J. Meseguer [2] that can be informally phrased as follows: if two users (or processes) share a system, then the action of one should have no effect on the other. In some sense, this is like what we would expect in many kinds of situations where security is important: if you're on a time-sharing system, you don't want your files, or what you do to them, to be visible to other people; if you're buying something online, you don't want the credit card number you send to the vendor to somehow end up on the computer of some third party not part of the transaction. Of course, such assurances are very hard to make on large systems that a lot of people use; it would be pure whimsy to suggest that one could ever make such an assurance about the Internet (especially considering that large-scale data mining by merchants and advertisers already counts, arguably, as producing unwanted side-effects), and it would even seem like a bit of stretch to make absolute promises about a large, practical system that a lot of different people had to use to readily exchange information. However, suppose that someone were to successfully construct a shared system conforming to Goguen-Meseguer noninterference; if we were really that confident in its conception and construction, we could be assured that no one would be meddling in anyone else's data, nor would the kernel be unwittingly divulging any secrets to attackers bent on trying to compromise it.

Here's the catch: even a perfectly conceived and constructed system has to interact with the rest of the world in order to be used by anyone. This of course introduces the vector of social engineering, whereby the human element becomes part of the system. Even so, we don't have to rely on operator fallibility to show how problems immediately and essentially arise once the theoretical construct is out of its own solitary universe. One such very simple and very clever example is due to Daryl McCullough [4], and works essentially as follows:





Imagine we don't want any information flowing from the red parts of the system to the blue parts, although blue-to-red is okay. (This is indicated by the directions of the arrows.) Considered separately, the blue and red parts of the system both satisfy noninterference, since the red portion consists only of a single process, while the blue portion is defined in such a way that its two processes never interact. Does the entire system obey noninterference, once its parts are put together? It turns out that it does not.

The reason for this comes from a subtle but important detail of machines, namely, their finiteness. Suppose that processes A and B fill up their respective input buffers -- which they certainly can do in any kind of realistic machine. Should they start throwing away messages, or should they wait? We don't want to lose any messages, so we insist that the processes wait once their respective buffers fill up. However, in order to know to wait, the buffer or some mechanism attached to it must be able to send signals back to its process, telling either to go ahead or wait. That is, we want our processes to perform blocking reads and writes on the buffers, wherein their execution is suspended until the necessary read or write becomes possible. Now suppose, that our red process has a one-bit input from S that is uses to decide which of buffers A or B to read from, i.e. red multiplexes A and B according to the input it receives from S. The red process waits until acknowledgment arrives in buffer C before reading the next input from S. Suppose processes A and B immediately fill their respective buffers; once our red process reads from one of them, the buffer will have space for a new message, and will signal back to its respective process that it can go ahead with its execution. This is all good and fine and perfectly reasonable. What's the problem? The problem is this: suppose also that A writes some innocuous notice to the output on the left, say '0', each time it sends to buffer A, and that B writes '1' to the same source each time it sends to buffer B. Why is this problem? Because, given this setup, the stream of bits being written to the (blue) output on the left now exactly matches the stream of inputs being read from the (red) input on the right, which is precisely what we did not want to happen.

One immediate conclusion that one can draw from this result is that some security properties simply are not composable, that is, even if two different systems exhibit the property, there is no guarantee that putting them together will result in a system that exhibits the same property. However, I think that there is another informative way of looking at what's happening in McCullough's example: connecting the blue to the red system gives the blue system an opportunity to emulate red.

Emulation is an idea that goes all the way back to Alan Turing's universal computer. In essence, one machine emulates another whenever it performs computations equivalent in rule and structure to another. This is what gives Turing's machine its universality; it has the capability to emulate any of a very large class of other machines, and hence to perform any computation of which any machine in that class is capable. Chip developers use emulators to test against design errors. Nostalgic gamers use emulators to play titles from long-defunct platforms on modern personal computers. Interpreted programming languages (e.g. Java) use an emulated abstract computer to achieve some measure of portability. However, the basic principle that one machine (or tool) can serve in the stead of any of large class of others seems to me much broader and deeper than any of the niche purposes to which it has so far been put, especially as regards security.

Most prisons in the United States place rigid constraints on what sorts of items prisoners are allowed to keep in their cells. The reason for this is that a small piece of metal or a hard, sturdy object can easily be improvised into an excavating tool or a weapon, given the proper motivation -- of which prison inmates typically have an abundance. Ingenuity in making and using tools is one of the distinguishing and noteworthy characteristics of humanity, and the dramatic success of the tool-weilding primate is a testament to the power of a usable tool, however crude. This is not a new or surprising observation. However, it is truly astonishing to observe the huge disparity between the smallness of the means necessary to cause a disruption and the explosive magnitude of the disruption itself. Who would have ever imagined that using a bludgeon instead of fists and teeth would have catapulted humans to the position of dominant predator, or that millennia later those same humans would be improvising artifacts for personal hygiene into deadly melee weapons?

What we have here is a very broad principle. How does it apply?

A number of attempts were made during the 1960s and 1970s to construct a universal Turing machine with the smallest number of possible states; Marvin Minsky constructed one with only 7 states and 4 symbols in 1962 [5]. Successive attempts collected and published by Yuri Rogozhin in 1998 produced at least one smaller machine. In 1985, Stephen Wolfram claimed that his famous Rule 110 one-dimensional cellular automaton was able to emulate a Turing machine with only two states and five symbols, sketching a proof in his widely read and controversial 2002 opus [6]. Though such constructions always give some whiff of obsession with arcana, they also give very concrete evidence of a genuinely startling conclusion: it takes very, very little in order to make almost anything possible.

This should be a very potent lesson for the discipline computer security. Systems can be very tightly walled off from the rest of the world, but it takes only a very narrow gap for an attacker to worm his way in. A first reflex is to try to wall off the system even tighter but this, ultimately, turns out to be a failing solution: one can only constrain the system's use so much before it becomes completely unusable, whereas the attacker needs only the slightest concession in order to devise an exploit. This seems to confirm Wulf's argument that a pitched battle over the integrity of a rigid boundary is doomed to defeat. However, it also gives a potentially very useful language in which to phrase the problems of security. Consider the following informal conjecture:

If a system S allows its users functionality F, then S is vulnerable to an exploit E if and only if F is computationally expressive enough to emulate E.

This is plainly visible in McCullough's construction above; the blocking signal from a full buffer gives the blue portion of the system exactly enough information to act as if it were reading off of the secret input buffer. Erik Buchanan, Ryan Roemer, and Stefan Savage presented a method of constructing exploits without the use of code injection (which I also cited here several months ago) at Black Hat 2008 [1], which seems to confirm this very same intuition. The authors showed that subverting normal control flow was sufficient to coerce "trusted" code into arbitrary computations, thus producing "bad" code without the need to introduce any new code.

Explaining security breaches in terms of "emulating your inferiors" also provides a graded metric of susceptibility. (This may be useful if it turns out that Mr. Wolfram is indeed right and the world is rife with computational universality.) If one system is capable of emulating another, then the time complexity of the emulated computations will always differ from those of the native, non-emulated computations by a constant factor. However, a given system may be better suited to emulating some systems than others, and the program required to set up the emulation may be substantially more or less complicated. A rock might serve as both a hammer or a crude knife, but it makes a much better hammer than knife; an actual knife, by contrast, can be improvised to a wide variety of very practical purposes. The same is undeniably true of computational systems; although the Rule 110 automaton can emulate a Universal Turing Machine, and that universal Turing Machine can emulate the operation of the latest multi-core processor running your favorite operating system, the time performance of your system would decrease by a very large (but nonetheless constant) factor, and require quite a bit of memory besides. In the same vein, dynamic database access through a webpage makes it relatively easy to steal privileged information from the database because (if the website is badly designed) the user has the chance to pass arbitrary SQL queries to the server, but would be much more difficult (by itself) to leverage into an attempt to seize control of the operating system kernel.

Malware, then is just software coerced into emulating an unwanted computation; attack vectors are essentially just abstract buses over which the victim machine receives instructions from its attacker; exploits are essentially programs running on a maliciously purposed abstract machine. This is, of course, all highly speculative, but it seems to give an expressive language in which to formulate many of the problems of security, and to tie together many well-developed branches of computer science.




[1] Buchanan, Erik, Ryan Roemer, and Stefan Savage. "Return-Oriented Programming: Exploits Without Code Injection". Presented at Black Hat 2008, slides available here

[2] Goguen, J. A. and J. Meseguer. "Security Policies and Security Models". IEEE Symposium on Security and Privacy, 1982.

[3] Landwehr, Carl E., Alan R. Bull, John P. McDermott and William S. Choi. "A Taxonomy of Computer Program Security Flaws, with Examples". ACM Computing Surveys, 26:3, September 1994.

[4] McCullough, Daryl. "Noninterference and the Composability of Security Properties". IEEE Symposium on Security and Privacy, 1988.

[5] Minsky, Marvin. "Size and Structure of Universal Turing Machines". Recursive Function Theory, Proceedings of the Symposium in Pure Mathematics, 5, American Mathematical Society 1962.

[6] Wolfram, Stephen. "A New Kind of Science". Wolfram Media, 2002.

[7] Wulf, William A. and Anita K. Jones. "Reflections on Cybersecurity". Science, vol. 326, 13 November 2009.

Sunday, January 31, 2010

"The Best Kind of Student Goes and Practices It Assiduously"

Lao Tzu said that when the best kind of student hears about the Way, he goes and practices is assiduously; when the worst kind of student hears about the Way, he laughs in contempt. This is a good statement about learning in general, and what it means to effectively apply one's self to a study -- any study, and every study.

In order to really learn something, you have to really truly make it a part of your self. This is a fine sentiment, except that 'self' itself is such a vague and illusive concept, and so talk of adding parts and pieces to such a thing quickly descends into confusion. Is something a part of yourself because you wish for it? Because you think about it? Because you attribute it to yourself? Because someone else attributes it to you? How much is enough, and how little is not? Can you know it when you see it? The boundaries of the self are so hazy that the metaphor of taking things from the outside and putting them inside simply does not work. Learning isn't an acquisition.

This is what makes Lao Tzu's attributed utterance profound: the best kind of student is the best for the simple reason that he goes and practices, in all the senses of that word. Learning means putting into practice, and what you choose to put into practice becomes a seamless part of the activity that is your life. Learning is doing.

There is a subtlety here, though. When you value you something, you keep it in mind; you don't set aside or casually forget about people you love, ideals you treasure, nor your own certainly your own goals and survival. When any of these things come up, you remember them, and you act in a way that accords with them. Learning is no different.

Hence the importance of the latter part of the saying; the worst kind of student hears about the Way and laughs in contempt. I say this having done things in just this way, many times in the past, and having utterly failed in such cases. This is the acquisitive approach to learning, the one that suppose that the facts are set in place and it is only a matter of taking them and putting them inside of one's brain. When you come out and say it this way, such an attitude sounds utterly false; everybody knows that you have to practice something to get good at it. But if you don't know what it is that you're actually doing, then your actions aren't practice. They're wasted effort. It's easy to go out and engage in a flurry of activity and to call it "practice", but what makes for real practice is a sensitivity to the interplay between what you do and what the rest of the world does in reply. If your practice is just the stubborn application of your self-conceived ideas to the situation your happen to be in, you're not learning. You're insisting. Practice acts, but carefully studies the consequence. Learning begins with questioning, and questioning is empty if no attention is paid to the answers.

When something is stated, it seems obvious. When something is done, it seems hard.

In a short comment appearing somewhere in the middle of "The Society of Mind", Marvin Minsky gives an interesting counter to the question of whether machines have souls. "I ask back", he says, "whether souls can learn. It does not seem a fair exchange -- if souls can live for endless time and yet not use that time to learn -- to trade all change for changelessness. And that's exactly what we get with inborn souls that cannot grow: a destiny the same as death, an ending in a permanence incapable of any change and, hence, devoid of intellect." Mr. Minsky's insight is quietly brilliant: learning is growth, and growth is inseparable from life.

Time passes. Situations differ. Nothing produces harmony by itself, and nothing acts by itself.

Assiduous practice is assiduous living. Our lives are nothing other than the lessons learned from a long dialogue between ourselves and our circumstances.

Sunday, December 6, 2009

All Computation Is Effectful

I had the fortunate opportunity to attend ACM's Symposium on Principles of Programming Languages (POPL) '09 earlier this year, including keynote addresses and open panel discussions by some of the field's most prominent and celebrated researchers. One issue that came up over and over again was the difficult problem of how to handle so-called "effects".

The functional programming community typically uses terms such as "effectful computation" or "side effects" to describe a broad class of things a computer program may do at runtime whose consequences may not be readily apparent from inspection of the program text itself. These may include memory references (e.g. as in the notoriously strange pointer semantics of C), I/O, interrupts, exceptions, and message passing. In certain quarters, there is a long history of concern over how to encapsulate these inevitabilities of useful programming within a language that somehow tames their unpredictability. This is no doubt a worthy motive; programs all of whose effects were perfectly and completely evident in their source code would make programming in general much easier and might even open the door to that elusive and often contentious goal of "formal program verification". A very substantial research effort has gone into solving the problem and the ideas put forward, which are far too numerous to survey here, show a dazzling sophistication. Even so, the fact that the problem of how to sensibly express computational effects is still an active concern of leading researchers is evidence that no work so far has decisively settled the issue.

To understand the difficulty, one must understand the curious notion of "functional purity". Functional programming languages are languages based on the Lambda Calculus, one of the three canonical (and interchangeable) paradigms of universal computation. The Lambda Calculus, originally due to Alonzo Church, expresses computations as the application three basic reduction rules to syntactic objects usually referred to as "lambda terms". Because the Lambda Calculus is a complete model of universal computation, any program that can be executed on a computer can, in theory, be expressed as a term in the calculus, with the "halt state" of the program equivalent in some sense to the fully-reduced form of the lambda term. The basic building block of a lambda term is a "lambda", which is nothing other than a function in the formal mathematical sense of the word "function". That is, a lambda specifies a rule according to which an input value is matched to a specific, well-defined output value. It would be ideal if programs behaved like lambdas, producing a well-defined output for each well-formed input, according to a specific and well-defined rule. Moreover, since lambda terms are composable into larger lambda terms, such programs could be modularly combined, according to traditional software engineering practice, to produce large and useful new programs from smaller, more basic ones, all while preserving the happy property that no program could have more than one output for any given input. This, in essence, is the goal of pure functional programming.

The significance of functional purity is that it leaves no room for unexpected effects. In theory, program execution should proceed according to nothing other than the well-defined reduction rules of the lambda calculus, whence each reduction has exactly one effect, namely, that specified by the appropriate reduction rule. This does not mean that a pure-functional program may not have bugs, only that source of bugs will be restricted to logical errors on the part of the programmer, rather than unexpected interactions between parts of the program. By contrast, a program in a more familiar and more organic language (such as C) may appear superficially correct but cause effects at runtime whose consequences ripple widely through the program with obscure and unintended consequences. However, the more attentive or skeptical reader may object: since any really useful programming language has a well-defined semantics that specifies what any given statement will do, separating a logical error in a pure functional language from a effect-caused bug in an impure language is a distinction without a difference. Any unexpected behavior of a program is a bug, regardless of its origin.

That's not to say that pure functions are not a useful organizing principle. Pure functions capture a basic intuition of how programs are "supposed to" work, producing no more than one possible output for any given input, and doing so according to a clearly specified rule whose deeper implementation mechanics are usually of no interest to the programmer. Moreover, the simple reductions of the lambda calculus make it relatively easy to foresee what a functional program will do, which is a notable contrast to the semantics of non-functional languages which, even though well-defined, may be forbiddingly complicated. It is very telling that even the illustrious Edsger Dijkstra, an unflinching champion of careful and semantically exact program composition, admitted that semantic analysis for even straightforward properties of trivial imperative programs seemed excessively complex[1]. (However, it's also noteworthy that Dijkstra did the analysis anyway.) The idea of a pure functional language certainly has virtues. It is, however, another matter whether these virtues are attainable in practice.

The best-developed and most successful pure functional language yet implemented is Haskell. Haskell enjoys a selection of stable compilers for every major platform, including the Glasgow Haskell Compiler (GHC), which is a commercial-grade compiler boasting numerous useful extensions and the capability to produce native machine code. Programs written in every major implementation of Haskell, however, suffer in most cases from serious performance deficits compared to similar programs in a non-imperative language. Even the official Haskell Wiki notes that "GHC doesn't have any credible competition in the performance department", and suggests that programs written in Haskell may keep pace with counterparts in other languages, but only with very aggressive tweeking and optimization. Haskell depends upon a very complex run-time system that is highly susceptible to memory leaks and greatly complicates formal verification of compiled Haskell code. One might argue, however, that for at least some applications this would be an acceptable price to pay for the straightforward semantics of a lambda calculus. Haskell's purity, however, is in name only.

Arguably, Haskell does not achieve purity at all, but only manages to localize all of its "impurities" to one place. This place is an essential Haskell construct known as the IO monad, where virtually all essential program behaviors take place. In essence, a Haskell program can only make system calls, catch or raise exceptions, or handle interrupts inside the IO monad. This allows the familiar Haskell type "IO a" to act as a wall separating the idyllic garden of pure functional delights made possible by the runtime system from the gritty details of how real programs execute on real machines. One of the chief architects of GHC, Simon Peyton-Jones, famously described the IO monad a giant "sin-bin, used whenever we want to do something that breaks the purely functional paradigm." [2] Peyton-Jones makes a reasonable argument in the same article that simply making the pure-impure distinction is useful in itself, but also acknowledges that contemporary attempts to more completely account for effects prove either too complicated or too inefficient to be practical. Haskell represents the end-product of a tremendous and concerted research effort by a large number of talented people and GHC is surely an impressive technical accomplishment. However, the sheer magnitude of the effort required to achieve even this modest gain toward the language enthusiasts' goal of functional purity makes its shortcomings that much more conspicuous.

There is, I think, a lesson in all this, and that lesson is that there is no promise in trying to capture all the effects. Computers are machines, and machines work via carefully a orchestrated cascade of predetermined physical causes and their expected effects. All computation is effectful computation. I realize that this may be an extremely controversial thing to say, but I feel that it stands on a well-founded principle. The difficulties and idiosyncracies of so-called "effects" all arise from the fact that computers have to be physically constructed, and thus must accommodate the protocols of the circuits that constitute them, must retain their data in some kind of physical memory, and must have some means to communicate with machines and components that are spatially separate. Trying to resist this fact by abstracting away such details is bound to end in abstractions of rapidly increasing complexity and rapidly decreasing practicality.

The motivations for abstraction via programming language are multifaceted and practically compelling. At the same time, not all abstractions are good abstractions. Church's calculus has proven a powerful and useful model of computation, and is theoretically interesting in its own right. However, it is telling that it was Alan Turing's eponymous and much more mechanical "machine" that became the conceptual basis of the first digital computers. The difficulty of a problem often depends upon its phrasing. We can't write programs that consist of causes with no effects. I admit that it's a very broad, very contentious, and very far-reaching claim, but the utter complexity and unusability of attempts so far to account for so-called "computational effects" suggests that perhaps we are trying to answer the wrong questions.




[1] Dijkstra, Edsger. "Notes on Structured Programming." T.H.-Report 70-WSK-03. 1970.

[2] Peyton-Jones, Simon. "Tackling the Awkward Squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell." Microsoft Research, Cambridge. 2001.

Tuesday, December 1, 2009

Something Better: The Essence of Naturalism

I've reflected recently on how the arguments of naturalistic philosophy can be so sound and eloquent and yet be fiercely resisted by so many people. I've also been dismayed the dry, perversely nihilistic view that some naturalists seem to take. Science, however, is a personal and very human endeavor, a fact that is neglected by both the more nihilistic naturalists and their vocal opponents. It is the lack of consideration for this strongly personal feature that leads some naturalists to treat scientific theory as untouchable empyrean truth, and that deters traditionalists from embracing what they see as a world-view that is anesthetic and impersonal.

I had planned out a much longer essay, but for now it seems more constructive to concisely state basic, working principles. A great deal of ink has been spilled on this subject already. What's missing are ideas that can be readily acted upon:





  1. Observe carefully. Truth is everywhere.


  2. Ask questions. Knowledge begins with a question.


  3. Acknowledge the unknown. Understand that assumptions have consequences, and these consequences point beyond.


  4. Be the truth. Apply your full understanding, and act according to everything you know.







Finding and knowing the truth is everyone's business.

To be human means to live in the midst of a conflict between hope and possibility. It's been wisely said that to exist is to suffer. It may be that our uniquely human existence entails uniquely human sufferings such as these. We have the distinct ability to dream up new worries for ourselves, and then to worry ourselves sick over them. We also have the distinct ability to deconstruct our own views and perceptions and thus rationalize away any and all appearances, to the point that the world of our experience is left desolate and bare. Sometimes we see things that aren't there. Sometimes we don't see things that plainly are there. This basic principle leads to a significant conclusion: seeing is not the same as understanding, and not seeing isn't the same as seeing clearly. This principle is widely applicable to all constructed philosophies.

Science has made wide inroads to areas considered the sole domain of mysticism or metaphysics, but even the eloquence of brilliant and heroic thinkers has been insufficient to dispel the unease with which many people regard the proposition that all the phenomena of our experience proceed from basic natural laws. Empirical or logical arguments fail to convince not because they are unsound or their conclusions untrue, but because they fail to adequately replace the practical function of gradually evolved systems of personal belief.

People do not need different theories. People need better ways of theorizing. Science is the acquisition of knowledge, and the acquisition of knowledge should not be constrained to a narrow set of subjects, or particular class of professionals. There is no sense in convincing people to abandon traditional views of God, free will, or humanity's place in the Universe if it only means substituting scientific theories for pre-scientific dogmas. Both represent incomplete views of the world, the distinction being that science puts its fictions to the test. This distinction is crucial but easily overlooked. A theory is nothing but a story whose deeper meaning manifests as a discovery about the world. People embrace traditional views because these views allow them to make discoveries about themselves. They resist naturalistic explanations only when they appear sterile and unable to explain anything new or useful within the scope of their own lives.

What's needed in the reform of all our views is a sincere valuation of the truth, a deep appreciation of what it is and how it is gotten. A close examination reveals that, at the personal level, this is no different from learning and growing as a human being.

It is through fictions that we learn, and knowledge is just the skillful manipulation of fictions. Wisdom is the ability to go beyond fictions.

Friday, November 27, 2009

Thoughts on Control and Proportion

In the common usage, a system is generally said to be "under control" whenever there is some way to act on the system to produce a predictable outcome. This is a perfectly sensible definition, but it makes clear that control is really a matter of degree. Does "outcome" refer to the ultimate behavior of the system, or only certain of its moving parts? Does "predictable" mean that outcomes are foreseeable one second into the future, or one year into the future, or indefinitely into the future?

There are other interesting questions one can ask that may be particular to a system or a class of systems: When control-actions put together serially or in parallel (or in that awkward hybrid of the two sometimes known as "concurrency") are their cumulative results foreseeable, so that large, structured actions can be composed of smaller ones? Do control-actions have an outcome that is constant with time, or does their behavior change, albeit in a predictable way? Do what degree is control of the system susceptible to irregularities of the environment or noise in the input?

Degree, though, seems to be an essential aspect of the notion of control. The things we are typically concerned with controlling are macroscopic and complicated. In those rare instances where we unequivocally succeed in controlling a physical phenomenon (a working machine is one instance of such a success) behavior of the thing may be quite steady and predictable, but still show susceptibility to abrupt, unexpected failures or malfunctions. Friction, cross-talk, ambient vibrations, waste-heat, leaky gates, freak-accidents, and all their like loom threateningly in the background of any working order. Though such entropic can never be eliminated, a successful machine (at least in all current conventional senses) has a design that somehow subsumes these forces.

The world is a vast and inconceivably complicated place. That anything is predictable or understandable at all is something of a miracle. That humans can produce even dim understanding or very modest instances of control is more miraculous still. In this sense, any given thing in the world, from a pebble to a space shuttle to a low-pressure trough to a working farm to an ocean, analyzed in full, contains a volume of information that is completely beyond the comprehension of even the most brilliant human mind. In essence, the information density of even the tiniest, simplest objects renders them wholly immovable to the human mind.

The idea of control thus hearkens back to Archimedes using a lever to move the whole world. Control is a particular arrangement that gives an agent (i.e. something with a minded purpose) leverage enough to move to the world from one understandable condition to another. This suggests a (very) slightly more formal idea of control as a specific kind of proportion: a thing is "controllable" when there is some arrangement by which a relatively low bandwidth input yields a comparably (very) high bandwidth output, i.e. a state of the system that is foreseen.

This is not necessarily a new way of looking at things, by any stretch. (After all, we can even give old Archimedes some credit, not to mention such big names as Boltzmann or Weiner, who first began asking the modern versions of such questions.) Control is essentially a means of mapping some relatively coarse vision of a complex phenomenon onto its extremely fine-grained reality, and doing so in a way that is suitably robust and structure-preserving. The transistor is the classic example of this, whereby something as complex as a semiconductor can be made to act like a trivial logic function. This view is suggestive of certain interesting avenues of investigation. One has to wonder, for instance, if establishing a regime of control, i.e. designing a machine or proving its properties, is something like playing Michael Barnsley's "Chaos Game": the design ask and answer, over and over again, how do the small things resemble the big things in this picture?

Tuesday, November 24, 2009

Amped Up Over Tasers: When Technical Details Don't Mix

Adoption of the electrical neuromuscular incapacitation device commonly known as the "Taser" is a contentious issue in law enforcement policy. As with many contemporary issues, the adoption and deployment of the Taser appears to incite a spirited public debate that is, in actuality, not so much a debate as a vicious clash of two different sets of vague and incommensurable intuitions. As should not be surprising, this quagmire of ill-formed but irreconcilable feelings is even more severely exacerbated whenever the works of science and late technology are involved.

In recent local news, an action group calling itself "People for a Taser-Free Columbia" hosted a public discussion on the police department's issuance of Tasers to beat officers. At that event, opponents raised frequent objection to the Taser: it subjects its victims to an electrical potential of 50,000 volts. This quantity, opponents contend, is manifestly unsafe, whence the Taser's status as a non-lethal weapon is questionable. The Columbia Daily Tribune reports that a certain city councilman dismissed this objection by noting that "it's not the voltage that matters, it's the amperage." Exchanges such as these have become typical in American civic discourse: one side glibly cites what appears to be a fact, and the other side, without considering any particular features of the problem, dismisses that fact as irrelevant. Because such exchanges have become typical it is easy to mistake them for serious policy debate, when in fact they are little more than hysterics and posturing on either side. This recent exchange by Taser opponents and the city councilman is a striking illustration of how much worse matters become when technical information is involved, and is often unwittingly used to perpetuate an unproductive argument.

A closer examination reveals how little the participants in this debate are actually saying. (Sadly, it's worth even less than the few sentences we've given it here.) Let's first address the councilman's inane rebuttal.

Electrical current is commonly measured in amperes. On this definition, the councilman seems to assert that the voltage figure quoted by opponents is irrelevant on the basis that it is the quantity of electrical current that actually determines the magnitude of injury. The councilman's objection superficially appears erudite: he correctly distinguishes between current, which measures the rate at which electrical charge flows through a medium, versus voltage, which is a measure of potential energy. Opponents, however, are clearly objecting to the Taser on the basis that its sheer energy output seems to be frighteningly high. Does the councilman's remark actually address the spirit of this concern? According to Ohm's Law, a basic physical principle familiar to anyone who has ever taken a college physics course,

electrical current = electrical potential / electrical resistance

which means in particular that current, and thus 'amperage', is proportional to voltage. Thus a small voltage will produce a small current when applied to a given conductor (e.g. a human subject), and a very large voltage will produce a very large current when applied to the same conductor. The number of amperes experienced by a person shot with a Taser dart thus depends upon the number of volts of electrical potential generated by the device. What the councilman seems to be saying is: "It doesn't matter how many volts the suspect is subjected to, as long as he doesn't suffer too many amps." In light of simple physical laws, such an argument makes no sense. Moreover, it does nothing to address generic fears that Thomas A. Swift's Electric Rifle shoots out a quantity of electricity that is simply too large.

It is possible the councilman actually meant something else by his objection, but I cannot think of any other sensible (or favorable) way to construe the remark. It is also worth noting that the councilman's remark is similar to an aphorism oft quoted in the electrician's trade. In the context of creating an electrical current, an electrician or engineer certainly is concerned with the problem of creating a current using as little voltage as possible, but this is quite a different concern than determining how much current can be applied to a human being without causing injury or death. Let this be a lesson about the danger of repeating aphorisms without clearly understanding their meaning and application. Be careful not to use pre-packaged phrases to cover up a lack of understanding.

The councilman's technical flub was only made worse when the Deputy Chief of Police asserted, according to the same Tribune article, that the Taser induces a current that is "much less than a standard wall socket's output." Considering that, in the United States, electricity is transmitted to homes at 120 volts, it is impossible that a correctly functioning wall outlet could induce a current greater than the peak current produced by a successful Taser deployment. According to Taser International Inc., the device's manufacturer, the TASER X26 delivers a maximum effective voltage of 1200 V across the body of the subject. All things being equal, Ohm's Law entails that the peak current delivered by a relatively low-voltage taser is at least ten times what a wall outlet could deliver.

This flub, however, leads into one of the subtle difficulties of citing figures: there are many to choose from, and it often matters which you choose. One should note that I said the X26 delivers a peak voltage of 1200 V; the one-second baseline average reported by the manufacturer is only 0.76 volts. There is probably a substantial and pertinent debate to be had on whether the peak or the average current output is more meaningful to the issue of the Taser's ability to do mortal harm, or how long a peak must be in order to be physiologically relevant. However, none of these issues were raised by any participants that I am aware of, nor is there any evidence that the Deputy Chief took these matters into account. One could blame the genre of news reporting: there is only so much space, and reporters favor simple questions with short answers. Moreover, the Deputy Chief is a peace officer, not an electrical engineer; he may have little or no knowledge of the Taser's technical details, beyond those necessary to its operation, and is mostly likely citing the nearest available figure.

Nonetheless, newspapers need to be able report news concisely, and police officers need to be able to do their jobs without worrying about a lot of scientific ephemera. What could have been done differently? The reporter could have troubled his or her self to formulate a somewhat more specific question -- and to follow up on fact-checking the answer. The Deputy Chief, for his part, could have given a more generic expression of his confidence in the device's safety. This would sufficiently express his position without giving the misleading and all too often conjured appearance that "this is all very scientific and things are completely under control." Don't cite specifics unless you are certain of specifics.

(Specifically Deputy Chief claimed the Taser's current output to be 0.014 amperes, without specifying this as average or a peak, or giving a source. I could not locate this figure on the manufacturer's website.)

Now, on to the question of the Taser opponents. The attentive reader may have noted that the peak voltage I cited above for the TASER X26 (1200 V) is substantially below the sensational 50,000 V figure. This is because, while the electrical circuitry of the Taser does in fact produce an internal potential of 50,000 V, this voltage is not the voltage applied to the body of a person shocked by a Taser. According to a Taser International fact sheet the Taser's effectiveness is partially due to its ability to administer a shock even in the case that the terminal probes do not make skin contact with a subject, e.g. in the instance that the probes are embedded in exterior clothing and do not reach the skin. The Taser accomplishes this by steadily increasing its internal voltage, up to 50,000 V, until the potential difference is sufficient to produce an electrical arc from the probes to the body of the subject. Much of the current produced by the 50,000 V potential difference, however, is lost in the process of "jumping" across the gap between the probes and the body of the subject. As soon as the potential difference built up within the device is released (by shocking the unfortunate person on the other end), the voltage rapidly drops. The extra voltage within the Taser is thus built up only far enough to overcome any electrical resistance on the probe end and thus to produce a current sufficient to subdue the human subject. (The basic idea at work here is also very succinctly described by Ohm's law.) What this means it that no person subjected to a shock from a correctly functioning Taser experiences anything close to 50,000 volts.

(That is not to say, however, that their experience is a pleasant one.)

Though I respect opponents' interest in protecting the public safety, they would know that the figure they so often quote is actually not pertinent if they had troubled themselves to learn about the issue they're debating. Throwing out a figure as an emotional artifact ("Look how big it is!") fails both rational discourse and impassioned elqoeunce. When facts in general, and numbers in particular, are used this way, it is usually results either from someone's lazy skimming of the available information for the first apparently supporting technical fact, or from the widespread repeating of such a carelessly disjointed fact. The end product is a clumsy admixture of fevered pleading and rote recital. The fact that Taser opponents often cite a technical fact of no relevance to their legitimate concerns diminishes their apparent gravity and opens the door to glib dismissals like the councilman's 'amperage' remark.

It would be nice if policy decisions were made the same way that a scientific question is studied or an engineering problem is solved: a collection of experts would assemble, collect and analyze as much data as possible, render a decision or propose a course of action, and publish the findings for public scrutiny. Even if such a system of governance were possible, however, I think it would be at best naive to expect it at this stage in history. Moreover, human societies have to take into account human passions; these can't be swept under the rug if any kind of peace or social harmony is to be maintained. A mode of governance more scientific than those in existence today would still have to account first for the hopes and fears of the governed, else it would be nothing but a brutal, mechanical autocracy. Putting aside dreams of later and elsewhere, what could be done differently right here and right now?

The episode at People for a Taser-Free Columbia's forum is problematic because both parties are clearly talking past one another, and using misconstrued technical details to do so. The effective output of the Taser and its short- and long-term physiological effects are essential points to understand and take into account. However, neither party seems to be seriously considering these issues, so much as cherry-picking bits and pieces to suit their existing biases. Both parties, however, have valid concerns that do not necessarily lie within the bounds of engineering details or known laws of electricity. Police serve a useful and necessary function any society, but citizens do have a legitimate interest in checking police powers and in dictating what is and what is not acceptable police action. This is a natural source of tension. The idea of a new kind of weapon is viscerally scary to any normal human being, and it is natural that some citizens would be concerned that the police, to whom they have granted a substantial measure of power, use these new weapons carefully and responsibly. On the other hand, early evidence suggests the Taser is a highly effective, non-lethal means for officers to subdue aggressive persons, with the promise to greatly reduce the incidence of serious injury to either police or citizens during arrest scenarios. These are two points of view that surely can be brought to some satisfactory reconciliation; Taser opponents surely would not want to see a greater number of suspects or police officers harmed during arrests, nor would Taser proponents want to see the police issued a weapon that posed unacceptable dangers to public.

To emphasize this last point, consider that in the most controversial Taser episodes in recent history (some of which are also local) are controversial not because an electrical neuromuscular incapacitator was deployed, but because it was deployed under highly questionable circumstances. In one sensationally publicized episode last year, Columbia police used a Taser on a man threatening to jump from the I-70 overpass at Providence Road, causing him to fall 15 feet to the highway median below. A Taser was used in spite of the fact that the man in question threatened nothing more than suicide, in spite of the fact that he was only passively uncooperative in his refusal to move himself to safety, and in spite of the fact that the officer's action quite foreseeably caused the man to fall from this perch, thus causing the very injuries police had sought to prevent the man from visiting on himself. In another episode on August 28 of last year, police in Moberly, Missouri used a Taser against one Stanley Harlan during a routine traffic stop; Mr. Harlan died shortly thereafter. The event has come under scrutiny because Mr. Harlan was Tased at once while lying on the ground. The city of Moberly has since agreed to pay the Harlan family $2.4 million.

Episodes such as these underscore the legitimacy opponents' concerns that the new weapon may be irresponsibly or recklessly deployed. At the same time, it is clear that the harm in these episodes was not essential to the Taser itself, but resulted from improper police conduct, which, it can be convincingly argued, could be remediated by better training and more stringent department policies on Taser use. By contrast, these salient points are lost behind shrill assertions about tens of thousands of volts, or the supercilious amperes that somehow matter more.

In closing, I would like to point out that I have assumed that Taser International Inc.'s technical data is all complete and correct, and that I have no reason to believe otherwise. However, this is a crucial assumption. The skeptical citizen should remember that every manufacturer has a large material interest in the perceived safety of their product and so is not necessarily an impartial judge of potential dangers said product may pose to the public.

The lesson in all of this is that we would do well to find a better way to express and legitimize the seemingly vague and unquantifiable hopes and fears from which our views originate. It's more communicative to say, "I'm afraid the police," than, "According to my calculations, the Gizmotron 3000 shoots out too many volts!" We need to be willing to acknowledge that we're human beings, with human hopes and human fears that need to be openly acknowledged and should be respected without qualification. At the same time, we also need to consider hard facts and well analyzed data in making decisions, being careful not to misuse them to give trappings of legitimacy to arguments that more emotional than rational. It's ultimately hopes and fears that bring us together as human beings; we should use the facts to harmonize rather than to obfuscate our deeper motives.