Lecture Notes in Artificial Intelligence 2408
Subseries of Lecture Notes in Computer Science
Edited by J. G. Carbonell and J. Siekmann
Lecture Notes in Computer Science
Edited by G. Goos, J. Hartmanis, and J. van Leeuwen
3
Berlin
Heidelberg
New York
Barcelona
Hong Kong
London
Milan
Paris
Tokyo
,Antonis C. Kakas Fariba Sadri (Eds.)
Computational Logic:
Logic Programming
and Beyond
Essays in Honour of Robert A. Kowalski
Part II
13
,Series Editors
Jaime G. Carbonell,Carnegie Mellon University, Pittsburgh, PA, USA
Jörg Siekmann, University of Saarland, Saarbrücken, Germany
Volume Editors
Antonis C. Kakas
University of Cyprus, Department of Computer Science
75 Kallipoleos St., 1678 Nicosia, Cyprus
E-mail:
Fariba Sadri
Imperial College of Science, Technology and Medicine
Department of Computing, 180 Queen’s Gate
London SW7 2BZ, United Kingdom
E-mail:
Cataloging-in-Publication Data applied for
Die Deutsche Bibliothek - CIP-Einheitsaufnahme
Computational logic: logig programming and beyond : essays in honour of Robert
A. Kowalski / Antonis C. Kakas ; Fariba Sadri (ed.). - Berlin ; Heidelberg ; New
York ; Barcelona ; Hong Kong ; London ; Milan ; Paris ; Tokyo : Springer Pt. 2 . -
(2002) (Lecture notes in computer science ; Vol. 2408 : Lecture notes in artificial
intelligence) ISBN 3-540-43960-9
CR Subject Classification (1998): I.2.3, D.1.6, I.2, F.4, I.1
ISSN 0302-9743
ISBN 3-540-43960-9 Springer-Verlag Berlin Heidelberg New York
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is
concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting,
reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication
or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965,
in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are
liable for prosecution under the German Copyright Law.
Springer-Verlag Berlin Heidelberg New York
a member of BertelsmannSpringer Science+Business Media GmbH
http://www.springer.de
© Springer-Verlag Berlin Heidelberg 2002
Printed in Germany
Typesetting: Camera-ready by author, data conversion by Boller Mediendesign
Printed on acid-free paper SPIN 10873683 06/3142 543210
, Foreword
Alan Robinson
This set of essays pays tribute to Bob Kowalski on his 60th birthday, an anniversary
which gives his friends and colleagues an excuse to celebrate his career as an original
thinker, a charismatic communicator, and a forceful intellectual leader. The logic
programming community hereby and herein conveys its respect and thanks to him for
his pivotal role in creating and fostering the conceptual paradigm which is its raison
d'être.
The diversity of interests covered here reflects the variety of Bob's concerns. Read
on. It is an intellectual feast. Before you begin, permit me to send him a brief
personal, but public, message: Bob, how right you were, and how wrong I was.
I should explain. When Bob arrived in Edinburgh in 1967 resolution was as yet fairly
new, having taken several years to become at all widely known. Research groups to
investigate various aspects of resolution sprang up at several institutions, the one
organized by Bernard Meltzer at Edinburgh University being among the first. For the
half-dozen years that Bob was a leading member of Bernard's group, I was a frequent
visitor to it, and I saw a lot of him. We had many discussions about logic,
computation, and language. By 1970, the group had zeroed in on three ideas which
were soon to help make logic programming possible: the specialized inference rule of
linear resolution using a selection function, together with the plan of restricting it to
Horn clauses ("LUSH resolution"); the adoption of an operational semantics for Horn
clauses; and a marvellously fast implementation technique for linear resolution,
based on structure-sharing of syntactic expressions. Bob believed that this work now
made it possible to use the predicate calculus as a programming language. I was
sceptical. My focus was still on the original motivation for resolution, to build better
theorem provers.
I worried that Bob had been sidetracked by an enticing illusion. In particular because
of my intellectual investment in the classical semantics of predicate logic I was quite
put off by the proposed operational semantics for Horn clauses. This seemed to me
nothing but an adoption of MIT's notorious "Planner" ideology of computational
inference. I did try, briefly, to persuade Bob to see things my way, but there was no
stopping him. Thank goodness I could not change his mind, for I soon had to change
mine.
In 1971, Bob and Alain Colmerauer first got together. They pooled their thinking.
The rest is history. The idea of using predicate logic as a programming language then
really boomed, propelled by the rush of creative energy generated by the ensuing
Marseilles-Edinburgh synergy. The merger of Bob's and Alain's independent insights
launched a new era. Bob's dream came true, confirmed by the spectacular practical
success of Alain's Prolog. My own doubts were swept away. In the thirty years since
then, logic programming has developed into a jewel of computer science, known all
over the world.
Happy 60th birthday, Bob, from all of us.
Subseries of Lecture Notes in Computer Science
Edited by J. G. Carbonell and J. Siekmann
Lecture Notes in Computer Science
Edited by G. Goos, J. Hartmanis, and J. van Leeuwen
3
Berlin
Heidelberg
New York
Barcelona
Hong Kong
London
Milan
Paris
Tokyo
,Antonis C. Kakas Fariba Sadri (Eds.)
Computational Logic:
Logic Programming
and Beyond
Essays in Honour of Robert A. Kowalski
Part II
13
,Series Editors
Jaime G. Carbonell,Carnegie Mellon University, Pittsburgh, PA, USA
Jörg Siekmann, University of Saarland, Saarbrücken, Germany
Volume Editors
Antonis C. Kakas
University of Cyprus, Department of Computer Science
75 Kallipoleos St., 1678 Nicosia, Cyprus
E-mail:
Fariba Sadri
Imperial College of Science, Technology and Medicine
Department of Computing, 180 Queen’s Gate
London SW7 2BZ, United Kingdom
E-mail:
Cataloging-in-Publication Data applied for
Die Deutsche Bibliothek - CIP-Einheitsaufnahme
Computational logic: logig programming and beyond : essays in honour of Robert
A. Kowalski / Antonis C. Kakas ; Fariba Sadri (ed.). - Berlin ; Heidelberg ; New
York ; Barcelona ; Hong Kong ; London ; Milan ; Paris ; Tokyo : Springer Pt. 2 . -
(2002) (Lecture notes in computer science ; Vol. 2408 : Lecture notes in artificial
intelligence) ISBN 3-540-43960-9
CR Subject Classification (1998): I.2.3, D.1.6, I.2, F.4, I.1
ISSN 0302-9743
ISBN 3-540-43960-9 Springer-Verlag Berlin Heidelberg New York
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is
concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting,
reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication
or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965,
in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are
liable for prosecution under the German Copyright Law.
Springer-Verlag Berlin Heidelberg New York
a member of BertelsmannSpringer Science+Business Media GmbH
http://www.springer.de
© Springer-Verlag Berlin Heidelberg 2002
Printed in Germany
Typesetting: Camera-ready by author, data conversion by Boller Mediendesign
Printed on acid-free paper SPIN 10873683 06/3142 543210
, Foreword
Alan Robinson
This set of essays pays tribute to Bob Kowalski on his 60th birthday, an anniversary
which gives his friends and colleagues an excuse to celebrate his career as an original
thinker, a charismatic communicator, and a forceful intellectual leader. The logic
programming community hereby and herein conveys its respect and thanks to him for
his pivotal role in creating and fostering the conceptual paradigm which is its raison
d'être.
The diversity of interests covered here reflects the variety of Bob's concerns. Read
on. It is an intellectual feast. Before you begin, permit me to send him a brief
personal, but public, message: Bob, how right you were, and how wrong I was.
I should explain. When Bob arrived in Edinburgh in 1967 resolution was as yet fairly
new, having taken several years to become at all widely known. Research groups to
investigate various aspects of resolution sprang up at several institutions, the one
organized by Bernard Meltzer at Edinburgh University being among the first. For the
half-dozen years that Bob was a leading member of Bernard's group, I was a frequent
visitor to it, and I saw a lot of him. We had many discussions about logic,
computation, and language. By 1970, the group had zeroed in on three ideas which
were soon to help make logic programming possible: the specialized inference rule of
linear resolution using a selection function, together with the plan of restricting it to
Horn clauses ("LUSH resolution"); the adoption of an operational semantics for Horn
clauses; and a marvellously fast implementation technique for linear resolution,
based on structure-sharing of syntactic expressions. Bob believed that this work now
made it possible to use the predicate calculus as a programming language. I was
sceptical. My focus was still on the original motivation for resolution, to build better
theorem provers.
I worried that Bob had been sidetracked by an enticing illusion. In particular because
of my intellectual investment in the classical semantics of predicate logic I was quite
put off by the proposed operational semantics for Horn clauses. This seemed to me
nothing but an adoption of MIT's notorious "Planner" ideology of computational
inference. I did try, briefly, to persuade Bob to see things my way, but there was no
stopping him. Thank goodness I could not change his mind, for I soon had to change
mine.
In 1971, Bob and Alain Colmerauer first got together. They pooled their thinking.
The rest is history. The idea of using predicate logic as a programming language then
really boomed, propelled by the rush of creative energy generated by the ensuing
Marseilles-Edinburgh synergy. The merger of Bob's and Alain's independent insights
launched a new era. Bob's dream came true, confirmed by the spectacular practical
success of Alain's Prolog. My own doubts were swept away. In the thirty years since
then, logic programming has developed into a jewel of computer science, known all
over the world.
Happy 60th birthday, Bob, from all of us.