Chapter 3: Systematic Synthesis of Functions

Koopman, Pieter; Plasmeijer, Rinus
September 2007
Trends in Functional Programming Volume 7;2007, Vol. 7, p35
Book Chapter
In this paper we introduce a new technique to synthesize functions matching a given set of input-output pairs. Using techniques similar to defunctionalisation the abstract syntax tree of the candidate functions is specified at a high level of abstraction. We use a recursive data type to represent the syntax tree of the candidate functions. The test system G∀ST is used for the systematic synthesis of candidate functions and the selection of functions matching the given condition. The representation of candidate functions as data structures gives us full control over them and the transformation of the syntax tree to the actual function is straight forward. Instances of the syntax tree are generated by a generic algorithm that can be tailored easily to specific needs. This yields a very flexible system to synthesize clear (recursive) function definitions efficiently.


Related Articles

  • Chapter 4: A Purely Functional Implementation of ROBDDs in Haskell. Christiansen, Jan; Huch, Frank // Trends in Functional Programming Volume 7;2007, Vol. 7, p55 

    This paper presents an implementation of the ROBDD data structure in Haskell. It shows that lazy evaluation can be used to improve the performance of some ROBDD algorithms. While standard implementations construct the whole structure no matter which parts are demanded we use lazy evaluation to...

  • Analysis of pattern overlaps and exact computation of P-values of pattern occurrences numbers: case of Hidden Markov Models. Régnier, Mireille; Furletova, Evgenia; Yakovlev, Victor; Roytberg, Mikhail // Algorithms for Molecular Biology;2014, Vol. 9 Issue 1, p1 

    Background: Finding new functional fragments in biological sequences is a challenging problem. Methods addressing this problem commonly search for clusters of pattern occurrences that are statistically significant. A measure of statistical significance is the P-value of a number of pattern...

  • The Analysis on Recursive Algorithm Implementation of Preorder-traversing Binary Tree. Yucheng Song; Shaoli Jin // Applied Mechanics & Materials;2014, Issue 631-632, p99 

    Traversing binary tree is an important algorithm in data structure. This paper analyses and discusses the recursive algorithm implementation of preorder-traversing binary tree through instance. It would contribute beginners to understand more deeply the process of preorder-traversing and enhance...

  • Traceable Recursion with Graphical Illustration for Novice Programmers. Sa, Leonardo; Wen-Jung Hsin // InSight: A Journal of Scholarly Teaching;2010, Vol. 5, p54 

    Recursion is a concept that can be used to describe the phenomena and natural occurrences in many different fields. As many applications utilize computer software to model recursion, recursion is a particularly important concept in the computing discipline. However, it is a difficult concept for...

  • Chapter 5: Static Single Information from a Functional Perspective. Singer, Jeremy // Trends in Functional Programming Volume 4;2005, Vol. 4, p63 

    Static single information form is a natural extension of the well-known static single assignment form. It is a program intermediate representation used in optimising compilers for imperative programming languages. In this paper we show how a program expressed in static single information form...

  • Clojure. Briddock, David // Micro Mart;Jun2013, Issue 1265, p74 

    The article features Clojure, a dialect of computer language Lisp designed by Rich Hickey. When complete, Clojure would reportedly become a member of .NET programming language family and have access to the .NET Framwork libraries. Clojure reportedly models data structures as immutable objects...

  • Local fill reduction techniques for sparse symmetric linear systems. Gunther Rei�?ig // Electrical Engineering;Sep2007, Vol. 89 Issue 8, p639 

    Abstract  Local algorithms for obtaining pivot orderings for sparse symmetric coefficient matrices are reviewed together with their mathematical background, appropriate data structures and details of efficient implementation. Heuristics that go beyond the classical Minimum Degree and...

  • Efficient Window Block Retrieval in Quadtree-Based Spatial Databases. Aref, Walid G.; Samet, Hanan // GeoInformatica;Apr1997, Vol. 1 Issue 1, p59 

    An algorithm is presented to answer window queries in a quadtree-based spatial database environment by retrieving all of the quadtree blocks in the underlying spatial database that cover the quadtree blocks that comprise the window. It works by decomposing the window operation into...

  • RECURSIVE OBJECTS--AN OBJECT ORIENTED PRESENTATION OF RECURSION. Sher, David B. // Mathematics & Computer Education;Winter2004, Vol. 38 Issue 1, p97 

    Presents an alternative approach to recursion in computer science. Features of the traditional approach to recursion; Tips on teaching recursion with recursive objects; Definition of a search tree for data structures.


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics