Can someone help me understand what really is the type A=>B in general and in particular in Scala? Does it have a real meaning? Or is it only an approximation that’s supposed to give us an intuition?
Is this a question which every type system (type systems of different languages) may answer in different ways?
One might think that the type is (or perhaps represents) the set of all functions which can be called with absolutely any element of type A and will always in that case return an object of type B. However, the Scala compiler certainly does not (and cannot) enforce that definition. For example, the following function returns Double on some given elements of type Int.
def f(a:Int):Double = {
if (a == 0)
sys.error("doesn't work for 0")
else if (a < 0){
def loop_forever():Double = loop_forever()
loop_forever()
}
else
a.toDouble
}
Why do I ask such an asinine question? The reason is that I’m putting together a historical perspective of certain type system features. Some of the examples come from Common Lisp whose type system was defined long before many modern concepts were understood. The CL type system does some things in a nice way while other some are just bizarre. I believe I understand the CL type system better as a result of studying Scala.
It is my understanding that A => B compiles to Function1[A, B]. You can see the API entry at https://www.scala-lang.org/api/current/scala/Function1.html. Note that it is contravariant on the input and covariant on the return type. In the case of Int and Double things are a bit different because they don’t have any subtype relationship, but there is an implicit conversion from Int to Double that can easily come into play.
Mark, are you saying that the meaning of function types in Scala simply is the set of objects whose type name is Function1, and that there is no set theoretical meaning associated with it?
Yep, that’s true. I think of it as a statement of intent – you should be able to pass in any A and get a B. In principle, that’s the difference between this and a PartialFunction, which is defined only over part of the domain of A. In practice, as you say, that’s not currently achieveable, and only the FP crowd tends to even take the idea really seriously.
I know that folks are thinking about how to express effects in Scala, and I hope that it might someday be possible to express the idea “no, really, this is a pure function dammit” with compiler enforcement. But that’s years off at best, might be a pipe dream, and I’m sure will always be subject to some exceptions at the extremes. (There’s not much you can do about an out of memory error.)
A function of type A => B just means that the function takes an argument of type A and, IF IT RETURNS NORMALLY, returns a value of type B. That seems fairly straightforward to me. What else could it mean? If the function doesn’t return normally, how could it be expected to return a value of type B? The notion of requiring the function to return normally is another matter that is separate from the type of the function. But is this exception any different than
And the compiler would need to somehow detect cases where the code is grammatically and semantically correct, but still contains bugs (say, index out of bounds). Perhaps one day we’ll have an AI so intelligent that it would be able to understand the meaning of the code, but then who’d need human programmers?
No AI will ever do that. Doing so requires solving the halting problem. Since there is a ice mathematical proof saying it can’t be done, I’m pretty sure that we won’t be seeing that added to any language. Granted, we can make tools that get arbitrarily close. The real question for me is, can we get close enough that it works for all practical programs? We can’t algorithmically prove all programs correct, but can we algorithmically prove useful programs correct? If not all of them, what fraction might be tractable?
Going back to original question:
In JVM the basic building blocks are interfaces, classes, static methods, non-static methods, etc Functions aren’t primitives, instead they are represented using classes with a method that acts as the function body. FunctionXXX traits have apply method that when implemented act as a function body. Scala offers a syntactic sugar so anything.apply(params) can be shortened to anything(params) so function(params) looks like a low level stuff, while in fact it’s an invocation of method apply on an instance of some (usually anonymous) class.
Scala compiler doesn’t give any guarantees about function totality. All Scala compiles sees is that throw something evaluates to type Nothing which is a subtype of every other type, so you can “return” Nothing from anywhere. I would say that without first forcing explicitly nullable types guaranteeing function totality is probably impossible - NullPointerExceptions could be thrown from basically anywhere. But tracking nulls is only a first step - you need to track all possible exceptions. Also: what about infinite loops? Do they affect function totality?
What else could it mean? Well it would seem to mean more than simply that because the scala compiler thinks this function has type Int=>Double, but that’s not covered by Russ’ proposed intepretation.
Also there are the questions of the types Nothing=>Nothing, Nothing=>Any, and Any=>Nothing. Neither of these is a subtype of Nothing, so they are not empty types.
The scala compiler compiles the following just fine.
Nothing is a subtype of all types, also called the bottom type. There is no value that has type Nothing .
Scala Function1 has signature:
traitFunction1[-T1, +R] extends AnyRef
So it’s contravariant in parameter types and covariant in return type. Nothing is a subtype of Any so you can then derive the subtyping relationships you’re interested in.
Another thing is that if Child is subtype of Parent then you can do the following:
def make: Parent = new Child
I.e. this returns a subtype of the type in signature and everything compiles fine. You can return a subtype of required type. Since Nothing is a subtype of every other type, returning Nothing is always legal.
This little “function” does not return anything “normally,” so I don’t see how it contradicts what I wrote. Let me try putting it another way:
A function of type A => B means that the function takes an argument of type A and CANNOT return any value that is NOT of type B. Does the clever double negative cover all bases? And is it true? Not being a language lawyer, I honestly don’t know. If the function does its intended job, it returns a value of type B, but that’s just a hope and a prayer.
Do these functions contradict what I wrote? I am curious (but not quite enough to figure it out for myself).
The idea in functional programming is that we use functions that are total, deterministic and pure. Such functions are side-effect free. Exceptions are a side effect.
Exceptions are a side effect. In FP instead of using side effects we use functional effects. The most common example of treating exceptions as functional effects in Scala is the Try abstraction.
This is somewhat similar to what Common Lisp defined in the mid 80s. A function A=>B is a function that if you pass something other than an object of type A it cannot be guaranteed that the result will be of type B. That definition later turned out to be problematic.
Yes I think it is still problematic. Because the following function takes an object of type Int and cannot return any object other than String. But it is not of type Int=>String.
I took at look at the slides. And I didn’t actually see the relevance to my question. Did I miss the explanation of what a function type really is semantically?
Semantically a function is just a syntax sugar for anonymous class, but with the difference that this refers to different object within a lambda syntax and within anonymous subclass of scala.FunctionXXX. Also return is affected - within a lambda syntax it does throw exception, outside a lambda it is just a regular early return from metod.
