A practical lambda-calculator 2.2
Details
| Size: | 22K |
| Last Update: | 2008-04-15 23:41:38 |
| OS Support: | Linux |
| License/Program Type: | Public Domain |
| Publisher: | Oleg |
| Price: | $0.00 |
Description:
A practical lambda-calculator 2.2 is mathematics software developed by Oleg.
A practical lambda-calculator is a normal-order evaluator for the untyped lambda-calculus, extended with convenient commands and shortcuts to make programming in it more productive.
Shortcuts are distinguished constants that represent terms. Commands define new shortcuts, activate tracing of all reductions, compare terms modulo alpha-conversion, print all defined shortcuts and evaluation flags, etc.
Terms to evaluate and commands are entered at a read-eval-print-loop (REPL) "prompt" or "included" from a file by a special command. A Haskell branch is an embedding of the lambda calculator (as a domain-specific language) into Haskell. The calculator can be used interactively within Hugs or GHCi.
The present calculator implements what seems to be an efficient and elegant algorithm of normal order reductions. The algorithm is "more functional" than the traditionally used approach.
The algorithm seems identical to that employed by yacc sans one critical difference. The calculator also takes a more "functional" approach to the hygiene of beta-substitutions, which is achieved by coloring of identifiers where absolutely necessary. This approach is "more functional" because it avoids a global counter or the threading of the paint bucket through the whole the process. The integration of the calculator with Haskell lets us store terms in variables and easily and intuitively combine them.
The traditional recipe for normal-order reductions includes an unpleasant phrase "cook until done". The phrase makes it necessary to keep track of reduction attempts, and implies an ugly iterative algorithm. We're proposing what seems to be an efficient and elegant technique that can be implemented through intuitive re-writing rules.
Our calculator, like yacc, possesses a stack and works by doing a sequence of shift and reduce steps. The only significant difference from yacc is that the lambda-calculator "reparses" the result after the successful reduce step. The source and the target languages of our "parser" (lambda-calculator) are the same; therefore, the parser can indeed apply itself.
The parsing stack can be made implicit. In that case, the algorithm can be used for normalization of typed lambda-terms in Twelf.
The following examples show that lambda-calculus becomes a domain-specific language embedded into Haskell:
> c0 = f ^ x ^ x -- Church numeral 0
> succ = c ^ f ^ x ^ f (c f x) -- Successor
> c1 = eval $ succ c0 -- pre-evaluate other numerals
> c2 = eval $ succ c1
> c3 = eval $ succ c2
> c4 = eval $ succ c3
It is indeed convenient to store terms in Haskell variables and pre-evaluate (i.e., normalize) them. They are indeed terms. We can always ask the interpreter to show the term. For example, show c4 yields (f. (x. f (f (f (f x))))).
let mul = a ^ b ^ f ^ a (b f) -- multiplication
eval $ mul c1 ---> (b. b), the identity function
eval $ mul c0 ---> (b. (f. (x. x))), which is "const 0"
These are algebraic results: multiplying any number by zero always gives zero. We can see now how lambda-calculus can be useful for theorem proving, even over universally-quantified formulas.
The calculator implements Dr. Fairbairn's suggestion to limit the depth of printed terms. This makes it possible to evaluate and print some divergent terms (so-called tail-divergent terms):
Lambda_calc> let y_comb = f^((p^pp) (c ^ f(cc))) in eval $ y_combc
c (c (c (c (c (c (c (c (c (c (...))))))))))
It is amazing how well lambda-calculus and Haskell play together.
A practical lambda-calculator 2.2 supports different languages (including english). It works with Linux.
Downloading A practical lambda-calculator 2.2 will take several seconds if you use fast ADSL connection.
0 comments
Add to
A practical lambda-calculator 2.2 Version History
Related Software
|
|
From category: Mathematics |
| Elca (Extended Line Calculator) evaluates mathematical expressions (more precisely Perl expressions).... |
|
|
From category: Mathematics |
| Coyotl 3.1.0 is mathematics software developed by Scott Robert Ladd. The Coyotl library defies easy classification much like it\'s namesake. Coyotl collects several C++ tools that have proven usefu... |
|
|
From category: Astronomy |
| BOTEC 0.3.4 is astronomy software developed by Erik Max Francis. BOTEC project is a simple astrophysical and orbital mechanics calculator, including a database of all named Solar System objects. \... |
|
|
From category: Mathematics |
| Freeplot 0.0.1 Alpha is mathematics software developed by Davidlohr Bueso Arnet. FreePlot is a simple mathematical program that plots 2-D functions written in Python. Freeplot provides an easy to u... |
|
|
From category: Artificial-Intelligence |
| Discrete Event Calculus Reasoner 1.0 is artificial intelligence software developed by Erik T. Mueller. Discrete Event Calculus Reasoner is an open source program for performing automated commonsens... |
|
|
From category: Mathematics |
| RPL/2 is a programming language for computations.... |
|
|
From category: Bioinformatics |
| Array Designer 4.11 is bioinformatics software developed by PREMIER Biosoft International. Array Designer project can help design thousands of efficient, highly specific oligos to make microarrays... |
|
|
From category: Medical-Science-Apps |
| Mirth is a cross-platform HL7 interface engine that enables bi-directional sending of HL7 messages.... |
|
|
From category: Visualization |
| Cvtool is a general-purpose computer vision tool.... |
|
|
From category: Electronic-Design-Automation |
| ASCO 0.4.5 is electronic design automation ( software developed by ASCO Team. ASCO aka A SPICE Circuit Optimizer project aims to bring circuit optimization capabilities to existing SPICE simulators... |
|
|
From category: Visualization |
| FractalEye 1.0.1 is visualization software developed by Frank Mertens. FractalEye is a height map generation by fractal formulas and perlin noise. Heights are delivered by a fractal formula or DEM... |
|
|
From category: Medical-Science-Apps |
| BMI Calculator 1.1 is medical science apps. software developed by Boulat Khakimov. BMI Calculator is a simple, easy-to-use BMI calculator. It accepts input in both the English and Metric measuring... |
|
|
From category: Astronomy |
| Cora 3.2 is astronomy software developed by Jan-Uwe Ness and Rainer Wichmann. Cora is a line fitting tool designed for emission line spectra with low count numbers. Cora is an optional Gtk... |
|
|
From category: Mathematics |
| Universal tool for statistical analysis and modeling of experimental and market data. Support import data from variety of data sources. Statistical schemes cover all major data modeling operations. Cr... |
Leave a comment