Accepted Papers in alphabetical order

Automated Method Induction − Functional Goes Object Oriented
Authors

Thomas Hieber, Martin Hofmann

Affiliation

University Bamberg - Cognitive Systems Group

Abstract

The development of software engineering has had a great deal of benefits for the development of software. Along with it came a whole new paradigm of the way software is designed and implemented − object orientation. Today it is a standard to have UML diagrams be translated into program code wherever possible. However, as few tools really go beyond this we demonstrate a simple functional representation for objects, methods and variables. In addtition we show how our program induction system Igor can not only un derstand those basic notions like referencing methods within objects or using a simple protocol like something we called message-passing, but how it can even learn them by a given specification - which is the major feature of this paper.

Type
technical paper
Link
pdf
Defining inductive operators using distances over lists
Author

V. Estruch, C. Ferri, J. Hernandez-Orallo, M.J. Ramirez-Quintana

Affiliation

DSIC, Univ. Politecnica de Valencia

Abstract

Instance-based learning is one of the most widely-used paradigms in the field of automatic induction. Several reasons back its popularity, among them, we must stand out its capability to cope with different data representations: these methods are designed on the basis of a similarity principle (similar examples should share similar properties) which makes them easily adaptable to different datatypes via redefining the similarity (distance) function. In this sense, multiple distances and similarity functions can be found in the literature. However, the most notorious downside when speaking of distance-based or similarity-based methods concerns the low expressivity of the models (if any) these methods learn. Decisions are made from expressions such as "example x is more similar or nearer to example y then" which results in little practical knowledge, very specially when structured data is involved. However, in many application areas we require patterns to describe the similarities of the data. In [Estruch 2008], we have addressed and formalised the problem of turning distance-based methods outputs into comprehensible and consistent patterns. In this work, we first overview our framework and then instantiated it for the case of data represented by lists of symbols.

Type
technical paper
Link
pdf
Enumerating Well-Typed Terms Generically
Authors

Alexey Rodriguez Yakushev(1), Johan Jeuring(2,3)

Affiliation

(1) Vector Fabrics B.V., Paradijslaan 28, 5611 KN Eindhoven, The Netherlands
(2) Department of Information and Computing Sciences, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands
(3) School of Computer Science, Open University of the Netherlands, P.O. Box 2960, 6401 DL Heerlen, The Netherlands

Abstract

We use generic programming techniques to generate well-typed lambda terms. We encode well-typed terms by generalized algebraic datatypes (GADTs) and existential types. The Spine approach (Hinze et al. 2006; Hinze and Löh 2006) to generic programming supports GADTs, but it does not support the definition of generic producers for existentials. We describe how to extend the Spine approach to support existentials and we use the improved Spine to define a generic enumeration function. We show that the enumeration function can be used to generate the terms of simply typed lambda calculus.

Type
technical paper
Link
pdf
Exhaustive program generation by interpretation of Herbelin's LJT variant
Author

Susumu Katayama

Affiliation

University of Miyazaki

Abstract

This research report formalizes the algorithm behind MagicHaskeller an inductive functional programming system based on systematic search, as a monadic interpretation of inference rules of a variant of Herbelin's LJT.

Type
work in progress report
Link
pdf
Incremental learning in inductive programming
Author

Robert Henderson

Affiliation

University of Edinburgh, UK

Abstract

Inductive programming systems characteristically exhibit an exponential explosion in search time as one increases the size of the programs to be generated. As a way of overcoming this, we introduce incremental learning, a process in which an inductive programming system automatically modifies its inductive bias towards some domain through solving a sequence of gradually more difficult problems in that domain.
We demonstrate a simple form of incremental learning in which a system incorporates solution programs into its background knowledge as it progresses through a sequence of problems. Using a search-based inductive functional programming system modelled on the MagicHaskeller system of Katayama (2007), we perform a set of experiments comparing the performance of inductive programming with and without incremental learning. Incremental learning is shown to produce a performance improvement of at least a factor of thirty on each of the four problem sequences tested. We discuss how, given some assumptions, inductive programming with incremental learning can be shown to have a polynomial, rather than exponential, time complexity with respect to the size of the program to be generated.

Type
technical paper
Link
pdf
Titel: Inductive Programming − A Survey
Author

Emanuel Kitzelmann

Affiliation

Cognitive Systems Group, University of Bamberg

Abstract

Inductive programming − the automatic construction of recursive declarative programs from incomplete specifications such as input/output-examples − is not a unified field until today but scattered over several different research fields such as machine learning, inductive logic programming, genetic programming, and functional programming. This impedes an exchange of theory and techniques and, as a consequence, a progress of inductive programming. In this paper we survey theoretical results and methods regarding IP that have been developed in different research fields until today.

Type
technical paper
Link
pdf
Porting IgorII from MAUDE to HASKELL − Introducing a System's Design
Authors

Martin Hofmann, Emanuel Kitzelmann, Ute Schmid

Affiliation

Cognitive Systems Group, University of Bamberg

Abstract

This paper describes our efforts and solutions in porting our IP system IGOR2 from the termrewriting language MAUDE to HASKELL. We describe how, for our purpose necessary, features of the homoiconic language MAUDE can be simulated in HASKELL using a stateful monad transformer. With our new implementation we are now able to use higher-order context during our synthesis and extract information from type classes useable as background knowledge. Keeping our new implmentation as close as possible to our old, we could keep all features of our system.

Type
technical paper
Link
pdf
Quick filtration of semantically equivalent expressions in program search results
Author

Susumu Katayama

Affiliation

University of Miyazaki

Abstract

This research is on improving the efficiency of our previous work for removing semantically equivalent expressions in program search results.

Type
work in progress report
Link
pdf