Programação Funcional Avançada 2004 / 2005

AKA: Advanced Functional Programming

General information

Advanced Functional Programming is an optional course made available for 5th year students of the following degrees:

• 5309?? - Licenciatura em Engenharia de Sistemas e Informática
• 7009?? - Licenciatura em Matemática e Ciências da Computação

Course Staff

(Alphabetically ordered by surname) J.C. Bacelar, J.B. Barros, M.A. Cunha, J.N. Oliveira J.S. Pinto, J.A. Saraiva (course leader), Joost Visser,

Structure of the Course

The course is organised into two parts:

1. A set of seminars introducing relevant topics to be covered. This seminars will be primarily given by the students. Some more advanced material, however, can/will be presented by the course lecturers or by guests visiting the department.
2. In the second, more substantial part of the course, students will develop a project (see List of Projects Available).

Number of students: Minimum 5, maximum 10.

Assessment

The following three items will be taken into account for student evaluation:

A - Background lecture

The students will deliver a short lecture (20m) introducing one of the topics covered in the course.

B - Brief Project/Tool Presentation

The different groups will give a lecture (30m) presenting the project they have chosen for development and the tool(s) that will be used in this task.

C - Project Presentation and Report

Each group will give a lecture presenting the project.

The final mark is computed according to the formula:

Program synopsis

Main topics of the course are:

• Imperative Functional Programming
  • Monads and Effects
  • Robots
  • Graphical User Interfaces
    • Functional Programming for the Web
      • Scripting Combinators (Wash-CGI)
      • HaXML? /XQuery
      • Language Processing in Strafunski
      • HASKELL development tools
  • Advanced Functional Data Structures
  • Program transformation techniques

Program in detail

• Week 1 (2004.10.06): kick off: definition of topics and projects

• Week 2 (2004.10.13): meetings with supervisors

• Week 3 (2004.10.17): talk by Simon Thompson
  • When/Where: Oct 20nd, 3pm, room DI-A1
  • Title: Refactoring Functional Programs
  • Abstract: Refactoring is about improving the design of existing computer programs and systems; as such it is familiar to every programmer, software engineer and designer. Its key characteristic is the focus on structural change, strictly separated from changes in functionality. A structural change can make a program simpler, by removing duplicate code, say, or can be the preparatory step for an upgrade or extension of a system.
    It is characteristic of refactorings that they are 'diffuse' and 'bureaucratic': consider the example of the simplest possible refactoring: renaming a component of a program. To effect this change requires not only the component definition to be changed, but also every use of the component must be similiarly modified. This involves changing every file/module which might use the component, potentially tens or hundreds of modules. Moreover, it is equally vital not to change any components hidden in other parts of the system which happen to share the same name. Of course, it is possible to do refactorings 'by hand', but this process is tedious and, more importantly, error-prone. Automated support for refactorings makes them safe and easy to perform and also secure in their implementation.
    The 'Refactoring Functional Programs' project comprising Huiqing Li, Claus Reinke and Simon Thompson is building the HaRe system to support refactorings for Haskell programs. HaRe is designed as a serious tool for use by practising programmers: HaRe supports the whole of the Haskell; it is integrated into standard development environments and it preserves the 'look and feel' of refactored programs. HaRe is built using a number of existing libraries: 'Programatica' provides tools on which to build the language-analysis components, and 'Strafunski' gives general support for tree transformations.
  • Links: http://www.cs.kent.ac.uk/projects/refactor-fp

• Week 4 (2003.10.24): students project presentations (item B)

• Week 5 (2004.11.31): talk by Joost Visser
  • When/Where: Oct 28, 16:00-18:00, room DI-1.04
  • Title: Strafunski: a Haskell-centered bundle for generic programming and language processing
  • Abstract: Strafunski is a bundle of a combinator library and various generative tools that support key tasks in language processing: parser generation and traversal. The traversal support is based on the notion of functional strategies: generic functions that can traverse into terms of any type while mixing type-specific and uniform behaviour. The parsing support is involves connectivity to the Generalized LR parser SGLR. Finally, an enhanced version of DrIFT ensures that traversal and parsing support can easily be deployed for (extremely) large languages such as Java or Cobol. The following will be covered in the talk:
    • Essentials of Strafunski: concepts and architecture, relationship to GHC's Data.Generics.
    • Hands-on session of strategic programming with Strafunski.
    • Design patterns for programming with Strafunski.
  • Slides: http://www.di.uminho.pt/~jno/html/StrafunskiAFP.pdf
  • Links:
    • http://www.cs.vu.nl/Strafunski/
    • StrafunskiTutorial.zip: download, unzip, go through the exercises in the contained pdf.

• Week 6 (2003.11.10):
  • Tutorial on foreign function interfacing by JoseBacelarAlmeida.
  • Support material: ffi.tgz

• Week 7 (2003.11.17): meetings with supervisors

• Week 8 (2003.11.24): Tutorials by Doaitse Swierstra
  • When/Where: Nov 23, 14:00-16:00, room Sala de Reuniões
  • Title: Linear, Online, Functional Pretty Printing
  • Abstract: We present an implementation of Oppen's Pretty printing solution in Haskell. The algorithm is linear in the size of the input, independent of the line width, uses limited look ahead, and has online behaviour.
    
  • Title: Parsing permutation phrases
  • Abstract: A permutation phrase is a sequence of elements (possibly of different types) in which each element occurs exactly once and the order is irrelevant. Some of the permutable elements may be optional. We show how to extend a parser combinator library with support for parsing such free-order constructs. A user of the library can easily write parsers for permutation phrases and does not need to care about checking and reordering the recognized elements. Applications include the generation of parsers for attributes of XML tags and Haskell's record syntax.

