https://wiki.haskell.org/api.php?action=feedcontributions&user=Stefan&feedformat=atomHaskellWiki - User contributions [en]2021-09-18T18:10:39ZUser contributionsMediaWiki 1.27.4https://wiki.haskell.org/index.php?title=Hac_2007_II/Attendees&diff=16002Hac 2007 II/Attendees2007-10-05T01:37:35Z<p>Stefan: obvious typo</p>
<hr />
<div>[[Image:Hac-axe-icon.png|Hac icon]]<br />
<br />
== Registrants ==<br />
<br />
If you've registered, do add your name to the following table:<br />
<br />
{| class="wikitable"<br />
! Name<br />
! Nick<br />
! Affiliiation<br />
! Provided tshirt size<br />
! Mobile #<br />
|-<br />
| [http://www.cse.unsw.edu.au/~dons Don Stewart]<br />
| dons<br />
| Galois<br />
| Yes<br />
|<br />
|-<br />
| Ian Lynagh<br />
| Igloo<br />
|<br />
| Yes<br />
|<br />
|-<br />
| Duncan Coutts<br />
| dcoutts<br />
| Oxford<br />
| Yes<br />
|<br />
|-<br />
| Lennart Kolmodin<br />
| kolmodin<br />
| Chalmers<br />
| Yes<br />
| +46736223606<br />
|-<br />
| Pepe Iborra<br />
| mnislaih<br />
| UPV<br />
| Yes<br />
|<br />
|-<br />
| Ben Lippmeier<br />
| benl23<br />
| ANU<br />
| Yes<br />
|<br />
|-<br />
| David Himmelstrup<br />
| Lemmih<br />
|<br />
| Yes<br />
|<br />
|- <br />
| [http://www.bringert.net/ Björn Bringert]<br />
| bringert<br />
| Chalmers <br />
| Yes<br />
| +46704779794<br />
|-<br />
| Tim Chevalier<br />
| Binkley<br />
| PSU<br />
| Yes<br />
|<br />
|-<br />
| Andy Gill<br />
| andyjgill<br />
| Galois<br />
| Yes<br />
|<br />
|-<br />
| Clemens Fruhwirth<br />
| therp<br />
| <br />
| Yes<br />
|<br />
|-<br />
| Thorkil Naur<br />
| naur<br />
|<br />
| Yes<br />
|<br />
|-<br />
| Benedikt Schmidt<br />
| beschmi<br />
|<br />
| Yes<br />
|<br />
|-<br />
| Thomas Schilling<br />
| nominolo<br />
|<br />
| Yes<br />
|<br />
|-<br />
| Conal Elliott<br />
| conal<br />
|<br />
| Yes<br />
|<br />
|-<br />
| Russell O'Connor<br />
| roconnor<br />
|<br />
| Yes<br />
| +31625178046<br />
|-<br />
| Ganesh Sittampalam<br />
| Heffalump<br />
| Credit Suisse<br />
| Yes<br />
|<br />
|-<br />
| Jürgen Nicklisch<br />
| Jutaro<br />
|<br />
| Yes<br />
|<br />
|-<br />
| Ivan Tarasov<br />
| ivant<br />
|<br />
| Yes<br />
|<br />
|-<br />
| Johan Tibell<br />
| tibbe<br />
|<br />
| Yes<br />
|<br />
|-<br />
| Clifford Beshers<br />
| thetallguy<br />
|<br />
| Yes<br />
|<br />
|-<br />
| David Fox<br />
| dsf<br />
| <br />
| Yes<br />
|<br />
|-<br />
| [http://www.esat.kuleuven.ac.be/~cpoucet Christophe Poucet]<br />
| vincenz<br />
| IMEC<br />
| Yes<br />
|<br />
|-<br />
| Matthias Neubauer<br />
| heckenpenner<br />
| Freiburg<br />
| Yes<br />
|<br />
|-<br />
| Stefan Wehr<br />
| <br />
| Freiburg<br />
| Yes<br />
|<br />
|-<br />
| [http://www.randomhacks.net/ Eric Kidd]<br />
| ekidd<br />
| Dartmouth<br />
| Yes<br />
|<br />
|-<br />
| Marcus Uneson<br />
| muneson<br />
| <br />
| Yes<br />
|<br />
|-<br />
| Conrad Barski<br />
| drcode<br />
| <br />
| Yes<br />
| [http://lisperati.com/haskell/ My Brand New Haskell Tutorial :-)]<br />
|-<br />
| Joachim Breitner<br />
| nomeata<br />
| <br />
| Yes<br />
|<br />
|}<br />
<br />
== Arriving ==<br />
<br />
===Train===<br />
<br />
* Igloo: 29 Sep at 21:00, Freiburg Hbf.<br />
* Lemmih: 29 Sep at 18:00, Freiburg Hbf.<br />
* Jutaro: 29 Sep at 23:09, Freiburg Hbf.<br />
* ivant: 30 Sep, at 8:00, from Vienna<br />
* tibbe: 5 Oct, at 8:00, from Zurich<br />
* vincenz: 4 Oct, At 23-24, Freiburg Hbf.<br />
* roconnor: 4 Oct, at 21:00, Freiburg Hbf.<br />
<br />
===Air===<br />
<br />
* Andy Gill, 29 Sep Frankfurt<br />
* Don Stewart, 29 Sep 8.35 am, Frankfurt<br />
* Thomas Schilling, 29 Sep Frankfurt Main<br />
* Conal Elliott, 25 Sep 11:10 am, Frankfurt<br />
* Ganesh Sittampalam, 29 Sep 2:50 pm, Zurich<br />
* Pepe Iborra, 29 Sep 8:40 pm, Frankfurt Hahn (HHN)<br />
* Lennart Kolmodin, 29 Sep, 12:05, Frankfurt<br />
* Björn Bringert, 04 Oct 18:55, Frankfurt (train to Freiburg dep 19.54, arr 22:15)<br />
<br />
== Accomodation ==<br />
<br />
A number of accommodation options are available. To organize to share,<br />
contact other attendees on irc or via email. <br />
<br />
=== Black Forest Hostel ===<br />
<br />
Some people are staying at the hostel: http://www.blackforest-hostel.de/<br />
<br />
* Igloo, Lemmih, nominolo: 29 Sep - 8 Oct<br />
* conal: same, in a 6-bed dorm room, 25 Sep - 8 Oct<br />
* ivant: same, 30 Sep - 8 Oct<br />
* tibbe: 6-bed dorm room, 5 Oct - 7 Oct<br />
* mnislaih: same<br />
* dcoutts, kolmodin: 6-bed dorm room, 29 Sep - 8 Oct<br />
* drcode<br />
* roconnor: dorm room, 4 Oct - 8 Oct (still to be confirmed)<br />
<br />
We will be meeting at 9am at the entrance of the Black Forest Hostel to go to the Hackathon venue.<br />
<br />
=== Best Western ===<br />
<br />
* dons, andy: Best Western<br />
<br />
=== InterCityHotel ===<br />
<br />
http://www.booking.com/hotel/de/intercityhotelfreiburg.html<br />
<br />
* bringert, vincenz: 04 Oct - 07 Oct<br />
<br />
=== Paradies ===<br />
<br />
* jutaro: 01 Oct - 07 Oct</div>Stefanhttps://wiki.haskell.org/index.php?title=IRC_channel&diff=15198IRC channel2007-08-20T19:19:01Z<p>Stefan: high water - past 400!</p>
<hr />
<div>== Overview ==<br />
<br />
Internet Relay Chat is a worldwide text chat service with many thousands<br />
of users among various irc networks.<br />
<br />
The Freenode IRC network hosts the large #haskell channel, and we've had up to<br />
411 concurrent users (average is 346). One famous resident is<br />
[[Lambdabot]], another is [http://hpaste.org hpaste] (see the [[#Bots|Bots]] section below).<br />
<br />
The IRC channel can be an excellent place to learn more about Haskell,<br />
and to just keep in the loop on new things in the Haskell world. Many<br />
new developments in the Haskell world first appear on the irc channel.<br />
<br />
== Getting there ==<br />
<br />
If you point your irc client to [irc://chat.freenode.net/haskell chat.freenode.net] and then join the #haskell channel, you'll be there. Alternately, you can try [http://ircatwork.com/ ircatwork.com] which connects inside the browser.<br />
<br />
Example, using [http://www.irssi.org/ irssi]:<br />
<br />
$ irssi -c chat.freenode.org -n myname -w mypassword<br />
/join #haskell<br />
<br />
Tip, if you're using Emacs to edit your Haskell sources then why not use it to chat about Haskell? Check out [http://www.emacswiki.org/cgi-bin/wiki/EmacsIRCClient ERC], The Emacs IRC client. Invoke it like this and follow the commands:<br />
<br />
M-x erc-select<br />
...<br />
/join #haskell<br />
<br />
[[Image:Irc--haskell-screenshot.png|frame|A screenshot of an irssi session in #haskell]]<br />
<br />
== Principles ==<br />
<br />
The #haskell channel is a very friendly, welcoming place to hang out,<br />
teach and learn. The goal of #haskell is to encourage learning and<br />
discussion of Haskell, functional programming, and programming in<br />
general. As part of this we welcome newbies, and encourage teaching of<br />
the language.<br />
<br />
Part of the #haskell success comes from the approach that the community<br />
is quite tight knit -- we know each other -- it's not just a homework<br />
channel. As a result, many collaborative projects have arisen between<br />
Haskell irc channel citizens.<br />
<br />
To maintain the friendly, open culture, the following is required:<br />
<br />
* Low to zero tolerance for ridiculing questions. Insulting new users is unacceptable<br />
<br />
New Haskell users should feel entirely comfortable asking new questions.<br />
Helpful answers should be encouraged with <hask>name++</hask> karma<br />
points, in public, as a reward for providing a good answer.<br />
<br />
== History ==<br />
<br />
The #haskell channel appeared in the late 90s, and really got going<br />
in early 2001, with the help of Shae Erisson (aka shapr).<br />
<br />
A fairly extensive analysis of the traffic on #haskell over the years is<br />
[http://www.cse.unsw.edu.au/~dons/irc/ kept here]<br />
<br />
<br />
== Related channels ==<br />
<br />
In addition to the main Haskell channel there are also:<br />
<br />
{| border="1" cellspacing="0" cellpadding="5" align="center"<br />
! Channel<br />
! Purpose<br />
|- <br />
| #haskell.de<br />
| German speakers<br />
|-<br />
| #haskell.dut<br />
| Dutch speakers<br />
|-<br />
| #haskell.es<br />
| Spanish speakers<br />
|-<br />
| #haskell.fi<br />
| Finnish speakers<br />
|-<br />
| #haskell.fr <br />
| French speakers <br />
|-<br />
| #haskell.hr<br />
| Croatian speakers<br />
|-<br />
| #haskell.it <br />
| Italian speakers<br />
|-<br />
| #haskell.jp <br />
| Japanese speakers<br />
|-<br />
| #haskell.no <br />
| Norwegian speakers<br />
|-<br />
| #haskell.ru <br />
| Russian speakers. Seems that most of them migrated to Jabber conference (haskell@conference.jabber.ru).<br />
|-<br />
| #haskell_ru <br />
| Russian speakers again, in UTF-8. For those, who prefer good ol' IRC channel with a lambdabot.<br />
|-<br />
| #haskell.se <br />
| Swedish speakers<br />
|-<br />
| #haskell-overflow<br />
| Overflow conversations<br />
|-<br />
| #haskell-blah <br />
| Haskell people talking about anything except Haskell itself<br />
|-<br />
| #haskell-books <br />
| Authors organizing the collaborative writing of the [http://en.wikibooks.org/wiki/Haskell Haskell wikibook] and other books or tutorials.<br />
|-<br />
| #gentoo-haskell <br />
| [[Gentoo]]/Linux specific Haskell conversations<br />
|-<br />
| #darcs <br />
| [[Darcs]] revision control channel (written in Haskell)<br />
|-<br />
| #perl6 <br />
| [http://www.pugscode.org Perl 6] development (plenty of Haskell chat there too)<br />
|-<br />
| #happs<br />
| [http://happs.org HAppS] Haskell Application Server channel<br />
|-<br />
| #xmonad<br />
| [http://xmonad.org Xmonad] a tiling window manager written in Haskell<br />
|}<br />
<br />
[[Image:Nick-activity.png|frame|Growth of #haskell]]<br />
<br />
== Logs ==<br />
<br />
'''Logs''' are kept at a few places, including<br />
<br />
* [http://tunes.org/~nef/logs/haskell/ tunes.org]<br />
* [http://ircbrowse.com/cdates.html?channel=haskell IRCBrowse]<br />
<br />
== Bots ==<br />
<br />
=== Lambdabot ===<br />
<br />
[[Lambdabot]] provides many useful services for visitors to the IRC channel. Check out its wiki page for information on its commands.<br />
<br />
=== Hpaste ===<br />
The hpaste bot provides a notification interface to the [http://hpaste.org hpaste pastebin]. [[Hpaste.el|Emacs integration]] is available.<br />
<br />
== Locations ==<br />
<br />
To get an overview of where everybody on the channel might<br />
be, physically, please visit [[Haskell user locations]].<br />
<br />
[[Category:Community]]</div>Stefanhttps://wiki.haskell.org/index.php?title=IRC_channel&diff=15049IRC channel2007-08-13T20:19:23Z<p>Stefan: high water</p>
<hr />
<div>== Overview ==<br />
<br />
Internet Relay Chat is a worldwide text chat service with many thousands<br />
of users among various irc networks.<br />
<br />
The Freenode IRC network hosts the large #haskell channel, and we've had up to<br />
385 concurrent users (average is 321). One famous resident is<br />
[[Lambdabot]], another is [http://hpaste.org hpaste] (see the [[#Bots|Bots]] section below).<br />
<br />
The IRC channel can be an excellent place to learn more about Haskell,<br />
and to just keep in the loop on new things in the Haskell world. Many<br />
new developments in the Haskell world first appear on the irc channel.<br />
<br />
== Getting there ==<br />
<br />
If you point your irc client to [irc://chat.freenode.net/haskell chat.freenode.net] and then join the #haskell channel, you'll be there. Alternately, you can try [http://ircatwork.com/ ircatwork.com] which connects inside the browser.<br />
<br />
Example, using [http://www.irssi.org/ irssi]:<br />
<br />
$ irssi -c chat.freenode.org -n myname -w mypassword<br />
/join #haskell<br />
<br />
Tip, if you're using Emacs to edit your Haskell sources then why not use it to chat about Haskell? Check out [http://www.emacswiki.org/cgi-bin/wiki/EmacsIRCClient ERC], The Emacs IRC client. Invoke it like this and follow the commands:<br />
<br />
M-x erc-select<br />
...<br />
/join #haskell<br />
<br />
[[Image:Irc--haskell-screenshot.png|frame|A screenshot of an irssi session in #haskell]]<br />
<br />
== Principles ==<br />
<br />
The #haskell channel is a very friendly, welcoming place to hang out,<br />
teach and learn. The goal of #haskell is to encourage learning and<br />
discussion of Haskell, functional programming, and programming in<br />
general. As part of this we welcome newbies, and encourage teaching of<br />
the language.<br />
<br />
Part of the #haskell success comes from the approach that the community<br />
is quite tight knit -- we know each other -- it's not just a homework<br />
channel. As a result, many collaborative projects have arisen between<br />
Haskell irc channel citizens.<br />
<br />
To maintain the friendly, open culture, the following is required:<br />
<br />
* Low to zero tolerance for ridiculing questions. Insulting new users is unacceptable<br />
<br />
New Haskell users should feel entirely comfortable asking new questions.<br />
Helpful answers should be encouraged with <hask>name++</hask> karma<br />
points, in public, as a reward for providing a good answer.<br />
<br />
== History ==<br />
<br />
The #haskell channel appeared in the late 90s, and really got going<br />
in early 2001, with the help of Shae Erisson (aka shapr).<br />
<br />
A fairly extensive analysis of the traffic on #haskell over the years is<br />
[http://www.cse.unsw.edu.au/~dons/irc/ kept here]<br />
<br />
<br />
== Related channels ==<br />
<br />
In addition to the main Haskell channel there are also:<br />
<br />
{| border="1" cellspacing="0" cellpadding="5" align="center"<br />
! Channel<br />
! Purpose<br />
|- <br />
| #haskell.de<br />
| German speakers<br />
|-<br />
| #haskell.dut<br />
| Dutch speakers<br />
|-<br />
| #haskell.es<br />
| Spanish speakers<br />
|-<br />
| #haskell.fi<br />
| Finnish speakers<br />
|-<br />
| #haskell.fr <br />
| French speakers <br />
|-<br />
| #haskell.hr<br />
| Croatian speakers<br />
|-<br />
| #haskell.it <br />
| Italian speakers<br />
|-<br />
| #haskell.jp <br />
| Japanese speakers<br />
|-<br />
| #haskell.no <br />
| Norwegian speakers<br />
|-<br />
| #haskell.ru <br />
| Russian speakers. Seems that most of them migrated to Jabber conference (haskell@conference.jabber.ru)<br />
|-<br />
| #haskell.se <br />
| Swedish speakers<br />
|-<br />
| #haskell-overflow<br />
| Overflow conversations<br />
|-<br />
| #haskell-blah <br />
| Haskell people talking about anything except Haskell itself<br />
|-<br />
| #haskell-books <br />
| Authors organizing the collaborative writing of the [http://en.wikibooks.org/wiki/Haskell Haskell wikibook] and other books or tutorials.<br />
|-<br />
| #gentoo-haskell <br />
| [[Gentoo]]/Linux specific Haskell conversations<br />
|-<br />
| #darcs <br />
| [[Darcs]] revision control channel (written in Haskell)<br />
|-<br />
| #perl6 <br />
| [http://www.pugscode.org Perl 6] development (plenty of Haskell chat there too)<br />
|-<br />
| #happs<br />
| [http://happs.org HAppS] Haskell Application Server channel<br />
|-<br />
| #xmonad<br />
| [http://xmonad.org Xmonad] a tiling window manager written in Haskell<br />
|}<br />
<br />
[[Image:Nick-activity.png|frame|Growth of #haskell]]<br />
<br />
== Logs ==<br />
<br />
'''Logs''' are kept at a few places, including<br />
<br />
* [http://tunes.org/~nef/logs/haskell/ tunes.org]<br />
* [http://ircbrowse.com/cdates.html?channel=haskell IRCBrowse]<br />
<br />
== Bots ==<br />
<br />
=== Lambdabot ===<br />
<br />
[[Lambdabot]] provides many useful services for visitors to the IRC channel. Check out its wiki page for information on its commands.<br />
<br />
=== Hpaste ===<br />
The hpaste bot provides a notification interface to the [http://hpaste.org hpaste pastebin]. [[Hpaste.el|Emacs integration]] is available.<br />
<br />
== Locations ==<br />
<br />
To get an overview of where everybody on the channel might<br />
be, physically, please visit [[Haskell user locations]].<br />
<br />
[[Category:Community]]</div>Stefanhttps://wiki.haskell.org/index.php?title=Safely_running_untrusted_Haskell_code&diff=15022Safely running untrusted Haskell code2007-08-12T03:48:27Z<p>Stefan: Rework implementation section, remove bizarre claims about show</p>
<hr />
<div>[[Category:How to]]<br />
Obviously, don't run code in the IO monad, just show pure results (or possibly make your own monad that is a restricted subset of IO). But it's a lot more complicated than that...<br />
<br />
== Verifying safety : lambdabot's approach ==<br />
<br />
Since 2004, lambdabot has executed arbitrary strings of Haskell provided<br />
by user's of various [[IRC_channel|IRC channels]], in particular, the<br />
Haskell channel. In order to do this, a particular security policy is<br />
required. The policy, and its implementation, is described here.<br />
<br />
=== The policy ===<br />
<br />
Only allow execution of pure Haskell expressions. <br />
<br />
=== The implementation ===<br />
<br />
The evaluator is essentially a function, <hask>eval :: String -> IO<br />
String</hask>, which takes a random Haskell string, verifies it,<br />
compiles it, and evaluates the result, returning a String representing<br />
the result, back over the network.<br />
<br />
This function is implemented as two separate processes:<br />
<br />
* [http://www.cse.unsw.edu.au/~dons/code/lambdabot/Plugin/Eval.hs Driver/simple verifier]<br />
* [http://www.cse.unsw.edu.au/~dons/code/lambdabot/scripts/RunPlugs.hs Evaluator binary]<br />
<br />
The driver reads a String from the network, and then subjects it to a<br />
simple test:<br />
<br />
* The expression is parsed as a Haskell 98 expression, hopefully preventing code injection (is this true? and can any string that can parse as a valid Haskell expression become something more sinister when put in a particular context?)<br />
<br />
If the string parses as a Haskell 98 expression, the 'runplugs' process<br />
is then forked to evaluate the string, and the following checks are put<br />
in place:<br />
<br />
* Only a trusted module set is imported, avoiding unsafePerformIO and unsafeIOtoST and such like.<br />
* Module imports are disallowed<br />
* Time and space limitations on the runplugs process are set by the OS 'rlimit' facility<br />
* The expression type checked, enforcing lack of memory errors<br />
* Because the user code is not at the beginning of the file, malicious {-# LANGUAGE #-} and {-# OPTIONS #-} flags are ignored<br />
* Only -fextended-default-rules are allowed, as language extensions over H98.<br />
* The resulting .o file is dynamically linked only into the throw-away runplugs instance<br />
* Even if all went well, the first 2048 characters of the shown string are returned to the caller (no infinite output DoS)<br />
<br />
A few other nicities are provided:<br />
<br />
* The expression is bound to a random identifier (harmless to guess), in order to allow nice line error messages with line pragmas.<br />
* The expression is wrapped in 'show'.<br />
* A catch-all instance of Show in terms of Typable is provided, to display non-displayble objects in a more useful way (e.g. putStrLn --> <[Char] -> IO ()>)<br />
* It is compiled to native code with -fasm for speed (compilation time is neglible compared to IRC lag)<br />
* The value is evaluated inside an exception handler; if an exception is thrown, the first 1024 characters of the exception string are returned.<br />
<br />
== Exploits ==<br />
<br />
A variety of interesting exploits have been found, or thought of, over<br />
the years. Those we remember are listed below:<br />
<br />
* using newtype recursion to have the inliner not terminate<br />
* using pathological type inference cases to have the type checker not terminate<br />
* code injection of code fragments that aren't Haskell expressions<br />
* Template Haskell used to run IO actions during type checking<br />
* stToIO to convert a safe ST action, into an IO action that is run<br />
* large strings returned in exceptions<br />
* unsafePerformIO, of course<br />
* unsafeCoerce#<br />
* throwing a piece of code as an exception, which is evaluated when the exception is shown<br />
* non-terminating code, in a tight loop that doesn't allocate, can't use GHC's threadDelay/scheduler (let f () = f () in f ()) to timeout (must use OS resource limits).<br />
* large array allocations can fill memory<br />
* very large array allocations can integer overflow the storage manager, allowing arbitrary memory access<br />
* creating class instances that violate assumed laws (cf EvilIx)<br />
* various literal strings that print IRC protocol commands could be printed using exceptions.<br />
* if a user guesses the top level identifier the expression is bound to, it can be used to print a silly string<br />
* zombies could be created by multiple runplugs calls, leading to blocking on endless output. the resulting zombies accumulate, eventually leading to DOS.<br />
<br />
== Template Haskell ==<br />
<br />
We believe that Template Haskell can be made safe for users by hiding runIO and reify.<br />
<br />
== See also ==<br />
<br />
* See [http://haskell.org/pipermail/haskell-cafe/2007-May/025941.html a long discussion] in Haskell Cafe.<br />
* The [http://hackage.haskell.org/trac/ghc/ticket/1380 GHC ticket] for -fsafe</div>Stefanhttps://wiki.haskell.org/index.php?title=User:NeilMitchell&diff=14617User:NeilMitchell2007-07-23T14:40:46Z<p>Stefan: fix old WikiWord link</p>
<hr />
<div>I am doing a PhD in computer science at [http://www.cs.york.ac.uk/ York University, UK]. My academic website is http://www-users.cs.york.ac.uk/~ndm/, my personal website is http://www.nmitchell.co.uk/.<br />
<br />
I hereby license all my contributions to this wiki, and the old hawiki, under the simple permissive license on [[HaskellWiki:Copyrights]].<br />
<br />
== Haskell Projects ==<br />
<br />
The ones that people might know include:<br />
<br />
* I am the author of [[Hoogle]]<br />
* I am in the process of rewriting the Windows front end to [[Hugs]], [[WinHugs]]<br />
* I help out with [[Yhc]]<br />
* I am interested in documentation [[Keywords]]<br />
<br />
== Contacting Me ==<br />
<br />
I am sometimes on the Haskell [[IRC channel]] as <tt>ndm</tt>. I can also be reached by email:<br />
<br />
<tt>email = "ndmitchell" ++ [chr 64] ++ reverse "liamg" ++ [chr 46] ++ "com"</tt><br />
<br />
== Todo Notes for Gtk2Hs ==<br />
<br />
* How do you get colours like "red" and "green" - I'm currently using maxBound<br />
* How to set a popup menu to exactly where you want it with x/y coordinates<br />
* The size of a monospace character</div>Stefanhttps://wiki.haskell.org/index.php?title=Haskell_Cafe_migration&diff=14344Haskell Cafe migration2007-07-15T05:23:09Z<p>Stefan: must... realphabetize!</p>
<hr />
<div>Often people post wonderful material to the mailing lists, hpaste.org or<br />
on #haskell. This can later be hard to find. The goal of this page is to<br />
collect a list of people who are happy for their contributions to the<br />
Haskell community, in any media, to be added directly to the Haskell wiki.<br />
<br />
If you are happy for your contributions (both new and old posts) on <br />
''any media that are part of the Haskell community'', including:<br />
<br />
* [[Mailing_lists|The mailing lists]] (haskell-cafe@, libraries@ and others)<br />
* [[IRC_channel|The IRC channel]]<br />
* [http://hpaste.org/ The Haskell Paste Bin]: hpaste.org<br />
* [[HaWiki_migration|The Old Haskell Wiki]]<br />
* And the new wiki.<br />
<br />
that ''are not specifically licensed'' to be treated as having been<br />
released under a [[HaskellWiki:Copyrights|Simple Permissive License]].<br />
please add your name to this list, so that others may move your<br />
contributions around haskell.org without fear.<br />
<br />
''Contributions will be licensed specifically under a<br />
[[HaskellWiki:Copyrights|Simple Permissive License]]''.<br />
<br />
* Andrew Bromage (aka Pseudonym)<br />
* Brandon Allbery<br />
* Bulat Ziganshin<br />
* Cale Gibbard<br />
* Chris Smith (cdsmith; blog also fair game)<br />
* Conor McBride<br />
* Conrad Parker<br />
* Dan Doel<br />
* Derek Elkins<br />
* Dominic Steinitz<br />
* Don Stewart<br />
* Eric Kow (kowey)<br />
* Henk-Jan van Tuyl<br />
* Ian Lynagh (Igloo)<br />
* Jonathan Cast<br />
* Neil Mitchell (ndm)<br />
* Samuel Bronson (SamB)<br />
* Stefan O'Rear<br />
* Thorkil Naur<br />
* Tim Chevalier (aka Kirsten)<br />
* Tom Conway<br />
<br />
[[Category:Community]]</div>Stefanhttps://wiki.haskell.org/index.php?title=OpenGL&diff=14343OpenGL2007-07-15T05:21:24Z<p>Stefan: fix link (sadly still very much with us)</p>
<hr />
<div>This is a stub page for Haskell's OpenGL and GLUT bindings. It is meant as a starting point to replace the outdated and misleading documentation at the<br />
[http://www.haskell.org/HOpenGL/ old page] (which should have disappeared by now, so that url will no longer lead anywhere, but you might still meet it on the web).<br />
<br />
First, note that the implementation is far more up-to-date than that old page suggested (originally, it was quite useful, but the page hasn't kept up with the implementation for a long time now). To find more recent information, try:<br />
<br />
[http://www.haskell.org/mailman/listinfo/hopengl the hopengl mailing list]<br />
<br />
[http://www.haskell.org/ghc/docs/latest/html/libraries/OpenGL/Graphics-Rendering-OpenGL-GL.html the API docs for the OpenGL binding]<br />
<br />
[http://www.haskell.org/ghc/docs/latest/html/libraries/GLUT/Graphics-UI-GLUT.html the API docs for the GLUT binding]<br />
<br />
[http://darcs.haskell.org/packages/OpenGL the darcs repo with the sources for the OpenGL binding]<br />
<br />
[http://darcs.haskell.org/packages/GLUT/ the darcs repo with the sources for the GLUT binding]<br />
<br />
In particular, note that the [http://darcs.haskell.org/packages/GLUT/examples/ examples/] directory in the GLUT repo contains lots of examples, including translations of the red book examples.<br />
<br />
Both the API documentation and the examples are best studied with the original specs and the original red book examples at hand.<br />
<br />
Projects using the OpenGL bindings:<br />
<br />
* [[Frag]], a 3D first-person shooter game<br />
<br />
[[Category:Packages]]</div>Stefanhttps://wiki.haskell.org/index.php?title=Haskell_Cafe_migration&diff=14310Haskell Cafe migration2007-07-14T05:49:55Z<p>Stefan: typo fix</p>
<hr />
<div>Often people post wonderful material to the mailing lists, hpaste.org or<br />
on #haskell. This can later be hard to find. The goal of this page is to<br />
collect a list of people who are happy for their contributions to the<br />
Haskell community, in any media, to be added directly to the Haskell wiki.<br />
<br />
If you are happy for your contributions (both new and old posts) on <br />
''any media that are part of the Haskell community'', including:<br />
<br />
* [[Mailing_lists|The mailing lists]] (haskell-cafe@, libraries@ and others)<br />
* [[IRC_channel|The IRC channel]]<br />
* [http://hpaste.org/ The Haskell Paste Bin]: hpaste.org<br />
* [[HaWiki_migration|The Old Haskell Wiki]]<br />
* And the new wiki.<br />
<br />
that ''are not specifically licensed'' to be treated as having been<br />
released under a [[HaskellWiki:Copyrights|Simple Permissive License]].<br />
please add your name to this list, so that others may move your<br />
contributions around haskell.org without fear.<br />
<br />
''Contributions will be licensed specifically under a<br />
[[HaskellWiki:Copyrights|Simple Permissive License]]''.<br />
<br />
* Brandon Allbery<br />
* Cale Gibbard<br />
* Chris Smith<br />
* Conor McBride<br />
* Conrad Parker<br />
* Dan Doel<br />
* Derek Elkins<br />
* Don Stewart<br />
* Eric Kow (kowey)<br />
* Jonathan Cast<br />
* Samuel Bronson (SamB)<br />
* Stefan O'Rear<br />
* Tim Chevalier (aka Kirsten)<br />
<br />
<br />
[[Category:Community]]</div>Stefanhttps://wiki.haskell.org/index.php?title=Haskell_Cafe_migration&diff=14298Haskell Cafe migration2007-07-14T02:09:28Z<p>Stefan: Unordered lists should probably be represented lexicographically</p>
<hr />
<div>Often people post wonderful material to the mailing lists. This can<br />
later be hard to find. The goal of this page is to collect a list of <br />
people who are happy for their contributions to be added directly to<br />
the Haskell wiki.<br />
<br />
If you are happy for your contributions (both new and old posts) on the<br />
Haskell mailing lists to be relicensed and moved to the new wiki when<br />
appropriate, please add your name to this list, so that others may move<br />
your contributions without fear.<br />
<br />
Contributions will be licensed specifically under a<br />
[[HaskellWiki:Copyrights|Simple Permissive License]].<br />
<br />
* Brandon Allbery<br />
* Cale Gibbard<br />
* Chris Smith<br />
* Conor McBride<br />
* Conrad Parker<br />
* Dan Doel<br />
* Derek Elkins<br />
* Don Stewart<br />
* Stefan O'Rear<br />
* Tim Chevalier (aka Kirsten)<br />
<br />
[[Category:Community]]</div>Stefanhttps://wiki.haskell.org/index.php?title=Haskell_Cafe_migration&diff=14288Haskell Cafe migration2007-07-14T00:06:05Z<p>Stefan: Add myself & alphabetize existing</p>
<hr />
<div>Often people post wonderful material to the mailing lists. This can<br />
later be hard to find. The goal of this page is to collect a list of <br />
people who are happy for their contributions to be added directly to<br />
the Haskell wiki.<br />
<br />
If you are happy for your contributions on the Haskell mailing lists to<br />
be relicensed and moved to the new wiki when appropriate, please add<br />
your name to this list, so that others may move your contributions<br />
without fear.<br />
<br />
Contributions will be licensed specifically under a<br />
[[HaskellWiki:Copyrights|Simple Permissive License]].<br />
<br />
* Derek Elkins<br />
* Don Stewart<br />
* Stefan O'Rear<br />
<br />
[[Category:Community]]</div>Stefanhttps://wiki.haskell.org/index.php?title=User_talk:Syzygies&diff=13984User talk:Syzygies2007-07-04T04:32:53Z<p>Stefan: note collision</p>
<hr />
<div>Your choice of nick is a tad unfortunate, as Mikael Johansson is already known as Syzygy-. (cf #haskell and planet.haskell.org). [[User:Stefan|Stefan]] 04:32, 4 July 2007 (UTC)</div>Stefanhttps://wiki.haskell.org/index.php?title=IRC_channel&diff=13769IRC channel2007-06-28T01:03:42Z<p>Stefan: highwater</p>
<hr />
<div>== Overview ==<br />
<br />
Internet Relay Chat is a worldwide text chat service with many thousands<br />
of users among various irc networks.<br />
<br />
The Freenode IRC network hosts the #haskell channel, and we've had up to<br />
354 concurrent users (average is 300). One famous resident is<br />
[[Lambdabot]], another is [http://hpaste.org hpaste] (see the [[#Bots|Bots]] section below).<br />
<br />
The IRC channel can be an excellent place to learn more about Haskell,<br />
and to just keep in the loop on new things in the Haskell world. Many<br />
new developments in the Haskell world first appear on the irc channel.<br />
<br />
== Getting there ==<br />
<br />
If you point your irc client to [irc://chat.freenode.net/haskell chat.freenode.net] and then join the #haskell channel, you'll be there. Alternately, you can try [http://ircatwork.com/ ircatwork.com] which connects inside the browser.<br />
<br />
Example, using [http://www.irssi.org/ irssi]:<br />
<br />
$ irssi -c chat.freenode.org -n myname -w mypassword<br />
/join #haskell<br />
<br />
Tip, if you're using Emacs to edit your Haskell sources then why not use it to chat about Haskell? Check out [http://www.emacswiki.org/cgi-bin/wiki/EmacsIRCClient ERC], The Emacs IRC client. Invoke it like this and follow the commands:<br />
<br />
M-x erc-select<br />
...<br />
/join #haskell<br />
<br />
[[Image:Irc--haskell-screenshot.png|frame|A screenshot of an irssi session in #haskell]]<br />
<br />
== Principles ==<br />
<br />
The #haskell channel is a very friendly, welcoming place to hang out,<br />
teach and learn. The goal of #haskell is to encourage learning and<br />
discussion of Haskell, functional programming, and programming in<br />
general. As part of this we welcome newbies, and encourage teaching of<br />
the language.<br />
<br />
Part of the #haskell success comes from the approach that the community<br />
is quite tight knit -- we know each other -- it's not just a homework<br />
channel. As a result, many collaborative projects have arisen between<br />
Haskell irc channel citizens.<br />
<br />
To maintain the friendly, open culture, the following is required:<br />
<br />
* Low to zero tolerance for ridiculing questions. Insulting new users is unacceptable<br />
<br />
New Haskell users should feel entirely comfortable asking new questions.<br />
Helpful answers should be encouraged with <hask>name++</hask> karma<br />
points, in public, as a reward for providing a good answer.<br />
<br />
== History ==<br />
<br />
The #haskell channel appeared in the late 90s, and really got going<br />
in early 2001, with the help of Shae Erisson (aka shapr).<br />
<br />
A fairly extensive analysis of the traffic on #haskell over the years is<br />
[http://www.cse.unsw.edu.au/~dons/irc/ kept here]<br />
<br />
<br />
== Related channels ==<br />
<br />
In addition to the main Haskell channel there are also:<br />
<br />
{| border="1" cellspacing="0" cellpadding="5" align="center"<br />
! Channel<br />
! Purpose<br />
|- <br />
| #haskell.de<br />
| German speakers<br />
|-<br />
| #haskell.dut<br />
| Dutch speakers<br />
|-<br />
| #haskell.es<br />
| Spanish speakers<br />
|-<br />
| #haskell.fi<br />
| Finnish speakers<br />
|-<br />
| #haskell.fr <br />
| French speakers <br />
|-<br />
| #haskell.hr<br />
| Croatian speakers<br />
|-<br />
| #haskell.it <br />
| Italian speakers<br />
|-<br />
| #haskell.jp <br />
| Japanese speakers<br />
|-<br />
| #haskell.no <br />
| Norwegian speakers<br />
|-<br />
| #haskell.ru <br />
| Russian speakers. Seems that most of them migrated to Jabber conference (haskell@conference.jabber.ru)<br />
|-<br />
| #haskell.se <br />
| Swedish speakers<br />
|-<br />
| #haskell-overflow<br />
| Overflow conversations<br />
|-<br />
| #haskell-blah <br />
| Haskell people talking about anything except Haskell itself<br />
|-<br />
| #haskell-books <br />
| Authors organizing the collaborative writing of the [http://en.wikibooks.org/wiki/Haskell Haskell wikibook] and other books or tutorials.<br />
|-<br />
| #gentoo-haskell <br />
| [[Gentoo]]/Linux specific Haskell conversations<br />
|-<br />
| #darcs <br />
| [[Darcs]] revision control channel (written in Haskell)<br />
|-<br />
| #perl6 <br />
| [http://www.pugscode.org Perl 6] development (plenty of Haskell chat there too)<br />
|-<br />
| #happs<br />
| [http://happs.org HAppS] Haskell Application Server channel<br />
|-<br />
| #xmonad<br />
| [http://xmonad.org Xmonad] a tiling window manager written in Haskell<br />
|}<br />
<br />
[[Image:Nick-activity.png|frame|Growth of #haskell]]<br />
<br />
== Logs ==<br />
<br />
'''Logs''' are kept at a few places, including<br />
<br />
* [http://tunes.org/~nef/logs/haskell/ tunes.org]<br />
* [http://meme.b9.com/clog/haskell/ meme]<br />
<br />
== Bots ==<br />
<br />
=== Lambdabot ===<br />
<br />
[[Lambdabot]] provides many useful services for visitors to the IRC channel. Check out its wiki page for information on its commands.<br />
<br />
=== Hpaste ===<br />
The hpaste bot provides a notification interface to the [http://hpaste.org hpaste pastebin]. [[Hpaste.el|Emacs integration]] is available.<br />
<br />
== Locations ==<br />
<br />
To get an overview of where everybody on the channel might<br />
be, physically, please visit [[Haskell user locations]].<br />
<br />
[[Category:Community]]</div>Stefanhttps://wiki.haskell.org/index.php?title=Yi&diff=13258Yi2007-05-27T16:48:21Z<p>Stefan: Spell my name correctly</p>
<hr />
<div>[[Category:Applications]]<br />
<br />
== Yi homepage ==<br />
<br />
http://www.cse.unsw.edu.au/~dons/yi.html<br />
<br />
== The obligatory screenshoot ==<br />
<br />
[[Image:yi-20070409.png]]<br />
<br />
== NEWS ==<br />
<br />
(Recent items first)<br />
<br />
* Synchronous keymaps: the behaviour of the keymap (ie. the underlying parser) can depend on the editor state.<br />
* Full-dynamic Yi<br />
* Yi is now hosted on darcs.haskell.org/yi<br />
** it's now possible to change any part of the Yi codebase and see the result with a mere 'M-x reconfigE' (take that, Steve Yegge :))<br />
* Dired mode (thanks Ben Moseley)<br />
* Yi 0.2 released!<br />
* Buffer-specific code is now contained in BufferM monad<br />
* Multiple marks per buffer<br />
* All keymaps use a unified mechanism! (and are therefore potentially composable)<br />
* Miniwindows for vty frontend<br />
* Miniwindows for GTK frontend<br />
* Basic support for query-replace (emacs)<br />
* Rudimentary support for indentation<br />
* Syntax highlighting in GTK frontend (using SourceView) <br />
* Completion for file names<br />
* Incremental search (emacs)<br />
* Completion for M-x, and buffer switch.<br />
* History for emacs mode minibuffer<br />
* New commands and keybindings can be defined easily and dynamically<br />
* Yi is an haskell interpreter! <br />
** Possibility to run editor actions interactively (similar to emacs M-x)<br />
** Configuration is just a haskell module exporting (yiMain :: Action)<br />
* Possibility to evaluate haskell expressions interactively.<br />
* New, unified way to define Keybindings<br />
* Vty frontend supports Haskell (lexical) syntax highlighting (thanks Stefan O'Rear)<br />
* GTK frontend works in Win32<br />
* GTK frontend (in addition of Vty frontend) (requires gtk>=0.9.10.4)<br />
* Linewrap support<br />
* Bugfixes in scrolling<br />
* Lots of simplifications in the cursor management<br />
* Keymaps can now process typed events instead of Chars (no extra decode step)<br />
* Yi.Debug added for debugging<br />
* Vty frontend replaces Curses frontend<br />
<br />
== Bugs ==<br />
<br />
* vi: delete (d) seems broken<br />
<br />
* emacs: matching names can make the window oversized.<br />
* emacs: isearch should unset the selection<br />
* emacs: buffer set should behave as a stack<br />
<br />
* vty: home,end: keys are not correctly supported <br />
** This is a vty library problem. sorear: it works fine on the linux console but fails to handle $TERM. (vty 3.1 will wrap ncurses)<br />
* vty: haskell syntax highlight chokes on {- -} comments<br />
* vty: killing the last line of a buffer brings the point to the beginning of the buffer<br />
<br />
* gtk: regexp search is not implemented<br />
<br />
== How to Configure Yi == <br />
<br />
You can find configuration file examples here:<br />
<br />
http://www.cse.unsw.edu.au/~dons/yi/examples/<br />
<br />
A good start is to copy YiConfig.hs in your ~/.yi directory (create it if needed), and hack as needed.<br />
<br />
To run the gtk frontend, use the "-fgtk" option.<br />
<br />
== Development plan ==<br />
<br />
Also read: http://www.cse.unsw.edu.au/~dons/yi/TODO<br />
<br />
=== Test suite ===<br />
<br />
The test suite has to be made up to date and re-instated.<br />
<br />
Build test: regular, gtk, and haddock html doc should be buildable at all times.<br />
<br />
=== Refactorings ===<br />
<br />
The below describes possible refactorings to investigate:<br />
<br />
*Keymaps<br />
** Evaluate "layered components architecture": http://www.cs.uu.nl/research/techreps/UU-CS-2002-030.html<br />
<br />
* Buffers<br />
at the buffer level)<br />
** Duplicating Buffer functions at the Core level by wrapping them in withBuffer is ugly<br />
<br />
* Nail-down the last remnants of C<br />
** C-code don't belong to yi but to low-level libraries<br />
<br />
=== New features ===<br />
<br />
Roughly by order of easy to do / reverse importance.<br />
<br />
* Window stuff<br />
** Add option to deactivate line-wrap (and truncate lines instead)<br />
*** gtk: attribute textViewWrapMode<br />
** vty: horizontal scrolling<br />
** Independent window scrolling (without moving the Point)<br />
<br />
* Open multiple windows on a buffer (each with a different point)<br />
<br />
* have a console that behaves more or less like ghci<br />
** prompt<br />
** direct evaluation (not only of (EditorM a))<br />
<br />
* cua mode<br />
<br />
* Buffers<br />
** Per-buffer specific state. Ideally this should be statically typed and fit the per-buffer keymap.<br />
** Do Undo/Redo on the "interactive" transaction boundaries<br />
** Re-think the Buffer interface/implementation (so it supports unicode (utf8), better marks, etc.)<br />
** Re-write the FastBuffer so it uses ByteString (or something else) instead of directly the C pointers<br />
*** Look at other possibilities for buffer storage; e.g. Simon Tatham has had success using lazily-constructed size-annotated 2-3-4 trees for editing >10GB files. [http://www.chiark.greenend.org.uk/~sgtatham/tweak/btree.html]<br />
<br />
* Invent/discover a system to have annotated buffers (syntax highlight, interactive content)<br />
** see emacs overlays<br />
<br />
== Yi ideas ==<br />
<br />
This section is meant to gather ideas people have for Yi.<br />
<br />
=== Emacs ===<br />
<br />
Coming from an Emacs background, I think a few things are essential,<br />
mainly the introspection capabilities of Emacs.<br />
<br />
==== Emacs goodness ====<br />
<br />
The following are things I like about Emacs, as an extensible<br />
environment, and miss in Yi:<br />
<br />
; Really good online documentation<br />
: Emacs can tell you a lot about a function or variable with a keypress--- the current value, where it is declared, and a hypertext formation string<br />
<br />
; Hooks-Extensibility<br />
: All (good) apps allow users to extend, through, e.g., hooks --- a list of functions that are run before/after some event (like saving a file)<br />
<br />
<br />
==== Emacs badness ====<br />
<br />
So, why replace it?:<br />
; ELisp<br />
: Dynamically scoped, Dynamically typed, ugly, old. 'Nuff said<br />
<br />
; What's a Parser?<br />
: A lot of apps in emacs do stuff with text, usually text that is in some language. There is no standard parser (like, e.g. parsec), so a lot of it is ugly handwritten spaghetti. This also means that adding analysis tools isn't really done (or done nicely).<br />
<br />
; ELisp again<br />
: Haskell is a lot cleaner to write, especially because of the large number of libraries.<br />
<br />
==== Emacs maybeness (?) ====<br />
<br />
Some things that are sometimes bad, sometimes good:<br />
<br />
; Everything is a buffer<br />
: Makes some sense, but sometimes doesn't. It is nice to have uniform key bindings do the right thing (e.g., C-Space sets the mark, and the region can then be used, e.g. to delete a sequence of emails in Wl) Sometimes, however, you just want some sort of GUI widget.<br />
: OTOH, having the minibuffer be a special kind of buffer is a good idea.<br />
<br />
; Properties<br />
: It is possible to associate arbitrary properties with symbols. This means you can annotate a symbol and then use that information at a later date<br />
<br />
=== Vi ? ===<br />
<br />
What about vi? I believe we want Yi to subsume vi as well.<br />
<br />
=== Ideas ===<br />
<br />
;An extension to GHCi to support documentation of symbols. <br />
:This seems to be (reasonably) straightforward, as GHCi already has :info. It would mean hacking the type environment (what about values?) to add documentation information. The main problem would seem to be populating this --- maybe hack haddock to produce something from the library docs? I assume that using package GHC uses the parent RTS (package GHC seems to be the way to go, but more investigation is required --- don?)<br />
<br />
;Views on data<br />
:Rather than just editing a file, you would open a view onto the file, i.e. there is no longer a 1-1 correspondence between buffers and files. Why? Well, for aggregate buffers (i.e., editing multiple files in the one view), or for multiple views of a file (e.g. AST and source-level). There would be some primitive ops for editing a buffer (insertChar, delete, etc.), which would then call update functions on anything observing that file.<br />
<br />
;Remote attach so I can work from home, but still use a remote machine<br />
<br />
;Haddock documentation<br />
:(no brainer), maybe associate with .hi files for binaries. <br />
<br />
;A class MiniBufferRead (or PromptingRead) which allows the user to<br />
invoke a function similar to M-x in Emacs, but without requiring<br />
(interactive) <br />
: This means that given f :: String -> Int -> Action, (makeInteractive f) :: Action would prompt the user for a String then an Int and run the corresponding action.<br />
<br />
;Maybe a class YiShow, which all config items must be a member of? This is to emulate describe-variable<br />
<br />
=== Implementation ===<br />
<br />
Considerations:<br />
; Configuration <br />
: Per mode/file/buffer/whatever Monads, or reload/recompile? Or some hybrid? How does this interact with the documentation aspects? Do we want to have separate sorts of symbols a la emacs (describe-function, describe-variable), or is everything a function? I would think that configuration info doesn't change that frequently --- is this globally true though?<br />
:We can probably use a GHCi-like "let". Rebinding a function would then be synonym to assign a variable, thereby achieve unification between functions and variables.<br />
:Also possible: use something similar to the GHCi debugger to "tune" the behavior of some functions.<br />
<br />
; Interface to the runtime<br />
: The scheduler, docs, etc.<br />
<br />
; Introspection of e.g. what processes are running.<br />
: There are already libraries in Haskell for processes, but they don't give Yi any extra information --- we really want a layer on top. <br />
<br />
...<br />
<br />
[[User:Sjw|Sjw]] 09:15, 2 June 2006 (UTC)</div>Stefanhttps://wiki.haskell.org/index.php?title=Safely_running_untrusted_Haskell_code&diff=13257Safely running untrusted Haskell code2007-05-27T16:47:51Z<p>Stefan: two other known exploits</p>
<hr />
<div>Obviously, don't run code in the IO monad, just show pure results (or possibly make your own monad that is a restricted subset of IO). But it's a lot more complicated than that...<br />
<br />
== Verifying safety : lambdabot's approach ==<br />
<br />
Since 2004, lambdabot has executed arbitrary strings of Haskell provided<br />
by user's of various [[IRC_channel|IRC channels]], in particular, the<br />
Haskell channel. In order to do this, a particular security policy is<br />
required. The policy, and its implementation, is described here.<br />
<br />
=== The policy ===<br />
<br />
Only allow execution of pure Haskell expressions. <br />
<br />
=== The implementation ===<br />
<br />
The evaluator is essentially a function, <hask>eval :: String -> IO<br />
String</hask>, which takes a random Haskell string, verifies it,<br />
compiles it, and evaluates the result, returning a String representing<br />
the result, back over the network.<br />
<br />
This function is implemented as two separate processes:<br />
<br />
* [http://www.cse.unsw.edu.au/~dons/code/lambdabot/Plugin/Eval.hs Driver/simple verifier]<br />
* [http://www.cse.unsw.edu.au/~dons/code/lambdabot/scripts/RunPlugs.hs Evaluator binary]<br />
<br />
The driver reads a String from the network, and then subjects it to a<br />
simple test:<br />
<br />
* parse the expression to check it is a Haskell 98 expression<br />
<br />
If the string parses as a Haskell 98 expression, the 'runplugs' process<br />
is then forked to evaluate the string, and the following checks are put<br />
in place:<br />
<br />
* Only a trusted module set is imported, avoiding unsafePerformIO and stToIO and such like.<br />
* Module imports are disallowed<br />
* Time and space limitations on the runplugs process are set by the OS<br />
* The expression is bound to a random top level identifier (harmless to guess)<br />
* The expression is wrapped in 'show', and must be an instance of Show<br />
* An instance of Show IO is defined, which prints "<IO>", rendering IO impossible.<br />
* The expression is type checked, with the show constraint, enforcing purity<br />
* If it type checks, and the type checker doesn't time out, it is compiled to native code with -fasm<br />
* Only -fextended-default-rules are allowed, as language extensions over H98.<br />
* The resulting .o file is dynamically linked into the throw-away runplugs instance<br />
* The value is evaluated inside an exception handler.<br />
* If an exception is thrown, only the first 1024 characters of the exception string are returned.<br />
* If all went well, the first 2048 characters of the shown string are returned to the caller.<br />
<br />
== Exploits ==<br />
<br />
A variety of interesting exploits have been found, or thought of, over<br />
the years. Those we remember are listed below:<br />
<br />
* using newtype recursion to have the typechecker not terminate<br />
* using pathological type inference cases to have the type checker not terminate<br />
* code injection of code fragments that arne't haskell expressions<br />
* Template Haskell used to run IO actions during type checking<br />
* stToIO to convert a safe ST action, into an IO action that is run<br />
* large strings returned in exceptions<br />
* unsafePerformIO, of course<br />
* unsafeCoerce#<br />
* throwing a piece of code as an exception, which is evaluated when the exception is shown<br />
* non-terminating code, in a tight loop that doesn't allocate, can't use GHC's threadDelay/scheduler (let f () = f () in f ()) to timeout (must use OS resource limits).<br />
* large array allocations can fill memory<br />
* very large array allocations can integer overflow the storage manager, allowing arbitrary memory access<br />
* creating class instances that violate assumed laws (cf EvilIx)<br />
* various literal strings that print IRC protocol commands could be printed using exceptions.<br />
* if a user guesses the top level identifier the expression is bound to, it can be used to print a silly string<br />
* zombies could be created by multiple runplugs calls, leading to blocking on endless output. the resulting zombies accumulate, eventually leading to DOS.<br />
<br />
== Template Haskell ==<br />
<br />
We believe that Template Haskell can be made safe for users by hiding runIO and reify.<br />
<br />
== See also ==<br />
<br />
* See [http://haskell.org/pipermail/haskell-cafe/2007-May/025941.html a long discussion] in Haskell Cafe.<br />
* The [http://hackage.haskell.org/trac/ghc/ticket/1380 GHC ticket] for -fsafe</div>Stefanhttps://wiki.haskell.org/index.php?title=Dynamic_programming_example&diff=12494Dynamic programming example2007-04-11T04:40:27Z<p>Stefan: Add optimization section</p>
<hr />
<div>[[Category:Tutorials]] [[Category:Code]]<br />
<br />
Dynamic programming refers to translating a problem to be solved into a recurrence formula, and crunching this formula with the help of an array (or any suitable collection) to save useful intermediates and avoid redundant work.<br />
<br />
Computationally, dynamic programming boils down to write once, share and read many times. This is exactly what lazy functional programming is for.<br />
<br />
== Sample problems and solutions ==<br />
<br />
=== Available in 6-packs, 9-packs, 20-packs ===<br />
<br />
A fast food place sells a finger food in only boxes of 6 pieces, boxes of 9 pieces, or boxes of 20 pieces. You can only buy zero or more such boxes. Therefore it is impossible to buy exactly 5 pieces, or exactly 7 pieces, etc. Can you buy exactly N pieces?<br />
<br />
If I can buy i-6 pieces, or i-9 pieces, or i-20 pieces (provided these are not negative numbers), I can then buy i pieces (by adding a box of 6 or 9 or 20). Below, I set up the array <hask>r</hask> for exactly that, with <hask>r!0</hask> forced to <hask>True</hask> to bootstrap the whole thing.<br />
<br />
<haskell><br />
import Data.Array<br />
<br />
buyable n = r!n<br />
where r = listArray (0,n) (True : map f [1..n])<br />
f i = i >= 6 && r!(i-6) || i >= 9 && r!(i-9) || i >= 20 && r!(i-20)<br />
</haskell><br />
<br />
== Optimization ==<br />
<br />
Simple dynamic programing is usually fast enough (and as always,<br />
profile before optimizing!) However, when you need more speed, it is<br />
usually fairly easy to shave an order of magnitude off the space usage<br />
of dynamic programming problems (with concomitant speedups due to<br />
cache effects.) The trick is to manually schedule the computation in<br />
order to discard temporary results as soon as possible.<br />
<br />
Notice that if we compute results in sequential order from 0 to the<br />
needed count, (in the example above) we will always have computed<br />
subproblems before the problems. Also, if we do it in this order we<br />
need not keep any value for longer than twenty values. So we can use<br />
the old fibonacci trick:<br />
<br />
<haskell><br />
buyable n = iter n (True : replicate 19 False)<br />
where iter 0 lst = lst !! 0<br />
iter n lst = iter (n-1) ((lst !! 5 || lst !! 8 || lst !! 19) : take 19 lst)<br />
</haskell><br />
<br />
At each call of iter, the n parameter contains (total - cur) and the<br />
lst parameter stores buyable for (cur-1, cur-2, cur-3, ...). Also<br />
note that the indexes change meaning through the cons, so we need to<br />
offset the !! indexes by 1. <br />
<br />
We can improve this more by packing the bit array:<br />
<br />
<haskell><br />
import Data.Bits<br />
<br />
buyable n = iter n 1<br />
where iter :: Int -> Int -> Bool<br />
iter 0 lst = odd lst<br />
iter n lst = iter (n-1) ((lst `shiftL` 1) .|.<br />
if lst .&. 0x8120 /= 0 then 1 else 0)<br />
</haskell><br />
<br />
This final version is compiled into a single allocation-free loop.</div>Stefanhttps://wiki.haskell.org/index.php?title=Yi&diff=12447Yi2007-04-08T08:37:31Z<p>Stefan: minor note/clarification on vty bug</p>
<hr />
<div>[[Category:Applications]]<br />
<br />
== Yi homepage ==<br />
<br />
http://www.cse.unsw.edu.au/~dons/yi.html<br />
<br />
== NEWS ==<br />
<br />
(Recent items first)<br />
<br />
* Miniwindows for GTK frontend<br />
* Basic support for query-replace (emacs)<br />
* Rudimentary support for indentation<br />
* Syntax highlighting in GTK frontend (using SourceView) <br />
* Completion for file names<br />
* Incremental search (emacs)<br />
* Completion for M-x, and buffer switch.<br />
* History for emacs mode minibuffer<br />
* New commands and keybindings can be defined easily and dynamically<br />
* Yi is an haskell interpreter! <br />
** Possibility to run editor actions interactively (similar to emacs M-x)<br />
** Configuration is just a haskell module exporting (yiMain :: Action)<br />
* Possibility to evaluate haskell expressions interactively.<br />
* New, unified way to define Keybindings<br />
* Vty frontend supports Haskell (lexical) syntax highlighting<br />
* GTK frontend works in Win32<br />
* GTK frontend (in addition of Vty frontend) (requires gtk>=0.9.10.4)<br />
* Linewrap support<br />
* Bugfixes in scrolling<br />
* Lots of simplifications in the cursor management<br />
* Keymaps can now process typed events instead of Chars (no extra decode step)<br />
* Yi.Debug added for debugging<br />
* Vty frontend replaces Curses frontend<br />
<br />
== Bugs ==<br />
<br />
* vim: insert key should switch to insert mode<br />
* vty: home,end,insert: keys are not correctly supported (this is a vty lib bug (sorear: it works fine on the linux console but fails to handle $TERM. vty 3.1 will wrap ncurses))<br />
* vty: minibuffer windows are normal windows<br />
* gtk: regexp search is not implemented<br />
* gtk: lineup at top of buffer brings to the end of the buffer<br />
* C-e and up/down do not seem to mix well<br />
* killing the last line of a buffer brings the point to the beginning of the buffer<br />
* gtk: upon clicking in textview, remembered column should be reset.<br />
* gtk: impossible to focus the cmdline<br />
* vi: delete (d) seems broken<br />
<br />
== Development plan ==<br />
<br />
Also read: http://www.cse.unsw.edu.au/~dons/yi/TODO<br />
<br />
=== Test suite ===<br />
<br />
The test suite has to be made up to date and re-instated.<br />
<br />
Build test: regular, gtk, and haddock html doc should be buildable at all times.<br />
<br />
=== Refactorings ===<br />
<br />
The below describes possible refactorings to investigate:<br />
<br />
*Keymaps<br />
** Evaluate if we could move to synchronous keymaps<br />
*** Would allow to move to a layered components architecture http://www.cs.uu.nl/research/techreps/UU-CS-2002-030.html<br />
<br />
* Buffers<br />
** All the buffer-only code should not modify the Editor state (ie. should work at the buffer level)<br />
** Duplicating Buffer functions at the Core level by wrapping them in withBuffer is ugly<br />
<br />
=== New features ===<br />
<br />
Roughly by order of easy to do / reverse importance.<br />
<br />
* Window stuff<br />
** Miniwindows (for minibuffers)<br />
** Add option to deactivate line-wrap (and truncate lines instead)<br />
*** gtk: attribute textViewWrapMode<br />
** vty: horizontal scrolling<br />
** Independent window scrolling (without moving the Point)<br />
<br />
* Open multiple windows on a buffer (each with a different point)<br />
<br />
* Buffers<br />
** Do Undo/Redo on the "interactive" transaction boundaries<br />
** Re-think the Buffer interface/implementation (so it supports unicode (utf8), marks, etc.)<br />
** Re-write the FastBuffer so it uses ByteString (or something else) instead of directly the C pointers<br />
*** Look at other possibilities for buffer storage; e.g. Simon Tatham has had success using lazily-constructed size-annotated 2-3-4 trees for editing >10GB files. [http://www.chiark.greenend.org.uk/~sgtatham/tweak/btree.html]<br />
<br />
* Invent/discover a system to have annotated buffers (syntax highlight, interactive content)<br />
<br />
== Yi ideas ==<br />
<br />
This section is meant to gather ideas people have for Yi.<br />
<br />
=== Emacs ===<br />
<br />
Coming from an Emacs background, I think a few things are essential,<br />
mainly the introspection capabilities of Emacs.<br />
<br />
==== Emacs goodness ====<br />
<br />
The following are things I like about Emacs, as an extensible<br />
environment:<br />
; Really good online documentation<br />
: Emacs can tell you a lot about a function or variable with a keypress--- the current value, where it is declared, and a hypertext formation string<br />
<br />
; Extensibility<br />
: All (good) apps allow users to extend, through, e.g., hooks --- a list of functions that are run before/after some event (like saving a file)<br />
<br />
; Integration<br />
: It is really easy in Emacs to have one package interact with another. Thus, I can, e.g., insert a new appointment from my mail app into the diary. <br />
<br />
; Everything is One Language<br />
: Ignoring the actual language (Lisp!), everything is handled in a uniform language --- from binding keys to writing apps.<br />
<br />
; Easy to start hacking<br />
: I can start playing with the system from the second I start up, and things pretty much work as expected. I.e., I can type a bit of code in, execute it, and the result is displayed in the minibuffer. The good docs help immeasurably.<br />
<br />
; Written for the frequent user<br />
: Lots of key shortcuts (and famous for it). There are still menus, for those who like em, but you aren't forced to pretend you just started using it.<br />
<br />
; A tonne of code<br />
: Well, Haskell has this to some degree. Haskell is (IMHO) much easier to write than ELisp, so maybe people will be encouraged to contribute.<br />
<br />
==== Emacs badness ====<br />
<br />
So, why replace it?:<br />
; ELisp<br />
: Dynamically scoped, Dynamically typed, ugly, old. 'Nuff said<br />
<br />
; What's a Parser?<br />
: A lot of apps in emacs do stuff with text, usually text that is in some language. There is no standard parser (like, e.g. parsec), so a lot of it is ugly handwritten spaghetti. This also means that adding analysis tools isn't really done (or done nicely).<br />
<br />
; ELisp again<br />
: Haskell is a lot cleaner to write, especially because of the large number of libraries.<br />
<br />
==== Emacs maybeness (?) ====<br />
<br />
Some things that are sometimes bad, sometimes good:<br />
<br />
; Everything is a buffer<br />
: Makes some sense, but sometimes doesn't. It is nice to have uniform key bindings do the right thing (e.g., C-Space sets the mark, and the region can then be used, e.g. to delete a sequence of emails in Wl) Sometimes, however, you just want some sort of GUI widget.<br />
: OTOH, having the minibuffer be a special kind of buffer is a good idea.<br />
<br />
; Properties<br />
: It is possible to associate arbitrary properties with symbols. This means you can annotate a symbol and then use that information at a later date<br />
<br />
=== Vi ? ===<br />
<br />
What about vi? I believe we want Yi to subsume vi as well.<br />
<br />
=== Ideas ===<br />
<br />
;An extension to GHCi to support documentation of symbols. <br />
:This seems to be (reasonably) straightforward, as GHCi already has :info. It would mean hacking the type environment (what about values?) to add documentation information. The main problem would seem to be populating this --- maybe hack haddock to produce something from the library docs? I assume that using package GHC uses the parent RTS (package GHC seems to be the way to go, but more investigation is required --- don?)<br />
<br />
;Views on data<br />
:Rather than just editing a file, you would open a view onto the file, i.e. there is no longer a 1-1 correspondence between buffers and files. Why? Well, for aggregate buffers (i.e., editing multiple files in the one view), or for multiple views of a file (e.g. AST and source-level). There would be some primitive ops for editing a buffer (insertChar, delete, etc.), which would then call update functions on anything observing that file.<br />
<br />
;Remote attach so I can work from home, but still use a remote machine<br />
<br />
;Haddock documentation<br />
:(no brainer), maybe associate with .hi files for binaries. <br />
<br />
;A class MiniBufferRead (or PromptingRead) which allows the user to<br />
invoke a function similar to M-x in Emacs, but without requiring<br />
(interactive) <br />
: This means that given f :: String -> Int -> Action, (makeInteractive f) :: Action would prompt the user for a String then an Int and run the corresponding action.<br />
<br />
;Maybe a class YiShow, which all config items must be a member of? This is to emulate describe-variable<br />
<br />
=== Implementation ===<br />
<br />
Considerations:<br />
; Configuration <br />
: Per mode/file/buffer/whatever Monads, or reload/recompile? Or some hybrid? How does this interact with the documentation aspects? Do we want to have separate sorts of symbols a la emacs (describe-function, describe-variable), or is everything a function? I would think that configuration info doesn't change that frequently --- is this globally true though?<br />
:We can probably use a GHCi-like "let". Rebinding a function would then be synonym to assign a variable, thereby achieve unification between functions and variables.<br />
:Also possible: use something similar to the GHCi debugger to "tune" the behavior of some functions.<br />
<br />
; Interface to the runtime<br />
: The scheduler, docs, etc.<br />
<br />
; Introspection of e.g. what processes are running.<br />
: There are already libraries in Haskell for processes, but they don't give Yi any extra information --- we really want a layer on top. <br />
<br />
...<br />
<br />
[[User:Sjw|Sjw]] 09:15, 2 June 2006 (UTC)</div>Stefanhttps://wiki.haskell.org/index.php?title=Performance/GHC&diff=12424Performance/GHC2007-04-05T15:16:26Z<p>Stefan: add a few of my observations</p>
<hr />
<div>{{Performance infobox}}<br />
[[Category:Performance|GHC]] [[Category:GHC]]<br />
Please report any overly-slow GHC-compiled programs. Since [[GHC]] doesn't have any credible competition in the performance department these days it's hard to say what overly-slow means, so just use your judgement! Of course, if a GHC compiled program runs slower than the same program compiled with another Haskell compiler, then it's definitely a bug. Furthermore, if an equivalent OCaml, SML or Clean program is faster, this ''might'' be a bug.<br />
<br />
== Use Optimisation ==<br />
<br />
[Optimise, using <tt>-O</tt> or <tt>-O2</tt>: this is the most basic way to make your program go faster. Compilation time will be slower, especially with <tt>-O2</tt>.<br />
<br />
At present, <tt>-O2</tt> is nearly indistinguishable from <tt>-O</tt>.<br />
<br />
GHCi cannot optimise interpreted code, so when using GHCi, compile critical modules using <tt>-O</tt> or <tt>-O2</tt>, then load them into GHCi.<br />
<br />
Here is a short summary of useful compile time flags:<br />
* <tt>-O</tt>:<br />
* <tt>-O2</tt>:<br />
* Do NOT use <tt>-O3</tt>, it actually gives less optimization than <tt>-O2</tt>, [[http://hackage.haskell.org/trac/ghc/ticket/1261]]<br />
* <tt>-funfolding-use-threshold=16</tt>: demand more inlining.<br />
* <tt>-fexcess-precision</tt>: see [[Performance/Floating_point]]<br />
* <tt>-optc-O3</tt>: Enables a suite of optimizations in the GCC compiler. See the gcc(1) man-page for details. (a C-compiler option).<br />
* <tt>-optc-ffast-math</tt>: A C-compiler option which allows it to be less strict with respect to the standard when compiling IEEE 754 floating point arithmetic. Math operations will not trap if something goes wrong and math operations will assume that NaN and +- Infinity are not in arguments or results. For most practical floating point processing, this is a non-issue and enabling the flag can speed up FP arithmetic by a considerable amount. Also see the gcc(1) man-page. (a C-compiler option).<br />
<br />
Other useful flags:<br />
* <tt>-ddump-simpl > core.txt</tt>: generate core.txt file (see below).<br />
<br />
<br />
== Measuring Performance ==<br />
<br />
The first thing to do is measure the performance of your program, and find out whether all the time is being spent in the garbage collector or not. Run your program with the <tt>+RTS -sstderr</tt> option:<br />
<br />
$ ./clausify 20 +RTS -sstderr<br />
42,764,972 bytes allocated in the heap<br />
6,915,348 bytes copied during GC (scavenged)<br />
360,448 bytes copied during GC (not scavenged)<br />
36,616 bytes maximum residency (7 sample(s))<br />
<br />
81 collections in generation 0 ( 0.07s)<br />
7 collections in generation 1 ( 0.00s)<br />
<br />
2 Mb total memory in use<br />
<br />
INIT time 0.00s ( 0.00s elapsed)<br />
MUT time 0.65s ( 0.94s elapsed)<br />
GC time 0.07s ( 0.06s elapsed)<br />
EXIT time 0.00s ( 0.00s elapsed)<br />
Total time 0.72s ( 1.00s elapsed)<br />
<br />
%GC time 9.7% (6.0% elapsed)<br />
<br />
Alloc rate 65,792,264 bytes per MUT second<br />
<br />
Productivity 90.3% of total user, 65.1% of total elapsed<br />
<br />
This tells you how much time is being spent running the program itself (MUT time), and how much time spent in the garbage collector (GC time). <br />
<br />
If your program is doing a lot of GC, then your first priority should be to check for [[Performance:Space Leaks|Space Leaks]] using [http://www.haskell.org/ghc/docs/latest/html/users_guide/prof-heap.html heap profiling], and then to try to reduce allocations by [http://www.haskell.org/ghc/docs/latest/html/users_guide/prof-time-options.html time and allocation profiling]. <br />
<br />
If you can't reduce the GC cost any further, then using more memory by tweaking the [http://www.haskell.org/ghc/docs/latest/html/users_guide/runtime-control.html#rts-options-gc GC options] will probably help. For example, increasing the default heap size with <tt>+RTS -H128m</tt> will reduce the number of GCs.<br />
<br />
If your program isn't doing too much GC, then you should proceed to [http://www.haskell.org/ghc/docs/latest/html/users_guide/prof-time-options.html time and allocation profiling] to see where the big hitters are.<br />
<br />
== Unboxed types ==<br />
<br />
When you are ''really'' desperate for speed, and you want to get right down to the &ldquo;raw bits.&rdquo; Please see [http://www.haskell.org/ghc/docs/latest/html/users_guide/primitives.html GHC Primitives] for some information about using unboxed types.<br />
<br />
This should be a last resort, however, since unboxed types and primitives are non-portable. Fortunately, it is usually not necessary to resort to using explicit unboxed types and primitives, because GHC's optimiser can do the work for you by inlining operations it knows about, and unboxing strict function arguments (see [[Performance:Strictness]]). Strict and unpacked constructor fields can also help a lot (see [[Performance:Data Types]]). Sometimes GHC needs a little help to generate the right code, so you might have to look at the Core output to see whether your tweaks are actually having the desired effect.<br />
<br />
One thing that can be said for using unboxed types and primitives is that you ''know'' you're writing efficient code, rather than relying on GHC's optimiser to do the right thing, and being at the mercy of changes in GHC's optimiser down the line. This may well be important to you, in which case go for it.<br />
<br />
=== An Example ===<br />
<br />
Usually unboxing is not explicitly required (see the Core tutorial below), however there<br />
are circumstances where you require precise control over how your code is<br />
unboxed. The following program was at one point an entry in the<br />
[http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=ghc&lang2=ghc Great Language Shootout]. <br />
GHC did a good job unboxing the loop, but wouldn't generate the best loop. The<br />
solution was to unbox the loop function by hand, resulting in better code.<br />
<br />
The original code:<br />
<br />
loop :: Int -> Double -> Double<br />
loop d s = if d == 0 then s<br />
else loop (d-1) (s + 1/fromIntegral d)<br />
The hand-unboxed code (note that it is uglier, and harder to read):<br />
<br />
import GHC.Base<br />
import GHC.Float<br />
<br />
loop :: Int# -> Double# -> Double#<br />
loop d s = if d ==# 0# then s <br />
else loop (d -# 1#) (s +## (1.0## /## int2Double# d))<br />
<br />
GHC 6.4.1 compiles the first loop to:<br />
<br />
$wloop :: Int# -> Double# -> Double#<br />
$wloop = \ (ww_s2Ga :: Int#) (ww1_s2Ge :: Double#) -><br />
case Double# ww_s2Ga of wild_XC {<br />
__DEFAULT -><br />
case /## 1.0 (int2Double# wild_XC) of y_a2Cd { <br />
__DEFAULT -> $wloop (-# wild_XC 1) (+## ww1_s2Ge y_a2Cd)<br />
};<br />
0 -> ww1_s2Ge<br />
}<br />
<br />
And the second, unboxed loop is translated to<br />
<br />
loop1 :: Int# -> Double# -> Double#<br />
loop1 = \ (d_a1as :: Int#) (s_a1at :: Double#) -><br />
case Double# d_a1as of wild_B1 {<br />
__DEFAULT -> loop1 (-# wild_B1 1) (+## s_a1at (/## 1.0 (int2Double# wild_B1)));<br />
0 -> s_a1at<br />
}<br />
<br />
which contains 1 less case statement. The second version runs as fast as C, the<br />
first a bit slower. A similar problem was also solved with explicit unboxing in the [http://shootout.alioth.debian.org/gp4/benchmark.php?test=recursive&lang=all recursive benchmark entry].<br />
<br />
== Primops ==<br />
<br />
If you really, really need the speed, and other techniques don't seem to<br />
be helping, programming your code in raw GHC primops can sometimes do<br />
the job. As for unboxed types, you get some guarantees that your code's<br />
performance isn't subject to changes to the GHC optimisations, at the<br />
cost of more unreadable code.<br />
<br />
For example, in an imperative benchmark program a bottleneck was<br />
swapping two values. Raw primops solved the problem:<br />
<br />
swap i j a s =<br />
if i <# j then case readIntOffAddr# a i s of { (# s, x #) -><br />
case readIntOffAddr# a j s of { (# s, y #) -><br />
case writeIntOffAddr# a j x s of { s -><br />
case writeIntOffAddr# a i y s of { s -><br />
swap (i +# 1#) (j -# 1#) a s<br />
}}}}<br />
else (# s, () #)<br />
{-# INLINE swap #-}<br />
<br />
== Inlining ==<br />
<br />
GHC does a lot of inlining, which has a dramatic effect on performance.<br />
<br />
Without -O, GHC does inlining ''within'' a module, but no ''cross-module'' inlining. <br />
<br />
With -O, it does a lot of cross-module inlining. Indeed, generally<br />
speaking GHC will inline ''across'' modules just as much as it does<br />
''within'' modules, with a single large exception. If GHC sees that a<br />
function 'f' is called just once, it inlines it regardless of how big<br />
'f' is. But once 'f' is exported, GHC can never see that it's called<br />
exactly once, even if that later turns out to be the case. This<br />
inline-once optimisation is pretty important in practice. <br />
<br />
So: if you care about performance, do not export functions that are not used outside the module (i.e. use an explicit export list, and keep it as small as possible).<br />
<br />
Sometimes ''explicitly'' inlining critical chunks of code can help.<br />
The INLINE pragma can be used for this purpose; but not for recursive functions, since inlining them forever would obviously be a bad idea.<br />
<br />
If a function you want inlined contains a slow path, it can help a<br />
good deal to seperate the slow path into its own function and NOINLINE<br />
it. <br />
<br />
== Looking at the Core ==<br />
<br />
GHC's compiler intermediate language can be very useful for improving<br />
the performance of your code. Core is a functional language much like a very<br />
stripped down Haskell (by design), so it's still readable, and still purely<br />
functional. The general technique is to iteratively inspect how the critical<br />
functions of your program are compiled to Core, checking that they're compiled<br />
in the most optimal manner. Sometimes GHC doesn't quite manage to unbox your<br />
function arguments, float out common subexpressions, or unfold loops ideally --<br />
but you'll only know if you read the Core.<br />
<br />
References:<br />
* [http://haskell.org/ghc/docs/papers/core.ps.gz An External Representation for the GHC Core Language], Andrew Tolmach<br />
* [http://research.microsoft.com/Users/simonpj/Papers/comp-by-trans-scp.ps.gz A transformation-based optimiser for Haskell], Simon L. Peyton Jones and Andre Santos<br />
* [http://research.microsoft.com/Users/simonpj/Papers/inlining/index.htm Secrets of the Glasgow Haskell Compiler Inliner], Simon L. Peyton Jones and Simon Marlow<br />
* [http://research.microsoft.com/users/simonpj/papers/spineless-tagless-gmachine.ps.gz Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine], Simon L. Peyton Jones<br />
<br />
== Core by Example ==<br />
<br />
Here's a step-by-step guide to optimising a particular program, <br />
the [http://shootout.alioth.debian.org/gp4/benchmark.php?test=partialsums&lang=ghc&id=2 partial-sums problem] from the [http://shootout.alioth.debian.org Great Language Shootout]. We developed a number<br />
of examples on [http://www.haskell.org/hawiki/PartialSumsEntry Haskell shootout entry] page.<br />
<br />
Begin with the naive translation of the Clean entry (which was fairly quick):<br />
Lots of math in a tight loop.<br />
<br />
import System<br />
import Numeric<br />
<br />
main = do n <- getArgs = readIO . head<br />
let sums = loop 1 n 1 0 0 0 0 0 0 0 0 0<br />
fn (s,t) = putStrLn $ (showFFloat (Just 9) s []) ++ "\t" ++ t<br />
mapM_ (fn :: (Double, String) - IO ()) (zip sums names)<br />
<br />
names = ["(2/3)^k", "k^-0.5", "1/k(k+1)", "Flint Hills", "Cookson Hills"<br />
, "Harmonic", "Riemann Zeta", "Alternating Harmonic", "Gregory"]<br />
<br />
loop k n alt a1 a2 a3 a4 a5 a6 a7 a8 a9<br />
| k n = [ a1, a2, a3, a4, a5, a6, a7, a8, a9 ]<br />
| otherwise = loop (k+1) n (-alt)<br />
(a1 + (2/3) ** (k-1))<br />
(a2 + k ** (-0.5))<br />
(a3 + 1 / (k * (k + 1)))<br />
(a4 + 1 / (k*k*k * sin k * sin k))<br />
(a5 + 1 / (k*k*k * cos k * cos k))<br />
(a6 + 1 / k)<br />
(a7 + 1 / (k*k))<br />
(a8 + alt / k)<br />
(a9 + alt / (2 * k - 1))<br />
<br />
Compiled with '''-O2''' it runs. However, the performance is ''really'' bad.<br />
Somewhere greater than 128M heap -- in fact eventually running out of<br />
memory. A classic space leak. So look at the generated Core. <br />
<br />
=== Inspect the Core ===<br />
<br />
The best way to check the Core that GHC generates is with the<br />
'''-ddump-simpl''' flag (dump the results after code simplification, and<br />
after all optimisations are run). The result can be verbose, so pipe it into a pager.<br />
<br />
Looking for the 'loop', we find that it has been compiled to a function with<br />
the following type:<br />
<br />
$sloop_r2U6 :: GHC.Prim.Double#<br />
-> GHC.Float.Double<br />
-> GHC.Float.Double<br />
-> GHC.Float.Double<br />
-> GHC.Float.Double<br />
-> GHC.Float.Double<br />
-> GHC.Float.Double<br />
-> GHC.Float.Double<br />
-> GHC.Float.Double<br />
-> GHC.Float.Double<br />
-> GHC.Float.Double<br />
-> GHC.Prim.Double#<br />
-> [GHC.Float.Double]<br />
<br />
Hmm, I certainly don't want boxed doubles in such a tight loop (boxed values<br />
are represented as pointers to closures on the heap, unboxed values are raw<br />
machine values).<br />
<br />
=== Strictify ===<br />
<br />
The next step then is to encourage GHC to unbox this loop, by providing some<br />
strictness annotations. So rewrite the loop like this:<br />
<br />
loop k n alt a1 a2 a3 a4 a5 a6 a7 a8 a9<br />
| () !k !n !alt !a1 !a2 !a3 !a4 !a5 !a6 !a7 !a8 !a9 !False = undefined<br />
| k > n = [ a1, a2, a3, a4, a5, a6, a7, a8, a9 ]<br />
| otherwise = loop (k+1) n (-alt)<br />
(a1 + (2/3) ** (k-1))<br />
(a2 + k ** (-0.5))<br />
(a3 + 1 / (k * (k + 1)))<br />
(a4 + 1 / (k*k*k * sin k * sin k))<br />
(a5 + 1 / (k*k*k * cos k * cos k))<br />
(a6 + 1 / k)<br />
(a7 + 1 / (k*k))<br />
(a8 + alt / k)<br />
(a9 + alt / (2 * k - 1)) where x ! y = x `seq` y<br />
<br />
Here the first guard is purely a syntactic trick to inform ghc that the<br />
arguments should be strictly evaluated. I've played a little game here, using<br />
'''!''' for '''`seq`''' is reminiscent of the new bang-pattern proposal for<br />
strictness. Let's see how this compiles. Strictifying all args GHC produces an<br />
inner loop of:<br />
<br />
$sloop_r2WS :: GHC.Prim.Double#<br />
-> GHC.Prim.Double#<br />
-> GHC.Prim.Double#<br />
-> GHC.Prim.Double#<br />
-> GHC.Prim.Double#<br />
-> GHC.Prim.Double#<br />
-> GHC.Prim.Double#<br />
-> GHC.Prim.Double#<br />
-> GHC.Prim.Double#<br />
-> GHC.Prim.Double#<br />
-> GHC.Prim.Double#<br />
-> GHC.Prim.Double#<br />
-> [GHC.Float.Double]<br />
<br />
Ah! perfect. Let's see how that runs:<br />
<br />
$ ghc Naive.hs -O2 -no-recomp<br />
$ time ./a.out 2500000<br />
3.000000000 (2/3)^k<br />
3160.817621887 k^-0.5<br />
0.999999600 1/k(k+1)<br />
30.314541510 Flint Hills<br />
42.995233998 Cookson Hills<br />
15.309017155 Harmonic<br />
1.644933667 Riemann Zeta<br />
0.693146981 Alternating Harmonic<br />
0.785398063 Gregory<br />
./a.out 2500000 4.45s user 0.02s system 99% cpu 4.482 total<br />
<br />
=== Crank up the gcc flags ===<br />
<br />
Not too bad. No space leak and quite zippy. But let's see what more can be<br />
done. First, double arithmetic usually (always?) benefits from<br />
-fexcess-precision, and cranking up the flags to gcc:<br />
<br />
paprika$ ghc Naive.hs -O2 -fexcess-precision -optc-O3 -optc-ffast-math -no-recomp<br />
paprika$ time ./a.out 2500000<br />
3.000000000 (2/3)^k<br />
3160.817621887 k^-0.5<br />
0.999999600 1/k(k+1)<br />
30.314541510 Flint Hills<br />
42.995233998 Cookson Hills<br />
15.309017155 Harmonic<br />
1.644933667 Riemann Zeta<br />
0.693146981 Alternating Harmonic<br />
0.785398063 Gregory<br />
./a.out 2500000 3.71s user 0.01s system 99% cpu 3.726 total<br />
<br />
Even better! Now, let's dive into the Core to see if there are any optimisation<br />
opportunites that GHC missed. So add '''-ddump-simpl''' and peruse the output.<br />
<br />
=== Common subexpressions ===<br />
<br />
Looking at the Core, I see firstly that some of the common subexpressions<br />
haven't been factored out:<br />
<br />
case [GHC.Float.Double] GHC.Prim./## 1.0<br />
(GHC.Prim.*## (GHC.Prim.*##<br />
(GHC.Prim.*## (GHC.Prim.*## sc10_s2VS sc10_s2VS) sc10_s2VS)<br />
(GHC.Prim.sinDouble# sc10_s2VS))<br />
(GHC.Prim.sinDouble# sc10_s2VS))<br />
<br />
Multiple calls to '''sin'''. Hmm... And similar for '''cos''' and '''k*k'''. <br />
Simon Peyton-Jones says:<br />
<br />
GHC doesn't do full CSE. It'd be a relatively easy pass for someone to<br />
add, but it can cause space leaks. And it can replace two<br />
strictly-evaluated calls with one lazy thunk:<br />
let { x = case e of ....; y = case e of .... } in ...<br />
==><br />
let { v = e; x = case v of ...; y = case v of ... } in ...<br />
<br />
Instead GHC does "opportunistic CSE". If you have<br />
let x = e in .... let y = e in ....<br />
then it'll discard the duplicate binding. But that's very weak.<br />
<br />
So it looks like we might have to float out the commmon subexpressions by hand.<br />
The inner loop now looks like:<br />
<br />
loop k n alt a1 a2 a3 a4 a5 a6 a7 a8 a9<br />
| () !k !n !alt !a1 !a2 !a3 !a4 !a5 !a6 !a7 !a8 !a9 !False = undefined<br />
| k > n = [ a1, a2, a3, a4, a5, a6, a7, a8, a9 ]<br />
| otherwise = loop (k+1) n (-alt)<br />
(a1 + (2/3) ** (k-1))<br />
(a2 + k ** (-0.5))<br />
(a3 + 1 / (k * (k + 1)))<br />
(a4 + 1 / (k3 * sk * sk))<br />
(a5 + 1 / (k3 * ck * ck))<br />
(a6 + 1 / k)<br />
(a7 + 1 / k2)<br />
(a8 + alt / k)<br />
(a9 + alt / (2 * k - 1))<br />
where sk = sin k<br />
ck = cos k<br />
k2 = k * k<br />
k3 = k2 * k<br />
x ! y = x `seq` y<br />
<br />
looking at the Core shows the sins are now allocated and shared:<br />
<br />
let a9_s2MI :: GHC.Prim.Double#<br />
a9_s2MI = GHC.Prim.sinDouble# sc10_s2Xa<br />
<br />
So the common expressions are floated out, and it now runs:<br />
<br />
paprika$ time ./a.out 2500000 <br />
3160.817621887 k^-0.5<br />
0.999999600 1/k(k+1)<br />
30.314541510 Flint Hills<br />
42.995233998 Cookson Hills<br />
15.309017155 Harmonic<br />
1.644933667 Riemann Zeta<br />
0.693146981 Alternating Harmonic<br />
0.785398063 Gregory<br />
./a.out 2500000 3.29s user 0.00s system 99% cpu 3.290 total<br />
<br />
Faster. So we gained 12% by floating out those common expressions.<br />
<br />
=== Strength reduction ===<br />
<br />
Finally, another trick -- manual <br />
[http://en.wikipedia.org/wiki/Strength_reduction strength reduction]. When I checked the C<br />
entry, it used an integer for the k parameter to the loop, and cast it<br />
to a double for the math each time around, so perhaps we can make it an<br />
Int parameter. Secondly, the alt parameter only has it's sign flipped<br />
each time, so perhaps we can factor out the alt / k arg (it's either 1 /<br />
k or -1 on k), saving a division. Thirdly, '''(k ** (-0.5))''' is just a<br />
slow way of doing a '''sqrt'''.<br />
<br />
The final loop looks like:<br />
<br />
loop i n alt a1 a2 a3 a4 a5 a6 a7 a8 a9<br />
| i !n !alt !a1 !a2 !a3 !a4 !a5 !a6 !a7 !a8 !a9 !False = undefined -- strict<br />
| k > n = [ a1, a2, a3, a4, a5, a6, a7, a8, a9 ]<br />
| otherwise = loop (i+1) n (-alt)<br />
(a1 + (2/3) ** (k-1))<br />
(a2 + 1 / sqrt k)<br />
(a3 + 1 / (k * (k + 1)))<br />
(a4 + 1 / (k3 * sk * sk))<br />
(a5 + 1 / (k3 * ck * ck))<br />
(a6 + dk)<br />
(a7 + 1 / k2)<br />
(a8 + alt * dk)<br />
(a9 + alt / (2 * k - 1))<br />
where k3 = k2*k; k2 = k*k; dk = 1/k; k = fromIntegral i :: Double<br />
sk = sin k; ck = cos k; x!y = x`seq`y<br />
<br />
Checking the generated C code (for another tutorial, perhaps) shows that the<br />
same C operations are generated as the C entry uses.<br />
<br />
And it runs:<br />
$ time ./i 2500000<br />
3.000000200 (2/3)^k<br />
3186.765000000 k^-0.5<br />
0.999852700 1/k(k+1)<br />
30.314493000 Flint Hills<br />
42.995068000 Cookson Hills<br />
15.403683000 Harmonic<br />
1.644725300 Riemann Zeta<br />
0.693137470 Alternating Harmonic<br />
0.785399100 Gregory<br />
./i 2500000 2.37s user 0.01s system 99% cpu 2.389 total<br />
<br />
A big speedup!<br />
<br />
This entry in fact <br />
[http://shootout.alioth.debian.org/gp4/benchmark.php?test=partialsums&lang=all runs] <br />
faster than hand optimised (and vectorised) GCC! And is only slower than<br />
optimised Fortran. Lesson: Haskell can be very, very fast.<br />
<br />
So, by carefully tweaking things, we first squished a space leak, and then<br />
gained another 45%.<br />
<br />
=== Summary ===<br />
<br />
* Manually inspect the Core that is generated<br />
* Use strictness annotations to ensure loops are unboxed<br />
* Watch out for optimisations such as CSE and strength reduction that are missed<br />
* Read the generated C for really tight loops.<br />
* Use -fexcess-precision and -optc-ffast-math for doubles<br />
<br />
== Parameters ==<br />
<br />
On x86 (possibly others), adding parameters to a loop is rather<br />
expensive, and it can be a large win to "hide" your parameters in a<br />
mutable array. (Note that this is the kind of thing quite likely to<br />
change between GHC versions, so measure before using this trick!)<br />
<br />
== Pattern matching ==<br />
<br />
On rare occasions pattern matching can give improvements in code that<br />
needs to repeatedly take apart data structures. This code:<br />
<br />
flop :: Int -> [Int] -> [Int]<br />
flop n xs = rs<br />
where (rs, ys) = fl n xs ys<br />
fl 0 xs ys = (ys, xs)<br />
fl n (x:xs) ys = fl (n-1) xs (x:ys)<br />
<br />
Can be rewritten to be faster (and more ugly) as:<br />
<br />
flop :: Int -> [Int] -> [Int]<br />
flop 2 (x1:x2:xs) = x2:x1:xs<br />
flop 3 (x1:x2:x3:xs) = x3:x2:x1:xs<br />
flop 4 (x1:x2:x3:x4:xs) = x4:x3:x2:x1:xs<br />
flop 5 (x1:x2:x3:x4:x5:xs) = x5:x4:x3:x2:x1:xs<br />
flop 6 (x1:x2:x3:x4:x5:x6:xs) = x6:x5:x4:x3:x2:x1:xs<br />
flop 7 (x1:x2:x3:x4:x5:x6:x7:xs) = x7:x6:x5:x4:x3:x2:x1:xs<br />
flop 8 (x1:x2:x3:x4:x5:x6:x7:x8:xs) = x8:x7:x6:x5:x4:x3:x2:x1:xs<br />
flop 9 (x1:x2:x3:x4:x5:x6:x7:x8:x9:xs) = x9:x8:x7:x6:x5:x4:x3:x2:x1:xs<br />
flop 10 (x1:x2:x3:x4:x5:x6:x7:x8:x9:x10:xs) = x10:x9:x8:x7:x6:x5:x4:x3:x2:x1:xs<br />
flop n xs = rs<br />
where (rs, ys) = fl n xs ys<br />
fl 0 xs ys = (ys, xs)<br />
fl n (x:xs) ys = fl (n-1) xs (x:ys)<br />
<br />
== Arrays ==<br />
<br />
If you are using array access and GHC primops, do not be too eager to<br />
use raw Addr#esses; MutableByteArray# is just as fast and frees you<br />
from memory management.<br />
<br />
== Memory allocation and arrays ==<br />
<br />
When you are allocating arrays, it may help to know a little about GHC's memory allocator. There are lots of deatils in [http://hackage.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage The GHC Commentary]), but here are some useful facts:<br />
<br />
* For larger objects ghc has an allocation granularity of 4k. That is it always uses a multiple of 4k bytes, which can lead to wasteage of up to 4k per array. Furthermore, a byte array has some overhead: it needs one word for the heap cell header and another for the length. So if you allocate a 4k byte array then it uses 8k. So the trick is to allocate 4k - overhead. This is what the Data.ByteString library does<br />
<br />
* GHC allocates memory from the OS in units of a "megablock", currently 1Mbyte. So if you allocate a 1Mb array, the storage manager has to allocate 1Mb + overhead, which will cause it to allocate a 2Mb megablock. The surplus will be returned to the system in the form of free blocks, but if all you do is allocate lots of 1Mb arrays, you'll waste about half the space because there's never enough contiguous free space to contain another 1Mb array. Similar problem for 512k arrays: the storage manager allocates a 1Mb block, and returns slightly less than half of it as free blocks, so each 512k allocation takes a whole new 1Mb block.<br />
<br />
== Rewrite rules ==<br />
<br />
Algebraic properties in your code might be missed by the GHC optimiser.<br />
You can use [[Playing by the rules|user-supplied rewrite rules]] to<br />
teach the compiler to optimise your code using domain-specific<br />
optimisations.</div>Stefanhttps://wiki.haskell.org/index.php?title=Performance/GHC&diff=12423Performance/GHC2007-04-05T14:40:31Z<p>Stefan: Note badness of -O3</p>
<hr />
<div>{{Performance infobox}}<br />
[[Category:Performance|GHC]] [[Category:GHC]]<br />
Please report any overly-slow GHC-compiled programs. Since [[GHC]] doesn't have any credible competition in the performance department these days it's hard to say what overly-slow means, so just use your judgement! Of course, if a GHC compiled program runs slower than the same program compiled with another Haskell compiler, then it's definitely a bug. Furthermore, if an equivalent OCaml, SML or Clean program is faster, this ''might'' be a bug.<br />
<br />
== Use Optimisation ==<br />
<br />
[Optimise, using <tt>-O</tt> or <tt>-O2</tt>: this is the most basic way to make your program go faster. Compilation time will be slower, especially with <tt>-O2</tt>.<br />
<br />
At present, <tt>-O2</tt> is nearly indistinguishable from <tt>-O</tt>.<br />
<br />
GHCi cannot optimise interpreted code, so when using GHCi, compile critical modules using <tt>-O</tt> or <tt>-O2</tt>, then load them into GHCi.<br />
<br />
Here is a short summary of useful compile time flags:<br />
* <tt>-O</tt>:<br />
* <tt>-O2</tt>:<br />
* Do NOT use <tt>-O3</tt>, it actually gives less optimization than <tt>-O2</tt>, [[http://hackage.haskell.org/trac/ghc/ticket/1261]]<br />
* <tt>-funfolding-use-threshold=16</tt>: demand more inlining.<br />
* <tt>-fexcess-precision</tt>: see [[Performance/Floating_point]]<br />
* <tt>-optc-O3</tt>: Enables a suite of optimizations in the GCC compiler. See the gcc(1) man-page for details. (a C-compiler option).<br />
* <tt>-optc-ffast-math</tt>: A C-compiler option which allows it to be less strict with respect to the standard when compiling IEEE 754 floating point arithmetic. Math operations will not trap if something goes wrong and math operations will assume that NaN and +- Infinity are not in arguments or results. For most practical floating point processing, this is a non-issue and enabling the flag can speed up FP arithmetic by a considerable amount. Also see the gcc(1) man-page. (a C-compiler option).<br />
<br />
Other useful flags:<br />
* <tt>-ddump-simpl > core.txt</tt>: generate core.txt file (see below).<br />
<br />
<br />
== Measuring Performance ==<br />
<br />
The first thing to do is measure the performance of your program, and find out whether all the time is being spent in the garbage collector or not. Run your program with the <tt>+RTS -sstderr</tt> option:<br />
<br />
$ ./clausify 20 +RTS -sstderr<br />
42,764,972 bytes allocated in the heap<br />
6,915,348 bytes copied during GC (scavenged)<br />
360,448 bytes copied during GC (not scavenged)<br />
36,616 bytes maximum residency (7 sample(s))<br />
<br />
81 collections in generation 0 ( 0.07s)<br />
7 collections in generation 1 ( 0.00s)<br />
<br />
2 Mb total memory in use<br />
<br />
INIT time 0.00s ( 0.00s elapsed)<br />
MUT time 0.65s ( 0.94s elapsed)<br />
GC time 0.07s ( 0.06s elapsed)<br />
EXIT time 0.00s ( 0.00s elapsed)<br />
Total time 0.72s ( 1.00s elapsed)<br />
<br />
%GC time 9.7% (6.0% elapsed)<br />
<br />
Alloc rate 65,792,264 bytes per MUT second<br />
<br />
Productivity 90.3% of total user, 65.1% of total elapsed<br />
<br />
This tells you how much time is being spent running the program itself (MUT time), and how much time spent in the garbage collector (GC time). <br />
<br />
If your program is doing a lot of GC, then your first priority should be to check for [[Performance:Space Leaks|Space Leaks]] using [http://www.haskell.org/ghc/docs/latest/html/users_guide/prof-heap.html heap profiling], and then to try to reduce allocations by [http://www.haskell.org/ghc/docs/latest/html/users_guide/prof-time-options.html time and allocation profiling]. <br />
<br />
If you can't reduce the GC cost any further, then using more memory by tweaking the [http://www.haskell.org/ghc/docs/latest/html/users_guide/runtime-control.html#rts-options-gc GC options] will probably help. For example, increasing the default heap size with <tt>+RTS -H128m</tt> will reduce the number of GCs.<br />
<br />
If your program isn't doing too much GC, then you should proceed to [http://www.haskell.org/ghc/docs/latest/html/users_guide/prof-time-options.html time and allocation profiling] to see where the big hitters are.<br />
<br />
== Unboxed types ==<br />
<br />
When you are ''really'' desperate for speed, and you want to get right down to the &ldquo;raw bits.&rdquo; Please see [http://www.haskell.org/ghc/docs/latest/html/users_guide/primitives.html GHC Primitives] for some information about using unboxed types.<br />
<br />
This should be a last resort, however, since unboxed types and primitives are non-portable. Fortunately, it is usually not necessary to resort to using explicit unboxed types and primitives, because GHC's optimiser can do the work for you by inlining operations it knows about, and unboxing strict function arguments (see [[Performance:Strictness]]). Strict and unpacked constructor fields can also help a lot (see [[Performance:Data Types]]). Sometimes GHC needs a little help to generate the right code, so you might have to look at the Core output to see whether your tweaks are actually having the desired effect.<br />
<br />
One thing that can be said for using unboxed types and primitives is that you ''know'' you're writing efficient code, rather than relying on GHC's optimiser to do the right thing, and being at the mercy of changes in GHC's optimiser down the line. This may well be important to you, in which case go for it.<br />
<br />
=== An Example ===<br />
<br />
Usually unboxing is not explicitly required (see the Core tutorial below), however there<br />
are circumstances where you require precise control over how your code is<br />
unboxed. The following program was at one point an entry in the<br />
[http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=ghc&lang2=ghc Great Language Shootout]. <br />
GHC did a good job unboxing the loop, but wouldn't generate the best loop. The<br />
solution was to unbox the loop function by hand, resulting in better code.<br />
<br />
The original code:<br />
<br />
loop :: Int -> Double -> Double<br />
loop d s = if d == 0 then s<br />
else loop (d-1) (s + 1/fromIntegral d)<br />
The hand-unboxed code (note that it is uglier, and harder to read):<br />
<br />
import GHC.Base<br />
import GHC.Float<br />
<br />
loop :: Int# -> Double# -> Double#<br />
loop d s = if d ==# 0# then s <br />
else loop (d -# 1#) (s +## (1.0## /## int2Double# d))<br />
<br />
GHC 6.4.1 compiles the first loop to:<br />
<br />
$wloop :: Int# -> Double# -> Double#<br />
$wloop = \ (ww_s2Ga :: Int#) (ww1_s2Ge :: Double#) -><br />
case Double# ww_s2Ga of wild_XC {<br />
__DEFAULT -><br />
case /## 1.0 (int2Double# wild_XC) of y_a2Cd { <br />
__DEFAULT -> $wloop (-# wild_XC 1) (+## ww1_s2Ge y_a2Cd)<br />
};<br />
0 -> ww1_s2Ge<br />
}<br />
<br />
And the second, unboxed loop is translated to<br />
<br />
loop1 :: Int# -> Double# -> Double#<br />
loop1 = \ (d_a1as :: Int#) (s_a1at :: Double#) -><br />
case Double# d_a1as of wild_B1 {<br />
__DEFAULT -> loop1 (-# wild_B1 1) (+## s_a1at (/## 1.0 (int2Double# wild_B1)));<br />
0 -> s_a1at<br />
}<br />
<br />
which contains 1 less case statement. The second version runs as fast as C, the<br />
first a bit slower. A similar problem was also solved with explicit unboxing in the [http://shootout.alioth.debian.org/gp4/benchmark.php?test=recursive&lang=all recursive benchmark entry].<br />
<br />
== Primops ==<br />
<br />
If you really, really need the speed, and other techniques don't seem to<br />
be helping, programming your code in raw GHC primops can sometimes do<br />
the job. As for unboxed types, you get some guarantees that your code's<br />
performance isn't subject to changes to the GHC optimisations, at the<br />
cost of more unreadable code.<br />
<br />
For example, in an imperative benchmark program a bottleneck was<br />
swapping two values. Raw primops solved the problem:<br />
<br />
swap i j a s =<br />
if i <# j then case readIntOffAddr# a i s of { (# s, x #) -><br />
case readIntOffAddr# a j s of { (# s, y #) -><br />
case writeIntOffAddr# a j x s of { s -><br />
case writeIntOffAddr# a i y s of { s -><br />
swap (i +# 1#) (j -# 1#) a s<br />
}}}}<br />
else (# s, () #)<br />
{-# INLINE swap #-}<br />
<br />
== Inlining ==<br />
<br />
GHC does a lot of inlining, which has a dramatic effect on performance.<br />
<br />
Without -O, GHC does inlining ''within'' a module, but no ''cross-module'' inlining. <br />
<br />
With -O, it does a lot of cross-module inlining. Indeed, generally speaking GHC will inline ''across'' modules just as much as<br />
it does ''within'' modules, with a single large exception.<br />
If GHC sees that a function 'f' is called just once, it inlines it<br />
regardless of how big 'f' is. But once 'f' is exported, GHC can<br />
never see that it's called exactly once, even if that later turns out<br />
to be the case. This inline-once optimisation is pretty important<br />
in practice.<br />
<br />
So: if you care about performance, do not export functions that are not used outside the module (i.e. use an explicit export list, and keep it as small as possible).<br />
<br />
Sometimes ''explicitly'' inlining critical chunks of code can help.<br />
The INLINE pragma can be used for this purpose; but not for recursive functions, since inlining them forever would obviously be a bad idea.<br />
<br />
== Looking at the Core ==<br />
<br />
GHC's compiler intermediate language can be very useful for improving<br />
the performance of your code. Core is a functional language much like a very<br />
stripped down Haskell (by design), so it's still readable, and still purely<br />
functional. The general technique is to iteratively inspect how the critical<br />
functions of your program are compiled to Core, checking that they're compiled<br />
in the most optimal manner. Sometimes GHC doesn't quite manage to unbox your<br />
function arguments, float out common subexpressions, or unfold loops ideally --<br />
but you'll only know if you read the Core.<br />
<br />
References:<br />
* [http://haskell.org/ghc/docs/papers/core.ps.gz An External Representation for the GHC Core Language], Andrew Tolmach<br />
* [http://research.microsoft.com/Users/simonpj/Papers/comp-by-trans-scp.ps.gz A transformation-based optimiser for Haskell], Simon L. Peyton Jones and Andre Santos<br />
* [http://research.microsoft.com/Users/simonpj/Papers/inlining/index.htm Secrets of the Glasgow Haskell Compiler Inliner], Simon L. Peyton Jones and Simon Marlow<br />
* [http://research.microsoft.com/users/simonpj/papers/spineless-tagless-gmachine.ps.gz Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine], Simon L. Peyton Jones<br />
<br />
== Core by Example ==<br />
<br />
Here's a step-by-step guide to optimising a particular program, <br />
the [http://shootout.alioth.debian.org/gp4/benchmark.php?test=partialsums&lang=ghc&id=2 partial-sums problem] from the [http://shootout.alioth.debian.org Great Language Shootout]. We developed a number<br />
of examples on [http://www.haskell.org/hawiki/PartialSumsEntry Haskell shootout entry] page.<br />
<br />
Begin with the naive translation of the Clean entry (which was fairly quick):<br />
Lots of math in a tight loop.<br />
<br />
import System<br />
import Numeric<br />
<br />
main = do n <- getArgs = readIO . head<br />
let sums = loop 1 n 1 0 0 0 0 0 0 0 0 0<br />
fn (s,t) = putStrLn $ (showFFloat (Just 9) s []) ++ "\t" ++ t<br />
mapM_ (fn :: (Double, String) - IO ()) (zip sums names)<br />
<br />
names = ["(2/3)^k", "k^-0.5", "1/k(k+1)", "Flint Hills", "Cookson Hills"<br />
, "Harmonic", "Riemann Zeta", "Alternating Harmonic", "Gregory"]<br />
<br />
loop k n alt a1 a2 a3 a4 a5 a6 a7 a8 a9<br />
| k n = [ a1, a2, a3, a4, a5, a6, a7, a8, a9 ]<br />
| otherwise = loop (k+1) n (-alt)<br />
(a1 + (2/3) ** (k-1))<br />
(a2 + k ** (-0.5))<br />
(a3 + 1 / (k * (k + 1)))<br />
(a4 + 1 / (k*k*k * sin k * sin k))<br />
(a5 + 1 / (k*k*k * cos k * cos k))<br />
(a6 + 1 / k)<br />
(a7 + 1 / (k*k))<br />
(a8 + alt / k)<br />
(a9 + alt / (2 * k - 1))<br />
<br />
Compiled with '''-O2''' it runs. However, the performance is ''really'' bad.<br />
Somewhere greater than 128M heap -- in fact eventually running out of<br />
memory. A classic space leak. So look at the generated Core. <br />
<br />
=== Inspect the Core ===<br />
<br />
The best way to check the Core that GHC generates is with the<br />
'''-ddump-simpl''' flag (dump the results after code simplification, and<br />
after all optimisations are run). The result can be verbose, so pipe it into a pager.<br />
<br />
Looking for the 'loop', we find that it has been compiled to a function with<br />
the following type:<br />
<br />
$sloop_r2U6 :: GHC.Prim.Double#<br />
-> GHC.Float.Double<br />
-> GHC.Float.Double<br />
-> GHC.Float.Double<br />
-> GHC.Float.Double<br />
-> GHC.Float.Double<br />
-> GHC.Float.Double<br />
-> GHC.Float.Double<br />
-> GHC.Float.Double<br />
-> GHC.Float.Double<br />
-> GHC.Float.Double<br />
-> GHC.Prim.Double#<br />
-> [GHC.Float.Double]<br />
<br />
Hmm, I certainly don't want boxed doubles in such a tight loop (boxed values<br />
are represented as pointers to closures on the heap, unboxed values are raw<br />
machine values).<br />
<br />
=== Strictify ===<br />
<br />
The next step then is to encourage GHC to unbox this loop, by providing some<br />
strictness annotations. So rewrite the loop like this:<br />
<br />
loop k n alt a1 a2 a3 a4 a5 a6 a7 a8 a9<br />
| () !k !n !alt !a1 !a2 !a3 !a4 !a5 !a6 !a7 !a8 !a9 !False = undefined<br />
| k > n = [ a1, a2, a3, a4, a5, a6, a7, a8, a9 ]<br />
| otherwise = loop (k+1) n (-alt)<br />
(a1 + (2/3) ** (k-1))<br />
(a2 + k ** (-0.5))<br />
(a3 + 1 / (k * (k + 1)))<br />
(a4 + 1 / (k*k*k * sin k * sin k))<br />
(a5 + 1 / (k*k*k * cos k * cos k))<br />
(a6 + 1 / k)<br />
(a7 + 1 / (k*k))<br />
(a8 + alt / k)<br />
(a9 + alt / (2 * k - 1)) where x ! y = x `seq` y<br />
<br />
Here the first guard is purely a syntactic trick to inform ghc that the<br />
arguments should be strictly evaluated. I've played a little game here, using<br />
'''!''' for '''`seq`''' is reminiscent of the new bang-pattern proposal for<br />
strictness. Let's see how this compiles. Strictifying all args GHC produces an<br />
inner loop of:<br />
<br />
$sloop_r2WS :: GHC.Prim.Double#<br />
-> GHC.Prim.Double#<br />
-> GHC.Prim.Double#<br />
-> GHC.Prim.Double#<br />
-> GHC.Prim.Double#<br />
-> GHC.Prim.Double#<br />
-> GHC.Prim.Double#<br />
-> GHC.Prim.Double#<br />
-> GHC.Prim.Double#<br />
-> GHC.Prim.Double#<br />
-> GHC.Prim.Double#<br />
-> GHC.Prim.Double#<br />
-> [GHC.Float.Double]<br />
<br />
Ah! perfect. Let's see how that runs:<br />
<br />
$ ghc Naive.hs -O2 -no-recomp<br />
$ time ./a.out 2500000<br />
3.000000000 (2/3)^k<br />
3160.817621887 k^-0.5<br />
0.999999600 1/k(k+1)<br />
30.314541510 Flint Hills<br />
42.995233998 Cookson Hills<br />
15.309017155 Harmonic<br />
1.644933667 Riemann Zeta<br />
0.693146981 Alternating Harmonic<br />
0.785398063 Gregory<br />
./a.out 2500000 4.45s user 0.02s system 99% cpu 4.482 total<br />
<br />
=== Crank up the gcc flags ===<br />
<br />
Not too bad. No space leak and quite zippy. But let's see what more can be<br />
done. First, double arithmetic usually (always?) benefits from<br />
-fexcess-precision, and cranking up the flags to gcc:<br />
<br />
paprika$ ghc Naive.hs -O2 -fexcess-precision -optc-O3 -optc-ffast-math -no-recomp<br />
paprika$ time ./a.out 2500000<br />
3.000000000 (2/3)^k<br />
3160.817621887 k^-0.5<br />
0.999999600 1/k(k+1)<br />
30.314541510 Flint Hills<br />
42.995233998 Cookson Hills<br />
15.309017155 Harmonic<br />
1.644933667 Riemann Zeta<br />
0.693146981 Alternating Harmonic<br />
0.785398063 Gregory<br />
./a.out 2500000 3.71s user 0.01s system 99% cpu 3.726 total<br />
<br />
Even better! Now, let's dive into the Core to see if there are any optimisation<br />
opportunites that GHC missed. So add '''-ddump-simpl''' and peruse the output.<br />
<br />
=== Common subexpressions ===<br />
<br />
Looking at the Core, I see firstly that some of the common subexpressions<br />
haven't been factored out:<br />
<br />
case [GHC.Float.Double] GHC.Prim./## 1.0<br />
(GHC.Prim.*## (GHC.Prim.*##<br />
(GHC.Prim.*## (GHC.Prim.*## sc10_s2VS sc10_s2VS) sc10_s2VS)<br />
(GHC.Prim.sinDouble# sc10_s2VS))<br />
(GHC.Prim.sinDouble# sc10_s2VS))<br />
<br />
Multiple calls to '''sin'''. Hmm... And similar for '''cos''' and '''k*k'''. <br />
Simon Peyton-Jones says:<br />
<br />
GHC doesn't do full CSE. It'd be a relatively easy pass for someone to<br />
add, but it can cause space leaks. And it can replace two<br />
strictly-evaluated calls with one lazy thunk:<br />
let { x = case e of ....; y = case e of .... } in ...<br />
==><br />
let { v = e; x = case v of ...; y = case v of ... } in ...<br />
<br />
Instead GHC does "opportunistic CSE". If you have<br />
let x = e in .... let y = e in ....<br />
then it'll discard the duplicate binding. But that's very weak.<br />
<br />
So it looks like we might have to float out the commmon subexpressions by hand.<br />
The inner loop now looks like:<br />
<br />
loop k n alt a1 a2 a3 a4 a5 a6 a7 a8 a9<br />
| () !k !n !alt !a1 !a2 !a3 !a4 !a5 !a6 !a7 !a8 !a9 !False = undefined<br />
| k > n = [ a1, a2, a3, a4, a5, a6, a7, a8, a9 ]<br />
| otherwise = loop (k+1) n (-alt)<br />
(a1 + (2/3) ** (k-1))<br />
(a2 + k ** (-0.5))<br />
(a3 + 1 / (k * (k + 1)))<br />
(a4 + 1 / (k3 * sk * sk))<br />
(a5 + 1 / (k3 * ck * ck))<br />
(a6 + 1 / k)<br />
(a7 + 1 / k2)<br />
(a8 + alt / k)<br />
(a9 + alt / (2 * k - 1))<br />
where sk = sin k<br />
ck = cos k<br />
k2 = k * k<br />
k3 = k2 * k<br />
x ! y = x `seq` y<br />
<br />
looking at the Core shows the sins are now allocated and shared:<br />
<br />
let a9_s2MI :: GHC.Prim.Double#<br />
a9_s2MI = GHC.Prim.sinDouble# sc10_s2Xa<br />
<br />
So the common expressions are floated out, and it now runs:<br />
<br />
paprika$ time ./a.out 2500000 <br />
3160.817621887 k^-0.5<br />
0.999999600 1/k(k+1)<br />
30.314541510 Flint Hills<br />
42.995233998 Cookson Hills<br />
15.309017155 Harmonic<br />
1.644933667 Riemann Zeta<br />
0.693146981 Alternating Harmonic<br />
0.785398063 Gregory<br />
./a.out 2500000 3.29s user 0.00s system 99% cpu 3.290 total<br />
<br />
Faster. So we gained 12% by floating out those common expressions.<br />
<br />
=== Strength reduction ===<br />
<br />
Finally, another trick -- manual <br />
[http://en.wikipedia.org/wiki/Strength_reduction strength reduction]. When I checked the C<br />
entry, it used an integer for the k parameter to the loop, and cast it<br />
to a double for the math each time around, so perhaps we can make it an<br />
Int parameter. Secondly, the alt parameter only has it's sign flipped<br />
each time, so perhaps we can factor out the alt / k arg (it's either 1 /<br />
k or -1 on k), saving a division. Thirdly, '''(k ** (-0.5))''' is just a<br />
slow way of doing a '''sqrt'''.<br />
<br />
The final loop looks like:<br />
<br />
loop i n alt a1 a2 a3 a4 a5 a6 a7 a8 a9<br />
| i !n !alt !a1 !a2 !a3 !a4 !a5 !a6 !a7 !a8 !a9 !False = undefined -- strict<br />
| k > n = [ a1, a2, a3, a4, a5, a6, a7, a8, a9 ]<br />
| otherwise = loop (i+1) n (-alt)<br />
(a1 + (2/3) ** (k-1))<br />
(a2 + 1 / sqrt k)<br />
(a3 + 1 / (k * (k + 1)))<br />
(a4 + 1 / (k3 * sk * sk))<br />
(a5 + 1 / (k3 * ck * ck))<br />
(a6 + dk)<br />
(a7 + 1 / k2)<br />
(a8 + alt * dk)<br />
(a9 + alt / (2 * k - 1))<br />
where k3 = k2*k; k2 = k*k; dk = 1/k; k = fromIntegral i :: Double<br />
sk = sin k; ck = cos k; x!y = x`seq`y<br />
<br />
Checking the generated C code (for another tutorial, perhaps) shows that the<br />
same C operations are generated as the C entry uses.<br />
<br />
And it runs:<br />
$ time ./i 2500000<br />
3.000000200 (2/3)^k<br />
3186.765000000 k^-0.5<br />
0.999852700 1/k(k+1)<br />
30.314493000 Flint Hills<br />
42.995068000 Cookson Hills<br />
15.403683000 Harmonic<br />
1.644725300 Riemann Zeta<br />
0.693137470 Alternating Harmonic<br />
0.785399100 Gregory<br />
./i 2500000 2.37s user 0.01s system 99% cpu 2.389 total<br />
<br />
A big speedup!<br />
<br />
This entry in fact <br />
[http://shootout.alioth.debian.org/gp4/benchmark.php?test=partialsums&lang=all runs] <br />
faster than hand optimised (and vectorised) GCC! And is only slower than<br />
optimised Fortran. Lesson: Haskell can be very, very fast.<br />
<br />
So, by carefully tweaking things, we first squished a space leak, and then<br />
gained another 45%.<br />
<br />
=== Summary ===<br />
<br />
* Manually inspect the Core that is generated<br />
* Use strictness annotations to ensure loops are unboxed<br />
* Watch out for optimisations such as CSE and strength reduction that are missed<br />
* Read the generated C for really tight loops.<br />
* Use -fexcess-precision and -optc-ffast-math for doubles<br />
<br />
== Pattern matching ==<br />
<br />
On rare occasions pattern matching can give improvements in code that<br />
needs to repeatedly take apart data structures. This code:<br />
<br />
flop :: Int -> [Int] -> [Int]<br />
flop n xs = rs<br />
where (rs, ys) = fl n xs ys<br />
fl 0 xs ys = (ys, xs)<br />
fl n (x:xs) ys = fl (n-1) xs (x:ys)<br />
<br />
Can be rewritten to be faster (and more ugly) as:<br />
<br />
flop :: Int -> [Int] -> [Int]<br />
flop 2 (x1:x2:xs) = x2:x1:xs<br />
flop 3 (x1:x2:x3:xs) = x3:x2:x1:xs<br />
flop 4 (x1:x2:x3:x4:xs) = x4:x3:x2:x1:xs<br />
flop 5 (x1:x2:x3:x4:x5:xs) = x5:x4:x3:x2:x1:xs<br />
flop 6 (x1:x2:x3:x4:x5:x6:xs) = x6:x5:x4:x3:x2:x1:xs<br />
flop 7 (x1:x2:x3:x4:x5:x6:x7:xs) = x7:x6:x5:x4:x3:x2:x1:xs<br />
flop 8 (x1:x2:x3:x4:x5:x6:x7:x8:xs) = x8:x7:x6:x5:x4:x3:x2:x1:xs<br />
flop 9 (x1:x2:x3:x4:x5:x6:x7:x8:x9:xs) = x9:x8:x7:x6:x5:x4:x3:x2:x1:xs<br />
flop 10 (x1:x2:x3:x4:x5:x6:x7:x8:x9:x10:xs) = x10:x9:x8:x7:x6:x5:x4:x3:x2:x1:xs<br />
flop n xs = rs<br />
where (rs, ys) = fl n xs ys<br />
fl 0 xs ys = (ys, xs)<br />
fl n (x:xs) ys = fl (n-1) xs (x:ys)<br />
<br />
== Memory allocation and arrays ==<br />
<br />
When you are allocating arrays, it may help to know a little about GHC's memory allocator. There are lots of deatils in [http://hackage.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage The GHC Commentary]), but here are some useful facts:<br />
<br />
* For larger objects ghc has an allocation granularity of 4k. That is it always uses a multiple of 4k bytes, which can lead to wasteage of up to 4k per array. Furthermore, a byte array has some overhead: it needs one word for the heap cell header and another for the length. So if you allocate a 4k byte array then it uses 8k. So the trick is to allocate 4k - overhead. This is what the Data.ByteString library does<br />
<br />
* GHC allocates memory from the OS in units of a "megablock", currently 1Mbyte. So if you allocate a 1Mb array, the storage manager has to allocate 1Mb + overhead, which will cause it to allocate a 2Mb megablock. The surplus will be returned to the system in the form of free blocks, but if all you do is allocate lots of 1Mb arrays, you'll waste about half the space because there's never enough contiguous free space to contain another 1Mb array. Similar problem for 512k arrays: the storage manager allocates a 1Mb block, and returns slightly less than half of it as free blocks, so each 512k allocation takes a whole new 1Mb block.<br />
<br />
== Rewrite rules ==<br />
<br />
Algebraic properties in your code might be missed by the GHC optimiser.<br />
You can use [[Playing by the rules|user-supplied rewrite rules]] to<br />
teach the compiler to optimise your code using domain-specific<br />
optimisations.</div>Stefanhttps://wiki.haskell.org/index.php?title=Yhc/TMR&diff=12187Yhc/TMR2007-03-22T14:04:19Z<p>Stefan: /* Integration with DOM */ speling fix (fantom -> phantom)</p>
<hr />
<div>Authors: Neil Mitchell, Tom Shackell, Matt Naylor, Dimitry Golubovsky, Andrew Wilkinson<br />
<br />
This is a draft of the Yhc TMR article, deadline April 13th. It isn't intended as a wiki article beyond the listed authors (although if you want to fix some spelling, we don't mind!). If you are interested in helping email the Yhc list.<br />
<br />
== The beginning ==<br />
<br />
In the beginning there was the nhc compiler, which had a number of issues. We fixed some of them.<br />
<br />
Author: Tom/Neil/Andrew<br />
<br />
How we started up Yhc, this is the section that would have been in the History of Haskell paper if they had done a Yhc section :)<br />
<br />
Include the transition from CVS -> york Darcs -> haskell.org Darcs<br />
<br />
== Portability concerns ==<br />
<br />
From the beginning portability was a prime concern, while the original nhc was only running on Linux v old.old, and never Windows, Yhc was fully portable by design.<br />
<br />
Author: Tom, Andrew<br />
<br />
Why portability is such a concern, details of our ports system. Include our scons architecture, buildbot system etc. Mention that Yhc runs under Hugs, and indeed some of the developers use Hugs.<br />
<br />
== Why the front end must die: Libraries for All ==<br />
<br />
Lots of the nhc features are pure evil. We should rewrite them to move forward, making the compiler more compliant and more friendly for all. Libraries would be a good strategy.<br />
<br />
Author: Neil/Tom<br />
<br />
Our thoughts on the future, kill the front end and turn everything into a library. Keep the compiler light weight, <br />
<br />
== Yhc.Core ==<br />
<br />
Yhc.Core is one area we have already moved into the library field, and its getting used quite a lot.<br />
<br />
Author: Neil (with bits from Matt, Dimitry)<br />
<br />
Why Yhc.Core is so very important, a list of the projects that use it. Why Yhc Core is better than GHC Core - i.e. the only option left around.<br />
<br />
Here is a simple Yhc.Core evaluator:<br />
<br />
<haskell><br />
import System<br />
import Yhc.Core<br />
<br />
norm :: CoreExpr -> CoreExpr<br />
norm (CoreCon c) = CoreApp (CoreCon c) []<br />
norm x = x<br />
<br />
try :: CoreExpr -> (CoreExpr, CoreExpr) -> [CoreExpr]<br />
try e (pat, rhs) = case (norm e, norm pat) of<br />
(CoreApp (CoreCon f) as, CoreApp (CoreCon g) bs)<br />
| f == g -> [CoreLet (zip (vars bs) as) rhs]<br />
(e, CoreVar v) -> [CoreLet [(v,e)] rhs]<br />
(a,b)<br />
| isCoreConst a && a == b -> [rhs]<br />
_ -> []<br />
where<br />
vars = map fromCoreVar<br />
<br />
match :: CoreExpr -> [(CoreExpr, CoreExpr)] -> CoreExpr<br />
match e as = head (concatMap (try (norm e)) as)<br />
<br />
hnf :: Core -> CoreExpr -> CoreExpr<br />
hnf p (CoreCase e as) = hnf p (match (hnf p e) as)<br />
hnf p (CoreLet ds e) = hnf p (replaceFreeVars ds e)<br />
hnf p (CoreCon c) = CoreCon c<br />
hnf p (CoreFun f) = hnf p (CoreLam bs body)<br />
where<br />
CoreFunc _ bs body = coreFunc p f<br />
hnf p (CoreLam [] e) = hnf p e<br />
hnf p (CoreApp (CoreCon c) as) = CoreApp (CoreCon c) as<br />
hnf p (CoreApp f []) = hnf p f<br />
hnf p (CoreApp f (a:as)) =<br />
case hnf p f of<br />
CoreLam [] e -> hnf p (CoreApp e (a:as))<br />
CoreLam (b:bs) e -> hnf p (CoreLet [(b,a)] (CoreApp<br />
(CoreLam bs e) as))<br />
hnf p (CorePos _ e) = hnf p e<br />
hnf p e = e<br />
<br />
nf :: Core -> CoreExpr -> CoreExpr<br />
nf p e = case hnf p e of<br />
CoreCon c -> CoreCon c<br />
CoreApp (CoreCon c) es -> CoreApp (CoreCon c) (map (nf p) es)<br />
e -> e<br />
<br />
main = do [filename] <- getArgs<br />
core <- loadCore filename<br />
let core' = removeRecursiveLet core<br />
print (nf core' (CoreFun "main"))<br />
</haskell><br />
<br />
<br />
== Javascript backend ==<br />
<br />
The Javascript backend is a unique feature of Yhc, something which our light weight approach makes easier.<br />
<br />
Author: Dimitry<br />
<br />
<small>the ideas behind it, the Javascript FFI, browser compatability, the approach</small><br />
<br />
The idea to write a converter from Haskell to Javascript has been floating around for a while [add links]. Many people expressed interest in such feature, but no practical implementation was visible.<br />
<br />
=== General concepts ===<br />
<br />
The Javascript backend converts a linked and optimized Yhc Core file into a piece of Javascript code to be embedded in a XHTML document. The Javascript code generator attempts to translate Core expressions to Javascript expressions one-to-one with minor optimizations on its own, taking advantage of Javascript capability to pass functions around as values.<br />
<br />
Three kinds of functions are present in the Javascript backend:<br />
<br />
* Unsafe functions that embed pieces of Javascript directly into the generated code: these functions pay no respect to types of arguments passed, and may force evaluation of their arguments if needed.<br />
<br />
* Typesafe wrappers that provide type signatures for unsafe functions. Such wrappers are either handwritten, or automatically generated from external interface specifications (such as the Document Object Model interface)<br />
<br />
* Regular library functions. These either come unmodified from the standard packages that come with Yhc, or are substituted by the Javascript backend using the Core overlay technique. An example of such a function is the <tt>toUpper</tt> function which is hooked up to the Javascript implementation supporting Unicode (the original library function currently works correctly only for the Latin1 range of characters).<br />
<br />
==== Unsafe interfaces ====<br />
<br />
The core part of unsafe interface to Javascript (or, in other words, Javascript FFI) is a pseudo-function <tt>unsafeJS</tt>.<br />
<br />
The function has a type signature: <br />
<br />
<hask><br />
foreign import primitive unsafeJS :: String -> a<br />
</hask><br />
<br />
Which means that it takes a string. Type of the return value does not matter: the function itself is never executed. Its applications are detected by ycr2js at the time of Javascript generation. <br />
<br />
The unsafeJS function should be called with a string literal. Neither explicitly coded (with (:)) list of characters nor concatenation of two or more strings will work. The converter will report an error in this situation. <br />
<br />
A valid example of using unsafeJS is shown below: <br />
<br />
<haskell><br />
global_YHC'_Primitive'_primIntSignum :: Int -> Int<br />
<br />
global_YHC'_Primitive'_primIntSignum a = unsafeJS<br />
"var ea = exprEval(a); if (ea>0) return 1; else if (ea<0) return -1; else return 0;"<br />
</haskell><br />
<br />
This is a Javascript overlay (in the sense that it overlays the default Prelude definition of the <hask>signum</hask> function) of a function that returns sign of an <hask>Int</hask> value. <br />
<br />
The string literal <tt>unsafeJS</tt> is applied to is the Javascript code to be wrapped. <br />
<br />
Below is the Javascript representation of this function found in generated code. <br />
<br />
<pre><br />
strIdx["F_hy"] = "YHC.Primitive.primIntSignum";<br />
...<br />
var F_hy=new HSFun("F_hy", 1, function(a){<br />
var ea = exprEval(a); if (ea>0) return 1; else if (ea<0) return -1; else return 0;});<br />
</pre><br />
<br />
==== Typesafe wrappers ====<br />
<br />
These functions add type safety on top of unsafe interface to Javascript. Sometimes they are defined within the same module as unsafe interfaces themselves, thus avoiding the exposure of unsafe interfaces to programmers.<br />
<br />
An example of a handwritten wrapper is a function to create a new <tt>JSRef</tt> (a mechanism similar to <hask>IORef</hask>, but specific to Javascript).<br />
<br />
<haskell><br />
data JSRef a<br />
<br />
newJSRef :: a -> CPS b (JSRef a)<br />
<br />
newJSRef a = toCPE (newJSRef' a)<br />
newJSRef' a = unsafeJS "return {_val:a};"<br />
</haskell><br />
<br />
Technically, a <tt>JSRef</tt> is a Javascript object with a property named ''_val'' that holds a persistent reference to some value. On the unsafe side, invoking a constructor for such an object would be sufficient. It is however desired that:<br />
<br />
* calls to functions creating such persistent references are properly sequenced with calls to funcitons using these references, and<br />
<br />
* type of values referred to were known to the Haskell compiler.<br />
<br />
The unsafe part is implemented by the function <tt>newJSRef'</tt> which merely calls <tt>unsafeJS</tt> with proper Javascript constructor. The wrapper part <tt>newJSRef</tt> wraps the unsafe function into a CPS-style function, and is given a proper type signature, so the compiler is better informed.<br />
<br />
In some cases, such typesafe wrappers may be generated automatically, using some external interface specifications provided by third parties for their APIs.<br />
<br />
As an example of such API, the W3C DOM interface may be taken. For instance, this piece of OMG IDL:<br />
<br />
<pre><br />
interface Text : CharacterData {<br />
Text splitText(in unsigned long offset)<br />
raises(DOMException);<br />
};<br />
</pre><br />
<br />
is converted into:<br />
<br />
<haskell><br />
data TText = TText<br />
<br />
...<br />
<br />
instance CText TText<br />
<br />
instance CCharacterData TText<br />
<br />
instance CNode TText<br />
<br />
...<br />
<br />
splitText :: (CText this, CText zz) => this -> Int -> CPS c zz<br />
splitText a b = toCPE (splitText' a b)<br />
splitText' a b<br />
= unsafeJS "return((exprEval(a)).splitText(exprEval(b)));"<br />
</haskell><br />
<br />
again, giving the Haskell compiler better control over types of this function's (initially type-agnostic) arguments.<br />
<br />
=== Usage of Continuation Passing Style ===<br />
<br />
Initially it was attempted to build a monadic framework. The <hask>JS</hask> monad was designed to play the same role as the <hask>IO</hask> monad plays in "regular" Haskell programming. There were however arguments in favor of using CPS style:<br />
<br />
* CPS style involves less overhead as each expression passes its continustion iself instead of <hask>bind</hask> which takes the expression and invokes the continuation<br />
<br />
* CPS style results in Javascript patterns that are easy to detect and optimize for (this is one of the future plans).<br />
<br />
* The Fudgets library internals are written in CPS style, so taking CPS as general approach to programming is believed to make adoption of Fudgets easier.<br />
<br />
=== Integration with DOM ===<br />
<br />
The Web Consortium provides OMG IDL files to describe the API to use with the Document Object Model (DOM). An utility was designed, based on HaskellDirect, to parse these files and convert them to set of Haskell modules. The way interface inheritance is reflected differs from the original HaskellDirect way: in HaskellDirect this was achieved by declaration of "nested" algebraic data types, while the Javascript backend utility takes advantage of Haskell typeclasses, representing DOM types with phantom types, and declaring them instances of appropriate class(es).<br />
<br />
=== Unicode support ===<br />
<br />
Despite the fact that all modern Web browsers support Unicode, this is not the case with Javascript: no access to Unicode characters' properties is provided. In the same time it is impossible for a Haskell application running in a browser not to have access to such information. The approach used is the same as used in Hugs and GHC: the Unicode characters database file from Unicode Consortium was converted into a set of Javascript arrays, each array entry representing a range of character code values, or a case conversion rule for a range (for this implementation, Unicode support was limited to character category, and simple case conversions). First, a range is found by character code using binary search; then character category and case conversion distances (values to add to character core to convert between upper and lower cases) are retrieved from the range entry. The whole set of arrays adds about 70 kilobytes to the web page size, if embedded inside a &lt;script&gt; tag.<br />
<br />
Using the Core overlay technique, Haskell character functions (like <tt>toUpper</tt>, <tt>isAlpha</tt>, etc.) were hooked up to the Javascript implementations supporting Unicode. This did not result in considerable slowdowns, rather, some browsers even showed minor speedup in heavy functions like <tt>read::String -> Int</tt>.<br />
<br />
=== Browsers compatibility ===<br />
<br />
Compatibility with major browsers such as Netscape/Mozilla/Firefox and Microsoft Internet Explorer, and also Opera was observed. Compatibility with Safari has not been reached so far.<br />
<br />
=== Future plan: Fudgets ===<br />
<br />
It is planned to port some portion of Fudgets, so it becomes possible to write Web applications using this library. Several experiments showed that the Stream Processors (SP), and some parts of Fudget Kernel layers worked within a Javascript application. More problems are expected with porting the toplevel widgets due to differences in many concepts between Web browser and X Window, for which the Fudgets library was originally developed.<br />
<br />
== Wacky features ==<br />
<br />
Yhc is going in many interesting directions. Some of these directions are likely to become very important in the future, some are likely to fade away. Yhc is a genuine research bed for brand new ideas.<br />
<br />
Author: All<br />
<br />
When you don't spend all the time on wacky type systems, you get a lot more time left to work on Wacky other stuff. Include Java interpetter, .NET back end, Javascript back end, Python interpretter, Hat debugging, yhi-stack, whole program optimisation. Lots of these things are breeding grounds for various useful technologies, and most are marching towards genuine usefulness.<br />
<br />
== Acknowledgements ==<br />
<br />
Thanks to everyone who has submitted a patch, become a buildbot, reported bugs or done anything else to benefit the Yhc project. We've put together a list of most of the people (if we've missed you, please shout, and we'll add your name in future versions of this document!)<br />
<br />
Andrew Wilkinson, Bernie Pope, Bob Davie, Brian Alliet, Christopher Lane Hinson, Dimitry Golubovsky, Gabor Greif, Goetz Isenmann, Isaac Dupree, Kartik Vaddadi, Krasimir Angelov, Malcolm Wallace, Michal Palka, Mike Dodds, Neil Mitchell, Robert Dockins, Samuel Bronson, Stefan O'Rear, Thorkil Naur, Tom Shackell</div>Stefanhttps://wiki.haskell.org/index.php?title=Toy_compression_implementations&diff=11858Toy compression implementations2007-03-09T01:59:58Z<p>Stefan: use laziness and HOFs to dramatically shrink lzw funcs</p>
<hr />
<div>[[Category:Code]]<br />
<br />
== About ==<br />
<br />
This code is provided in the hope that someone might find it interesting/entertaining, and to demonstrate what an excellent programming language Haskell truly is. (A working polymorphic LZW implementation in 10 lines? Try ''that'' in Java!)<br />
<br />
This is 'toy' code. Please don't try to use it to compress multi-GB of data. It has not been thoroughly checked for correctness, and I shudder to think what the time and space complexity would be like! However, it is enlightening and entertaining to see how many algorithms you can implement with a handful of lines...<br />
<br />
[[User:MathematicalOrchid|MathematicalOrchid]] 16:46, 15 February 2007 (UTC)<br />
<br />
== Main module ==<br />
<br />
<haskell><br />
module Compression where<br />
<br />
import List<br />
import Maybe<br />
import IO (hFlush, stdout)<br />
<br />
chars = [' '..'~'] -- Becuase ' ' = 0x20 and '~' = 0x7F.<br />
<br />
-- Run-length encoding<br />
<br />
encode_RLE :: (Eq t) => [t] -> [(Int,t)]<br />
encode_RLE = map (\xs -> (length xs, head xs)) . groupBy (==)<br />
<br />
decode_RLE :: [(Int,t)] -> [t]<br />
decode_RLE = concatMap (uncurry replicate)<br />
<br />
<br />
-- Limpel-Ziv-Welch encoding<br />
<br />
encode_LZW :: (Eq t) => [t] -> [t] -> [Int]<br />
encode_LZW alphabet = work (map (:[]) alphabet) where<br />
chunk pred lst = last . takeWhile (pred . fst) . tail $ zip (inits lst) (tails lst)<br />
work table [] = []<br />
work table lst = fromJust (elemIndex tok table) : work (table ++ [tok ++ [head rst]]) rst<br />
where (tok, rst) = chunk (`elem` table) lst<br />
<br />
decode_LZW :: [t] -> [Int] -> [t]<br />
decode_LZW alphabet xs = concat output where<br />
output = map (table !!) xs<br />
table = map (:[]) alphabet ++ zipWith (++) output (map (take 1) (tail output))<br />
<br />
main = do x <- take 20000 `fmap` readFile "/usr/share/dict/words"<br />
let l = length x `div` 80<br />
a = ['\0' .. '\255']<br />
eq a b | a == b = putChar '=' >> hFlush stdout<br />
| otherwise = error "data error"<br />
cmp = zipWith eq x . decode_LZW a . encode_LZW a $ x<br />
vl = map head $ unfoldr (\cm -> case cm of [] -> Nothing ; _ -> Just (splitAt l cm)) cmp<br />
sequence_ vl<br />
<br />
</haskell><br />
<br />
Some examples are in order:<br />
<br />
<haskell><br />
> encode_RLE "AAAABBBBDDCCCCEEEGGFFFF"<br />
<br />
[(4,'A'),(4,'B'),(2,'D'),(4,'C'),(3,'E'),(2,'G'),(4,'F')]<br />
<br />
<br />
> decode_RLE [(4,'A'),(4,'B'),(2,'D'),(4,'C'),(3,'E'),(2,'G'),(4,'F')]<br />
<br />
"AAAABBBBDDCCCCEEEGGFFFF"<br />
<br />
<br />
> encode_LZW chars "This is just a simple test."<br />
<br />
[52,72,73,83,0,97,0,74,85,83,84,0,65,0,83,73,77,80,76,69,0,84,69,104,14]<br />
<br />
<br />
> decode_LZW chars [52,72,73,83,0,97,0,74,85,83,84,0,65,0,83,73,77,80,76,69,0,84,69,104,14]<br />
<br />
"This is just a simple test."<br />
</haskell><br />
<br />
== Huffman coding ==<br />
<br />
<haskell><br />
module Huffman<br />
(count, markov1, Tree, encode_huffman, decode_huffman)<br />
where<br />
<br />
import Data.List (nub)<br />
<br />
-- Marvok1 probability model...<br />
<br />
count :: (Eq t) => [t] -> [(t,Int)]<br />
count xs = map (\x -> (x, length $ filter (x ==) xs)) $ nub xs<br />
<br />
markov1 :: (Eq t) => [t] -> [(t,Double)]<br />
markov1 xs =<br />
let n = fromIntegral $ length xs<br />
in map (\(x,c) -> (x, fromIntegral c / n)) $ count xs<br />
<br />
<br />
-- Build a Huffman tree...<br />
<br />
data Tree t = Leaf Double t | Branch Double (Tree t) (Tree t) deriving Show<br />
<br />
prob :: Tree t -> Double<br />
prob (Leaf p _) = p<br />
prob (Branch p _ _) = p<br />
<br />
get_tree :: [Tree t] -> (Tree t, [Tree t])<br />
get_tree (t:ts) = work t [] ts where<br />
work x xs [] = (x,xs)<br />
work x xs (y:ys)<br />
| prob y < prob x = work y (x:xs) ys<br />
| otherwise = work x (y:xs) ys<br />
<br />
huffman_build :: [(t,Double)] -> Tree t<br />
huffman_build = build . map (\(t,p) -> Leaf p t) where<br />
build [t] = t<br />
build ts =<br />
let (t0,ts0) = get_tree ts<br />
(t1,ts1) = get_tree ts0<br />
in build $ Branch (prob t0 + prob t1) t0 t1 : ts1<br />
<br />
<br />
-- Make codebook...<br />
<br />
data Bit = Zero | One deriving (Eq, Show)<br />
type Bits = [Bit]<br />
<br />
huffman_codebook :: Tree t -> [(t,Bits)]<br />
huffman_codebook = work [] where<br />
work bs (Leaf _ x) = [(x,bs)]<br />
work bs (Branch _ t0 t1) = work (bs ++ [Zero]) t0 ++ work (bs ++ [One]) t1<br />
<br />
<br />
-- Do the coding!<br />
<br />
encode :: (Eq t) => [(t,Bits)] -> [t] -> Bits<br />
encode cb = concatMap (\x -> maybe undefined id $ lookup x cb)<br />
<br />
decode :: (Eq t) => Tree t -> Bits -> [t]<br />
decode t = work t t where<br />
work _ (Leaf _ x) [] = [x]<br />
work t (Leaf _ x) bs = x : work t t bs<br />
work t (Branch _ t0 t1) (b:bs)<br />
| b == Zero = work t t0 bs<br />
| otherwise = work t t1 bs<br />
<br />
encode_huffman :: (Eq t) => [t] -> (Tree t, Bits)<br />
encode_huffman xs =<br />
let t = huffman_build $ markov1 xs<br />
bs = encode (huffman_codebook t) xs<br />
in (t,bs)<br />
<br />
decode_huffman :: (Eq t) => Tree t -> Bits -> [t]<br />
decode_huffman = decode<br />
</haskell><br />
<br />
If anybody can make this code shorter / more elegant, feel free!<br />
<br />
A short demo:<br />
<haskell><br />
> encode_huffman "this is just a simple test"<br />
<loads of data><br />
<br />
> decode_huffman (fst it) (snd it)<br />
"this is just a simple test"<br />
</haskell></div>Stefanhttps://wiki.haskell.org/index.php?title=Toy_compression_implementations&diff=11850Toy compression implementations2007-03-09T00:23:04Z<p>Stefan: fix the LZW code</p>
<hr />
<div>[[Category:Code]]<br />
<br />
== About ==<br />
<br />
This code is provided in the hope that someone might find it interesting/entertaining, and to demonstrate what an excellent programming language Haskell truly is. (A working polymorphic LZW implementation in 10 lines? Try ''that'' in Java!)<br />
<br />
This is 'toy' code. Please don't try to use it to compress multi-GB of data. It has not been thoroughly checked for correctness, and I shudder to think what the time and space complexity would be like! However, it is enlightening and entertaining to see how many algorithms you can implement with a handful of lines...<br />
<br />
[[User:MathematicalOrchid|MathematicalOrchid]] 16:46, 15 February 2007 (UTC)<br />
<br />
== Main module ==<br />
<br />
<haskell><br />
module Compression where<br />
<br />
import Data.List<br />
import Data.Word -- In case you want it. (Not actually used anywhere!)<br />
<br />
chars = [' '..'~'] -- Becuase ' ' = 0x20 and '~' = 0x7F.<br />
<br />
<br />
-- Run-length encoding<br />
<br />
encode_RLE :: (Eq t) => [t] -> [(Int,t)]<br />
encode_RLE = map (\xs -> (length xs, head xs)) . groupBy (==)<br />
<br />
decode_RLE :: [(Int,t)] -> [t]<br />
decode_RLE = concatMap (uncurry replicate)<br />
<br />
-- Limpel-Ziv-Welch encoding<br />
<br />
encode_LZW :: (Eq t) => [t] -> [t] -> [Int]<br />
encode_LZW _ [] = []<br />
encode_LZW alphabet (x:xs) = work (make alphabet) [x] xs where<br />
make = map (\x -> [x])<br />
work table buffer [] = [maybe undefined id $ elemIndex buffer table]<br />
work table buffer (x:xs) =<br />
let new = buffer ++ [x]<br />
in case elemIndex new table of<br />
Nothing -> maybe undefined id (elemIndex buffer table) : work (table ++ [new]) [x] xs<br />
Just _ -> work table new xs<br />
<br />
decode_LZW :: [t] -> [Int] -> [t]<br />
decode_LZW _ [] = []<br />
decode_LZW alphabet xs = work (length alphabet) (make alphabet) [] xs where<br />
make = map (\x -> [x])<br />
work _ t _ [] = []<br />
work n table prev (x:xs) =<br />
let out = if (x == n) then (prev ++ [head prev]) else (table !! x)<br />
in out ++ if null prev<br />
then work n table out xs<br />
else work (n+1) (table ++ [prev ++ [head out]]) out xs<br />
<br />
</haskell><br />
<br />
Some examples are in order:<br />
<br />
<haskell><br />
> encode_RLE "AAAABBBBDDCCCCEEEGGFFFF"<br />
<br />
[(4,'A'),(4,'B'),(2,'D'),(4,'C'),(3,'E'),(2,'G'),(4,'F')]<br />
<br />
<br />
> decode_RLE [(4,'A'),(4,'B'),(2,'D'),(4,'C'),(3,'E'),(2,'G'),(4,'F')]<br />
<br />
"AAAABBBBDDCCCCEEEGGFFFF"<br />
<br />
<br />
> encode_LZW chars "This is just a simple test."<br />
<br />
[52,72,73,83,0,97,0,74,85,83,84,0,65,0,83,73,77,80,76,69,0,84,69,104,14]<br />
<br />
<br />
> decode_LZW chars [52,72,73,83,0,97,0,74,85,83,84,0,65,0,83,73,77,80,76,69,0,84,69,104,14]<br />
<br />
"This is just a simple test."<br />
</haskell><br />
<br />
== Huffman coding ==<br />
<br />
<haskell><br />
module Huffman<br />
(count, markov1, Tree, encode_huffman, decode_huffman)<br />
where<br />
<br />
import Data.List (nub)<br />
<br />
-- Marvok1 probability model...<br />
<br />
count :: (Eq t) => [t] -> [(t,Int)]<br />
count xs = map (\x -> (x, length $ filter (x ==) xs)) $ nub xs<br />
<br />
markov1 :: (Eq t) => [t] -> [(t,Double)]<br />
markov1 xs =<br />
let n = fromIntegral $ length xs<br />
in map (\(x,c) -> (x, fromIntegral c / n)) $ count xs<br />
<br />
<br />
-- Build a Huffman tree...<br />
<br />
data Tree t = Leaf Double t | Branch Double (Tree t) (Tree t) deriving Show<br />
<br />
prob :: Tree t -> Double<br />
prob (Leaf p _) = p<br />
prob (Branch p _ _) = p<br />
<br />
get_tree :: [Tree t] -> (Tree t, [Tree t])<br />
get_tree (t:ts) = work t [] ts where<br />
work x xs [] = (x,xs)<br />
work x xs (y:ys)<br />
| prob y < prob x = work y (x:xs) ys<br />
| otherwise = work x (y:xs) ys<br />
<br />
huffman_build :: [(t,Double)] -> Tree t<br />
huffman_build = build . map (\(t,p) -> Leaf p t) where<br />
build [t] = t<br />
build ts =<br />
let (t0,ts0) = get_tree ts<br />
(t1,ts1) = get_tree ts0<br />
in build $ Branch (prob t0 + prob t1) t0 t1 : ts1<br />
<br />
<br />
-- Make codebook...<br />
<br />
data Bit = Zero | One deriving (Eq, Show)<br />
type Bits = [Bit]<br />
<br />
huffman_codebook :: Tree t -> [(t,Bits)]<br />
huffman_codebook = work [] where<br />
work bs (Leaf _ x) = [(x,bs)]<br />
work bs (Branch _ t0 t1) = work (bs ++ [Zero]) t0 ++ work (bs ++ [One]) t1<br />
<br />
<br />
-- Do the coding!<br />
<br />
encode :: (Eq t) => [(t,Bits)] -> [t] -> Bits<br />
encode cb = concatMap (\x -> maybe undefined id $ lookup x cb)<br />
<br />
decode :: (Eq t) => Tree t -> Bits -> [t]<br />
decode t = work t t where<br />
work _ (Leaf _ x) [] = [x]<br />
work t (Leaf _ x) bs = x : work t t bs<br />
work t (Branch _ t0 t1) (b:bs)<br />
| b == Zero = work t t0 bs<br />
| otherwise = work t t1 bs<br />
<br />
encode_huffman :: (Eq t) => [t] -> (Tree t, Bits)<br />
encode_huffman xs =<br />
let t = huffman_build $ markov1 xs<br />
bs = encode (huffman_codebook t) xs<br />
in (t,bs)<br />
<br />
decode_huffman :: (Eq t) => Tree t -> Bits -> [t]<br />
decode_huffman = decode<br />
</haskell><br />
<br />
If anybody can make this code shorter / more elegant, feel free!<br />
<br />
A short demo:<br />
<haskell><br />
> encode_huffman "this is just a simple test"<br />
<loads of data><br />
<br />
> decode_huffman (fst it) (snd it)<br />
"this is just a simple test"<br />
</haskell></div>Stefanhttps://wiki.haskell.org/index.php?title=IRC_channel&diff=11608IRC channel2007-02-26T03:24:17Z<p>Stefan: high water</p>
<hr />
<div>== Overview ==<br />
<br />
Internet Relay Chat is a worldwide text chat service with many thousands<br />
of users among various irc networks.<br />
<br />
The Freenode IRC network hosts the #haskell channel, and we've had up to<br />
332 concurrent users (average is 296). One famous resident is<br />
[[Lambdabot]], another is [http://hpaste.org hpaste].<br />
<br />
The IRC channel can be an excellent place to learn more about Haskell,<br />
and to just keep in the loop on new things in the Haskell world. Many<br />
new developments in the Haskell world first appear on the irc channel.<br />
<br />
== Getting there ==<br />
<br />
If you point your irc client to [irc://chat.freenode.net/haskell chat.freenode.net] and then join the #haskell channel, you'll be there. Alternately, you can try the webchat client at http://www.cs.uu.nl/wiki/FP/ChatHaskell (this will take you directly<br />
into the channel from your browser, if it supports Java).<br />
<br />
Example, using [http://www.irssi.org/ irssi]:<br />
<br />
$ irssi -c chat.freenode.org -n myname -w mypassword<br />
/join #haskell<br />
<br />
[[Image:Irc--haskell-screenshot.png|frame|A screenshot of an irssi session in #haskell]]<br />
<br />
== Principles ==<br />
<br />
The #haskell channel is a very friendly, welcoming place to hang out,<br />
teach and learn. The goal of #haskell is to encourage learning and<br />
discussion of Haskell, functional programming, and programming in<br />
general. As part of this we welcome newbies, and encourage teaching of<br />
the language.<br />
<br />
Part of the #haskell success comes from the approach that the community<br />
is quite tight knit -- we know each other -- it's not just a homework<br />
channel. As a result, many collaborative projects have arisen between<br />
Haskell irc channel citizens.<br />
<br />
To maintain the friendly, open culture, the following is required:<br />
<br />
* Low to zero tolerance for ridiculing questions. Insulting new users is unacceptable<br />
<br />
New Haskell users should feel entirely comfortable asking new questions.<br />
Helpful answers should be encouraged with <hask>name++</hask> karma<br />
points, in public, as a reward for providing a good answer.<br />
<br />
== History ==<br />
<br />
The #haskell channel appeared in the late 90s, and really got going<br />
in early 2001, with the help of Shae Erisson (aka shapr).<br />
<br />
A fairly extensive analysis of the traffic on #haskell over the years is<br />
[http://www.cse.unsw.edu.au/~dons/irc/ kept here]<br />
<br />
<br />
== Related channels ==<br />
<br />
In addition to the main Haskell channel there are also:<br />
<br />
{| border="1" cellspacing="0" cellpadding="5" align="center"<br />
! Channel<br />
! Purpose<br />
|- <br />
| #haskell.de<br />
| German speakers<br />
|-<br />
| #haskell.dut<br />
| Dutch speakers<br />
|-<br />
| #haskell.es<br />
| Spanish speakers<br />
|-<br />
| #haskell.fi<br />
| Finnish speakers<br />
|-<br />
| #haskell.fr <br />
| French speakers <br />
|-<br />
| #haskell.hr<br />
| Croatian speakers<br />
|-<br />
| #haskell.it <br />
| Italian speakers<br />
|-<br />
| #haskell.jp <br />
| Japanese speakers<br />
|-<br />
| #haskell.no <br />
| Norwegian speakers<br />
|-<br />
| #haskell.ru <br />
| Russian speakers. Seems that most of them migrated to Jabber conference (haskell@conference.jabber.ru)<br />
|-<br />
| #haskell.se <br />
| Swedish speakers<br />
|-<br />
| #haskell-overflow<br />
| Overflow conversations<br />
|-<br />
| #haskell-blah <br />
| Haskell people talking about anything except Haskell itself<br />
|-<br />
| #gentoo-haskell <br />
| Gentoo/Linux specific Haskell conversations<br />
|-<br />
| #darcs <br />
| Darcs revision control channel (written in Haskell)<br />
|-<br />
| #perl6 <br />
|Perl 6 development (plenty of Haskell chat there too)<br />
|-<br />
|}<br />
<br />
[[Image:Nick-activity.png|frame|Growth of #haskell]]<br />
<br />
== Logs ==<br />
<br />
'''Logs''' are kept at a few places, including<br />
<br />
* [http://tunes.org/~nef/logs/haskell/ tunes.org]<br />
* [http://meme.b9.com/clog/haskell/ meme]<br />
<br />
== Locations ==<br />
<br />
To get an overview of where everybody on the channel might<br />
be, physically, please visit [[Haskell user locations]].<br />
<br />
[[Category:Community]]</div>Stefanhttps://wiki.haskell.org/index.php?title=IRC_channel&diff=11591IRC channel2007-02-25T20:06:18Z<p>Stefan: new high water</p>
<hr />
<div>Internet Relay Chat is a worldwide text chat service with many thousands<br />
of users among various irc networks.<br />
<br />
The Freenode IRC network hosts the #haskell channel, and we've had up to<br />
331 concurrent users (average is 294). One famous resident is<br />
[[Lambdabot]], another is [http://hpaste.org hpaste].<br />
<br />
The IRC channel can be an excellent place to learn more about Haskell,<br />
and to just keep in the loop on new things in the Haskell world. Many<br />
new developments in the Haskell world first appear on the irc channel.<br />
<br />
== Getting there ==<br />
<br />
If you point your irc client to [irc://chat.freenode.net/haskell chat.freenode.net] and then join the #haskell channel, you'll be there. Alternately, you can try the webchat client at http://www.cs.uu.nl/wiki/FP/ChatHaskell (this will take you directly<br />
into the channel from your browser, if it supports Java).<br />
<br />
Example, using [http://www.irssi.org/ irssi]:<br />
<br />
$ irssi -c chat.freenode.org -n myname -w mypassword<br />
/join #haskell<br />
<br />
[[Image:Irc--haskell-screenshot.png|frame|A screenshot of an irssi session in #haskell]]<br />
<br />
== Principles ==<br />
<br />
The #haskell channel is a very friendly, welcoming place to hang out,<br />
teach and learn. The goal of #haskell is to encourage learning and<br />
discussion of Haskell, functional programming, and programming in<br />
general. As part of this we welcome newbies, and encourage teaching of<br />
the language.<br />
<br />
Part of the #haskell success comes from the approach that the community<br />
is quite tight knit -- we know each other -- it's not just a homework<br />
channel. As a result, many collaborative projects have arisen between<br />
Haskell irc channel citizens.<br />
<br />
To maintain the friendly, open culture, the following is required:<br />
<br />
* Low to zero tolerance for ridiculing questions. Insulting new users is unacceptable<br />
<br />
New Haskell users should feel entirely comfortable asking new questions.<br />
Helpful answers should be encouraged with <hask>name++</hask> karma<br />
points, in public, as a reward for providing a good answer.<br />
<br />
== History ==<br />
<br />
The #haskell channel appeared in the late 90s, and really got going<br />
in early 2001, with the help of Shae Erisson (aka shapr).<br />
<br />
A fairly extensive analysis of the traffic on #haskell over the years is<br />
[http://www.cse.unsw.edu.au/~dons/irc/ kept here]<br />
<br />
<br />
== Related channels ==<br />
<br />
In addition to the main Haskell channel there are also:<br />
<br />
{| border="1" cellspacing="0" cellpadding="5" align="center"<br />
! Channel<br />
! Purpose<br />
|- <br />
| #haskell.de<br />
| German speakers<br />
|-<br />
| #haskell.dut<br />
| Dutch speakers<br />
|-<br />
| #haskell.es<br />
| Spanish speakers<br />
|-<br />
| #haskell.fi<br />
| Finnish speakers<br />
|-<br />
| #haskell.fr <br />
| French speakers <br />
|-<br />
| #haskell.hr<br />
| Croatian speakers<br />
|-<br />
| #haskell.it <br />
| Italian speakers<br />
|-<br />
| #haskell.jp <br />
| Japanese speakers<br />
|-<br />
| #haskell.no <br />
| Norwegian speakers<br />
|-<br />
| #haskell.ru <br />
| Russian speakers. Seems that most of them migrated to Jabber conference (haskell@conference.jabber.ru)<br />
|-<br />
| #haskell.se <br />
| Swedish speakers<br />
|-<br />
| #haskell-overflow<br />
| Overflow conversations<br />
|-<br />
| #haskell-blah <br />
| Haskell people talking about anything except Haskell itself<br />
|-<br />
| #gentoo-haskell <br />
| Gentoo/Linux specific Haskell conversations<br />
|-<br />
| #darcs <br />
| Darcs revision control channel (written in Haskell)<br />
|-<br />
| #perl6 <br />
|Perl 6 development (plenty of Haskell chat there too)<br />
|-<br />
|}<br />
<br />
[[Image:Nick-activity.png|frame|Growth of #haskell]]<br />
<br />
== Logs ==<br />
<br />
'''Logs''' are kept at a few places, including<br />
<br />
* [http://tunes.org/~nef/logs/haskell/ tunes.org]<br />
* [http://meme.b9.com/clog/haskell/ meme]<br />
<br />
== Locations ==<br />
<br />
To get an overview of where everybody on the channel might<br />
be, physically, please visit [[Haskell user locations]].<br />
<br />
[[Category:Community]]</div>Stefanhttps://wiki.haskell.org/index.php?title=IRC_channel&diff=11309IRC channel2007-02-15T00:08:16Z<p>Stefan: new high water</p>
<hr />
<div>Internet Relay Chat is a worldwide text chat service with many thousands<br />
of users among various irc networks.<br />
<br />
The Freenode IRC network hosts the #haskell channel, and we've had up to<br />
328 concurrent users (average is 277). One famous resident is<br />
[[Lambdabot]], another is [http://hpaste.org hpaste].<br />
<br />
The IRC channel can be an excellent place to learn more about Haskell,<br />
and to just keep in the loop on new things in the Haskell world. Many<br />
new developments in the Haskell world first appear on the irc channel.<br />
<br />
== Getting there ==<br />
<br />
If you point your irc client to [irc://chat.freenode.net/haskell chat.freenode.net] <br />
<br />
[[(spanish)Canal En espanol para latinoamerica En la red Undernet]] [irc://eu.undernet.org/haskell eu.undernet.org] <br />
<br />
and then join the #haskell channel, you'll be there. Alternately, you can try the<br />
webchat client at http://www.cs.uu.nl/wiki/FP/ChatHaskell (this will take you directly<br />
into the channel from your browser, if it supports Java).<br />
<br />
Example, using [http://www.irssi.org/ irssi]:<br />
<br />
$ irssi -c chat.freenode.org -n myname -w mypassword<br />
/join #haskell<br />
<br />
*New* Red Undernet, Channel no oficcial. User adicts Haskell<br />
$ irssi -c eu.undernet.org -n myname -w mypassword<br />
/join #haskell<br />
<br />
and you're there.<br />
<br />
[[Image:Irc--haskell-screenshot.png|frame|A screenshot of an irssi session in #haskell]]<br />
<br />
== Principles ==<br />
<br />
The #haskell channel is a very friendly, welcoming place to hang out,<br />
teach and learn. The goal of #haskell is to encourage learning and<br />
discussion of Haskell, functional programming, and programming in<br />
general. As part of this we welcome newbies, and encourage teaching of<br />
the language.<br />
<br />
Part of the #haskell success comes from the approach that the community<br />
is quite tight knit -- we know each other -- it's not just a homework<br />
channel. As a result, many collaborative projects have arisen between<br />
Haskell irc channel citizens.<br />
<br />
To maintain the friendly, open culture, the following is required:<br />
<br />
* Low to zero tolerance for ridiculing questions. Insulting new users is unacceptable<br />
<br />
New Haskell users should feel entirely comfortable asking new questions.<br />
Helpful answers should be encouraged with <hask>name++</hask> karma<br />
points, in public, as a reward for providing a good answer.<br />
<br />
== History ==<br />
<br />
The #haskell channel appeared in the late 90s, and really got going<br />
in early 2001, with the help of Shae Erisson (aka shapr).<br />
<br />
A fairly extensive analysis of the traffic on #haskell over the years is<br />
[http://www.cse.unsw.edu.au/~dons/irc/ kept here]<br />
<br />
<br />
== Related channels ==<br />
<br />
Red Undernet: Haskell ( /server eu.undernet.org )<br />
|- <br />
| #haskell<br />
| Spanish (espanol - Latinoamerica )<br />
|-<br />
<br />
<br />
In addition to the main Haskell channel there are also:<br />
<br />
{| border="1" cellspacing="0" cellpadding="5" align="center"<br />
! Channel<br />
! Purpose<br />
|- <br />
| #haskell.de<br />
| German speakers<br />
|-<br />
| #haskell.dut<br />
| Dutch speakers<br />
|-<br />
| #haskell.es<br />
| Spanish speakers<br />
|-<br />
| #haskell.fi<br />
| Finnish speakers<br />
|-<br />
| #haskell.fr <br />
| French speakers <br />
|-<br />
| #haskell.hr<br />
| Croatian speakers<br />
|-<br />
| #haskell.it <br />
| Italian speakers<br />
|-<br />
| #haskell.jp <br />
| Japanese speakers<br />
|-<br />
| #haskell.no <br />
| Norwegian speakers<br />
|-<br />
| #haskell.ru <br />
| Russian speakers. Seems that most of them migrated to Jabber conference (haskell@conference.jabber.ru)<br />
|-<br />
| #haskell.se <br />
| Swedish speakers<br />
|-<br />
| #haskell-overflow<br />
| Overflow conversations<br />
|-<br />
| #haskell-blah <br />
| Haskell people talking about anything except Haskell itself<br />
|-<br />
| #gentoo-haskell <br />
| Gentoo/Linux specific Haskell conversations<br />
|-<br />
| #darcs <br />
| Darcs revision control channel (written in Haskell)<br />
|-<br />
| #perl6 <br />
|Perl 6 development (plenty of Haskell chat there too)<br />
|-<br />
|}<br />
<br />
[[Image:Nick-activity.png|frame|Growth of #haskell]]<br />
<br />
== Logs ==<br />
<br />
'''Logs''' are kept at a few places, including<br />
<br />
* [http://tunes.org/~nef/logs/haskell/ tunes.org]<br />
* [http://meme.b9.com/clog/haskell/ meme]<br />
<br />
== Locations ==<br />
<br />
To get an overview of where everybody on the channel might<br />
be, physically, please visit [[Haskell user locations]].<br />
<br />
[[Category:Community]]</div>Stefanhttps://wiki.haskell.org/index.php?title=From_a_newbie&diff=10040From a newbie2007-01-10T23:48:14Z<p>Stefan: reply</p>
<hr />
<div>== Introduction ==<br />
<br />
Greetings. I am a Haskell newbie. I am writing this page because I couldn't think of any other way to get attention. (More on this below.) Maybe somebody will see this page and add some useful comments. Maybe this page will simply be deleted. I don't know&hellip;<br />
<br />
== First Impressions of Haskell ==<br />
<br />
For some background... I first starting programming with BASIC, way back in the Dark Ages of 8-bit home computers. I then moved on to raw machine code (couldn't afford an assembler). From there I went on to Pascal &mdash; which I found much to my liking. Later I learned about Smalltalk and Java. (Java &mdash; Nice idea, shame it's a crock of junk&hellip;)<br />
<br />
Then I learned Haskell. Presumably it goes without saying that it was a mind-bending experience. (!) Much like learning OOP &mdash; but more intense! Haskell is utterly unlike ''anything'' I have ever seen before&hellip; and I think I like it!<br />
<br />
== The Trouble with Haskell ==<br />
<br />
Sadly, it turns out that Haskell appears to have 2 fatal problems. (Which is really what I'm writing this page for.)<br />
<br />
=== The First Problem ===<br />
<br />
It seems to be that virtually all programming languages can be neatly seperated into two disjoint categories:<br />
<br />
* First there are type-I languages. Surely C is the apex of what it is to be a type-I language. C is ugly, complex, low-level, poorly defined, dangerous, extremely hard to read, and ''actually impossible'' to write. In short, C is a ''disgusting'' language which should never ever have been invented in the first place. But you can '''do stuff''' in C.<br />
<br />
* And then there are the type-II languages. Things like Smalltalk, Eiffel, etc. Languages which are simple, flexible, powerful, elligant, beautiful. Languages with are a sheer joy to program with. Unfortunately, you cannot '''do stuff''' with type-II languages.<br />
<br />
If Eiffel is &ldquo;powerful&rdquo; then Haskell is surely some kind of weapon of mass destruction! Regrettably, it seems that Haskell is yet another type-II language. Inside Haskell you can write some amazing stuff. But you just can't talk to the outside world. No graphics, no sound, no GUI, no networking, no database access, no compression, no cryptography, no threading&hellip; the list just goes on and on.<br />
<br />
:Huh? Graphics, GUI, networking, threading, and compression are all very well supported.<br />
Dunno about cryptography, sound is irrelevant because hearing is better reserved for detecting disk crashes :)<br />
Check Graphics.Rendering.OpenGL, Graphics.UI.Gtk, Network, Control.Concurrent, and Codec.Compression.GZip respectively.<br />
[[User:Stefan|Stefan]] 23:48, 10 January 2007 (UTC)<br />
<br />
Do you have ''any idea'' how frustrating it is to have found such a supremely powerful programming language and yet have utterly ''no way'' of '''using''' it?!<br />
<br />
Also, in common with many type-II languages, I find the language itself works, but everything else around it is lacking. Tools don't work well. Libraries are sparse. Everything is fairly poorly documented. It just makes life harder. (I could name any number of standard modules right now that have virtually ''no'' documentation beyond function names and type signatures.)<br />
<br />
=== The Second Problem ===<br />
<br />
The other problem is the Haskell community &mdash; or rather, the total non-existence of such. There are no web forums, no NTTP server, nothing. Nowhere a newbie like me can ask questions. I've had to resort to creating an orphan Wiki page just to say want I wish to be heard. This isn't an efficient way to communicate.<br />
<br />
I understand there is an email list, but SMTP is really not well suited to large group discussions. NNTP works much better for that. (Assuming you have a client and know how to use it. Web forums are generally a better idea.)<br />
<br />
:A wiki page is infinitely worse than SMTP for large group discussions, and I speak from (this) experience. [[User:Stefan|Stefan]] 23:48, 10 January 2007 (UTC)<br />
<br />
Oh, there ''is'' the Haskell IRC channel. Boy, that was a hoot! I've been on IRC channels with 6 people that are so busy you can't tell who's talking to who. But the Haskell IRC channel was something else&hellip; Over 300 people connected, and ''nobody speaking!'' Every 20 minutes or so, somebody would ask a question or something. They were all greeted by utter silence.<br />
<br />
:You must have arrived at the wrong time ... we have ~20 active users and many bursts of activity, with silence in between, check back soon and people will help. (at least if you return in the 6 hrs before my curfew) [[User:Stefan|Stefan]] 23:48, 10 January 2007 (UTC)<br />
<br />
Extremely amusing, but not especially helpful.<br />
<br />
So it is that I am left with half a dozen &ldquo;getting started&rdquo; tutorials scattered over the Internet, plus the Language Report. The Language Report of course is a reference document. And very unfriendly it is too. Oh, and there's the library docs &mdash; highly incomplete as they are.<br />
<br />
All of this is really quite dissappointing. I actually have several questions I'd like answers to, but I can't find anywhere to ask.<br />
<br />
== In Closing ==<br />
<br />
Oh well, since I'm here I suppose I might as well ask a few actual ''questions'' rather than just looking like I'm here to flame everything.<br />
<br />
* Why does ''every'' non-trivial program or library '''require''' language extensions. Seriously. What the hell? Is plain Haskell 98 such a feeble language that no interesting software can be written with it? If so, that doesn't bode well! (For example, I tried to use the module Control.Monad.State. However, instead of importing the module I merely got a fairly opaque error message basically telling me I need to enable extensions. '''Why?''' It's perfectly possible to write a state monad in plain Haskell. So ''why'' do the standard modules not to this??)<br />
<br />
:Actually, the problem is that you are using Hugs. Since some people use language extensions, Control.Monad.State uses them<br />
itself to "play nicer" with modules that use extensions. GHCi supports encapsulation of language use, so you need not know<br />
or care what extensions the libraries use. GHCi also has much better error messages, and is much more actively maintained. [[User:Stefan|Stefan]] 23:48, 10 January 2007 (UTC)<br />
<br />
* Why is it that Haskell seems to attract people who casually throw around phrases like &ldquo;existential qualification&rdquo; as if they ''mean'' something? Seriously. All programming languages have their own special terms, and in some cases stuff doesn't really make sense until you learn these. (For example, in OOP people debate whether &ldquo;inheritance breaks encapsulation&rdquo; or that &ldquo;inheritance is overused and collaboration is underused&rdquo;.) But Haskell seems to attract utterly bizzare terms vastly more than any other language I've ever seen! Why is that?<br />
<br />
:Haskell is written by mathematicians, and most of the terms are perfectly meaningful terms borrowed from incredibly arcane fields. (category theory mostly.) Not like it makes a difference. [[User:Stefan|Stefan]] 23:48, 10 January 2007 (UTC)<br />
<br />
* Is there any way to make is to that making a type an instance of class X automatically makes it an instance of class Y? I'm getting really tired of cut-and-pasting identical instance definitions&hellip;<br />
<br />
:No. [[User:Stefan|Stefan]] 23:48, 10 January 2007 (UTC)<br />
<br />
* When I read about 'lines' and 'words', I was expecting them to by curried versions of some more general function. However, it appears that no such general function exists. Why?<br />
<br />
split_with :: (Eq t) => t -> [t] -> [[t]]<br />
split_with ":" "5:11:21" == ["5","11","21"]<br />
<br />
It's not hard!<br />
<br />
:Hint: google. That problem has been discussed innumerable times. [[User:Stefan|Stefan]] 23:48, 10 January 2007 (UTC)<br />
<br />
* Does anybody have a good explanation of the seemingly arbitrary and random distribution of numerical types and classes? I'm sure I'm not the only person confused by this&hellip;<br />
<br />
:Ditto. [[User:Stefan|Stefan]] 23:48, 10 January 2007 (UTC)<br />
<br />
* Is there ''any'' way I can make it so that 'Complex' means 'Data.Complex.Complex Predule.Double'? I have tried and tried and tried to make this work; Hugs isn't having any of it.<br />
<br />
:GHCi will let you say :m + Data.Complex and then Complex Double. If you use a file, you can say 'type X = Complex Double'.<br />
<br />
* You know that the latest release of Hugs is horribly unstable, right? I mean, I used the Nov 2003 version for a long time, without issue. But the new Sep 2006 version behaves very unpredictably. It has a habit of truncating output, reprinting bits of previous output (the intro banner is especially popular), and frequently just stopping with a Dr Watson error. What the hell&hellip;?<br />
<br />
* Does anybody know what 'seq' actually does? The Prelude documentation is a fleeting comment about &ldquo;avoiding unnecessary laziness&rdquo;, but presumably an entire book could be written on such a subject. Where is this book?<br />
<br />
:No, nobody does. [[User:Stefan|Stefan]] 23:48, 10 January 2007 (UTC)<br />
<br />
If anybody has anything useful to say, please add it to the ''bottom'' of this page.<br />
<br />
:Since you didn't use SMTP, I have been forced to choose between attribution and context. The latter seemed more helpful. [[User:Stefan|Stefan]] 23:48, 10 January 2007 (UTC)<br />
<br />
[[User:MathematicalOrchid|MathematicalOrchid]] 21:31, 10 January 2007 (UTC)</div>Stefanhttps://wiki.haskell.org/index.php?title=Yi&diff=9747Yi2006-12-27T00:48:50Z<p>Stefan: mention lazy-counted-trees implementation</p>
<hr />
<div>[[Category:Applications]]<br />
<br />
<br />
= Yi ideas =<br />
<br />
This page is meant to gather ideas people have for<br />
[http://www.cse.unsw.edu.au/~dons/yi.html Yi], an extensible editor<br />
written in Haskell.<br />
<br />
== Emacs ==<br />
<br />
Coming from an Emacs background, the current version of Yi lacks a few<br />
things I think are essential, mainly the introspection capabilities<br />
of Emacs. One of the main problems is that Yi is based on purely<br />
compiled code --- there is little or no interaction with the run-time<br />
system.<br />
<br />
Ideally, the next version of Yi would be based on a (modified?)<br />
version of GHCi, maybe taking advantage of package GHC. <br />
<br />
=== Emacs goodness ===<br />
<br />
The following are things I like about Emacs, as an extensible<br />
environment:<br />
; Really good online documentation<br />
: Emacs can tell you a lot about a function or variable with a keypress--- the current value, where it is declared, and a hypertext formation string<br />
<br />
; Extensibility<br />
: All (good) apps allow users to extend, through, e.g., hooks --- a list of functions that are run before/after some event (like saving a file)<br />
<br />
; Integration<br />
: It is really easy in Emacs to have one package interact with another. Thus, I can, e.g., insert a new appointment from my mail app into the diary. <br />
<br />
; Everything is One Language<br />
: Ignoring the actual language (Lisp!), everything is handled in a uniform language --- from binding keys to writing apps.<br />
<br />
; Easy to start hacking<br />
: I can start playing with the system from the second I start up, and things pretty much work as expected. I.e., I can type a bit of code in, execute it, and the result is displayed in the minibuffer. The good docs help immeasurably.<br />
<br />
; Written for the frequent user<br />
: Lots of key shortcuts (and famous for it). There are still menus, for those who like em, but you aren't forced to pretend you just started using it.<br />
<br />
; A tonne of code<br />
: Well, Haskell has this to some degree. Haskell is (IMHO) much easier to write than ELisp, so maybe people will be encouraged to contribute.<br />
<br />
=== Emacs badness ===<br />
<br />
So, why replace it?:<br />
; ELisp<br />
: Dynamically scoped, Dynamically typed, ugly, old. 'Nuff said<br />
<br />
; What's a Parser?<br />
: A lot of apps in emacs do stuff with text, usually text that is in some language. There is no standard parser (like, e.g. parsec), so a lot of it is ugly handwritten spaghetti. This also means that adding analysis tools isn't really done (or done nicely).<br />
<br />
; ELisp again<br />
: Haskell is a lot cleaner to write, especially because of the large number of libraries.<br />
<br />
=== Emacs maybeness (?) ===<br />
<br />
Some things that are sometimes bad, sometimes good:<br />
<br />
; Everything is a buffer<br />
: Makes some sense, but sometimes doesn't. It is nice to have uniform key bindings do the right thing (e.g., C-Space sets the mark, and the region can then be used, e.g. to delete a sequence of emails in Wl) Sometimes, however, you just want some sort of GUI widget.<br />
: OTOH, having the minibuffer be a special kind of buffer is a good idea.<br />
<br />
; Properties<br />
: It is possible to associate arbitrary properties with symbols. This means you can annotate a symbol and then use that information at a later date<br />
<br />
== Vi ? ==<br />
<br />
What about vi? I believe we want Yi to subsume vi as well.<br />
<br />
== Ideas ==<br />
<br />
;Yi should include GHCi <br />
:like emacs includes a elisp interpreter.<br />
<br />
;An extension to GHCi to support documentation of symbols. <br />
:This seems to be (reasonably) straightforward, as GHCi already has :info. It would mean hacking the type environment (what about values?) to add documentation information. The main problem would seem to be populating this --- maybe hack haddock to produce something from the library docs? I assume that using package GHC uses the parent RTS (package GHC seems to be the way to go, but more investigation is required --- don?)<br />
<br />
;Intermixed compiled/interpreted code<br />
:(for speed/hacking)<br />
<br />
;GUI abstraction <br />
:want it to work on terminals as well as X<br />
:#Use Stefan O'Rear's vty. for terminal. http://members.cox.net/stefanor/vty/ <br />
:#Use gtk2hs for X http://haskell.org/gtk2hs/<br />
<br />
;Views on data<br />
:Rather than just editing a file, you would open a view onto the file, i.e. there is no longer a 1-1 correspondence between buffers and files. Why? Well, for aggregate buffers (i.e., editing multiple files in the one view), or for multiple views of a file (e.g. AST and source-level). There would be some primitive ops for editing a buffer (insertChar, delete, etc.), which would then call update functions on anything observing that file.<br />
<br />
;Remote attach so I can work from home, but still use a remote machine<br />
<br />
;Haddock documentation<br />
:(no brainer), maybe associate with .hi files for binaries. <br />
<br />
;A class MiniBufferRead (or PromptingRead) which allows the user to<br />
invoke a function similar to M-x in Emacs, but without requiring<br />
(interactive) <br />
:-- This is incomprehensibe, would the original author elaborate?<br />
<br />
;Maybe a class YiShow, which all config items must be a member of? This is to emulate describe-variable<br />
<br />
== Implementation ==<br />
<br />
Considerations:<br />
; Configuration <br />
: Per mode/file/buffer/whatever Monads, or reload/recompile? Or some hybrid? How does this interact with the documentation aspects? Do we want to have separate sorts of symbols a la emacs (describe-function, describe-variable), or is everything a function? I would think that configuration info doesn't change that frequently --- is this globally true though?<br />
:We can probably use a GHCi-like "let". Rebinding a function would then be synonym to assign a variable, thereby achieve unification between functions and variables.<br />
<br />
; Interface to the runtime<br />
: The scheduler, docs, etc.<br />
<br />
; Introspection of e.g. what processes are running.<br />
: There are already libraries in Haskell for processes, but they don't give Yi any extra information --- we really want a layer on top. <br />
<br />
...<br />
<br />
[[User:Sjw|Sjw]] 09:15, 2 June 2006 (UTC)<br />
<br />
= Development Plan =<br />
<br />
== Refactorings ==<br />
<br />
The below defines stuff that should be done before actual development of new feature start (to keep the code maintainable, more easily approachable by contributors).<br />
<br />
* Re-factor so the UI module really takes care of all the presentation/terminal specific stuff<br />
<br />
* Simplify the cursor movements functions<br />
** Most code/checks should be in Buffer<br />
*** In particular, the point should be managed by the buffer as a normal mark<br />
** Window should do the least possible cursor-management<br />
** Core should do no cursor management<br />
<br />
*Keymaps <br />
** Input should be a stream of properly typed events<br />
*** (Currently keymaps take a [Char] as input, with this or that bit set for indication of meta and control. This is somewhat ugly, and certainly lacks a bit of strongness in typing. -> It's impossible to bind C-space, etc.)<br />
**** Reason invoked: Alex support (I think we don't really need this)<br />
**Don't throw a exception for switching keymap<br />
***Instead, return a special Action.<br />
type Keymap = Stream Event () -> Stream Action Keymap<br />
data Stream a end = Stream a (Stream a) | End end<br />
<br />
* Re-write the FastBuffer so it uses ByteString instead of directly the C <br />
pointers<br />
<br />
** Look at other possibilities for buffer storage; e.g. Simon Tatham has had success using lazily-constructed size annotated 2-3-4 trees for editing >10GB files. [http://www.chiark.greenend.org.uk/~sgtatham/tweak/btree.html]<br />
<br />
* Remove the dependency on fps (base package has enough)<br />
<br />
== New Features ==<br />
<br />
Roughly by order of easy to do / reverse importance.<br />
<br />
* Implement per-buffer keymaps<br />
** Extend per-buffer configuration (to a full emacs-like mode).<br />
<br />
* emacs-style minibuffer<br />
<br />
* Open multiple windows on a buffer (each with a different point)<br />
<br />
* Gtk port -- stalled: probably bugs in gtk<br />
<br />
* Invent a system to have annotated buffers (syntax highlight, interactive content)<br />
<br />
* GHCi-like interpretation, etc.</div>Stefanhttps://wiki.haskell.org/index.php?title=Short_theorem_prover&diff=9665Short theorem prover2006-12-22T02:09:26Z<p>Stefan: cat:code</p>
<hr />
<div>Theorum prover in 625 characters of Haskell<br />
<br />
> import Monad;import Maybe;import List<br />
> infixr 9 ?<br />
> (?)=(:>);z=Just;y=True<br />
> data P=A Integer|P:>P deriving(Read,Show,Eq)<br />
> [a,b,c,d,e,f]=map A[1,3..11]<br />
> g=h(?).(A.)<br />
> h f z(A x)=z x<br />
> h f z(x:>y)=h f z x`f`h f z y<br />
> i p(A i)j=p&&i==j<br />
> i p(a:>b)j=i y a j||i y b j<br />
> j(A l)s(A k)|i False s l=Nothing|l==k=z s|y=z$A k<br />
> j f@(A i)s(a:>b)=liftM2(?)(j f s a)(j f s b)<br />
> j f s@(A i)p=j s f p<br />
> j(a:>b)(c:>d)p=let u=j a c in join$liftM3 j(u b)(u d)(u p)<br />
> l x=g(toInteger.fromJust.flip elemIndex (h union (:[]) x))x<br />
> m=(a?a:)$map l$catMaybes$liftM2(uncurry.j.g(*2))m[((((a?b?c)<br />
> ?(a?b)?a?c)?(d?e?d)?f),f),((a?b),(c?a)?c?b)]<br />
> main=getLine>>=print.(`elem`m).read<br />
<br />
You are not expected to understand that, so here is the explanation:<br />
<br />
First, we need a type of prepositions. Each A constructor represents a prepositional variable (a, b, c, etc), and :> represents implication. Thus, for example, (A 0 :> A 0) is the axiom of tautology in classical logic.<br />
<br />
> type U = Integer<br />
> data P = A U | P:>P deriving(Read,Show,Eq)<br />
> infixr 9 :><br />
<br />
To prove theorums, we need axioms and deduction rules. This theorum prover is based on the [[Curry-Howard-Lambek correspondance]] applied to the programming language Jot (http://ling.ucsd.edu/~barker/Iota/#Goedel). Thus, we have a single basic combinator and two deduction rules, corresponding to partial application of the base case and two combinators of Jot.<br />
<br />
> axiom = A 0:>A 0<br />
> rules = let[a,b,c,d,e,f]=map A[1,3..11]in[ (((a:>b:>c):>(a:>b):>a:>c):>(d:>e:>d):>f):>f, (a:>b):>(c:>a):>c:>b]<br />
<br />
We will also define foogomorphisms on the data structure:<br />
<br />
> pmap :: (U -> U) -> P -> P<br />
> pmap f = pfold (:>) (A .f)<br />
<br />
> pfold :: (a -> a -> a) -> (U -> a) -> P -> a<br />
> pfold f z (A x) = z x<br />
> pfold f z (x:>y) = pfold f z x`f`pfold f z y<br />
<br />
In order to avoid infinite types (which are not intrinsicly dangerous in a programming language but wreak havoc in logic because terms such as fix a. (a -> b) correspond to statements such as "this statement is false"), we check whether the replaced variable is mentioned in the replacing term:<br />
<br />
> cnt p(A i) j = p && i == j<br />
> cnt p(a:>b) j = cnt True a j || cnt True b j<br />
<br />
The deduction steps are performed by a standard unification routine:<br />
<br />
> unify :: P -> P -> P -> Maybe P<br />
> unify (A i) s (A j) | cnt False s i = Nothing<br />
> | i == j = Just $ s<br />
> | otherwise = Just $ A j<br />
> unify f@(A i) s (a:>b) = liftM2 (:>) (unify f s a) (unify f s b)<br />
> unify f s@(A i) pl = unify s f pl<br />
> unify (a:>b) (c:>d) pl = let u = unify a c in join $ liftM3 unify (u b) (u d) (u pl)<br />
<br />
We need to renumber terms to prevent name conflicts.<br />
<br />
> fan (A x) = A (x*2)<br />
> fan (x:>y)= fan x:> fan y<br />
<br />
Make a deduction given a rule, by setting the LHS of the rule equal to the state and taking the RHS of the rule.<br />
<br />
> deduce t r = let (a:>b)=r in unify (fan t) a b<br />
<br />
Canonicalize the numbers in the rule, thus allowing matching.<br />
<br />
> canon :: P -> P<br />
> canon x = pmap (toInteger . fromJust . flip elemIndex ( allvars x )) x<br />
> allvars :: P -> [U]<br />
> allvars = pfold union (:[])<br />
<br />
Given this, we can lazily construct the list of all true statements:<br />
> facts = nub $ (axiom:) $ map canon $ catMaybes $ liftM2 deduce facts rules<br />
<br />
main=getLine>>=print.(`elem`facts).read<br />
[[Category:Code]]</div>Stefanhttps://wiki.haskell.org/index.php?title=Short_theorem_prover&diff=9664Short theorem prover2006-12-22T02:08:56Z<p>Stefan: found one more tweak, down to 590 ch</p>
<hr />
<div>Theorum prover in 590 characters of Haskell<br />
<br />
> import Monad;import Maybe;import List<br />
> infixr 9 ?<br />
> (?)=(:>);z=Just;y=True<br />
> data P=A Integer|P:>P deriving(Read,Show,Eq)<br />
> [a,b,c,d,e,f]=map A[1,3..11]<br />
> g=h(?).(A.)<br />
> h f z(A x)=z x<br />
> h f z(x:>y)=h f z x`f`h f z y<br />
> j f@(A l)s(A k)|h(||)(==l)s&&f/=s=Nothing|l==k=z s|y=z$A k<br />
> j f@(A i)s(a:>b)=liftM2(?)(j f s a)(j f s b)<br />
> j f s@(A i)p=j s f p<br />
> j(a:>b)(c:>d)p=let u=j a c in join$liftM3 j(u b)(u d)(u p)<br />
> l x=g(toInteger.fromJust.flip elemIndex (h union (:[]) x))x<br />
> m=(a?a:)$map l$catMaybes$liftM2(uncurry.j.g(*2))m[((((a?b?c)<br />
> ?(a?b)?a?c)?(d?e?d)?f),f),((a?b),(c?a)?c?b)]<br />
> main=getLine>>=print.(`elem`m).read<br />
<br />
You are not expected to understand that, so here is the explanation:<br />
<br />
First, we need a type of prepositions. Each A constructor represents a prepositional variable (a, b, c, etc), and :> represents implication. Thus, for example, (A 0 :> A 0) is the axiom of tautology in classical logic.<br />
<br />
> type U = Integer<br />
> data P = A U | P:>P deriving(Read,Show,Eq)<br />
> infixr 9 :><br />
<br />
To prove theorums, we need axioms and deduction rules. This theorum prover is based on the [[Curry-Howard-Lambek correspondance]] applied to the programming language Jot (http://ling.ucsd.edu/~barker/Iota/#Goedel). Thus, we have a single basic combinator and two deduction rules, corresponding to partial application of the base case and two combinators of Jot.<br />
<br />
> axiom = A 0:>A 0<br />
> rules = let[a,b,c,d,e,f]=map A[1,3..11]in[ (((a:>b:>c):>(a:>b):>a:>c):>(d:>e:>d):>f):>f, (a:>b):>(c:>a):>c:>b]<br />
<br />
We will also define foogomorphisms on the data structure:<br />
<br />
> pmap :: (U -> U) -> P -> P<br />
> pmap f = pfold (:>) (A .f)<br />
<br />
> pfold :: (a -> a -> a) -> (U -> a) -> P -> a<br />
> pfold f z (A x) = z x<br />
> pfold f z (x:>y) = pfold f z x`f`pfold f z y<br />
<br />
In order to avoid infinite types (which are not intrinsicly dangerous in a programming language but wreak havoc in logic because terms such as fix a. (a -> b) correspond to statements such as "this statement is false"), we check whether the replaced variable is mentioned in the replacing term:<br />
<br />
> cnt p(A i) j = p && i == j<br />
> cnt p(a:>b) j = cnt True a j || cnt True b j<br />
<br />
The deduction steps are performed by a standard unification routine:<br />
<br />
> unify :: P -> P -> P -> Maybe P<br />
> unify (A i) s (A j) | cnt False s i = Nothing<br />
> | i == j = Just $ s<br />
> | otherwise = Just $ A j<br />
> unify f@(A i) s (a:>b) = liftM2 (:>) (unify f s a) (unify f s b)<br />
> unify f s@(A i) pl = unify s f pl<br />
> unify (a:>b) (c:>d) pl = let u = unify a c in join $ liftM3 unify (u b) (u d) (u pl)<br />
<br />
We need to renumber terms to prevent name conflicts.<br />
<br />
> fan (A x) = A (x*2)<br />
> fan (x:>y)= fan x:> fan y<br />
<br />
Make a deduction given a rule, by setting the LHS of the rule equal to the state and taking the RHS of the rule.<br />
<br />
> deduce t r = let (a:>b)=r in unify (fan t) a b<br />
<br />
Canonicalize the numbers in the rule, thus allowing matching.<br />
<br />
> canon :: P -> P<br />
> canon x = pmap (toInteger . fromJust . flip elemIndex ( allvars x )) x<br />
> allvars :: P -> [U]<br />
> allvars = pfold union (:[])<br />
<br />
Given this, we can lazily construct the list of all true statements:<br />
> facts = nub $ (axiom:) $ map canon $ catMaybes $ liftM2 deduce facts rules<br />
<br />
main=getLine>>=print.(`elem`facts).read</div>Stefanhttps://wiki.haskell.org/index.php?title=Short_theorem_prover&diff=9663Short theorem prover2006-12-22T02:04:56Z<p>Stefan: 625 *character* theroum prover, and dissection (FIXME: looking like haddocks)</p>
<hr />
<div>Theorum prover in 625 characters of Haskell<br />
<br />
> import Monad;import Maybe;import List<br />
> infixr 9 ?<br />
> (?)=(:>);z=Just;y=True<br />
> data P=A Integer|P:>P deriving(Read,Show,Eq)<br />
> [a,b,c,d,e,f]=map A[1,3..11]<br />
> g=h(?).(A.)<br />
> h f z(A x)=z x<br />
> h f z(x:>y)=h f z x`f`h f z y<br />
> i p(A i)j=p&&i==j<br />
> i p(a:>b)j=i y a j||i y b j<br />
> j(A l)s(A k)|i False s l=Nothing|l==k=z s|y=z$A k<br />
> j f@(A i)s(a:>b)=liftM2(?)(j f s a)(j f s b)<br />
> j f s@(A i)p=j s f p<br />
> j(a:>b)(c:>d)p=let u=j a c in join$liftM3 j(u b)(u d)(u p)<br />
> l x=g(toInteger.fromJust.flip elemIndex (h union (:[]) x))x<br />
> m=(a?a:)$map l$catMaybes$liftM2(uncurry.j.g(*2))m[((((a?b?c)<br />
> ?(a?b)?a?c)?(d?e?d)?f),f),((a?b),(c?a)?c?b)]<br />
> main=getLine>>=print.(`elem`m).read<br />
<br />
You are not expected to understand that, so here is the explanation:<br />
<br />
First, we need a type of prepositions. Each A constructor represents a prepositional variable (a, b, c, etc), and :> represents implication. Thus, for example, (A 0 :> A 0) is the axiom of tautology in classical logic.<br />
<br />
> type U = Integer<br />
> data P = A U | P:>P deriving(Read,Show,Eq)<br />
> infixr 9 :><br />
<br />
To prove theorums, we need axioms and deduction rules. This theorum prover is based on the [[Curry-Howard-Lambek correspondance]] applied to the programming language Jot (http://ling.ucsd.edu/~barker/Iota/#Goedel). Thus, we have a single basic combinator and two deduction rules, corresponding to partial application of the base case and two combinators of Jot.<br />
<br />
> axiom = A 0:>A 0<br />
> rules = let[a,b,c,d,e,f]=map A[1,3..11]in[ (((a:>b:>c):>(a:>b):>a:>c):>(d:>e:>d):>f):>f, (a:>b):>(c:>a):>c:>b]<br />
<br />
We will also define foogomorphisms on the data structure:<br />
<br />
> pmap :: (U -> U) -> P -> P<br />
> pmap f = pfold (:>) (A .f)<br />
<br />
> pfold :: (a -> a -> a) -> (U -> a) -> P -> a<br />
> pfold f z (A x) = z x<br />
> pfold f z (x:>y) = pfold f z x`f`pfold f z y<br />
<br />
In order to avoid infinite types (which are not intrinsicly dangerous in a programming language but wreak havoc in logic because terms such as fix a. (a -> b) correspond to statements such as "this statement is false"), we check whether the replaced variable is mentioned in the replacing term:<br />
<br />
> cnt p(A i) j = p && i == j<br />
> cnt p(a:>b) j = cnt True a j || cnt True b j<br />
<br />
The deduction steps are performed by a standard unification routine:<br />
<br />
> unify :: P -> P -> P -> Maybe P<br />
> unify (A i) s (A j) | cnt False s i = Nothing<br />
> | i == j = Just $ s<br />
> | otherwise = Just $ A j<br />
> unify f@(A i) s (a:>b) = liftM2 (:>) (unify f s a) (unify f s b)<br />
> unify f s@(A i) pl = unify s f pl<br />
> unify (a:>b) (c:>d) pl = let u = unify a c in join $ liftM3 unify (u b) (u d) (u pl)<br />
<br />
We need to renumber terms to prevent name conflicts.<br />
<br />
> fan (A x) = A (x*2)<br />
> fan (x:>y)= fan x:> fan y<br />
<br />
Make a deduction given a rule, by setting the LHS of the rule equal to the state and taking the RHS of the rule.<br />
<br />
> deduce t r = let (a:>b)=r in unify (fan t) a b<br />
<br />
Canonicalize the numbers in the rule, thus allowing matching.<br />
<br />
> canon :: P -> P<br />
> canon x = pmap (toInteger . fromJust . flip elemIndex ( allvars x )) x<br />
> allvars :: P -> [U]<br />
> allvars = pfold union (:[])<br />
<br />
Given this, we can lazily construct the list of all true statements:<br />
> facts = nub $ (axiom:) $ map canon $ catMaybes $ liftM2 deduce facts rules<br />
<br />
main=getLine>>=print.(`elem`facts).read</div>Stefanhttps://wiki.haskell.org/index.php?title=GenericSerialize&diff=9506GenericSerialize2006-12-16T06:46:51Z<p>Stefan: mostly verbatim copy from haskell@ announce</p>
<hr />
<div>GenericSerialize is a library for serializing data using the existing<br />
"Scrap your boilerplate" infrastructure.<br />
<br />
The main advantage that generic serialization posseses is that it is<br />
possible to simultaneously have several serialization modes. While<br />
interfaces such as AltBinary allow writing to any type of stream, the<br />
data format is fixed. By contrast, GenericSerialize supports multiple<br />
serialization modes; while the only currently existing module is for a<br />
subset of R5RS s-expressions, that module is less than 90 lines of code<br />
and is almost pure grammar.<br />
<br />
It can be obtained from:<br />
darcs get http://members.cox.net/stefanor/genericserialize</div>Stefanhttps://wiki.haskell.org/index.php?title=Applications_and_libraries/Data_structures&diff=9505Applications and libraries/Data structures2006-12-16T06:42:14Z<p>Stefan: GenericSerialize</p>
<hr />
<div>{{unknown copyright}}<br />
{{LibrariesPage}}<br />
<br />
== Haskell Libraries and Tools for Data Structures ==<br />
<br />
;[http://www.eecs.tufts.edu/~rdocki01/edison.html Edison]<br />
:This is the latest version of the Edison library of efficient data structures. There are also [http://www.haskell.org/ghc/docs/edison/ earlier version of Edison] by Chris Okasaki. It provides sequences, finite maps, priority queues, and sets/bags. ([http://www.eecs.usma.edu/Personnel/okasaki/pubs.html#hw00 overview paper]).<br />
<br />
;[http://homepages.nildram.co.uk/~ahey/HLibs/Data.Tree.AVL/ Data.Tree.AVL]<br />
:An implementation of AVL trees and related utilities.<br />
<br />
;[http://homepages.nildram.co.uk/~ahey/HLibs/Data.StringMap/ Data.StringMap]<br />
:A library providing maps from String keys to values, based on Tries.<br />
<br />
;[http://www.cs.vu.nl/Strafunski/ Strafunski]<br />
:A bundle for generic programming. It provides programming support for generic traversal as useful in the implementation of program transformations.<br />
<br />
;[http://www.lochan.org/2005/keith-cl/libs/ Partial v0.1]<br />
:The Partial library provides a partial order class. It also provides routines for generating a Hasse diagram from a set and a partial order. Renderers are provided for the abstract Hasse diagram representation into LaTeX (via Xy-pic) and into dot, the format for AT&amp;T's Graphviz tools. Since no horizontal sorting is done, the Xy-pic output is rather poor at present; dot does a much better job with its layout optimisation algorithm.<br />
<br />
;[http://web.engr.oregonstate.edu/~erwig/diet/ Discrete Interval Encoding Trees]<br />
:The discrete interval encoding tree is a structure for storing subsets of types having a total order and a predecessor and a successor function.<br />
<br />
;[http://sourceforge.net/projects/ranged-sets/ Ranged Sets]<br />
:A ranged set is a list of non-overlapping ranges. The ranges have upper and lower boundaries, and a boundary divides the base type into values above and below. No value can ever sit on a boundary. So you can have the set {2.0 < x <= 3.0, 5.3 < x < 6}<br />
<br />
;[http://www.cwi.nl/~ralf/HList/ HList]<br />
:A heterogeneous collection is a datatype that is capable of storing data of different types, while providing operations for look-up, update, iteration, and others. There are various kinds of heterogeneous collections, differing in representation, invariants, and access operations.<br />
<br />
;[http://www.csee.ogi.edu/~diatchki/monadLib monadLib]<br />
:Iavor Diatchki's library of monad transformers for Haskell. It enables the quick construction of monads --- abstract data types that capture common programming idioms, such as throwing and catching exceptions or continuations. In many programming languages such features are built into the language (if they're provided at all), but in Haskell they are user-programmable.<br />
<br />
;[http://wiki.di.uminho.pt/wiki/bin/view/Alcino/PointlessHaskell Pointless Haskell]<br />
:Pointless Haskell is library for [[pointfree|point-free]] programming with recursion patterns defined as hylomorphisms. It also allows the visualization of the intermediate data structure of the hylomorphisms with GHood. This feature together with the DrHylo tool allows us to easily visualize recursion trees of Haskell functions.<br />
<br />
;[http://www.informatik.uni-freiburg.de/~wehr/haskell/ rhaskell : Reactive Objects]<br />
:Stefan Wehr's reactive objects library. Reactive objects are a convenient abstraction for writing programs which have to interact with a concurrent environment. A reactive object has two characteristics: the abandonment of all blocking operations and the unification of the concepts state and process. The former allows a reactive object to accept input from multiple sources without imposing any ordering on the input events. The latter prevents race conditions because the state of an object is only manipulated from the process belonging to the object.<br />
<br />
;[http://repetae.net/john/recent/out/GenUtil.html GenUtil]<br />
:A collection of random useful utility functions written in pure Haskell 98. In general, it trys to conform to the naming scheme put forth the Haskell prelude and fill in the obvious omissions, as well as provide useful routines in general.<br />
<br />
;[http://www.cs.uu.nl/~afie/pd09122004.zip PersistentDocument] ''The link is dead, somebody please either update it or remove it.''<br />
:The persistent document abstraction takes care of dealing with a document you want to open from and save to disk and that supports undo. This functionality can be used by editors of arbitrary documents and saves you a lot of quite subtle coding.<br />
<br />
;[[Zipper monad]]<br />
:A generic monad for navigating around arbitrary data structures<br />
<br />
=== Graphs ===<br />
<br />
;[http://web.engr.oregonstate.edu/~erwig/fgl/haskell/ FGL - A Functional Graph Library]<br />
:The functional graph library provides a collection of graph operations.<br />
<br />
;[http://wiki.di.uminho.pt/wiki/bin/view/PURe/PUReSoftware Data.Relation]<br />
:Part of the UMinho Haskell libraries, this library provides a representation and operations on relations. A special case of relations are graphs. The operations include graph chopping and slicing, strong connected component analysis, graphs metrics, and more.<br />
<br />
;[http://article.gmane.org/gmane.comp.lang.haskell.libraries/4739 Haskell Graph Automorphism Library]<br />
:Jean-Philippe Bernardy's implementation of Brendan McKay's algorithm for graph canonic labeling and automorphism group (Nauty).<br />
<br />
=== IO ===<br />
<br />
;[http://haskell.org/haskellwiki/Library/Streams Streams]<br />
:Streams is a feature-rich, flexible, extensible, backward-compatible and fast I/O library. It supports various stream types: files and legacy Handle type, string and memory buffers, pipes. There is also common functionality, available for any stream: buffering, Char encoding, locking.<br />
<br />
<br />
=== Mutable data ===<br />
<br />
;[http://www.isi.edu/~hdaume/STPP/ The Haskell STate Preprocessor]<br />
:This is a short preprocessor for stateful Haskell programs. It aleviates the pain of performing single array lookup/write/update functions with some syntax to support it. It also supports hash table operations based on the HashTable implementation available from the author. Finally, it supports monadic if and monadic case constructions. It is lightweight in the sense that it performs no syntactic analysis and is essentially a character transformer.<br />
<br />
;[http://haskell.org/haskellwiki/Library/ArrayRef Arrays & References Library]<br />
:Featuring:<br />
* Unboxed references in IO and ST monads<br />
* Monad-independent interfaces to boxed and unboxed references<br />
* Syntax sugar to make using of mutable objects easier (=:, +=, -=,..)<br />
* Reimplemented Arrays library with the following improvements:<br />
* Unboxed arrays now can be used in polymorphic functions<br />
* The MArray class now supports arrays with dynamic bounds<br />
* Implementation of dynamic (resizable) arrays<br />
<br />
See also [[Modern array libraries]]<br />
<br />
=== Lists ===<br />
<br />
;[http://code.google.com/p/slist/ SList]<br />
:Sized lists for Haskell<br />
<br />
;[http://www.cse.unsw.edu.au/~dons/dlist.html dlist]<br />
:Difference lists (supporting O(1) append and snoc)<br />
<br />
=== Strings ===<br />
<br />
;[http://www.cse.unsw.edu.au/~dons/fps.html Data.ByteString]<br />
:The FPS library provides mmapped and malloc'd packed strings (byte arrays held by a ForeignPtr), along with a list interface to these strings. It lets you do extremely fast I/O in Haskell; in some cases, even faster than typical C implementations, as well as conserving space.<br />
<br />
;[http://quux.org/devel/missingh MissingH]<br />
:MissingH is a library of pure-Haskell utility functions relating to strings, logging, and I/O.<br />
<br />
;[http://repetae.net/john/recent/out/HsLocale.html HsLocale]<br />
:A locale-aware replacement for the standard IO routines, and support for ''wide'' strings<br />
<br />
;[http://www.cse.unsw.edu.au/~dons/code/icfp05/tests/unit-tests/VariableExpansion.hs VariableExpansion]<br />
:A library for variable expansion inside strings<br />
<br />
;[http://haskell-i18n.cvs.sourceforge.net/haskell-i18n/ i18n strings]<br />
:At sourceforge<br />
<br />
=== Serialising data ===<br />
<br />
;[http://www.n-heptane.com/nhlab/repos/NewBinary NewBinary]<br />
:A port of Malcolm Wallace's Binary library from NHC, offering facilities for heap compression and binary I/O. The de-facto standard for binary I/O in Haskell<br />
<br />
;[http://www.cs.helsinki.fi/u/ekarttun/SerTH/ SerTH]<br />
:SerTH is a binary serialization library for Haskell. It supports serializing cyclic datatypes in a fast binary format. SerTH uses template haskell for deriving the serializing interface for new datatypes.<br />
<br />
;[http://haskell.org/haskellwiki/Library/AltBinary AltBinary]<br />
: AltBinary is an exhaustive library that support binary I/O and serialization. It's part of [http://haskell.org/haskellwiki/Library/Streams Streams] library, so serialization is possible to any I/O source, from String to memory-mapped file. It's also backward compatible with [http://www.n-heptane.com/nhlab/repos/NewBinary NewBinary] library what makes translation of old code trivial. Very fast, very feature-rich, Hugs/GHC compatible, etc, etc...<br />
<br />
;[http://svn.openfoundry.org/pugs/third-party/HsSyck/ HsSyck]<br />
:YAML is a straightforward machine parsable data serialization format designed for human readability and interaction with dynamic languages. It is optimized for data serialization, configuration settings, log files, Internet messaging and filtering. Syck is an extension, written in C, for reading and writing YAML swiftly in popular scripting languages. It is part of core Ruby, and also has bindings for Perl 5, Python, Lua, Cocoa, and Perl 6. HsSyck provides Data.Yaml.Syck as an interface to YAML structures, using Data.ByteString for efficient textual data representation. Additionally, we provide a set of DrIFT rules to dump and load arbitrary Haskell data types in the YAML format.<br />
<br />
;[[GenericSerialize]]<br />
:GenericSerialize is a library which serializes data using the "Scrap Your Boilerplate" infrastructure. This means that while it cannot easily support data-structure-specific serialization, it can support many different data formats cheaply.<br />
<br />
=== Compressing data ===<br />
<br />
;[http://freearc.narod.ru/ Compression-2005]<br />
:Features of the Compression-2005 Library: <br />
* easy and uniform access to most competitive free compression algorithms as of April'05: LZMA, PPMd and GRZip<br />
* all input/output performed via user-supplied functions (callbacks), so you can compress data in memory, files, pipes, sockets and anything else<br />
* all parameters of compression algorithm are defined with a single string, for example "lzma:8mb:fast:hc4:fb32". <br />
* Using this library, you can write a bzip-like utility in one line, with better compression results than bzip2 itself.<br />
<br />
;[http://haskell.org/~duncan/zlib Zlib]<br />
:Zlib bindings for ByteStrings. darcs get http://haskell.org/~duncan/zlib ([http://haskell.org/~duncan/zlib/docs docs])<br />
<br />
;[http://haskell.org/~duncan/bzlib BZip2]<br />
:BZip2 bindings for ByteStrings. darcs get http://haskell.org/~duncan/bzlib ([http://haskell.org/~duncan/bzlib/docs docs])<br />
<br />
=== Benchmarking data structures ===<br />
<br />
;[http://www.cs.york.ac.uk/fp/auburn/ Auburn]<br />
:Auburn is Graeme Moss's kit for benchmarking implementations of lazy data structures. Give it several implementations of an ADT (abstract data type) and it will tell you which one is best for your particular application.<br />
<br />
;[http://www.cse.unsw.edu.au/~dons/code/fps/tests/Bench.hs Bench]<br />
:Simple time and space benchmarking for various list-like data structures. Easily adapted to arbitrary structures<br />
<br />
=== Generic traverals ===<br />
<br />
;[http://eecs.oregonstate.edu/~erwig/reclib/ RecLib A Recursion and Traversal Library for Haskell]<br />
:The Recursion Library for Haskell provides a rich set of generic traversal strategies to facilitate the flexible specification of generic term traversals. The underlying mechanism is the Scrap Your Boilerplate (SYB) approach. Most of the strategies that are used to implement recursion operators are taken from Stratego.</div>Stefanhttps://wiki.haskell.org/index.php?title=HaskLS&diff=8789HaskLS2006-11-30T05:24:21Z<p>Stefan: Fix url typo</p>
<hr />
<div>Welcome to the HaskLS page, a Haskell implementation for Lindenmayer Systems (L-systems). The goal is to implement L-systems in Haskell, and provide a way to visualize them using [http://www.haskell.org/HOpenGL HOpenGL] (otherwise, they just produce a bunch of crap).<br />
<br />
website: http://www.elis.ugent.be/~kehoste/Haskell/HaskLS<br />
<br />
contact: kenneth [dot] hoste [at] UGent [dot] be<br />
<br />
This project is a part of a bigger project, called ["H3D"]. Its goal is to start up a 3D modeller project in Haskell.<br />
<br />
== Current Status ==<br />
<br />
First (context-free and deterministic) L-system implementation. Graphic support: simple visualization with HOpenGL, GUI which allows to set some parameters...<br />
<br />
The code is available in a darcs repository located at http://www.elis.ugent.be/~kehoste/Haskell/HaskLS/darcs/haskls. <br />
<br />
It also includes a nice HOpenGL example ([http://www.elis.ugent.be/~kehoste/Haskell/HaskLS/darcs/haskls/RotatingCube.lhs RotatingCube.lhs]).<br />
<br />
There is also a port to [http://haskell.org/gtk2hs/archives/2005/11/11/more-opengl-goodness/ "Gtk2Hs's OpenGL widget"] rather than using GLUT. [http://www.haskell.org/gtk2hs/albums/OpenGL/HaskLS.png (screenshot)]<br />
<br />
== Some links for more information ==<br />
<br />
* http://en.wikipedia.org/wiki/L-system (general info on L-systems)<br />
* http://www.nbb.cornell.edu/neurobio/land/OldStudentProjects/cs490-94to95/hwchen (3D L-system using C and Direct3D)<br />
* http://www.director-online.com/buildArticle.php?id=1119 (implementation info on 2D and 3D L-systems)<br />
* http://www.alesdar.org/oldSite/IS/chap4-4.html (3D L-system in C++)<br />
* http://www.mario-konrad.ch/index.php?page=20016 (3D L-system in Java using OpenGL)<br />
* http://cgm.cs.mcgill.ca/~msuder/courses/557/tutorial/tutorial.html (OpenGL tutorial)<br />
* http://www.cin.ufpe.br/~haskell/hopengl (old HOpenGL tutorial, most of it wont work with HOpenGL-2.0)<br />
* http://www.tfh-berlin.de/~panitz/hopengl/skript.html (big tutorial for HOpenGL)<br />
* http://www.coscorrosa.com/programs/lsysexp/source/latest/src/builtin.h (lot's of L-System examples)<br />
<br />
== HaskLs and splines ==<br />
<br />
hints by bourbaki:<br />
<br />
* <bourbaki> boegel the idea is that ... ie think of the first think of the tree the root<br />
* <bourbaki> it starts in one point and that is on the ground on the ground you have a circle as a shape<br />
* <bourbaki> and then in the next position you have lets say an ellipse<br />
* <bourbaki> then you want to have something like<br />
* <bourbaki> spline1( lambda ) = pos_on_spline_1<br />
* <bourbaki> spline2( mu ) = pos_on_spline_2<br />
* <bourbaki> and now the homotopy comes into play<br />
* <bourbaki> hom( spline1, spline2, t1, t2 ) = spline( spline1( t1 ), spline2( t1 ), t2 )<br />
* <bourbaki> boegel i mean that along the < and turn symbols you also have a variable along that tells you the amount<br />
* <bourbaki> that way you can do animations of the thickness of branches of changeing textures like makeing the bark darker where the tree is older or so<br />
* <bourbaki> there also are growth models with lsystems that make use of the nutrition of the plant propageteing stuff throught the lsystem string and so<br />
<br />
----<br />
<br />
boegel<br />
<br />
[[Category:Applications]]</div>Stefanhttps://wiki.haskell.org/index.php?title=Curry-Howard-Lambek_correspondence&diff=8710Curry-Howard-Lambek correspondence2006-11-28T01:04:12Z<p>Stefan: describe negation</p>
<hr />
<div>[[Category:Theoretical foundations]]<br />
The '''Curry-Howard-Lambek correspondance''' is a three way isomorphism between types (in programming languages), propositions (in logic) and objects of a Cartesian closed [[Category theory|category]]. Interestingly, the isomorphism maps programs (functions in Haskell) to (constructive) proofs in logic (and ''vice versa''). <br />
<br />
__TOC__<br />
<br />
== The Answer ==<br />
As is well established by now,<br />
<haskell>theAnswer :: Integer<br />
theAnswer = 42</haskell><br />
The logical interpretation of the program is that the type <hask>Integer</hask> is inhabited (by the value <hask>42</hask>), so the existence of this program ''proves'' the proposition <hask>Integer</hask> (a type without any value is the "bottom" type, a proposition with no proof).<br />
<br />
== Inference ==<br />
A (non-trivial) Haskell function maps a value (of type <hask>a</hask>, say) to another value (of type <hask>b</hask>), therefore, ''given'' a value of type <hask>a</hask> (a proof of <hask>a</hask>), it ''constructs'' a value of type <hask>b</hask> (so the proof is ''transformed'' into a proof of <hask>b</hask>)! So <hask>b</hask> is inhabited if <hask>a</hask> is, and a proof of <hask>a -> b</hask> is established (hence the notation, in case you were wondering).<br />
<br />
<haskell><br />
representation :: Bool -> Integer<br />
representation False = 0<br />
representation True = 1<br />
</haskell><br />
<br />
says, for example, if <hask>Boolean</hask> is inhabited, so is <hask>Integer</hask> (well, the point here is demonstration, not discovery).<br />
<br />
== Connectives ==<br />
Of course, atomic propositions contribute little towards knowledge, and the Haskell type system incorporates the logical connectives <math>\and</math> and <math>\or</math>, though heavily disguised.<br />
Haskell handles <math>\or</math> conjuction in the manner described by Intuitionistic Logic. When a program has type <math>A \or B</math>, the value returned itself indicates which one. The algebraic data types in Haskell has a tag on each alternative, the constructor, to indicate the injections:<br />
<haskell>data Message a = OK a | Warning a | Error a<br />
<br />
p2pShare :: Integer -> Message String<br />
p2pShare n | n == 0 = Warning "Share! Freeloading hurts your peers."<br />
| n < 0 = Error "You cannot possibly share a negative number of files!"<br />
| n > 0 = OK ("You are sharing " ++ show n ++ " files."<br />
</haskell><br />
So any one of <hask>OK String</hask>, <hask>Warning String</hask> or <hask>Error String</hask> proves the proposition <hask>Message String</hask>, leaving out any two constructors would not invalidate the program. At the same time, a proof of <hask>Message String</hask> can be pattern matched against the constructors to see which one it proves.<br />
On the other hand, to prove <hask>String</hask> is inhabited from the proposition <hask>Message String</hask>, it has to be proven that you can prove <hask>String</hask> from any of the alternatives...<br />
<haskell><br />
show :: Message String -> String<br />
show (OK s) = s<br />
show (Warning s) = "Warning: " ++ s<br />
show (Error s) = "ERROR! " ++ s<br />
</haskell><br />
The <math>\and</math> conjuction is handled via an isomorphism in Closed Cartesian Categories in general (Haskell types belong to this category): <math>\mathrm{Hom}(X\times Y,Z) \cong \mathrm{Hom}(X,Z^Y)</math>. <br />
That is, instead of a function from <math>X \times Y</math> to <math>Z</math>, we can have a function that takes an argument of type <math>X</math> and returns another function of type <math>Y \rightarrow Z</math>, that is, a function that takes <math>Y</math> to give (finally) a result of type <math>Z</math>: this technique is (known as currying) logically means <math>A \and B \rightarrow C \iff A \rightarrow (B \rightarrow C)</math>.<br />
<br />
''(insert quasi-funny example here)''<br />
<br />
So in Haskell, currying takes care of the <math>\and</math> connective. Logically, a proof of <math>A \and B</math> is a pair <math>(a, b)</math> of proofs of the propositions. In Haskell, to have the final <math>C</math> value, values of both <math>A</math> and <math>B</math> have to be supplied (in turn) to the (curried) function. <br />
<br />
== Theorems for free! ==<br />
Things get interesting when polymorphism comes in. The composition operator in Haskell proves a very simple theorem.<br />
<br />
<haskell><br />
(.) :: (a -> b) -> (b -> c) -> (a -> c)<br />
(.) f g x = f (g x)<br />
</haskell><br />
<br />
The type is, actually, <hask>forall a b c. (a -> b) -> (b -> c) -> (a -> c)</hask>, to be a bit verbose, which says, logically speaking, for all propositions <hask>a, b</hask> and <hask>c</hask>, if from <hask>a</hask>, <hask>b</hask> can be proven, and if from <hask>b</hask>, <hask>c</hask> can be proven, then from <hask>a</hask>, <hask>c</hask> can be proven (the program says how to go about proving: just compose the given proofs!)<br />
<br />
== Negation ==<br />
Of course, there's not much you can do with just truth. <hask>forall b. a -> b</hask> says that given <hask>a</hask>, we can infer anything. Therefore we will take <hask>forall b. a -> b</hask> as meaning <hask>not a</hask>. Given this, we can prove several more of the axioms of logic.<br />
<br />
<haskell><br />
type Not x = (forall a. x -> a)<br />
<br />
doubleNegation :: x -> Not (Not x)<br />
doubleNegation k pr = pr k<br />
<br />
contraPositive :: (a -> b) -> (Not b -> Not a)<br />
contraPositive fun denyb showa = denyb (fun showa)<br />
<br />
deMorganI :: (Not a, Not b) -> Not (Either a b)<br />
deMorganI (na, _) (Left a) = na a<br />
deMorganI (_, nb) (Right b) = nb b<br />
<br />
deMorganII :: Either (Not a) (Not b) -> Not (a,b)<br />
deMorganII (Left na) (a, _) = na a<br />
deMorganII (Right nb) (_, b) = nb b<br />
</haskell><br />
<br />
== Type classes ==<br />
A type class in Haskell is a proposition ''about'' a [[type]]. <br />
<br />
<haskell><br />
class Eq a where<br />
(==) :: a -> a -> Bool<br />
(/=) :: a -> a -> Bool<br />
</haskell><br />
<br />
means, logically, there is a type <hask>a</hask> for which the type <hask>a -> a -> Bool</hask> is inhabited, or, from <hask>a</hask> it can be proved that <hask>a -> a -> Bool</hask> (the class promises two different proofs for this, having names <hask>==</hask> and <hask>/=</hask>). <br />
This proposition is of existential nature (not to be confused with [[existential type]]). A proof for this proposition (that there is a type that conforms to the specification) is (obviously) a set of proofs of the advertized proposition (an implementation), by an <hask>instance</hask><br />
declaration:<br />
<br />
<haskell><br />
instance Eq Bool where<br />
True == True = True<br />
False == False = True<br />
_ == _ = False<br />
<br />
(/=) a b = not (a == b)<br />
</haskell><br />
<br />
A not-so-efficient Quicksort implementation would be:<br />
<br />
<haskell><br />
quickSort [] = []<br />
quickSort (x : xs) = quickSort lower ++ [x] ++ quickSort higher<br />
where lower = filter (<= x) xs<br />
higher = filter (> x) xs<br />
</haskell><br />
<br />
Haskell infers its type to be <hask>forall a. (Ord a) => [a] -> [a]</hask>. It means, if a type <hask>a</hask> satisfies the proposition about propositions <hask>Ord</hask> (that is, has an ordering defined, as is necessary for comparison), then <hask>quickSort</hask> is a proof of <hask>[a] -> [a]</hask>. For this to work, somewhere, it should be proved (that is, the comparison functions defined) that <hask>Ord a</hask> is true.<br />
<br />
== Multi-parameter type classes ==<br />
Haskell makes frequent use of multiparameter type classes. Type classes use a logic language (Prolog-like), and for multiparamter type classes they define a relation between types.<br />
=== [[Functional dependencies]] ===<br />
These type level functions are set-theoretic. That is, <hask> class TypeClass a b | a -> b</hask> defines a relation between types <hask>a</hask> and <hask>b</hask>, and requires that there would not be different instances of <hask>TypeClass a b</hask> and <hask>TypeClass a c</hask> for different <hask>b</hask> and <hask>c</hask>, so that, essentially, <hask>b</hask> can be inferred as soon as <hask>a</hask> is known. This is precisely functions as relations as prescribed by set theory.<br />
<br />
== Indexed types ==<br />
''(please someone complete this, should be quite interesting, I have no idea what it should look like logically)''</div>Stefanhttps://wiki.haskell.org/index.php?title=New_monads/MonadRandomSplittable&diff=8402New monads/MonadRandomSplittable2006-11-17T23:49:24Z<p>Stefan: The use case that led me to reinvent this monad</p>
<hr />
<div>[[Category:Code]]<br />
<br />
When using [[New monads/MonadRandom]], one may also want to use a <hask>MonadRandom</hask> equivalent of <hask>RandomGen</hask>'s <hask>split</hask> function:<br />
<br />
<haskell><br />
class (MonadRandom m) => MonadRandomSplittable m where<br />
splitRandom :: m a -> m a<br />
<br />
instance (Monad m, RandomGen g) => MonadRandomSplittable (RandomT g m) where<br />
splitRandom ma = (RandomT . liftState) split >>= lift . evalRandomT ma<br />
</haskell><br />
<br />
MonadRandomSplittable can then be derived for Rand by [[GHC]]:<br />
<haskell><br />
newtype Rand g a = Rand { unRand :: RandomT g Identity a }<br />
deriving (Functor, Monad, MonadRandom, MonadRandomSplittable)<br />
</haskell><br />
<br />
== Example of usage ==<br />
<br />
<haskell><br />
test :: Rand StdGen [Bool] -> (Int, [Bool], Int)<br />
test ma = evalRand (liftM3 (,,) (getRandomR (0,99)) ma (getRandomR (0,99)))<br />
(mkStdGen 0)<br />
</haskell><br />
<br />
Then<br />
<haskell><br />
*MonadRandom> test (replicateM 0 getRandom)<br />
(45,[],55)<br />
*MonadRandom> test (replicateM 2 getRandom)<br />
(45,[True,True],0)<br />
<br />
*MonadRandom> test (splitRandom $ replicateM 0 getRandom)<br />
(45,[],16)<br />
*MonadRandom> test (splitRandom $ replicateM 2 getRandom)<br />
(45,[False,True],16)<br />
<br />
*MonadRandom> case test undefined of (a,_,c) -> (a,c)<br />
*** Exception: Prelude.undefined<br />
*MonadRandom> case test (splitRandom undefined) of (a,_,c) -> (a,c)<br />
(45,16)<br />
</haskell><br />
<br />
== Laws ==<br />
<br />
It is not clear to me exactly what [[Monad laws|laws]] <hask>splitRandom</hask> should satisfy, besides monadic variations of the "split laws" from the [http://haskell.org/onlinereport/random.html Haskell Library Report]<br />
<br />
For all terminating <hask>ma</hask> and <hask>mb</hask>, it should hold that<br />
<haskell><br />
liftM3 (\a _ c -> (a,c)) getRandom ma getRandom === liftM3 (\a _ c -> (a,c)) getRandom mb getRandom<br />
</haskell><br />
<br />
For [[monad transformer]]s, it would also be nice if<br />
<haskell><br />
splitRandom undefined === splitRandom (return ()) >> lift undefined<br />
</haskell><br />
<br />
For example,<br />
<haskell><br />
>runIdentity $ runRandomT (splitRandom (return ()) >> lift undefined >> return ()) (mkStdGen 0)<br />
((),40014 2147483398)<br />
>runIdentity $ runRandomT (splitRandom undefined >> return ()) (mkStdGen 0)<br />
((),40014 2147483398)<br />
</haskell><br />
But<br />
<haskell><br />
>runRandomT (splitRandom (return ()) >> lift undefined >> return ()) (mkStdGen 0)<br />
*** Exception: Prelude.undefined<br />
>runRandomT (splitRandom undefined >> return ()) (mkStdGen 0)<br />
*** Exception: Prelude.undefined<br />
</haskell><br />
<br />
I have no idea how to express this idea for monads that aren't transformers though. But for <hask>Rand</hask> it means that:<br />
<haskell><br />
>runRand (splitRandom undefined >> return ()) (mkStdGen 0)<br />
((),40014 2147483398)<br />
</haskell><br />
<br />
== Why? ==<br />
In <hask>replicateM 100 (splitRandom expensiveAction)</hask> There are no RNG-dependencies between the different expensiveActions, so they may be computed in parallel.<br />
<br />
<haskell><br />
makeRandomTree = do this <- randomNode<br />
left <- split $ randomLeftChild this<br />
right <- split $ randomRightChild this<br />
return $ Node this left right<br />
</haskell><br />
By removing the RNG-dependencies, infinite random data structures can be constructed lazily.</div>Stefanhttps://wiki.haskell.org/index.php?title=Algebraic_data_type&diff=7206Algebraic data type2006-10-22T18:12:57Z<p>Stefan: typo fix</p>
<hr />
<div>This is a [[type]] where we specify the shape of each of the elements.<br />
<br />
==Tree examples==<br />
<br />
Suppose we want to represent the following tree:<br />
<br />
5<br />
/ \<br />
3 7<br />
/ \<br />
1 4<br />
<br />
We may actually use a variety of Haskell data declarations that will handle this.<br />
===Binary search tree===<br />
<br />
In this example, values are stored at each node, with smaller values to the left, greater to the right.<br />
<br />
<haskell><br />
data Stree a = Tip | Node (Stree a) a (Stree a)<br />
</haskell><br />
and then our example tree would be:<br />
<haskell><br />
etree = Node (Node (Node Tip 1 Tip) 3 (Node Tip 4 Tip)) 5 (Node Tip 7 Tip)<br />
</haskell><br />
<br />
To maintain the order, such a tree structure is usually paired with a [[Smart constructor]].<br />
<br />
===Rose tree===<br />
Alternatatively, it may be represented in what appears to be a totally different stucture.<br />
<haskell><br />
data Rose a = Rose a [Rose a]<br />
</haskell><br />
In this case, the examlple tree would be:<br />
<haskell><br />
retree = Rose 5 [Rose 3 [Rose 1 [], Rose 4[]], Rose 7 []]<br />
</haskell><br />
<br />
The two representations are almost equivalent, with the exception that the <br />
binary search tree <hask>Tip</hask> is not representable in this <hask>Rose</hask> type declaration. Also, due to laziness, I believe we could represent infinite trees with the above declaration.<br />
<br />
[[Category:Language]]</div>Stefanhttps://wiki.haskell.org/index.php?title=Research_papers/Runtime_systems&diff=4502Research papers/Runtime systems2006-06-21T02:44:19Z<p>Stefan: </p>
<hr />
<div>__TOC__<br />
<br />
;[http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/spineless-tagless-gmachine.ps.gz&pub=34 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.<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.<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.)<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)<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://www.reid-consulting-uk.ltd.uk/alastair/publications/ifl98/index.html 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.cs.bris.ac.uk/~spilio/festival.ps.gz 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://www.cs.chalmers.se/~boquist/ifl96.ps 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 />
==Profiling==<br />
<br />
;[http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/1997_profiling_TOPLAS.ps.gz&pub=ACM 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/YCS-92-172.ps.Z Heap Profiling of Lazy Functional Programs]<br />
:Colin Runciman and David Wakeling. York University. YCS-92-172. 1992.<br />
<br />
;[http://www.cs.york.ac.uk/ftpdir/reports/YCS-95-256.ps.Z New Dimensions in Heap Profiling]<br />
:Colin Runciman and Niklas Rojemo. York University. YCS-95-256. 1995.<br />
<br />
==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 Fax�n. 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://www.cse.unsw.edu.au/~dons/papers/SC05.html 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://www.cs.chalmers.se/~rjmh/Papers/cds-loops.ps 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 />
==Concurrency==<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/conc-ffi/index.htm Extending the Haskell Foreign Function Interface with Concurrency]<br />
:Simon Marlow, Simon Peyton Jones, and Wolfgang Thaller, Proceedings of the Haskell Workshop, Snowbird, Sept 2004.<br />
<br />
;[http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/concurrent-haskell.ps.gz&pub=ACM Concurrent Haskell]<br />
:SL Peyton Jones, A Gordon, S Finne, 23rd ACM Symposium on Principles of Programming Languages, St Petersburg Beach, Florida, Jan 1996, pp295-308.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/marktoberdorf Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell]<br />
:In "Engineering theories of software construction", ed Tony Hoare, Manfred Broy, Ralf Steinbruggen, IOS Press, ISBN 1 58603 1724, 2001, pp47-96.<br />
<br />
;[http://www.haskell.org/~simonmar/papers/web-server-jfp.pdf Developing a high-performance web server in Concurrent Haskell]<br />
:Simon Marlow. Journal of Functional Programming, 12(4+5):359--374, July 2002<br />
<br />
==Parallel Haskell==<br />
<br />
;[http://www.haskell.org/~simonmar/papers/multiproc.pdf Haskell on a Shared-Memory Multiprocessor]<br />
:Tim Harris, Simon Marlow, Simon Peyton Jones) Haskell '05: Proceedings of the 2005 ACM SIGPLAN workshop on Haskell, pages 49--61, Tallinn, Estonia, ACM Press, September 2005<br />
<br />
==Software transactional memory==<br />
<br />
;[http://www.haskell.org/~simonmar/papers/stm.pdf Composable Memory Transactions] <br />
:Tim Harris, Simon Marlow, Simon Peyton Jones, Maurice Herlihy. PPoPP'05: ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Chicago, Illinois, June 2005<br />
<br />
;[http://www.haskell.org/~simonmar/papers/lockfreedatastructures.pdf Lock Free Data Structures using STMs in Haskell]<br />
:Anthony Discolo, Tim Harris, Simon Marlow, Simon Peyton Jones, Satnam Singh) FLOPS 2006: Eighth International Symposium on Functional and Logic Programming, Fuji Susono, JAPAN, April 2006<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://www.galois.com/~sof/papers/hdirect.ps.gz 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.</div>Stefan