Memoirs of a PhD student

Program Slicing

2006-06-26T18:57:35+02:00

Now have slicing working over matches:

consider:

h :: Int -> (Int, Int)
h y = result 2
where
bob = 42
result x = res 3
res k = (23,24)
bill = 24
h x = (x, x+1)

this creates:

h1 y = result 2
where
res k = 23
result x = res 3
h1 x = x

h2 y = result 2
where
res k = 24
result x = res 3
h2 x = x + 1

Of course the question now is what does the slicer do for recursive definitions? such as splitAt?

Also the pretty printer has gon e abit dodgy in the at does not preserve the declaration order of the new matches... but this seems to type check.

Comments

Welcome Back!

2006-06-20T15:26:29+02:00

After a couple of months of being absent from my blog, I feel its a good time to start updating again. I also feel this is going to be a bit of a lengthy update. Quite a lot has happened in the last couple of months or so since I last updated.

I have:
-> Submitted papers to the postgrad (including poster) and Haskell Workshop conferences.
-> Ported HaRe to use the GHC type checker.
-> Implemented the splitting definitions refactoring.
-> Completed the add constructor to data type refactoring.
-> Done lots and lots of background reading.

I have just had my panel review today. Basically Olaf and Andy were pleased with the progress I had made since the last review. They said, although I had a slow first year things were really starting to move forward and I was starting to become very involved in the work. However, I need to look into fewer areas in more detail. Instead of chossing lots of refactorings to implement, it would be better to pick a specific one and concentrate on formalising and writting a prrof for it. In particular the program slicer.

Olaf commented that it would be a useful exercise to write up the work I had done on using Programatica and GHC-API. It would be a good idea to put the write up on my home page.

I need to make Huiqing's thesis my Gospel. In particular the section on the her theories of formalising refactorings.

In general I need to start writing up implementation and concentrate on just the program slicing. Working towards a formalisation and a proof. Perhaps neglect the merging stuff.

I also need to aim at getting 2 more publications done. Preferably, submitted before February next year.

I think I did OK, but I am left wondering whether what they said was positive or negative. I also regret my first year. But there is nothing I can do about that now. I am wondering whether I am going to finish within 3 years. I guess the challenge is to aim to do so.

Comments

GHC Typechecking

2006-03-31T17:34:01+02:00

I have written a simple program using the GHC API, which outputs the following for a simple module...

Fish.f [T] :: GHC.Num.Integer
[]
{ lit_auR = fromInteger 1
fromInteger = GHC.Num.fromInteger GHC.Num.Integer $dNum
lit_auQ = lit_auR
+ = (GHC.Num.+) GHC.Num.Integer $dNum
$dNum = $dNum
f = 1 + 1 }, $dNum = GHC.Num.$f3

That uses the pretty printer - so now I need to work out the data structure that GHC is using for its AST and then extract the information from it and map it into Programatica's AST.

Comments

GHC 6.5

2006-03-30T21:18:42+02:00

At last I have ghc 6.5 built, installed and working on my iBook. I finally got it to work by hacking it to bits so that ghc used its native assembler istead of the evil mangler and gcc. This means that the executable that ghc 6.5 produces won't be as optimised as usual, but I'm not that bothered about this. I have tested it with a simple program that uses the API to set up a small project and do some general printing out status stuff. I'll have a play tomorrow.

I'm annoyed that this, along with lots of marking this week has put me behind schedule on my research a few days. In the process however I have learned a lot about GHC - and I am guessing that the problem I am having with perl is not hardware but something to do with faulty locale information. Now I have ghc working and I know how to get around thisl its not too much of an issue any more. I'm just so pleased its finally working.

Now its time to leave the office and have the night off.

Comments

Update

2006-03-27T14:26:24+02:00

I havn't updated my blog for a few days - so I thought an update is in order.

Last week was a bit of a messy week research wise. I played around quite a bit with Template Haskell to discover that it is a really nice tool for source to source program transformations. I managed to write some simple refactorings using it in a few hours. I was surprised at how easy tree traversal is, I expected to write a lot of boilerplate code. The GHC AST is not multiple typed like the Programatica AST is, so I didn't need to use Strafunski.