• Week 9 (2003.12.01):
  • Luís Pedro Machado presents the project: Embedding Disambiguation Rules in the HaGLR System
  • meetings with supervisors

• Week 10 (2003.12.08): J.M.Valença
  • Monadic Strategies - the teachers allocation problem
  • program files here

• Week 11 (2003.12.15):
  • Students present the studied papers (see literature section in projects).

• January 2004: project presentations (item C)

List of Projects Available

List of projects announced so far :

• ChopaChopsAFPProject
• SpreadsheetUnderScrutinyAFPProject
• StrategicXMLQueryingAFPProject
• XMLtoSQLConversionToolAFPProject
• HaskellBindingToGraphViz
• DisambiguationGLR

Final Marks

Information to become available in due time.

• ProgramacaoFuncional0405

-- JorgeSousaPinto - 04 Mar 2006

Notas da época normal disponibilizadas nesta página

-- JorgeSousaPinto - 07 Feb 2006

Disponíveis nesta página:

• Notas do TP
• Slides relativos ao 3o. capítulo da matéria (Problemas NP-completos)

-- JorgeSousaPinto - 15 Dec 2005

Disponíveis nesta página os slides relativos ao primeiro capítulo da matéria (Análise de Algoritmos) e um conjunto de enunciados de exercícios sobre este tema.

-- JorgeSousaPinto - 19 Nov 2005

Disponível nesta página o enunciado do trabalho prático

-- JorgeSousaPinto - 29 Oct 2005

Já disponíveies os slides relativos ao primeiro capítulo da matéria (Grafos)

-- JorgeSousaPinto - 26 Sep 2005

Phase 1 (Opção 3, sep 2003 -- feb 2004)

The first edition of the Attack On The Clones project was a project carried out in the context of Opção 3 of LESI.

Project description

Create a Clone Detection Portal. Clones are duplicate pieces of software that generally result from copy-paste techniques in programming. Clones can differ slightly, for instance in the names of variables or in the exact order of statements and declarations. A pragmatic technique for detecting clones is to compute metrics over the code, and compare the metrics. If the metrics for two pieces are (almost) identical, they are clones. In this project you will create a web site where one can (i) upload Java source code to be subjected to metric-based clone detection, and (ii) inspect the detection results.

Team

• Bruno Silva (30174)
• RuiAbreu? (30257)

Supervision

• Joost Visser
• Antonio Nestor Ribeiro

Phase 2 (continuation)

Objectives

• Support for more projects
• "Project to itself" comparison
• Improve the user interface

Project description

The project is based on the detection of similar source code in Java source code files. One of the major reasons why clones occur is code reuse by copying a pre-existing program fragment. Code clones are one of the factors that degrade the structure of the software and lower the software quality. If one changes a code clone, he/she must also update all other copies and that can raise the maintenance cost. It is also useful to know wich parts of different source codes are clones to each other. The result of the project is the next step of the 1. edition of the clone detection portal. Because the 1. edition was designed for testing only two Java projects in one "detection", this was changed and now the portal supports the submition of more projects. Therefore the way of metrics extraction had to be changed; metrics are extracted from each project directly after the submition. The time needed to calculate metrics remains the same as in the previous version-can increase drastically when computing large projects source code. Because it is very useful to know which parts of a project are similar to other ones-contain similar source code, the option of comparing the project to itself was added also. The problem of finding out if duplicated source code is spread out over a single project shouldn't be one anymore. After the metrics have been computed, the detection of clones can be initialised either by comparing projects metrics (overlap of projects metrics and overlap of class comparison between two projects) and/or by a line-by-line comparison with the later also supporting a graphical representation of the cloned lines. When detecting clones, both ways should be taken in account. For validation purposes different editions of the JJTraveler tool and some students projects were used.

Team

• RokPurkeljc

Supervision

• Joost Visser

ChopaChops: view and manipulate Java program graphs

Powered by Chocapic!

Student: Patrick Machado

In this project you will develop an interactive tool to view and manipulate various kinds of graphical representations of Java programs. Your starting point is an initial version of the tool (called ChopaChops) that can already:

• a. parse Java
• b. derive inheritance, import, and nesting relations
• c. display these relations in a graph
• d. perform slicing and chopping on this graph

• e. derive data flow and control flow relations
• f. compute some graph-based program metrics
• g. support more graph manipulations
• h. improve the interactive interface

You will be using and extending functionality offered by the UMinho Haskell Libraries to accomplish these tasks.

Paper Presentation

Project Report

Presentations

• Program slicing
• Final project presentation

-- PatrickMachado? - 15 Dec 2004

Recomended Literature

1. A Survey of Program Slicing Techniques, Frank Tip, 1994
2. The Use of Program Dependence Graphs in Software Engineering, Susan Horwits and Thomas Reps, 1992
3. Graph Theoretic Foundations of Program Slicing and Integration, Arun Lakhotia, 1993

-- JoaoSaraiva - 27 Oct 2004

To be filled with abundant and pertinent information.

Work-in-progress project page: http://www.patanisca.com/clones/

-- GuilhermeLopes - 28 Oct 2005

Aula 2 -- 2 de Março
Apresentação da disciplina. Apresentação do trabalho prático 1.

Aula 3 -- 9 de Março
E-learning. Apresentação do conceito e análise de alguns documentos sobre o tema.

