Identifying clones in functional programs for refactoring

Clone detection is well established for imperative programs. It works mostly on the statement level and therefore is ill-suited for func- tional programs, whose main constituents are expressions and types. In this paper we introduce clone detection for functional programs using a new intermediate program representation, dubbed Functional Control Tree. We extend clone detection to the identi cation of non-trivial func- tional program clones based on the recursion patterns from the so-called Bird-Meertens formalism

Slicing functional programs by calculation

Program slicing is a well known family of techniques used to identify code fragments which depend on or are depended upon specific program entities. They are particularly useful in the areas of reverse engineering, program understanding, testing and software maintenance. Most slicing methods, usually targeting either the imperative or the object oriented paradigms, are based on some sort of graph structure representing program dependencies. Slicing techniques amount, therefore, to (sophisticated) graph transversal algorithms. This paper proposes a completely different approach to the slicing problem for functional programs. Instead of extracting program information to build an underlying dependencies’ structure, we resort to standard program calculation strategies, based on the so-called Bird- Meertens formalism. The slicing criterion is specified either as a projection or a hiding function which, once composed with the original program, leads to the identification of the intended slice. Going through a number of examples, the paper suggests this approach may be an interesting, even if not completely general alternative to slicing functional programs

Facilitating coordination improvement efforts in cross-functional process development programs

Business process improvement is a common approach in increasing the effectiveness of an organization. It can be seen as an effort to increase coordination between units. Process improvement has proved to be challenging, and most management consultation firms facilitate organizations in this kind of initiatives. Cross-functional improvement is one of the main areas for internal consultants as well. However, the needs, challenges and means of cross-functional help have been rarely discussed in the literature. The objective of this thesis is on one hand to present a conceptual and descriptive framework to help understand the challenges of facilitating coordination improvement efforts in cross-functional improvement programs, and on the other hand to develop and test feasible solutions for some facilitation situations. The research questions are: 1. Why and in what kind of situations do organizations need help in developing coordination in cross-functional processes? 2. How can a facilitator help organizations in improving coordination to develop cross-functional processes? The study consists of two parts. The first part is an overview of the dissertation, and the second part comprises six research publications. The theoretical background for the study are the differentiation causing challenges in cross-functional settings, the coordination needed to improve processes, change management principles, methods and tools, and consultation practises. Three of the publications introduce tools for helping in developing prerequisites, planning responsibilities and supporting learning during the cross-functional program. The three other papers present frameworks to help understand and analyse the improvement situation. The main methodological approaches used in this study are design science research, action research and case research. The research data has been collected from ten cases representing different kinds of organizations, processes and developing situations. The data has been collected mainly by observation, semi-structured interviews and questionnaires. The research contributes to the rare literature combining coordination theories and process improvement practises. It also provides additional understanding of a holistic point of view in process improvement situations. The most important contribution is the addition to the theories of facilitating change in process improvement situations. From the managerial point of view, this study gives advice to managers and consultants in planning and executing cross-functional programs. The main factors increasing the need for facilitation are the challenges for differentiation, challenges of organizational change in general, and the novelty of initiatives and improvement practices concerning process development. Organizations need help in creating the prerequisites to change, in planning initiatives, easing conflict management and collaboration between groups, as well as supporting the learning of cross-functional improvement. The main challenges of facilitation are combining the different roles as a consultant, maintaining the ownership for the improvement project with the client, and supporting learning in the client organization.

Formal methods within a totally functional approach to programming

Taking functional programming to its extremities in search of simplicity still requires integration with other development (e.g. formal) methods. Induction is the key to deriving and verifying functional programs, but can be simplified through packaging proofs with functions, particularly folds, on data (structures). Totally Functional Programming avoids the complexities of interpretation by directly representing data (structures) as platonic combinators - the functions characteristic to the data. The link between the two simplifications is that platonic combinators are a kind of partially-applied fold, which means that platonic combinators inherit fold-theoretic properties, but with some apparent simplifications due to the platonic combinator representation. However, despite observable behaviour within functional programming that suggests that TFP is widely-applicable, significant work remains before TFP as such could be widely adopted.

