(source)

Duck typing is the concept in programming by which an object is interchangeable with any other object as long as it can run through the same code while providing a sufficiently complete interface1. It is a direct application of a popular idea: If it walks like a duck and quacks like a duck, it must be a duck. That is, you do not try to obtain proof that you have a duck, you just observe and see that, for the limited time your observation lasted, it appeared to be a duck. It might not be a duck, but you do not care. It is present in popular programming languages like Ruby, JavaScript and Python. Considering that Python is the prototyping language of choice of companies such as Google and JavaScript is ubiquitous on the Web, duck typing has become quite a common paradigm among programmers.

For the non programmers… Imagine you run a routine meant for ducks. First you weight the object, if it is over 2 kilograms, then you check the color of the feathers, if not you terminate the routine (because the duck is not ready to be eaten yet). Then you continue the routine based on the color of the feathers. Now, in this routine, a small rock will pass off as a duck, because you never check its feathers, but if you have a larger rock, then you will encounter a problem in your routine because you can’t check the color of the feathers of a large rock.

Comparatively2, many languages (Java, C#, C++, C) first check whether the object is a duck. They may allow it to be a special type of duck, but before the routine even runs, you need to prove you have duck first.

I have come to realize recently that duck typing is a central concept in artificial intelligence and philosophy. Peter Turney argues again and again for the application of this principle, though he would not care to call it duck typing. What is the Turing test, if not an example of duck typing? If you can substitute the human being by a machine, and things still work, then, you might as well say that the machine is human (for the purposes of determining whether it has human intelligence). If you can replace part of my brain by a computer, then isn’t a computer as good as neural matter?

Imagine a similar problem in programming. You are a Python, JavaScript or Ruby programmer and you are asked whether this object can replace this other object. Or, to simplify the task, whether this function is a substitute to this other function. Specifically, you want to know if, once you have made the substitution, you will encounter any missing attributes.

How would you do it? Well, I might try switching one function for the other in some program. And if it works, I might be happy, but I have not really shown that one function can pass for the other, have I? It could still fail in another piece of code. I can falsify the question, but never get a truly positive answer. And no, in general, I cannot exhaust all possible tests to prove my case.

Strongly typed programming languages like Java, C++, C, C#, on the other hand, provide you a way to make sure, at compile-time, before the code even runs, that the interface is complete. And that is why duck typing is fundamentally different from static-typed polymorphism3.

This brings about a few questions. In other words, how long must the machine fool the human being before we conclude that the Turing test is a success?

This is not just a theoretical concern. For example, my life is made slightly miserable because of all the spam I receive. For a time, the combined spam filters ACM and Google Mail made it ok. I was pleased with the result and I would have rated the filtering on par with what a bored human assistant could do. As of a few months ago, these spam filters no longer pass my little Turing test.

This is very common in Machine Learning and Artificial Intelligence. You see the textbook example and you think to yourself wow! this is extraordinary! But then, any long term, real-life exposure with the technique, and you realize how stupid it is. Sometimes it can remain useful (I wouldn’t go without spam filters!), but it no longer fools you into thinking it is “intelligent.”

Similarly, if you use a large collection of text to determine the semantics of a word or a phrase, or to study analogies, you might get decent results for a time, but when the conditions change, things might go to hell. The Semantic Web is similarly plagued: you can never demonstrate that you have an accurate representation, but you can hope to eventually falsify it.

(This reminds me of the No Free Lunch theorems. The best solutions are always local and contextual. )

I’m sure that this is a very common objection to the Turing test or to Natural Language processing: there is no possible exhaustive testing. I think that the only remaining option is to limit the scope of these tests. That is, instead of using the somewhat ill-defined Turing test, you describe a very specific experiment, a very narrow one that can be reproduced exactly. The problem with this approach is that machines already pass such narrow tests.

In other words, as far as duck typing goes, there are many instances where you can already replace a human being by a machine.

Ah! So, I would argue that the Turing test is not a scientific test, really, but just a rather general paradigm, no different than duck typing.

Well, there is something even deeper, I think. Suppose that a machine could pass all my specific Turing tests, except for one of them. But I have an infinite number of tests, and only one of them could show the machine for what it really is. Then what? I have a probability of 0% of discovering the problem considering that the universe will not be around forever, let alone the human race. Would we conclude that the machine has human intelligence then?

To this Stevan Harnad might answer that it is arbitrary to ask for more from a machine than I ask from a person, just because it’s a machine. I do not buy this argument. I am not certain whether I am the only intelligent person in the universe and you are all part of a conspiracy to fool me into thinking there are several of me. Yes, I’m not insane and I tend to believe that other human beings roughly think and feel the way I do. But this is not arbitrary: human beings look a lot like me, down to their inner workings.

Another objection might come from relating the problem to the physical sciences. How do I know that gravity works? Yes, it has worked for many years, but how do I know that gravity always hold true. Well, I do not. It could be that there are part of the universe where gravity is absent or it could weaken one day. Why not?

All I know is that Newton’s laws are useful. All I know is that my spam filters are useful. Going from “this is a useful spam filter” to “this spam filter has human intelligence” is a step I am not yet ready to make, even in principle. And why is that even a useful step to take? Even if we create machines that can pass the Turing test, will we know what intelligence is? It does not necessarily follow. People were able to create highly radioactive materials before they understood what it was. Will these machines be more useful that other machines? Would a machine that can pass 100,000 different Turing tests, necessarily be more useful that the machine that can only pass 99,000 Turing tests?

This has very concrete consequences if you accept my ideas. Research in Computer Science should therefore be focused on making machines useful. Whether or not they can pass some specific Turing tests, even a large number, seems totally secondary to me. Bring me a machine that can filter my spam mail with human-like ability, and I will be happy. Don’t bother me by trying to prove to me that this machine is actually “intelligent.” I do not see why this is a useful concept.

Hence, Computer Science should focus on usefulness criteria and reject other criteria.

(Yes, I am fishing for your objections.)

1- Duck typing is a bit more complicated to define than what I did here. There is no specific interface to check. For example, consider this function:


def f(o):
if(o.hasLegs):
o.danceWithMe()

In this instance, any object o not having the attribute “hasLegs” will fail. But any object having the attribute “hasLegs” with value false whenever it gets passed to this function will also do (whether it has the danceWithMe method or not). You see how it can be complicated to determine if a given object can be used with function f. It is probably equivalent to the halting problem.

It is not the same thing as polymorphism because it requires that there be no static typing: the interface does not have to be complete, only sufficiently complete to run through the parts of the code that apply.

2- As an aside, languages supporting duck typing are far more powerful than others in my opinion. Languages with static typing are based on the assumption that catching bugs earlier is better. They were largely influenced by the belief that we should prove our code to be correct. That is, that programming is like proving theorems. Except that they got it wrong. Designing algorithms is like proving theorems; programming is like sketching the plans of a building. Architects do not prove that their buildings are pretty and work. Architects design their buildings to be pretty and functional. There is a huge difference in spirit between proving and designing, but both are hard work.

3- … and a poor model for reality.

15 Comments

  1. You are committing a sophomore error: Turing did not propose “specific
    Turing tests”. He proposed one particular test for general-purpose
    intelligence.

    You confuse “performing at the same level as a human” with “performing
    similarly to a human, foibles and all”. You obviously don’t mean the
    latter — but Turing’s “imitation game” most certainly did.

    You also confuse different uses of the word “intelligent”. Turing
    proposed his test as a way, in principle, to decide if a computer
    was intelligent in a general-purpose sense that included things like
    creativity, language use, arithmetic ability, humor, etc.

    When we talk about “intelligent spam filters”, or “intelligent
    backtracking”, or even “intelligent toasters”, we mean “intelligent”
    in the sense of performing a particular task well.

    And your comment that creating an intelligent computer is secondary to
    utility is amusing: you poo-poo what would be the greatest invention
    in human history in favor of short-term grantsmanship? Small dreams
    means small disappointment, I guess.

    Comment by Arugula — 27/1/2007 @ 4:19

  2. In other words, how long must the machine fool the human being before we conclude that the Turing test is a success?

    Yes, time is very important. This point has been made many times. Search on Google for “time limit” “turing test”.

    Hence, Computer Science should focus on usefulness criteria and reject other criteria.

    I agree that usefulness is very important. Other criteria (e.g., perplexity in NLP) are generally substitutes for usefulness when usefulness is difficult to measure. If you look at papers by AI researchers, the motivation is almost always some concrete application. Most AI researchers do not take the Turing test seriously. Joseph Weizenbaum’s Eliza program showed how easy it is to fool people (at least for a short time). His 1976 book Computer Power and Human Reason probably turned many researchers away from the Turing test. The vast majority of papers on the Turing test are not written by AI researchers.

    This has very concrete consequences if you accept my ideas. Research in Computer Science should therefore be focused on making machines useful.

    You won’t get much argument from computer scientists. This is already the majority view in computer science. My own focus is on making machines useful.

    On the other hand, a general-purpose artificial intelligence is likely to be very useful, compared to a highly specialized artificial intelligence.

    Comment by Peter Turney — 27/1/2007 @ 8:41

  3. Arugula: Please calm down. This post was designed to start discussions. No insults are warranted at this point. I don’t poo-poo anything.

    Comment by Daniel Lemire — 27/1/2007 @ 9:54

  4. Daniel: It is cute how you talk down to me, as if I am one of your students.

    I certainly did discuss your posting — I think the most interesting thing about it is that you are making common beginners errors that lead you to what I think are very foolish conclusions.

    I have no interest in tip-toeing around a professor’s ego, so I will not be bothering you again.

    Comment by Arugula — 27/1/2007 @ 13:28

  5. I enjoyed your post, and Arugula’s reply even more, a shame that you saw insults in it.

    Comment by alex — 27/1/2007 @ 17:11

  6. You are committing a sophomore error

    Small dreams means small disappointment, I guess.

    In my opinion, these comments are somewhat insulting. I think it was appropriate for Daniel to request cooler, less emotional discussion.

    Comment by Peter Turney — 27/1/2007 @ 18:24

  7. At best, I though that Arugula demonstrated the point: we don’t really know what “intelligence” means.

    I’m behind the notion of focusing on the criteria of useful. I strive for that in my own work. Coming up with a general “intelligence” may or may not be attainable, but perhaps the best way to get there is just keep doing useful things and see if some pattern emerges.

    I’ve been studying programming languages for my graduate work and I get the feeling that “useful” is not on in the minds of those trying to advance the field. There’s this urge to try and come up with the “be all and end all” tool instead of a “not quite perfect, but beneficial” tool. It’s never sat well with me.

    Comment by Geoff Wozniak — 27/1/2007 @ 23:25

  8. I think you misrepresent the concept of duck typing.

    Take java. I think, if you ask any programmer familiar with a number of languages, if java has ‘duck typing’, your poll will come up with a resounding NO, java doesn’t have it.

    And yet by your description here, java does; any two objects with both implement, say, “Comparator” (an interface), can be fed into a sort routine. The sort code in the JVM doesn’t care beyond the notion that it’s a Comparator, after that all’s fair.

    The elephant in the corner here is what duck typing really means in common discussions on programming languages:

    The idea that attribute names alone are enough. In other words, the very fact that an object happends to have an attribute named ‘compareTo’ is enough; that is (in python/JS/ruby style languages) basically the definition of being a Comparator.

    In java/C# and company, that’s not enough – you need to implement Comparator (and that forces you to have that compareTo method). The major advantage is namespacing:

    ‘compareTo’ has no namespace. This isn’t an obvious problem for a method named ‘compareTo’, but if we start playing with ‘shoot()’ then accidentally shooting my Gun instead of my Camera could cause some nasty surprises. Even if the intent is the same, the implementation details (e.g. do I feed it a list and does that get updated in place, or do I feed it a tuple and do I get a new tuple back?) of the interface definition may still preclude actually mixing and matching to your heart’s content.

    On the other hand, all those interface definitions are a whole lotta typing.

    Personally I prefer the typing, not so much for the Gun/Camera thing (though a nice bug-preventing bonus in rare circumstances), but for the ability to ctrl+click on any interface name in my IDE and read all about what it means to be a Comparator. Do I return a negative number to indicate a is larger than b, or smaller than? I never remember.

    What you are talking about is completely different: You’re just talking about OOP.

    Comment by Reinier Zwitserloot — 28/1/2007 @ 1:25

  9. Reinier: I do mean duck typing and I don’t think Java has duck typing. I actually link to wikipedia for those who want to learn more about the concept. But you are right that my explanation is incomplete. I have edited my post accordingly. Thanks.

    Comment by Daniel Lemire — 28/1/2007 @ 13:15

  10. I’ve been studying programming languages for my graduate work and I get the feeling that “useful” is not on in the minds of those trying to advance the field.

    Those of us in computer science who are trying to invent new programming languages are in a minority. Most computer scientists, being practical people, will use whatever existing programming language is most suitable for the task at hand.

    Comment by Peter Turney — 29/1/2007 @ 14:44

  11. Okay, but now the article doesn’t make any sense. The comparison you make between programming principles and the turing test is interesting, but certainly not so specific as to have a restriction like not including static methods make any sort of sense.

    Not to mention that static methods cannot be polymorphed in java; you can’t stuff them in interfaces, and a class with a static method can’t be ‘extended’ meaningfully (you can redefine the method, but this won’t result in objects of the subtype linking to the new method). Basically, this definition still doesn’t cover what’s ordinarily meant with duck typing.

    More importantly:I think the key IS polymorphism here, and not a specific implementation of it. Duck typing is one way to pull it off. (the existence of duck typing in e.g. python also explains why there is no such thing as an ‘interface definition’ in those languages; the duck typing is their way of doing it. Java and C# and the like have no duck typing (Actually they do, it’s called proxy classes, but that’s “cheating”, I guess) but they do have interface definitions – that’s their way of doing it.

    As long as your programming language offers a way of doing polymorphism, is what I’m saying.

    Comment by Reinier Zwitserloot — 30/1/2007 @ 16:42

  12. Static typing is not the same idea as static methods (http://en.wikipedia.org/wiki/Static_typing). With polymorphism in Java, it is trivial to determine whether an object has the right interface. A simple “instanceof” will determine, in constant time, whether you can plug this object in this function. In Python or Ruby, determining whether a given object can be used inside a given function is much harder… and in practice, you only care whether it works *within the scope of your code*. Python and Ruby are not the only such languages… JavaScript might even be a better example because it is weakly typed too!

    I agree you can make Java use duck typing, but that’s now how 99.999% of the code out there works, so that’s a tiny technical issue.

    Comment by Daniel Lemire — 30/1/2007 @ 17:20

  13. But isn’t the difference between instanceof and if ( object.methodName ) in the end only a minor technicality?

    Maybe, depends on what you consider to be technical.

    In Python/Ruby/JavaScript, if an object has *all* of the methods that are ever used in a function, then it is safe to use to pass this object in the function. However, there are many other objects with an incomplete interface that will also do. The interpreter has no easy way to know whether your code will fail because of a missing method… so it just runs the code… and thousands of programmers live happily with this model. These languages use a “fail late” approach: try your best to succeed and fail only when you have to.

    In Java, if your object has an incomplete interface, and you try to pass it to a function, then it wil not compile! That’s because the designers of the Java language think that it is better to catch “possible errors” as earlier as possible. These languages use a “fail early” approach.

    Now, if you look at what happens with experimental sciences… we are in a fail late approach: you run experiments and if you learn as late as is possible that you have failed.

    I’d in fact argue that the JS view fails because it doesn’t step back and
    take an abstract view of the concept of polymorphism; just because an object
    has a shoot() method it doesn’t mean what you think it might (english has
    homonyms, e.g. shoot with a camera or shoot with a gun, and there are
    implementation differences; basically a method stands for something, it is
    supposed to do something. It’s not always possible or even desirable to put
    all the details in the name itself, it can help to stuff the details in a
    comment, or maybe in the parameter list definition, etcetera.

    You argue not only for a fail early approach, but in fact for a “fail super early” approach by introducing semantics. I hold the view that more semantics than is absolutely necessarily is evil because it makes systems more complex.

    In any case, fail early goes against the point of my post, I think.

    Comment by Daniel Lemire — 30/1/2007 @ 19:23

  14. Experiments are fail super early.

    Physical laws are falsifiable, but not provable. This is why, even if you have tested a law 100,000 times, you must still test it, again and again and again and you stop only in case of a failure. You have no way of stopping your experiments early unless you encounter a failure in the course of an experiment.

    Which is why I’m, again, correct, in asserting that that’s taking it way too
    far: The idea that polymorphism is inherent in AI discussions is an
    interesting one, the moment you take it beyond this metaphor and start
    trying to assign it to specific implementations of the idea of polymorphism,
    it becomes a pointless tirade.

    If determining machine intelligence was like Java’s polymorphism, then to check whether a machine is intelligent, we would do “machine instanceof intelligentbeing”. This can be done in constant time. On the other hand, validating duck typing is equivalent to the halting problem and that is a very hard problem.

    Comment by Daniel Lemire — 30/1/2007 @ 20:53

  15. Let me say that the first poster could certainly have phrased his particular insight with a little more compassion and clarity.

    Next, I want to commend you. Your question here is quite interesting. How many (and what kind of) tests do we need to show this machine can think? If we’re strict dualists, there’s nothing that show this — just as there’s no gesture we can perform to prove God exists, or that gravity will *always* function as we conceive it currently.

    I think the important step to take is denying this dualism — that there’s no difference between language and the actions and passions of bodies. The question is substratum, material, construction methodology. Who’s to say a computer won’t ‘think’ if we build a recursive network of self-organizing social agents? What indeed would be the difference, if a robot was *acting* wise and compassionate, responding as necessary to the situation?

    Comment by Joe — 8/9/2007 @ 1:28

Sorry, the comment form is closed at this time.

« Blog's main page

Powered by WordPress