Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-25T00:42:50.651Z Has data issue: false hasContentIssue false
  • English
  • Français

Improving intervals1

Part of: JFP Research Articles

Published online by Cambridge University Press:  07 November 2008

W. Ken Jackson  and
F. Warren Burton
W. Ken Jackson
Affiliation:
School of Computing Science, Simon Fraser University, Burnaby, British Columbia, CanadaV5A 1S6 (e-mail: [email protected])
F. Warren Burton
Affiliation:
School of Computing Science, Simon Fraser University, Burnaby, British Columbia, CanadaV5A 1S6 (e-mail: [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We show how improving values (Burton, 1991) can be extended to handle both upper and lower bounds. The result is a new data type, called improving intervals. We give a simple implementation of improving intervals that uses a list of successively tighter bounds to represent a value. A program using improving intervals can be evaluated as a parallel program using speculative evaluation. The utility of improving intervals is demonstrated through two programs: parallel alpha-beta and parallel branch-and-bound

Type
Articles
Information
Journal of Functional Programming , Volume 3 , Issue 2 , April 1993 , pp. 153 - 169
Copyright
Copyright © Cambridge University Press 1993

References

Akl, S., Barnard, D. and Doran, R. 1982. Design, analysis and implementation of a parallel tree search algorithm. IEEE Trans. Pattern Analysis & Machine Intelligence, 4(2): 192–203.CrossRefGoogle ScholarPubMed
Bird, R. and Wadler, P. 1988. Introduction to Functional Programming. Prentice Hall.Google Scholar
Bird, R. S. and Hughes, J. 1987. The alpha-beta algorithm: An exercise in program transformation. Inf. Process. Lett., 24: 53–57.CrossRefGoogle Scholar
Burton, F. W. 1985. Speculative computation, parallelism, and functional programming. IEEE Trans. Comput., 34(12): 1190–1193.CrossRefGoogle Scholar
Burton, F. W. 1991. Encapsulating nondeterminacy in an abstract data type with deterministic semantics. J. Functional Programming. 1(1): 3–20.CrossRefGoogle Scholar
Burton, F. W. and Jackson, W. K. 1990. Partially deterministic functions. IV Higher Order Workshop, Springer-Verlag Workshops in Computing, pp 1–10, Banff, Canada10–1409, Graham, Birtwistle (Ed.).Google Scholar
Hughes, J. 1989. Why functional programming matters. Comput. J., 32(2): 98–107.CrossRefGoogle Scholar
Lai, T.-H. and Sahni, S. 1984. Anomalies in parallel branch-and-bound algorithms. Commun. ACM, 27(6): 594–602.CrossRefGoogle Scholar
Li, G.-J. and Wah, B. W. 1990. Computational efficiency of parallel combinatorial or-tree searches. IEEE Trans. Softw. Eng., 16(1): 13–31.Google Scholar
Powley, C., Ferguson, C. and Korf, R. E. 1989. Parallel heuristic search: Two approaches. In Kumar, V., Gopalakrishnan, P. and Kanal, L. N., editors, Parallel Algorithms for Machine Intelligence and Vision, pp. 42–65. Springer-Verlag.Google Scholar
Turner, D. A. 1986. An overview of Miranda. SIGPLAN Notices, 21(12): 158–166.CrossRefGoogle Scholar
Submit a response

Discussions

No Discussions have been published for this article.