Evaluation order control between two expressions

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

Evaluation order control between two expressions

Takenobu Tani
Dear Community,

Apologies if I'm missing context.

Does Haskell 2020 specify evaluation order control by `pseq`?

We use `pseq` to guarantee the evaluation order between two expressions.
But Haskell 2010 did not specify how to control the evaluation order between two expressions.
(only specified `seq` in Haskell 2010 section 6.2 [1]. but `seq` don't guarantee the order. [2])

I think it's better to explicitly specify `pseq` as standard way.

Already discussed? or out of scope?


Regards,
Takenobu


_______________________________________________
Haskell-prime mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime
Reply | Threaded
Open this post in threaded view
|

Re: Evaluation order control between two expressions

José Manuel Calderón Trilla
Hello Takenobu,

Great question, this is actually a pretty interesting issue! It isn't
out of scope at all.

The first thing to think about is the following thought experiment:

Without the presence of side-effects, how can you tell the difference
between a `seq` that conforms to the Haskell report and one that
evaluates it's first argument before its second?

If your answer involves `unsafePerformIO` then you're cheating ;)

Even if your first argument to `seq` is an IO action it won't get
executed because `seq` only evaluates to WHNF. It might be possible to
construct a program that allows you to observe the difference, but in
the general case I don't see how you could. I'd be very interested to
be shown otherwise though!

Now in a parallel program things change. When we use `pseq` it's
because we don't want two threads to collide when trying to evaluate
the same expression. Let's look at an example:

x `par` y `seq` x + y

As you noted, the semantics of `seq` doesn't actually guarantee that
`y` will be evaluated before `x + y`. But this only matters because
we've used `par` and introduced threads (via an effect!) and therefore
the possibility of collision. We can avoid this by using `pseq`
instead.

So, both `seq` and `pseq` both allow the programmer to express
*operational* concerns, `seq` is used mostly to eliminate/manage space
leaks, and `pseq` is used to specify order of evaluation. Those
concerns sometimes overlap, but they are different!

It could be argued (and I would agree) that `seq` is a bad name; a
better name might have been something like `synch` [1]. That being
said, unless we add parallelism to the standard (and even then) I am
not sure it would be wise to change the operational behavior of `seq`.
It's current behavior is well established, and if you're writing
sequential Haskell code where order of evaluation matters, it's
probably better to reach for a different tool (IMO). However, if
parallelism is introduced then I'd fight for `pseq` to be part of that
(as you suggest).

I hope that sheds some light on the issue.

Cheers,

Jose

[1]: John Hughes introduced a `synch` combinator in his thesis, but it
had very different semantics, so maybe that's a reason it was avoided?
Someone with more knowledge of the history can probably shed more
light on this.


On Thu, Apr 28, 2016 at 6:56 PM, Takenobu Tani <[hidden email]> wrote:

> Dear Community,
>
> Apologies if I'm missing context.
>
> Does Haskell 2020 specify evaluation order control by `pseq`?
>
> We use `pseq` to guarantee the evaluation order between two expressions.
> But Haskell 2010 did not specify how to control the evaluation order between
> two expressions.
> (only specified `seq` in Haskell 2010 section 6.2 [1]. but `seq` don't
> guarantee the order. [2])
>
> I think it's better to explicitly specify `pseq` as standard way.
>
> Already discussed? or out of scope?
>
> [1]:
> https://www.haskell.org/onlinereport/haskell2010/haskellch6.html#x13-1260006.2
> [2]:
> https://www.schoolofhaskell.com/user/snoyberg/general-haskell/advanced/evaluation-order-and-state-tokens
>
> Regards,
> Takenobu
>
>
> _______________________________________________
> Haskell-prime mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime
>
_______________________________________________
Haskell-prime mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime
Reply | Threaded
Open this post in threaded view
|

Re: Evaluation order control between two expressions

Cale Gibbard

Well, the value of par x y is identical to that of y, so any expression which you could use to semantically distinguish pseq from seq using par could be rewritten into one which did so without involving par.

If the way in which we're telling programs apart involves performance characteristics then it may already be possible to distinguish seq from pseq. It somewhat comes down to whether the implementation of the language is clever enough to notice when compiling seq x y any cases where it might be better to finish evaluating y first and simply evaluate x before making the result of that first evaluation available. GHC does do this rearranging, so probably someone can come up with a good example there.

On Apr 29, 2016 5:38 PM, "José Manuel Calderón Trilla" <[hidden email]> wrote:
Hello Takenobu,

Great question, this is actually a pretty interesting issue! It isn't
out of scope at all.

The first thing to think about is the following thought experiment:

Without the presence of side-effects, how can you tell the difference
between a `seq` that conforms to the Haskell report and one that
evaluates it's first argument before its second?

If your answer involves `unsafePerformIO` then you're cheating ;)

Even if your first argument to `seq` is an IO action it won't get
executed because `seq` only evaluates to WHNF. It might be possible to
construct a program that allows you to observe the difference, but in
the general case I don't see how you could. I'd be very interested to
be shown otherwise though!

Now in a parallel program things change. When we use `pseq` it's
because we don't want two threads to collide when trying to evaluate
the same expression. Let's look at an example:

x `par` y `seq` x + y

As you noted, the semantics of `seq` doesn't actually guarantee that
`y` will be evaluated before `x + y`. But this only matters because
we've used `par` and introduced threads (via an effect!) and therefore
the possibility of collision. We can avoid this by using `pseq`
instead.

So, both `seq` and `pseq` both allow the programmer to express
*operational* concerns, `seq` is used mostly to eliminate/manage space
leaks, and `pseq` is used to specify order of evaluation. Those
concerns sometimes overlap, but they are different!

It could be argued (and I would agree) that `seq` is a bad name; a
better name might have been something like `synch` [1]. That being
said, unless we add parallelism to the standard (and even then) I am
not sure it would be wise to change the operational behavior of `seq`.
It's current behavior is well established, and if you're writing
sequential Haskell code where order of evaluation matters, it's
probably better to reach for a different tool (IMO). However, if
parallelism is introduced then I'd fight for `pseq` to be part of that
(as you suggest).

I hope that sheds some light on the issue.

Cheers,

Jose

[1]: John Hughes introduced a `synch` combinator in his thesis, but it
had very different semantics, so maybe that's a reason it was avoided?
Someone with more knowledge of the history can probably shed more
light on this.


On Thu, Apr 28, 2016 at 6:56 PM, Takenobu Tani <[hidden email]> wrote:
> Dear Community,
>
> Apologies if I'm missing context.
>
> Does Haskell 2020 specify evaluation order control by `pseq`?
>
> We use `pseq` to guarantee the evaluation order between two expressions.
> But Haskell 2010 did not specify how to control the evaluation order between
> two expressions.
> (only specified `seq` in Haskell 2010 section 6.2 [1]. but `seq` don't
> guarantee the order. [2])
>
> I think it's better to explicitly specify `pseq` as standard way.
>
> Already discussed? or out of scope?
>
> [1]:
> https://www.haskell.org/onlinereport/haskell2010/haskellch6.html#x13-1260006.2
> [2]:
> https://www.schoolofhaskell.com/user/snoyberg/general-haskell/advanced/evaluation-order-and-state-tokens
>
> Regards,
> Takenobu
>
>
> _______________________________________________
> Haskell-prime mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime
>
_______________________________________________
Haskell-prime mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime

_______________________________________________
Haskell-prime mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime
Reply | Threaded
Open this post in threaded view
|

Re: Evaluation order control between two expressions

Takenobu Tani
Hi Jose and Cale,

Thank you for clear and detailed explanation.

short summary:

 * `seq`  used to eliminate/manage space leaks
 * `pseq` used to specify order of evaluation

 * `seq` is a bad name, but well established.
 * If we introduce parallelism to standard, we need `pseq` or some method.


It's depending on whether or not corresponding to the parallelism.
I learned a lot. Thank you very much.

Regards,
Takenobu

2016-04-30 8:17 GMT+09:00 Cale Gibbard <[hidden email]>:

Well, the value of par x y is identical to that of y, so any expression which you could use to semantically distinguish pseq from seq using par could be rewritten into one which did so without involving par.

If the way in which we're telling programs apart involves performance characteristics then it may already be possible to distinguish seq from pseq. It somewhat comes down to whether the implementation of the language is clever enough to notice when compiling seq x y any cases where it might be better to finish evaluating y first and simply evaluate x before making the result of that first evaluation available. GHC does do this rearranging, so probably someone can come up with a good example there.

On Apr 29, 2016 5:38 PM, "José Manuel Calderón Trilla" <[hidden email]> wrote:
Hello Takenobu,

Great question, this is actually a pretty interesting issue! It isn't
out of scope at all.

The first thing to think about is the following thought experiment:

Without the presence of side-effects, how can you tell the difference
between a `seq` that conforms to the Haskell report and one that
evaluates it's first argument before its second?

If your answer involves `unsafePerformIO` then you're cheating ;)

Even if your first argument to `seq` is an IO action it won't get
executed because `seq` only evaluates to WHNF. It might be possible to
construct a program that allows you to observe the difference, but in
the general case I don't see how you could. I'd be very interested to
be shown otherwise though!

Now in a parallel program things change. When we use `pseq` it's
because we don't want two threads to collide when trying to evaluate
the same expression. Let's look at an example:

x `par` y `seq` x + y

As you noted, the semantics of `seq` doesn't actually guarantee that
`y` will be evaluated before `x + y`. But this only matters because
we've used `par` and introduced threads (via an effect!) and therefore
the possibility of collision. We can avoid this by using `pseq`
instead.

So, both `seq` and `pseq` both allow the programmer to express
*operational* concerns, `seq` is used mostly to eliminate/manage space
leaks, and `pseq` is used to specify order of evaluation. Those
concerns sometimes overlap, but they are different!

It could be argued (and I would agree) that `seq` is a bad name; a
better name might have been something like `synch` [1]. That being
said, unless we add parallelism to the standard (and even then) I am
not sure it would be wise to change the operational behavior of `seq`.
It's current behavior is well established, and if you're writing
sequential Haskell code where order of evaluation matters, it's
probably better to reach for a different tool (IMO). However, if
parallelism is introduced then I'd fight for `pseq` to be part of that
(as you suggest).

I hope that sheds some light on the issue.

Cheers,

Jose

[1]: John Hughes introduced a `synch` combinator in his thesis, but it
had very different semantics, so maybe that's a reason it was avoided?
Someone with more knowledge of the history can probably shed more
light on this.


On Thu, Apr 28, 2016 at 6:56 PM, Takenobu Tani <[hidden email]> wrote:
> Dear Community,
>
> Apologies if I'm missing context.
>
> Does Haskell 2020 specify evaluation order control by `pseq`?
>
> We use `pseq` to guarantee the evaluation order between two expressions.
> But Haskell 2010 did not specify how to control the evaluation order between
> two expressions.
> (only specified `seq` in Haskell 2010 section 6.2 [1]. but `seq` don't
> guarantee the order. [2])
>
> I think it's better to explicitly specify `pseq` as standard way.
>
> Already discussed? or out of scope?
>
> [1]:
> https://www.haskell.org/onlinereport/haskell2010/haskellch6.html#x13-1260006.2
> [2]:
> https://www.schoolofhaskell.com/user/snoyberg/general-haskell/advanced/evaluation-order-and-state-tokens
>
> Regards,
> Takenobu
>
>
> _______________________________________________
> Haskell-prime mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime
>
_______________________________________________
Haskell-prime mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime


_______________________________________________
Haskell-prime mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime
Reply | Threaded
Open this post in threaded view
|

Re: Evaluation order control between two expressions

Lennart Augustsson
In reply to this post by José Manuel Calderón Trilla
Order of evaluation can be very important for memory use.  So I can imagine cases where seq would run out of memory, but pseq would not. 

I would argue that pseq is almost always what you want, but seq has a nicer denotational semantics. 

  -- Lennart

On Friday, April 29, 2016, José Manuel Calderón Trilla <[hidden email]> wrote:
Hello Takenobu,

Great question, this is actually a pretty interesting issue! It isn't
out of scope at all.

The first thing to think about is the following thought experiment:

Without the presence of side-effects, how can you tell the difference
between a `seq` that conforms to the Haskell report and one that
evaluates it's first argument before its second?

If your answer involves `unsafePerformIO` then you're cheating ;)

Even if your first argument to `seq` is an IO action it won't get
executed because `seq` only evaluates to WHNF. It might be possible to
construct a program that allows you to observe the difference, but in
the general case I don't see how you could. I'd be very interested to
be shown otherwise though!

Now in a parallel program things change. When we use `pseq` it's
because we don't want two threads to collide when trying to evaluate
the same expression. Let's look at an example:

x `par` y `seq` x + y

As you noted, the semantics of `seq` doesn't actually guarantee that
`y` will be evaluated before `x + y`. But this only matters because
we've used `par` and introduced threads (via an effect!) and therefore
the possibility of collision. We can avoid this by using `pseq`
instead.

So, both `seq` and `pseq` both allow the programmer to express
*operational* concerns, `seq` is used mostly to eliminate/manage space
leaks, and `pseq` is used to specify order of evaluation. Those
concerns sometimes overlap, but they are different!

It could be argued (and I would agree) that `seq` is a bad name; a
better name might have been something like `synch` [1]. That being
said, unless we add parallelism to the standard (and even then) I am
not sure it would be wise to change the operational behavior of `seq`.
It's current behavior is well established, and if you're writing
sequential Haskell code where order of evaluation matters, it's
probably better to reach for a different tool (IMO). However, if
parallelism is introduced then I'd fight for `pseq` to be part of that
(as you suggest).

I hope that sheds some light on the issue.

Cheers,

Jose

[1]: John Hughes introduced a `synch` combinator in his thesis, but it
had very different semantics, so maybe that's a reason it was avoided?
Someone with more knowledge of the history can probably shed more
light on this.


On Thu, Apr 28, 2016 at 6:56 PM, Takenobu Tani <<a href="javascript:;" onclick="_e(event, &#39;cvml&#39;, &#39;takenobu.hs@gmail.com&#39;)">takenobu.hs@...> wrote:
> Dear Community,
>
> Apologies if I'm missing context.
>
> Does Haskell 2020 specify evaluation order control by `pseq`?
>
> We use `pseq` to guarantee the evaluation order between two expressions.
> But Haskell 2010 did not specify how to control the evaluation order between
> two expressions.
> (only specified `seq` in Haskell 2010 section 6.2 [1]. but `seq` don't
> guarantee the order. [2])
>
> I think it's better to explicitly specify `pseq` as standard way.
>
> Already discussed? or out of scope?
>
> [1]:
> https://www.haskell.org/onlinereport/haskell2010/haskellch6.html#x13-1260006.2
> [2]:
> https://www.schoolofhaskell.com/user/snoyberg/general-haskell/advanced/evaluation-order-and-state-tokens
>
> Regards,
> Takenobu
>
>
> _______________________________________________
> Haskell-prime mailing list
> <a href="javascript:;" onclick="_e(event, &#39;cvml&#39;, &#39;Haskell-prime@haskell.org&#39;)">Haskell-prime@...
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime
>
_______________________________________________
Haskell-prime mailing list
<a href="javascript:;" onclick="_e(event, &#39;cvml&#39;, &#39;Haskell-prime@haskell.org&#39;)">Haskell-prime@...
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime

_______________________________________________
Haskell-prime mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime
Reply | Threaded
Open this post in threaded view
|

Re: Evaluation order control between two expressions

Takenobu Tani
In reply to this post by Takenobu Tani
Hi Prime,

This is additional information to organize my brain.

This issue also occurs in single thread.
Especially, when they have side effects.

   seq exp1 exp2

Because compiler can always re-order two expressions
in accordance with seq's denotational semantics.

Regards,
Takenobu


2016-04-30 16:11 GMT+09:00 Takenobu Tani <[hidden email]>:
Hi Jose and Cale,

Thank you for clear and detailed explanation.

short summary:

 * `seq`  used to eliminate/manage space leaks
 * `pseq` used to specify order of evaluation

 * `seq` is a bad name, but well established.
 * If we introduce parallelism to standard, we need `pseq` or some method.


It's depending on whether or not corresponding to the parallelism.
I learned a lot. Thank you very much.

Regards,
Takenobu

2016-04-30 8:17 GMT+09:00 Cale Gibbard <[hidden email]>:

Well, the value of par x y is identical to that of y, so any expression which you could use to semantically distinguish pseq from seq using par could be rewritten into one which did so without involving par.

If the way in which we're telling programs apart involves performance characteristics then it may already be possible to distinguish seq from pseq. It somewhat comes down to whether the implementation of the language is clever enough to notice when compiling seq x y any cases where it might be better to finish evaluating y first and simply evaluate x before making the result of that first evaluation available. GHC does do this rearranging, so probably someone can come up with a good example there.

On Apr 29, 2016 5:38 PM, "José Manuel Calderón Trilla" <[hidden email]> wrote:
Hello Takenobu,

Great question, this is actually a pretty interesting issue! It isn't
out of scope at all.

The first thing to think about is the following thought experiment:

Without the presence of side-effects, how can you tell the difference
between a `seq` that conforms to the Haskell report and one that
evaluates it's first argument before its second?

If your answer involves `unsafePerformIO` then you're cheating ;)

Even if your first argument to `seq` is an IO action it won't get
executed because `seq` only evaluates to WHNF. It might be possible to
construct a program that allows you to observe the difference, but in
the general case I don't see how you could. I'd be very interested to
be shown otherwise though!

Now in a parallel program things change. When we use `pseq` it's
because we don't want two threads to collide when trying to evaluate
the same expression. Let's look at an example:

x `par` y `seq` x + y

As you noted, the semantics of `seq` doesn't actually guarantee that
`y` will be evaluated before `x + y`. But this only matters because
we've used `par` and introduced threads (via an effect!) and therefore
the possibility of collision. We can avoid this by using `pseq`
instead.

So, both `seq` and `pseq` both allow the programmer to express
*operational* concerns, `seq` is used mostly to eliminate/manage space
leaks, and `pseq` is used to specify order of evaluation. Those
concerns sometimes overlap, but they are different!

It could be argued (and I would agree) that `seq` is a bad name; a
better name might have been something like `synch` [1]. That being
said, unless we add parallelism to the standard (and even then) I am
not sure it would be wise to change the operational behavior of `seq`.
It's current behavior is well established, and if you're writing
sequential Haskell code where order of evaluation matters, it's
probably better to reach for a different tool (IMO). However, if
parallelism is introduced then I'd fight for `pseq` to be part of that
(as you suggest).

I hope that sheds some light on the issue.

Cheers,

Jose

[1]: John Hughes introduced a `synch` combinator in his thesis, but it
had very different semantics, so maybe that's a reason it was avoided?
Someone with more knowledge of the history can probably shed more
light on this.


On Thu, Apr 28, 2016 at 6:56 PM, Takenobu Tani <[hidden email]> wrote:
> Dear Community,
>
> Apologies if I'm missing context.
>
> Does Haskell 2020 specify evaluation order control by `pseq`?
>
> We use `pseq` to guarantee the evaluation order between two expressions.
> But Haskell 2010 did not specify how to control the evaluation order between
> two expressions.
> (only specified `seq` in Haskell 2010 section 6.2 [1]. but `seq` don't
> guarantee the order. [2])
>
> I think it's better to explicitly specify `pseq` as standard way.
>
> Already discussed? or out of scope?
>
> [1]:
> https://www.haskell.org/onlinereport/haskell2010/haskellch6.html#x13-1260006.2
> [2]:
> https://www.schoolofhaskell.com/user/snoyberg/general-haskell/advanced/evaluation-order-and-state-tokens
>
> Regards,
> Takenobu
>
>
> _______________________________________________
> Haskell-prime mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime
>
_______________________________________________
Haskell-prime mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime



_______________________________________________
Haskell-prime mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime
Reply | Threaded
Open this post in threaded view
|

Re: Evaluation order control between two expressions

Carter Schonwald


On Sat, Apr 30, 2016, 10:16 AM Takenobu Tani <[hidden email]> wrote:
Hi Prime,

This is additional information to organize my brain.

This issue also occurs in single thread.
Especially, when they have side effects.

   seq exp1 exp2

Because compiler can always re-order two expressions
in accordance with seq's denotational semantics.

Regards,
Takenobu

That requires / presumes a none idempotent use of unsafe perform io in those  sub expressions right?




2016-04-30 16:11 GMT+09:00 Takenobu Tani <[hidden email]>:
Hi Jose and Cale,

Thank you for clear and detailed explanation.

short summary:

 * `seq`  used to eliminate/manage space leaks
 * `pseq` used to specify order of evaluation

 * `seq` is a bad name, but well established.
 * If we introduce parallelism to standard, we need `pseq` or some method.


It's depending on whether or not corresponding to the parallelism.
I learned a lot. Thank you very much.

Regards,
Takenobu

2016-04-30 8:17 GMT+09:00 Cale Gibbard <[hidden email]>:

Well, the value of par x y is identical to that of y, so any expression which you could use to semantically distinguish pseq from seq using par could be rewritten into one which did so without involving par.

If the way in which we're telling programs apart involves performance characteristics then it may already be possible to distinguish seq from pseq. It somewhat comes down to whether the implementation of the language is clever enough to notice when compiling seq x y any cases where it might be better to finish evaluating y first and simply evaluate x before making the result of that first evaluation available. GHC does do this rearranging, so probably someone can come up with a good example there.

On Apr 29, 2016 5:38 PM, "José Manuel Calderón Trilla" <[hidden email]> wrote:
Hello Takenobu,

Great question, this is actually a pretty interesting issue! It isn't
out of scope at all.

The first thing to think about is the following thought experiment:

Without the presence of side-effects, how can you tell the difference
between a `seq` that conforms to the Haskell report and one that
evaluates it's first argument before its second?

If your answer involves `unsafePerformIO` then you're cheating ;)

Even if your first argument to `seq` is an IO action it won't get
executed because `seq` only evaluates to WHNF. It might be possible to
construct a program that allows you to observe the difference, but in
the general case I don't see how you could. I'd be very interested to
be shown otherwise though!

Now in a parallel program things change. When we use `pseq` it's
because we don't want two threads to collide when trying to evaluate
the same expression. Let's look at an example:

x `par` y `seq` x + y

As you noted, the semantics of `seq` doesn't actually guarantee that
`y` will be evaluated before `x + y`. But this only matters because
we've used `par` and introduced threads (via an effect!) and therefore
the possibility of collision. We can avoid this by using `pseq`
instead.

So, both `seq` and `pseq` both allow the programmer to express
*operational* concerns, `seq` is used mostly to eliminate/manage space
leaks, and `pseq` is used to specify order of evaluation. Those
concerns sometimes overlap, but they are different!

It could be argued (and I would agree) that `seq` is a bad name; a
better name might have been something like `synch` [1]. That being
said, unless we add parallelism to the standard (and even then) I am
not sure it would be wise to change the operational behavior of `seq`.
It's current behavior is well established, and if you're writing
sequential Haskell code where order of evaluation matters, it's
probably better to reach for a different tool (IMO). However, if
parallelism is introduced then I'd fight for `pseq` to be part of that
(as you suggest).

I hope that sheds some light on the issue.

Cheers,

Jose

[1]: John Hughes introduced a `synch` combinator in his thesis, but it
had very different semantics, so maybe that's a reason it was avoided?
Someone with more knowledge of the history can probably shed more
light on this.


On Thu, Apr 28, 2016 at 6:56 PM, Takenobu Tani <[hidden email]> wrote:
> Dear Community,
>
> Apologies if I'm missing context.
>
> Does Haskell 2020 specify evaluation order control by `pseq`?
>
> We use `pseq` to guarantee the evaluation order between two expressions.
> But Haskell 2010 did not specify how to control the evaluation order between
> two expressions.
> (only specified `seq` in Haskell 2010 section 6.2 [1]. but `seq` don't
> guarantee the order. [2])
>
> I think it's better to explicitly specify `pseq` as standard way.
>
> Already discussed? or out of scope?
>
> [1]:
> https://www.haskell.org/onlinereport/haskell2010/haskellch6.html#x13-1260006.2
> [2]:
> https://www.schoolofhaskell.com/user/snoyberg/general-haskell/advanced/evaluation-order-and-state-tokens
>
> Regards,
> Takenobu
>
>
> _______________________________________________
> Haskell-prime mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime
>
_______________________________________________
Haskell-prime mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime


_______________________________________________
Haskell-prime mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime

_______________________________________________
Haskell-prime mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime
Reply | Threaded
Open this post in threaded view
|

Re: Evaluation order control between two expressions

José Manuel Calderón Trilla
In reply to this post by Lennart Augustsson
On Sat, Apr 30, 2016 at 6:11 AM, Lennart Augustsson
<[hidden email]> wrote:
> Order of evaluation can be very important for memory use.  So I can imagine
> cases where seq would run out of memory, but pseq would not.
>

That's fair enough. Do you think it's worth attempting to standardize
the behavior of `seq` to be like `pseq`?

> I would argue that pseq is almost always what you want, but seq has a nicer
> denotational semantics.

Is this the reason it wasn't standardized this way to begin with?
Miranda's `seq` is like `pseq` (as was `seq` in other lazy language
implementations) so it's not as if there wasn't precedent.
_______________________________________________
Haskell-prime mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime
Reply | Threaded
Open this post in threaded view
|

