Modelling of space-efficient one-pass translation using attribute grammars

Automatic production of one-pass compilers from attribute grammars is considered. An examination of a one-pass grammar for the programming language Euclid shows that the present definition of one-pass grammars is too general: the space behaviour of the produced compilers differs from that found in conventional hand-written compilers. A new class of attribute grammars is defined. The class models naturally the use of space in a hand-written compiler. This implies that the compiler produced automatically on the basis of the grammar uses space in the same way as a practical hand-written recursive descent compiler. Furthermore, a graphical notation is introduced as a design tool for obtaining grammars in the proposed class.     

Inductive logic programming for relational knowledge discovery

Inductive logic programming (ILP) is concerned with the induction of logic programs from examples and background knowledge. In ILP, the shift of attention from program synthesis to knowledge discovery resulted in advanced techniques that are practically applicable for discovering knowledge in relational databases. This paper gives a brief introduction to ILP, presents selected ILP techniques for relational knowledge discovery and reviews selected ILP applications. Nada Lavrač, Ph.D.: She is a senior research associate at the Department of Intelligent Systems, J. Stefan Institute, Ljubljana, Slovenia (since 1978) and a visiting professor at the Klagenfurt University, Austria (since 1987). Her main research interest is in machine learning, in particular inductive logic programming and intelligent data analysis in medicine. She received a BSc in Technical Mathematics and MSc in Computer Science from Ljubljana University, and a PhD in Technical Sciences from Maribor University, Slovenia. She is coauthor of KARDIO: A Study in Deep and Qualitative Knowledge for Expert Systems, The MIT Press 1989, and Inductive Logic Programming: Techniques and Applications, Ellis Horwood 1994, and coeditor of Intelligent Data Analysis in Medicine and Pharmacology, Kluwer 1997. She was the coordinator of the European Scientific Network in Inductive Logic Programming ILPNET (1993–1996) and program cochair of the 8th European Machine Learning Conference ECML’95, and 7th International Workshop on Inductive Logic Programming ILP’97. Sašo Džeroski, Ph.D.: He is a research associate at the Department of Intelligent Systems, J. Stefan Institute, Ljubljana, Slovenia (since 1989). He has held visiting researcher positions at the Turing Institute, Glasgow (UK), Katholieke Universiteit Leuven (Belgium), German National Research Center for Computer Science (GMD), Sankt Augustin (Germany) and the Foundation for Research and Technology-Hellas (FORTH), Heraklion (Greece). His research interest is in machine learning and knowledge discovery in databases, in particular inductive logic programming and its applications and knowledge discovery in environmental databases. He is co-author of Inductive Logic Programming: Techniques and Applications, Ellis Horwood 1994. He is the scientific coordinator of ILPnet2, The Network of Excellence in Inductive Logic Programming. He was program co-chair of the 7th International Workshop on Inductive Logic Programming ILP’97 and will be program co-chair of the 16th International Conference on Machine Learning ICML’99. Masayuki Numao, Ph.D.: He is an associate professor at the Department of Computer Science, Tokyo Institute of Technology. He received a bachelor of engineering in electrical and electronics engineering in 1982 and his Ph.D. in computer science in 1987 from Tokyo Institute of Technology. He was a visiting scholar at CSLI, Stanford University from 1989 to 1990. His research interests include Artificial Intelligence, Global Intelligence and Machine Learning. Numao is a member of Information Processing Society of Japan, Japanese Society for Artificial Intelligence, Japanese Cognitive Science Society, Japan Society for Software Science and Technology and AAAI.     

A portable approach to dynamic optimization in run-time specialization

