Paper Info
Title
A declarative specification of tree-based symbolic arithmetic computations
Abstract
We use Prolog as a flexible meta-language to provide executable specifications of some interesting mathematical objects and their operations. In the process, isomorphisms are unraveled between natural numbers and rooted ordered trees representing hereditarily finite sequences and rooted ordered binary trees representing Gödel's System T types. Our isomorphisms result in an interesting "paradigm shift": we provide recursive definitions that perform the equivalent of arbitrary-length integer computations directly on rooted ordered trees. Besides the theoretically interesting fact of "breaking the arithmetic/symbolic barrier", our arithmetic operations performed with symbolic objects like trees or types turn out to be genuinely efficient --- we derive implementations with asymptotic performance comparable to ordinary bitstring implementations of arbitrary-length integer arithmetic. The Prolog code of the paper, organized as a literate program, is available at http://logic.cse.unt.edu/tarau/research/2012/padl12.pl
Year
DOI
Venue
2012
10.1007/978-3-642-27694-1_20
PADL
Keywords
Field
DocType
theoretically interesting fact,tree-based symbolic arithmetic computation,declarative specification,symbolic barrier,asymptotic performance,arbitrary-length integer arithmetic,isomorphisms result,interesting mathematical object,arbitrary-length integer,prolog code,arithmetic operation,symbolic object
Integer,Natural number,Programming language,Gödel,Computer science,Arithmetic,Theoretical computer science,Prolog,Isomorphism,Recursion,Binary search tree,Executable
Conference
Citations 
PageRank 
References 
0
0.34
18
Authors
1
Name
Order
Citations
PageRank
Paul Tarau11529113.14