controllingcomputers.html


	*Controlling Computers Through Language* Veronica Dahl 1. Introduction More than twenty years have passed since the first efforts towards declarative programming catapulted computing sciences from the old number-crunching paradigm into a new era paradigm of inferential engines. An era in which we no longer measure efficiency in terms of calculations per second, but in terms of inferences per second- a fantastic qualitative leap. Computational logic, at the heart of this revolution in Computing Sciences, has been responsible for many beautiful incarnations, particularly in Artificial Intelligence, of the idea of programming through logic. Notable among them, natural language processing applications have blossomed around the axis of parsing-as-deduction (an expression coined by Fernando Pereira), ever since Alain Colmerauer developed the first logic grammar formalism, Metamorphosis Grammars. Meanwhile, the field of speech analysis and recognition has also slowly been reaching maturity, to the point that reasonably efficient speech software has become easily available, and hardware technology is swiftly moving towards networks of wireless, portable, small personal computers that have little to envy our previous "big" computers in terms of power. The pieces of the puzzle are laid down to now attempt more human like communication with computers- computers in a wide sense, including robots, virtual worlds, and the Internet. Industry is already identifying the need to integrate "voice recognition software so that the computer can listen to you, voice synthesis so it can talk back to you, and AI programs to guess what you really want" (Newsweek, March 1998: interview to Bill Gates). From a health perspective, since computers have become so ubiquituouts, it is high time to develop alternative computer work modes than the present typing/screen based model. We are the first generation with exponents that have spent twenty or thirty years working in front of a computer terminal, and the ill effects are all too visible around us: tendonitis; eye, neck and back strain; Carpal Tunnel syndrome. In this article we examine some applications of computational logic that in our view, should be explored along the route towards making computers into true extensions of our human abilities- extensions that adapt to our biology, rather than requiring our bodies to adapt. 2. User-friendly tools for natural language processing Linguistics is just as much of an evolving science as ours is. In the last few decades it has become formalized to an extent that makes it amenable to computer applications. Some of its objectives, such as descriptive economy and declarativeness, coincide with our objectives as computing scientists. Moreover, linguistics also resorts to logic in many of its aspects: knowledge about language is, in many linguistic frameworks, expressed as some sort of deduction from general principles which can be expressed as axioms; partial, incremental information is also typical in linguistics, and can be expressed through the logical variable; many meaning representation formalisms are based on logic. This means in particular that, by chosing a logic-based formalism to process language, the implementation means becomes closer to some of the representations manipulated in processing, thus minimizing the need for interfaces by providing a uniform methodology: logic throughout, in one form or another. Specialized logic systems have been incorporated into several linguistic formulations, particularly regarding semantic representations for natural language (e.g., situation semantics [BP83] and Montague semantics [DWP81]. Higher order logics have been used for semantic interpretation [Per90]. Lambek calculus has been used for inferring the syntactic categories of phrases [Lam87] and for handling long distance dependencies (the relating of constituents separated by arbitrary strings, e.g. the relating of a pronoun with its antecedent) [HM92]. Intuitionistic treatments of the latter have also been explored [PM90,DT98,RDT98]. Cross-fertilizations between subfields of logic programming and natural language have also proved useful. In particular, natural language tailored Constraint Logic Programming techniques have been studied, such as memoization within CLP [Joh83], constraint extensions of Earley deduction [Joh], and the incorporation of feature-structure constraints into logic programming [CW89]. Such wealth of intersection between the complementary fields of linguistics, logic and computational logic has not been exploited to full capacity. Among the reasons: linguists do not in general have enough knowledge of computational formalisms to use them by themselves, computer scientists do not in general have enough linguistic background to comfortably implement linguistic theories, and interdisciplinary work requires a substantial effort to even speak the same jargon. Often the same word (e.g. "argument") has a technical meaning that is different in linguistics than in logic or computing sciences. More effort should be put into providing tools that make it easy for linguists to describe grammars in terms they are familiar with. Within computational logic, these descriptions can in turn become executable, as we know, and can therefore allow linguists to test the adequacy of certain grammars for specific languages, and to examine, and perhaps improve, the underlying principles of linguistic theories themselves, by contrasting theoretical claims with actual results in concrete systems. Such tools would also, by the way, provide computer scientists with high level means for incorporating natural language front ends to Prolog-based knowledge bases. If they became widely used, they would provide a living proof of the usefulness and versatility of computational logic. 3. Accessing the web and controlling robots through language The intersection between logic programming and the internet is a very new but rapidly growing field. Recent logic-based web applications have been presented [TDH97,TD98a,TD98b], and a special issue of the Journal of Logic Programming on this subject is currently under preparation. As anyone knows who has tried to query the internet through the existing search engines, there is a glaring need for intelligent access to that fantastic but frustratingly mechanical repository of world knowledge that the Internet has become. From this perspective alone, logic should play a major role, given that deduction is obviously needed to make enough sense of a query as to minimize noise (the number of irrelevant documents obtained for a given query to a search engine) and silence (the number of failures to find any relevant documents that do exist). Concept-based search engines are starting to appear, but to our knowledge there are none yet that go much beyond a shallow use of keywords and concept classifications. Full meaning extraction and comparison, however, can only be done once the subtleties of natural language semantics are taken into account. A challenging task, but again, one for which computational logic is particularly suited [ZFRDT97]. Logic programming for the internet is also advancing greatly, so fruitful interactions can be reasonably expected. Among the exciting new fields that these interactions are making possible, virtual worlds stand out as particularly promising for long-distance interactions, distributed work, and interactive teaching through the web [RDT98]. Endowing these budding applications with access through language would greatly enhance their capabilities. In particular, multilingual access to virtual worlds over the internet would help remove geographic and language barriers to cooperation. Preliminary work in this direction is [DTRS98]. Using speech to control robots is also an interesting application of natural language processing through logic. Preliminary work has been done [DFT95] to control a simple world of mini robots through natural language commands. Because these robots' world is quite restricted (they can move to sources of light, recharge themselves, avoid obstacles, etc.), commands are relatively simple and fairly devoid of ambiguity. This will be the case of many robot worlds, since we are moving towards specialized robots that concentrate on certain tasks. Mobile computers and wireless networks, as well as already available speech software which can be adapted, will help towards the goal of transporting these specialized robots to wherever they are needed, while communicating with them in more human terms. Another interesting family of internet applications of speech is that of robots that operate in virtual, visual worlds. For instance, internet-based VRML animations have been generated through English-controlled partial order planners [SDT98]. The next step is for such systems to accept speech rather than written input. 4. Database manipulation/programming through language Database interfacing through spoken language has been little explored, possibly because the availability of reasonably efficient speech analysis and synthesis software is relatively new. Written text, however, has long been used for database consultation (e.g. [Dah79]), and for database updates (e.g. [Dav84]). There is increasing interest from industry in the spoken language field. The availability of very effective low-cost software (e.g. Virtual Personalities Inc.'s Sylvie agent, Microsoft speech agent, Dragon Co.'s Naturally Speaking software) makes speech applications such as database creation and access reasonably feasible. And of course, logic programming's long experience with both deductive databases and natural language processing will come in most handy. However, putting all the pieces of the puzzle together will require careful crafting. Within the logic-based database field, some recent developments could prove most valuable towards this objective, like the uses of Inductive Logic Programming to automate the construction of natural language interfaces for database queries [Zel96]. The availability of poweful while mobile computers also adds unprecedented potential to speech interfacing software, for instance for business people or academics who often travel, and who could therefore make the most of such results useful if they were portable. Finally, experience with the circumscribed domain of database creation could prove useful as a first step towards an even more daring application, that of programming through natural language. 5. Conclusion Speech-driven database creation and consultation, just as speech driven robot control or programming, and web access through language, could bring relief from computer use related health problems that the present typing/screen based model of computer use entails. They can also partially address the present need to integrate voice recognition software, voice synthesis, and AI programs. In helping linguists write executable grammars in their own terms, we might by the way be able to tap on linguistic expertise that might be most valuable for our own language processing applications. Efforts are under way for a EU/NorthAmerica Compulog Network of Centres of Excellence to launch a cooperation around NL projects using logic programming, which I am presently coordinating jointly with Dr. Pearce. Since as we have seen, inductive logic programming and constraint logic programming can also play an important role in natural language processing, it would be most helpful to join forces across areas as well. Helpers welcome! References [DT98] Dahl, V., and Tarau, P. (1998) Assumptive Logic Programming. Manuscript, to be submitted. [Dah79] Dahl, V. (1979) Logical Design of Deductive, Natural Language Consultable Data Bases. In Proc. V Int. Conf. on Very Large Databases, Rio de Janeiro:24-31. [TDDR98] Tarau, P., De Bosschere, K., Dahl, V. and Rochefort, S. (to appear, Journal of Logic Programming) LogiMOO: an Extensible Multi-User Virtual World with Natural Language Control. [ZFRDT97] Zaiane, O. R., Fall, A., Rochefort, S., Dahl, V. and Tarau, P. (1997) On-Line Resource Discovery using Natural Language. In Proc. RIAO'97,Computer-Assisted Searching on the Internet, Montreal: 336-355. [DFT95] Dahl, V., Fall, A. and Thomas, M.C. (1995) Driving Robots through Natural Language. In Proc. 1995 IEEE International Conference on Systems, Man and Cybernetics: 1904-1908. [TDH97] Tarau, P., De Bosschere, K. and Hermenegildo, M. (eds.) Proc. of the 2nd International Workshop on Logic Programming Tools for Internet Applications, ICLP'97, Leuven. [Zel96] Zelle, J. M. and Mooney, R. J. (1996) Learning to Parse Database Queries using Inductive Logic Programming. Proc. Thirteenth Natuional Conference on Artificial Intelligence,: 1050-1055. [Dav84] Davison, James (1984) A Natural Language Interface for Performing Database Updates. ICDE:69-76. [TD98a] Tarau, P., and Dahl, V. (1998) Towards a Logic Programming Infrastructure for Internet Programming. Special LNAI issue on AI and Internet, Springer-Verlag (invited contribution, 26 p.). [TD98b] Tarau, P., and Dahl, V. (1998) Code Migration with First Order Continuations. In Proc. Joint Declarative Programming Conference AGP98, La CoruÒa, Spain: 215-226. [RDT98] Rochefort, S., Dahl, V. and Tarau, P. (1998) A Virtual Environment for Collaborative Learning. In Proc. World Multiconference on Systemics, Cybernetics and Informatics , Florida: 413-416. [DTRS98] Dahl, V., Tarau, P., Rochefort, S. and Scurtescu, M. (1998) A Spanish Interface to LogiMOO- towards multilingual virtual worlds. Accepted Oct.1998, Informatica, Special Issue on Natural Language Processsing and Agent Communication, number 4. [SDT98] Schiel, A., Dahl, V. and Tarau, P. (1998) Generating Internet Based VRML Animations through NL controlled Partial Order Planners. Simon Fraser University internal report- to be submitted. [CW89] Chen, W. and Warren, D.S. (1989) C-Logic of Complex Objects. TR, Dept. of COmputer Science, State Univ. of New York at Stony Brook. [Joh83] Johnson, M. (1983) Memoization in Constraint Logic Programming, TR, Brown University. [Joh] Johnson, M. Constraints and the Chart. Unpublished manuscript. [BP83] Barwise, J. and Perry, J. (1989) Situations and Attitudes. MIT Press, Cambridge, MA. [DWP81] Dowty, D.R., Wall, R. E., and Peters, S. (1981) Introduction to Montague Semantics. D. Reidel Publishing Co., Dordrecht. [Per90] Pereira, F. C. N. (1990) Semantic Interpretation as Higher-Order Deduction. Proc. Second European Workshop on Logics and AI, Springer, N.Y. [Lam87] Lambek, J. (1987) Multicategories Revisited. Categories Comp. Sci. Contemporary Math 92:217-239. [HM92] Hodas, J. and Miller, D. (1992) Logic Programming in a Fragment of Intuitionistic Linear Logic. Journal Informatics and Computation. [PM90] Pareschi, R. and Miller, D. (1990) Extending Definite Clause Grammars with Scoping Constructs. In: D.H.D. Warren and P. Szeredi (eds.) International Conference on Logic Programming MIT PRess, Cambridge, MA, pp. 373-389.

Controlling Computers Through Language

Veronica Dahl

1. Introduction

More than twenty years have passed since the first efforts towards declarative programming catapulted computing sciences from the old number-crunching paradigm into a new era paradigm of inferential engines. An era in which we no longer measure efficiency in terms of calculations per second, but in terms of inferences per second- a fantastic qualitative leap.

Computational logic, at the heart of this revolution in Computing Sciences, has been responsible for many beautiful incarnations, particularly in Artificial Intelligence, of the idea of programming through logic. Notable among them, natural language processing applications have blossomed around the axis of parsing-as-deduction (an expression coined by Fernando Pereira), ever since Alain Colmerauer developed the first logic grammar formalism, Metamorphosis Grammars.

Meanwhile, the field of speech analysis and recognition has also slowly been reaching maturity, to the point that reasonably efficient speech software has become easily available, and hardware technology is swiftly moving towards networks of wireless, portable, small personal computers that have little to envy our previous "big" computers in terms of power.

The pieces of the puzzle are laid down to now attempt more human like communication with computers- computers in a wide sense, including robots, virtual worlds, and the Internet. Industry is already identifying the need to integrate "voice recognition software so that the computer can listen to you, voice synthesis so it can talk back to you, and AI programs to guess what you really want" (Newsweek, March 1998: interview to Bill Gates).

From a health perspective, since computers have become so ubiquituouts, it is high time to develop alternative computer work modes than the present typing/screen based model. We are the first generation with exponents that have spent twenty or thirty years working in front of a computer terminal, and the ill effects are all too visible around us:

tendonitis; eye, neck and back strain; Carpal Tunnel syndrome.

In this article we examine some applications of computational logic that in our view, should be explored along the route towards making computers into true extensions of our human abilities- extensions that adapt to our biology, rather than requiring our bodies to adapt.

2. User-friendly tools for natural language processing

Linguistics is just as much of an evolving science as ours is. In the last few decades it has become formalized to an extent that makes it amenable to computer applications. Some of its objectives, such as descriptive economy and declarativeness, coincide with our objectives as computing scientists.

Moreover, linguistics also resorts to logic in many of its aspects: knowledge about language is, in many linguistic frameworks, expressed as some sort of deduction from general principles which can be expressed as axioms; partial, incremental information is also typical in linguistics, and can be expressed through the logical variable; many meaning representation formalisms are based on logic. This means in particular that, by chosing a logic-based formalism to process language, the implementation means becomes closer to some of the representations manipulated in processing, thus minimizing the need for interfaces by providing a uniform methodology: logic throughout, in one form or another.

Specialized logic systems have been incorporated into several linguistic formulations, particularly regarding semantic representations for natural language (e.g., situation semantics [BP83] and Montague semantics [DWP81]. Higher order logics have been used for semantic interpretation [Per90]. Lambek calculus has been used for inferring the syntactic categories of phrases [Lam87] and for handling long distance dependencies (the relating of constituents separated by arbitrary strings, e.g. the relating of a pronoun with its antecedent) [HM92]. Intuitionistic treatments of the latter have also been explored [PM90,DT98,RDT98].

Cross-fertilizations between subfields of logic programming and natural language have also proved useful. In particular, natural language tailored Constraint Logic Programming techniques have been studied, such as memoization within CLP [Joh83], constraint extensions of Earley deduction [Joh], and the incorporation of feature-structure constraints into logic programming [CW89].

Such wealth of intersection between the complementary fields of linguistics, logic and computational logic has not been exploited to full capacity. Among the reasons: linguists do not in general have enough knowledge of computational formalisms to use them by themselves, computer scientists do not in general have enough linguistic background to comfortably implement linguistic theories, and interdisciplinary work requires a substantial effort to even speak the same jargon. Often the same word (e.g. "argument") has a technical meaning that is different in linguistics than in logic or computing sciences.

More effort should be put into providing tools that make it easy for linguists to describe grammars in terms they are familiar with. Within computational logic, these descriptions can in turn become executable, as we know, and can therefore allow linguists to test the adequacy of certain grammars for specific languages, and to examine, and perhaps improve, the underlying principles of linguistic theories themselves, by contrasting theoretical claims with actual results in concrete systems. Such tools would also, by the way, provide computer scientists with high level means for incorporating natural language front ends to Prolog-based knowledge bases. If they became widely used, they would provide a living proof of the usefulness and versatility of computational logic.

3. Accessing the web and controlling robots through language

The intersection between logic programming and the internet is a very new but rapidly growing field. Recent logic-based web applications have been presented [TDH97,TD98a,TD98b], and a special issue of the Journal of Logic Programming on this subject is currently under preparation.

As anyone knows who has tried to query the internet through the existing search engines, there is a glaring need for intelligent access to that fantastic but frustratingly mechanical repository of world knowledge that the Internet has become. From this perspective alone, logic should play a major role, given that deduction is obviously needed to make enough sense of a query as to minimize noise (the number of irrelevant documents obtained for a given query to a search engine) and silence (the number of failures to find any relevant documents that do exist).

Concept-based search engines are starting to appear, but to our knowledge there are none yet that go much beyond a shallow use of keywords and concept classifications. Full meaning extraction and comparison, however, can only be done once the subtleties of natural language semantics are taken into account. A challenging task, but again, one for which computational logic is particularly suited [ZFRDT97]. Logic programming for the internet is also advancing greatly, so fruitful interactions can be reasonably expected.

Among the exciting new fields that these interactions are making possible, virtual worlds stand out as particularly promising for long-distance interactions, distributed work, and interactive teaching through the web [RDT98]. Endowing these budding applications with access through language would greatly enhance their capabilities. In particular, multilingual access to virtual worlds over the internet would help remove geographic and language barriers to cooperation. Preliminary work in this direction is [DTRS98].

Using speech to control robots is also an interesting application of natural language processing through logic. Preliminary work has been done [DFT95] to control a simple world of mini robots through natural language commands. Because these robots' world is quite restricted (they can move to sources of light, recharge themselves, avoid obstacles, etc.), commands are relatively simple and fairly devoid of ambiguity. This will be the case of many robot worlds, since we are moving towards specialized robots that concentrate on certain tasks. Mobile computers and wireless networks, as well as already available speech software which can be adapted, will help towards the goal of transporting these specialized robots to wherever they are needed, while communicating with them in more human terms.

Another interesting family of internet applications of speech is that of robots that operate in virtual, visual worlds. For instance, internet-based VRML animations have been generated through English-controlled partial order planners [SDT98]. The next step is for such systems to accept speech rather than written input.

4. Database manipulation/programming through language

Database interfacing through spoken language has been little explored, possibly because the availability of reasonably efficient speech analysis and synthesis software is relatively new. Written text, however, has long been used for database consultation (e.g. [Dah79]), and for database updates (e.g. [Dav84]). There is increasing interest from industry in the spoken language field.

The availability of very effective low-cost software (e.g. Virtual Personalities Inc.'s Sylvie agent, Microsoft speech agent, Dragon Co.'s Naturally Speaking software) makes speech applications such as database creation and access reasonably feasible. And of course, logic programming's long experience with both deductive databases and natural language processing will come in most handy. However, putting all the pieces of the puzzle together will require careful crafting. Within the logic-based database field, some recent developments could prove most valuable towards this objective, like the uses of Inductive Logic Programming to automate the construction of natural language interfaces for database queries [Zel96].

The availability of poweful while mobile computers also adds unprecedented potential to speech interfacing software, for instance for business people or academics who often travel, and who could therefore make the most of such results useful if they were portable. Finally, experience with the circumscribed domain of database creation could prove useful as a first step towards an even more daring application, that of programming through natural language.

5. Conclusion

Speech-driven database creation and consultation, just as speech driven robot control or programming, and web access through language, could bring relief from computer use related health problems that the present typing/screen based model of computer use entails. They can also partially address the present need to integrate voice recognition software, voice synthesis, and AI programs. In helping linguists write executable grammars in their own terms, we might by the way be able to tap on linguistic expertise that might be most valuable for our own language processing applications.

Efforts are under way for a EU/NorthAmerica Compulog Network of Centres of Excellence to launch a cooperation around NL projects using logic programming, which I am presently coordinating jointly with Dr. Pearce. Since as we have seen, inductive logic programming and constraint logic programming can also play an important role in natural language processing, it would be most helpful to join forces across areas as well. Helpers welcome!

References

[DT98] Dahl, V., and Tarau, P. (1998) Assumptive Logic Programming. Manuscript, to be submitted.

[Dah79] Dahl, V. (1979) Logical Design of Deductive, Natural Language Consultable Data Bases. In Proc. V Int. Conf. on Very Large Databases, Rio de Janeiro:24-31.

[TDDR98] Tarau, P., De Bosschere, K., Dahl, V. and Rochefort, S. (to appear, Journal of Logic Programming) LogiMOO: an Extensible Multi-User Virtual World with Natural Language Control.

[ZFRDT97] Zaiane, O. R., Fall, A., Rochefort, S., Dahl, V. and Tarau, P. (1997) On-Line Resource Discovery using Natural Language. In Proc. RIAO'97,Computer-Assisted Searching on the Internet, Montreal: 336-355.

[DFT95] Dahl, V., Fall, A. and Thomas, M.C. (1995) Driving Robots through Natural Language. In Proc. 1995 IEEE International Conference on Systems, Man and Cybernetics: 1904-1908.

[TDH97] Tarau, P., De Bosschere, K. and Hermenegildo, M. (eds.) Proc. of the 2nd International Workshop on Logic Programming Tools for Internet Applications, ICLP'97, Leuven.

[Zel96] Zelle, J. M. and Mooney, R. J. (1996) Learning to Parse Database Queries using Inductive Logic Programming. Proc. Thirteenth Natuional Conference on Artificial Intelligence,: 1050-1055.

[Dav84] Davison, James (1984) A Natural Language Interface for Performing Database Updates. ICDE:69-76.

[TD98a] Tarau, P., and Dahl, V. (1998) Towards a Logic Programming Infrastructure for Internet Programming. Special LNAI issue on AI and Internet, Springer-Verlag (invited contribution, 26 p.).

[TD98b] Tarau, P., and Dahl, V. (1998) Code Migration with First Order Continuations. In Proc. Joint Declarative Programming Conference AGP98, La CoruÒa, Spain: 215-226.

[RDT98] Rochefort, S., Dahl, V. and Tarau, P. (1998) A Virtual Environment for Collaborative Learning. In Proc. World Multiconference on Systemics, Cybernetics and Informatics , Florida: 413-416.

[DTRS98] Dahl, V., Tarau, P., Rochefort, S. and Scurtescu, M. (1998) A Spanish Interface to LogiMOO- towards multilingual virtual worlds. Accepted Oct.1998, Informatica, Special Issue on Natural Language Processsing and Agent Communication, number 4.

[SDT98] Schiel, A., Dahl, V. and Tarau, P. (1998) Generating Internet Based VRML Animations through NL controlled Partial Order Planners. Simon Fraser

University internal report- to be submitted.

[CW89] Chen, W. and Warren, D.S. (1989) C-Logic of Complex Objects. TR, Dept. of COmputer Science, State Univ. of New York at Stony Brook.

[Joh83] Johnson, M. (1983) Memoization in Constraint Logic Programming, TR, Brown University.

[Joh] Johnson, M. Constraints and the Chart. Unpublished manuscript.

[BP83] Barwise, J. and Perry, J. (1989) Situations and Attitudes. MIT Press, Cambridge, MA.

[DWP81] Dowty, D.R., Wall, R. E., and Peters, S. (1981) Introduction to Montague Semantics. D. Reidel Publishing Co., Dordrecht.

[Per90] Pereira, F. C. N. (1990) Semantic Interpretation as Higher-Order Deduction. Proc. Second European Workshop on Logics and AI, Springer, N.Y.

[Lam87] Lambek, J. (1987) Multicategories Revisited. Categories Comp. Sci. Contemporary Math 92:217-239.

[HM92] Hodas, J. and Miller, D. (1992) Logic Programming in a Fragment of Intuitionistic Linear Logic. Journal Informatics and Computation.

[PM90] Pareschi, R. and Miller, D. (1990) Extending Definite Clause Grammars with Scoping Constructs. In: D.H.D. Warren and P. Szeredi (eds.) International Conference on Logic Programming MIT PRess, Cambridge, MA, pp. 373-389.