Re: Evaluation order control between two expressions

John Wiegley-2
>>>>> José Manuel Calderón Trilla <[hidden email]> writes:

> Is this the reason it wasn't standardized this way to begin with? Miranda's
> `seq` is like `pseq` (as was `seq` in other lazy language implementations)
> so it's not as if there wasn't precedent.

Note that this has been discussed previously, but another incarnation of the
Prime committee:

https://mail.haskell.org/pipermail/glasgow-haskell-users/2006-November/011480.html

--
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2
_______________________________________________
Haskell-prime mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime
Reply | Threaded
Open this post in threaded view
|

Re: Evaluation order control between two expressions

Takenobu Tani
In reply to this post by Carter Schonwald
Hi Carter,

You are right. I had mixed case.
In single thread case, I implicitly assumed IO context rather than pure parallel context.

Thank you for explanation.

Regards,
Takenobu


2016-04-30 23:20 GMT+09:00 Carter Schonwald <[hidden email]>:


On Sat, Apr 30, 2016, 10:16 AM Takenobu Tani <[hidden email]> wrote:
Hi Prime,

This is additional information to organize my brain.

This issue also occurs in single thread.
Especially, when they have side effects.

   seq exp1 exp2

Because compiler can always re-order two expressions
in accordance with seq's denotational semantics.