Chris Ryder and I had a brief discussion about his work on porting HaRe to GHC, and it seems that a nice fix to get around the clumsy and slow type checker that Programatica provides by using the GHC type checker. This would require having a "Programatica land" and also a "GHC Land". Both "Lands" are kept in sync with the refactoring project and the GHC API is only called to get type information, and then the type information is mapped over the Programatica AST. A nice hack I would say. This means that HaRe would basically require GHC 6.5+ to be bolted onto the side, but I think that is a minor issue.

Using GHC in this way would allow for much faster type checking, and make my life easier. However its never simple. GHC has given me nothing but hassle on my Mac, and it has something to do with the evil mangler. Whenever I try to compile source code with the -fvia option set, non-deterministically the compiler fails. Interestingly, it always fails at the point of the evil mangler or the assembler. Something is not right with the system, and after endless reinstalls of Mac OS and memory tests that took all of the weekend I'm still no further forward. Wolfgang doesn't seem to know anything about this, and generally it seems I'm the only guy in the world that has seen this error. Perhaps it has something to do with 10.4... What I need is someone with an iBook G4 running Mac OS X 10.4 so they can check GHC for me.

Today I need to mark some Java assesments and then get my head down and do some research, the lastc few days have put me off course a bit.

Comments

TCS seminar and Template haskell

2006-03-21T18:41:45+01:00

Yesterday I gave my TCS seminar. I think it went alright, I got a nice discussion going and managed to answer all the questions. Olaf gave me some constructive feedback about some of the slides. I think next time I won't use LaTeX, its too cumbersome and awkward to get it the way you want. Next time I am just going to use keynote.

Been playing around with Template Haskell today and I have managed to write some simple transformations. I even implemented a simple "refactoring" to convert a data type into a newtype in about 5 or 6 lines of code. I need to think of an interesting example to give in my talk. I have read through "template meta programming for Haskell" by Peyton Jones and Sheard. Later I am going to read an interestig paper about using Template Haskell to create a simple Tetris game.

Comments

strange ghc behaviour

2006-03-16T13:38:29+01:00

I have been encountering some strange behaviour in ghc, but it now seems to be fixed thanks to Chris Ryder. Apparently, the latest GHC likes to use GCC 3.3, and I was using gcc 4.0.

Bizzarre - but it works. I thought it could be because I had bad RAM but after running an exhaustive test that took about 6 hours (ran all night) it passed.

Comments

Bug corrected - and ideas to expand TI API.

2006-03-14T22:35:00+01:00

Fixed the problem with the type checker adding in the extra parameter to functions that do not return Ints. I should put these in the tped API together with a collection of useful functions that would would with type information.

Comments

more bugs fixed and strange behaviour.

2006-03-14T18:34:51+01:00

I have corrected the problem I had last night, and now the refactoring will always try and place the pattern in the case expression. I think this is more suitable. Also this is strange and I can't work out why the type checker is doing this.

Suppose I have the function (without type information)

f (Con1 x) = 34

then the typechecker converts to something of the form...

f d9 (Con1 x) = 34

it puts an extra pattern in for some reason and it only does this if the function has no type signature and it returns an Int.

Comments

Refactoring with type information

2006-03-14T01:32:33+01:00

I have just finished the first version of my refactoring which uses type information to check which functions need pattern binding. This means you can have the declaration:

f :: New -> Int
f x = 45

and the refactoring will add

f :: New -> Int
f (Con2 x) = addedCon2
f x = 45

I have found something very fascinating:

ht (Con2 a b) = addedCon2
ht x
= case x of
(Con1 y) -> y
_ -> 44

In the above example the refactoring added the pattern at the top level declaration, because x is of type New. This is acceptable but I feel there is an alternative and that is to add in the case pattern. There are a nember of ways to deal with this:

1) always add to the top level
2) always add to the case pattern (but not the top level)
3) add to both the top level and the case patterns (belt and braces)

1 or 3 are the easiest to implement.

TODO: remove the hardcoded "New" data type!

Comments

