Efficient implementation of lattice operations

ABSTRACT

Lattice operations such as greatest lower bound (GLB), least upper bound (LUB), and relative complementation (BUTNOT) are becoming more and more important in programming languages supporting object inheritance. We present a general technique for the efficient implementation of such operations based on an encoding method. The effect of the encoding is to plunge the given ordering into a boolean lattice of binary words, leading to an almost constant time complexity of the lattice operations. A first method is described based on a transitive closure approach. Then a more space-efficient method minimizing code-word length is described. Finally a powerful grouping technique called modulation is presented, which drastically reduces code space while keeping all three lattice operations highly efficient. This technique takes into account idiosyncrasies of the topology of the poset being encoded that are quite likely to occur in practice. All methods are formally justified. We see this work as an original contribution towards using semantic (vz., in this case, taxonomic) information in the engineering pragmatics of storage and retrieval of (vz., partially or quasi-ordered) information.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Hassan Ait-Kaci, A lattice theoretic approach to computation based on a calculus of partially ordered type structures (property inheritance, semantic nets, graph unification), 1984
• 3: Hassan Aït-Kaci, An algebraic semantics approach to the effective resolution of type equations, Theoretical Computer Science, v.45 n.3, p.293-351, Sept., 1986
• 4: AiT-KACI, H., BOYER, R., L1NCOLN, P., ANO NASR, R. Efficient implementation of object inheritance. Tech. Rep. AI-102-87, Microelectronics and Computer Technology Corporation, Austin, Tex., 1987.
• 5: H Aït-Kaci , R Nasr, Login: A logic programming language with built-in inheritance, Journal of Logic Programming, v.3 n.3, p.185-215, Oct. 1986 [doi>10.1016/0743-1066(86)90013-0]
• 6: AiT-KACI, H., AND LINCOLN, P. LIFE: A natural language for natural language. Teeh. Rep. ACA-ST-074-88, Microelectronics and Computer Technology Corporation, Austin, Tex., Feb. 1988.
• 7: A. Albano , F. Giannotti , R. Orsini , D. Pedreschi, The type system of Galileo, Data types and persistence, Springer-Verlag, London, 1988
• 8: BIRKHOFF, G. Lattice Theory. Volume 25 of Colloquium Publications, American Mathematical{ Society, Providence, R.I., (third edition) (1979).
• 9: Daniel G. Bobrow , Kenneth Kahn , Gregor Kiczales , Larry Masinter , Mark Stefik , Frank Zdybel, CommonLoops: merging Lisp and object-oriented programming, Conference proceedings on Object-oriented programming systems, languages and applications, p.17-29, September 29-October 02, 1986, Portland, Oregon, United States
• 10: CARDELLI, L. Amber. Tech. Memo. 11271-840924-10TM, AT&T Bell Labs, Murray Hill, N.J., 1984.
• 11: Joseph A. Goguen , José Meseguer, Extensions and foundations of object-oriented programming, ACM SIGPLAN Notices, v.21 n.10, p.153-162, Oct. 1986
• 12: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 13: J. Jaffar , J.-L. Lassez, Constraint logic programming, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.111-119, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41635]
• 14: David McAllester , Ramin Zabih, Boolean classes, ACM SIGPLAN Notices, v.21 n.11, p.417-423, Nov. 1986
• 15: MUKAI, K. Anadic tuples in Prolog. Paper presented at the workshop organized by J. Minker on Foundations of Deductive Databases and Logic Programming (Washington, D.C., Aug. 1986).
• 16: PARKER, D.S. Partial Order Programming. Tech. Rep. CSD-870067, Computer Science Department, UCLA, Los Angeles, Cal., Dec. 1987.
• 17: SMOLKA, G., NUTT, W., GOGUEN, Z., AND MESEGUER, J. Order-sorted equational computation. In H. Ait-Kaci, and M. Nivat, Eds. Resolution of Equations in Algebraic Structures. Academic Press, Cambridge, Mass. (Forthcoming).
• 18: STICKEL, M. Automatic deduction by theory resolution. In Proceedings of International Joint Conference on Artificial Intelligence (Los Angeles, Cal. 1985). Morgan Kauffman, 1985, pp. 1181-1186.
• 19: Christoph Walther, A mechanical solution of Schubert's steamroller by many-sorted resolution, Artificial Intelligence, v.26 n.2, p.217-224, May 1985 [doi>10.1016/0004-3702(85)90029-3]
• 20: Daniel Weinreb, Lisp machine manual, Massachusetts Institute of Technology, 1981

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Frames and scripts

General Terms:
Algorithms, Languages, Performance