TWiki.PhD Program

Three years ago I started working on my TWiki.PhD project, under FCT's grant SFRH/BD/19186/2004.
I've been working under the supervision of João Saraiva (University if Minho) and Oege de Moor (University of Oxford).
With this TWiki.PhD project, named "Embedded Attribute Grammars", we propose to develop techniques and tools for the embedding of Attribute Grammars in a modern, lazy functional language. In particular, we want to study techniques to embed recent developments in AGs, namely, aspects (aspect-oriented programming), references (imperative programming), multiple inheritance (object oriented programming), strategies (strategic programming) and incremental attribute evaluation (incremental computation).
Yet, Attribute Grammars are also suitable to expresse incremental algorithms. Indeed, there are well known techniques to automatically derive incremental, strict attribute evaluators from an attribute grammar. The techniques developed until now, however, do not consider lazy evaluation. We want to study techniques to merge lazy and incremental evaluation.

This TWiki.PhD research project is to be carried out in the Department of Informatics as Minho University and at Oxford Computing Laboratory, Oxford University.

Activities:

The CircLib? library

The CircLib? library is a Haskell based library that implements the schedulling of circular definitions.

This library implements an adaptation of Kasten's attribute scheduling algorithm to circular programs. The basic idea is that, if a circular program is an ordered circular program, it exists an alternative way to produce the same results produced by the circular program.

The adaptation we propose for Kasten's algorithm also determines this alternative way of producing results.

The complete documentation for this library may be found here.

The HaGLR tool

