Pruning with improving sequences in lazy functional programs
Tóm tắt
This paper presents a library based on improving sequences and demonstrates that they are effective for pruning unnecessary computations while retaining program clarity. An improving sequence is a monotonic sequence of approximation values of a final value that are improved gradually according to some ordering relation. A computation using improving sequences proceeds by demanding for the next approximation value. If an approximation value in the middle of the improving sequence has sufficient information to yield the result of some part of the program, the computations that produce the remaining values can be pruned. By combining suitable improving sequences and primitive functions defined for the sequences, we can write efficient programs in the same form as simple and naive programs. We give examples that show the effectiveness of improving sequences and show by program calculation that a simple minimax-like program using improving sequences implements a well-known branch-and-bound searching algorithm.
Tài liệu tham khảo
Acar, U.A., Blelloch, G.E., Harper, R.: Adaptive functional programming. ACM Trans. Program. Lang. Syst. 28(6), 990–1034 (2006)
Acar, U.A., Blelloch, G.E., Harper, R.: Selective memoization. In: Proceedings of 30th. ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 2003), pp. 14–25 (2003)
Bird, R.: Introduction to Functional Programming Using Haskell, 2nd edn. Prentice Hall, Englewood Cliffs (1998)
Bird, R., Hughes, J.: The alpha-beta algorithm: an exercise in program transformation. Inf. Process. Lett. 24(1), 53–57 (1987)
Burton, F.W.: Encapsulating non-determinacy in an abstract data type with determinate semantics. J. Funct. Program. 1(1), 3–20 (1991)
Carlsson, M.: Monads for incremental computing. In: Proceedings of 7th International Conference on Functional Programming (ICFP 2002), pp. 26–35. ACM Press, New York (2002)
Ennals, R., Peyton Jones, S.L.: Optimistic evaluation: an adaptive evaluation strategy for non-strict programs. In: Proceedings of 8th International Conference on Functional Programming (ICFP 2003), pp. 287–298. ACM Press, New York (2003)
Horowitz, E., Sahni, S.: Fundamentals of Computer Algorithms. Computer Science Press, New York (1978)
Hu, Z., Iwasaki, H., Takeichi, M.: Deriving structural hylomorphisms from recursive definitions. In: Proceedings of 1996 International Conference on Functional Programming (ICFP 1996), pp. 73–82. ACM Press, New York (1996)
Hu, Z., Iwasaki, H., Takeichi, M.: Calculating accumulations. New Gener. Comput. 17(2), 153–173 (1999)
Knuth, D.E., Moore, R.W.: An analysis of alpha-beta pruning. Artif. Intell. 6(4), 293–326 (1975)
Lawler, E.L., Wood, D.E.: Branch-and-bound methods: a survey. Oper. Res. 14(4), 699–719 (1966)
Leijen, D., Meijer, D.: Domain specific embedded compilers. In: Proceedings of 2nd Conference on Domain-Specific Languages (DSL 1999), pp. 109–122. ACM Press, New York (1999)
Liu, Y.A., Stoller, S.D., Teitelbaum, T.: Static caching for incremental computation. ACM Trans. Program. Lang. Syst. 20(3), 546–585 (1998)
Meijer, E., Fokkinga, M.M., Paterson, R.: Functional programming with bananas, lenses, envelopes and barbed wire. In: Proceedings of 1991 International Conference on Functional Programming and Computer Architecture (FPCA 1991). Lecture Notes in Computer Science, vol. 523, pp. 124–144. Springer, Berlin (1991)
Morimoto, T., Takano, Y., Iwasaki, H.: Instantly turning a naive exhaustive search into three efficient searches with pruning. In: Proceedings of 9th International Symposium on Practical Aspects of Declarative Languages (PADL 2007). Lecture Notes in Computer Science, vol. 4354, pp. 65–79. Springer, Berlin (2007)
Ramalingam, G., Reps, T.W.: A categorized bibliography on incremental computation. In: Proceedings of 20th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 1993), pp. 502–510. ACM Press, New York (1993)
Takano, A., Meijer, E.: Shortcut deforestation in calculational form. In: Proceedings of 1995 International Conference on Functional Programming and Computer Architecture (FPCA 1995), pp. 306–313. ACM Press, New York (1995)
Tanaka, K.: Studies on parallel functional programming. M.Phil. thesis, Graduate School of Engineering, The University of Tokyo (1993)