This paper proposes arun-time bytecode specialization (BCS) technique that analyzes programs and generates specialized programs at run-time in an intermediate language. By using an intermediate language for code generation, a back-end system canoptimize the specialized programs after specialization. The system uses Java virtual machine language (JVML) as the intermediate language, which allows the system to easily achieve practicalportability and to use existing sophisticated just-in-time (JIT) compilers as its back-end. The binding-time analysis algorithm is based on a type system, and covers a non-object-oriented subset of JVML. The specializer generates programs on a per-instruction basis, and can performmethod inlining at run-time. Our performance measurements show that a non-trivial application program specialized at run-time by BCS runs approximately 3–4 times faster than the unspecialized one. Despite the large overhead of JIT compilation of specialized code, we observed that the overall performance of the application can be improved. This paper is an extended version of “A Portable Approach to Generating Optimized Specialized Code”, inProceedings of Second Symposium on Programs as Data Objects (PADO-II), Lecture Notes in Computer Science, vol. 2053, pp. 138–154, Aarhus, Denmark, May 2001.²³) Hidehiko Masuhara, D.Sc.: He is an Assistant Professor at Department of Graphics and Computer Science, Graduate School of Arts and Sciences, University of Tokyo. He received his B.S., M.S. and D.Sc. degrees from Department of Information Science, University of Tokyo in 1992, 1994, and 1999, respectively. His research interests are in programming languages, especially in mechanisms to support flexible and efficient computation such as dynamic optimization and reflection. He received the best-paper award from Information Processing Society of Japan in 1996. Akinori Yonezawa, Ph.D.: He is a Professor of computer science at Department of Computer Science, University of Tokyo. He received Ph.D. in Computer Science from the Massachusetts Institute of Technology in 1977. His current major research interests are in the areas of concurrent/parallel computation models, programming languages, object-oriented computing, and distributed computing. He is the designer of an object-oriented concurrent language ABCL/1 and the editor of several books and served as an associate editor of ACM Transaction of Programming Languages and Systems (TOPLAS). Since 1998, he has been an ACM Fellow.     

Guarded attribute grammars

Contrary to a widely-held belief, it is possible to construct executable specifications of language processors that use a top-down parsing strategy and which have structures that directly reflect the structure of grammars containing left-recursive productions. A novel technique has been discovered by which the non-termination that would otherwise occur is avoided by ‘guarding’ top-down left-recursive language processors by non-left-recursive recognizers. The use of a top-down parsing strategy increases modularity and the use of left-recursive productions facilitates specification of semantic equations. A combination of the two is of significant practical value because it results in modular and expressively clear executable specifications of language processors. The new approach has been tested in an attribute grammar programming environment that has been used in a number of projects including the development of natural language interfaces, SQL processors and circuit design transformers within a VLSI design package.     

A metamodel for modeling system features and their refinement, constraint and interaction relationships

This paper presents a metamodel for modeling system features and relationships between features. The underlying idea of this metamodel is to employ features as first-class entities in the problem space of software and to improve the customization of software by explicitly specifying both static and dynamic dependencies between system features. In this metamodel, features are organized as hierarchy structures by the refinement relationships, static dependencies between features are specified by the constraint relationships, and dynamic dependencies between features are captured by the interaction relationships. A first-order logic based method is proposed to formalize constraints and to verify constraints and customization. This paper also presents a framework for interaction classification, and an informal mapping between interactions and constraints through constraint semantics. Hong Mei received the BSc and MSc degrees in computer science from the Nanjing University of Aeronautics and Astronautics (NUAA), China, in 1984 and 1987, respectively, and the PhD degree in computer science from the Shanghai Jiao Tong University in 1992. He is currently a professor of Computer Science at the Peking University, China. His current research interests include Software Engineering and Software Engineering Environment, Software Reuse and Software Component Technology, Distributed Object Technology, and Programming Language. He has published more than 100 technical papers. Wei Zhang received the BSc in Engineering Thermophysics and the MSc in Computer Science from the Nanjing University of Aeronautics and Astronautics (NUAA), China, in 1999 and 2002, respectively. He is currently a PhD student at the School of Electronics Engineering and Computer Science of the Peking University, China. His research interests include feature-oriented requirements modeling, feature-driven software architecture design and feature-oriented software reuse. Haiyan Zhao received both the BSc and the MSc degree in Computer Science from the Peking Univeristy, China, and the Ph.D degree in Information Engineering from the University of Tokyo, Japan. She is currently an associate professor of Computer Science at the Peking University, China. Her research interests include Software Reuse, Domain Engineering, Domain Specific Languange and Program Transformation.     