Refactoring now works with typed AST. (Bugs fixed).

2006-03-13T13:05:29+01:00

This morning has been a very productive few hours. I consulted with Huiqing about why addDecl was putting the [ ] in, and it turns out it was because the pretty printer did not know how to print a list of TiDeclI PNT. This is now fixed - and I learned a whole lot about the pretty printer in the process. I also corrected another bug where the type checker always placed every Int expression in a fromInteger application. My refactoring now removes these leaving Int expressions the same as they were before the refactoring took place.

This afternoon I need to catch up on my Haskell marking and I am also going to implement the next step of my refactoring: to select functions which have an argument of the type in question using type information.

Comments

TI API

2006-03-10T17:20:26+01:00

Thte last 2 days has been very hectic. Yesterday I came to port my add constructor refactorinng over to use the TI AST instead, and then realised (with horror) that the API only worked over the normal AST.

I then had to create an API which worked over the TI AST, by creating new type synonyms for the TI Exp, Pat and Decls constructors. I then had to copy the AST into a new file RefacTypeUtils and modify it work with the new constructors. This also require modification to refacLocUtils (also copied over to refacTILocUtils).

After all that and more modifications to the TI API to get my refactoring to work I have found something very interesting. Wherever in the program there is an expression of type Int the type checker wraps up the expression in an application of fromInteger expression. And when the API writes the refactored output to the file - lo and behold it also puts this application in its place.

At the moment I can think of some ways to deal with this:

1. Leave it as it is - it doesn't alter the behaviour, the type checker only puts it in to resolve types;
2. Map the normal AST onto the TI AST preserving TI information (therefore removing these from integer applications)
3. Traverse the TI AST to find where ever there is an INT expression and remove the application.

THis is a pain, I have also found another strange perculiarity: My refactoring adds a declaration, and now it adds the declaration with [ ] around it. This must be do with the new TI API playing up over the constructors.

Intriging. I was hoping to have a version of my refactoring completed today which uses type information, but with porting the API and fixing about a million bugs in the port its put me behind schedule.

Comments

An API over the TI?

2006-03-08T14:40:34+01:00

I spent most of yesterday playing around with the TI AST. Manily getting my head around some of the subtle differences it has with the normal AST. There is not huge amounts of difference...

In general most things are the same except of identifiers which are decorated with type information. Yesterday I wrote a number of traversals to try and get used to traversing the TI AST. In general i created a simple traversal which asks you for a type - and then finds all expression that match that type. I noticed some interesting things:

All Ints are wrapped up in a fromInteger application;
Some times the type information is wrapped up in a scheme (which also includes any contexts and constraints). I'm still testing the consistency of this.

Today I almost died when I copied my refacAddCon file over to the version of the release I have where the type checker doesn't work. It was because I also modified refacUtils - and forgot to copy that over as well

I also realised something quite important. The API is currently defined over the AST and not over the TI AST. I can't see any major problems apart from creating another refacTypeSyn file which creates synonyms for the TI types. And the importing this file when the TI API is needed. I am also freting about the fact that the API might complain about ambigous occurences of Exp (there is one in TiDecorate and one in SyntaxRec). Hopefully I can get a new version of my refactoring working which will look at patterns which are of the type in Question. Ie.

f :: NewData -> Int
f x = 45

without just looking to see if any of the constructors are referenced in the pattern binding. Claus mentioned something interesting about using TH instead of DrIFT to create the instances. An intersting project, something I might have looked into if I had the time. But my concentration is on my research at the moment.

Its so long since I've listened to Chopin....it just melts in your ears.

Comments

DrIFT now works over TI

2006-03-06T22:27:00+01:00

I have had a productive couple of days. Firstly I checked the first version of my refactoring, but more importantly I got DrIFT to work. Well, when I say I got it to work - I manually created the instances that Strafunski needed for the TI myself. It took a while todo - All of Saturday and most of today. It seems to work and I have created a simple test using strafunski to return all expressions on the program that have the type "Int".

This means that I can now start to incorporate type checking into my refactoring, -somithng that I have been wanting to do for a while. I have learned so much this weekend, I have learned what the instances mean in the DriftStructUtils file, and also the structure of the TI AST.

