Why can't Haskell be faster?

[Arnar Birgisson]

Hi there,

I'm new here, so sorry if I'm stating the obvious.

On Nov 1, 2007 2:46 PM, apfelmus <apfelmus@...> wrote:

> Stefan Holdermans wrote:
> > Exposing uniqueness types is, in that sense, just an alternative
> > to monadic encapsulation of side effects.
>
> While  *World -> (a, *World)  seems to work in practice, I wonder what
> its (denotational) semantics are. I mean, the two programs
>
>    loop, loop' :: *World -> ((),*World)
>
>    loop  w = loop w
>    loop' w = let (_,w') = print "x" w in loop' w'
>
> both have denotation _|_ but are clearly different in terms of side
> effects. (The example is from SPJs awkward-squad tutorial.) Any pointers?

For side-effecting program one has to consider bisimilarity. It's
common that semantically equivalent (under operational or denotational
semantics) behave differently with regard to side-effects (i/o) - i.e.
they are not bisimilar.

http://en.wikipedia.org/wiki/Bisimulation

Arnar
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Bryan O'Sullivan]

Ketil Malde wrote:

> Python used to do pretty well here compared
> to Haskell, with rather efficient hashes and text parsing, although I
> suspect ByteString IO and other optimizations may have changed that
> now.

It still does just fine.  For typical "munge a file with regexps, lists,
and maps" tasks, Python and Perl remain on par with comparably written
Haskell.  This because the scripting-level code acts as a thin layer of
glue around I/O, regexps, lists, and dicts, all of which are written in
native code.

The Haskell regexp libraries actually give us something of a leg down
with respect to Python and Perl.  The aggressive use of polymorphism in
the return type of (=~) makes it hard to remember which of the possible
return types gives me what information.  Not only did I write a regexp
tutorial to understand the API in the first place, I have to reread it
every time I want to match a regexp.

A suitable solution would be a return type of RegexpMatch a => Maybe a
(to live alongside the existing types, but aiming to become the one
that's easy to remember), with appropriate methods on a, but I don't
have time to write up a patch.

        <b
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Justin Bailey]

On 10/31/07, ajb@... <ajb@...> wrote:
> I didn't keep a copy, but if someone wants to retrieve it from the Google
> cache and put it on the new wiki (under the new licence, of course), please
> do so.
>
> Cheers,
> Andrew Bromage

Done: http://www.haskell.org/haskellwiki/RuntimeCompilation . Please
update it as needed.

Justin
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[ChrisK-5]

Hi Bryan,

  I wrote the current regex API, so your suggestions are interesting to me.  The
also goes for anyone else's regex API opinions, of course.

Bryan O'Sullivan wrote:
> Ketil Malde wrote:
>
>> Python used to do pretty well here compared
>> to Haskell, with rather efficient hashes and text parsing, although I
>> suspect ByteString IO and other optimizations may have changed that
>> now.

>
> It still does just fine.  For typical "munge a file with regexps, lists,
> and maps" tasks, Python and Perl remain on par with comparably written
> Haskell.  This because the scripting-level code acts as a thin layer of
> glue around I/O, regexps, lists, and dicts, all of which are written in
> native code.
>
> The Haskell regexp libraries actually give us something of a leg down
> with respect to Python and Perl.

True, the pure Haskell library is not as fast as a C library.  In particular,
the current regex-tdfa handles lazy bytestring in a sub-optimal manner.  This
may eventually be fixed.

But the native code libraries have also been wrapped in the same API, and they
are quite fast when combined with strict ByteStrings.

> The aggressive use of polymorphism in
> the return type of (=~) makes it hard to remember which of the possible
> return types gives me what information.  Not only did I write a regexp
> tutorial to understand the API in the first place, I have to reread it
> every time I want to match a regexp.

The (=~) operator uses many return types provided by the instances of
RegexContext.  These are all thin wrappers around the unpolymorphic return types
of the RegexLike class.  So (=~) could be avoided altogether, or another API
created.

