öz - AMiner

öz
KOMBİNATORE DAYALI GRAFİK AZALTMA SİSTEMLERİ
NECLA VARDAL
Bilgisayar Mühendisliği Anabilim Dalı
Yüksek Lisans Tezi
Ocak , 2001
Hantal fonksiyonel programlama için önemli bir uygulama stratejisi grafik
azaltma konusudur. Bu tezin kapsamı kombinatör fonksiyonu tabanlı grafik
azaltma algoritmalarını, test amacı ile geliştirilmiş olan minimum ifade dili ile
analiz etmektir. SKI kombinatör fonksiyonu tekniği ile Hughes'a ait olan süperkombinatör fonksiyonu tekniğini analiz ettik. Daha sonra şablon tabanlı
kombinatör fonksiyonu ile azaltma algoritması önerilmiştir.
Kombinatör içinde serbest değişkenleri barındırmayan fonksiyondur. Temel
düşünce program içerisindeki tüm değişkenlerin, ard arda gelen kombinatörlere
dönüştürülerek kaldırılabilmesidir ki, bu işlem az sayıdaki önceden tanımlanmış
kombinatör kümesi vasıtası ile, yada limitsiz sayıda olabilen önceden
belirlenmemiş dinamik olarak oluşan süper-kombinatörler ile yapılabilir.
Bu tezde mevcut olan SKI kombinatör üretme algoritması ile Hughes'un
süper-kombinatör üretme algoritması karşılaştırılmaktadır. Bu algoritmalar Icon
programlama dili kullanılarak uygulanmıştır. Daha sonra şablon tabanlı
algoritma önerilmiş ve bu algoritmanın gerçekleştirilmesindeki detaylar
sunulmuştur. Tezde mevcut algoritma uygulamaları ve şablon tabanlı
algoritmalar test
edilmiş ve 5 nolu bölümde bu testlerin karşılaştırılması
sunulmuştur.
Anahtar Kelimeler: Grafik azaltma, SKI, kombinatör, fonksiyonel
programlama, soyutlama.
ABSTRACT
GRAPH REDUCTION SYSTEM BASED ON COMBINATOR
By
NECLA VARDAL
Department of Computer Engineering Master Thesis
January, 2001
Graph reduction is one of the important evaluation strategy for lazy functional
programming. The context of this thesis is analyzing combinator based graph
reduction algorithms with a minimal expression language developed for test
purposes. We analyzed SKI combinator technique and Hughes' supercombinator technique. Then template based combinator reduction algorithm is
proposed.
A combinator is function that contains no free variables. The idea is based on
that all of the variables in the program can be removed by transforming it into
sequence of combinators which would be drawn from a small pre-defined (fixed)
set of combinators (SKI), or which would be drawn from an unlimited number of
non-pre-defined set of dynamic super-combinators.
In this thesis, existing SKI combinator generation and Hughes' supercombinator generation algorithms are compared. These algorithms have been
implemented with Icon programming language. Then template based algorithm
is proposed and implementation details of these algorithms are given. In this
thesis existing algorithms and template based algorithms have been tested and
compared.
Keywords: Graph reduction, SKI, combinator, functional
programming, abstraction.
LIST OF REFERENCES:
[1] R.j.M. Hughes, Super-combinators, 1982 ACM Symp. on LISP and Functional
Programming, pp 1-10,1982.
[2] Jones Neil, Mucknick Steven, A fixed Program Machine For Combinator Exspression
Evaluation, ACM Symp on LISP and Functional Programming, 1982.
[3] Andrea Asperti,"On the complexity of beta reduction", ACM Symposium on Principles of
Porgramming Languages.pp. 110-118,1996
[4] Alonzo Church, The Calculi of Lambda Conversion, Princeton University Press, 1941.
[5] Anthony J. Field and Peter G. Harrison, Functional Programming, Addison Wesley, 1988
[6] L. Augustsson and T. Johnson, The Chalmers lazy_ML compiler, Comput. J32,2, 1989.
[7] J. Barkley Rosser," Highlights of the History of the Lambda calculus", ACM on LISP and
Functional Programming, 1982.
[8] Burton Warren, Annotations to control Parallelism and Reduction Order in Distributed
Evaluation of Functional Programs, ACM transactions on Programming Languages and
systems, Vol 6, No 2,1984.
[9] C. Clark and S. L. Peyton Jones,Strictness analysis- a practical approach, 2nd
functional Programming Languages and Computer architecture , Berlin, 1985.
[10] K. Davis and P.L. Wadler, Backwards strictness analysis: Proved and improved,
Functional Programming, Berlin, 1989.
[11] Doris Appleby, Programming Languages: Paradigm and Practice,McGraw Hill, 1991.
[12] J. Fairbrain and S. C. Wray , TIM,ACM third conference on Functional Programming
Languages and computer Architecture, New York ,1987.
[13] Guy Argo, Improving the Three Instruction Machine, ACM 4th conference on Functional
Programming Languages and computer Architecture, New York ,1989.
[14] Haskell Curry and Robert Feys, Combinatory Logic, volume 1, North Holland, 1958.
[15] Akihiko Takano, Generalized Partial Computation for a Lazy Functional Language, In
Proceedings of the Symposium on Partial Evaluation and Semantics-Based Program
Manipulation,volume 26, pp 1-11, Sep 1991.
[16] John Backus, Can Programming be Liberated from the von Neumann Style? A Functional
Style and its Algebra of Programs, Communications of the ACM, pp 613-641,1978.
[17] T. Johnson, Efficient compilation of lazy evaluation, SIGPLAN,1984
[18] Andrea Asperti, Harry G. Mairson/'Parallel Beta Recursion is not Elementary
Recursive", POPL ,ACM, pp. 303-315,1998.
[19] Julia Lawall,Harry Mairson, "On Global Dynamics of Optimal Graph Reduction", ACM
International Conference on Functional Programming ,pp.188-195,1997.
[20] Julia Lawall, Harry Mairson,"Optimality and Inefficiency: What isn't a cost model of the
lambda calculus? ", ACM International Conference on Functional Programming ,pp. 92101 ,1997.
[21] Pingali Keshav and Arvind, Efficient demand-Driven Evaluation. Parti, ACM
Transactions on Programming Languages and Systems, Vol7, No2,1985.
[22] Ralph E. Griswolt, Madge T. Griswolt, The Icon Programming Language, 1983.
[23] Revesz Gyorgy, Parallel Graph reduction with a sared Memory Multiprocessor Systems,
Int. Conf. On computer Languages, 1990.
[24] R. Milner, A Theory of Type Polymorphism in Programming, J. Computer and System
Science, V.3. pp. 348-375, 1978.
[25] Simon Peyton Jones, C. Clack, J. Salkild, and M. Hardie,GRIP-A High Performance
Architecturefor
Parallel
Graph
Reduction,
Third
Conference
on
Functional
Programming Languages and Computer Architecture, LNCS 274, pp98-112, 1987.
[26]
Sreedhar Vugranam.Guang R. Gao, Yong-fong Lee,"A new Framework for
Exhaustive and Incremental Dtat Flow Analysis Using DJ Graphs",ACM,1996
[27] Stark Richard, A glimpse intıo the Paradise of combinatory Algebra,International
Journal of Comp. And Inf. Sc, vol 13, No3, 1984.
[28] D. A.Turner," A New Implementaion Technique for Applicative Languages, Software
Practices and Experience", 1979.
[29] Stefano Guerrini,"Sharing-graphs ,sharing-morphism and lambda reduction", ACM
Symposium on Principles of programming Languages, 1995.
[30] Paul Hudak, Conception, Evolution, and Application of Functional Programming
Languages, ACM Computing Surveys, pp359-411, Sept 1989
[31]
J. McCarthy, P. Abrahams, D. Edwards, T. Hart, and M. Levin, LISP 1.5
Programmers Manual, MIT Press, 1962.
[32] Susan Eisenbach, Functional Programming, Languages Tools, and Architectures, Ellis
Horwood, 1987.
[33] Harold Abelson, Gerald Sussman, and Julie Sussman, Structure and Interpretation of
Computer Programs, McGraw Hill, 1985.