Re: [Haskell-beginners] Compiling C into Haskell

newer
Re: calling polymorphic function...

Hein Hundal

13 Apr 2010 13 Apr '10

8:39 a.m.

Thanks Allan! I was hoping the C-Haskell mix would work. I am glad to hear that you have good things to say about it. My main reason for thinking about the C-to-Haskell compiler was to address the question "Say you had a C program. Can you always convert it to Haskell in such a way that the compiled Haskell is not too slow and does not need too much memory?" Supposing that too slow means slower than 1/4 the speed of C and too much memory means twice the memory of C. Do you know the answer to this question? Cheers, Hein

Show replies by date

Brent Yorgey

13 Apr 13 Apr

10:42 a.m.

New subject: Compiling C into Haskell

On Tue, Apr 13, 2010 at 05:39:04AM -0700, Hein Hundal wrote:

...

Thanks Allan!

   I was hoping the C-Haskell mix would work. I am glad to hear that you have good things to say about it.

   My main reason for thinking about the C-to-Haskell compiler was to address the question "Say you had a C program. Can you always convert it to Haskell in such a way that the compiled Haskell is not too slow and does not need too much memory?" Supposing that too slow means slower than 1/4 the speed of C and too much memory means twice the memory of C.

   Do you know the answer to this question?

My guess is that the answer is technically "no". If I recall correctly, there are some imperative data structures where the best known time complexity for a functional version is worse than the imperative version by a factor of (log n), so in that case you wouldn't be able to stay within a constant factor of C. However, I think in practice the answer is usually "yes"; but it might be hard to do it via a mechanical compilation. Idiomatic (and fast) Haskell is often organized very differently than corresponding C code. So if you want to know whether you will necessarily be taking a big performance hit in moving from C to Haskell, the answer is usually no, if the translation is sufficiently intelligent --- which a straightforward C-to-Haskell compiler is (probably) not. -Brent

Heinrich Apfelmus

14 Apr 14 Apr

6:21 a.m.

New subject: Compiling C into Haskell

Brent Yorgey wrote:

...

Hein Hundal wrote:

...
I was hoping the C-Haskell mix would work. I am glad to hear that you have good things to say about it.

My main reason for thinking about the C-to-Haskell compiler was to address the question "Say you had a C program. Can you always convert it to Haskell in such a way that the compiled Haskell is not too slow and does not need too much memory?" Supposing that too slow means slower than 1/4 the speed of C and too much memory means twice the memory of C.

Do you know the answer to this question?

My guess is that the answer is technically "no". If I recall correctly, there are some imperative data structures where the best known time complexity for a functional version is worse than the imperative version by a factor of (log n), so in that case you wouldn't be able to stay within a constant factor of C.

Well, you can always fall back to arrays in the ST monad...

...

However, I think in practice the answer is usually "yes"; but it might be hard to do it via a mechanical compilation. Idiomatic (and fast) Haskell is often organized very differently than corresponding C code.

If you already have a C program, then it's probably easiest to link it in with the Foreign Function Interface. Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com

Maciej Piechotka

13 Apr 13 Apr

10:54 a.m.

New subject: Compiling C into Haskell

On Tue, 2010-04-13 at 05:39 -0700, Hein Hundal wrote:

...

Thanks Allan!

I was hoping the C-Haskell mix would work. I am glad to hear that you have good things to say about it.

Why would you like to compile C to Haskell as opposed to using FFI (Foreign Function Interface) - i.e. calling C from Haskell or Haskell from C?

...

My main reason for thinking about the C-to-Haskell compiler was to address the question "Say you had a C program. Can you always convert it to Haskell in such a way that the compiled Haskell is not too slow and does not need too much memory?" Supposing that too slow means slower than 1/4 the speed of C and too much memory means twice the memory of C.

I'd say that given optimal Haskell compiler (and possibly in IO) - yes. However we don't have optimal Haskell compiler (neither optimal C compiler BTW) so Haskell program might be slower. Or faster (like with combination of sorting and taking first element).

...

Do you know the answer to this question?

Cheers, Hein

Regards PS. Could you limit length of line to 72-80 characters? Thank you in advance.

Juan Pedro Bolivar Puente

16 Apr 16 Apr

2:05 a.m.

