Seif Haridi
Peter Van Roy
Gert Smolka
Skip Abstract Section
Abstract
We define a practical algorithm for distrubuted rational tree unification and prove its correctness in both the off-line and on-line cases. We derive the distributed algorithm from a centralized one, showing clearly the trade-offs between local and distributed execution. The algorithm is used to realize logic variables in the Mozart Programming System, which implements the Oz language (see http://www/mozart-oz.org). Oz appears to the programmer as a concurrent object-oriented language with dataflow synchronization. Logic variables implement the dataflow behavior. We show that lohgic variables can easily be added to the more restricted models of Java and ML, thus providing an alternative way to do concurent programming in these languages. We present common distributed programming idioms in a network-transparent way using logic variables. We show that in common cases the algorithm maintains the same message latency as explicit message passing. In addition, it is able to handle uncommon cases that arise from the properties of latency tolerance and third-party independence. This is evidence that using logic variables in distributed computing is beneficial at both the system and language levels. At the system level, they improve latency tolerance and third-party independence. At the language level, they help make network-transparent distribution practical.
- ALFORD, M. W., LAMPORT, L., AND MULLERY, G. P. 1985. Lecture Notes in Computer Science, vol. 190. Springer Verlag, Chapter 2. Basic Concepts, in Distributed Systems-Methods and Tools for Specification, An Advanced Course.]] Google Scholar
- ALOUINI, I. AND VAN ROY, P. 1999. Le protocole r6parti de Distributed Oz (in French). In Colloque Francophone sur l'Ingdnierie des Protocoles (CFIP 99). 283-298.]]Google Scholar
- ARMSTRONG, J., WILLIAMS, M., WIKSTROM, C., AND VIRDING, R. 1996. Concurrent Programming in Erlang. Prentice-HM1, Englewood Cliffs, N.J.]] Google Scholar
- ARVIND AND THOMAS, R. E. 1980. I-Structures: An efficient data type for functional languages. Tech. Rep. 210, MIT, Laboratory for Computer Science.]]Google Scholar
- BAL, H. E., STEINER, J. G., AND TANENBAUM, A. S. 1989. Programming languages for distributed computing systems. ACM Cornput. Surv. 21, 3 (Sept.), 261-322.]] Google Scholar
- BRAND, P., VAN ROY, P., COLLET, R., AND I~LINTSKOG, E. 1999. Formal definition and correctness of a reliable mobile-state protocol for constructing fault-tolerant applications. In preparation.]]Google Scholar
- CARDELLI, L. 1995. A language with distributed scope. ACM Trans. Comput. Syst. 8, 1 (Jan.), 27-59.]]Google Scholar
- CHOW, R. AND JOHNSON, T. 1997. Distributed Operating Systems and Algorithms. Addison- Wesley, San Francisco, Calif.]] Google Scholar
- COLMERAUER, A. 1982. Prolog and Infinite Trees. Academic Press. In Logic Programming, Keith L. Clark and Sten-Ake Tarnlund, eds.]]Google Scholar
- COURCELLE, B. 1983. Fundamental properties of infinite trees. Theoretical Computer Science 25, 95-169.]]Google Scholar
- DFKI Oz 1998. DFKI Oz version 2.0. Available at http://www.ps.uni-sb.de.]]Google Scholar
- DIAZ, M., RUBIO, B., AND TROYA, J. M. 1997. DRL: A distributed real-time logic language. Comput. Lang. 23, 2-4, 87-120.]]Google Scholar
- DUCHIER, D., KORNSTAEDT, L., SCHULTE, C., AND SMOLKA, G. 1998. A Higher-order Module Discipline with Separate Compilation, Dynamic Linking, and Pickling. Tech. rep., Programming Systems Lab, DFKI and Universitgt des Saarlandes. DRAFT.]]Google Scholar
- FOSTER, I. 1988. Parallel implementation of Parlog. In International Conference on Parallel Processing. IEEE Computer Society, 9-16.]]Google Scholar
- FUJISE, T., CHIKAYAMA, T., ROKUSAWA, K., AND NAKASE, A. 1994. KLIC: A portable implementation of KL1. In Fifth Generation Computing Systems (FGCS '94). 66-79.]] Google Scholar
- GOSLING, J., JoY, B., AND STEELE, G. 1996. The Java Language Specification. Addison-Wesley. Available at http ://www. j avasoft, com.]] Google Scholar
- GUDEMAN, D. 1993. Representing type information in dynamically typed languages. Tech. Rep. TR93-27, University of Arizona, Department of Computer Science. Sept.]]Google Scholar
- HALSTEAD, R. H. 1985. MultiLisp: A language for concurrent symbolic computation. ACM Trans. Program. Lang. Syst. 7, 4 (Oct.), 501-538.]] Google Scholar
- HARIDI, S. 1981. Logic programming based on a natural deduction system. Ph.D. thesis, Royal Institute of Technology, Stockholm.]]Google Scholar
- HARIDI, S. AND FRANZI~N, N. 1999. Tutorial of Oz. Tech. rep. In Mozart documentation, available at http ://www. mozart-oz, org.]]Google Scholar
- HARIDI, S. AND SAHLIN, D. 1984. Efficient implementation of unification of cyclic structures. Ellis Horwood Limited. In Implementations of Prolog, J. A. Campbell, ed.]]Google Scholar
- HARIDI, S., VAN ROY, P., BRAND, P., AND SCHULTE, C. 1998. Programming languages for distributed applications. New Generation Computing 16, 3 (May), 223-261.]] Google Scholar
- HARIDI, S., VAN ROY, P., AND SMOLKA, G. 1997. An overview of the design of Distributed Oz. In the 2rid International Symposium on Parallel Symbolic Computation (PASCO 97). ACM.]] Google Scholar
- HENZ, M. 1997&. Objects for Concurrent Constraint Programming. The Kluwer International Series in Engineering and Computer Science, vol. 426. Kluwer Academic Publishers, Boston.]] Google Scholar
- HENZ, M. 1997b. Objects in Oz. Ph.D. thesis, Universitgt des Saarlandes, Fachbereich Informatik, Saarbriicken, Germany.]]Google Scholar
- IANNUCCI, R. t. 1990. Parallel Machines: Parallel Machine Languages. The Emergence of Hybrid Dataflow Computer Architectures. Kluwer, Dordrecht, the Netherlands.]] Google Scholar
- ICHIYOSHI, N., MIYAZAKI, T., AND TAKI, K. 1987. A distributed implementation of Flat GHC on the Multi-PSI. In gth International Conference on Logic Programming. MIT Press, 257-275.]]Google Scholar
- JAFFAR, J. AND MAHER, M. 1994. Constraint logic programming: A survey. J. Log. Prog. 19/20, 503-581.]]Google Scholar
- LAMMA, E., MELLO, P., STEFANELLI, C., AND VAN HENTENRYCK, P. 1997. Improving distributed unification through type analysis. In Euro-Par '97 Parallel Processing. Lecture Notes in Computer Science, vol. 1300. Springer-Verlag, 1181-1190.]] Google Scholar
- LEA, D. 1997. Concurrent Programming in Java. Addison-Wesley.]] Google Scholar
- LEUNG, H.-F. 1993. Distributed Constraint Logic Programming. Series in Computer Science, vol. 41. World Scientific, Singapore.]] Google Scholar
- LEUNG, H.-F. AND CLARK, K. L. 1996. Constraint satisfaction in distributed concurrent logic programming. J. Symbolic Computation 21, 699-714.]] Google Scholar
- LLOYD, J. 1987. Foundations of Logic Programming, Second Edition. Springer-Verlag.]] Google Scholar
- MARTELLI, A. AND MONTANARI, U. 1982. An efficient unification algorithm. ACM Trans. Program. Lang. Syst. 4, 2 (Apr.), 258-282.]] Google Scholar
- MEHL, M. 1999. The Oz virtual machine - records, transients, and deep guards. Ph.D. thesis, Technische FakultSot der UniversitS~t des Saarlandes.]]Google Scholar
- MEHL, M., SCHULTE, C., AND SMOLKA, G. 1998. Futures and by-need synchronization for Oz.]]Google Scholar
- MEHLHORN, K. AND TSAKALIDIS, A. 1990. Data structures. In Handbook of Theoretical Computer Science - Volume A: Algorithms and Complexity, J. van Leeuwen, Ed. Elsevier HIT Press, 301-341.]] Google Scholar
- HOZART CONSORTIUM. 1999.The Mozart programming system (Oz 3). Available at http ://www. mozart-oz, org.]]Google Scholar
- OTTE, R., PATRICK, P., AND ROY, H. 1996. Understanding CORBA: The Common Object Request Broker Architecture. Prentice-Hall PTR, Upper Saddle River, N.J.]] Google Scholar
- PLAINFOSSI~, D. AND SHAPIRO, M. 1995. A survey of distributed garbage collection techniques. In the International Workshop on Memory Management. Lecture Notes in Computer Science, vol. 986. Springer-Verlag, Berlin, 211-249.]] Google Scholar
- PODELSKI, A. AND SMOLKA, G. 1997. Situated simplification. Theoretical Computer Science 173, 209-233.]] Google Scholar
- ROBINSON, J. A. 1965. A machine-oriented logic based on the resolution principle. J. ACM 12, 23-41.]] Google Scholar
- ROKUSAWA, K., NAKASE, A., AND CHIKAYAMA, T. 1996. Distributed memory implementation of KLIC. New Generation Computing 14, 3, 261-280.]]Google Scholar
- SARASWAT, V. t. 1993. Concurrent Constraint Programming. HIT Press.]] Google Scholar
- SCHULTE, C. 1997. Programming constraint inference engines. In Proceedings of the 3rd International Conference on Principles and Practice of Constraint Programming, G. Smolka, Ed. Lecture Notes in Computer Science, vol. 1330. Springer-Verlag, Schlof3 Hagenberg, Austria, 519-533.]]Google Scholar
- SHAPIRO, E. 1989. The family of concurrent logic programming languages. ACM Comput. Surv. 21, 3 (Sept.), 413-510.]] Google Scholar
- SMOLKA, G. 1995. The Oz programming model. In Computer Science Today. Lecture Notes in Computer Science, vol. 1000. Springer-Verlag, Berlin, 324-343.]]Google Scholar
- SMOLKA, G. 1996. Problem solving with constraints and programming. ACM Computing Surveys 28, 4es (Dec.). Electronic Section.]] Google Scholar
- SMOLKA, G. 1998. Concurrent constraint programming based on functional programming. In Programming Languages and Systems, C. Hankin, Ed. Lecture Notes in Computer Science, vol. 1381. Springer-Verlag, Lisbon, Portugal, 1-11.]] Google Scholar
- SMOLKA, G., SCHULTE, C., AND VAN ROY, P. 1995. PERDIO--Persistent and distributed programming in Oz. BHBF project proposal. Available at http://www.ps.uni-sb.de.]]Google Scholar
- STROUSTRUP, B. 1997. The C-/--/- Programming Language, Third Edition. Addison-Wesley.]] Google Scholar
- SUN MICROSYSTEMS. 1997. The Remote Method Invocation Specification. Available at http ://www. j avasoft, com.]]Google Scholar
- SUNDSTROM, A. 1998. Comparative study between Oz 3 and Java. Tech. rep., Uppsala University and Swedish Institute of Computer Science. July.]]Google Scholar
- TAYLOR, t. 1991. High-performance Prolog implementation. Ph.D. thesis, Basset Department of Computer Science, University of Sydney.]]Google Scholar
- TEL, G. 1994. An Introduction to Distributed Algorithms. Cambridge University Press, Cambridge, United Kingdom.]] Google Scholar
- VAN RoY, P. 1994. 1983-1993: The wonder years of sequential Prolog implementation. J. Log. Prog. 19/20, 385-441.]]Google Scholar
- VAN ROY, P. 1999. On the separation of concerns in distributed programming: Application to distribution structure and fault tolerance in Mozart. In International Workshop on Parallel and Distributed Computing for Symbolic and Irregular Applications (PDSIA 99). Tohoku University, Sendal, Japan.]]Google Scholar
- VAN RoY, P., BRAND, P., HARIDI, S., AND COLLET, R. 1999. A lightweight reliable object migration protocol. Lecture Notes in Computer Science, vol. 1686. Springer Verlag.]] Google Scholar
- VAN ROY, P., HARIDI, S., AND BRAND, P. 1999. Distributed progr&mming in Moz&rt - A tutori&l introduction. Tech. rep. In Moz&rt document&tion, &v&il&ble &t http://www.mozart-oz.org.]]Google Scholar
- VAN ROY, P., HARIDI, S., BRAND, P., SMOLKA, G., MEHL, M., AND SCHEIDHAUER, R. 1997. Mobile objects in Distributed Oz. ACM Trans. Program. Lang. Syst. 19, 5 (Sept.), 804-851.]] Google Scholar
- VEEN, A. H. 1986. D&t&flow re&chine &rchitecture. ACM Comput. Surv. 18, 4 (Dec.), 365-396.]] Google Scholar
- WARREN, D. H. D. 1977. Applied logic-its use &nd implement&tion &s & progr&mming tool. Ph.D. thesis, University of Edinburgh. Reprinted &s Technic&l Note 290, SRI Intern&tion&l.]]Google Scholar
- WIKSTROM, C. 1994. Distributed progr&mming in Erl&ng. In the 1st International Symposium on Parallel Symbolic Computation (PASCO 94). World Scientific, Sing&pore, 412-421.]]Google Scholar
Index Terms
- Efficient logic variables for distributed computing
Recommendations
Distributed programming languages: design and implementation
Considerable discussion has appeared in recent literature about 'distributed programming'. One area of discussion concerns the design of programming languages which support distributed algorithms. This paper examines the important issues in programming ...
Logic programming in the context of multiparadigm programming: the Oz experience
Oz is a multiparadigm language that supports logic programming as one of its major paradigms. A multiparadigm language is designed to support different programming paradigms (logic, functional, constraint, object-oriented, sequential, concurrent, etc.) ...
Comments