whither operational semantics?

41 views
Skip to first unread message

raould

unread,
Sep 17, 2009, 8:07:52 PM9/17/09
to
hi,

sounds like folks criticize haskell (and probably rightly so) for not
having a good definition, so implementations can ethically vary
widely. so which fp actually does have well nailed-down semantics?
plus a useful-in-the-real-world implementation (or two or three)?

thanks.

Mark T. B. Carroll

unread,
Sep 17, 2009, 8:28:29 PM9/17/09
to
raould <rao...@gmail.com> writes:

> sounds like folks criticize haskell (and probably rightly so) for not
> having a good definition, so implementations can ethically vary
> widely.

So far I've found that more of a theoretical than a practical problem.
(-:

> so which fp actually does have well nailed-down semantics?

I'd have guessed that Standard ML probably does? The folks over on
comp.lang.functional might know better. From a practical view, I wonder
if Erlang would have to as well.

> plus a useful-in-the-real-world implementation (or two or three)?

http://www.smlnj.org/ would probably be worth a look.

Does anyone know if the Disciplined Disciple Compiler offers a Haskell
variant with less ambiguous semantics?

Mark

Mark T. B. Carroll

unread,
Sep 17, 2009, 8:32:48 PM9/17/09
to
raould <rao...@gmail.com> writes:

> sounds like folks criticize haskell (and probably rightly so) for not
> having a good definition, so implementations can ethically vary
> widely. so which fp actually does have well nailed-down semantics?

Hmm - you've piqued my curiosity - is there something specific about
Haskell's semantics that bothers you? Perhaps it's to do with when
unforced things may be evaluated?

Mark

Paul Rubin

unread,
Sep 17, 2009, 8:34:31 PM9/17/09
to

This might be of interest:

Beauty in the Beast: A Functional Semantics for the Awkward Squad
Wouter Swierstra and Thorsten Altenkirch. Haskell Workshop 2007.
http://www.cse.chalmers.se/~wouter/Publications/BeautyInTheBeast.pdf

Some of Swierstra's other publications at that site (such as his
thesis that I just happened to mention in an unrelated post) touch on
similar subjects.

raould

unread,
Sep 18, 2009, 4:26:38 PM9/18/09
to
> Hmm - you've piqued my curiosity - is there something specific about
> Haskell's semantics that bothers you?

i'm not clueful enough to give a concrete example, but have seen
discussions here and in comp.lang.functional where some folks have
said what i paraphrased (hopefully w/out changing the message too
much). i hazard that it generally has to do with space leaks due to
laziness.

sincerely.

raould

unread,
Sep 18, 2009, 6:45:12 PM9/18/09
to
> Some of Swierstra's other publications at that site (such as his
> thesis that I just happened to mention in an unrelated post) touch on
> similar subjects.

they all sound great (i skimmed the Beast one). anybody know if they
are actually being implemented in some real-world Haskell
implementation? one can dream.

raould

unread,
Sep 18, 2009, 6:48:52 PM9/18/09
to
> I'd have guessed that Standard ML probably does?

ja, i would very much like it if this particular slice of the
multiverse had some smart effective people making SML++ that would be
a conservative clean-up and nailing-down of that language, with
perhaps a few important improvements e.g. really good modules or
whatever other top issue.

Adrian Hey

unread,
Sep 24, 2009, 5:45:44 AM9/24/09
to
Hello Raould

I think the problem with ambiguity wrt space behaviour of Haskell
programs isn't so much with laziness. If all Haskell implementations
were truely lazy then they should all use the same fully determined
reduction order (normal order reduction). Laziness induced space leaks
could be nailed using explicit seqs in the program source.

The problem is that normal order reduction can be inefficient, so
compilers can change the reduction order provided this does not affect
the termination properties. They may use strictness analysis to decide
when this is safe, but this is not mandated nor is the algorithm used
standardised. As strictness analysis is AFAICS effectively the halting
problem in disguise, it has no general solution. Some compilers may well
do a better job than others, hence they won't all use same reduction
order or exhibit same space behaviour for the same source program. In
fact even with the same compiler you may get completely different space
behaviour for the same program, depending on optimisation settings.

Regards
--
Adrian Hey

raould

unread,
Oct 8, 2009, 8:44:43 PM10/8/09
to
> I think the problem with ambiguity wrt space behaviour of Haskell
> programs isn't so much with laziness. If all Haskell implementations
> were truely lazy then they should all use the same fully determined
> reduction order (normal order reduction). Laziness induced space leaks
> could be nailed using explicit seqs in the program source.

as an aside: reading the Clojure list, i often see people tripped up
by laziness there, even w/out the added problem of ambiguous
evaluation order iiuc. i think laziness needs to be really
stupendously explicit in the ascii sources.

heap on top of that the issue of changing reduction order and oy veh.

Reply all
Reply to author
Forward
0 new messages