Collecting and calling a list of thunks


#1

Can someone please help me with this code? I’m trying to collect a list of thunks (0-ary functions)
and later iterate over the list and call them. The compiler gives me a very uninformative message: “Not applicable to”, but I don’t know what it is trying to tell me.
I’d like removes to be a list of objects each of type Unit=>Unit. Isn’t there a way to do this easier than to define an extra function named thunk? Also isn’t there a way to function-call all these functions simply as some clever call to map? removes.map(..some..magic..)

    def qmReduce():Unit = {
      var maxPosCount:Integer = hash.foldLeft(0){ case (acc, (k, _)) => max(k,acc) }
      def loop():Unit = {
        var changed = false
        var removes:List[Unit=>Unit] = Nil
        def addCBF(clause:Clause,posCount:Integer,length:Integer):Unit = {
          changed = true
          addClause(clause,posCount,length,false,false)
        }
        def removeCBF(clause:Clause,posCount:Integer,length:Integer):Unit = {
          def thunk():Unit = {
            removeClause(clause,posCount,length)
          }
          removes = thunk::removes // <--- compiler says "Not applicable to"
        }
        for((posCount -> _) <- hash) {
          if (posCount < maxPosCount)
            reduceOne(posCount,addCBF,removeCBF)
        }
        for(thunk <- removes)
          thunk()
        maxPosCount = hash.foldLeft(0){
          case (acc, (k, _)) => if (k<maxPosCount) max(k,acc) else acc
        }
        if (changed)
          loop()
      }
      loop()
    }

#2

Looks like there are two problems here.

First, removes is a List of functions, and thunk() is a method. They’re not the same thing, and I think you can’t just mix-and-match them in this way. I think you have to eta-expand thunk().

Second, removes is a List[Function1[Unit, Unit]] – that is, it expects functions with one parameter, of type Unit. thunk, even eta-expanded, is a Function0[Unit] – a function that takes zero parameters, and returns Unit. So the types are incompatible.

Here’s a fiddle with just those bits, that compiles successfully…


#3

Thanks jducoeur, it looks like if I change thunk::removes to thunk(_)::removes
then intelliJ is happy, but the scala compiler complains that I cannot pass an argument to a 0-ary function, and rightly so.

So what I wonder is how to do the following from lisp: (lambda () (f a b c))
which evaluates to a 0-ary function which when called will call f with three arguments,
which are the closed over values of a, b, and c.

It seems like both IntelliJ and the scala compiler are happy if I declare removes as

var removes:List[()=>Unit] = Nil

and do the push as follows

  removes = (()=>removeClause(clause,posCount,length))::removes

Then I don’t need to declare the local function, thunk


#4

Actually, not quite – when you say thunk(_)::removes, you’re not adding thunk to your List, you’re creating and adding a new function, which takes the passed-in parameters and forwards them to thunk. I confess that I’m slightly surprised that syntax works, but I suspect it’s effectively the same as the eta-expansion I showed in my link.

It’s roughly the same:

def f(a: A, b: B, c: C): Whatever = ...
val a: A = ...
val b: B = ...
val c: C = ...
def lambda(): Whatever = f(a, b, c)

While the syntax is quite different, lambdas and closures are conceptually pretty similar to LISP (and most other sensible languages).

(ETA: actually, I may be misremembering what you mean, since it’s been decades since I last seriously worked in LISP. Is lambda a generic function applicator that works for any function? That isn’t really Scala-ish, since it’s not easily represented in a strongly-typed way, although there are ways to work around it by breaking out to dynamic types…)


#6

My lisp is a bit rusty, but I’m pretty sure the equivalent is () => f(a, b, c).
And one correct way to eta expand the method thunk and add it to a list would be (thunk _) :: removes. With the premise that the types of thunk _ and removes should be compatible of course.
f _ means “transform method f with n parameters to a function with n parameters”. f(_) means “transform method f with 1 parameter to a function with 1 parameter”. More or less…


#7

@Jasper-M, are you saying that thunk _ is a function whose arity is the same as that of thunk even if thunk has 0 parameters? If so that’s indeed an interesting syntax which I would not have guessed.


