Abstract
The G-line is a horizontally coded graph reducer. In lazy functional languages much time is used to manage the graph. A method has been developed to perform construction of a subgraph in a single parallel access to the graph memory. With a simulation, using infinite hardware, we have shown that the architecture performs well. We argue that a realistic implementation is possible.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
T.Johnsson; Efficient compilation of lazy evaluation; Sigplan Notices 19(6): 58, 69, June 1984.
Simon L.Peyton Jones; Implementation of graph reduction; Prentice Hall; London, 1987.
D.A. Turner, “A new implementation technique for applicative languages”; Software Practice and Experience 9(1) pp 31–49 (A jan. 1979 ).
J.Fairbairn, S.Wray; TIM: A simple lazy abstract machine to execute supercombinators; Third conference on functional programming and computer architecture; Portland, Oregon, USA; Proceedings 34–35, September 1987.
Guy Argo; Improving the three instruction machine; Proceedings of the FPLCA, pp 100–115, London 1989.
Simon L.Peyton Jones, Jon Salkild; The spineless tagless G-machine; Proceedings of the FPLCA, pp 184–201, London 1989.
L.Augustsson, T.Johnsson; Parallel graph reduction with the =nu,G=-machine; Proceedings of the FPLCA,pp 202–213, London 1989.
W.R.Stoye, T.J.W.Clarke, A.C.Norman; Some practical methods for rapid combinator reduction; Proc. of 1984 ACM Conf on Lisp and Functional Prog, pp 159–166, aug 1984.
M.Scheevel, NORMA, a normal-order combinator reduction machine, colloquium presented at Oregon Graduate Center, july 1984.
R.B.Kieburtz; The G-machine, a fast graph-reduction evaluator; Second Conference on functional Languages and Computer Architecture, LNCS 201, Nancy, 1985; Springer Verlag.
R.B.Kieburtz; A Rise architecture for symbolic computation; Sigplan Notices 22 (10): 146–155, October 1987.
Willem Vree, Design considerations for a parallel reduction machine; Ph. D. thesis, pp 27–50, Amsterdam, 1989
R.B.Kieburtz and B. Agapiev; Optimizing the evaluation of suspensions, pp 267–282 in Proceedings of the Workshop of functional languages, ed. T.Johnsson, S.L.Peyton Jones, K.Karlsson, Dept of Computer Science, Chalmers Univ. of Technology, Göteborg, Aspensas, 1988.
P.H.Hartel; Performance of lazy combinator graph reduction; To be published in “Software practice and experience”.
W.G Vree, P.H.Hartel; Parallel graph reduction for divide-and conquer applications; Part II -program performance; Internal Report D-20, PRMProject, December 1988.
T.Johnsson; Compiling Lazy Functional Languages, Ph.D. thesis, Göteborg, 1987.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Milikowski, R., Vree, W.G. (1991). The G-Line a Distributed Processor for Graph Reduction. In: Aarts, E.H.L., van Leeuwen, J., Rem, M. (eds) Parle ’91 Parallel Architectures and Languages Europe. Lecture Notes in Computer Science, vol 505. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-25209-3_9
Download citation
DOI: https://doi.org/10.1007/978-3-662-25209-3_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-23206-4
Online ISBN: 978-3-662-25209-3
eBook Packages: Springer Book Archive