New subject: Compiling C into Haskell

I am going a bit off-topic here...

...

PS. Could you limit length of line to 72-80 characters? Thank you in advance.

Please, don't impose others how to format their email. There is an interesting reasoning in favor of not breaking lines in email: it is better for accessibility, because of how screen-readers for visually impaired people work. I will quote a message by the accessibility expert Chris Hofstader:

...

I forgot to mention that, when using a screen reader, many users try to maximize their line width so, if reading by line, they can often get an entire paragraph with a single down arrow rather than reading through superfluously narrow lines which have two problems: 1. they require more keystrokes which 2. break up a user's concentration as the flow of sentences are broken up by needing to take action a every few words.

And what is the universally best length of line anyway? I have also seen people sending emails with really thin columns that get annoying to read... If you feel bad about emails sent with long lines, just enable text wrapping in your email reader. And yes, I wrap the text in my email because I know there are many people like you, but maybe this message will help us in being more tolerant about how others use their tools --I did not know about these accessibility issues a few months ago neither! JP

Ertugrul Soeylemez

3:20 a.m.

New subject: Compiling C into Haskell

Juan Pedro Bolivar Puente wrote:

...

I am going a bit off-topic here...

Me too, but that's how mailing lists work. =)

...

And what is the universally best length of line anyway? I have also seen people sending emails with really thin columns that get annoying to read... If you feel bad about emails sent with long lines, just enable text wrapping in your email reader.

The big problem is that some mail/news readers assume that lines are prebroken, especially when it comes to older terminal-based readers. This is bad, but it's the state of things. Otherwise there is little reason to prebreak lines and many reasons not to do it. To answer your question, typographically you should prefer lines with no more and no less than 80-90 characters. Longer lines tend to distract the reader when it comes to find the beginning of the next line. Shorter lines are annoying to read, because you need too much reorientation. That's why all HTML pages I write contain something like the following CSS statement: div#content { max-width: 80ex; } I think mail/news readers like Thunderbird go into the right direction by employing an additional header, which precisely specifies the line breaking behaviour used in the mail. The actual text is prewrapped, but using the header newer readers can reconstruct the paragraphs and display them the way the user wishes. In fact I would love if HTML mails would be more accepted in the open source community. After all there is nothing bad about HTML and it would solve the above problem. Most reasonings against it are related to compatibility or interoperability, which is no problem, because you can always add a text/plain part. Greets, Ertugrul -- nightmare = unsafePerformIO (getWrongWife >>= sex) http://blog.ertes.de/

Thomas Davie

3:28 a.m.

New subject: Compiling C into Haskell

On 16 Apr 2010, at 08:20, Ertugrul Soeylemez wrote:

...

Juan Pedro Bolivar Puente wrote:

...
I am going a bit off-topic here...

Me too, but that's how mailing lists work. =)

...
And what is the universally best length of line anyway? I have also seen people sending emails with really thin columns that get annoying to read... If you feel bad about emails sent with long lines, just enable text wrapping in your email reader.

The big problem is that some mail/news readers assume that lines are prebroken, especially when it comes to older terminal-based readers.

I'd highly recommend that you stop using such readers, or patch them to soft-wrap long lines, neither is difficult.

...

This is bad, but it's the state of things. Otherwise there is little reason to prebreak lines and many reasons not to do it. I think mail/news readers like Thunderbird go into the right direction by employing an additional header, which precisely specifies the line breaking behaviour used in the mail. The actual text is prewrapped, but using the header newer readers can reconstruct the paragraphs and display them the way the user wishes.

Interesting, and useful sounding, though how does it tell the difference between a wrap at 80 characters and an intentional new line at 80 characters?

...

In fact I would love if HTML mails would be more accepted in the open source community. After all there is nothing bad about HTML and it would solve the above problem. Most reasonings against it are related to compatibility or interoperability, which is no problem, because you can always add a text/plain part.

I suspect the only way this would solve the problem is by forcing people not to use broken email clients – you can't read an html email in an old email client, in the same way as you can't read a non-hard-wrapped email in an ancient email client. Anyway, my basic point is that an email client that will not soft-wrap lines is fundamentally broken. Emails can and do have lines longer than 80 characters, and a client that can't render them has a serious bug. If your client is one of these, I suggest you either (a) move to a less buggy client, or (b) write a patch to fix the bug. The correct solution though is not to enforce upon everyone else that they must write emails with a particular line length. Bob