Aula 4 -- 16 de Março
Open Source Software. Apresentação do conceito e análise de alguns documentos sobre o tema.

Aula 5 -- 23 de Março
Introdução ao Latex. Apresentação de exemplos.

Aula 6 -- 30 de Março
Realização do trabalho prático 1.

Aula 7 -- 6 de Abril
Introdução ao UML. Diagramas de casos de uso. Realização do trabalho prático 1.

Aula 8 -- 20 de Abril
Não houve aula. Motivo: doença.

Aula 9 -- 27 de Abril
Apresentação oral do trabalho nº 1.

Aula 10 -- 4 de Maio
UML: Diagramas de actividade e diagramas de transição de estados. Resolução de exercícios.

Aula 11 -- 11 de Maio
UML: Diagramas de classes. Resolução de exercícios.

Aula 12 -- 18 de Maio
Não há aula. Motivo: Enterro da Gata.

Aula 13 -- 25 de Maio
UML: Resolução de exercícios.

Aula 14 -- 1 de Junho
Apresentação oral do trabalho nº 2.

Embedding Disambiguation Rules in the HaGLR System

Student: Luís Pedro Machado

In this project we will embed a domain specific language to express disambiguation rules in the HaGLR system: A Generalised LR parser generator. Such disambiguation rules "work" very much like precedence and priority rules used by YACC-like systems. Traditional techniques use a language processor for processing the disambiguation "language" and, then, combine them with the parser (either buy applying such rules at parse time , or by applying them as a filter over the resulting set of abstract syntax trees).
The UMinho Haskell Libraries already provide support for:

• a. Generalised LR parsing. The HaGLR system is a GLR parser generator.
• b. Parsing SDF grammars, that includes a large set of real programming language grammars defintions.
• c. The construction and visualization of the resulting XML parse trees.

You will define a language to express disambiguation rules (based on exiting ones). Then you will implement a function that given a sentence of that langauge (ie, a set of rules) and the resulting parse forest and it selects the right tree(s).

Recomended Literature

1. Disambiguation Filters for Scannerless Generalized LR Parsers, M.G.J. van den Brand, J. Scheerder, J.J. Vinju, and E. Visser, 2002
2. Pure Functional Parsing, Peter Ljunglof, 2002
3. Parser Generation for Interactive Environments, J. Rekers, 1992

T (2006.10.21b): Introdução à modelação de sistemas computacionais em VDM-SL. Tipos e invariantes. Especificação de operações. Estudo de um caso.

T (2006.11.04a): Conclusão da aula anterior. Apresentação da ferramenta VDMTools.

T (2006.11.04b): A linguagem de especificação VDM-SL: expressão de propriedades em lógica de 1a ordem. Problemas de definição.

T (2006.11.11a e 11b): Não houve aula.

T (2006.12.9a): A linguagem de especificação VDM-SL: modelação de problemas com conjuntos e sequências. Polimorfismo e ordem superior (exemplos). Especificação ímplicita vs explícita. Funções vs operações. Exemplo: cálculo da raíz quadrada (especificação disponível aqui).

T (2006.12.9b): A linguagem de especificação VDM-SL: modelação de problemas com correspondências. O caso do sistema de gestão de contas bancárias. Especificação funcional (BAMS) e orientada ao estado (SBAMS).

T (2006.12.16a): Aula laboratorial em VDMTools.

T (2006.12.16b): Aula laboratorial em VDMTools.

T (2007.01.20a): Estudo de caso em modelação VDM: multiconjuntos.

T (2007.01.20b): Discussão dos projectos individuais de modelação.

T (2007.01.27a): Estudo de caso em modelação VDM: o espaço de endereçamento web.

T (2007.01.27b): Acompanhamento dos projectos individuais de modelação.

-- LuisSoaresBarbosa - 27 Jan 2007

Elementos Lógicos da Programação 3

Licenciatura em Matemática e Ciências da Computação
3º Ano - 2º Semestre
Ano lectivo 2004-2005

Responsável

• JoseManuelValenca

Equipa Docente

Horário das Aulas

• Teórica: 3a das 11:00 às 13:00 (DI A1)
• Teórico-prática:
  • TP1 - 2a das 11:00 às 13:00 (DI 0.11)
  • TP2 - 5a das 11:00 às 13:00 (DI 0.11)

Programa Detalhado

• Redes de Petri
  • Modelação de sistemas concorrentes com redes de Petri.
  • Cálculo de matrizes de incidência.
  • Semântica operacional baseada em sistemas de transição de estados.
  • Propriedades fundamentais de redes: finitude, animação e invertibilidade.
  • Cálculo de invariantes de estado.
  • Extensões às redes não coloridas: lugares com capacidade explicita e arcos inibidores.
  • Redes coloridas.
  • Ferramentas para especificação e animação de redes de Petri (DaNAMiCS, PEP).
• Verificação de modelos
  • Especificação de propriedades de segurança e animação usando lógica temporal.
  • Lógicas CTL*, CTL e LTL.
  • Representação mínima de fórmulas CTL.
  • Verificação directa de modelos para a lógica CTL.
  • Representação da relação de acessibilidade usando lógica proposicional.
  • Verificação simbólica de modelos para a lógica CTL baseada em OBDDs.
  • Ferramentas para verificação simbólica de modelos (SMV).

Critério de Avaliação

• Hipótese 1
  • Exame Teórico (100%)
• Hipótese 2
  • Exame Teórico (60%, com nota mínima de 8 valores) + Projecto Prático (40%)

