Fwd: Re: [Haskell-cafe] Functions are first class values in C

newer
Re: [Haskell-cafe] Functions are...

older
Fwd: Re: [Haskell-cafe] more on...

Cristian Baboi

22 Dec 2007 22 Dec '07

9 a.m.

------- Forwarded message ------- From: "Cristian Baboi" To: "Jules Bean" Cc: Subject: Re: [Haskell-cafe] Functions are first class values in C Date: Sat, 22 Dec 2007 15:58:50 +0200 On Sat, 22 Dec 2007 14:09:13 +0200, Jules Bean wrote:

...

Cristian Baboi wrote:

...
Let me show you an example to prove it.

...

That's not C. That's the C preprocessor, which is a textual substitution macro language.

Well, the preprocessor is part of the language in a way. These two come together.

...

Macros certainly aren't first class (you can't pass a macro to a function, only its expansion).

In Haskell I cannot pass a function to a function, only its expansion.

...

C does support function pointers, which are something like first class functions. The main things C lacks which people associate with true first-class function is:

...

The ability to construct anonymous/local functions.

If you look at the example you will see I've done that.

...

The ability to capture local variables and return a function with some variables bound.

If I can construct "anonymous" functions and "constants", I can construct functions with some variables bound.

...

The ability to write type-safe functions with polymorphic arguments.

I didn't know this must be a property of first-class functions. C is staticaly typed, so type errors will be detected. Haskell is just C with some syntactic sugar :-)

Show replies by date

Miguel Mitrofanov

22 Dec 22 Dec

9:25 a.m.

New subject: Functions are first class values in C

...

...
That's not C. That's the C preprocessor, which is a textual substitution macro language.

Well, the preprocessor is part of the language in a way. These two come together.

No. In fact, these are even two different programs, see man cpp.

...

...
Macros certainly aren't first class (you can't pass a macro to a function, only its expansion).

In Haskell I cannot pass a function to a function, only its expansion.

What do you mean by "expansion"? Can you clarify this?

...

...
C does support function pointers, which are something like first class functions. The main things C lacks which people associate with true first-class function is:

...
The ability to construct anonymous/local functions.

If you look at the example you will see I've done that.

No. Your "compose" macro is not a function; for example, you can't use it as an argument to itself (which is easy in Haskell: (.)(.))

...

...
The ability to capture local variables and return a function with some variables bound.

If I can construct "anonymous" functions and "constants", I can construct functions with some variables bound.

See above. You can't.

Cristian Baboi

9:47 a.m.

New subject: Functions are first class values in C

On Sat, 22 Dec 2007 16:25:26 +0200, Miguel Mitrofanov wrote:

...

...
...
That's not C. That's the C preprocessor, which is a textual substitution macro language.

Well, the preprocessor is part of the language in a way. These two come together.

...

No. In fact, these are even two different programs, see man cpp.

These two different programs come together.

...

...
...
Macros certainly aren't first class (you can't pass a macro to a function, only its expansion).

In Haskell I cannot pass a function to a function, only its expansion.

...

What do you mean by "expansion"? Can you clarify this?

f1=\x->x+1 f2=\x->2*x g=\x->x.f1 h=\x->x.(\x->x+1) h is g

...

...
...
C does support function pointers, which are something like first class functions. The main things C lacks which people associate with true first-class function is:

...
The ability to construct anonymous/local functions.

If you look at the example you will see I've done that.

...

No. Your "compose" macro is not a function; for example, you can't use it as an argument to itself (which is easy in Haskell: (.)(.))

Ok.

...

...
...
The ability to capture local variables and return a function with some variables bound.

If I can construct "anonymous" functions and "constants", I can construct functions with some variables bound.

See above. You can't.

Ok.

Miguel Mitrofanov

9:55 a.m.

New subject: Functions are first class values in C

...

...
...
In Haskell I cannot pass a function to a function, only its expansion.

...
What do you mean by "expansion"? Can you clarify this?

f1=\x->x+1 f2=\x->2*x g=\x->x.f1 h=\x->x.(\x->x+1)

h is g

Not clear. Try starting with "function's expansion is..."

Cristian Baboi

9:57 a.m.

New subject: Functions are first class values in C

On Sat, 22 Dec 2007 16:55:08 +0200, Miguel Mitrofanov wrote:

...

...
...
...
In Haskell I cannot pass a function to a function, only its expansion.

...
What do you mean by "expansion"? Can you clarify this?

f1=\x->x+1 f2=\x->2*x g=\x->x.f1 h=\x->x.(\x->x+1)

h is g

Not clear. Try starting with "function's expansion is..."

function's expansion is ... just like macro expansion.

Philippa Cowderoy

10:13 a.m.

New subject: Functions are first class values in C

On Sat, 22 Dec 2007, Cristian Baboi wrote:

...

On Sat, 22 Dec 2007 16:55:08 +0200, Miguel Mitrofanov wrote:

...
...
...
...
In Haskell I cannot pass a function to a function, only its expansion.

...
What do you mean by "expansion"? Can you clarify this?

f1=\x->x+1 f2=\x->2*x g=\x->x.f1 h=\x->x.(\x->x+1)

h is g

Not clear. Try starting with "function's expansion is..."

function's expansion is ... just like macro expansion.

