Hacker News Reader

Comment by choeger | Hacker News Reader

>I think it’s important to be more specific here. You can always mess up and pass the wrong thing, the type system can never know what is semantically correct

This is not true. Consider the map function of a typical functional language with parametric polymorphism:

map : (a -> b) -> [a] -> [b]

That signature is complete, it covers everything there is to know about the function. And, except for trivial implementations, there is no way to implement it wrongly.

In some cases, one can even rule out trivial implementations and infer the correct implementations from the type signature alone.

In any case, there is no "semantically wrong" input to such a function. It is just a function and totally agnostic regarding your use case.

View on HN

Of course that type doesn't encode everything there is to know about that function, even assuming purity.

Here are some functions that match that type signature:

    map1 foo x:xs = [foo x]

    mapR foo x:xs = append (mapR foo xs) foo x

    mapI foo x:xs = foo x : mapI foo x:xs

Of course, we can create many more functions that arrange the values in other creative ways, that add more or fewer values etc. If the function isn't pure, we can also imagine many more dimensions of functions that do arbitrarily different things from what you would expect.

If you want complete signatures without dependent types, you need functions which take only single values of different unknown types, like apply: (a -> b) -> a -> b. If you have more than one parameter of the same unknown type, you'll have some ambiguity already.

Non-dependent types can only be used to encode extremely simple properties of a program. They are certainly useful, but they are not in any way the be-all, end-all of static verification.

> Of course that type doesn't encode everything there is to know about that function, even assuming purity.

Right—we need to require foo id = id.

That only works because Haskell can't really express it. That is, if you could write Haskell code that checked that equality, that equality wouldn't be enough, because you could write a function `mapStrange foo [x]` that is equal to `map` if `foo = id` and is something else otherwise.

But since you can't compare 2 functions for equality, and you can't compare two arbitrary values for equality, then yes - your informal requirement is enough togethet with the type to force the function to be `map`.

Sorry for the confusion, I think we are using different definitions of "semantics" here, I'm not talking about formal semantics. I'm considering these to be semantically different, even though their structural types are the same:

    fn min(x: int, y: int) -> int
    fn max(x: int, y: int) -> int

The meaning of a computation changes depending on which one we use.

I probably should have used a different word than "semantics" since that has a technical definition in the PL field...

Reply on news.ycombinator.com