3 search hits
-
Schema-Guided Inductive Functional Programming through Automatic Detection of Type Morphisms
(2010)
-
Martin Hofmann
- Inductive functional programming systems can be characterised by two diametric approaches: Either they apply exhaustive program enumeration which uses input/output examples (IO) as test cases, or they perform an analytical, data-driven structural generalisation of the IO examples. Enumerative approaches ignore the structural information provided with the IO examples, but use type information to guide and restrict the search. They use higher-order functions which capture recursion schemes during their enumeration, but apply them randomly in a uninformed manner. Analytical approaches on the other side heavily exploit this structural information, but have ignored the benefits of a strong type system so far and use only recursion schemes either fixed and built in, or selected by an expert user. In category theory universal constructs, such as natural transformations or type morphisms, describe recursion schemes which can be defined on any inductively defined data type. They can be characterised by specific universal properties. Those type morphisms and related concepts provide a categorical approach to functional programming, which is often called categorical programming. This work shows how categorical programming can be applied to Inductive Programming and how universal constructs, such as catamorphisms, paramorphisms, and type functors, can be used as recursive program schemes for inductive functional programming. The use of program schemes for Inductive Programming is not new. The special appeal and novelty of this work is that, contrary to previous approaches, the program schemes are neither fixed, nor selected by an expert user: The applicability of those recursion schemes can be automatically detected in the given IO examples of a target function by checking the universal properties of the corresponding type morphisms. Applying this to the analytical system Igor2, both the capabilities and the expressiveness can be extended without a decrease in efficiency. An extension of the analytical functional inductive programming system Igor2 is proposed and its algorithms described. An empirical evaluation demonstrates the improvements with respect to efficiency and effectiveness that can be achieved by the use of type morphisms for Igor2 due to a reduction in search space complexity.
-
A Combined Analytical and Search-Based Approach to the Inductive Synthesis of Functional Programs
(2010)
-
Emanuel Kitzelmann
- This thesis is concerned with the inductive synthesis of recursive declarative programs and in particular with the analytical inductive synthesis of functional programs. Program synthesis addresses the problem of (semi-)automatically generating computer programs from specifications. In inductive program synthesis, recursive programs are constructed by generalizing over incomplete specifications such as finite sets of input/output examples (I/O examples). Classical methods for induction of functional programs are analytical, that is, a recursive function definition is derived by detecting and generalizing recurrent patterns between the given I/O examples. Most recent methods, on the other side, are generate-and-test based, that is, they repeatedly generate programs independently from the provided I/O examples until a program is found that correctly computes the examples. Analytical methods are much faster than generate-and-test methods, because they do not rely on search in a program space. Therefore, however, the schemas that generatable programs conform to, must be much more restricted. This thesis at first provides a comprehensive overview of current approaches and methods to inductive program synthesis. Then we present a new algorithm to the inductive synthesis of functional programs that generalizes the analytical approach and combines it with search in a program space. Thereby, the strong restrictions of analytical methods can be resolved for the most part. At the same time, applying analytical techniques allows for pruning large parts of the problem space so that solutions can often be found faster than with generate-and-test methods. By means of several experiments with an implementation of the described algorithm, we demonstrate its capabilities.
-
The Simulation of Action Strategies of Different Personalities In Perspective of the Interaction between Emotions, Motivations, and Cognition (An Experimental Study in the Field of Cognitive Psychology and Artificial Intelligence)
(2006)
-
Ayman Elkady
- The Simulation of Action Strategies of Different Personalities in Perspective of the Interaction between Emotions, Motivations, and Cognition (An Experimental Study in the Field of Cognitive Psychology and Artificial Intelligence) Inaugural-Dissertation in der Fakultät Pädagogik, Philosophie und Psychologie der Otto-Friedrich-Universität Bamberg submitted by Ayman Elkady Abstract 1. Introduction: This research investigates the relationship between the theoretical basis of PSI-theory by Dietrich Dörner and the actual performance of subjects in the Island-game (a well-structured problem in an uncertain environment). The study compares the behavior of human subjects and the PSI simulation. The main results show that the PSI agent is not only able to simulate the different strategies of the experimental subjects, but also able to simulate single cases of personality. 2. Participants: A sample of 40 subjects participated in the experiment. The sample of participants was divided into two groups (group A and group B). Each group consisted of twenty participants. While "group A" played an island-game whos resources could be renewed, group B played the non-renewable resources version. 3. Materials: Island game, a computer simulation of a robot, called James, - endowed with several needs (e.g. for energy, for water), was used. The "island" contains numerous locations with different objects that can be manipulated in various ways. Manipulations of the objects can have effects on the robot (e.g. water can be drunk and the need for food is satisfied). Subjects have to control the robot and satisfy his existential needs. Moreover, they have to collect energy-rich-lumps of rock called 'Nucleotides'. 4. Experimental Design and Procedure: At the beginning of the experiment, participants were informed that they took part in a problem-solving experiment. Before beginning the first session, standard instructions for the task were given using Power Point presentation that explained the basic rules of the game and the tasks, namely, to keep the robot alive (e.g. to find enough water and food for the robot) and to collect so-called "Nucleotides". During these periods and all experimental conditions, subjects were allowed to think and speak freely. 5. Results of the experiment: The experiment show that there are no differences between the results of the participants of group A and the results of the participants of group B with respect to the eight dependent variables and the fact that the participants had played the game using different strategies. Therefore, we can assume that in this case the type of environment, whether poor or rich, does not play an important role. Most important is the way (the strategy) the available resources are managed by the actors. We have found these playing strategies: The Nucleotides-First-Strategy: Nucleotides are considered as a main motive and the existential needs of the robot are ignored. Survival-strategy: Existential needs of the robot are considered as a main motive and nucleotides are ignored. The Balance-Between-Motives-Strategy: Some participants made a balance between motives. In other words, some participants were capable of achieving both tasks (saving the robot from breakdowns and collecting nucleotides) by considering all goals of existential needs together with nucleotides. Stereotype-strategy: All goals of the different motives are included and are accompanied by a low selection threshold. 6. Simulation: We proposed that the PSI-program (and of course the theory behind the program) had motives, emotions and cognitive processes similar to those which human participants had in the experiment. Therefore, we set PSI-parameters in way that could simulate and produce the same strategies the subjects used in the experiment. The program was run with varying chance values within the specific range of all parameters. Simulation time had been varied because we discovered that the subjects had different playing-speeds. 7. Results of the simulation: The PSI model can produce the same strategies that the subjects had used during playing the Island game. There are highly significant correlations between PSI's behavioral parameters and the subjects' means for all parameter sets. Moreover, qualitative analyses of the two single cases indicated that PSI can also simulate single case strategies.