• Notas finais época recurso (notas)
• Notas finais época normal (notas)
• Notas finais época especial (notas)

Exames

• 1a Chamada (exame, notas)
• 2a Chamada (exame, notas)
• Recurso (exame)

Exemplos

• Aula 2
  • Partida (bim) e Corrida (bim)
  • Semáforo seguro (bim) e justo (bim)
• Aula 3
  • Produtor consumidor (bim)
• Aula 4
  • Produtor consumidor com 2 buffers sequenciais (bim) e paralelos (bim)
  • Bolas vermelhas e pretas (bim)
• Aula 5
  • 2 produtores com prioridade (bim) e depois do unfold (bim).
  • Biblioteca (bim, bim, bim) e depois do unfold (bim)
  • Conferência (bim)
• SMV
  • Exclusão mútua (smv), biblioteca (smv) e cache (smv)
• Exames
  • Rãs e Princesa normal (bim) e de 3 em 3 (bim).
  • Elevador (smv)
  • Slot machine (bim) sem moedeiro temporário (bim).
  • Braço mecânico (bim)
  • Exercício 3 da 2a chamada (smv).

Bibliografia

• Petri Nets for Systems Engineering: A Guide to Modeling, Verification, and Applications, Claude Girault and Rüdiger Valk (editors). Springer-Verlag 2003.
• Elements of Distributed Algorithms: modeling and analysis with petri nets, Wolfgang Reisig. Springer-Verlag 1998.
• Model Checking, Edmund M. Clarke Jr., Orna Grumberg, and Doron A. Peled. MIT Press 2001.

Apontadores WEB

• Petri Net World
• PIPE (zip)
• DaNAMiCS (tar.gz)
• PEP tool
• Integrated Network Analyser
• SMV Model Checker (binário)
• NuSmv Model Checker (uma variante Open Source do SMV)

Edições Anteriores

• 2003-2004

27 Jul Já saíram as notas das orais.

22 Jul Já saíram as notas do exame de recurso. As orais serão no dia 27 às 10h00.

11 Jul Já saíram as notas finais da época normal.

5 Jul Quem quiser entregar o projecto prático deverá fazê-lo até ao dia 8 de Julho.

5 Jul As notas da 2a chamada já saíram.

28 Jun As notas da 1a chamada já saíram. As orais serão no dia 7 Julho às 10h00.

5 Abr O enunciado do projecto prático pode ser consultado aqui.

9 Mar Os exemplos das aulas práticas já estão disponíveis para download.

7 Mar A ferramenta DaNAMiCS já está disponível para download.

Grammar Engineering

Location: Vrije Universiteit or CWI in Amsterdam, The Netherlands.

In many areas of computing, languages play a central role. Programming languages, data definition languages, scripting languages, mark-up-languages, query languages, etc. Unfortunately, it is common practise in software engineering to apply mostly ad-hoc techniques when dealing with language syntaxes. Grammar Engineering seeks to remedy this situation by regarding grammars as valueable software artifacts, and applying good engineering practises to their development, deployment, and maintenance.

In this project you will implement a tool-suite for Grammar Engineering. The tool-suite will include (i) support for grammar reconstruction from language reference manuals, (ii) a combinator library for reshaping grammars, and (iii) support for generating parsers, XML shema's, transformation libraries, and other software components from grammars. Your tool-suite will use the Syntax Definition Formalism (SDF) as internal representation format. To design your tool-suite you will take inspiration from published work and previously developed prototypes.

The implementation of this tool-suite will normally require some technology that it is fit to implement all of the above components while this technology should then also benefit from the provided components. Here are some options:

• A Haskell-centric approach with combinator parsing.
• An ASF+SDF Meta-Environment approach with its SGLR parsing technology.
• General-purpose programming languages and main-stream parser generators like ANTLR.

For example, in the Haskell scenario, the tool-suite is implemented in Haskell and it would be useful for the Haskell programmer. That is, the tool-suite would then help with deploying Haskell-based parsers, XML components and others while processing SDF grammars as input.

See also: the Grammar Ware page.

Supervisors: Ralf Laemmel (VU & CWI, The Netherlands), JoostVisser (UMinho)

Benchmarking Generic Programs

Location: Vrije Universiteit or CWI in Amsterdam, The Netherlands.

Generic Programming encompasses programming techniques that allow the construction of programs that work for just about any kind of data type. Examples of generic programming solutions are Strafunski, traversal functions in ASF+SDF, Generic Haskell, Polytypic Programming, and visitor combinators.

In this project you will perform thorough benchmarking of various generic programming approaches, and investigate some options for improving the efficiency of generic programs. To this end, you will develop a benchmark suite of generic programming problems, and corresponding solutions for each approach under scrutiny. You will investigate both time and space consumption by the various approaches. You will publish your benchmark suite and the results of running it on the internet, such that in future others can take advantage of it when comparing and evaluating generic programming approaches in future.

Supervisors: Ralf Laemmel (VU & CWI, The Netherlands), JoostVisser (UMinho)

%STARTINCLUDE%

body {
  background-color : lightgray;
  font-family: Verdana, Arial, Helvetica, sans-serif;
  font-size: 12px ;
}

a:link    { text-decoration : none ; color : darkblue ; }
a:visited { text-decoration : none ; color : darkblue ; }
a:hover   { text-decoration : none ; color : darkred ; }
a:active  { text-decoration : none ; color : darkred ; }

