Tabulation with Zippers

• Author(s): Viera, Marcos ; Pardo, Alberto ; Saraiva, João
• Date: 2024
• Persistent ID: https://hdl.handle.net/1822/95652
• Origin: RepositóriUM - Universidade do Minho
• Subject(s): Zipper; Tabulation; Generics; Attribute Grammars
• Document Type: Conference paper
• Language: English
• Contributor(s): Universidade do Minho

Description

Tabulation is a well-known technique for improving the efficiency of recursive functions with redundant function calls. A key point in the application of this technique is to identify a suitable representation for the table. In this paper, we propose the use of zippers as tables in the tabulation process. Our approach relies on a generic function zipWithZipper, that makes strong use of lazy evaluation to traverse two zippers in a circular manner. The technique turns out to be particularly efficient when the arguments to recursive calls are closely situated within the function domain. For example, in the case of natural numbers this means function calls on fairly contiguous values. Likewise, when dealing with tree structures, it means functions calls on immediate sub-trees and parent nodes. This results in a concise and efficient zipper-based embedding of attribute grammars.