Computer Science – Programming Languages
Scientific paper
2011-12-16
Computer Science
Programming Languages
Online Proceedings of the 11th International Colloquium on Implementation of Constraint LOgic Programming Systems (CICLOPS 201
Scientific paper
e use Prolog as a flexible meta-language to provide executable specifications of some fundamental mathematical objects and their transformations. In the process, isomorphisms are unraveled between natural numbers and combinatorial objects (rooted ordered trees representing hereditarily finite sequences and rooted ordered binary trees representing G\"odel's System {\bf T} types). This paper focuses on an application that can be seen as an unexpected "paradigm shift": we provide recursive definitions showing that the resulting representations are directly usable to perform symbolically arbitrary-length integer computations. Besides the theoretically interesting fact of "breaking the arithmetic/symbolic barrier", the 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 source code of the paper, organized as a literate Prolog program, is available at \url{http://logic.cse.unt.edu/tarau/research/2011/pPAR.pl}
No associations
LandOfFree
Computing with Hereditarily Finite Sequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Computing with Hereditarily Finite Sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing with Hereditarily Finite Sequences will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-136741