How to detect dynamic extent


#1

Is there a way in Scala to detect whether a function f is being called within the dynamic extent of function g?

I have a function f which, when called, may destroy a particular data structure, unless it is called within the dynamic extent of g. I can document this in the comment of f but I’d like to enforce it if possible.

In Common Lisp I would bind a dynamic (thread-local) variable to true inside g, and assert the value of that variable is true inside f.

I’m tempted to use DynamicVariable, and just emulate the CL idiom. But perhaps there’s a more Scala-think way?


#2

You can use an implicit whose creation is controlled by g or g's direct parent module or class.

object Module {
  @annotation.implicitNotFound("This function can only be called in the context of Module.g")
  sealed trait CanCallg
  private[this] object CanCallg extends CanCallg

  def g(someCode: CanCallg => Unit) = {
    someCode(CanCallg)
    f(CanCallg) // I can call f
  }

  def f(implicit sentinel: CanCallg) = {
    ???
  }
}

object Main extends App {
  import Module._
  g{ implicit sentinel =>
    println("start f")
    f // I can call f
    println("stop f")
  }

  f // error: This function can only be called in the context of Module.g
}

You could still circumvent this with f(null). Which you can defend against at runtime with assert(sentinel != null). Or you could try using a value class as sentinel, or possibly some other creative solution.


#3

This mechanism could still be easily circumvented:

    var saved: CanCallg = null
    g(saved = _)
    f(saved) // here I use `f` outside of `g`

One possible additional safety measure would be to save a flag inside the permit produced by g, e.g:

import java.util.concurrent.atomic.AtomicBoolean

object ForceNestedFunctions {
  object Module {
    @annotation.implicitNotFound(
      "This function can only be called in the context of Module.g")
    sealed trait CanCallG {
      def isValid: Boolean
    }

    def g(someCode: CanCallG => Unit): Unit = {
      val canCallG =
        new AtomicBoolean(true) with CanCallG {
          override def isValid: Boolean = get()
        }
      try {
        someCode(canCallG)
      } finally {
        canCallG.set(false)
      }
    }

    def f(implicit sentinel: CanCallG): Unit = {
      assert(sentinel.isValid)
    }
  }

  def main(args: Array[String]): Unit = {
    import Module._
    var saved: CanCallG = null
    g(saved = _)
    f(saved) // this causes assertion to fail
  }
}

Whether is that worth the complexity is up to the OP.


#4

A way around that loophole is restricting the visibility of CanCallg.

private[Module] sealed trait CanCallg

You can call this a bug or a feature, but now it is still possible to use CanCallg in the signature of f and g. Only it is not possible to refer to the name CanCallg outside of Module.


#5

It seems like there is a close semantic connection between implicits and dynamic variables/functions. As I understand the Clojure language supports dynamic functions, and most lisps support some sort of dynamic values. But I have to admit I haven’t yet got my head completely around Scala implicits.


#6

Hmm. I’m not sure that’s true, particularly because I think of dynamics (as you’re using it here) as being a runtime concept, and implicits as a compile-time one. What are you thinking of as the relationship?


#7

Well, my naive understanding is that at run-time, the value of the implicit is looked up by examining the run-time value of some secret stack of implicit key/value pars which get pushed and popped, and are cleaned up properly if exceptions are raised. I.e. If I call the same function from two different call-sites, the value of the implicit may be different. So I don’t see how it can be resolved at compile time. That’s pretty much what dynamic variables do, but they just use the variable name space, rather than a secret stack.


#8

Well they’re both ways for a function to get individualized information without it being an explicitly written parameter that has to be repeated every time it’s needed.
Indeed they differ in their scope though; dynamic variables have a dynamic (runtime) scope while implicits have a static (compiler-determined) sope.

An example of this is certain information about the current request in Play: in the Scala API it’s usually passed around as an implicit, but I think in the Java API it is or used to be a dynamic variable (in Lift it certainly is). They’re both ways for code in various places (e.g. inside the template or view code) to get information about the current request without having to pass a request object around explicitly all the time.


#9

Ok so actually how implicits work, is that they are a parameter just like any other, but when you call the method the compiler writes the parameter for you, choosing a value to fill in based on the expected type. So it’s purely a compile-time thing.


