https://wiki.haskell.org/api.php?action=feedcontributions&user=Jeffstyr&feedformat=atomHaskellWiki - User contributions [en]2020-02-17T10:30:58ZUser contributionsMediaWiki 1.27.4https://wiki.haskell.org/index.php?title=Safe_Haskell&diff=62940Safe Haskell2019-06-21T20:42:55Z<p>Jeffstyr: Updated links</p>
<hr />
<div>= Introduction = <br />
<br />
Safe Haskell is a Haskell language extension. It is described in detail:<br />
<br />
; ''In the GHC user manual:'' : https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/safe_haskell.html<br />
; ''In the Safe Haskell paper:'' : http://community.haskell.org/~simonmar/papers/safe-haskell.pdf<br />
; ''Further technical discussion of Safe Haskell is on the GHC Wiki:'' : https://gitlab.haskell.org/ghc/ghc/wikis/safe-haskell<br />
<br />
For a high-level overview, see this blog post: http://begriffs.com/posts/2015-05-24-safe-haskell.html.<br />
<br />
= In detail = <br />
<br />
As the Safe Haskell paper describes, it "hardens" the Haskell language by providing five properties: type safety, referential transparency, strict module encapsulation, modular reasoning and semantic consistency.<br />
<br />
Safe Haskell is ''not'' magic, and not about catching bugs. It does not ensure that library authors who mark modules as "Trustworthy" are not lying, or incorrect. It does not ensure code inferred safe but in IO cannot perform arbitrary IO. It ''does'' ensure that untrusted code inferred to be safe will, assuming its "Trustworthy" imports are ''indeed'' "Trustworthy" obey the above five properties. As such, again assuming "Trustworthy" imports are indeed so, Safe Haskell infers that untrusted code inferred safe and ''not'' in IO can be run without fear (aside from fear of resource over-utilization/exhaustion).<br />
<br />
Most code that most people want to write is going to be Safe Haskell by default. As Simon Marlow has pointed out, <br />
<br />
<blockquote><br />
"Normally when you use an unsafe feature, the purpose is to use it to implement a safe API - if that's the case, all you have to do is add Trustworthy to your language pragma, and the API is available to use from Safe code. 99% of Hackage should be either Safe or Trustworthy. We know that 27% is already inferred Safe (see the paper), and a lot of the rest is just waiting for other libraries to add Trustworthy where necessary."<br />
</blockquote><br />
<br />
Again, as Simon Marlow argues, <br />
<br />
<blockquote><br />
"For typical Haskell programmers, using <code>{-# LANGUAGE Safe #-}</code> will be like <code>-Wall</code>: something that is considered good practice from a hygiene point of view. If you don't ''need'' access to unsafe features, then it's better to write in the safe subset, where you have stronger guarantees. Just like -Wall, you get to choose whether to use <code>{-# LANGUAGE Safe #-}</code> or not."<br />
</blockquote></div>Jeffstyrhttps://wiki.haskell.org/index.php?title=Introduction_to_IO&diff=61981Introduction to IO2017-07-11T05:15:41Z<p>Jeffstyr: Updated intrawiki link</p>
<hr />
<div>''(This page is intended as a quick introduction to how IO is treated in Haskell. It doesn't describe everything there is to know, but should give some idea of how things work.)''<br />
<br />
Haskell separates pure functions from computations where side effects<br />
must be considered by encoding those side effects as values of a<br />
particular type. Specifically, a value of type <code>(IO a)</code> is an action,<br />
which if executed would produce a value of type <code>a</code>.<br />
<br />
Some examples:<br />
<haskell><br />
getLine :: IO String<br />
putStrLn :: String -> IO () -- note that the result value is an empty tuple.<br />
randomRIO :: (Random a) => (a,a) -> IO a<br />
</haskell><br />
<br />
Ordinary Haskell evaluation doesn't cause this execution to occur. A<br />
value of type <code>(IO a)</code> is almost completely inert. In fact, the only IO<br />
action which can really be said to run in a compiled Haskell program<br />
is <code>main</code>.<br />
<br />
Armed with this knowledge, we can write a "hello, world" program:<br />
<haskell><br />
main :: IO ()<br />
main = putStrLn "Hello, World!"<br />
</haskell><br />
<br />
Now, so far, all this is great, but without a way to chain actions<br />
together end-to-end, we can't do a whole lot. So Haskell provides us<br />
with a few primitives for composing and chaining together IO actions.<br />
A simple one of these is:<br />
<haskell><br />
(>>) :: IO a -> IO b -> IO b<br />
</haskell><br />
where if <code>x</code> and <code>y</code> are IO actions, then <code>(x >> y)</code> is the action that<br />
performs <code>x</code>, dropping the result, then performs <code>y</code> and returns its<br />
result.<br />
Great, we can now write programs which do multiple things:<br />
<haskell><br />
main = putStrLn "Hello" >> putStrLn "World"<br />
</haskell><br />
will print "Hello" and "World" on separate lines.<br />
<br />
However, we don't yet have a way to chain actions in which we are<br />
allowed to use the result of the first in order to affect what the<br />
second action will do. This is accomplished by the following<br />
operation, called 'bind':<br />
<haskell><br />
(>>=) :: IO a -> (a -> IO b) -> IO b<br />
</haskell><br />
Now, <code>x >>= f</code> is the action that first performs the action <code>x</code>, and captures its result, passing it to <code>f</code>, which then computes a second action to be performed. That action is then carried out, and its result is the result of the overall computation.<br />
<br />
That's a mouthful, but once you see it in use, perhaps the idea will<br />
become clearer:<br />
<haskell><br />
main = putStrLn "Hello, what is your name?"<br />
>> getLine<br />
>>= \name -> putStrLn ("Hello, " ++ name ++ "!")<br />
</haskell><br />
<br />
This is most of what we need. In fact, this bind function is really<br />
successful, and we can define <code>(>>)</code> in terms of it:<br />
<haskell><br />
x >> y = x >>= const y<br />
</haskell><br />
<br />
In practice, it turns out to also be quite important to turn a value<br />
into an IO action which does nothing, and simply returns that value.<br />
This is quite handy near the end of a chain of actions, where we want<br />
to decide what to return ourselves, rather than leaving it up to the<br />
last action in the chain. So there's one more primitive,<br />
<haskell><br />
return :: a -> IO a<br />
</haskell><br />
which does just that.<br />
<br />
You might see do-notation all over the place in real Haskell programs. In<br />
do-notation, our example program might look like:<br />
<br />
<haskell><br />
main = do putStrLn "Hello, what is your name?"<br />
name <- getLine<br />
putStrLn ("Hello, " ++ name ++ "!")<br />
</haskell><br />
<br />
This is in fact entirely equivalent to the above form, and is<br />
translated into it by the Haskell compiler. So whenever you see a do<br />
block, you can just imagine a chain of applications of <code>(>>)</code> and <code>(>>=)</code>,<br />
and some lambdas when appropriate to capture the results of actions. An action on its own on a line in a do-block will be executed, and a line of the form <code>v <- x</code> will cause the action <code>x</code> to be run, and the result bound to the variable <code>v</code>.<br />
<br />
A common mistake is to put something other than an action in the place of <code>x</code>, usually some other value. If you want to make a variable binding inside a do-block which doesn't involve running an action, then you can use a line of the form <code>let a = b</code>, which, like an ordinary let-expression will define <code>a</code> to be the same as <code>b</code>, but the definition scopes over the remainder of the do-block.<br />
<br />
Note that there is no function:<br />
<haskell><br />
unsafe :: IO a -> a<br />
</haskell><br />
as this would defeat the referential transparency of Haskell --<br />
applying <code>unsafe</code> to the same IO action might return different things<br />
every time, and Haskell functions aren't allowed to behave that way.<br />
<br />
Now, I haven't really told you anything about monads in general yet.<br />
Most monads are actually rather unlike IO, but they do share the<br />
similar concepts of bind and return. For more on monads in general,<br />
see my [[Monads as containers]] article, or my [[Monads as computation]] article which give two different ways to look at what monads abstract.<br />
<br />
- [[User:CaleGibbard|CaleGibbard]]<br />
<br />
== Further reading ==<br />
<br />
* For a comprehensive tutorial on using IO monad, look at the [[IO_inside|Haskell I/O inside: Down the Rabbit's Hole]]<br />
* An explanation of the basic Monad functions, with examples, can be found in the reference guide [http://members.chello.nl/hjgtuyl/tourdemonad.html A tour of the Haskell Monad functions], by Henk-Jan van Tuyl.<br />
* There is also more information on [[Avoiding IO|how to avoid IO]]<br />
<br />
[[Category:Idioms]]<br />
[[Category:Monad]]<br />
<br />
Languages: [[IO入門編|ja]]</div>Jeffstyrhttps://wiki.haskell.org/index.php?title=Difference_list&diff=61675Difference list2017-03-28T13:46:04Z<p>Jeffstyr: /* Examples */ Update hackage URLs</p>
<hr />
<div>== Difference lists as functions ==<br />
<br />
A difference list of the second sort represents lists as a function <hask>f</hask>, which when given a list <hask>x</hask>, returns the list that <hask>f</hask> represents, prepended to <hask>x</hask>.<br />
Whether this kind of difference list is more efficient than another list representations depends on usage patterns.<br />
If an algorithm builds a list by concatenating smaller lists, which are themselves built by concatenating still smaller lists,<br />
then use of difference lists can improve performance by effectively "flattening" the list building computations.<br />
<br />
This can best be exemplified by <hask>show</hask> and <hask>shows</hask> of Prelude, where the first one implements the naive approach and the second one uses difference lists.<br />
Consider showing a binary tree.<br />
<br />
<hask>L-T-R</hask> gives<br />
* <hask> (show L) ++ (show T ++ (show R)) </hask><br />
* <hask> ((show LL) ++ (show LT ++ (show LR))) ++ (show T ++ (show R)) </hask><br />
* <hask> (((show LLL) ++ (show LLT ++ (show LLR))) ++ (show LT ++ (show LR))) ++ (show T ++ (show R)) </hask><br />
<br />
If the tree is large, you end up with a pretty large left association for the left subtree.<br />
True, there's lot of right association, too, but bad enough.<br />
<br />
With difference lists you write<br />
<br />
* <hask> shows L . (shows T . shows R) </hask><br />
* <hask> (shows LL . (shows LT . shows LR)) . (shows T . shows R) </hask><br />
* <hask> ((shows LLL . (shows LLT . shows LLR)) . (shows LT . shows LR)) . (shows T . shows R) </hask><br />
<br />
You still need to resolve three (.) until you get to the first character of the result string,<br />
but for the subsequent characters you do not need to resolve those dots.<br />
In the end, resolution of all (.) may need some time but then concatenation is performed entirely right-associative.<br />
<br />
== Examples ==<br />
<br />
* [[ShowS]] type in the Prelude of Haskell<br />
* The Endo monoid from <hask>Data.Monoid</hask> allows a simple difference list implementation. E.g. <hask>Endo ("bla"++)</hask> represents the list <hask>"bla"</hask>, <hask>mempty</hask> represents the empty list, <hask>mappend</hask> is list concatenation and <hask>appEndo dlist []</hask> converts the difference list <hask>dlist</hask> to a regular list.<br />
* Donald Bruce Stewart's [http://hackage.haskell.org/package/dlist difference list library]<br />
* Bas van Dijk's [http://hackage.haskell.org/package/dstring difference strings library] (which is just a newtype wrapper around a DList Char)<br />
<br />
== See also ==<br />
<br />
* Haskell-Cafe: [http://www.haskell.org/pipermail/haskell-cafe/2008-January/037405.html Difference lists and ShowS]<br />
* Wikipedia on [http://en.wikipedia.org/wiki/Difference_list Difference lists]<br />
<br />
[[Category:Idioms]]</div>Jeffstyrhttps://wiki.haskell.org/index.php?title=Extensible_record&diff=61375Extensible record2016-12-30T21:45:25Z<p>Jeffstyr: /* Related concepts */ Updated link</p>
<hr />
<div>__TOC__<br />
<br />
Proposals, implementations can be found on the [http://hackage.haskell.org/trac/haskell-prime/wiki/FirstClassLabels FirstClassLabels] page of Haskell' Wiki.<br />
<br />
== Papers and libraries ==<br />
* [[CTRex]] Extensible records as a library using closed type families and type literals.<br />
* [https://www.researchgate.net/profile/Keean_Schupke/publication/234806693_Strongly_typed_heterogeneous_collections/links/02e7e51e92fd6109e3000000.pdf HList – a Haskell library for strongly typed heterogeneous collections] includes also extensible records. Its relatedness to database programming is described in the articles, see also its [http://hackage.haskell.org/trac/summer-of-code/ticket/33 possible] relatedness to [[Libraries and tools/Database interfaces/HaskellDB|HaskellDB]] project.<br />
* Daan Leijen: [http://www.cs.uu.nl/~daan/pubs.html#fclabels First-class labels for extensible rows]. See also the description of the Haskell-like language [http://www.cs.uu.nl/~daan/morrow/ Morrow], it is based on the concepts of the article. And [http://www.cs.uu.nl/~daan/pubs.html#scopedlabels Extensible records with scoped labels]: "We describe a natural approach to typing polymorphic and extensible records that is simple, easy to use in practice, and straightforward to implement."<br />
* Simon Peyton Jones and Greg Morrisett: [http://research.microsoft.com/~simonpj/Haskell/records.html A proposal for records in Haskell]<br />
* Mark Jones and Simon Peyton Jones: [http://research.microsoft.com/~simonpj/Papers/records.htm Lightweight Extensible Records for Haskell]<br />
* Mark P. Jones: [http://www.cs.sfu.ca/CourseCentral/SW/Haskell/hugs/TREX A prototype implementation of extensible records for Hugs]<br />
* Didier Remy's [http://www.cs.uu.nl/wiki/Uhc/ErikKnoop#Typing_record_concatenation_for Typing record concatenation for free] on Erik Knoop's page<br />
* Benedict R. Gaster, Mark P. Jones: [http://web.cecs.pdx.edu/~mpj/pubs/polyrec.html A Polymorphic Type System for Extensible Records and Variants]<br />
* [http://www.comp.nus.edu.sg/~sulzmann/chameleon/ Chameleon], a Haskell-like language, see its [http://www.comp.nus.edu.sg/~sulzmann/chameleon/download/haskell.html#record records] [dead link as of 2011-09-15]<br />
* [[Grapefruit]] contains the package grapefruit-records which implements a record system in Haskell with GHC extensions. This record system allows field selection and dropping of fields using pattern matching. It also supports defaulting.<br />
* [http://www.ioc.ee/~wolfgang/research/ppdp-2010-paper.pdf Generic Record Combinators with Static Type Checking] describes a record system with several novel features, which is provided by the [http://hackage.haskell.org/package/records records package]. It is derived from the record system of [[Grapefruit]].<br />
<br />
=== Libraries on hackage ===<br />
<br />
* [http://hackage.haskell.org/package/extensible-data extensible-data]<br />
* [http://hackage.haskell.org/package/has has]<br />
* [http://hackage.haskell.org/package/HList HList]<br />
* [http://hackage.haskell.org/package/named-records named-records]<br />
* [http://hackage.haskell.org/package/records records] / [http://hackage.haskell.org/package/grapefruit-records grapefruit-records]<br />
* [http://hackage.haskell.org/package/vinyl vinyl]<br />
<br />
== Applications ==<br />
<br />
=== Declarative database management ===<br />
<br />
Such systems can achieve more type safety (compared to direct SQL handling).<br />
They usually formulate a [[relational algebra]] concept in a declarative language.<br />
<br />
==== HaskellDB ====<br />
<br />
A problem where some concepts of extensible records could be useful is described in the [[Libraries and tools/Database interfaces/HaskellDB|HaskellDB]] project. More precisely, the problem is described in the paper downloadable from<br />
* [http://haskelldb.sourceforge.net/ Chalmers version of HaskellDB] (see ''Papers'' subsection on [http://haskelldb.sourceforge.net/#documentation Documentation])<br />
* which presupposes reading also paper on the [http://www.haskell.org/haskellDB/ Daan Leijen's original HaskellDB] page (see [http://www.haskell.org/haskellDB/doc.html Documentation subpage], PostScript version)<br />
<br />
[[Libraries and tools/Database interfaces/HaskellDB|HaskellDB]] uses its own extensible record system, but see also [[Libraries and tools/Database interfaces/HaskellDB#Future|HaskellDB#Future]].<br />
<br />
==== CoddFish ====<br />
<br />
[[Libraries and tools/Database interfaces/CoddFish|CoddFish]] is another declarative, type safe database system. As for extensible record system, it uses [http://homepages.cwi.nl/~ralf/HList/ HList --- a Haskell library for strongly typed heterogeneous collections].<br />
<br />
=== Functional Reactive Programming ===<br />
<br />
[[Functional Reactive Programming|FRP]] often makes it necessary to deal with very large tuples as arrow inputs and outputs. For example, a GUI component would receive the behavior of all its writeable properties as its input. Extensible records can therefore make FRP more usable, especially if they provide defaulting.<br />
<br />
==== Grapefruit ====<br />
<br />
[[Grapefruit]] uses extensible records which support pattern matching and defaulting for functional reactive GUI programming.<br />
<br />
== Related concepts ==<br />
<br />
[[Dependent type]] -- as an explanation for its relatedness here, see [http://www.cs.nott.ac.uk/~psztxa/publ/ydtm.pdf Why Dependent Types Matter] written by Thorsten Altenkirch, Conor McBride, James McKinna -- or see at least its ''Conclusions'' section (section 8, pages 18--19).<br />
<br />
[[Type arithmetic]] seems to me also a way yielding some tastes from [[dependent type]] theory.<br />
<br />
[[Relational algebra]] implementations usually use extensible records.<br />
<br />
[[Category:Proposals]]</div>Jeffstyrhttps://wiki.haskell.org/index.php?title=Extensible_record&diff=61374Extensible record2016-12-30T21:31:08Z<p>Jeffstyr: /* Papers and libraries */ Updated link</p>
<hr />
<div>__TOC__<br />
<br />
Proposals, implementations can be found on the [http://hackage.haskell.org/trac/haskell-prime/wiki/FirstClassLabels FirstClassLabels] page of Haskell' Wiki.<br />
<br />
== Papers and libraries ==<br />
* [[CTRex]] Extensible records as a library using closed type families and type literals.<br />
* [https://www.researchgate.net/profile/Keean_Schupke/publication/234806693_Strongly_typed_heterogeneous_collections/links/02e7e51e92fd6109e3000000.pdf HList – a Haskell library for strongly typed heterogeneous collections] includes also extensible records. Its relatedness to database programming is described in the articles, see also its [http://hackage.haskell.org/trac/summer-of-code/ticket/33 possible] relatedness to [[Libraries and tools/Database interfaces/HaskellDB|HaskellDB]] project.<br />
* Daan Leijen: [http://www.cs.uu.nl/~daan/pubs.html#fclabels First-class labels for extensible rows]. See also the description of the Haskell-like language [http://www.cs.uu.nl/~daan/morrow/ Morrow], it is based on the concepts of the article. And [http://www.cs.uu.nl/~daan/pubs.html#scopedlabels Extensible records with scoped labels]: "We describe a natural approach to typing polymorphic and extensible records that is simple, easy to use in practice, and straightforward to implement."<br />
* Simon Peyton Jones and Greg Morrisett: [http://research.microsoft.com/~simonpj/Haskell/records.html A proposal for records in Haskell]<br />
* Mark Jones and Simon Peyton Jones: [http://research.microsoft.com/~simonpj/Papers/records.htm Lightweight Extensible Records for Haskell]<br />
* Mark P. Jones: [http://www.cs.sfu.ca/CourseCentral/SW/Haskell/hugs/TREX A prototype implementation of extensible records for Hugs]<br />
* Didier Remy's [http://www.cs.uu.nl/wiki/Uhc/ErikKnoop#Typing_record_concatenation_for Typing record concatenation for free] on Erik Knoop's page<br />
* Benedict R. Gaster, Mark P. Jones: [http://web.cecs.pdx.edu/~mpj/pubs/polyrec.html A Polymorphic Type System for Extensible Records and Variants]<br />
* [http://www.comp.nus.edu.sg/~sulzmann/chameleon/ Chameleon], a Haskell-like language, see its [http://www.comp.nus.edu.sg/~sulzmann/chameleon/download/haskell.html#record records] [dead link as of 2011-09-15]<br />
* [[Grapefruit]] contains the package grapefruit-records which implements a record system in Haskell with GHC extensions. This record system allows field selection and dropping of fields using pattern matching. It also supports defaulting.<br />
* [http://www.ioc.ee/~wolfgang/research/ppdp-2010-paper.pdf Generic Record Combinators with Static Type Checking] describes a record system with several novel features, which is provided by the [http://hackage.haskell.org/package/records records package]. It is derived from the record system of [[Grapefruit]].<br />
<br />
=== Libraries on hackage ===<br />
<br />
* [http://hackage.haskell.org/package/extensible-data extensible-data]<br />
* [http://hackage.haskell.org/package/has has]<br />
* [http://hackage.haskell.org/package/HList HList]<br />
* [http://hackage.haskell.org/package/named-records named-records]<br />
* [http://hackage.haskell.org/package/records records] / [http://hackage.haskell.org/package/grapefruit-records grapefruit-records]<br />
* [http://hackage.haskell.org/package/vinyl vinyl]<br />
<br />
== Applications ==<br />
<br />
=== Declarative database management ===<br />
<br />
Such systems can achieve more type safety (compared to direct SQL handling).<br />
They usually formulate a [[relational algebra]] concept in a declarative language.<br />
<br />
==== HaskellDB ====<br />
<br />
A problem where some concepts of extensible records could be useful is described in the [[Libraries and tools/Database interfaces/HaskellDB|HaskellDB]] project. More precisely, the problem is described in the paper downloadable from<br />
* [http://haskelldb.sourceforge.net/ Chalmers version of HaskellDB] (see ''Papers'' subsection on [http://haskelldb.sourceforge.net/#documentation Documentation])<br />
* which presupposes reading also paper on the [http://www.haskell.org/haskellDB/ Daan Leijen's original HaskellDB] page (see [http://www.haskell.org/haskellDB/doc.html Documentation subpage], PostScript version)<br />
<br />
[[Libraries and tools/Database interfaces/HaskellDB|HaskellDB]] uses its own extensible record system, but see also [[Libraries and tools/Database interfaces/HaskellDB#Future|HaskellDB#Future]].<br />
<br />
==== CoddFish ====<br />
<br />
[[Libraries and tools/Database interfaces/CoddFish|CoddFish]] is another declarative, type safe database system. As for extensible record system, it uses [http://homepages.cwi.nl/~ralf/HList/ HList --- a Haskell library for strongly typed heterogeneous collections].<br />
<br />
=== Functional Reactive Programming ===<br />
<br />
[[Functional Reactive Programming|FRP]] often makes it necessary to deal with very large tuples as arrow inputs and outputs. For example, a GUI component would receive the behavior of all its writeable properties as its input. Extensible records can therefore make FRP more usable, especially if they provide defaulting.<br />
<br />
==== Grapefruit ====<br />
<br />
[[Grapefruit]] uses extensible records which support pattern matching and defaulting for functional reactive GUI programming.<br />
<br />
== Related concepts ==<br />
<br />
[[Dependent type]] -- as an explanation for its relatedness here, see [http://www.dcs.st-andrews.ac.uk/~james/RESEARCH/ydtm-submitted.pdf Why Dependent Types Matter] written by Thorsten Altenkirch, Conor McBride, James McKinna -- or see at least its ''Conclusions'' section (section 8, pages 18--19).<br />
<br />
[[Type arithmetic]] seems to me also a way yielding some tastes from [[dependent type]] theory.<br />
<br />
[[Relational algebra]] implementations usually use extensible records.<br />
<br />
[[Category:Proposals]]</div>Jeffstyrhttps://wiki.haskell.org/index.php?title=Extensible_record&diff=61373Extensible record2016-12-30T21:15:05Z<p>Jeffstyr: /* Papers and libraries */ Updated link</p>
<hr />
<div>__TOC__<br />
<br />
Proposals, implementations can be found on the [http://hackage.haskell.org/trac/haskell-prime/wiki/FirstClassLabels FirstClassLabels] page of Haskell' Wiki.<br />
<br />
== Papers and libraries ==<br />
* [[CTRex]] Extensible records as a library using closed type families and type literals.<br />
* [http://www.researchgate.net/publication/234806693_Strongly_typed_heterogeneous_collections/file/72e7e51e92fd6109e3.pdf HList – a Haskell library for strongly typed heterogeneous collections] includes also extensible records. Its relatedness to database programming is described in the articles, see also its [http://hackage.haskell.org/trac/summer-of-code/ticket/33 possible] relatedness to [[Libraries and tools/Database interfaces/HaskellDB|HaskellDB]] project.<br />
* Daan Leijen: [http://www.cs.uu.nl/~daan/pubs.html#fclabels First-class labels for extensible rows]. See also the description of the Haskell-like language [http://www.cs.uu.nl/~daan/morrow/ Morrow], it is based on the concepts of the article. And [http://www.cs.uu.nl/~daan/pubs.html#scopedlabels Extensible records with scoped labels]: "We describe a natural approach to typing polymorphic and extensible records that is simple, easy to use in practice, and straightforward to implement."<br />
* Simon Peyton Jones and Greg Morrisett: [http://research.microsoft.com/~simonpj/Haskell/records.html A proposal for records in Haskell]<br />
* Mark Jones and Simon Peyton Jones: [http://research.microsoft.com/~simonpj/Papers/records.htm Lightweight Extensible Records for Haskell]<br />
* Mark P. Jones: [http://www.cs.sfu.ca/CourseCentral/SW/Haskell/hugs/TREX A prototype implementation of extensible records for Hugs]<br />
* Didier Remy's [http://www.cs.uu.nl/wiki/Uhc/ErikKnoop#Typing_record_concatenation_for Typing record concatenation for free] on Erik Knoop's page<br />
* Benedict R. Gaster, Mark P. Jones: [http://web.cecs.pdx.edu/~mpj/pubs/polyrec.html A Polymorphic Type System for Extensible Records and Variants]<br />
* [http://www.comp.nus.edu.sg/~sulzmann/chameleon/ Chameleon], a Haskell-like language, see its [http://www.comp.nus.edu.sg/~sulzmann/chameleon/download/haskell.html#record records] [dead link as of 2011-09-15]<br />
* [[Grapefruit]] contains the package grapefruit-records which implements a record system in Haskell with GHC extensions. This record system allows field selection and dropping of fields using pattern matching. It also supports defaulting.<br />
* [http://www.ioc.ee/~wolfgang/research/ppdp-2010-paper.pdf Generic Record Combinators with Static Type Checking] describes a record system with several novel features, which is provided by the [http://hackage.haskell.org/package/records records package]. It is derived from the record system of [[Grapefruit]].<br />
<br />
=== Libraries on hackage ===<br />
<br />
* [http://hackage.haskell.org/package/extensible-data extensible-data]<br />
* [http://hackage.haskell.org/package/has has]<br />
* [http://hackage.haskell.org/package/HList HList]<br />
* [http://hackage.haskell.org/package/named-records named-records]<br />
* [http://hackage.haskell.org/package/records records] / [http://hackage.haskell.org/package/grapefruit-records grapefruit-records]<br />
* [http://hackage.haskell.org/package/vinyl vinyl]<br />
<br />
== Applications ==<br />
<br />
=== Declarative database management ===<br />
<br />
Such systems can achieve more type safety (compared to direct SQL handling).<br />
They usually formulate a [[relational algebra]] concept in a declarative language.<br />
<br />
==== HaskellDB ====<br />
<br />
A problem where some concepts of extensible records could be useful is described in the [[Libraries and tools/Database interfaces/HaskellDB|HaskellDB]] project. More precisely, the problem is described in the paper downloadable from<br />
* [http://haskelldb.sourceforge.net/ Chalmers version of HaskellDB] (see ''Papers'' subsection on [http://haskelldb.sourceforge.net/#documentation Documentation])<br />
* which presupposes reading also paper on the [http://www.haskell.org/haskellDB/ Daan Leijen's original HaskellDB] page (see [http://www.haskell.org/haskellDB/doc.html Documentation subpage], PostScript version)<br />
<br />
[[Libraries and tools/Database interfaces/HaskellDB|HaskellDB]] uses its own extensible record system, but see also [[Libraries and tools/Database interfaces/HaskellDB#Future|HaskellDB#Future]].<br />
<br />
==== CoddFish ====<br />
<br />
[[Libraries and tools/Database interfaces/CoddFish|CoddFish]] is another declarative, type safe database system. As for extensible record system, it uses [http://homepages.cwi.nl/~ralf/HList/ HList --- a Haskell library for strongly typed heterogeneous collections].<br />
<br />
=== Functional Reactive Programming ===<br />
<br />
[[Functional Reactive Programming|FRP]] often makes it necessary to deal with very large tuples as arrow inputs and outputs. For example, a GUI component would receive the behavior of all its writeable properties as its input. Extensible records can therefore make FRP more usable, especially if they provide defaulting.<br />
<br />
==== Grapefruit ====<br />
<br />
[[Grapefruit]] uses extensible records which support pattern matching and defaulting for functional reactive GUI programming.<br />
<br />
== Related concepts ==<br />
<br />
[[Dependent type]] -- as an explanation for its relatedness here, see [http://www.dcs.st-andrews.ac.uk/~james/RESEARCH/ydtm-submitted.pdf Why Dependent Types Matter] written by Thorsten Altenkirch, Conor McBride, James McKinna -- or see at least its ''Conclusions'' section (section 8, pages 18--19).<br />
<br />
[[Type arithmetic]] seems to me also a way yielding some tastes from [[dependent type]] theory.<br />
<br />
[[Relational algebra]] implementations usually use extensible records.<br />
<br />
[[Category:Proposals]]</div>Jeffstyrhttps://wiki.haskell.org/index.php?title=Research_papers/Runtime_systems&diff=61327Research papers/Runtime systems2016-12-18T04:09:06Z<p>Jeffstyr: /* Garbage collection */ Fix broken link to Wallace RTGC paper</p>
<hr />
<div>__TOC__<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/spineless-tagless-gmachine.ps.gz Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine]<br />
:SL Peyton Jones, Journal of Functional Programming 2(2), Apr 1992, pp127-202. (Cited by 206)<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/eval-apply/index.htm How to make a fast curry: push/enter vs eval/apply]<br />
:Simon Marlow and Simon Peyton Jones, Proc International Conference on Functional Programming, Snowbird, Sept 2004, pp4-15. (Cited by 6)<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/new-rts.htm The New GHC/Hugs Runtime System]<br />
:Simon Marlow and Simon Peyton Jones. (Unpublished.) (Cited by 6)<br />
<br />
;[ftp://ftp.cs.chalmers.se/pub/cs-reports/papers/jfp-interactive.ps.Z The interactive Lazy ML System]<br />
:Lennart Augustsson, J. Funct. Program. 3(1): 77-92 (1993) (Cited by 3)<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/weak.htm Stretching the storage manager: weak pointers and stable names in Haskell]<br />
:Simon Peyton Jones, Simon Marlow, and Conal Elliott. Proc Workshop on Implementing Functional Languages, 1999.<br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.411 Putting the Spine back in the Spineless Tagless G-machine: An Implementation of Resumable Blackholes]<br />
:A. Reid, In Proceedings of Implementation of Functional Languages (IFL98), Lecture Notes in Computer Science, volume 1595, pp 189-202, Springer Verlag, 1999. <br />
<br />
;[http://www.cs.bris.ac.uk/Publications/Papers/1000248.pdf The Brisk Machine: A Simplified STG Machine]<br />
:Ian Holyer and Eleni Spiliopoulou. University of Bristol. Technical Report CSTR-98-003. March 1998.<br />
<br />
;[http://www.macs.hw.ac.uk/~fairouz/forest/events/festival/workshop1/spiliopoulou.ps The Brisk Machine: the Next Step in the Execution of Functional Languages]<br />
:Eleni Spiliopoulou. Proceedings of Festival Workshop in Foundations and Computations, FC'00. July 2000.<br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.3918 The GRIN Project: A Highly Optimising Back End For Lazy Functional Languages]<br />
:Urban Boquist and Thomas Johnsson. 8th International Workshop on Implementation of Functional Languages. LNCS 1268. September 1996.<br />
<br />
;[http://www.cl.cam.ac.uk/~am21/papers/msp02.ps.gz The Cache Behaviour of Large Lazy Functional Programs on Stock Hardware]<br />
:Nicholas Nethercote, In Proceedings of the ACM SIGPLAN Workshop on Memory System Performance. 2003<br />
<br />
==Profiling==<br />
<br />
;[http://research.microsoft.com/apps/pubs/default.aspx?id=68455 Formally-based profiling for higher-order functional languages]<br />
:PM Sansom and SL Peyton Jones, ACM Transactions on Programming Languages and Systems, 19(2), March 1997, pp 334-385.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/profiling.ps.gz Time and space profiling for non-strict functional languages]<br />
:P Sansom and SL Peyton Jones, 22nd ACM Symposium on Principles of Programming Languages (POPL'95), San Francisco, Jan 1995, pp355-366.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/1994_nonstrict-profiling_THESIS.ps.gz Execution profiling for non-strict functional languages]<br />
:P Sansom, PhD thesis, University of Glasgow, Nov 1994.<br />
<br />
;[http://www.cs.york.ac.uk/ftpdir/reports/92/YCS/172/YCS-92-172.pdf Heap Profiling of Lazy Functional Programs]<br />
:Colin Runciman and David Wakeling. York University. YCS-92-172. 1992.<br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.9361 New Dimensions in Heap Profiling]<br />
:Colin Runciman and Niklas Rojemo. York University. YCS-95-256. 1995.<br />
<br />
==Garbage collection==<br />
<br />
See also [[Research_papers/Parallelism_and_concurrency#Parallel_garbage_collection|parallel garbage collection]]<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/non-stop/index.htm Exploring the Barrier to Entry: Incremental Generational Garbage Collection for Haskell]<br />
:Andy Cheadle, Tony Field, Simon Marlow, Simon Peyton Jones, and Lyndon While, International Symposium on Memory Management, Vancouver, 2004.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/inc-gc.htm Non-stop Haskell]<br />
:Andy Cheadle, Tony Field, Simon Marlow, Simon Peyton Jones, and Lyndon While. ICFP 2000.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/gen-gc-for-haskell.ps.gz Generational garbage collection for Haskell]<br />
:P Sansom and SL Peyton Jones Proc Functional Programming Languages and Computer Architecture (FPCA'93), Copenhagen, June 1993, pp106-116.<br />
<br />
;[https://www.cs.york.ac.uk/ftpdir/pub/malcolm/rtgc.ps.Z An Incremental Garbage Collector for Embedded Real-Time Systems],<br />
:Malcolm Wallace and Colin Runciman. Proceedings of Chalmers Winter Meeting, June 1993.<br />
<br />
;[http://homepages.inf.ed.ac.uk/wadler/papers/leak/leak.ps.gz Fixing some space leaks with a garbage collector]<br />
:Philip Wadler. Software Practice and Experience, 17(9):595-608, September 1987.<br />
<br />
==Optimistic Evaluation==<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/optimistic/index.htm Optimistic Evaluation: an adaptive evaluation strategy for non-strict programs]<br />
:Robert Ennals and Simon Peyton Jones, Proc ACM International Conference on Functional Programming, Uppsala, Aug 2003 (ICFP'03).<br />
<br />
;[http://portal.acm.org/citation.cfm?id=581694&dl=ACM&coll=portal&CFID=15151515&CFTOKEN=6184618 Eager Haskell: Resource-bounded Execution Yields Efficient Iteration]<br />
:Jan-Willem Maessen. Proceedings of the 2002 ACM SIGPLAN workshop on Haskell. Pittsburgh, Pennsylvania. 38 - 50. 2002 ISBN 1-58113-605-6<br />
<br />
;[http://www.it.kth.se/~kff/cheap.ps.gz Cheap Eagerness: Speculative Evaluation in a Lazy Functional Language]<br />
:Karl-Filip Faxn. ICFP 2000. September 2000.<br />
<br />
==Dynamic linking==<br />
<br />
;[http://www.cse.unsw.edu.au/~dons/papers/PSSC04.html Plugging Haskell In]<br />
:Andre Pang, Don Stewart, Sean Seefried, and Manuel M. T. Chakravarty. In Proceedings of the ACM SIGPLAN Workshop on Haskell, pages 10-21. ACM Press, 2004<br />
<br />
;[http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.113.1406 Dynamic Applications From the Ground Up]<br />
:Don Stewart and Manuel M. T. Chakravarty. In Proceedings of the ACM SIGPLAN Workshop on Haskell, pages 27-38. ACM Press, 2005.<br />
<br />
==Loop detection==<br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.2888 A Loop-detecting Interpreter for Lazy, Higher-order Programs]<br />
:Alex Ferguson and John Hughes. The 1992 Glasgow Workshop on Functional Programming. 85-101<br />
<br />
==Foreign language interfaces==<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/com.ps.gz Scripting COM components in Haskell]<br />
:SL Peyton Jones, E Meijer, and D Leijen, Software Reuse 1998.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/comserve.htm Calling hell from heaven and heaven from hell]<br />
:Sigbjorn Finne, Daan Leijen, Erik Meijer, and Simon Peyton Jones. ICFP '99.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/green-card-1.ps.gz Green Card: a foreign-language interface for Haskell]<br />
:T Nordin and SL Peyton Jones, Proceedings of the Haskell Workshop, Amsterdam, June 1997.<br />
<br />
;[http://www.research.microsoft.com/users/simonpj/papers/comserve.ps.gz Calling heaven from hell, and hell from heaven]<br />
:Sigbjorn Finne, Daan Leijen, Erik Meijer and Simon Peyton Jones. ICFP'99<br />
<br />
;[http://www.cse.unsw.edu.au/~chak/papers/Cha99b.html C -> Haskell, or Yet Another Interfacing Tool]<br />
:Manuel M. T. Chakravarty. In Pieter Koopman and Chris Clack, editors, Implementation of Functional Languages, 11th. International Workshop (IFL'99), Springer-Verlag, LNCS 1868, 2000.<br />
<br />
;[http://research.microsoft.com/~emeijer/Papers/HDirect.pdf H/Direct: A Binary Foreign Language Interface for Haskell]<br />
:Sigbjorn Finne, Daan Leijen, Erik Meijer and Simon Peyton Jones. Presented at the International Conference on Functional Programming, Baltimore, M<br />
<br />
;[http://www.reid-consulting-uk.ltd.uk/alastair/publications/ifl03/index.html Template Greencard]<br />
:A. Reid. To be presented at IFL 2003, 15th International Workshop on the Implementation of Functional Languages, Edinburgh, Scotland, September 8-10, 2003.<br />
<br />
;[http://research.microsoft.com/~simonpj/papers/ptr-tag/index.htm Faster laziness using dynamic pointer tagging]<br />
:Simon Marlow, Alexey Rodriguez Yakushev, and Simon Peyton Jones. Submitted to ICFP 2007. <br />
<br />
[[Category:Research]]</div>Jeffstyrhttps://wiki.haskell.org/index.php?title=Research_papers/Runtime_systems&diff=61326Research papers/Runtime systems2016-12-18T03:38:47Z<p>Jeffstyr: Fix broken link to Brisk paper</p>
<hr />
<div>__TOC__<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/spineless-tagless-gmachine.ps.gz Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine]<br />
:SL Peyton Jones, Journal of Functional Programming 2(2), Apr 1992, pp127-202. (Cited by 206)<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/eval-apply/index.htm How to make a fast curry: push/enter vs eval/apply]<br />
:Simon Marlow and Simon Peyton Jones, Proc International Conference on Functional Programming, Snowbird, Sept 2004, pp4-15. (Cited by 6)<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/new-rts.htm The New GHC/Hugs Runtime System]<br />
:Simon Marlow and Simon Peyton Jones. (Unpublished.) (Cited by 6)<br />
<br />
;[ftp://ftp.cs.chalmers.se/pub/cs-reports/papers/jfp-interactive.ps.Z The interactive Lazy ML System]<br />
:Lennart Augustsson, J. Funct. Program. 3(1): 77-92 (1993) (Cited by 3)<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/weak.htm Stretching the storage manager: weak pointers and stable names in Haskell]<br />
:Simon Peyton Jones, Simon Marlow, and Conal Elliott. Proc Workshop on Implementing Functional Languages, 1999.<br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.411 Putting the Spine back in the Spineless Tagless G-machine: An Implementation of Resumable Blackholes]<br />
:A. Reid, In Proceedings of Implementation of Functional Languages (IFL98), Lecture Notes in Computer Science, volume 1595, pp 189-202, Springer Verlag, 1999. <br />
<br />
;[http://www.cs.bris.ac.uk/Publications/Papers/1000248.pdf The Brisk Machine: A Simplified STG Machine]<br />
:Ian Holyer and Eleni Spiliopoulou. University of Bristol. Technical Report CSTR-98-003. March 1998.<br />
<br />
;[http://www.macs.hw.ac.uk/~fairouz/forest/events/festival/workshop1/spiliopoulou.ps The Brisk Machine: the Next Step in the Execution of Functional Languages]<br />
:Eleni Spiliopoulou. Proceedings of Festival Workshop in Foundations and Computations, FC'00. July 2000.<br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.3918 The GRIN Project: A Highly Optimising Back End For Lazy Functional Languages]<br />
:Urban Boquist and Thomas Johnsson. 8th International Workshop on Implementation of Functional Languages. LNCS 1268. September 1996.<br />
<br />
;[http://www.cl.cam.ac.uk/~am21/papers/msp02.ps.gz The Cache Behaviour of Large Lazy Functional Programs on Stock Hardware]<br />
:Nicholas Nethercote, In Proceedings of the ACM SIGPLAN Workshop on Memory System Performance. 2003<br />
<br />
==Profiling==<br />
<br />
;[http://research.microsoft.com/apps/pubs/default.aspx?id=68455 Formally-based profiling for higher-order functional languages]<br />
:PM Sansom and SL Peyton Jones, ACM Transactions on Programming Languages and Systems, 19(2), March 1997, pp 334-385.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/profiling.ps.gz Time and space profiling for non-strict functional languages]<br />
:P Sansom and SL Peyton Jones, 22nd ACM Symposium on Principles of Programming Languages (POPL'95), San Francisco, Jan 1995, pp355-366.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/1994_nonstrict-profiling_THESIS.ps.gz Execution profiling for non-strict functional languages]<br />
:P Sansom, PhD thesis, University of Glasgow, Nov 1994.<br />
<br />
;[http://www.cs.york.ac.uk/ftpdir/reports/92/YCS/172/YCS-92-172.pdf Heap Profiling of Lazy Functional Programs]<br />
:Colin Runciman and David Wakeling. York University. YCS-92-172. 1992.<br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.9361 New Dimensions in Heap Profiling]<br />
:Colin Runciman and Niklas Rojemo. York University. YCS-95-256. 1995.<br />
<br />
==Garbage collection==<br />
<br />
See also [[Research_papers/Parallelism_and_concurrency#Parallel_garbage_collection|parallel garbage collection]]<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/non-stop/index.htm Exploring the Barrier to Entry: Incremental Generational Garbage Collection for Haskell]<br />
:Andy Cheadle, Tony Field, Simon Marlow, Simon Peyton Jones, and Lyndon While, International Symposium on Memory Management, Vancouver, 2004.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/inc-gc.htm Non-stop Haskell]<br />
:Andy Cheadle, Tony Field, Simon Marlow, Simon Peyton Jones, and Lyndon While. ICFP 2000.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/gen-gc-for-haskell.ps.gz Generational garbage collection for Haskell]<br />
:P Sansom and SL Peyton Jones Proc Functional Programming Languages and Computer Architecture (FPCA'93), Copenhagen, June 1993, pp106-116.<br />
<br />
;[ftp://ftp.cs.york.ac.uk/pub/malcolm/rtgc.html An Incremental Garbage Collector for Embedded Real-Time Systems],<br />
:Malcolm Wallace and Colin Runciman. Proceedings of Chalmers Winter Meeting, June 1993.<br />
<br />
;[http://homepages.inf.ed.ac.uk/wadler/papers/leak/leak.ps.gz Fixing some space leaks with a garbage collector]<br />
:Philip Wadler. Software Practice and Experience, 17(9):595-608, September 1987.<br />
<br />
==Optimistic Evaluation==<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/optimistic/index.htm Optimistic Evaluation: an adaptive evaluation strategy for non-strict programs]<br />
:Robert Ennals and Simon Peyton Jones, Proc ACM International Conference on Functional Programming, Uppsala, Aug 2003 (ICFP'03).<br />
<br />
;[http://portal.acm.org/citation.cfm?id=581694&dl=ACM&coll=portal&CFID=15151515&CFTOKEN=6184618 Eager Haskell: Resource-bounded Execution Yields Efficient Iteration]<br />
:Jan-Willem Maessen. Proceedings of the 2002 ACM SIGPLAN workshop on Haskell. Pittsburgh, Pennsylvania. 38 - 50. 2002 ISBN 1-58113-605-6<br />
<br />
;[http://www.it.kth.se/~kff/cheap.ps.gz Cheap Eagerness: Speculative Evaluation in a Lazy Functional Language]<br />
:Karl-Filip Faxn. ICFP 2000. September 2000.<br />
<br />
==Dynamic linking==<br />
<br />
;[http://www.cse.unsw.edu.au/~dons/papers/PSSC04.html Plugging Haskell In]<br />
:Andre Pang, Don Stewart, Sean Seefried, and Manuel M. T. Chakravarty. In Proceedings of the ACM SIGPLAN Workshop on Haskell, pages 10-21. ACM Press, 2004<br />
<br />
;[http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.113.1406 Dynamic Applications From the Ground Up]<br />
:Don Stewart and Manuel M. T. Chakravarty. In Proceedings of the ACM SIGPLAN Workshop on Haskell, pages 27-38. ACM Press, 2005.<br />
<br />
==Loop detection==<br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.2888 A Loop-detecting Interpreter for Lazy, Higher-order Programs]<br />
:Alex Ferguson and John Hughes. The 1992 Glasgow Workshop on Functional Programming. 85-101<br />
<br />
==Foreign language interfaces==<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/com.ps.gz Scripting COM components in Haskell]<br />
:SL Peyton Jones, E Meijer, and D Leijen, Software Reuse 1998.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/comserve.htm Calling hell from heaven and heaven from hell]<br />
:Sigbjorn Finne, Daan Leijen, Erik Meijer, and Simon Peyton Jones. ICFP '99.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/green-card-1.ps.gz Green Card: a foreign-language interface for Haskell]<br />
:T Nordin and SL Peyton Jones, Proceedings of the Haskell Workshop, Amsterdam, June 1997.<br />
<br />
;[http://www.research.microsoft.com/users/simonpj/papers/comserve.ps.gz Calling heaven from hell, and hell from heaven]<br />
:Sigbjorn Finne, Daan Leijen, Erik Meijer and Simon Peyton Jones. ICFP'99<br />
<br />
;[http://www.cse.unsw.edu.au/~chak/papers/Cha99b.html C -> Haskell, or Yet Another Interfacing Tool]<br />
:Manuel M. T. Chakravarty. In Pieter Koopman and Chris Clack, editors, Implementation of Functional Languages, 11th. International Workshop (IFL'99), Springer-Verlag, LNCS 1868, 2000.<br />
<br />
;[http://research.microsoft.com/~emeijer/Papers/HDirect.pdf H/Direct: A Binary Foreign Language Interface for Haskell]<br />
:Sigbjorn Finne, Daan Leijen, Erik Meijer and Simon Peyton Jones. Presented at the International Conference on Functional Programming, Baltimore, M<br />
<br />
;[http://www.reid-consulting-uk.ltd.uk/alastair/publications/ifl03/index.html Template Greencard]<br />
:A. Reid. To be presented at IFL 2003, 15th International Workshop on the Implementation of Functional Languages, Edinburgh, Scotland, September 8-10, 2003.<br />
<br />
;[http://research.microsoft.com/~simonpj/papers/ptr-tag/index.htm Faster laziness using dynamic pointer tagging]<br />
:Simon Marlow, Alexey Rodriguez Yakushev, and Simon Peyton Jones. Submitted to ICFP 2007. <br />
<br />
[[Category:Research]]</div>Jeffstyrhttps://wiki.haskell.org/index.php?title=Rank-N_types&diff=61225Rank-N types2016-10-23T15:54:15Z<p>Jeffstyr: /* See also */ Update link</p>
<hr />
<div>[[Category:Language extensions]]<br />
<br />
== About ==<br />
<br />
Normal Haskell '98 types are considered Rank-1 types. A Haskell '98 type signature such as<br />
<haskell>a -> b -> a</haskell><br />
implies that the type variables are universally quantified like so:<br />
<haskell>forall a b. a -> b -> a</haskell><br />
<hask>forall</hask> can be floated out of the right-hand side of <hask>-></hask> if it appears there, so:<br />
<haskell>forall a. a -> (forall b. b -> a)</haskell><br />
is also a Rank-1 type because it is equivalent to the previous signature.<br />
<br />
However, a <hask>forall</hask> appearing within the left-hand side of <hask>(->)</hask> cannot be moved up, and therefore forms another level or rank. The type is labeled "Rank-N" where N is the number of <hask>forall</hask>s which are nested and cannot be merged with a previous one. For example:<br />
<br />
<hask>(forall a. a -> a) -> (forall b. b -> b)</hask><br />
<br />
is a Rank-2 type because the latter <hask>forall</hask> can be moved to the start but the former one cannot. Therefore, there are two levels of universal quantification.<br />
<br />
Rank-N type reconstruction is undecidable in general, and some explicit type annotations are required in their presence.<br />
<br />
Rank-2 or Rank-N types may be specifically enabled by the language extensions<br />
<hask>{-# LANGUAGE Rank2Types #-}</hask> or <hask>{-# LANGUAGE RankNTypes #-}</hask>.<br />
<br />
== Church-encoded Lists ==<br />
Church-encoded lists use RankNTypes too, as seen in [http://stackoverflow.com/a/15593349/849891 a StackOverflow answer by sacundim]:<br />
<haskell> <br />
-- | Laws:<br />
--<br />
-- > runList xs cons nil == xs<br />
-- > runList (fromList xs) f z == foldr f z xs<br />
-- > foldr f z (toList xs) == runList xs f z<br />
newtype ChurchList a = <br />
ChurchList { runList :: forall r. (a -> r -> r) -> r -> r }<br />
<br />
-- | Make a 'ChurchList' out of a regular list.<br />
fromList :: [a] -> ChurchList a<br />
fromList xs = ChurchList $ \k z -> foldr k z xs<br />
<br />
-- | Turn a 'ChurchList' into a regular list.<br />
toList :: ChurchList a -> [a]<br />
toList xs = runList xs (:) []<br />
<br />
-- | The 'ChurchList' counterpart to '(:)'. Unlike 'DList', whose<br />
-- implementation uses the regular list type, 'ChurchList' abstracts<br />
-- over it as well.<br />
cons :: a -> ChurchList a -> ChurchList a<br />
cons x xs = ChurchList $ \k z -> k x (runList xs k z)<br />
<br />
-- | Append two 'ChurchList's. This runs in O(1) time. Note that<br />
-- there is no need to materialize the lists as @[a]@.<br />
append :: ChurchList a -> ChurchList a -> ChurchList a<br />
append xs ys = ChurchList $ \k z -> runList xs k (runList ys k z)<br />
<br />
-- i.e.,<br />
<br />
nil = {- fromList [] = ChurchList $ \k z -> foldr k z []<br />
= -} ChurchList $ \k z -> z<br />
<br />
singleton x = {- cons x nil = ChurchList $ \k z -> k x (runList nil k z) <br />
= -} ChurchList $ \k z -> k x z<br />
<br />
snoc xs x = {- append xs $ singleton x<br />
= ChurchList $ \k z -> runList xs k (runList (singleton x) k z) <br />
= -} ChurchList $ \k z -> runList xs k (k x z)<br />
</haskell><br />
<br />
== Relation to Existentials ==<br />
<br />
In order to unpack an existential type, you need a polymorphic function that works on any type that could be stored in the existential. This leads to a natural relation between higher-rank types and existentials; and an encoding of existentials in terms of higher rank types in continuation-passing style.<br />
<br />
In general, you can replace<br />
<haskell>data T a1 .. ai = forall t1 .. tj. constraints => Constructor e1 .. ek</haskell><br />
(where <hask>e1..ek</hask> are types in terms of <hask>a1..ai</hask> and <hask>t1..tj</hask>)<br />
<br />
<haskell>Constructor exp1 .. expk -- application of the constructor</haskell><br />
<br />
<haskell>case e of (Constructor pat1 .. patk) -> res</haskell><br />
<br />
with<br />
<br />
<haskell>data T' a1 .. ai = Constructor' (forall b. (forall t1..tj. constraints => e1 -> e2 -> ... -> ek -> b) -> b)</haskell><br />
<br />
<haskell>Constructor' (\f -> f exp1 .. expk)</haskell><br />
<br />
<haskell>case e of (Constructor' f) -> let k pat1 .. patk = res in f k</haskell><br />
<br />
== See also ==<br />
<br />
* [http://hackage.haskell.org/trac/haskell-prime/wiki/RankNTypes Rank-N types] on the Haskell' website.<br />
* [https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts.html#arbitrary-rank-polymorphism The GHC User's Guide on higher-ranked polymorphism].</div>Jeffstyrhttps://wiki.haskell.org/index.php?title=Editors&diff=59923Editors2015-07-19T18:57:05Z<p>Jeffstyr: Add mention of BBEdit and correct link to wiki page for emacs Haskell mode</p>
<hr />
<div>[[Category:Tools]]<br />
<br />
''For detailed information on Haskell IDEs, see [[IDEs]].''<br />
<br />
This page lists Haskell-aware editors with support for Haskell syntax highlighting and formatting support in text editors, grouped by platform.<br />
<br />
Multi-platform<br />
* [http://www.gnu.org/software/emacs/ Emacs]<br />
** [[Emacs |Haskell mode]]<br />
** Integration with [[Hugs]]<br />
* [http://www.vim.org/ Vim]<br />
** [http://www.vim.org/scripts/script.php?script_id=2356 Superior Haskell Interaction Mode]<br />
* [http://www.nedit.org/ Nedit]<br />
* [http://www.jedsoft.org/jed/ Jed]<br />
* [http://www.geany.org/ Geany]<br />
* [http://www.sublimetext.com/ Sublime Text] (proprietary)<br />
* [http://www.activestate.com/komodo-edit Komodo Edit]<br />
* [[Yi]] (work in progress; no binaries yet)<br />
Linux<br />
* [http://kate-editor.org/kate Kate (KDE)]<br />
* [http://www.scintilla.org/SciTE.html SciTE] (Also see these [[Tips for using SciTE with Haskell|tips]])<br />
Windows<br />
* [http://www.textpad.com/ Textpad]<br />
* [http://notepad-plus.sourceforge.net Notepad++]<br />
MacOS X<br />
* [http://www.codingmonkeys.de/subethaedit/ SubEthaEdit]<br />
* [http://macromates.com/ TextMate] has a [http://macromates.com/textmate/manual/bundles#installing_a_bundle Haskell bundle], now kept on [https://github.com/textmate/haskell.tmbundle github].<br />
* [http://www.barebones.com/products/bbedit/ BBEdit] and [http://www.barebones.com/products/textwrangler/ TextWrangler] have a [http://code.google.com/p/bbedit-haskell/ codeless language module for Haskell]</div>Jeffstyr