No, it's not. Expanding variables (swapping f1 for \x->x+1) isn't the evaluation mechanism in haskell, g and h really are semantically equivalent values and we can't do actual computation just by expanding variables. Whereas expanding a macro is equivalent to beta-reduction (evaluating a function application), which isn't required before passing something in Haskell. We pass functions, not just their results. Here's a trivial example that does so: (\x -> x) (\x -> x) A lambda calculus classic that doesn't typecheck in Haskell: (\x -> x x) (\x -> x x) Feel free to try evaluating it! -- flippa@flippac.org "I think you mean Philippa. I believe Phillipa is the one from an alternate universe, who has a beard and programs in BASIC, using only gotos for control flow." -- Anton van Straaten on Lambda the Ultimate

Cristian Baboi

10:22 a.m.

New subject: Functions are first class values in C

On Sat, 22 Dec 2007 17:13:55 +0200, Philippa Cowderoy wrote:

...

...
function's expansion is ... just like macro expansion.

No, it's not. Expanding variables (swapping f1 for \x->x+1) isn't the evaluation mechanism in haskell, g and h really are semantically equivalent values and we can't do actual computation just by expanding variables. Whereas expanding a macro is equivalent to beta-reduction (evaluating a function application), which isn't required before passing something in Haskell. We pass functions, not just their results.

Here's a trivial example that does so:

(\x -> x) (\x -> x)

A lambda calculus classic that doesn't typecheck in Haskell:

(\x -> x x) (\x -> x x)

...

Feel free to try evaluating it!

Thank you for your message. I tryed and this is what I've got: ERROR - cannot find "show" function for: *** Expression : (\x -> x) (\x -> x) *** Of type : a -> a

Philippa Cowderoy

10:25 a.m.

New subject: Functions are first class values in C

On Sat, 22 Dec 2007, Cristian Baboi wrote:

...

On Sat, 22 Dec 2007 17:13:55 +0200, Philippa Cowderoy wrote:

...
Here's a trivial example that does so:

(\x -> x) (\x -> x)

A lambda calculus classic that doesn't typecheck in Haskell:

(\x -> x x) (\x -> x x)

...
Feel free to try evaluating it!

Thank you for your message.

I tryed and this is what I've got: ERROR - cannot find "show" function for: *** Expression : (\x -> x) (\x -> x) *** Of type : a -> a

Yep, that's because while it can evaluate it down to (\x -> x) your interpreter doesn't know how to print the result. You can demonstrate that it works by then passing in something to that result though: ((\x ->x) (\x -> x)) 1 You'll have to evaluate the other one by hand. Don't spend too long with it though! -- flippa@flippac.org "The reason for this is simple yet profound. Equations of the form x = x are completely useless. All interesting equations are of the form x = y." -- John C. Baez

Cristian Baboi

10:33 a.m.

New subject: Functions are first class values in C

On Sat, 22 Dec 2007 17:25:34 +0200, Philippa Cowderoy wrote:

...

On Sat, 22 Dec 2007, Cristian Baboi wrote:

...
On Sat, 22 Dec 2007 17:13:55 +0200, Philippa Cowderoy wrote:

...
Here's a trivial example that does so:

(\x -> x) (\x -> x)

A lambda calculus classic that doesn't typecheck in Haskell:

(\x -> x x) (\x -> x x)

...
Feel free to try evaluating it!

Thank you for your message.

I tryed and this is what I've got: ERROR - cannot find "show" function for: *** Expression : (\x -> x) (\x -> x) *** Of type : a -> a

...

Yep, that's because while it can evaluate it down to (\x -> x) your interpreter doesn't know how to print the result. You can demonstrate that it works by then passing in something to that result though:

((\x ->x) (\x -> x)) 1

I know that. The reason the interpreter doesn't know how to print the result is because converting functions to strings doesn't make sense. Thank you.

...

You'll have to evaluate the other one by hand. Don't spend too long with it though!

Don't worry, I'm lazy too :-)

Miguel Mitrofanov

10:22 a.m.

New subject: Functions are first class values in C

...

function's expansion is ... just like macro expansion.

Then you CAN pass a function to another function.

Antti-Juhani Kaijanaho

24 Dec 24 Dec

5:22 a.m.

New subject: Functions are first class values in C

On Sat, Dec 22, 2007 at 05:25:26PM +0300, Miguel Mitrofanov wrote:

...

...
...
That's not C. That's the C preprocessor, which is a textual substitution macro language.

Well, the preprocessor is part of the language in a way. These two come together.

No. In fact, these are even two different programs, see man cpp.

No, in fact, preprocessing is an integral part of translating a C program, see the standard. The standard allows implementing the translation phases 1-6 (the so-called preprocessing phases) as a separate program, but there is no requirement to do that. It is true, however, that preprocessing used to be (in pre-standard days) separate from the language. This has not been true for decades. That said, this is all irrelevant to the question of whether C allows first-class functions. I'm sure we all are capable of writing Haskell programs that do not have simple and readable translations to C :) -- Antti-Juhani Kaijanaho, Jyväskylä, Finland http://antti-juhani.kaijanaho.fi/newblog/ http://www.flickr.com/photos/antti-juhani/

6362

Age (days ago)

6364

Last active (days ago)

List overview

Download

10 comments

4 participants

participants (4)

Antti-Juhani Kaijanaho
Cristian Baboi
Miguel Mitrofanov
Philippa Cowderoy