Head-Order Techniques and Other Pragmatics of Lambda Calculus Graph Reduction
eBook Features
-
Read Anywhere
Read your book anywhere, on any device, through RedShelf's cloud based eReader.
-
Digital Notes and Study Tools
Built-in study tools include highlights, study guides, annotations, definitions, flashcards, and collaboration.
-
Offline Access
(
20% )
The publisher of this book allows a portion of the content to be used offline.
-
Printing
(
10%
)
The publisher of this book allows a portion of the content to be printed.
This title has been removed from sale.
Additional Book Details
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.
Sold By | Dissertation.com |
---|---|
ISBNs | 9781612339603, 1612337570, 9781612339603 |
Language | English |
Number of Pages | 248 |