div.WebLeftBar a:link    { text-decoration : none ; color : #444444 ; }
div.WebLeftBar a:visited { text-decoration : none ; color : #444444 ; }
div.WebLeftBar a:hover   { text-decoration : none ; color : darkred ; }
div.WebLeftBar a:active  { text-decoration : none ; color : darkred ; }

hr { color : black ; border : solid 0 ; padding : 0 ; background-color : darkgray; height : 1px}

div.WebTopBar {
  background : white ;
  border : solid ;  
  border-width : 1px ;
  border-color : darkgray; 
  font-size : 200% ;
  font-style : italic ;
  margin: 0em ;
  padding : 0.5em ;
}

.WebTopMenuBar {
  background : %WEBBGCOLOR%;
  border : solid ;
  border-width : 1px;  
  border-color : %WEBBGCOLOR%; 
/*  width : 100% ; */
  margin: 0em ;
  padding : 0.5em ;
}

.WebContentCanvas {
  background : %WEBBGCOLOR% ;
  border: solid ;
  border-right-width : 1px;  
  border-left-width : 1px;  
  border-bottom-width : 1px;  
  border-top-width : 0em;  
  border-color: darkgray; 
  margin: 0em ;
  padding : 0em ;
}

.ContentTopicTitle {
  font-size : 150% ;
}

H1, H2, H3, H4, H5, H6 { 
  display: block 
}

H1 { margin-top: 0em; margin-bottom: 1em }
H2, H3, H4 { margin-top: 1em; margin-bottom: 1em }
H5, H6 { margin-top: 1em }
//H1 { text-align: center }
H1, H2, H4, H6 { font-weight: bold }
H3, H5 { font-style: italic }

H1 { font-size: xx-large }
H2 { font-size: x-large }
H3 { font-size: large }

.WebLeftBar {
  vertical-align : top ;
  background : %WEBBGCOLOR% ;
  border: 0em;
  width : 120px ; 
  font-size : 90% ;
  color : #444444 ;
  float : left; 
  margin: 0em ;
  padding-left : 10px ;
  padding-top : 10px ;
  padding-right : 10px ;
  padding-bottom : 10px ;
}

.newsbar {
  font-size : 85% ;
}

.WebContent {
  position : scroll ;
  vertical-align : top ;
  background : white ;
  border: solid; 
  border-left-width: 1px;  
  border-right-width: 1px;  
  border-top-width: 1px;  
  border-bottom-width: 1px;  
  border-color: darkgray; 
  padding-top : 20px ;
  padding-left : 20px ;
  padding-right : 20px ;
  padding-bottom : 10px ;
  margin-top: 0em ;
  margin-left: 140px ;;
}

.WebContentSolo {
  position : scroll ;
  vertical-align : top ;
  background : white ;
  border: solid; 
  border-left-width: 1px;  
  border-right-width: 0em;  
  border-top-width: 0em;  
  border-bottom-width: 0em;  
  border-color: darkgray; 
  padding-top : 20px ;
  padding-left : 20px ;
  padding-right : 20px ;
  padding-bottom : 10px ;
  margin-top: 0em ;
  margin-left: 0px ;;
}

/* Show the "PREVIEW" word in the background when previewing a topic: */
.WebPreview {
  background: url('%PUBURL%/TWiki/PreviewBackground/previewbg.gif');
  vertical-align : top ;
  border: solid; 
  border-left-width: 1px;  
  border-right-width: 1px;  
  border-top-width: 1px;  
  border-bottom-width: 1px;  
  border-color: darkgray; 
  padding-top : 20px ;
  padding-left : 20px ;
  padding-right : 20px ;
  padding-bottom : 10px ;
  margin-top: 0em ;
  margin-left: 140px ;;

}



/* Make warnings appear in red, bold text: */
font.warn
{
  color: red;
  font-weight: bold;
}

%STOPINCLUDE%

{ Edit | Attach | Ref-By | Printable | Diffs | More... }

Copyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback

Haskell Biding to GraphViz

Student: João Paulo Barbosa

Overview

This project consists of creating a Haskell binding to AT&T's GraphViz library. This involves using a Foreign Function Interface (FFI) to invoke the C functions of the GraphViz library from within Haskell. To simplify the task of writing this FFI invocations, a tool named GreenCard is beeing used. Next, an abstraction layer is introduced to hide all the miscelaneous procedures of GraphViz and to provide a simple, but powerfull interface to the Haskell application.

With a minimal binding it's possible to replace the graph visualization support in the HaLex library (generating DOT) by invocations to the foreign functions specified. Also, new instances are declared of the types witch one wants to visualize. HaLex is an instance, since UMinho's Haskell Libraries uses GraphViz widely. This is of course a incremental work and hopefully in the end one could visualize and interact with data.

Implementation

To be updated soon... need to sleep... (Knock, Knock.... wake up.... :)) (Who's there?) (That's me! :))

Greencard

Graphviz

Core

Attribute

Graphable

Layoyt

Render

UI

Future Work

Download

Checkout module Graphics.Graphviz from Research.PURe CVS repository. PUReSoftware

Presentations

• First presentation (portuguese)

• Final presentation (portuguese)

Recomended Literature

1. An open graph visualization system and its applications to software engineering, Emden R. Gansner and Stephen C. North, Software - Practice and Experience, 1999.
2. Drawing graphs with Graphviz, Emden R. Gansner, 2004.
3. The Haskell 98 Foreign Function Interface 1.0: An Addendum to the Haskell 98 Report, Manuel Chakravarty (ed.), 2002,2003.

-- JoaoPBarbosa - 04 Mar 2005

1 de Março início das aulas -- JoseManuelValenca