Joost Kremers

4:21 a.m.

New subject: Compiling C into Haskell

On Fri, Apr 16, 2010 at 08:28:25AM +0100, Thomas Davie wrote:

...

Anyway, my basic point is that an email client that will not soft-wrap lines is fundamentally broken.

AFAIK the relevant RFCs state that email should *not* have unwapped lines. Which means that a mail client that doesn't soft-wrap is not broken but standard-conforming.

...

Emails can and do have lines longer than 80 characters, and a client that can't render them has a serious bug.

I disagree. There is a clear standard for dealing with different line lengths. It's called 'format=flowed' and basically states that lines should be wrapped and end in space+newline. Email thus formatted can be reformatted by the client.

...

If your client is one of these, I suggest you either (a) move to a less buggy client, or (b) write a patch to fix the bug. The correct solution though is not to enforce upon everyone else that they must write emails with a particular line length.

format=flowed does exactly that: not force upon everyone to write emails with a particular line length. See RFC 2646. IMHO email clients that send long lines instead of using format=flowed are buggy. -- Joost Kremers Life has its moments

Maciej Piechotka

5:38 a.m.

New subject: Compiling C into Haskell

On Fri, 2010-04-16 at 08:28 +0100, Thomas Davie wrote:

...

On 16 Apr 2010, at 08:20, Ertugrul Soeylemez wrote:

...
Juan Pedro Bolivar Puente wrote:

...
I am going a bit off-topic here...

Me too, but that's how mailing lists work. =)

...
And what is the universally best length of line anyway? I have also seen people sending emails with really thin columns that get annoying to read... If you feel bad about emails sent with long lines, just enable text wrapping in your email reader.

The big problem is that some mail/news readers assume that lines are prebroken, especially when it comes to older terminal-based readers.

I'd highly recommend that you stop using such readers, or patch them to soft-wrap long lines, neither is difficult.

Except that it may be a line which should not be wrapped. For example ascii table should not be wrapped as it destroys the content. Pice of code in Haskell or python as well. And pre-breaking have little problems, confirms to RFC and causes no problems (excepts in broken screen readers. I understand that software should be accessible but it should follow the conventions that was already established a long time ago).

...

...
In fact I would love if HTML mails would be more accepted in the open source community. After all there is nothing bad about HTML and it would solve the above problem. Most reasonings against it are related to compatibility or interoperability, which is no problem, because you can always add a text/plain part.

Add quoting and size. While for 'normal' users it is not a problem it might be problem for users which uses EDGE/GPRS/... to get their mail. From example from http://www.asciiribbon.org/ (not counting sound as it lazy download) - it's 231 K. Text plain is 3K. If you can download 1 MB via EDGE/GPRS/... or pay a lot for extra download - it HAVE a difference (compare using 23% of limit to download a mail and 0.3%). Personally I'd choose to always show text/plain message as: - Security reasons. Last time I heard about text/plain exploit was here - http://ur1.ca/ve1h ;). Ok - I don't use Outlook Express or anything on MSHTML but still there are exploits from time to time. - I cannot use terminal. Sometimes I have to use terminal to browse web/read e-mail. I can tell that HTML engines on terminal are terribly underdeveloped. - Quoting. text/plain quoting is very simple. HTML quoting can be quite hard - how to quote a part of table? what to do with CSS?

...

I suspect the only way this would solve the problem is by forcing people not to use broken email clients – you can't read an html email in an old email client, in the same way as you can't read a non-hard-wrapped email in an ancient email client.

If you mean by 'ancient' released not longer then month ago and confirming to spec then yes ;)

...

Anyway, my basic point is that an email client that will not soft-wrap lines is fundamentally broken. Emails can and do have lines longer than 80 characters, and a client that can't render them has a serious bug. If your client is one of these, I suggest you either (a) move to a less buggy client, or (b) write a patch to fix the bug. The correct solution though is not to enforce upon everyone else that they must write emails with a particular line length.

Bob

Hmm. I guess you can send to the IEFT - all I found in RFC was limits (ok. different - 60, 78 and 80). Regards

Thomas Davie