Regards,
Takenobu

That requires / presumes a none idempotent use of unsafe perform io in those  sub expressions right?




2016-04-30 16:11 GMT+09:00 Takenobu Tani <[hidden email]>:
Hi Jose and Cale,

Thank you for clear and detailed explanation.

short summary:

 * `seq`  used to eliminate/manage space leaks
 * `pseq` used to specify order of evaluation

 * `seq` is a bad name, but well established.
 * If we introduce parallelism to standard, we need `pseq` or some method.


It's depending on whether or not corresponding to the parallelism.
I learned a lot. Thank you very much.

Regards,
Takenobu

2016-04-30 8:17 GMT+09:00 Cale Gibbard <[hidden email]>:

Well, the value of par x y is identical to that of y, so any expression which you could use to semantically distinguish pseq from seq using par could be rewritten into one which did so without involving par.

If the way in which we're telling programs apart involves performance characteristics then it may already be possible to distinguish seq from pseq. It somewhat comes down to whether the implementation of the language is clever enough to notice when compiling seq x y any cases where it might be better to finish evaluating y first and simply evaluate x before making the result of that first evaluation available. GHC does do this rearranging, so probably someone can come up with a good example there.

On Apr 29, 2016 5:38 PM, "José Manuel Calderón Trilla" <[hidden email]> wrote:
Hello Takenobu,