8 de Março devido à minha presença num júri não é possível dar a aula deste dia; nesta semana funciona só o turno de 4ª feira. -- JoseManuelValenca

22 e 23 de Março devido a uma reunião em Lisboa não posso dar aulas esta semana. -- JoseManuelValenca

21 de Abril foi criada a primeira página de ensaios que pode servir de exemplo para outras páginas. -- JoseManuelValenca

13 de Junho atenção aos critérios de avaliação dos trabalhos; está definida a escala de classificação na gama D .. A -- JoseManuelValenca

30 de Junho tendo em atenção que dificilmente se conseguirá fazer todas as apresentações nos dias 8 e 9 de Julho, continuaremos essas apresentações no dia 14 às 9:00 horas -- JoseManuelValenca

5 de Julho atendendo ao elevado número de possíveis apresentações (cerca de 90) não é logisticamente possível realiza-las como estava acordado. Por isso é necessário alterar as condições de apresentação como se indica nesta página. Ficam sem efeito as datas de apresentação de 8, 9 de Julho; as apresentações serão efectuadas numa dada a combinar com cada um dos alunos interessados. -- JoseManuelValenca

Ensaios de Helena Ribeiro, Arlindo Barros e Liliana Correia

Sociedade de Informação – Cartão Único de Saúde

Voto Electrónico

Digitaliação de Livros

Comércio Electrónico

Cidades Digitais

-- JoseManuelValenca - 02 May 2005

-

Ensaios de Ana Ferreira, Alexandra Cruz e Michelle Pinto

-- JoseManuelValenca - 11 Jun 2005

O Comércio Electrónico

-- JoseManuelValenca - 11 Jun 2005

Phishing

-- JoseManuelValenca - 11 Jun 2005

Este também é um trabalho expositivo mas está melhor focado e dá alguma informação. Avalio-o como B

-- JoseManuelValenca - 11 Jun 2005

Registos Criminais

-- JoseManuelValenca - 11 Jun 2005

Sistemas de Informação Clínica

Voto Electrónico

-- JoseManuelValenca - 05 May 2005 -

Ensaios de Joana Vilas Boas e Ana Daniela Barbosa

Que força probatória terá uma mensagem de correio electrónico?

O Voto Electrónico

eCash

Cifra

Cartão Único do Cidadão

-

-- JoseManuelValenca - 05 May 2005

Ensaios de Carlos Macedo

Criptografia

Direito vs Informática

-- JoseManuelValenca - 06 May 2005

Ensaios de Jorge Serralheiro, Pedro Lima e Luis Cantanhede

Bilhete de Identidade Electrónico

BIOMETRIA: “SERÃO MESMO OS OLHOS O ESPELHO DA ALMA”

OS DIREITOS DE AUTOR NA INTERNET

Menores e Internet:Perigos Iminentes

NOVAS TECNOLGIAS E A PRIVACIDADE DO TRABALHADOR: “Big Boss ou Big Brother?”

-- JoseManuelValenca - 09 May 2005

Ensaios de Ana Araújo Silva e Filipe Macedo

Vigilância electrónica: Ponderação de princípios

-- JoseManuelValenca - 12 Jun 2005

A Teoria da Personalidade no Voto

-- JoseManuelValenca - 12 Jun 2005

Tratamento de Dados Pessoais

-- JoseManuelValenca - 12 Jun 2005

Privacidade On-Line

-- JoseManuelValenca - 12 Jun 2005

Sigilio Bancário

-- JoseManuelValenca - 12 Jun 2005

-- JoseManuelValenca - 12 May 2005

-

Ensaios de Vitor Novo, Manuel Almeida e João Varela

Privacidade dos Dados Clínicos

Agentes e Eventos

A Questão Humana na Segurança da Informacão (parte 1)

Faz sentido falar em direitos específicos das SI ou basta transpor para o novo contexto os direitos actuais?

AS BARREIRAS IMPOSTAS PELOS GOVERNOS POLÍTICOS À LIVRE CIRCULAÇÃO DE INFORMAÇÃO NA INTERNET

-- JoseManuelValenca - 16 May 2005

-

Ensaios de Adelaide Cerqueira e Sandra Pereira

Criptografia e Assinatura Digital

-- AdelaideCerqueira? - 23 May 2005

Segurança Informática

Dados Pessoais

Escritura Pública Informatizada: Uma alternativa?!

Informatização dos Tribunais

-- AdelaideCerqueira? - 23 May 2005

-

-- JoseManuelValenca - 18 May 2005

Ensaios de Eunice Coelho

Titulo1

resumo1

• Titulo1

Titulo2

resumo2

• Titulo2

-

Ensaios de Ana Pereira e Daniela Seixas

Ética Hacker

-- JoseManuelValenca - 11 Jun 2005

Pirataria Legal

-- JoseManuelValenca - 11 Jun 2005

Privaciadade de Dados Clínicos

-- JoseManuelValenca - 11 Jun 2005

Sim ao voto electrónico

-- JoseManuelValenca - 11 Jun 2005

Vidas virtuais

-- JoseManuelValenca - 11 Jun 2005

-- JoseManuelValenca - 27 May 2005

Ensaios de Henrique Cunha, Cristina Ferreira e Mafalda Magalhães

Esteganografia no Processo Civi

-- MafaldaMagalhaes? - 08 Jun 2005

-- MafaldaMagalhaes? - 08 Jun 2005

-- MafaldaMagalhaes? - 08 Jun 2005

-- MafaldaMagalhaes? - 08 Jun 2005