3:23 a.m.

New subject: Compiling C into Haskell

On 16 Apr 2010, at 07:05, Juan Pedro Bolivar Puente wrote:

...

I am going a bit off-topic here...

...
PS. Could you limit length of line to 72-80 characters? Thank you in advance.

Please, don't impose others how to format their email. There is an interesting reasoning in favor of not breaking lines in email: it is better for accessibility, because of how screen-readers for visually impaired people work. I will quote a message by the accessibility expert Chris Hofstader:

...
I forgot to mention that, when using a screen reader, many users try to maximize their line width so, if reading by line, they can often get an entire paragraph with a single down arrow rather than reading through superfluously narrow lines which have two problems: 1. they require more keystrokes which 2. break up a user's concentration as the flow of sentences are broken up by needing to take action a every few words.

And what is the universally best length of line anyway? I have also seen people sending emails with really thin columns that get annoying to read... If you feel bad about emails sent with long lines, just enable text wrapping in your email reader.

And yes, I wrap the text in my email because I know there are many people like you, but maybe this message will help us in being more tolerant about how others use their tools --I did not know about these accessibility issues a few months ago neither!

Re your last paragraph, please don't (not that I mean to impose this upon you). My final reason to add is that once an email is replied to sufficiently many times, limiting yourself to 72-80 characters can cause major problems: This line: 12345678901234567890123456789012345678901234567890123456789012345678901234567890 Will commonly become:

...

123456789012345678901234567890123456789012345678901234567890123456789012345678 90 Which will become:

...
1234567890123456789012345678901234567890123456789012345678901234567890123456 78 90 etc.

Not only is this annoying, but it's irrecoverable too. There is no way to tell which new lines are some one adding hard wrapping to an email, and which are actual intentional newlines. All this, simply because one user couldn't enable the softwrap option in their email reader. Bob

Maciej Piechotka

4:59 a.m.

New subject: Compiling C into Haskell

On Fri, 2010-04-16 at 09:05 +0300, Juan Pedro Bolivar Puente wrote:

...

I am going a bit off-topic here...

...
PS. Could you limit length of line to 72-80 characters? Thank you in advance.

Please, don't impose others how to format their email. There is an interesting reasoning in favor of not breaking lines in email: it is better for accessibility, because of how screen-readers for visually impaired people work. I will quote a message by the accessibility expert Chris Hofstader:

...
I forgot to mention that, when using a screen reader, many users try to maximize their line width so, if reading by line, they can often get an entire paragraph with a single down arrow rather than reading through superfluously narrow lines which have two problems: 1. they require more keystrokes which 2. break up a user's concentration as the flow of sentences are broken up by needing to take action a every few words.

Depends on the logic of down key. Some editors make down key jump to corresponding visual line some corresponding real line.

...

And what is the universally best length of line anyway? I have also seen people sending emails with really thin columns that get annoying to read... If you feel bad about emails sent with long lines, just enable text wrapping in your email reader.

According to RFC 1855 - 65 characters: "- Limit line length to fewer than 65 characters and end a line with a carriage return." http://tools.ietf.org/html/rfc1855 So it is official. Traditionally the paragraphs are separated by two newlines so there is no problem

...

And yes, I wrap the text in my email because I know there are many people like you, but maybe this message will help us in being more tolerant about how others use their tools --I did not know about these accessibility issues a few months ago neither!

JP

Screen readers could be easily patched too (to skip whole paragraph on key down or shift+key down). The paragraph for email has been traditionally separated by two newlines. Regards

Maciej Piechotka

5:43 a.m.

New subject: Compiling C into Haskell

On Fri, 2010-04-16 at 10:59 +0200, Maciej Piechotka wrote:
> > > I forgot to mention that, when using a screen reader, many  users
> try to maximize their line width so, if reading by line, they can
> often get an entire paragraph with a single down arrow rather than
> reading through superfluously narrow lines which have two problems:
> 1. they require more keystrokes which 2. break up a user's
> concentration as the flow of sentences are broken up by needing to
> take action a every few words.
> > > 
> > 
> 
> Depends on the logic of down key. Some editors make down key jump to
> corresponding visual line some corresponding real line. 

