- Deriving Generic Functions by Example - from York Doctoral Symposium 2007 (Derive) (abstract)(hide abstract)
A function is said to be generic if it operates over values of
any data type. For example, a generic equality function can test pairs of
booleans, integers, lists, trees etc. In most languages programmers must
define generic functions multiple times, specialised for each data type.
Alternatively, a tool could be used to specify the relationship between the
data type and the implementation, but this relationship may be complex.
This paper describes a solution: given a single example of the generic
function on one data type, we can infer the relationship between a data
type and the implementation. We have used our method in the Derive
tool, allowing the implementation of 60% of the generic functions to be
inferred.
(bibtex)(hide bibtex)@inproceedings{mitchell:derive_2007_10_26
,title = "Deriving Generic Functions by Example"
,author = "Neil Mitchell"
,year = "2007"
,month = "October"
,day = "26"
,pages = "55--62
,publisher = "Tech. Report YCS-2007-421, Dept. of Computer Science, University of York, UK"
,editor = "Jan Tobias M\"{u}hlberg and Juan Ignacio Perna"
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/paper-deriving_generic_functions_by_example-26_oct_2007.pdf'"
}
- Uniform Boilerplate and List Processing - from Haskell Workshop 2007 (Uniplate) (abstract)(hide abstract)
Generic traversals over recursive data structures are often referred
to as boilerplate code. The definitions of functions involving such
traversals may repeat very similar patterns, but with variations for
different data types and different functionality. Libraries of operations
abstracting away boilerplate code typically rely on elaborate
types to make operations generic. The motivating observation for
this paper is that most traversals have value-specific behaviour for
just one type. We present the design of a new library exploiting
this assumption. Our library allows concise expression of traversals
with competitive performance.
(bibtex)(hide bibtex)@inproceedings{mitchell:uniplate_2007_9_30
,title = "Uniform Boilerplate and List Processing"
,author = "Neil Mitchell and Colin Runciman"
,year = "2007"
,month = "September"
,day = "30"
,booktitle = "Haskell '07: Proceedings of the ACM SIGPLAN workshop on Haskell workshop"
,pages = "49--60
,location = "Freiburg, Germany"
,doi = "http://doi.acm.org/10.1145/1291201.1291208"
,publisher = "ACM"
,isbn = "978-1-59593-674-5"
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/paper-uniform_boilerplate_and_list_processing-30_sep_2007.pdf'"
}
- Supero: Making Haskell Faster - from IFL 2007 (Supero) (abstract)(hide abstract)
Haskell is a functional language, with features such as higher
order functions and lazy evaluation, which allow succinct programs. These
high-level features are difficult for fast execution, but GHC is a mature
and widely used optimising compiler. This paper presents a whole-program
approach to optimisation, which produces speed improvements
of between 10% and 60% when used with GHC, on eight benchmarks.
(bibtex)(hide bibtex)@inproceedings{mitchell:supero_2007_9_27
,title = "Supero: Making {Haskell} Faster"
,author = "Neil Mitchell and Colin Runciman"
,year = "2007"
,month = "September"
,day = "27"
,booktitle = "IFL 2007: Draft Proceedings of the 19th International Symposium on Implementation and Application of Functional Languages"
,location = "Freiburg, Germany"
,publisher = "Tech. Report No. 12-07 of the Computing Laboratory, University of Kent, UK"
,editor = "Olaf Chitil"
,pages = "334--349
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/paper-supero_making_haskell_faster-27_sep_2007.pdf'"
}
- Yhc.Core - from Haskell to Core - from The Monad.Reader (Yhc) (abstract)(hide abstract)
The Yhc compiler is a hot-bed of new and interesting ideas. We present Yhc.Core
- one of the most popular libraries from Yhc. We describe what we think makes
Yhc.Core special, and how people have used it in various projects including an
evaluator, and a Javascript code generator.
(bibtex)(hide bibtex)@article{mitchell:yhc_2007_4_30
,title = "{Yhc.Core} - from {Haskell} to Core"
,author = "Dimitry Golubovsky and Neil Mitchell and Matthew Naylor"
,year = "2007"
,month = "April"
,day = "30"
,journal = "The Monad.Reader"
,number = "7"
,pages = "45--61
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/paper-yhc_core-30_apr_2007.pdf'"
}
- A Static Checker for Safe Pattern Matching in Haskell - from TFP 2005 post proceedings (Catch) (abstract)(hide abstract)
A Haskell program may fail at runtime with a pattern-match error if
the program has any incomplete (non-exhaustive) patterns in definitions or case
alternatives. This paper describes a static checker that allows non-exhaustive patterns
to exist, yet ensures that a pattern-match error does not occur. It describes a
constraint language that can be used to reason about pattern matches, along with
mechanisms to propagate these constraints between program components.
(bibtex)(hide bibtex)@inproceedings{mitchell:catch_2007_2_1
,title = "A Static Checker for Safe Pattern Matching in {Haskell}"
,author = "Neil Mitchell and Colin Runciman"
,year = "2007"
,month = "February"
,day = "1"
,publisher = "Intellect"
,booktitle = "Trends in Functional Programming"
,volume = "6"
,isbn = "978-1-84150-176-5"
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/paper-a_static_checker_for_safe_pattern_matching_in_haskell-01_feb_2007.pdf'"
}
- Visual Hat (Hat) (abstract)(hide abstract)
This paper describes a new approach to visualizing
the data contained in Hat traces. The aim is to cater for Windows
users who are more familiar with graphical debugging tools.
(bibtex)(hide bibtex)@inproceedings{mitchell:hat_2005_10_28
,title = "Visual {Hat}"
,author = "Neil Mitchell"
,year = "2005"
,month = "October"
,day = "28"
,booktitle = "Hat Day 2005: work in progress on the Hat tracing system for Haskell"
,pages = "23--26
,publisher = "Tech. Report YCS-2005-395, Dept. of Computer Science, University of York, UK"
,editor = "Colin Runciman"
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/paper-hatday-28_oct_2005.pdf'"
}
- Unfailing Haskell: A Static Checker for Pattern Matching - from TFP 2005 (Catch) (abstract)(hide abstract)
A Haskell program may fail at runtime with a pattern-match error if the program has
any incomplete (non-exhaustive) patterns in definitions or case alternatives. This paper
describes a static checker that allows non-exhaustive patterns to exist, yet ensures
that a pattern-match error does not occur. It describes a constraint language that can
be used to reason about pattern matches, along with mechanisms to propagate these
constraints between program components.
(bibtex)(hide bibtex)@inproceedings{mitchell:catch_2005_9_24
,title = "Unfailing {Haskell}: A Static Checker for Pattern Matching"
,author = "Neil Mitchell and Colin Runciman"
,year = "2005"
,month = "September"
,day = "24"
,booktitle = "Proceedings of the Sixth Symposium on Trends in Functional Programming"
,pages = "313--328
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/paper-unfailing_haskell_a_static_checker_for_pattern_matching-24_sep_2005.pdf'"
}
- Qualifying Dissertation: Unfailing Haskell (Thesis) (abstract)(hide abstract)
Programs written in Haskell may fail at runtime with either a
pattern match error, or with non-termination. Both of these can be
thought of as giving the value _|_ as a result. Other forms of
failure, for example heap exhaustion, are not considered.
The first section of this document reviews previous work, including
total functional programming and sized types. Attention is paid to
termination checkers for both Prolog and various functional
languages.
The main result from work so far is a static checker for pattern
match errors that allows non-exhaustive patterns to exist, yet
ensures that a pattern match error does not occur. It includes a
constraint language that can be used to reason about pattern
matches, along with mechanisms to propagate these constraints
between program components.
The proposal deals with future work to be done. It gives an
approximate timetable for the design and implementation of a static
checker for termination and pattern match errors.
(bibtex)(hide bibtex)@misc{mitchell:thesis_2005_6_30
,title = "Qualifying Dissertation: Unfailing {Haskell}"
,author = "Neil Mitchell"
,year = "2005"
,month = "June"
,day = "30"
,institution = "University of York"
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/paper-qualifying_dissertation-30_jun_2005.pdf'"
}
- Not All Patterns, But Enough - an automatic verifier for partial but sufficient pattern matching - submitted to ICFP 2008 (Catch) (abstract)(hide abstract)
We describe an automated analysis of Haskell 98 programs to
check statically that, despite the possible use of partial (or nonexhaustive)
pattern matching, no pattern-match failure can occur.
Our method is an iterative backward analysis using a novel form
of pattern-constraint to represent sets of data values. The analysis
is defined for a core first-order language to which Haskell 98
programs are reduced. Our analysis tool has been successfully
applied to a range of programs, and our techniques seem to scale
well. Throughout the paper, methods are represented much as we
have implemented them in practice, again in Haskell.
(bibtex)(hide bibtex)@unpublished{mitchell:catch_2008_4_2
,title = "Not All Patterns, But Enough - an automatic verifier for partial but sufficient pattern matching"
,author = "Neil Mitchell and Colin Runciman"
,year = "2008"
,month = "April"
,day = "2"
,note = "Draft, submitted to ICFP 2008"
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/draft-catch-02_apr_2008.pdf'"
}
- Losing Functions without Gaining Data - a new method for defunctionalisation - submitted to ICFP 2008 (Firstify) (abstract)(hide abstract)
We describe an automated transformation which takes a higherorder
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 it is remarkably successful.
(bibtex)(hide bibtex)@unpublished{mitchell:firstify_2008_4_2
,title = "Losing Functions without Gaining Data - a new method for defunctionalisation"
,author = "Neil Mitchell and Colin Runciman"
,year = "2008"
,month = "April"
,day = "2"
,note = "Draft, submitted to ICFP 2008"
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/draft-firstify-02_apr_2008.pdf'"
}
- A Supercompile for Core Haskell - submitted to the post proceedings of IFL 2007 (Supero) (abstract)(hide abstract)
Haskell is a functional language, with features such as higher
order functions and lazy evaluation, which allow succinct programs. These
high-level features present many challenges for optimising compilers. We
report practical experiments using novel variants of supercompilation,
with special attention to let bindings and the generalisation technique.
Results include runtime reductions of up to 55% when our supercompiler
is used in conjunction with GHC.
(bibtex)(hide bibtex)@unpublished{mitchell:supero_2007_12_10
,title = "A Supercompile for Core {Haskell}"
,author = "Neil Mitchell and Colin Runciman"
,year = "2007"
,month = "December"
,day = "10"
,note = "Draft, submitted to the post proceedings of IFL 2007"
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/draft-supero-10_dec_2007.pdf'"
}
- Parser Design - very early notes on my ideas regarding parsing. (Parsing) (bibtex)(hide bibtex)
@unpublished{mitchell:parsing_2004_11_17
,title = "Parser Design"
,author = "Neil Mitchell"
,year = "2004"
,month = "November"
,day = "17"
,note = "Draft, very early notes on my ideas regarding parsing."
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/draft-parser_design-17_nov_2004.pdf'"
}
- Detecting Pattern-Match Failures in Haskell - from The Oxford Centre for Metacomputation (Catch) (bibtex)(hide bibtex)
@misc{mitchell:catch_2007_11_26
,title = "Detecting Pattern-Match Failures in {Haskell}"
,author = "Neil Mitchell"
,year = "2007"
,month = "November"
,day = "26"
,note = "Presentation from The Oxford Centre for Metacomputation"
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/slides-detecting_pattern_match_failures_in_haskell-26_nov_2007.pdf'"
}
- Deriving Generic Functions by Example - from York Doctoral Symposium 2007 (Derive)
- Uniform Boilerplate and List Processing - from Haskell Workshop 2007 (Uniplate)
- Supero: Making Haskell Faster - from IFL 2007 (Supero)
- Faster Haskell - from Anglo Haskell 2007 (Supero) (bibtex)(hide bibtex)
@misc{mitchell:supero_2007_8_10
,title = "Faster {Haskell}"
,author = "Neil Mitchell"
,year = "2007"
,month = "August"
,day = "10"
,note = "Presentation from Anglo Haskell 2007"
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/slides-faster_haskell-10_aug_2007.pdf'"
}
- Yhc: Past, Present, Future - from Anglo Haskell 2007 (Yhc) (bibtex)(hide bibtex)
@misc{mitchell:yhc_2007_8_10
,title = "Yhc: Past, Present, Future"
,author = "Neil Mitchell"
,year = "2007"
,month = "August"
,day = "10"
,note = "Presentation from Anglo Haskell 2007"
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/slides-yhc_past_present_future-10_aug_2007.pdf'"
}
- Transformation and Analysis of Haskell Source Code - from my thesis seminar (Thesis) (bibtex)(hide bibtex)
@misc{mitchell:thesis_2007_7_2
,title = "Transformation and Analysis of {Haskell} Source Code"
,author = "Neil Mitchell"
,year = "2007"
,month = "July"
,day = "2"
,note = "Presentation from my thesis seminar"
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/slides-transformation_and_analysis_of_haskell_source_code-02_jul_2007.pdf'"
}
- Fastest Lambda First - from PLASMA (Supero) (bibtex)(hide bibtex)
@misc{mitchell:supero_2007_5_30
,title = "Fastest Lambda First"
,author = "Neil Mitchell"
,year = "2007"
,month = "May"
,day = "30"
,note = "Presentation from PLASMA"
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/slides-fastest_lambda_first-30_may_2007.pdf'"
}
- First Order Haskell - from BCTCS 2007 (Firstify) (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://www-users.cs.york.ac.uk/~ndm/downloads/slides-first_order_haskell-06_apr_2007.pdf'"
}
- Ada: Generics - from the Algorithms and Data Structures course (Teaching) (bibtex)(hide bibtex)
@misc{mitchell:teaching_2007_3_7
,title = "Ada: Generics"
,author = "Neil Mitchell"
,year = "2007"
,month = "March"
,day = "7"
,note = "Presentation from the Algorithms and Data Structures course"
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/slides-ada_generics-07_mar_2007.pdf'"
}
- Playing with Haskell Data - from PLASMA (Uniplate) (bibtex)(hide bibtex)
@misc{mitchell:uniplate_2007_1_18
,title = "Playing with {Haskell} Data"
,author = "Neil Mitchell"
,year = "2007"
,month = "January"
,day = "18"
,note = "Presentation from PLASMA"
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/slides-playing_with_haskell_data-18_jan_2007.pdf'"
}
- Haskell With Go Faster Stripes - from PLASMA (Supero) (bibtex)(hide bibtex)
@misc{mitchell:supero_2006_11_30
,title = "Haskell With Go Faster Stripes"
,author = "Neil Mitchell"
,year = "2006"
,month = "November"
,day = "30"
,note = "Presentation from PLASMA"
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/slides-haskell_with_go_faster_stripes-30_nov_2006.pdf'"
}
- Hat: Windows and WIMP - from Hat Day 2006 (Kent) (Hat) (bibtex)(hide bibtex)
@misc{mitchell:hat_2006_10_5
,title = "Hat: {Windows} and {WIMP}"
,author = "Neil Mitchell"
,year = "2006"
,month = "October"
,day = "5"
,note = "Presentation from Hat Day 2006 (Kent)"
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/slides-hat_windows_and_wimp-05_oct_2006.pdf'"
}
- Catch, A Practical Tool - from BCTCS 2006 (Catch) (bibtex)(hide bibtex)
@misc{mitchell:catch_2006_4_6
,title = "Catch, A Practical Tool"
,author = "Neil Mitchell"
,year = "2006"
,month = "April"
,day = "6"
,note = "Presentation from BCTCS 2006"
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/slides-catch-06_apr_2006.pdf'"
}
- Catch, Lazy Termination - from PLASMA (Thesis) (bibtex)(hide bibtex)
@misc{mitchell:thesis_2006_3_16
,title = "Catch, Lazy Termination"
,author = "Neil Mitchell"
,year = "2006"
,month = "March"
,day = "16"
,note = "Presentation from PLASMA"
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/slides-catch-16_mar_2006.pdf'"
}
- Hoogle - from PLASMA (Hoogle) (bibtex)(hide bibtex)
@misc{mitchell:hoogle_2005_12_8
,title = "Hoogle"
,author = "Neil Mitchell"
,year = "2005"
,month = "December"
,day = "8"
,note = "Presentation from PLASMA"
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/slides-hoogle-08_dec_2005.pdf'"
}
- Unfailing Haskell: A Static Checker for Pattern Matching - from TFP 2005 (Catch)
- Hat Visual - from Hat Day 2005 (York) (Hat)
- Total Pasta - from BCTCS 2005 (Total Pasta) (bibtex)(hide bibtex)
@misc{mitchell:totalpasta_2005_3_23
,title = "Total {Pasta}"
,author = "Neil Mitchell"
,year = "2005"
,month = "March"
,day = "23"
,note = "Presentation from BCTCS 2005"
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/slides-total_pasta-23_mar_2005.pdf'"
}
- Termination checking for a lazy functional language - from my first year literature review seminar (Thesis) (bibtex)(hide bibtex)
@misc{mitchell:thesis_2004_12_21
,title = "Termination checking for a lazy functional language"
,author = "Neil Mitchell"
,year = "2004"
,month = "December"
,day = "21"
,note = "Presentation from my first year literature review seminar"
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/slides-termination_checking_for_a_lazy_functional_language-21_dec_2004.pdf'"
}
- A New Parser - from PLASMA (Parsing) (bibtex)(hide bibtex)
@misc{mitchell:parsing_2004_11_17
,title = "A New Parser"
,author = "Neil Mitchell"
,year = "2004"
,month = "November"
,day = "17"
,note = "Presentation from PLASMA"
,url = "\verb'http://www-users.cs.york.ac.uk/~ndm/downloads/slides-a_new_parser-17_nov_2004.pdf'"
}