-- MafaldaMagalhaes? - 08 Jun 2005

-- MafaldaMagalhaes? - 08 Jun 2005

-- MafaldaMagalhaes? - 08 Jun 2005

Registos e Informática

-- MafaldaMagalhaes? - 08 Jun 2005

-- MafaldaMagalhaes? - 08 Jun 2005

-- MafaldaMagalhaes? - 08 Jun 2005

A utilização da Informática e o número único na CRP

O mundo jurídico e as tecnologias da informação

Privacidade de dados clínicos e não repúdio de actos médicos

-- JoseManuelValenca - 31 May 2005

Ensaios de Casimiro Rosa e Abilio Ribeiro

A INternet e os Direitos de Autor

Assinatura Digital

Internet: Meio de Ultrapassar Barreiras

Phishing: Alerta Máximo!

Tecnologias da Informação e Saúde

-- JoseManuelValenca - 31 May 2005

Ensaios de Sofia Silva

Segurança na Net

-- JoseManuelValenca - 09 Jun 2005

Ensaios de Eunice Coelho

Dados Pessoais

Video-Vigilância

Trabalho 3

Trabalho 4

Trabalho 5

-

Ensaios de Isabel Nunes, Claudia Pereira e Ana Tavares

Voto Electrónico

Vantagens da implementação de um sistema de voto alternativo ao tradicional sistema de voto presencial: voto electrónico.

Privacidade dos Dados Clínicos Pessoais

Assinatura Digital

Cartão Único

Comércio Electrónico

-

Ensaios de Karina Silva e Eva Mendes

Privacidade dos dados clínicos

O voto electrónico

A assinatura digital

O correio electrónico

A sociedade da informação

-

-- JoseManuelValenca - 27 Apr 2005

Ensaios de Andreia Leite, Angela Santos e Vera Silva

Base de Dados de Recolha Genética

-- JoseManuelValenca - 12 Jun 2005

Cartão Único do Cidadão

-- JoseManuelValenca - 12 Jun 2005

Factura Eletrónica

-- JoseManuelValenca - 12 Jun 2005

Publicidade Ilicita e Abusiva na Internet

-- JoseManuelValenca - 12 Jun 2005

O Documento Electronico

-- JoseManuelValenca - 12 Jun 2005

-

-- JoseManuelValenca - 27 Apr 2005

Ensaios de Bruno Silva

Voto Electrónico

A Democracia nos dedos dos Cidadãos. -

-- JoseManuelValenca - 13 Jun 2005

Outros trabalhos

-- JoseManuelValenca - 13 Jun 2005

-- JoseManuelValenca - 28 Apr 2005

Ensaios de Vanessa Freitas e Magda Nunes

Assinatura Digital

Identificação Retinal

Ensino Electrónico

Comércio Electrónico

Voto Electrónico

-

-- JoseManuelValenca - 29 Apr 2005

Ensaios de Susana Dias

Tecnologias da Informação e Comunicação na Saúde

A Progressiva Informatização no Direito

(RE) PENSAR A SOCIEDADE DE INFORMAÇÃO E COMUNICAÇÃO

Teletrabalho: o futuro

A EDUCAÇÃO E AS T.I.C.

-- JoseManuelValenca - 02 May 2005

-

Sessão Laboratorial 2

Nesta sessão pretende-se tomar conhecimento com conceitos básicos da linguagem Haskell, nomeadamente:

• expressões e sua avaliação,
• tipos básicos,
• tipos estruturados,
• utilização do interpretador ghci e do compilador ghc.

ghci: um interpretador da linguagem Haskell

Ao longo deste curso iremos utilizar o interpretador ghci para executar programas escritos na linguagem Haskell. Este interpretador pode ser invocado a partir do Terminal:

$ ghci
   ___         ___ _
  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 6.5.20060608, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base-1.0 ... linking ... done.
Prelude> 

Uma vez no interpretador, podemos realizar uma de duas tarefas:

1. avaliar expressões
2. executar um comando do interpretador

Avaliar Expressões: para avaliar uma expressão basta-nos digitar essa expressão no interpretador. Por exemplo:

Prelude> 5 + 3 * 2
11
Prelude> show (3 * 2 + 1)
"7"
Prelude> 2 * sin(pi/2)
2.0
Prelude> "ABC" ++ (reverse "DEF")
"ABCFED"
Prelude> if odd(3) then (1,"IMPAR") else (0,"PAR")
(1,"IMPAR")

Verificamos então que o ghci avalia as expressões introduzidas apresentando o respectivo resultado. Mesmo sem conhecermos ainda todas as funções apresentadas, podemos desde logo observar que o Haskell não se limita a avaliar expressões numéricas --- na realidade, é capaz de processar dados de natureza muito diversa (diferentes tipos de dados) como números inteiros, decimais, valores de verdade (booleanos), caracteres, sequências, etc. Por outro lado verificamos que dispõe já do conhecimento de algumas funções pré-definidas (como sin, odd, etc.). Estas funções (e muitas outras, naturalmente) estão definidas na biblioteca básica da linguagem, a que se dá o nome de Prelude. Daí o prefixo "=Prelude>=" apresentado no ghci: informa-nos que ele (só) tem carregadas as definições dessa biblioteca. (obs.: biblioteca, em programação, consiste num conjunto de definições disponibilizadas para serem (re)utilizadas pelos programadores.)

Execução de Comandos: para além de avaliar expressões, é-nos também possível executar comandos que controlam o comportamento do ghci (como carregar um ficheiro com definições de novas funções, solicitar informação de tipos, etc.). Os comandos mais utilizados serão:

• :l (fich) - carrega ficheiro (fich),
• :t (expr) - interroga o interpretador sobre o tipo de (expr),
• :b (mod) - visualiza o conjunto de definições de (mod),
• :? - comando de ajuda que fornece uma breve explicação dos comandos disponíveis
• :q - sai do interpretador

De referir é ainda a integração existente entre o ghci/haskell e o Emacs. De facto, este último dispõe de um modo de edição próprio para a linguagem Haskell, activado automáticamente quando é carregado um ficheiro com extensão .hs, que constitui uma mais valia quando editamos programas nessa linguagem (disponibiliza indentação automática, coloração do texto, etc.).

Tarefa 1 - Verifique qual é o tipo das expressões apresentadas acima.

Tipos básicos e estruturados

O Haskell é uma linguagem fortemente tipada - com isto quer-se dizer que o Haskell força a que todas as expressões da linguagem possuam um tipo.

A linguagem oferece o seguinte conjunto de tipos básicos:

• Bool - Booleanos: True e False
• Char - Caracteres: 'a', 'x', 'R', '7', '\n', ...
• Int - Inteiros de tamanho limitado: 1, -4, 23467, ...
• Integer - Inteiros de tamanho ilimitado: 36, 37829938847736292938338283
• Float - Números de vírgula flutuante: 3.5, -45.3, 3e-2, ...
• Double - Números de vírgula flutuante com precisão dupla
• () - Unit: ()

Para além dos tipos básicos, o Haskell disponibiliza formas de construir novos tipos a partir de outros existentes.

• produto cartesiano - (a1, a2) :: (t1, t2) - um par cuja primeira componente a1 é do tipo t1 e a segunda componente a2 é do tipo t2. O produto cartesiano generaliza-se par n-tuplos (i.e. (a1, ..., an) :: (t1, ..., tn),
• listas - [a1,a2, ..., an] :: [t] - uma lista (sequência) constituída pelos elementos a1, a2, ..., an, todos do tipo t,
• funções f :: t1 -> t2 - f é uma função que espera um argumento de tipo t1 e cujo resultado é do tipo t2.

Para além dos tipos apresentados, o utilizador pode ainda definir novos tipos (assunto que retomaremos numa próxima sessão).

Tarefa 2:

• Verifique o tipo das funções utilizadas nas expressões apresentadas acima (e.g. odd, sin, ...)
• Porque é que o Haskell não aceita as seguintes expressões:
  • 3 + 'A'
  • [1,True]
  • not (0)
  • not not

Tarefa 3: * Teste as definições por compreensão apresentadas na aula teórico prática de Programação Funcional da semana anterior disponível aqui.

Definição de funções

A principa tarefa de um programador na linguagem Haskell consiste na definição de funções que realizem as tarefas pretendidas. As funções são definidas por intermédio de regras de cálculo. A título de exemplo, temos

eZero :: Int -> Bool
eZero x = if x==0 then True else False

eZero' :: Int -> Bool
eZero' 0 = True
eZero' _ = False

As funções podem ainda possuir mais do que um argumento. Considere:

maior :: Int -> Int -> Int
maior x y = if x>y then x else y

Note que as definição das funções não deve ser realizada directamente no ghci - devem antes ser definidas num ficheiro (com extensão .hs) que será depois carregado no ghci (comando :l).

Tarefa 4: Defina funções que:

• dados dois números inteiros retorne um par onde a primeira componente é o menor número e a segunda o maior,
• dado o comprimento dos dois lados catetos de um triângulo retorne o comprimento da hipotenusa.
• dado o raio do círculo, retorne o perímetro e a área desse círculo.

Módulos

Um programa em Haskell é formado por um conjunto de módulos. Cada módulo contém um conjunto de definições (declarações de tipos, de funções, de classes, ...) que podem ser utilizados internamente, ou exportados para serem utilizados noutros módulos. Um módulo Haskell é armazenado num ficheiro com extensão .hs, .hs, em que representa o nome do módulo, como declarado na primeira linha do ficheiro. Por exemplo, o ficheiro Teste.hs deverá começar com a declaração seguinte:

module Teste where
   ...

Para utilizar definições contidas num outro módulo é necessário referencia-lo explicitamente. Este tipo de ligação entre módulos estabelece-se utilizando uma declaração import. Como exemplo, vejamos como podemos ter acesso às funções de manipulação de caracteres e strings (listas de caracteres) disponíveis no módulo Char.

module Main where
  import Char
  main = putStrLn ("Isto é o resultado de executar a função "++[toLower x | x <- "MAIN..."])

Uma excepção a esta regra é o módulo Prelude, que constitui a base da linguagem Haskell, e cujas definições estão disponíveis por omissão.

Compilador

Também é possível produzir uma aplicação (ficheiro executável) a partir de um ficheiro em Haskell. Para tal deve-se utilizar o compilador ghc. O módulo a compilar deve conter a função main, que corresponde ao "ponto de entrada" da aplicação (ou seja, essa função será avaliada quando executarmos o programa). A título de de exemplo, para compilar e executar o programa apresentado atrás, devíamos proceder da seguinte forma:

$ ghc -o teste Main.hs
$ ./teste
Isto é o resultado de executar a função main...
$ _

Tarefa 5:

• Compile o programa apresentado e execute-o.
• Crie um módulo com as funções definidas atrás (tarefa 3) e modifique o módulo Main para utilizar uma dessas funções.