Higher-order lazy functional slicing

Program slicing is a well known family of techniques intended to identify and isolate code fragments which depend on, or are depended upon, specific program entities. This is particularly useful in the areas of reverse engineering, program understanding, testing and software maintenance. Most slicing methods, and corresponding tools, target either the imperative or the object oriented paradigms, where program slices are computed with respect to a variable or a program statement. Taking a complementary point of view, this paper focuses on the slicing of higher-order functional programs under a lazy evaluation strategy. A prototype of a Haskell slicer, built as proof-of-concept for these ideas, is also introduced

Obstacles to a totally functional programming style

"Totally functional programming" (TFP) advocates the complete replacement of symbolic representations for data by functions. TFP is motivated by observations from practice in language extensibility and functional programming. Its technical essence extends the role of "fold" functions in structuring functional programs to include methods that make comparisons on elements of data structures. The obstacles that currently prevent the immediate uptake of TFP as a style within functional programming equally indicate future research directions in the areas of theoretical foundations, supporting technical infrastructure, demonstrated practical applicability, and relationship to OOP.

Program slicing by calculation

Program slicing is a well known family of techniques used to identify code fragments which depend on or are depended upon specific program entities. They are particularly useful in the areas of reverse engineering, program understanding, testing and software maintenance. Most slicing methods, usually oriented towards the imperative or object paradigms, are based on some sort of graph structure representing program dependencies. Slicing techniques amount, therefore, to (sophisticated) graph transversal algorithms. This paper proposes a completely different approach to the slicing problem for functional programs. Instead of extracting program information to build an underlying dependencies’ structure, we resort to standard program calculation strategies, based on the so-called Bird-Meertens formalism. The slicing criterion is specified either as a projection or a hiding function which, once composed with the original program, leads to the identification of the intended slice. Going through a number of examples, the paper suggests this approach may be an interesting, even if not completely general, alternative to slicing functional programs

Component identification through program slicing

This paper reports on the development of specific slicing techniques for functional programs and their use for the identification of possible coherent components from monolithic code. An associated tool is also introduced. This piece of research is part of a broader project on program understanding and re-engineering of legacy code supported by formal methods

Extending Implicit Computational Complexity and Abstract Machines to Languages with Control

The Curry-Howard isomorphism is the idea that proofs in natural deduction can be put in correspondence with lambda terms in such a way that this correspondence is preserved by normalization. The concept can be extended from Intuitionistic Logic to other systems, such as Linear Logic. One of the nice conseguences of this isomorphism is that we can reason about functional programs with formal tools which are typical of proof systems: such analysis can also include quantitative qualities of programs, such as the number of steps it takes to terminate. Another is the possiblity to describe the execution of these programs in terms of abstract machines. In 1990 Griffin proved that the correspondence can be extended to Classical Logic and control operators. That is, Classical Logic adds the possiblity to manipulate continuations. In this thesis we see how the things we described above work in this larger context.

Instalación de un sistema funcional sobre un computador convencional

