How does by-name arguments work in higher-order functions?

Question

I'm trying to understand what by-name type annotations mean in the context of higher-order functions. Here's an example:

object Test { 
  def apply[A, B](f: (=> A) => B, x: => A): B = f(x) 
  def const[A](ignored: A): Int = 1
  val res: Int = apply(const, ???)
}

const is strict in its argument (i.e. it lacks a => annotation), so why isn't it forcing its argument (which is ??? in this case) and raises an exception?

Is there a paper describing the semantics here?

I'm looking for an authoritative answer here.

score 5 · Accepted Answer · edited May 23 '17 at 11:52

5

The argument f in your apply function is a Funcion1 which takes a call-by-name parameter of type A and returns a B. Therefore, f(x) will not evaluate the call-by-name parameter x, but pass its reference directly to f.

It is helpful to understand res as follows:

def res[C]: Int = apply[C, Int](const, ???)

where in your example C would be an unspecific type. Now what is the type parameter inferred for const in this line? It is => C. Unfortunately you cannot type that parameter:

def res[C]: Int = apply[C, Int](const[=> C], ???)  // illegal syntax

But you can verify what is going on:

def res[C]: Int = apply[C, Int](const[Nothing], ???)

giving you

<console>:10: error: type mismatch;
 found   : Nothing => Int
 required: => C => Int
         def res[C]: Int = apply[C, Int](const[Nothing], ???)
                                              ^

This type appears inside const as a Function0[Int] (so Scala implicitly treats call-by-name or "thunk" arguments as a function with no arguments). Again you can verify this:

def const[A](ignored: A): Int = if (ignored.isInstanceOf[Function0[_]]) 1 else 0

Now Test.res will give you 1 (meaning that ignored is indeed a Function0).

So to answer the question a different way, const has an eager argument of type A, but that doesn't matter here because A becomes a function in your example, and you never apply that function, therefore ??? is never executed.

There is some debate as to why there is both a "thunk" or parentheses-less function and an empty-paren function (Function0) in Scala.

edited May 23 '17 at 11:52

Community

1
1

answered Apr 18 '13 at 23:29

0__

66,707
21
171
266

Thanks for the detailed explanation. Is the semantics of by-need (which I mistook for by-name) in Scala defined somewhere? Typically strictness properties are defined in terms of the function being applied (in this case `const`) but your explanation is very much about the implementation and how the argument to `const` is constructed. – tibbe Apr 19 '13 at 00:39
Another question, can a type parameter `A` unify with both a by-value argument (e.g. `Int`) and a by-need argument (i.e. `=> Int`)? – tibbe Apr 19 '13 at 00:41
@tibbe: I'm not familiar with the term "by-need", but it's important to distinguish Scala's by-name parameters from lazily evaluated parameters. The latter is evaluated zero or one times while the former is evaluated 0 _or more_ times. – Randall Schulz Apr 19 '13 at 01:30
["Call-by-need is a memoized version of call-by-name"](http://en.wikipedia.org/wiki/Evaluation_strategy#Call_by_need) - in other words, by-need would correspond to Scala's `lazy` value. – 0__ Apr 19 '13 at 10:38
@tibbe : A by-name argument (see my previous comment about by-need!) _does_ unify both. If you need to use the value multiple times in the function body, you will most likely use memoisation (assign the argument to a `lazy val`). See also [this question](http://stackoverflow.com/questions/4543228/whats-the-difference-between-and-unit) and [that question](http://stackoverflow.com/questions/9809313/scalas-lazy-arguments-how-do-they-work). – 0__ Apr 19 '13 at 10:41

score 0 · Answer 2 · answered Apr 19 '13 at 10:50

I'm opening another answer, because it still seems unclear to you what is happening:

Typically strictness properties are defined in terms of the function being applied (in this case const) but your explanation is very much about the implementation and how the argument to const is constructed.

I will restate your object with distinct type names:

object Test { 
  def apply[A, B](f: (=> A) => B, x: => A): B = f(x) 
  def const[C](ignored: C): Int = 1
  def res[A1]: Int = apply[A1, Int](const, ???)
}

Now, let's exchange by-name parameters with Function0, to highlight where the "laziness" is hidden:

object Test { 
  def apply[A, B](f: (() => A) => B, x: () => A): B = f(x) 
  def const[C](ignored: C): Int = 1
  def res[A1]: Int = apply[A1, Int](const[() => A1], () => ???)
}

You see, the definition of const doesn't matter. What matters is that the x argument to apply is by-name (or a function in the last version). So f(x) calls f with a function argument x, so whatever x's body is, that is not evaluated at this point.

How does by-name arguments work in higher-order functions?

2 Answers2