WebHome
- Education Page?
- Description?
- Literature?
- Schedule?
- Assignments?

Center
Master Program
Arjan Oosting

Uhc
-- Main.ArjanOosting - 09 Sep 2003

---++ General Reading Material
---+++Read:
   * "A Static Semantics for Haskell", [[http://www.it.kth.se/~kff/publications.html][Karl Filip Faxén]], \
[[http://titles.cambridge.org/journals/journal_toc.asp?mnemonic=JFP&vol=12&issue=5][Journal of Functional Programming Vol 12, Issue 5.]], \
or through the home page of the author in [[http://www.it.kth.se/~kff/semantics.ps.gz][compressed postscript]]
   * [[http://research.microsoft.com/Users/simonpj/][Simon Peyton Jones]] and [[http://www.cse.ogi.edu/~mbs/][Mark Shields]]. [[http://research.microsoft.com/Users/simonpj/papers/putting/index.htm][Practical type inference for arbitrary-rank types]]
   * Benedict R. and Jones, Mark P., [[http://citeseer.nj.nec.com/gaster96polymorphic.html][A Polymorphic Type System for Extensible Records and Variants]], No. NOTTCS-TR-96-3, Nov 1996. 

---+++Working on:
   * Diatchki, Iavor S., Jones, Mark P. and Hallgren, Thomas, [[http://www.cse.ogi.edu/~diatchki/hsmod/Description.pdf][A Formal Specification of the Haskell 98 Module System]], Haskell Workshop, 2002, pp. 17-29.
   * Mark Shields and Simon Peyton Jones. [[http://www.cse.ogi.edu/~mbs/pub/first_class_modules/][First-class Modules for Haskell]]. Ninth International Conference on Foundations of Object-Oriented Languages (FOOL 9), Portland, Oregon, Dec 2001.

---++ Generics in UHC 
The goal of this project is to look at different possibilities to support generic programming extensions in Haskell and determine how these (easily) could be implemented in UHC. For more info on Generic Haskell go to http://www.generic-haskell.org/ 

---+++ Reviews

   * *Derivable Typeclasses*: This paper is quite easy to read and gives an nice introduction into generic programming. It present a nice solution to fit generic functions into Haskell. Furthurmore it describes an elegant replacement for the _deriving_ construct and points out a shortcoming of the type system with respect to context declarations. I think the way in which generic functions are implemented in this paper is quite intuitive and is quite easy to use, even for functional programmers without a lot of experience. This solution can be implemented with a source to source translation, and some little changes to the UHC. A problem with this solution is that you only can define a generic method for type classes and not for constructor classes and you only can define your generic functions on types of kind star. So you can't write a generic map function and use it like we can use it in Generic Haskell (see code for Generic Haskell below): 
<verbatim>
type Map{| * |} t1 t2 = t1 -> t2
type Map{| k -> l |} t1 t2 = forall a1 a2. Map {| k |} a1 a2 -> Map {| l |} (t1 a1) (t2 a2)

map{| t :: k |} :: Map {| k |} t t
map{| Unit |} Unit = Unit
map{| :+: |} mapa mapb (Inl a) = Inl (mapa a)
map{| :+: |} mapa mapb (Inr b) = Inr (mapb b)
map{| :*: |} mapa mapb (a :*: b) = mapa a :*: mapb b 

> map{| List |} toUpper "hello world"
  HELLO WORLD
</verbatim> 
   
   * *A New Approach to Generic Functional Programming*: This paper is relatively old and not that easy to read. (It came on the litature list by mistake, it should have been _A Lightweight Implementation of Generics and Dynamics_).   
   
   * *A Lightweight Implementation of Generics and Dynamics*: This paper shows us an implementation of generics which need only a few extensions to the compiler. It uses an datatype =Rep= with represents the type of a value. This datatype is used to give the type of the argument of an generic function. This datatype =Rep= is also used to implement an dynamic value, that is a value with runtime annotion of it's type. These dynamic values can be _cast_ to the specific type at runtime. Through the use of embedding-projection pairs inside the =Rep= datatype problems due to the _parametricity theorem_ can circumvented. _More to come...._
   
   * *A Generic Programming Extension for Clean*: This paper describes an extended implementation of derivable type classes in [[http://www.cs.kun.nl/~clean/][Clean]]. One of the problems of the original Derivable Type classes design is the fact that it only works for type classes with type variables ranging over types of kind *. The design used in this paper uses kind-indexed type classes which make it possible to use type classes with type variables ranging over all kinds.

   * *Generic Haskell, Specifically*: This paper introduces some extensions to the original Generic Haskell design.  These extensions are _copy lines_, _constructor cases_ and _generic abstraction_. Furthurmore the paper explains  some of the pro and cons of the MPC style which is used in Generic Haskell and the POPL style used in the derivable type classes in GHC.   
   
   * *Polytypic values possess polykinded types*: This papers explains the theory behind Generic Haskell. One of the main points in the paper is the fact that when we have a value _v_ which depends on type _t_, the type of the value _v_ depends on the kind of the type _t_.  The paper also shows how polytypic values can be represented in simple typed lambda calculus and how specialisation of polytypic values can be modelled in the simply typed lambda calculus.   

   * *Dependency-style Generic Haskell*: In this paper a big problem in Generic Haskell is solved. In Classic Generic Haskell it isn't easy to define generic function which depend on other generic functions. If you want to do this use have to define ALL the dependent functions on the same time in a tuple. This is rather cumbersome and you want the compiler to take care of the dependencies. The problem here is that Generic Haskell uses the MPC style and inside the function you don't have access to type to which the function is specialized to. In the POPL style used in derivable type classes, the type information is available. The author tries to get the best of both worlds.

 
---+++ Pro and Cons of different styles
   | *Property* | *Derivable Type Classes (POPL)* | *Generic Haskell (MPC)* | *Dependency-style Generic Haskell* |
   | dependent generic functions     |  YES  |  NO    |  YES  |    
   | one set of structure types      |  NO   |  YES   |  YES  |    
   | functions have polykinded types |  NO   |  YES   |       |    
   | copy lines                      |  NO   |  YES   |  YES  |    
   | constructor cases               |       |  YES   |  YES  |    
   | generic abstraction             |       |  YES   |  YES  |    
    
---+++ Examples
 GenericsExamples
---+++ Litature List:

   * [[http://www.informatik.uni-bonn.de/~ralf/][Ralf Hinze]] and [[http://www.cs.uu.nl/people/johanj/][Johan Jeuring]]. *[[http://www.cs.uu.nl/~johanj/publications/GH.pdf"][Generic Haskell: Practice and Theory]]*. To appear in the lecture notes of the Summer School on Generic Programming,  LNCS  &copy; Springer-Verlag, 2003.
   * [[http://www.informatik.uni-bonn.de/~ralf/][Ralf Hinze]] and [[http://www.cs.uu.nl/people/johanj/][Johan Jeuring]]. *[[http://www.cs.uu.nl/~johanj/publications/ghpractice.pdf"][Generic Haskell: Applications]]*. To appear in the lecture notes of the Summer School on Generic Programming,  LNCS  &copy; Springer-Verlag, 2003.
   * [[http://www.informatik.uni-bonn.de/~ralf/][Ralf Hinze]]. *Polytypic values possess polykinded types*. In Roland Backhouse, J.N. Oliveira, editors, Proceedings of the Fifth International Conference on Mathematics of Program Construction (MPC 2000), Ponte de Lima, Portugal, July 3-5, 2000, &copy; Springer-Verlag. This paper is a revised version of the report: [[http://www.informatik.uni-bonn.de/~ralf/MPC2000.ps.gz][gzipped postscript]].
   * [[http://www.informatik.uni-bonn.de/~ralf/][Ralf Hinze]] and [[http://research.microsoft.com/Users/simonpj/][Simon Peyton Jones]]. *Derivable Type Classes*. In Graham Hutton, editor. Proceedings of the 2000 ACM SIGPLAN Haskell Workshop, Montreal, Canada, September 17, 2000. Volume 41.1 of [[Electronic Notes in Theoretical][http://math.tulane.edu/~entcs/]] Computer Science, Elsevier Science, August 2001. (preliminary version: 89K [[http://www.informatik.uni-bonn.de/~ralf/publications/HW00.ps.gz][gzipped postscript]], final version: 119K [[http://www.informatik.uni-bonn.de/~ralf/publications/Derive.ps.gz][gzipped postscript]])
   * [[http://www.cs.cornell.edu/people/jcheney/][James Cheney]] and [[http://www.informatik.uni-bonn.de/~ralf/][Ralf Hinze]]. *A Lightweight Implementation of Generics and Dynamics*. In Manuel Chakravarty, editor, Proceedings of the ACM SIGPLAN 2002 Haskell Workshop, Pittsburgh, PA, USA, October 3, 2002, pp 90-104. ([[http://www.informatik.uni-bonn.de/~ralf/publications/HW02.pdf][PDF]], [[http://www.informatik.uni-bonn.de/~ralf/publications/HW02.ps.gz][gzipped postscript]])
   * [[http://www.informatik.uni-bonn.de/~ralf/][Ralf Hinze]]. *A New Approach to Generic Functional Programming*. In Proceedings of the 27th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Boston, Massachusetts, January 19-21, 2000. [[http://info.acm.org/pubs/toc/CRnotice.html">][&copy;Copyright 2000 by ACM, Inc.]] <strong>NB.</strong> This paper is a revised version of the report: [[http://www.informatik.uni-bonn.de/~ralf/POPL2000.ps.gz][gzipped postscript]], the copy is posted by permission of ACM and may not be redistributed.
   * [[http://www.cs.uu.nl/people/andres/][Andres Löh]], [[http://www.cs.uu.nl/people/dave/][Dave Clarke]] and [[http://www.cs.uu.nl/people/johanj/][Johan Jeuring]]. *[[http://www.cs.uu.nl/~johanj/publications/GHTypeSystem.pdf][Dependency-style Generic Haskell]]*. Accepted at ICFP 2003.
   * [[http://www.cs.uu.nl/people/dave/][Dave Clarke]] and [[http://www.cs.uu.nl/people/andres/][Andres Löh]]. *[[http://www.cs.uu.nl/~andres/GHExtensions.pdf][Generic Haskell, Specifically]]*. In Jeremy Gibbons and Johan Jeuring, editors. Generic Programming. Proceedings of the IFIP TC2 Working Conference on Generic Programming, Schloss Dagstuhl, July 2002. ISBN 1-4020-7374-7. Kluwer Academic Publishers, pages 21 - 48, 2003.
   * Arten Alimarine and [[http://www.cs.kun.nl/~rinus/][Rinus Plasmeijer]. *[[ftp://ftp.cs.kun.nl/pub/Clean/papers/2001/alim2001-GenericClean.ps.gz][A Generic Programmic Extension for Clean]]*. In: Arts, Th., Mohnen, M. eds. Proceedings of the 13th International workshop on the Implementation of Functional Languages, IFL'01, Älvsjö, Sweden, September 24-26, 2001, Ericsson Computer Science Laboratory, pp.257-278. [[ftp://ftp.cs.kun.nl/pub/Clean/papers/2001/alim2001-GenericClean.pdf][pdf]], [[ftp://ftp.cs.kun.nl/pub/Clean/papers/2001/GenericCleanIFL01.ppt][powerpoint presentation]].
   * [[http://flint.cs.yale.edu/trifonov/][Valery Trifonov]]. *Simulating Quantified Class Constraints*. [[http://flint.cs.yale.edu/trifonov/papers/sqcc.ps.gz][ps.gz]] [[http://flint.cs.yale.edu/trifonov/papers/sqcc.pdf][pdf]] &copy;2003 [[http://www.acm.org][ACM]] [[http://www.cs.uu.nl/~johanj/HaskellWorkshop/cfp03.html][Proc. ACM SIGPLAN 2003 Haskell Workshop]], pp. 98-102.
   * [[http://www.math.chalmers.se/~ulfn/][Ulf Norell]]. *Functional Generic Programming and Type Theory* [[http://www.math.chalmers.se/~ulfn/papers/thesis.dvi][dvi]] [[http://www.math.chalmers.se/~ulfn/papers/thesis.ps][ps]]
   * Wolfram Kahl and Jan Scheffczyk. *[[http://www.cs.uu.nl/people/ralf/hw2001/4.html][Named Instances for Haskell Type Classes]]* Haskell Workshop 2001
   * More on [[http://www2-data.informatik.UniBw-Muenchen.DE/Haskell/NamedInstances/thesis/][named instances]].

---+++ Disclaimer
Material on this page is shamelessly copied from other websites, including but not limited to http://www.generic-haskell.org and [[Master.Implemenation Of UHC][Implementation Of UHC]].
   * [[%ATTACHURL%/presentation.pdf][presentation.pdf]]: Final presentation
Topic attachments
I	Attachment	Action	Size	Date	Who	Comment
pdf	presentation.pdf	manage	533.6 K	12 Nov 2003 - 14:40	ArjanOosting	Final presentation