En esta tesis se tratan dos aspectos fundamentales de los sistemas funcionales, de cuyo tratamiento depende, en gran medida, la eficiencia de tales sistemas. En primer lugar, se presentan y evalúan una serie de soluciones al problema de representación interna en los sistemas funcionales, soluciones basadas en la utilización de estructuras lineales para obtener una mejora en el tiempo de ejecución y en la ocupación de la memoria del sistema. En segundo lugar, se presenta un sistema de evaluación multitarea para reducir programas funcionales, basado en la especificación de varios ficheros de salida. En él, las tareas del sistema evalúan, de forma concurrente, las diversas partes del resultado de un programa y se .comunican entre sí en base a mensajes que permiten detectar y resolver, sin necesidad de abortar la ejecución, bucles de dependencias entre tareas. El sistema reacciona ante estas situaciones de error de forma comedida, de modo que este error no afecta al resto de las tareas del sistema. Se plantea también un mecanismo de gestión de memoria, mecanismo que introduce una tarea especial en el sistema, encargada de la gestión de una memoria común a todo él, y satisface las necesidades de memoria de las tareas de forma, transparente al mecanismo de evaluación.---ABSTRACT---Two fundamental aspects of functional systems, of which their efficiency to a large extent depends, are dealt with in this thesis. Firstly, several solutions to the internal representation problem of functional systems are proposed and evaluated. These solutions are based on the use of linear data structures in order to achieve a shorter execution time and smaller memory requirement. Secondly, a new multitask evaluation system for the reduction of functional programs is described; it is based on the specifücation of several output files. In this evaluation system, the task evaluates in the different parts of the program result concurrently. Tasks communicate one another through messages, which make it possible to detect and solve the dependency loops within tasks. The program does not need to be aborted, the sistem reacts to such error situations in a smooth way, no other tasks are affected. A memory management system is also introduced. This management system inserts a special task, that carries-out the management of a common memory and serves all tasks memory requirements in a transparent mode to the evaluation mechanism.

Derivación deductiva de programas funcionales con patrones

Una de las dificultades principales en el desarrollo de software es la ausencia de un marco conceptual adecuado para su estudio. Una propuesta la constituye el modelo transformativo, que entiende el desarrollo de software como un proceso iterativo de transformación de especificaciones: se parte de una especificación inicial que va transformándose sucesivamente hasta obtener una especificación final que se toma como programa. Este modelo básico puede llevarse a la práctica de varias maneras. En concreto, la aproximación deductiva toma una sentencia lógica como especificación inicial y su proceso transformador consiste en la demostración de la sentencia; como producto secundario de la demostración se deriva un programa que satisface la especificación inicial. La tesis desarrolla un método deductivo para la derivación de programas funcionales con patrones, escritos en un lenguaje similar a Hope. El método utiliza una lógica multigénero, cuya relación con el lenguaje de programación es estudiada. También se identifican los esquemas de demostración necesarios para la derivación de funciones con patrones, basados en la demostración independiente de varias subsentencias. Cada subsentencia proporciona una subespecificación de una ecuación del futuro programa a derivar. Nuestro método deductivo está inspirado en uno previo de Zohar Manna y Richard Waldinger, conocido como el cuadro deductivo, que deriva programas en un lenguaje similar a Lisp. El nuevo método es una modificación del cuadro de estos autores, que incorpora géneros y permite demostrar una especificación mediante varios cuadros. Cada cuadro demuestra una subespecificación y por tanto deriva una ecuación del programa. Se prevén mecanismos para que los programas derivados puedan contener definiciones locales con patrones y variables anónimas y sinónimas y para que las funciones auxiliares derivadas no usen variables de las funciones principales. La tesis se completa con varios ejemplos de aplicación, un mecanismo que independentiza el método del lenguaje de programación y un prototipo de entorno interactivo de derivación deductiva. Categorías y descriptores de materia CR D.l.l [Técnicas de programación]: Programación funcional; D.2.10 [Ingeniería de software]: Diseño - métodos; F.3.1 [Lógica y significado de los programas]: Especificación, verificación y razonamiento sobre programas - lógica de programas; F.3.3 [Lógica y significado de los programas]: Estudios de construcciones de programas - construcciones funcionales; esquemas de programa y de recursion; 1.2.2 [Inteligencia artificial]: Programación automática - síntesis de programas; 1.2.3 [Inteligencia artificial]: Deducción y demostración de teoremas]: extracción de respuesta/razón; inducción matemática. Términos generales Programación funcional, síntesis de programas, demostración de teoremas. Otras palabras claves y expresiones Funciones con patrones, cuadro deductivo, especificación parcial, inducción estructural, teorema de descomposición.---ABSTRACT---One of the main difficulties in software development is the lack of an adequate conceptual framework of study. The transformational model is one such proposal that conceives software development as an iterative process of specifications transformation: an initial specification is developed and successively transformed until a final specification is obtained and taken as a program. This basic model can be implemented in several ways. The deductive approach takes a logical sentence as the initial specification and its proof constitutes the transformational process; as a byproduct of the proof, a program which satisfies the initial specification is derived. In the thesis, a deductive method for the derivation of Hope-like functional programs with patterns is developed. The method uses a many-sorted logic, whose relation to the programming language is studied. Also the proof schemes necessary for the derivation of functional programs with patterns, based on the independent proof of several subsentences, are identified. Each subsentence provides a subspecification of one equation of the future program to be derived. Our deductive method is inspired on a previous one by Zohar Manna and Richard Waldinger, known as the deductive tableau, which derives Lisp-like programs. The new method incorporates sorts in the tableau and allows to prove a sentence with several tableaux. Each tableau proves a subspecification and therefore derives an equation of the program. Mechanisms are included to allow the derived programs to contain local definitions with patterns and anonymous and synonymous variables; also, the derived auxiliary functions cannot reference parameters of their main functions. The thesis is completed with several application examples, i mechanism to make the method independent from the programming language and an interactive environment prototype for deductive derivation. CR categories and subject descriptors D.l.l [Programming techniques]: Functional programming; D.2.10 [Software engineering]: Design - methodologies; F.3.1 [Logics and meanings of programa]: Specifying and verifying and reasoning about programs - logics of programs; F.3.3 [Logics and meanings of programs]: Studies of program constructs - functional constructs; program and recursion schemes; 1.2.2 [Artificial intelligence]: Automatic programming - program synthesis; 1.2.3 [Artificial intelligence]: Deduction and theorem proving - answer/reason extraction; mathematical induction. General tenas Functional programming, program synthesis, theorem proving. Additional key words and phrases Functions with patterns, deductive tableau, structural induction, partial specification, descomposition theorem.