>
> A suitable solution would be a return type of RegexpMatch a => Maybe a
> (to live alongside the existing types, but aiming to become the one
> that's easy to remember), with appropriate methods on a, but I don't
> have time to write up a patch.
>
>     <b

The (=~~) is the monadic wrapper for (=~) to allow for different failure
behaviors.  So using (=~~) with Maybe is already possible, and gives Nothing
whenever there are zero matches.

But more interesting to me is learning what API you would like to see.
What would you like the code that uses the API to be?
Could you sketch either the definition or usage of your RegexMatch class suggestion?

I don't use my own regex API much, so external feedback and ideas would be
wonderful.

--
Chris

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Bryan O'Sullivan]

ChrisK wrote:

>> The Haskell regexp libraries actually give us something of a leg down
>> with respect to Python and Perl.
>
> True, the pure Haskell library is not as fast as a C library.

Actually, I wasn't referring to the performance of the libraries, merely
to the non-stick nature of the API.  For my purposes, regex-pcre
performs well (though I owe you some patches to make it, and other regex
back ends, compile successfully out of the box).

> But more interesting to me is learning what API you would like to see.
> What would you like the code that uses the API to be?

Python's regexp API is pretty easy to use, and also to remember.  Here's
what it does for match objects.

http://docs.python.org/lib/match-objects.html

        <b
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Tim Newsham]

> Unfortunately, they replaced line counts with bytes of gzip'ed code --
> while the former certainly has its problems, I simply cannot imagine
> what relevance the latter has (beyond hiding extreme amounts of
> repetitive boilerplate in certain languages).

Sounds pretty fair to me.  Programming is a job of compressing a solution
set.  Excessive boilerplate might mean that you have to type a lot, but
doesn't necessarily mean that you have to think a lot.  I think the
previous line count was skewed in favor of very terse languages like
haskell, especially languages that let you put many ideas onto a single
line.  At the very least there should be a constant factor applied when
comparing haskell line counts to python line counts, for example.
(python has very strict rules about putting multiple things on the same
line).

Obviously no simple measure is going to satisfy everyone, but I think the
gzip measure is more even handed across a range of languages.  It probably
more closely aproximates the amount of mental effort and hence time it
requires to construct a program (ie. I can whip out a lot of lines of code
in python very quickly, but it takes a lot more of them to do the same
work as a single, dense, line of haskell code).

> When we compete against Python and its ilk, we do so for programmer
> productivity first, and performance second.  LOC was a nice measure,
> and encouraged terser and more idiomatic programs than the current
> crop of performance-tweaked low-level stuff.

The haskell entries to the shootout are very obviously written for speed
and not elegance.  If you want to do better on the LoC measure, you can
definitely do so (at the expense of speed).

> -k

Tim Newsham
http://www.thenewsh.com/~newsham/
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Sebastian Sylvan]

On 01/11/2007, Tim Newsham <newsham@...> wrote:

> > Unfortunately, they replaced line counts with bytes of gzip'ed code --
> > while the former certainly has its problems, I simply cannot imagine
> > what relevance the latter has (beyond hiding extreme amounts of
> > repetitive boilerplate in certain languages).
>
> Sounds pretty fair to me.  Programming is a job of compressing a solution
> set.  Excessive boilerplate might mean that you have to type a lot, but
> doesn't necessarily mean that you have to think a lot.  I think the
> previous line count was skewed in favor of very terse languages like
> haskell, especially languages that let you put many ideas onto a single
> line.  At the very least there should be a constant factor applied when
> comparing haskell line counts to python line counts, for example.
> (python has very strict rules about putting multiple things on the same
> line).
>
> Obviously no simple measure is going to satisfy everyone, but I think the
> gzip measure is more even handed across a range of languages.  It probably
> more closely aproximates the amount of mental effort and hence time it
> requires to construct a program (ie. I can whip out a lot of lines of code
> in python very quickly, but it takes a lot more of them to do the same
> work as a single, dense, line of haskell code).
>
> > When we compete against Python and its ilk, we do so for programmer
> > productivity first, and performance second.  LOC was a nice measure,
> > and encouraged terser and more idiomatic programs than the current
> > crop of performance-tweaked low-level stuff.
>
> The haskell entries to the shootout are very obviously written for speed
> and not elegance.  If you want to do better on the LoC measure, you can
> definitely do so (at the expense of speed).
>

Personally I think syntactic noise is highly distracting, and semantic
noise is even worse! Gzip'd files don't show you that one language
will require you to do 90%  book-keeping for 10% algorithm, while the
other lets you get on with the job, it may make it look as if both
languages are roughly equally good at letting the programmer focus on
the important bits.

I'm not sure what metric to use, but actively disgusing noisy
languages using compression sure doesn't seem like anywhere close to
the ideal. Token count would be good, but then we'd need a parser for
each language, which is quite a bit of work to do...


--
Sebastian Sylvan
[phone]
UIN: 44640862
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Hugh Perkins]

