The disclosed embodiments provide a system that facilitates the compilation and execution of a software program. During operation, the system obtains a closure from source code for the software program. Next, the system characterizes a type of the closure based on a mutability of one or more variables captured by the closure. Finally, the system encodes the type into a compiled form of the closure to facilitate subsequent execution of the closure in a multithreaded environment.