Great question, this is actually a pretty interesting issue! It isn't
out of scope at all.

The first thing to think about is the following thought experiment:

Without the presence of side-effects, how can you tell the difference
between a `seq` that conforms to the Haskell report and one that
evaluates it's first argument before its second?

If your answer involves `unsafePerformIO` then you're cheating ;)

Even if your first argument to `seq` is an IO action it won't get
executed because `seq` only evaluates to WHNF. It might be possible to
construct a program that allows you to observe the difference, but in
the general case I don't see how you could. I'd be very interested to
be shown otherwise though!

Now in a parallel program things change. When we use `pseq` it's
because we don't want two threads to collide when trying to evaluate
the same expression. Let's look at an example:

x `par` y `seq` x + y

As you noted, the semantics of `seq` doesn't actually guarantee that
`y` will be evaluated before `x + y`. But this only matters because
we've used `par` and introduced threads (via an effect!) and therefore
the possibility of collision. We can avoid this by using `pseq`
instead.

So, both `seq` and `pseq` both allow the programmer to express
*operational* concerns, `seq` is used mostly to eliminate/manage space
leaks, and `pseq` is used to specify order of evaluation. Those
concerns sometimes overlap, but they are different!

It could be argued (and I would agree) that `seq` is a bad name; a
better name might have been something like `synch` [1]. That being
said, unless we add parallelism to the standard (and even then) I am
not sure it would be wise to change the operational behavior of `seq`.
It's current behavior is well established, and if you're writing
sequential Haskell code where order of evaluation matters, it's
probably better to reach for a different tool (IMO). However, if
parallelism is introduced then I'd fight for `pseq` to be part of that
(as you suggest).