Program transformation system based on generalized partial computation

Generalized Partial Computation (GPC) is a program transformation method utilizing partial information about input data, abstract data types of auxiliary functions and the logical structure of a source program. GPC uses both an inference engine such as a theorem prover and a classical partial evaluator to optimize programs. Therefore, GPC is more powerful than classical partial evaluators but harder to implement and control. We have implemented an experimental GPC system called WSDFU (Waseda Simplify-Distribute-Fold-Unfold). This paper demonstrates the power of the program transformation system as well as its theorem prover and discusses some future works. Yoshihiko Futamura, Ph.D.: He is Professor of Department of Information and Computer Science and the director of the Institute for Software Production Technology (ISPT) of Waseda University. He received his BS in mathematics from Hokkaido University in 1965, MS in applied mathematics from Harvard University in 1972 and Ph.D. degree from Hokkaido University in 1985. He joined Hitachi Central Research Laboratory in 1965 and moved to Waseda University in 1991. He was a visiting professor of Uppsala University from 1985 to 1986 and a visiting scholar of Harvard University from 1988 to 1989. Automatic generation of computer programs and programming methodology are his main research fields. He is the inventor of the Futamura Projections in partial evaluation and ISO8631 PAD (Problem Analysis Diagram). Zenjiro Konishi: He is a visiting lecturer of Institute for Software Production Technology, Waseda University. He received his M. Sc. degree in mathematics from Waseda University in 1995. His research interests include automated theorem proving. He received JSSST Takahashi Award in 2001. He is a member of JSSST and IPSJ. Robert Glück, Ph.D., Habil.: He is an Associate Professor of Computer Science at the University of Copenhagen. He received his Ph.D. and Habilitation (venia docendi) from the Vienna University of Technology in 1991 and 1997. He was research assistant at the City University of New York and received twice the Erwin-Schrodinger-Fellowship of the Austrian Science Foundation (FWF). After being an Invited Fellow of the Japan Society for the Promotion of Science (JSPS), he is now funded by the PRESTO21 program for basic research of the Japan Science and Technology Corporation (JST) and located at Waseda University in Tokyo. His main research interests are advanced programming languages, theory and practice of program transformation, and metaprogramming.     

GigaE PM: a high performance communication facility using a Gigabit Ethernet