Ups - I haven't read till the end. Modern software does not require
additional keystrokes every few lines but it can breaks automatically.
For example currently writing this mail I haven't presses enter so far
(no copy newline from another editor etc.). It automatically wraps the
line as I write.

I don't have to break my concentration - I just write. Even if I'm
inserting something in the middle it will automatically rewrap the whole
paragraph - there is no need for pressing enter manually or counting
characters.

Regards

matthew coolbeth

6:35 a.m.

New subject: Compiling C into Haskell

Can we move this to another mailing list, guys?  We don't want to put anyone
off learning Haskell.

On Fri, Apr 16, 2010 at 05:43, Maciej Piechotka wrote:

> On Fri, 2010-04-16 at 10:59 +0200, Maciej Piechotka wrote:
> > > > I forgot to mention that, when using a screen reader, many  users
> > try to maximize their line width so, if reading by line, they can
> > often get an entire paragraph with a single down arrow rather than
> > reading through superfluously narrow lines which have two problems:
> > 1. they require more keystrokes which 2. break up a user's
> > concentration as the flow of sentences are broken up by needing to
> > take action a every few words.
> > > >
> > >
> >
> > Depends on the logic of down key. Some editors make down key jump to
> > corresponding visual line some corresponding real line.
>
> Ups - I haven't read till the end. Modern software does not require
> additional keystrokes every few lines but it can breaks automatically.
> For example currently writing this mail I haven't presses enter so far
> (no copy newline from another editor etc.). It automatically wraps the
> line as I write.
>
> I don't have to break my concentration - I just write. Even if I'm
> inserting something in the middle it will automatically rewrap the whole
> paragraph - there is no need for pressing enter manually or counting
> characters.
>
> Regards
>
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
>


-- 
mac

Chaddaï Fouché

14 Apr 14 Apr

6:20 a.m.

New subject: Compiling C into Haskell

On Tue, Apr 13, 2010 at 2:39 PM, Hein Hundal wrote:

...

Thanks Allan!

   I was hoping the C-Haskell mix would work. I am glad to hear that you have good things to say about it.

   My main reason for thinking about the C-to-Haskell compiler was to address the question "Say you had a C program. Can you always convert it to Haskell in such a way that the compiled Haskell is not too slow and does not need too much memory?" Supposing that too slow means slower than 1/4 the speed of C and too much memory means twice the memory of C.

   Do you know the answer to this question?

I would say probably yes, since Haskell can do much of the same thing C does or simulate it closely... But that's not idiomatic Haskell and thus very uninteresting and probably unreadable. A C to idiomatic Haskell compiler would be more interesting but extremely hard to write and the results would probably be pretty slow (since a good and fast translation would necessarily imply some change of algorithms and data-structure and so be too hard even for a smart compiler (needs a full AI ! ;)). If the question is : Can we always write a fast Haskell equivalent ? The response is probably yes (when we can write an Haskell equivalent) but with some effort and not mechanically. Of course, when we have a good enough C library, it may be better to just use the FFI in practice. -- Jedaï

Hein Hundal

7:34 a.m.

New subject: Compiling C into Haskell

Thank you to everyone who responded. My main question was "Say you had a C program. Can you always convert it to Haskell in such a way that the compiled Haskell is not too slow and does not need too much memory?" supposing that too slow means slower than 1/4 the speed of C and too much memory means twice the memory of C. Let me summarize some of your responses: 1) The general consensus seems to be the answer is probably yes. The exceptions, if there are any, are C programs with complex data structures. 2) One of the simpler ways to get the speed and memory efficiency of C is using the ST monad. 3) The "Foreign Function Interface" (FFI) is sometimes used by Haskell programmers to improve the speed or memory efficiency of a slow or memory intensive subroutine. 4) For my particular project, I should look into "hmatrix" which binds to LAPACK, a linear algebra package that I have used before. 5) The conversion process from the C program to the speedy Haskell program is probably not simple. These responses were great! Cheers, Hein

5513

Age (days ago)

5516

Last active (days ago)

List overview

Download

14 comments

10 participants

participants (10)

Brent Yorgey
Chaddaï Fouché
Ertugrul Soeylemez
Hein Hundal
Heinrich Apfelmus
Joost Kremers
Juan Pedro Bolivar Puente
Maciej Piechotka
matthew coolbeth
Thomas Davie