is GHC's implementation of Haskell semantically broken?
I noticed something interesting this morning that I wanted to ask about to see if it is in anyway significant.
So in Haskell, undefined Semantically subsumes non-termination. So it should be impossible to have a function
isUndefined :: a -> Bool
as the semantics would indicate that this solves the halting problem.
However I believe that some of GHC's built in functions allow this restriction to be "fairly reliably" broken. Particularly catch#.
The following code allows undefined values to be "fairly reliably" detected:
import Control.Exception
import System.IO.Unsafe
import Unsafe.Coerce
isUndefined :: a -> Bool
isUndefined x = unsafePerformIO $ catch ((unsafeCoerce x :: IO ()) >> return False) ((e -> return $ show e == "Prelude.undefined") :: SomeException -> IO Bool)
Also, does this really count, as you will have noticed it uses several "unsafe" functions?
Jules
EDIT: Some people seem to think that I claim to have solved the Halting problem XD I'm not being a crank. I am simply stating that there is a rather severe break in the semantics of undefined in that they state that a value of undefined should be in a sense indistinguishable from non-termination. Which this function sort of allows. I just wanted to check if people agree with this and what people think of this, is this unintended side effect of the addition of certain unsafe functions in the GHC implementation of Haskell for convenience a step to far? :)
EDIT: fixed the code to compile
I'd like to make three, ah, no, four (interrelated) points.
No, using unsafe...
doesn't count:
Using unsafeCoerce
is clearly a rule-breaking move, so to answer the question "Does this really count?": no, it doesn't count. unsafe
is the warning that all sorts of stuff breaks, including semantics:
isGood :: a -> Bool
isGood x = unsafePerformIO . fmap read $ readFile "I_feel_like_it.txt"
> isGood '4'
True
> isGood '4'
False
Yikes! Broken semantics according to the Haskell report. Oh, no, wait, I used unsafe...
. I was warned.
The main problem is using unsafeCoerce
, with which you can turn anything into anything else. It's as bad as typecasts in imperative programming, so all type safety has gone out of the window.
You're catch
ing an IOException, not a pure error (⊥).
To use catch, you've converted the pure error undefined
to an IO Exception. The IO
monad is deceptively simple, and the error handling semantics don't require the use of ⊥. Think of it as like a monad transformer including an error-handling Either
at some level.
The link with the halting problem is completely spurious
We don't need any unsafe features of any programming language to cause this sort of distinguishing between non-termination and error.
Imagine two programs. One program Char -> IO ()
that outputs the character, the other which writes the output of the first to a file, then compares that file with the string "*** Exception: Prelude.undefined"
, and finds its length. We can run the first one with input undefined
or with input 'c'
. The first is ⊥, the second is normal termination.
Yikes! We've solved the halting problem by distinguishing between undefined and non-termination. Oh no, wait, no, we've actually only distinguished between undefined
and termination. If we run the two programs on the input non_terminating where non_terminating = head.show.length $ [1..]
, we find the second one doesn't terminate, because the first one doesn't. In fact our second program fails to solve the halting problem, because it itself does not terminate.
A solution to the halting problem would be more like having a total function halts :: (a -> IO ()) -> a -> Bool
that always terminates with the output True
if the given function terminates with input a
, and False
if it never terminates. You're impossibly far from that when you distinguish between undefined
and error "user-defined error"
, which is what your code does.
Thus all your references to the halting problem are confusing deciding whether one program terminates with deciding whether any program terminates. It fails to draw any conclusion if you use the input non-terminating
above instead of undefined
; it's already a big stretch semantically to call that distinguishing between non-termination and undefined
, and it's nonsense to call it a solution to the halting problem.
The problem isn't a huge semantic issue
Essentially all your code is able to do is determine whether your error value was produced using undefined
or some other error producing function. The semantic issue there is that both undefined
and error "not defined with undefined"
have the semantic value ⊥, but you can distinguish between them. OK, that's not very clean theoretically, but having different outputs on different causes for ⊥ is so useful for debugging that it'd be crazy to enforce a common response to the value ⊥, because it would have to be always non-termination to be completely correct.
The result would be that any program with any bug would be obliged to go into an infinite output-free loop when it had an error. This is taking theoretical niceness to the point of deep unhelpfulness. Much better is to print *** Exception: Prelude.undefined
or Error: ungrokable wibbles
or other helpful, descriptive error messages.
To be at all helpful in a crisis, any programming language has to sacrifice your desire to have every ⊥ behave the same as each other. Distinguishing between different ⊥s isn't theoretically lovely, but it would stupid to not do this in practice.
If a programming language theorist calls that a severe semantic problem, they should be teased for living in a world where program-freeze/non-termination is always the best outcome for invalid input.
From the docs:
The highly unsafe primitive unsafeCoerce
converts a value from any type to any other type. Needless to say, if you use this function, it is your responsibility to ensure that the old and new types have identical internal representations, in order to prevent runtime corruption.
It obviously also breaks referential transparency, thus pureness, so you give up all the guarantees that the Haskell semantics give you.
There are lots of ways to shoot yourself in the foot as soon as you leave pure terrain. You could just as well use OS primitives to read your whole process memory in IO
, breaking referential transparency in the worst kind of way.
Apart from that,, your definition of isUndefined
does not solve the halting problem, because it's not total, which means that it doesn't terminate on all inputs.
For example, isUndefined (last [1..])
will not terminate.
There are lots of programs for which we can prove that they do or do not terminate, but that doesn't mean we have solved the halting problem.
链接地址: http://www.djcxy.com/p/7488.html上一篇: 有没有什么比unsafePerformIO更适合这个....?
下一篇: 是GHC的Haskell语义破坏的实现?