I hope that sheds some light on the issue.

Cheers,

Jose

[1]: John Hughes introduced a `synch` combinator in his thesis, but it
had very different semantics, so maybe that's a reason it was avoided?
Someone with more knowledge of the history can probably shed more
light on this.


On Thu, Apr 28, 2016 at 6:56 PM, Takenobu Tani <[hidden email]> wrote:
> Dear Community,
>
> Apologies if I'm missing context.
>
> Does Haskell 2020 specify evaluation order control by `pseq`?
>
> We use `pseq` to guarantee the evaluation order between two expressions.
> But Haskell 2010 did not specify how to control the evaluation order between
> two expressions.
> (only specified `seq` in Haskell 2010 section 6.2 [1]. but `seq` don't
> guarantee the order. [2])
>
> I think it's better to explicitly specify `pseq` as standard way.
>
> Already discussed? or out of scope?
>
> [1]:
> https://www.haskell.org/onlinereport/haskell2010/haskellch6.html#x13-1260006.2
> [2]:
> https://www.schoolofhaskell.com/user/snoyberg/general-haskell/advanced/evaluation-order-and-state-tokens
>
> Regards,
> Takenobu
>
>
> _______________________________________________
> Haskell-prime mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime
>
_______________________________________________
Haskell-prime mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime


_______________________________________________
Haskell-prime mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime


_______________________________________________
Haskell-prime mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime
Reply | Threaded
Open this post in threaded view
|

Re: Evaluation order control between two expressions

Carter Schonwald


On Sat, Apr 30, 2016 at 8:47 PM Takenobu Tani <[hidden email]> wrote:
Hi Carter,

You are right. I had mixed case.
In single thread case, I implicitly assumed IO context rather than pure parallel context.


thank you for your wonderful questions! 
 
Thank you for explanation.

Regards,
Takenobu


2016-04-30 23:20 GMT+09:00 Carter Schonwald <[hidden email]>:


On Sat, Apr 30, 2016, 10:16 AM Takenobu Tani <[hidden email]> wrote:
Hi Prime,

This is additional information to organize my brain.

This issue also occurs in single thread.
Especially, when they have side effects.

   seq exp1 exp2

Because compiler can always re-order two expressions
in accordance with seq's denotational semantics.

Regards,
Takenobu

That requires / presumes a none idempotent use of unsafe perform io in those  sub expressions right?




2016-04-30 16:11 GMT+09:00 Takenobu Tani <[hidden email]>:
Hi Jose and Cale,

Thank you for clear and detailed explanation.

short summary:

 * `seq`  used to eliminate/manage space leaks
 * `pseq` used to specify order of evaluation

 * `seq` is a bad name, but well established.
 * If we introduce parallelism to standard, we need `pseq` or some method.