During my degree internship I was to study, among other things, Parser techniques and algorithms.
Under this goal, we (me and my internship supervisor, João Saraiva) found out that, surprisingly, little work had been done on Generalised LR parsing by the functional programming community.
Given so, we (with Joost Visser's cooperation) embarked on a challenging aproach: to provide GLR support directly in Haskell.
In fact, the popularity of Generalised Parsing is growing since it is able to solve many problems that are common on other technologies based on LL and LR algorithms, and since it is able to handle both real programming languages and domain specific languages.
Our work resulted on the development of the HaGLR tool, a Generalised LR parser generator.

GLR's motivations and HaGLR's implementation and development options, as well as achieved results and performance benchmarks are much better detailed in DI-PURe-04.11.01.pdf's Technical Report.

The tool itself is free for download and use, available as part of the UMinho Haskell Software.

This internship project occurred under the PURe project.

The OCirc tool

The OCirc tool is a tool that allows OCaml programmers to express their multiple traversal programs as circular programs. This tool transforms circular programs written in Ocaml notation, into correct strict Ocaml programs.

There are two versions of the OCirc tool:

• a batch tool that given as input a circular OCaml program generates in the output its strict OCaml program. This version is downloadable here (instalation requirements and instructions included).

• a web-based interactive tool that allows OCirc to be used online. Please try it out here.

Research Projects:

Supervision:

Together with João Saraiva I co-supervise the TWiki.PhD program of Msc. Pedro Martins with title Zippers based embedding of Attribute Grammars.

-- Main.JoaoFernandes - 25 Sep 2008

• JoaoFernandesCV.pdf: Curriculum Vitae

• proposal.pdf: TWiki.PosDocProposal

Circular program

Strict program

Deforested program

Circular Programs

Circular Programs were first proposed by Richard Bird as an elegant and efficient technique to eliminate multiple traversal of data structures.

As the name suggests, Circular Programs are characterized by having what appears to be a circular definition: arguments in a function call depend on results of that same call. That is, they contain definitions of the form:

(...,x,...) = f ... x ...

In order to motivate the use of circular programs, Bird introduces the following problem: consider the problem of transforming a binary leaf tree into a second tree, identical in shape to the original one, but with all the tip values replaced by the minimum tip value.

An instance of such a problem is presented next.

The input tree						The output tree

In a strict and purely functional setting, solving this problem would require a two traversal strategy: the first traversal would compute the original tree's minimum value, and the second traversal would replace all the tip values by the minimum value, therefore producing the desired result.

However, a two traversal strategy is not essential to solve the repmin problem. An alternative solution can, on a single traversal, compute the minimum tip value and, at the same time, replace all tip values by that minimum value.

Bird also showed a program transformation technique to derive circular programs from the straightforward strict, multiple traversal solutions.

The Haskell circular program that solves the repmin problem is presented next.

data R    = TWiki.RootProd Tree

data Tree = Tip  Int 
          | Fork Tree Tree

repmin (TWiki.RootProd t)   = replace
   where (replace,m)  = repmin_aux (t, m)
         
repmin_aux (Tip n,      minIn) = (replace, m)
   where replace          = Tip minIn
         m                = n
repmin_aux (Fork t1 t2, minIn) = (replace, m) 
   where replace          = Fork replace1 replace2
         m                = min  m1 m2
         (replace1, m1)   = repmin_aux (t1, minIn)
         (replace2, m2)   = repmin_aux (t2, minIn)

Notice that, on the above program's call:

         (replace,m)  = repmin_aux (t, m)

the variable

m

This type of circular definitions are directly executable on lazy languages only.

• Main.TWikiGuest - example@your.company

Web Changes Notification Service

Each TWiki web has an automatic e-mail notification service that sends you an e-mail with links to all of the topics modified since the last alert.

Users subscribe to email notifications using their TWiki.WikiName or an alternative email address, and can specify the webs/topics they wish to track using one of these bullet list formats:

three spaces * [ webname . ] wikiName - SMTP mail address
three spaces * [ webName . ] wikiName
three spaces * SMTP mail address
three spaces * SMTP mail address : topics
three spaces * [ webname . ] wikiName : topics

In the above examples, topics is a space-separated list of topic names. The user may further customize the specific content they will receive using the following formats:

• Specify topics without a Web. prefix
• Topics must exist in this web.
• Topics may be specified using * wildcards
• Each topic may optionally be preceded by a '+' or '-' sign. The '+' sign means "subscribe to this topic" (the same as not putting anything). The '-' sign means "unsubscribe" or "don't send notifications regarding this topic". This allows users to elect to filter out certain topics (and their children, to an arbitrary depth). Topic filters ('-') take precedence over topic includes ('+').
• Each topic may optionally be followed by an integer in parentheses, indicating the depth of the tree of children below that topic. Changes in all these children will be detected and reported along with changes to the topic itself. Note This uses the TWiki "Topic parent" feature.
• Each topic may optionally be immediately followed by an exclamation mark ! or a question mark ? with no intervening spaces, indicating that the topic (and children if there is a tree depth specifier as well) should be mailed out as complete topics instead of change summaries. ! causes the topic to be mailed every time even if there have been no changes, ? will mail the topic only if there have been changes to it. This only makes sense for subscriptions.

For example: Subscribe Daisy to all changes to topics in this web.

   * daisy.cutter@flowers.com

   * daisy.cutter@flowers.com: Web*

   * TWiki.DaisyCutter: Petal* (1) TWiki.WeedKillers (3) Pretty*Flowers

   * TWiki.StarTrekFan: Star* - *Wars - *sInTheirEyes - *shipTroopers

   * daisy@flowers.com: TWiki.NewsLetter?

   * buttercup@flowers.com: TWiki.NewsLetter! (1)

   * TWiki.GardenGroup: TWiki.AllNewsLetters? (3)
   * petunia@flowers.com: - TWiki.ManureNewsLetter

If a TWiki group is listed for notification, the group will be recursively expanded to the e-mail addresses of all members.

Tip: List names in alphabetical order to make it easier to find the names.

Note for System Administrators: Notification is supported by an add-on to the TWiki kernel called the MailerContrib. See the TWiki.MailerContrib topic for details of how to set up this service.

Note: If you prefer a news feed, point your reader to Personal/Joao.WebRss (for RSS 1.0 feeds) or Personal/Joao.WebAtom (for ATOM 1.0 feeds). Learn more at TWiki.WebRssBase and TWiki.WebAtomBase, respectively.

Related topics: TWiki.WebChangesAlert, Main.TWikiUsers, TWiki.TWikiRegistration

Warning

Can't INCLUDE TWiki.WebSearchAdvanced repeatedly, topic is already included.

Statistics for Personal/Joao Web

Notes:

• Do not edit this topic, it is updated automatically. (You can also force an update)
• TWiki.TWikiDocumentation tells you how to enable the automatic updates of the statistics.
• Suggestion: You could archive this topic once a year and delete the previous year's statistics from the table.