Fernando García Mercadal y el Movimiento Moderno

La tesis plantea el estudio de la figura de Fernando García Mercadal (1896- 1985) y su obra, en el contexto del proyecto moderno perteneciente a la racionalidad teórica colectiva de la segunda generación del Movimiento Moderno en Europa, y explora la vida y circunstancias de un arquitecto que aunque nacido en el XIX, trajo la modernidad a España. El Movimiento Moderno en España, se articula en las décadas de los años 20 y 30 a través del GATEPAC y un grupo de arquitectos racionalistas en Madrid que Carlos Flores denomina Generación del 1925. Fernando García Mercadal, primero de su promoción en 1921 y pensionado en Roma, pertenece a ambos y pronto se convierte junto con Josep Lluis Sert, en una de las figuras más relevantes del panorama moderno español. Único miembro fundador del GATEPAC que había nacido en el siglo XIX, publica habitualmente en la revista AC (1931-1937), y en la revista Arquitectura desde 1920. Organiza en la Residencia de Estudiantes, entre 1928 y 1932, un famoso ciclo de Conferencias que imparten Le Corbusier, Mendelsohn, Van Doesburg, Gropius y Giedion. También asiste a la reunión constituyente de los CIAM en La Sarraz en 1928, al CIAM II en Frankfurt en 1929 y al CIAM III en Bruselas en 1930. Fue profesor en la Escuela de Arquitectura de Madrid y Arquitecto Jefe de la Oficina de Urbanismo y de Parques y Jardines del Ayuntamiento de Madrid, cargo al que accede por oposición en 1932. Tras la guerra fue depurado e inhabilitado profesionalmente, hasta que en 1946 comienza a trabajar en el Departamento de Arquitectura del I.N.P. donde continúa hasta los años 70. En 1979 es nombrado Académico de número de la Real Academia de Bellas Artes de San Fernando y muere en Madrid en 1985. Estos son los datos conocidos y aunque en la tesis se aportan nuevos datos inéditos, es en las premisas para su interpretación donde este trabajo de investigación pone el acento. En la historiografía de nuestra arquitectura moderna, pervive una tendencia a suponer una desconexión entre la vanguardia arquitectónica en los años 20 y 30 y el movimiento moderno internacional. El manto de silencio que cayó sobre la generación anterior a la guerra, una vez terminada esta, contribuye a reforzar la idea, cuyo origen y causas exceden el ámbito de trabajo, aunque se tratarán tangencialmente por ser ineludible hacerlo. La tesis pone en cuestión ese planteamiento desde el convencimiento fundamentado en los datos y en la consulta de fuentes originales, que la arquitectura española anterior a la guerra, aun con las circunstancias particulares del país, estuvo en sintonía con la europea, siendo esta la hipótesis de partida de la investigación. Las aportaciones más significativas que, a mi entender, presenta la tesis doctoral, y tienen mayor originalidad, son las siguientes; 1.Puesta en valor de la arquitectura de FGM, antes y después de la guerra, abandonando la idea de su supuesta renuncia a las ideas modernas a partir de los 30; 2. Puesta en valor, con aportación de datos concretos, de la Intensa relación mantenida por FGM y otros arquitectos españoles del Movimiento Moderno con los arquitectos de igual tendencia en el resto de Europa, a través de contactos recíprocos y continuos; 3. Estudio de la obra de FGM en el marco del Movimiento Moderno como una nueva arquitectura basada no tanto en la epidermis, como en una forma de hacer y encarar los problemas donde el proceso es tan importante como el resultado; con el Urbanismo como una nueva ciencia, y con el desarrollo de nuevos programas funcionales acordes a las necesidades de la sociedad contemporánea como el Rincón de Goya y el Hospital de Zaragoza. Se manejan tres métodos de trabajo. Los dos primeros aportan un nuevo enfoque al análisis crítico de FGM y su obra, situándole en el contexto internacional, además del español. El tercero, de carácter instrumental, permite el manejo y sistematización de la documentación. El primer método, consiste en aplicar el criterio generacional de Pevsner o Giedion entre otros, al Movimiento Moderno en España, situando a Fernando García Mercadal como arquitecto de la segunda generación, para hacer un análisis crítico comparativo de su trayectoria con otros arquitectos europeos de la misma, que permita establecer semejanzas y diferencias. El segundo método, complementario al anterior, consiste en estudiar las relaciones internacionales de FGM con las figuras más próximas a él y sus posibles influencias. Por último, y en relación con la documentación de obras y proyectos, se manejan a su vez dos criterios. Para la obra completa, y debido a la inexistencia de originales del Legado García Mercadal, se utiliza con carácter general el material ya publicado, disperso en libros y revistas. En el caso de las cinco obras seleccionadas, se completa con búsqueda en archivos, toma de datos in situ actualizados cuando es posible, y una recopilación de su repercusión en prensa escrita de su momento. ABSTRACT This research study focuses on Fernando Garcia Mercadal (1896-1985) and his work in the context of the Modern project as part of the collective theoretical rationality of the second generation of European Modern architecture. It explores the life and circumstances of the architect, who even though born in 19th century introduced Modern architecture in Spain. Modern architecture (Modern Movement) in Spain covered two decades between 20's and 30's through GATEPAC and a group of rationalists in Madrid that Carlos Flores named “generation of '25”. Fernando Garcia Mercadal, top of his class in 1921 and granted with the scholarship in Rome, belonged to both groups and early in his career he became, along with Josep Lluis Sert, one of the most relevant figures of Modern Architecture in Spain. He was the only member of GATEPAC who was born in 19th century. He frequently published on the magazine “AC” (1931-1937) and on “Arquitecture” magazine since 1920. He organized a series of famous lectures at “Residencia de Estudiantes” (Madrid) between 1928 and 1932 in which Le Corbusier, Mendelsohn, Van Doesburg, Gropius or Giedion took part. He was a member of the constituent meeting of CIAM in La Sarraz in 1928, CIAM II in Frankfurt in 1929 and CIAM III in Brussels in 1930. Mercadal was a teacher at Escuela de Arquitectura de Madrid and the Chief of the Urban Planning, Parks and Gardens Office of the Council of Madrid. He earned his position by public examination in 1932. After the civil war he was disqualified professionally until 1946, when he started working at the Architecture Department at INP until 70's. In 1979 he was elected as an academic member of “Real Academia de Bellas Artes de San Fernando” and later died in 1985. These are the well-known facts and even though this research study provides unpublished facts, it focuses on the premises to interpret them. Throughout the historiographical discourse of Spanish Modern architecture there is a tendency to assume a disconnection between the Avant-garde architecture movements in 20's and 30's and International Modern architecture (Modern Movement). The generation preceding the war remained silent in regard to this issue and once the war was over, they contributed to support the disconnection. The origin and cause exceed the frame of this work, even though they are incidentally commented due to its importance. This research study questions the approach explained above, based on the facts and the original sources. Its first hypothesis states that Spanish architecture before the civil war was, under its own circumstances, in tune with European architecture. The most important and original contributions of this research study are the following under my point of view: 1. To highlight the architecture of FGM, before and after the war, leaving behind his reputed withdrawal of Modernity after 30's; 2. To highlight the intense relationship between FGM and other Modern Spanish architects and other European architects sharing the same ideas, providing detailed facts; 3. Study of FGM's work in the context of Modern architecture as a new architecture based on its know-how and the way problems are faced. The process is as important as the result, not so much based on the dermis; with urban planning as the new science and with the development of the new functional programs based on the needs of contemporary society as in Rincón de Goya or Hospital de Zaragoza. Three work methods are used. The first two add a new vision of the critical analysis related to FGM and his work, positioning him in the international context in addition to Spain. The third is used as an instrument to manage and systematize the documentation. The first method applies the generational criteria of Pevsner or Giedion (among others) to Modern architecture in Spain, positioning Fernando Garcia Mercadal as a second generation architect. A critical-comparative analysis of his career and contemporary European architects is made to establish similarities and differences. The second method is complementary to the previous one and studies the international relationships of FGM with other recognised architects that were close to him and their possible influences. At last, in relation to his works and projects, two methods are used. For the complete works, due to the lack of originals, published material found on magazines and books is used as the source. In the case of the five selected buildings, it is complemented with archive search, onsite data collection when possible and the impact on the press at that moment.

Back to Basics: Deriving Representation Changers Functionally

Many functional programs can be viewed as representation changers, that is, as functions that convert abstract values from one concrete representation to another. Examples of such programs include base-converters, binary adders and multipliers, and compilers. In this paper we give a number of different approaches to specifying representation changers (pointwise, functional, and relational), and present a simple technique that can be used to derive functional programs from the specifications.

Monadic Parsing in Haskell

This paper is a tutorial on defining recursive descent parsers in Haskell. In the spirit of one-stop shopping, the paper combines material from three areas into a single source. The three areas are functional parsers, the use of monads to structure functional programs, and the use of special syntax for monadic programs in Haskell. More specifically, the paper shows how to define monadic parsers using do notation in Haskell. The paper is targeted at the level of a good undergraduate student who is familiar with Haskell, and has completed a grammars and parsing course. Some knowledge of functional parsers would be useful, but no experience with monads is assumed.

Measuring and predicting non-functional properties of customizable programs

Magdeburg, Univ., Fak. für Informatik, Diss., 2012