#10

Right. Implicits are mostly just boilerplate reduction – more or less everything you do with implicits you could do by spelling things out explicitly; it would just be wordier and more annoying. AFAIK they don’t exist at all at runtime, and don’t affect runtime functionality.

Actually, it happens precisely at compile time. The implicit parameter isn’t looking at what the runtime values are, it’s looking at the scope at compile time, and basically creating a connection from the value of type T that’s defined up here, down to the parameter that uses that type implicitly down there.

I generally describe a “cloud” of implicit values, in scope at any given place in your program. When you declare an implicit parameter of type T, the compiler looks into the in-scope cloud looking for a T; assuming it finds it, it hooks them together. (If it doesn’t find a T, or finds more than one, it’s an error.)


#11

Implicits are completely static, just like the counterparts without implicit keyword. You can consider implicits handling as a rewrite step during compilation, e.g. such code:

implicit def implicitProvider: TypeA = ???
def implicitTaker(implicit value: TypeA) = ???
implicitTaker // argument is implicitly provided by compiler

is transformed to such code:

def implicitProvider: TypeA = ???
def implicitTaker(value: TypeA) = ???
implicitTaker(implicitProvider) // here implicit argument is turned into explicit argument

Any “secret stacks” of implicits exists only inside the Scala compiler during that rewrite step.


#12

@jimka Back to your initial question, what exactly do you want to enforce?
If it’s just that f is called within g, you’d define f as a local function to g.


#13

Hi Peter, good question. I have an object named Bdd which has an apply method. This apply method uses a memoization hash table to assure that the same object (in the sense of eq) is returned whenever the given arguments are the same. If the set of arguments are new (never been seen before), then the apply method calls the constructor for the class BddNode, and memoizes its value.

A brief description of the algorithm can be found here utexas, as well as here Andersen

If anyone else calls the BddNode constructor, my hash table will be out of date. Currently my code does not enforce this, and I discovered the problem when writing unit tests on the BddNode constructor.

It might be that I could solve the problem another way with the privacy settings of the BddNode constructor, but I don’t know how to do that?


#14

I see. In case BddNode is not a case class it is sufficient to make its constructor private.


#15

Interesting. In my case BddNode is a case class, but assuming (for pedagogical reasons) that it were not. How would making the constructor private, prevent me from calling it incorrectly from within the same class?


#16

Normally you are in full control of your class so there is no need to prevent a constructor call in that class. It is only meaningful to prevent it for the clients of your class.


#17

Restricting type visibility is still easy to circumvent. Look at this:

object ForceNestedFunctions {
  // library code
  object Module {
    @annotation.implicitNotFound(
      "This function can only be called in the context of Module.g")
    private[Module] sealed trait CanCallG

    def g(someCode: CanCallG => Unit): Unit = {
      someCode(new CanCallG {})
    }

    def f(implicit sentinel: CanCallG): Unit = {
      assert(sentinel != null)
    }
  }

  // user code
  def main(args: Array[String]): Unit = {
    import Module._
    var saved: AnyRef = null
    g(saved = _)
    f(forceNarrow(saved)) // running `f` outside of `g`
  }

  def forceNarrow[T](value: AnyRef): T =
    value.asInstanceOf[T]
}

#18

Sure, but if you have to use casts that’s acceptable.


#19

Okay. If casts change anything, then there’s version without casts:

object ForceNestedFunctions {
  // library code
  object Module {
    @annotation.implicitNotFound(
      "This function can only be called in the context of Module.g")
    private[Module] sealed trait CanCallG

    def g(someCode: CanCallG => Unit): Unit = {
      someCode(new CanCallG {})
    }

    def f(implicit sentinel: CanCallG): Unit = {
      assert(sentinel != null)
    }
  }

  // user code
  def main(args: Array[String]): Unit = {
    import Module._
    val saved = extractSentinel(g)
    f(saved) // running `f` outside of `g`
  }

  def extractSentinel[T](fun: (T => Unit) => Unit): T = {
    fun(return _)
    ???
  }
}

Still not hard :slight_smile:


#20

This all feels like it may be getting off-topic. @jimka, question: are you trying to make it absolutely impossible for outside code to call this inappropriately, or just arrange it to be less easy to make a mistake?