Comments

quickCheck' -- by induction?

2006-03-03T13:38:16+01:00

Last night on the train I had a very productive few hours of work. I managed to implement support for records, and infix contructors, learning lots about the Haskell type system and Programatica's type system in the process. Today I need to test my implementations to make sure there are no bugs. I also need to look for the "as a" contruct:

x@(Con1 x x) = ... x ...

Also I have been thinking about the talk Colin Runciman gave and also Haskell quick check. By my knowledge Haskell quick check uses a speciification that program must satisfy and then quick check tests that the properties hold in a large number of random test cases.

What would be better would be to use induction and proofs by equivelence.

Suppose we have an arbitrary function f...

f 0 = 1
f n = n * f (n-1)

Now, I want to prove that f will calculate the factorial of n. I can prove this by using induction. But what about creating a program that uses induction to prove the equality? This builds on Colin's talk - these arn't regular expressions, but its the same principle.

I think this will be really interesting to look into - however I realise that the work on refactoring takes top priority but I may give this some thought.

Comments

Infix and Records

2006-03-01T20:35:28+01:00

I was in the process of testing my refactoring today and I came to a few conclusions:

I still need to implement cases for parsing infix contructors and also constructors which use records.

Also w.r.t to naming identifiers on the LHS, I think it is a very difficult job. Not only will it be hard to work out the consistency (if there is any) oy naming for types - what happens in cases where the rcefactoring cannot infer a name? I think it is satisfactory to have an _ in place of a variable name, afterall the RHS simply calls a function which returns an error anyway so its not a huge problem.

The main reason I am thinking about this is because creating an algoritim to match naming consistencies is not an easy task. It will take time - and that time at the moment can be better spent on other things. Such as completing the refactoring etc...

Here is a list of things to do:
Implement functionality to deal with infiix expressions and records;
test refactoring and check into darcs;
get DrIFT working;
complete add constructor refactoring;
complete work on program slicing;
Continue reading Backhouse's book on program construction;
make a start on types and programming languages;

Also, Colin's talk yesterday has given me some inspiration for an idea. How about a program which uses induction to check whether a Haskell definition is correct or not? I thought it could be interesting. I know there is quickCheck, but I am not sure how it is implemented.

Comments

Progress on my refactoring

2006-02-27T19:43:59+01:00

I have just made 2 new changes to my refactoring.

Now the user selects the constructor and the refactoring places the new constructor AFTER the selectded constructor. The refactoring places a space in between the new constructor and the "|" character.

Tonight I will add functionality to automatically create a function (that returns an error) and the new patterns will refer to that function.

Comments

Web pages, darcs and refactorings.

2006-02-25T18:47:02+01:00

Today I have set up a darcs repository for HaRe. This means you can use darcs to get the repository from the Internet:

darcs get http://www.cs.kent.ac.uk/projects/refactor-fp/release

I have also been making good progress on my refactoring, and I hope to be able to demo a promising start to Simon on monday. I have also had a think about pattern bindings:

Suppose we have a pattern binding:

(Con1) = 45

Then in my opinion, the refactoring cannot infer other pattern binding automatically - how does the refactoring know that it was the users intention to create pattern bindings for the new constructor. I think it is sensible to only check for patterns within function bindings and case expressions.

Claus made a good point today about trying to get a paper published, and I noticed this on the Haskell irc:

http://haskell.org/haskell-workshop/2006/

Perhaps I could try to publish a paper to that. Today I have also been updating the project website. I wanted to read another chapter of types and programming languages but setting up darcs took longer than I expected. I realised that the webpages directory is on a different server, so I couldn't just create a link to the repository - instead I have made a syncdarcs script which you run when you commit something, and the directories are synced.

Comments

Welcome to my Blog!

2005-10-31T13:25:21+01:00

After seeing a blog created by Malcome Wallace - I thought it would be a good idea to set up my own. After all - they seem to be the new fashion. This blog will be used as my own personal diary of my work - I will write down my thoughts, problems and progress about my PhD work here.

Comments