#8

Yes, that’s basically what I’m saying. I think that technically thunk _ is eta expansion, and thunk(_) is partial function application (with zero of one parts applied in this case).


#9

@jimka, you might want to check out this article on eta expansion, which covers a lot of the relevant nitty-gritty.

But I think the key thing you need to keep in mind is that methods are not functions, and can’t be passed as values. You have to create an adapter layer that is a function when you want to pass it as a value. That’s generally known as eta expansion, and is what is happening in the thunk _ syntax.


#10

@jducoeur, I’ll take a look at the article. But in the mean time, it seems strange that methods and functions are treated differently. Honestly, I don’t understand the difference between methods and functions, but I believe the same syntax restriction applies to functions as well to methods. For example, if you define any ole non-anonymous function f, I doubt you can make a list of it simply with List(f).

BTW, how can I create a non-anonymous function which is not a method in order to test my claim?


#11

I assume it’s the result of Scala’s OO/Java heritage, and it makes sense from an OO point of view, even though it’s kind of weird from an FP one.

A method is specifically a named member of an object, and can’t really be treated separately from that object. Whereas a function is a value, that can be passed around freely, assigned to vals and vars, and doesn’t intrinsically have a name any more than the integer 42 does.

Actually, that last is a good lens through which to think of this. Consider this example:

object Foo {
  val i: Int = 42
  def bar(s: String): String = ...
}

val baz: String => String = Foo.bar _

Foo.i is a member of Foo – you can’t really think of it separately from the instance of Foo. By contrast, 42 is the value of Foo.i, and can be passed around freely – it has no inherent connection to Foo.

Similarly, bar() is a member of Foo, and you can’t just pass it around. But if you say bar _, it hands you a function value (that is a proxy wrapped around bar), that again is independent and anonymous, and we can freely assign it to baz.

Sure you can – click for example. Functions are simply values, and can be passed around as parameters, and abstracted over by functors such as List, the same way you can with Int, String or any other value.

Note, in that example, that I’ve defined the function with val, not def. That difference in syntax is usually the giveaway about which one you’re talking about. val means that it is holding a value, so it must be a function. def, OTOH, is always used to define a method, so it is never a first-class value in and of itself.


#12

So I think I understand, and the terminology is indeed weird from an FP perspective. If I understand, a method is not an object which the programmer has access to as an object. The compiler has access to it, but the programmer does not. The programmer has access to the name to the method, and can call the method by name. In the following case bar is not method, but rather the “name” of a method. And that name bar does not evaluate to the method, but rather evaluates as a call to the method, assuming it is used syntactically correctly.

def bar(s: String): String = {
  ...
}

This is a point which as a lisp programmer has been confusing to me. In lisp, a method is a function which wraps another function, the compiler-generated wrapper handles discrimination, and dispatch, but the programmer can access either the method or the underlying function. Moreover, the method may be used anywhere a function can be used, including in mapping functions, comprehensions, reductions, or indirect calls, etc…

In the Scala example above, bar is NOT a method, even though people often claim that, rather bar is only the name of a method. It also seems to me (maybe I’m wrong) that a method has exactly one name, never zero names, and never multiple names.

On the other hand, a function is an actual object. It may have a name, or multiple names, or no name, and can be called by name or indirectly.

A method may not be encapsulated in a function, but a call to a method can be.
The syntax for doing that is (F _), which evaluates to a function whose arity is the same as the method named by F.


#13

I think you’re close, but you’re going to have to get used to the differences in terminology. The heart of the problem is the word “method” – you’re used to it having a universal precise meaning, but that’s really not true: it is defined quite differently from language to language.

I actually think Scala’s usage of the word “method” is somewhat more common. LISP’s usage reflects the fact that LISP came to OO quite late (IIRC, I didn’t hit OO in LISP until at least the third dialect I learned), and sort of adapted the terminology to fit LISP’s somewhat idiosyncratic version of OO. In LISP, methods are just functions, whereas in most languages that evolved from the Java world, they’re a different category altogether.

Anyway, while I get where you’re thinking when you say:

you’re going to find that most people disagree with this characterization. Moreover, I believe it doesn’t really reflect reality – the fact is, methods are a fundamental concept of the JVM. Indeed, I think the reality is that methods are the underlying concept, and functions are implemented on top of methods with various shenanigans, but I’m not an expert on the subject. As I understand it, Scala goes to quite a bit of work to synthesize anonymous function objects in a world that isn’t really designed for them.

And yes, that’s exactly backwards from what you’re used to. Welcome to the JVM, which came to FP very late, and very reluctantly, with Scala and other such languages dragging it there kicking and screaming…


#14

It might help to know that the compiler is doing roughly

/*
 val f = (n: Int) => { n + 1 }
 f(3) // 4
*/

val f = new Function1[Int, Int] {
  def apply(n: Int): Int = n + 1
}

f.apply(3) // 4

Which is how a function is a value in Scala. Methods are members of a class which is how the JVM knows how to access them. In both cases Scala applies values to the function/method name so calling them looks the same. If you want to hold onto a method as a function you need to wrap the method invocation into a function so you can carry it around.

object Foo {
  def bar(n: Int): Int = n + 1
}

val f = Foo.bar  // error
val f = Foo.bar _  // success

// Last is roughly
val f = (n: Int) => Foo.bar(n)
// -desugaring to-
val f = new Function1[Int,Int] {
  def apply(n: Int): Int = Foo.bar(n)
}

#15

@jducoeur and @LannyRipple, I thought I more or less understood after reading your responses. Then I looked back again at Scala/Chiusano (the red book), and it seems to contradict what I though I understood.

On page 21 and 22 of the red book, the authors define an object MyModule with methods abs and factorial, then they later use the method names as function objects, which I wasn’t able to do in my original post. thunk::removes

Why can I use abs (likeways factorial) to mean the corresponding function object, in the call to formatResult, but not in my original code in the call to :: ?

object MyModule {
  def abs(n: Int): Int =
    if (n < 0) -n
    else n

  def factorial(n: Int): Int = {
    @annotation.tailrec
    def go(n: Int, acc: Int): Int =
      if (n <= 0) acc
      else go(n-1, n*acc)

    go(n, 1)
  }
}

and later

object FormatAbsAndFactorial {

  import MyModule._

  // Now we can use our general `formatResult` function
  // with both `abs` and `factorial`
  def main(args: Array[String]): Unit = {
    println(formatResult("absolute value", -42, abs))
    println(formatResult("factorial", 7, factorial))
  }
}

#16

Huh – yeah, that’s a really subtle one.

I believe what’s going on (and I’ll admit that I’m at the edge of my expertise here, so don’t take it as gospel) is that the compiler is smart enough to auto-convert from method to function if it’s expecting a function of the right shape in the right place. In this particular case, formatResult() is (I assume – I don’t have FPiS open) expecting a Int => Int, and it has a method of shape def xxx(x: Int): Int, so the compiler knows enough to do this conversion automatically.

So your expectation from the beginning wasn’t far off – it was just pushing the compiler a bit further than it can cope with. To illustrate, I took the code above, added a couple of variants of your original problem, and stuck it all into this fiddle. Notably, this line compiles:

  val l1: List[Int => Int] = List(m.abs, m.factorial)

but this one fails:

  val l2: List[Int => Int] = m.abs :: m.factorial :: Nil

with the error:

ScalaFiddle.scala:23: error: missing argument list for method abs in class MyModule
Unapplied methods are only converted to functions when a function type is expected.
You can make this conversion explicit by writing `abs _` or `abs(_)` instead of `abs`.
    val l2: List[Int => Int] = m.abs :: m.factorial :: Nil

So the point stands – methods are not functions. But the compiler is sometimes smart enough to auto-convert them (by building the eta expansion under the hood). You only need to do the abs _ dance when you’ve gone beyond what it can do automatically.

(IIUC Scala 3 goes further with this, to the point where you don’t ever have to to the eta-expansion manually – methods and functions are still different, but it’s rarely in your face. But Scala 2 does have some limitations…)