It's depending on whether or not corresponding to the parallelism.
I learned a lot. Thank you very much.

Regards,
Takenobu

2016-04-30 8:17 GMT+09:00 Cale Gibbard <[hidden email]>:

Well, the value of par x y is identical to that of y, so any expression which you could use to semantically distinguish pseq from seq using par could be rewritten into one which did so without involving par.

If the way in which we're telling programs apart involves performance characteristics then it may already be possible to distinguish seq from pseq. It somewhat comes down to whether the implementation of the language is clever enough to notice when compiling seq x y any cases where it might be better to finish evaluating y first and simply evaluate x before making the result of that first evaluation available. GHC does do this rearranging, so probably someone can come up with a good example there.

On Apr 29, 2016 5:38 PM, "José Manuel Calderón Trilla" <[hidden email]> wrote:
Hello Takenobu,

Great question, this is actually a pretty interesting issue! It isn't
out of scope at all.

The first thing to think about is the following thought experiment:

Without the presence of side-effects, how can you tell the difference
between a `seq` that conforms to the Haskell report and one that
evaluates it's first argument before its second?

If your answer involves `unsafePerformIO` then you're cheating ;)

Even if your first argument to `seq` is an IO action it won't get
executed because `seq` only evaluates to WHNF. It might be possible to
construct a program that allows you to observe the difference, but in
the general case I don't see how you could. I'd be very interested to
be shown otherwise though!