A high performance communication facility, called theGigaE PM, has been designed and implemented for parallel applications on clusters of computers using a Gigabit Ethernet. The GigaE PM provides not only a reliable high bandwidth and low latency communication, but also supports existing network protocols such as TCP/IP. A reliable communication mechanism for a parallel application is implemented on the firmware on a NIC while existing network protocols are handled by an operating system kernel. A prototype system has been implemented using an Essential Communications Gigabit Ethernet card. The performance results show that a 58.3 μs round trip time for a four byte user message, and 56.7 MBytes/sec bandwidth for a 1,468 byte message have been achieved on Intel Pentium II 400 MHz PCs. We have implemented MPICH-PM on top of the GigaE PM, and evaluated the NAS parallel benchmark performance. The results show that the IS class S performance on the GigaE PM is 1.8 times faster than that on TCP/IP. Shinji Sumimoto: He is a Senior Researcher of Parallel and Distributed System Software Laboratory at Real World Computing Partnership, JAPAN. He received BS degree in electrical engineering from Doshisha University. His research interest include parallel and distributed systems, real-time systems, and high performance communication facilities. He is a member of Information Processing Society of Japan. Hiroshi Tezuka: He is a Senior Researcher of Parallel and Distributed System Software Laboratory at Real World Computing Partnership, JAPAN. His research interests include real-time systems and operating system kernel. He is a member of the Information Processing Society of Japan, and Japan Society for Software Science and Technology. Atsushi Hori, Ph.D.: He is a Senior Researcher of Parallel and Distributed System Software Laboratory at Real World Computing Partnership, JAPAN. His current research interests include parallel operating system. He received B.S. and M.S. degrees in Electrical Engineering from Waseda University, and received Ph.D. from the University of Tokyo. He worked as a researcher in Mitsubishi Research Institute from 1981 to 1992. Hiroshi Harada: He is a Senior Researcher of Parallel and Distributed System Software Laboratory at Real World Computing Partnership, JAPAN. His research interests include distributed/parallel systems and distributed shared memory. He received BS degree in physics from Science University of Tokyo. He is a member of ACM and Information Processing Society of Japan. Toshiyuki Takahashi: He is a Researcher at Real World Computing Partnership since 1998. He received his B.S. and M.S. from the Department of Information Sciences of Science University of Tokyo in 1993 and 1995. He was a student of the Information Science Department of the University of Tokyo from 1995 to 1998. His current interests are in meta-level architecture for programming languages and high-performance software technologies. He is a member of Information Processing Society of Japan. Yutaka Ishikawa, Ph.D.: He is the chief of Parallel and Distributed System Software Laboratory at Real World Computing Partnership, JAPAN. He is currently temporary retirement from Electrotechnical Laboratory, MITI. His research interests include distributed/parallel systems, object-oriented programming languages, and real-time systems. He received the B.S., M.S. and Ph.D degrees in electrical engineering from Keio University. He is a member of the IEEE Computer Society, ACM, Information Processing Society of Japan, and Japan Society for Software Science and Technology.     

Aspects as Modular Language Extensions

Extensible programming languages and their compilers use highly modular specifications of languages and language extensions that allow a variety of different language feature sets to be easily imported into the programming environment by the programmer. Our model of extensible languages is based on higher-order attribute grammars and an extension called “forwarding” that mimics a simple rewriting process. It is designed so that no additional attribute definitions need to be written when combining a language with language extensions. Thus, programmers can remain unaware of the underlying attribute grammars when building customized languages by importing various extensions. In this paper we show how aspects and the aspect weaving process from Aspect-Oriented Programming can be specified as a modular language extension and imported into a base language specified in an extensible programming language framework.     

Web information visualization method employing immune network model for finding topic stream from document-set sequence

A Web information visualization method based on the document set-wise processing is proposed to find the topic stream from a sequence of document sets. Although the hugeness as well as its dynamic nature of the Web is burden for the users, it will also bring them a chance for business and research if they can notice the trends or movement of the real world from the Web. A sequence of document sets found on the Web, such as online news article sets is focused on in this paper. The proposed method employs the immune network model, in which the property of memory cell is used to find the topical relation among document sets. After several types of memory cell models are proposed and evaluated, the experimental results show that the proposed method with memory cell can find more topic streams than that without memory cell. Yasufumi Takama, D.Eng.: He received his B.S., M.S. and Dr.Eng. degrees from the University of Tokyo in 1994, 1996, and 1999, respectively. From 1999 to 2002 he was with Tokyo Institute of Technology, Japan. Since 2002, he has been Associate Professor of Department of Electronic Systems and Engineering, Tokyo Metropolitan Institute of Technology, Tokyo, Japan. He has also been participating in JST (Japan Science and Technology Corporation) since October 2000. His current research interests include artificial intelligence, Web information retrieval and visualization systems, and artificial immune systems. He is a member of JSAI (Japanese Society of Artificial Intelligence), IPS J (Information Processing Society of Japan), and SOFT (Japan Society for Fuzzy Theory and Systems). Kaoru Hirota, D.Eng.: He received his B.E., M.E. and Dr.Eng. degrees in electronics from Tokyo Institute of Technology, Tokyo, Japan, in 1974, 1976, and 1979, respectively. From 1979 to 1982 and from 1982 to 1995 he was with the Sagami Institute of Technology and Hosei University, respectively. Since 1995, he has been with the Interdisciplinary Graduate School of Science and Technology, Tokyo Institute of Technology, Yokohama, Japan. He is now a department head professor of Department of Computational Intelligence and Systems Science. Dr.Hirota is a member of IFSA (International Fuzzy Systems Association (Vice President 1991–1993), Treasurer 1997–2001), IEEE (Associate Editors of IEEE Transactions on Fuzzy Systems (1993–1995) and IEEE Transactions on Industrial Electronics (1996–2000)) and SOFT (Japan Society for Fuzzy Theory and Systems (Vice President 1995–1997, President 2001–2003)), and he is an editor in chief of Int. J. of Advanced Computational Intelligence.     

