Paperback Edition
Paperback
248 pages
$25.95
Choose vendor to order paperback edition
BrownWalker Press
Amazon.com
Barnes & Noble
Return policy
PDF eBook
Entire PDF eBook
3742k
$24
Get instant access to an entire eBook
Buy PDF Password
Download Complete PDF
eBook editions
Head-Order Techniques and Other Pragmatics of Lambda Calculus Graph Reduction
by Nikos B. Troullinos
Paperback
eBook PDF
Publisher: | Dissertation |
Pub date: | 2011 |
Pages: | 248 |
ISBN-10: | 1612337570 |
ISBN-13: | 9781612337579 |
Categories: | Computer Science Computers Mathematics |
Abstract
The operational aspects of Lambda Calculus are studied as a fundamental basis for high-order functional computation. We consider systems having full reduction semantics, i.e., equivalence-preserving transformations of functions. The historic lineage from Eval-Apply to SECD to RTNF/RTLF culminates in the techniques of normal-order graph Head Order Reduction (HOR). By using a scalar mechanism to artificially bind relatively free variables, HOR makes it relatively effortless to reduce expressions beyond weak normal form and to allow expression-level results while exhibiting a well-behaved linear self-modifying code structure. Several variations of HOR are presented and compared to other efficient reducers, with and without sharing, including a conservative breadth-first one which mechanically takes advantage of the inherent, fine-grained parallelism of the head normal form. We include abstract machine and concrete implementations of all the reducers in pure functional code. Benchmarking comparisons are made through a combined time-space efficiency metric. The original results indicate that circa 2010 reduction rates of 10-100 million reductions per second can be achieved in software interpreters and a billion reductions per second can be achieved by a state-of-the art custom VLSI implementation.
Paperback Edition
Paperback
248 pages
$25.95
Choose vendor to order paperback edition
BrownWalker Press
Amazon.com
Barnes & Noble
Return policy
PDF eBook
Entire PDF eBook
3742k
$24
Get instant access to an entire eBook
Buy PDF Password
Download Complete PDF
eBook editions
Share this book
Relevant events
APR
3
03 - 05 Apr 2024
Aberystwyth, United Kingdom
10 - 12 Apr 2024
Taiwan, China
12 - 14 Apr 2024
Verbania, Italy
13 - 14 Apr 2024
SYDNEY, Aruba
14 - 19 Apr 2024
Seoul, Korea (South)
19 - 21 Apr 2024
Shanghai, China
19 - 21 Apr 2024
Singapore, Singapore
19 - 21 Apr 2024
Bangkok, Thailand
19 - 22 Apr 2024
Xi'an, China
APR
19
19 - 21 Apr 2024
Xi'an, China