Now in a parallel program things change. When we use `pseq` it's
because we don't want two threads to collide when trying to evaluate
the same expression. Let's look at an example:

x `par` y `seq` x + y

As you noted, the semantics of `seq` doesn't actually guarantee that
`y` will be evaluated before `x + y`. But this only matters because
we've used `par` and introduced threads (via an effect!) and therefore
the possibility of collision. We can avoid this by using `pseq`
instead.

So, both `seq` and `pseq` both allow the programmer to express
*operational* concerns, `seq` is used mostly to eliminate/manage space
leaks, and `pseq` is used to specify order of evaluation. Those
concerns sometimes overlap, but they are different!

It could be argued (and I would agree) that `seq` is a bad name; a
better name might have been something like `synch` [1]. That being
said, unless we add parallelism to the standard (and even then) I am
not sure it would be wise to change the operational behavior of `seq`.
It's current behavior is well established, and if you're writing
sequential Haskell code where order of evaluation matters, it's
probably better to reach for a different tool (IMO). However, if
parallelism is introduced then I'd fight for `pseq` to be part of that
(as you suggest).

I hope that sheds some light on the issue.

Cheers,

Jose

[1]: John Hughes introduced a `synch` combinator in his thesis, but it
had very different semantics, so maybe that's a reason it was avoided?
Someone with more knowledge of the history can probably shed more
light on this.


On Thu, Apr 28, 2016 at 6:56 PM, Takenobu Tani <[hidden email]> wrote:
> Dear Community,
>
> Apologies if I'm missing context.
>
> Does Haskell 2020 specify evaluation order control by `pseq`?
>
> We use `pseq` to guarantee the evaluation order between two expressions.
> But Haskell 2010 did not specify how to control the evaluation order between
> two expressions.
> (only specified `seq` in Haskell 2010 section 6.2 [1]. but `seq` don't
> guarantee the order. [2])
>
> I think it's better to explicitly specify `pseq` as standard way.
>
> Already discussed? or out of scope?
>
> [1]:
> https://www.haskell.org/onlinereport/haskell2010/haskellch6.html#x13-1260006.2
> [2]:
> https://www.schoolofhaskell.com/user/snoyberg/general-haskell/advanced/evaluation-order-and-state-tokens
>
> Regards,
> Takenobu
>
>
> _______________________________________________
> Haskell-prime mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime
>
_______________________________________________
Haskell-prime mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime


_______________________________________________
Haskell-prime mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime


_______________________________________________
Haskell-prime mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-prime