The evolution of stochastic regular motifs for protein sequences

Stochastic regular motifs are evolved for protein sequences using genetic programming. The motif language, SRE-DNA, is a stochastic regular expression language suitable for denoting biosequences. Three restricted versions of SRE-DNA are used as target languages for evolved motifs. The genetic programming experiments are implemented in DCTG-GP, which is a genetic programming system that uses logic-based attribute grammars to define the target language for evolved programs. Earlier preliminary work tested SRE-DNA’s viability as a representation language for aligned protein sequences. This work establishes that SRE-DNA is also suitable for evolving motifs for unaligned sets of sequences. Brian J. Ross, Ph.D.: He is an associate professor of computer science at Brock University, where he has worked since 1992. He obtained his BCSc at the University of Manitoba, Canada, in 1984, his MSc at the University of British Columbia, Canada, in 1988, and his PhD at the University of Edinburgh, Scotland, in 1992. His research interests include evolutionary computation, machine learning, language induction, concurrency, and logic programming.     

Proofs of a set of hybrid let-polymorphic type inference algorithms

We present a generalized let-polymorphic type inference algorithm, prove that any of its instances is sound and complete with respect to the Hindley/Milner let-polymorphic type system, and find a condition on two instance algorithms so that one algorithm should find type errors earlier than the other. By instantiating the generalized algorithm with different parameters, we can obtain not only the two opposite algorithms (the bottom-up standard algorithmW and the top-down algorithmM) but also other hybrid algorithms which are used in real compilers. Such instances’ soudness and completeness follow automatically, and their relative earliness in detecting type-errors is determined by checking a simple condition. The set of instances of the generalized algorithm is a superset of those used in the two most popular ML compilers: SML/NJ and OCaml. This work is supported by Creative Research Initiatives of the Korean Ministry of Science and Technology National Creative Research Initiative Center, http://ropas.kaist.ac.kr Work done while the third author was associated with Korea Advanced Institute of Science and Technology Hyunjun Eo: He is a Ph.D. candidate in the Department of Computer Science at KAIST (Korea Advanced Institute of Science and Technology). He recieved his bachelor’s degree and master’s degree in Computer Science from KAIST in 1996 and 1998, respectively. His research interest has been on static program analysis, fixpoint iteration algorithm and higher-order and typed languages. From fall 1998, he has been a research assistant of the National Creative Research Initiative Center for Research on Program Analysis System. He is currently working on developing a tool for automatic generation of program analyzer. Oukseh Lee: He is a Ph.D. candidate in the Department of Computer Science at KAIST (Korea Advanced Institute of Science and Technology). He received his bachelor’s and master’s degree in Computer Science from KAIST in 1995 and 1997, respectively. His research interest has been on static program analysis, type system, program language implementation, higher-order and typed languages, and program verification. From 1998, he has been a research assistant of the National Creative Research Initiative Center for Research on Program Analysis System. He is currently working on compile-time analyses and verification for the memory behavior of programs. Kwangkeun Yi, Ph.D.: His research interest has been on semanticbased program analysis and systems application of language technologies. After his Ph.D. from University of Illinois at Urbana-Champaign he joined the Software Principles Research Department at Bell Laboratories, where he worked on various static analysis approaches for higher-order and typed programming languages. For 1995 to 2003 he was a faculty member in the Department of Computer Science, Korea Advanced Institute of Science and Technology. Since fall 2003, he has been a faculty member in the School of Computer Science and Engineering, Seoul National University.     