On 10/31/07, Paulo J. Matos <pocm@...> wrote:
> Hello all,
>
> I, along with some friends, have been looking to Haskell lately. I'm
> very happy with Haskell as a language, however, a friend sent me the
> link:
> http://shootout.alioth.debian.org/gp4/
>

Careful: it's worse than you think.  Many of the solutions to the
shootout test are using "imperative" Haskell.  "Real" "functional"
Haskell performs significantly slower.  (Orders of magnitude)
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Lennart Augustsson]

Yes, of course.  But they don't do partial evaluation.

On 11/1/07, Bulat Ziganshin <bulat.ziganshin@...> wrote:

Hello Lennart,

Thursday, November 1, 2007, 2:45:49 AM, you wrote:

> But yeah, a code generator at run time is a very cool idea, and one
> that has been studied, but not enough.

vm-based languages (java, c#) has runtimes that compile bytecode to
the native code at runtime

--
Best regards,
Bulat                            mailto:Bulat.Ziganshin@...

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Paul Hudak]

One can certainly use an operational semantics such as bisimulation, but you don't have to abandon denotational semantics.  The trick is to make output part of the "final answer".  For a conventional imperative language one could define, for example, a (lifted, recursive) domain:

Answer = Terminate + (String x Answer)

and then define a semantic function "meaning", say, such that:

meaning loop = _|_
meaning loop' = <"x", <"x", ... >>

In other words, loop denotes bottom, whereas loop' denotes the infinite sequence of "x"s.  There would typically also be a symbol to denote proper termination, perhaps <>.

A good read on this stuff is Reynolds book "Theories of Programming Languages", where domain constructions such as the above are called "resumptions", and can be made to include input as well.

In the case of Clean, programs take as input a "World" and generate a "World" as output.  One of the components of that World would presumably be "standard output", and that component's value would be _|_ in the case of loop, and <"x", <"x", ... >> in the case of loop'.  Another part of the World might be a file system, a printer, a missile firing, and so on.  Presumably loop and loop' would not affect those parts of the World.

If returning one World is semantically problematical, one might also devise a semantics where the result is a sequence of Worlds.

    -Paul


Arnar Birgisson wrote:

Hi there,

I'm new here, so sorry if I'm stating the obvious.

On Nov 1, 2007 2:46 PM, apfelmus apfelmus@... wrote:
  

Stefan Holdermans wrote:
    

Exposing uniqueness types is, in that sense, just an alternative
to monadic encapsulation of side effects.
      

While  *World -> (a, *World)  seems to work in practice, I wonder what
its (denotational) semantics are. I mean, the two programs

   loop, loop' :: *World -> ((),*World)

   loop  w = loop w
   loop' w = let (_,w') = print "x" w in loop' w'

both have denotation _|_ but are clearly different in terms of side
effects. (The example is from SPJs awkward-squad tutorial.) Any pointers?
    

For side-effecting program one has to consider bisimilarity. It's
common that semantically equivalent (under operational or denotational
semantics) behave differently with regard to side-effects (i/o) - i.e.
they are not bisimilar.

http://en.wikipedia.org/wiki/Bisimulation

Arnar

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[ajb-2]

Quoting Justin Bailey <jgbailey@...>:

> Done: http://www.haskell.org/haskellwiki/RuntimeCompilation . Please
> update it as needed.

Thanks!

Cheers,
Andrew Bromage
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Bulat Ziganshin-2]

Hello Sebastian,

Thursday, November 1, 2007, 9:58:45 PM, you wrote:

> the ideal. Token count would be good, but then we'd need a parser for
> each language, which is quite a bit of work to do...

i think that wc (word count) would be good enough approximation

--
Best regards,
 Bulat                            mailto:Bulat.Ziganshin@...

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Ketil Malde-3]

"Sebastian Sylvan" <sebastian.sylvan@...> writes:

[LOC vs gz as a program complexity metric]

>> Obviously no simple measure is going to satisfy everyone, but I think the
>> gzip measure is more even handed across a range of languages.  
>> It probably more closely aproximates the amount of mental effort [..]

I'm not sure I follow that reasoning?

At any rate, I think the ICFP contest is much better as a measure of
productivity. But, just like for performance, LOC for the shootout can
be used as a micro-benchmark.

> Personally I think syntactic noise is highly distracting, and semantic
> noise is even worse!

This is important - productivity doesn't depend so much on the actual
typing, but the ease of refactoring, identifying and fixing bugs, i.e
*reading* code.

