Firstify

This page relates to a transformation which takes a higher-order program, and a produces an equivalent first-order program. Unlike Reynolds style defunctionalisation, it does not introduce any new data types, and the results are more amenable to subsequent analysis operations. Our transformation is implemented, and works on a Core language to which Haskell programs can be reduced. Our method cannot always succeed in removing all functional values, but in practice is remarkably successful.

Downloads

• Released version
  • Bug tracker
• darcs get --partial http://community.haskell.org/~ndm/darcs/firstify
• Losing Functions without Gaining Data - from Haskell Symposium 2009 (abstract)(hide abstract)
  We describe a transformation which takes a higher-order program, and produces an equivalent first-order program. Unlike Reynolds-style defunctionalisation, it does not introduce any new data types, and the results are more amenable to subsequent analysis operations. We can use our method to improve the results of existing analysis operations, including strictness analysis, pattern-match safety and termination checking. Our transformation is implemented, and works on a Core language to which Haskell programs can be reduced. Our method cannot always succeed in removing all functional values, but in practice is remarkably successful.
  (bibtex)(hide bibtex)
  @inproceedings{mitchell:firstify_2009_9_3
      ,title          = {Losing Functions without Gaining Data}
      ,author         = {Neil Mitchell and Colin Runciman}
      ,year           = {2009}
      ,month          = {September}
      ,day            = {3}
      ,booktitle      = {Haskell '09: Proceedings of the second ACM SIGPLAN symposium on Haskell}
      ,location       = {Edinburgh, Scotland, UK}
      ,publisher      = {ACM}
      ,isbn           = {978-1-60558-508-6}
      ,url            = {\verb'http://community.haskell.org/~ndm/downloads/paper-losing_functions_without_gaining_data-03_sep_2009.pdf'}
  }
  
  • Losing Functions without Gaining Data - from Haskell Symposium 2009
  • Losing Functions without Gaining Data
• First Order Haskell - from BCTCS 2007 (bibtex)(hide bibtex)
  @misc{mitchell:firstify_2007_4_6
      ,title          = {First Order {Haskell}}
      ,author         = {Neil Mitchell}
      ,year           = {2007}
      ,month          = {April}
      ,day            = {6}
      ,note           = {Presentation from BCTCS 2007}
      ,url            = {\verb'http://community.haskell.org/~ndm/downloads/slides-first_order_haskell-06_apr_2007.pdf'}
  }
  

Tags: thesis