Pitch-Dependent Identification of Musical Instrument Sounds

This paper describes a musical instrument identification method that takes into consideration the pitch dependency of timbres of musical instruments. The difficulty in musical instrument identification resides in the pitch dependency of musical instrument sounds, that is, acoustic features of most musical instruments vary according to the pitch (fundamental frequency, F0). To cope with this difficulty, we propose an F0-dependent multivariate normal distribution, where each element of the mean vector is represented by a function of F0. Our method first extracts 129 features (e.g., the spectral centroid, the gradient of the straight line approximating the power envelope) from a musical instrument sound and then reduces the dimensionality of the feature space into 18 dimension. In the 18-dimensional feature space, it calculates an F0-dependent mean function and an F0-normalized covariance, and finally applies the Bayes decision rule. Experimental results of identifying 6,247 solo tones of 19 musical instruments shows that the proposed method improved the recognition rate from 75.73% to 79.73%. This research was partially supported by the Ministry of Education, Culture, Sports, Science and Technology (MEXT), Grant-in-Aid for Scientific Research (A), No.15200015, and Informatics Research Center for Development of Knowledge Society Infrastructure (COE program of MEXT, Japan). Tetsuro Kitahara received the B.S. from Tokyo University of Science in 2002 and the M.S. from Kyoto University in 2004. He is currently a Ph.D. course student at Graduate School of Informatics, Kyoto University. Since 2005, he has been a Research Fellow of the Japan Society for the Promotion of Science. His research interests include music informatics. He recieved IPSJ 65th National Convention Student Award in 2003, IPSJ 66th National Convention Student Award and TELECOM System Technology Award for Student in 2004, and IPSJ 67th National Convention Best Paper Award for Young Researcher in 2005. He is a student member of IPSJ, IEICE, JSAI, ASJ, and JSMPC. Masataka Goto received his Doctor of Engineering degree in Electronics, Information and Communication Engineering from Waseda University, Japan, in 1998. He then joined the Electrotechnical Laboratory (ETL; reorganized as the National Institute of Advanced Industrial Science and Technology (AIST) in 2001), where he has been engaged as a researcher ever since. He served concurrently as a researcher in Precursory Research for Embryonic Science and Technology (PRESTO), Japan Science and Technology Corporation (JST) from 2000 to 2003, and an associate professor of the Department of Intelligent Interaction Technologies, Graduate School of Systems and Information Engineering, University of Tsukuba since 2005. His research interests include music information processing and spoken language processing. Dr. Goto received seventeen awards including the IPSJ Best Paper Award and IPSJ Yamashita SIG Research Awards (MUS and SLP) from the Information Processing Society of Japan (IPSJ), Awaya Prize for Outstanding Presentation and Award for Outstanding Poster Presentation from the Acoustical Society of Japan (ASJ), Award for Best Presentation from the Japanese Society for Music Perception and Cognition (JSMPC), WISS 2000 Best Paper Award and Best Presentation Award, and Interaction 2003 Best Paper Award. He is a member of the IPSJ, ASJ, JSMPC, Institute of Electronics, Information and Communication Engineers (IEICE), and International Speech Communication Association (ISCA). Hiroshi G. Okuno received the B.A. and Ph.D from the University of Tokyo in 1972 and 1996, respectively. He worked for Nippon Telegraph and Telephone, Kitano Symbiotic Systems Project, and Tokyo University of Science. He is currently a professor at the Department of Intelligence Technology and Science, Graduate School of Informatics, Kyoto University. He was a visiting scholar at Stanford University, and a visiting associate professor at the University of Tokyo. He has done research in programming languages, parallel processing, and reasoning mechanism in AI, and he is currently engaged in computational auditory scene analysis, music scene analysis and robot audition. He received the best paper awards from the Japanese Society for Artificial Intelligence and the International Society for Applied Intelligence, in 1991 and 2001, respectively. He edited with David Rosenthal “Computational Auditory Scene Analysis” from Lawrence Erlbaum Associates in 1998 and with Taiichi Yuasa “Advanced Lisp Technology” from Taylor and Francis Inc. in 2002. He is a member of IPSJ, JSAI, JSSST, JSCS, ACM, AAAI, ASA, and IEEE.     