Verbosity means noise, and also lower information content in a
screenful of code.

I think there were some (Erlang?) papers where they showed a
correlation between program size (in LOC), time of development, and
possibly number of bugs?) - regardless of language.

> Token count would be good, but then we'd need a parser for
> each language, which is quite a bit of work to do...

Whatever you do, it'll be an approximation, so why not 'wc -w'?

With 'wc -c' for J etc where programs can be written as spaceless
sequences of symbols.  Or just average chars, words and lines?

-k
--
If I haven't seen further, it is by standing in the footprints of giants
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Heinrich Apfelmus]

Paul Hudak wrote:

>>   loop, loop' :: *World -> ((),*World)
>>
>>   loop  w = loop w
>>   loop' w = let (_,w') = print "x" w in loop' w'
>>
>> both have denotation _|_ but are clearly different in terms of side effects.
>
>    One can certainly use an operational semantics such as bisimulation,
> but you don't have to abandon denotational semantics.  The trick is to
> make output part of the "final answer".  For a conventional imperative
> language one could define, for example, a (lifted, recursive) domain:
>
> Answer = Terminate + (String x Answer)
>
> and then define a semantic function "meaning", say, such that:
>
> meaning loop = _|_
> meaning loop' = <"x", <"x", ... >>
>
> In other words, loop denotes bottom, whereas loop' denotes the infinite
> sequence of "x"s.  There would typically also be a symbol to denote
> proper termination, perhaps <>.
>
> A good read on this stuff is Reynolds book "Theories of Programming
> Languages", where domain constructions such as the above are called
> "resumptions", and can be made to include input as well.
>
> In the case of Clean, programs take as input a "World" and generate a
> "World" as output.  One of the components of that World would presumably
> be "standard output", and that component's value would be _|_ in the
> case of loop, and <"x", <"x", ... >> in the case of loop'.  Another part
> of the World might be a file system, a printer, a missile firing, and so
> on.  Presumably loop and loop' would not affect those parts of the World.

Ah, so the denotational semantics would be a bit like good old
stream-based IO.

However, we have to change the semantics of  -> , there's no way to put
the side effects in *World only. I mean, the problem of both loop and
loop' is that they never return any world at all, the side effects occur
during function evaluation. Then, we'd need a "purity lemma" that states
that any function not involving the type *World as in- and output is
indeed pure, which may be a bit tricky to prove in the presence of
higher-order functions and polymorphism. I mean, the function arrows are
"tagged" for side effects in a strange way, namely by looking like
*World -> ... -> (*World, ...).

In contrast, we can see  IO a  as an abstract (co-)data type subject to
some straightforward operational semantics, no need to mess with the
pure  -> . So, in a sense, the Haskell way is cleaner than the Clean way ;)


Regards,
apfelmus

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Sebastian Sylvan]

On 02/11/2007, Bulat Ziganshin <bulat.ziganshin@...> wrote:
> Hello Sebastian,
>
> Thursday, November 1, 2007, 9:58:45 PM, you wrote:
>
> > the ideal. Token count would be good, but then we'd need a parser for
> > each language, which is quite a bit of work to do...
>
> i think that wc (word count) would be good enough approximation
>

Yes, as long as you police abuse ( eg
"if(somevar)somfunccall(foo,bar,baz)"shouldn't be treated as a single
word)).

--
Sebastian Sylvan
[phone]
UIN: 44640862
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Brandon S. Allbery KF8NH]

On Nov 2, 2007, at 6:35 , apfelmus wrote:

> during function evaluation. Then, we'd need a "purity lemma" that  
> states that any function not involving the type *World as in- and  
> output is indeed pure, which may be a bit tricky to prove in the  
> presence of higher-order functions and polymorphism. I mean, the  
> function arrows are "tagged" for side effects in a strange way,  
> namely by looking like *World -> ... -> (*World, ...).

I don't quite see that; the Clean way looks rather suspiciously like  
my "unwrapped I/O in GHC" example from a couple weeks ago, so I have  
trouble seeing where any difficulty involving functions not using  
*World / RealWorld# creeps in.

I will grant that hiding *World / RealWorld# inside IO is cleaner  
from a practical standpoint, though.  Just not from a semantic one.

--
brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@...
system administrator [openafs,heimdal,too many hats] allbery@...
electrical and computer engineering, carnegie mellon university    KF8NH


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Heinrich Apfelmus]

Brandon S. Allbery KF8NH wrote:

> apfelmus wrote:
>> during function evaluation. Then, we'd need a "purity lemma" that
>> states that any function not involving the type *World as in- and
>> output is indeed pure, which may be a bit tricky to prove in the
>> presence of higher-order functions and polymorphism. I mean, the
>> function arrows are "tagged" for side effects in a strange way, namely
>> by looking like *World -> ... -> (*World, ...).
>
> I don't quite see that; the Clean way looks rather suspiciously like my
> "unwrapped I/O in GHC" example from a couple weeks ago, so I have
> trouble seeing where any difficulty involving functions not using *World
> / RealWorld# creeps in.
>
> I will grant that hiding *World / RealWorld# inside IO is cleaner from a
> practical standpoint, though.  Just not from a semantic one.

What do you mean?

I mean, in Clean, we may ask the following question: are all functions
of type say

   forall a . Either (a -> *World -> a) String -> [*World]

or

   Either (forall a . a -> *World -> a) String -> Maybe *World

pure? In Haskell, the answer to any such question is unconditionally
"yes" (unless you're hacking with unsafePerformIO and GHC internals like
RealWorld# of course) even with plenty of appearances of the  IO  type
constructor. But in Clean, functions may perform side effects, that's
the only way to explain why the examples  loop  and  loop'  aren't the same.


Regards,
apfelmus

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Jonathan Cast-2]

On Fri, 2007-11-02 at 08:35 -0400, Brandon S. Allbery KF8NH wrote:

> On Nov 2, 2007, at 6:35 , apfelmus wrote:
>
> > during function evaluation. Then, we'd need a "purity lemma" that  
> > states that any function not involving the type *World as in- and  
> > output is indeed pure, which may be a bit tricky to prove in the  
> > presence of higher-order functions and polymorphism. I mean, the  
> > function arrows are "tagged" for side effects in a strange way,  
> > namely by looking like *World -> ... -> (*World, ...).
>
> I don't quite see that; the Clean way looks rather suspiciously like  
> my "unwrapped I/O in GHC" example from a couple weeks ago, so I have  
> trouble seeing where any difficulty involving functions not using  
> *World / RealWorld# creeps in.
>
> I will grant that hiding *World / RealWorld# inside IO is cleaner  
> from a practical standpoint, though.  Just not from a semantic one.

On the contrary.  GHC's IO newtype isn't an implementation of IO in
Haskell at all.  It's an implementation in a language that has a
Haskell-compatible subset, but that also has semantically bad constructs
like unsafePerformIO and unsafeInterleaveIO that give side effects to
operations of pure, non-RealWorld#-involving types.  Clean's type system
is specified in a way that eliminates both functions from the language,
which recovers purity.  But proving that is harder than I'd like to
attempt.

jcc


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Brandon S. Allbery KF8NH]

On Nov 2, 2007, at 11:51 , Jonathan Cast wrote:

>> I will grant that hiding *World / RealWorld# inside IO is cleaner
>> from a practical standpoint, though.  Just not from a semantic one.
>
> On the contrary.  GHC's IO newtype isn't an implementation of IO in
> Haskell at all.  It's an implementation in a language that has a
> Haskell-compatible subset, but that also has semantically bad  
> constructs

Differing viewpoints, I guess; from my angle, Clean's "uniqueness  
constraint" looks like a hack hidden in the compiler.

--
brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@...
system administrator [openafs,heimdal,too many hats] allbery@...
electrical and computer engineering, carnegie mellon university    KF8NH


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Jonathan Cast-2]

On Fri, 2007-11-02 at 11:56 -0400, Brandon S. Allbery KF8NH wrote:

> On Nov 2, 2007, at 11:51 , Jonathan Cast wrote:
>
> >> I will grant that hiding *World / RealWorld# inside IO is cleaner
> >> from a practical standpoint, though.  Just not from a semantic one.
> >
> > On the contrary.  GHC's IO newtype isn't an implementation of IO in
> > Haskell at all.  It's an implementation in a language that has a
> > Haskell-compatible subset, but that also has semantically bad  
> > constructs
>
> Differing viewpoints, I guess; from my angle, Clean's "uniqueness  
> constraint" looks like a hack hidden in the compiler.

Yeah.  After all, the "uniqueness constraint" has a theory with an
excellent pedigree (IIUC linear logic, whose proof theory Clean uses
here, goes back at least to the 60s, and Wadler proposed linear types
for IO before anybody had heard of monads).  It's not some random hack
somebody happened to notice would work, any more than existential types
are.

jcc


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe