Homework

ProgrammingEnvironments
---+++ November 22

Write a Java program that displays a tree structure. It should be possible to select individual nodes; when a node is selected, its name is displayed in a label. Make use of =org.eclipse.swt.widgets.Tree= and =org.eclipse.swt.widgets.Label=.

---+++ November 24

Explain the key differences between Proxima and Eclipse in about 20 lines of text.

---+++ November 29 (extended to December 6)

Discuss the concept of dynamic programming, with special reference to whitespace distribution.

We discuss a sequence of instances of nfib.

---+++++ Recursive definition
Verify for yourself why the following function is extremely expensive.
<verbatim>
nfib 1 = 1
nfib 2 = 1
nfib n = nfib (n-1) + nfib (n-2)
</verbatim>

---+++++ Memoisation
The Haskell libraries contain a [[file:///Applications/Glasgow%20Haskell%20Compiler%206.4.1/Documentation/hslibs/memo-library.html][function]]:
<verbatim>
memo :: (a -> b) -> a -> b
</verbatim>
which suggests that it can be used to overcome the problem of rescusrive calls with the same argument.

Unfortunately, as the documentation explains, the function however does not work for integers, but essentially depends on pointer equality.

---+++++ Memoisation II
Using an array we can build our own memo function. We make now explicitly use of the fact that we know beforehand with which arguments the function will be called!
<verbatim>
fib n = let index = (1,n)
            fibs  = index -> [(i,if i < 3 then 1 else fibs!(n-1) + (fibs!(n-2) )| i <- index]
        in fibs ! n
</verbatim>
---++++ Scheduling the computation
A little bit of reflection reveals that once we have constructed the value ot fib!i, we may forget the value at fib!j, where j < i-1, assuming of course that we are ultimately only interested in fib n. So we convert the demand driven algorithm (which is typical for  such recurrent relations) into a data driven algorithm, in which we carefully organise the storage needed for memoising what we still need, and schedule the computation accordingly:
<verbatim>
fib n = if n < 3 then 1
        else loop (n-2) 1 1
        where loop 0 prev last = last
              loop n prev last = loop (n-1) last (prev+last)
</verbatim>
---+++++ Dynamic programming.
Typical dynamic programming algorithms:
   * are based on some recurrent relation
   * which can be analysed for its recurring patterns
   * leading to an explicit scheduling of the computation and use of memory

The recurrence relation in quite a few occasions occurs in some  some optimisation problem, in which we memoize "best" solutions for subproblems.
---+++++ Optimal Line Breaking
In !TeX the algorithm that is used to split a paragraph into lines, is based on _dynamic programming_, in which we memoise *optimal solution for subproblems* of the original problem..

When looking for the paper describing the paragraph formatting problem, I stumbled upon:

   * [[http://doi.acm.org/10.1145/872730.806462][Achugbue, J. O. 1981. On the line breaking problem in text formatting. In Proceedings of the ACM SIGPLAN SIGOA Symposium on Text Manipulation (Portland, Oregon, United States, June 08 - 10, 1981)., 117-122.]] , which makes also interesting reading to see what the state of the art was back in 1981. 
   * [[http://oedipus.sourceforge.net/texlib/]]
   * DE Knuth and MF Plass. Breaking paragraphs into lines. Software: Practice andExperience, 11:1119-1184, 1981.

For the assignment, in which you explain in your own words how this process takes place,  you may want to provide an implementation of the formatting algorithm in Haskell (probably documenting it with lhs2TeX).          


---+++ December 1

Use the PDE to create a simple plugin for Eclipse. Package it into a zip file ready for installation in the plugins directory.

---+++ December 13

In the paper "Notes on the Eclipse Plug-in Architecture" the file
=plugins/org.eclipse.platform.source_2.1.0/src/org.eclipse.ui_2.1.0/schema/actionSets.exsd= is referenced.
   a. In Eclipse 3.1.*, the corresponding file is in a different directory. Where is it now?
   a. How does the file differ from the one in the paper? List the differences and explain their purpose.
   a. Explain how to open this file with Eclipse's Extension Point Schema Editor.

---+++ December 20

Modify the presentation sheet (=HeliumEditor/PresentationAG.ag=) of the Helium editor in such a way that the background color of an expression represents the nesting depth of that expression. Use color (255,255,255) for a depth of 0, color (223,223,223) for a depth of 1, color (191,191,191) for depth 2, etc. Here's an example:

<span style="font-family: courier">haakjes = 1^(<span style="background-color: #dfdfdf">(<span style="background-color: #bfbfbf">(<span style="background-color: #9f9f9f">2+3</span>)</span>)*4</span>)</span>

To make the assignment a bit easier, I've put a slightly modified version of the presentation sheet in SVN, so make sure you do an update on =HeliumEditor/PresentationAG.ag=.

*HINTS*
   * The file =HeliumEditor/DocumentType.hs= contains the document type definition for the Helium editor.
   * You need to declare an attribute that represents the nesting depth. In order to handle the attribution over the generated parts of lists of expressions and list of alternatives (=[Exp]= and =[Alt]=), add the following declarations:

<pre>
ATTR List_Exp     [ depth : Int | | ]
ATTR ConsList_Exp [ depth : Int | | ]
ATTR List_Alt     [ depth : Int | | ]
ATTR ConsList_Alt [ depth : Int | | ]
</pre>

   * No =SEM= rules need to be specified for the depth attributes on these list data structures since the attribution is entirely handled by copy rules. You can have a look at =PresentationAG_Generated= to see the exact AG datastructures that are generated for =[Exp]= and =[Alt]=.

---+++January 12

Write an Eclipse plugin containing a variation on the =Word View= that, given a string, displays its [[http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Suffix/][suffix tree]].

---+++ January 17

Write an Eclipse plugin that provides an editor for *.wiki files. Syntax coloring should make the delimiters '|' red, boldface items (surrounded by '*') green, italic items (surrounded by '_') orange, monospaced items (surrounded by '=') purple, and hyperlinks (surrounded by double brackets) blue.

Autocompletion should function when a line is started with '---' and should offer the possibility to add one through six '+' signs. It should also function when a line is started with three spaces, and should then offer the possibility to add a '*' or '1' or 'A' or 'i' or '$'.