The design of a language processor generator

Language processor generators are systems that produce various language processors (including compilers) on the basis of a high-level specification. The design of language processor generators is discussed on the basis of experiments with a traditional compiler writing system (HLP78) employing pore LALR parsing and general attribute grammars. It is argued that these methods are too primitive from the practical point of view. The design of a new language processor generator, HLP84, is based on this view. This system is an attempt to provide high-level tools for a restricted class of applications (one-pass analysis). The syntactic facilities include regular expressions on the right-hand sides of productions, a disambiguating mechanism that is integrated with regular expressions, and a mechanism for using semantic information to aid parsing. The semantic facilities include automatic support for semantic error handling and for symbol tables. Early experiences with the new system show that in spite of the general overhead caused by the higher automation level, the system allows the generation of reasonably efficient processors.     

Inductive attribute grammars

Attribute grammars are traditionally constrained to be noncircular. In using attribute grammars to specify the semantics of programming languages, this noncircularity limitation has restricted attribute grammars to compile-time or static semantics. Inductive attribute grammars add a general form of circularity to this standard approach. Inductive attribute grammars have the expressiveness required to describe the full semantics of programming languages, while at the same time maintaining the declarative character of standard attribute grammars. This expanded view of attribute grammars proves to be useful in interactive language-based programming environments, as inductive attribute grammars allow the environment to provide an interpreter for incremental re-evaluation of programs after small changes to the code. The addition of run-time semantics via circular attribute grammars permits automatically generated environments to be complete, in that incremental static semantic checking and fast incremental execution are now available within a single framework.The authors' present affiliations are the United States Geological Survey and the Northrop Corporation respectively.     

Intelligent systems using Web-pages as knowledge base for statistical decision making

In this paper, we propose an approach to the construction of an intelligent system that handles various domain information provided on the Internet. The intelligent system adopts statistical decision-making as its reasoning framework and automatically constructs probabilistic knowledge, required for its decision-making, from Web-pages. This construction of probabilistic knowledge is carried out using aprobability interpretation idea that transforms statements in Web-pages into constraints on the subjective probabilities of a person who describes the statements. In this paper, we particularly focus on describing the basic idea of our approach and on discussing difficulties in our approach, including our perspective. Kazunori Fujimoto: He received bachelor’s degree from Department of Electrical Engineering, Doshisha University, Japan, in 1989, and master’s degree from Division of Applied Systems Science, Kyoto University, Japan, in 1992. From there, he joined NTT Electrical Communications Laboratories, Tokyo, Japan, and has been engaged in research on Artificial Intelligence. He is currently interested in probabilistic reasoning, knowledge acquisition, and especially in quantitative approaches to research in human cognition and behavior. Mr. Fujimoto is a member of Decision Analysis Society, The Behaviormetric Society of Japan, Japanese Society for Artificial Intelligence, Information Processing Society of Japan, and Japanese Society for Fuzzy Theory and Systems. Kazumitsu Matsuzawa: He received B.S. and M.S. degrees in electronic engineering from Tokyo Institute of Technology, Tokyo, Japan, in 1975 and 1977. From there, he joined NTT Electrical Communications Laboratories, Tokyo, Japan, and has been engaged in research on computer architecture and the design of LSI. He is currently concerned with AI technology. Mr. Matsuzawa is a member of The Institute of Electronics, Information and Communication Engineers, Information Processing Society of Japan, Japanese Society for Artificial Intelligence, and Japanese Society for Fuzzy Theory and Systems.     

Secure software infrastructure in the internet age

The rapid growth and penetration of the Internet are now leading us to a world where networks are ubiquitous and everything is connected. Breaking the distance barrier by the ubiquitous connection, however, is a two-edged sword. Our network infrastructure today is still fragile and thus “everything is connected” may simply mean “everything can be attacked from whatever place on the earth.” In this paper, we first point out the importance and inherent problems of software systems that underlay open and extensible networks, especially the Internet. We put emphasis on software since software vulnerabilities account for most attacks, incidents, or even disasters on the Internet today. Next we present general ideas of promising techniques in defense of software systems, including theoretical, language-based, and runtime solutions. Finally, we show our experience in developing a secure mail system. Etsuya Shibayama, D.Sc.: He is a professor of the Graduate School of Information Science and Engineering at Tokyo Institute of Technology. He received B.Sc. and M.Sc. in mathematical sciences from Kyoto University in 1981 and 1983, respectively, and D.Sc. in information science from the University of Tokyo in 1991. He is interested in various topics in software including design and implementation of textual and visual programming languages, system software, and user interface software. Recently, he has been doing research on language-based software security and methodologies for building secure software. Akinori Yonezawa, Ph.D.: He is a Professor of computer science at Department of Computer Science, the University of Tokyo. He received his Ph.D. in Computer Science form the Massachusetts Institute of Technology in 1977. His current major research interests are in the areas of concurrent/parallel computation models, programming languages, object-oriented computing and distributed computing. He is the designer of and object-oriented concurrent language ABCL/1 and the editor of several books and served as an associate editor of ACM Transaction of Programming Language and Systems (TOPLAS). Since 1998, he has been an ACM Fellow.     

Logic-based genetic programming with definite clause translation grammars

DCTG-GP is a genetic programming system that uses definite clause translation grammars. A DCTG is a logical version of an attribute grammar that supports the definition of context-free languages, and it allows semantic information associated with a language to be easily accommodated by the grammar. This is useful in genetic programming for defining the interpreter of a target language, or incorporating both syntactic and semantic problem-specific constraints into the evolutionary search. The DCTG-GP system improves on other grammar-based GP systems by permitting nontrivial semantic aspects of the language to be defined with the grammar. It also automatically analyzes grammar rules in order to determine their minimal depth and termination characteristics, which are required when generating random program trees of varied shapes and sizes. An application using DCTG-GP is described. Brian James Ross, Ph.D.: He is an associate professor of computer science at Brock University, where he has worked since 1992. He obtained his BCSc at the University of Manitoba, Canada, in 1984, his MSc at the University of British Columbia, Canada, in 1988, and his PhD at the University of Edinburgh, Scotland, in 1992. His research interests include evolutionary computation, machine learning, language induction, concurrency, and logic programming.     

A pure embedding of attribute grammars

Attribute grammars are a powerful specification paradigm for many language processing tasks, particularly semantic analysis of programming languages. Recent attribute grammar systems use dynamic scheduling algorithms to evaluate attributes on demand. In this paper, we show how to remove the need for a generator, by embedding a dynamic approach in a modern, object-oriented and functional programming language. The result is a small, lightweight attribute grammar library that is part of our larger Kiama language processing library. Kiama’s attribute grammar library supports a range of advanced features including cached, uncached, higher order, parameterised and circular attributes. Forwarding is available to modularise higher order attributes and decorators abstract away from the details of attribute value propagation. Kiama also implements new techniques for dynamic extension and variation of attribute equations. We use the Scala programming language because of its support for domain-specific notations and emphasis on scalability. Unlike generators with specialised notation, Kiama attribute grammars use standard Scala notations such as pattern-matching functions for equations, traits and mixins for composition and implicit parameters for forwarding. A benchmarking exercise shows that our approach is practical for realistic language processing.