Repository: tweag/nickel
Pull request #916 (2022-11-14 09:09:32)

Refactor/eval cache
This refactor adds a `Cache` trait that abstracts away (not yet 100%) from `Thunk`s.
This change will facilitate the adoption of a new incremental caching mechanism and further experiments on evaluation/caching strategies other than CBN.

`Thunk`s are still leaking from the abstraction, but I think that's the best we can afford given the current state of `CacheIndex`

dpl0a: Thanks a lot for all the feedback. It'd be great to pair next week 😄 
yannham: > Overall, my major concern here is the number of functions we now need to pass a Cache into. It feels like an architectural smell to me & I suspect there are ways of structuring the interpreter (like, e.g., allowing various parts to hold Rcs to a central Cache) that would clean this up a lot. If you're interested in looking into this further, I'd be happy to do some pairing next week.

The issue is that you need mutable access to the cache in many parts. So you end up with `Rc<RefCell<Cache>>`, which is already less sexy, as we're trading static safety for runtime safety.

Another possibility would be to have one global cache stored statically, and that multiple VM instances wouldn't "collide" and could each use this cache independently (I guess that would be handled by `CacheIndex`). We probably still need a refcell, a mutex, or something akin to ensure that there isn't concurrent mutable access to the cache. 

This is not absurd that only one global cache is allocated for each run of the `nickel` binary (or the LSP, or the tests, etc.). May also get rid of a lot of cache parameter passing around.
matthew-healy: Yeah, the loss of static safety here is a reasonable concern. I wonder if we could alleviate some of that with something like a `CacheReference` newtype which keeps the specific details private & provides a more specialised API that directly using the `RefCell` would... :thinking: 

I'd need to think more about the implications of a single static cache instance. The idea of synchronising access to a mutable data store for multiple VMs fills me with significantly more dread than relying on runtime safety guarantees, but perhaps I'm misunderstanding. :grinning: 

Patch:
diff --git a/src/bin/nickel.rs b/src/bin/nickel.rs
index 5ce4c1c3..b2c3c7c5 100644
--- a/src/bin/nickel.rs
+++ b/src/bin/nickel.rs
@@ -1,5 +1,6 @@
 //! Entry point of the program.
 use nickel_lang::error::{Error, IOError};
+use nickel_lang::eval::cache::CBNCache;
 use nickel_lang::program::Program;
 use nickel_lang::repl::query_print;
 #[cfg(feature = "repl")]
@@ -15,6 +16,8 @@ use std::{
 use directories::BaseDirs;
 use structopt::StructOpt;
 
+type EC = CBNCache;
+
 /// Command-line options and subcommands.
 #[derive(StructOpt, Debug)]
 /// The interpreter of the Nickel language.
@@ -211,7 +214,7 @@ fn main() {
 }
 
 fn export(
-    program: &mut Program,
+    program: &mut Program<EC>,
     format: Option<ExportFormat>,
     output: Option<PathBuf>,
 ) -> Result<(), Error> {
diff --git a/src/cache.rs b/src/cache.rs
index 05dc0ec0..5c6bb49e 100644
--- a/src/cache.rs
+++ b/src/cache.rs
@@ -1,6 +1,7 @@
 //! Source cache.
 
 use crate::error::{Error, ImportError, ParseError, ParseErrors, TypecheckError};
+use crate::eval::cache::Cache as EvalCache;
 use crate::parser::lexer::Lexer;
 use crate::position::TermPos;
 use crate::stdlib::{self as nickel_stdlib, StdlibModule};
@@ -908,7 +909,7 @@ impl Cache {
     /// for performance reasons: this is done in the test suite. Return an initial environment
     /// containing both the evaluation and type environments. If you only need the type environment, use
     /// `load_stdlib` then `mk_type_env` to avoid transformations and evaluation preparation.
-    pub fn prepare_stdlib(&mut self) -> Result<Envs, Error> {
+    pub fn prepare_stdlib<EC: EvalCache>(&mut self, eval_cache: &mut EC) -> Result<Envs, Error> {
         #[cfg(debug_assertions)]
         if self.skip_stdlib {
             return Ok(Envs::new());
@@ -926,7 +927,7 @@ impl Cache {
                 cache_err
                     .unwrap_error("cache::prepare_stdlib(): expected standard library to be parsed")
             })?;
-        let eval_env = self.mk_eval_env().unwrap();
+        let eval_env = self.mk_eval_env(eval_cache).unwrap();
         Ok(Envs {
             eval_env,
             type_ctxt,
@@ -954,11 +955,15 @@ impl Cache {
 
     /// Generate the initial evaluation environment from the list of `file_ids` corresponding to the standard
     /// library parts.
-    pub fn mk_eval_env(&self) -> Result<eval::Environment, CacheError<Void>> {
+    pub fn mk_eval_env<EC: EvalCache>(
+        &self,
+        eval_cache: &mut EC,
+    ) -> Result<eval::Environment, CacheError<Void>> {
         if let Some(ids) = self.stdlib_ids.as_ref().cloned() {
             let mut eval_env = eval::Environment::new();
             ids.iter().for_each(|(_, file_id)| {
                 let result = eval::env_add_term(
+                    eval_cache,
                     &mut eval_env,
                     self.get_owned(*file_id).expect(
                         "cache::mk_eval_env(): can't build environment, stdlib not parsed",
diff --git a/src/deserialize.rs b/src/deserialize.rs
index 88051126..ec6c443d 100644
--- a/src/deserialize.rs
+++ b/src/deserialize.rs
@@ -594,10 +594,12 @@ impl serde::de::Error for RustDeserializationError {
 mod tests {
     use std::io::Cursor;
 
+    use nickel_lang_utilities::TestProgram;
     use serde::Deserialize;
 
+    use crate::{eval::cache::CBNCache, program::Program};
+
     use super::RustDeserializationError;
-    use crate::program::Program;
 
     #[test]
     fn rust_deserialize_struct_with_fields() {
@@ -629,7 +631,7 @@ mod tests {
 
         assert_eq!(
             A::deserialize(
-                Program::new_from_source(
+                TestProgram::new_from_source(
                     Cursor::new(
                         br#"{ a = 10, b = "test string", c = null, d = true, e = `foo, f = null, g = -10, h = { bar = "some other string" } }"#.to_vec()
                     ),
@@ -657,7 +659,7 @@ mod tests {
     fn rust_deserialize_array_of_numbers() {
         assert_eq!(
             Vec::<f64>::deserialize(
-                Program::new_from_source(Cursor::new(br#"[1, 2, 3, 4]"#.to_vec()), "source")
+                TestProgram::new_from_source(Cursor::new(br#"[1, 2, 3, 4]"#.to_vec()), "source")
                     .expect("program should't fail")
                     .eval_full()
                     .expect("evaluation should't fail")
@@ -672,13 +674,16 @@ mod tests {
         #[derive(Debug, PartialEq, Deserialize)]
         struct A;
 
+        let mut p = Program::<CBNCache>::new_from_source(
+            Cursor::new(br#"fun a b => a + b"#.to_vec()),
+            "source",
+        )
+        .expect("program should't fail");
+
+        let q = p.eval_full().expect("evaluation should't fail");
+
         assert_eq!(
-            A::deserialize(
-                Program::new_from_source(Cursor::new(br#"fun a b => a + b"#.to_vec()), "source")
-                    .expect("program should't fail")
-                    .eval_full()
-                    .expect("evaluation should't fail")
-            ),
+            A::deserialize(q),
             Err(RustDeserializationError::InvalidType {
                 expected: "Null".to_string(),
                 occurred: "Fun".to_string()
@@ -695,10 +700,13 @@ mod tests {
 
         assert_eq!(
             A::deserialize(
-                Program::new_from_source(Cursor::new(br#"{ a = (10 | Num) }"#.to_vec()), "source")
-                    .expect("program should't fail")
-                    .eval_full()
-                    .expect("evaluation should't fail")
+                TestProgram::new_from_source(
+                    Cursor::new(br#"{ a = (10 | Num) }"#.to_vec()),
+                    "source"
+                )
+                .expect("program should't fail")
+                .eval_full()
+                .expect("evaluation should't fail")
             )
             .expect("deserialization should't fail"),
             A { a: 10.0 }
diff --git a/src/error.rs b/src/error.rs
index c733100b..73cbea64 100644
--- a/src/error.rs
+++ b/src/error.rs
@@ -1084,7 +1084,7 @@ mod blame_error {
         // If we have a reference to the thunk that was being tested, we can try to show
         // more information about the final, evaluated value that is responsible for the
         // blame.
-        if let Some(ref thunk) = blame_label.arg_thunk {
+        if let Some(ref thunk) = blame_label.arg_idx {
             let mut val = thunk.get_owned().body;
 
             match (val.pos, blame_label.arg_pos.as_opt_ref(), contract_id) {
diff --git a/src/eval/cache.rs b/src/eval/cache.rs
new file mode 100644
index 00000000..b7c2cf1b
--- /dev/null
+++ b/src/eval/cache.rs
@@ -0,0 +1,97 @@
+use std::fmt::Debug;
+
+use super::{
+    lazy::{BlackholedError, Thunk, ThunkState, ThunkUpdateFrame},
+    IdentKind,
+};
+use crate::{eval::Closure, identifier::Ident, term::BindingType};
+
+pub trait Cache: Clone {
+    type UpdateIndex; // Temporary: we won't really need that once an alternative caching mechanism gets implemented
+
+    fn get(&self, idx: CacheIndex) -> Closure;
+    fn get_update_index(
+        &mut self,
+        idx: &mut CacheIndex,
+    ) -> Result<Option<Self::UpdateIndex>, BlackholedError>;
+    fn add(&mut self, clos: Closure, kind: IdentKind, bty: BindingType) -> CacheIndex;
+    fn patch<F: FnOnce(&mut Closure)>(&mut self, idx: CacheIndex, f: F);
+    fn get_then<T, F: FnOnce(&Closure) -> T>(&self, idx: CacheIndex, f: F) -> T;
+    fn update(&mut self, clos: Closure, idx: Self::UpdateIndex);
+    fn new() -> Self;
+    fn reset_index_state(&self, idx: &mut Self::UpdateIndex);
+    fn map_at_index<F: FnMut(&Closure) -> Closure>(&mut self, idx: &CacheIndex, f: F)
+        -> CacheIndex;
+    // TODO: Needs a better name
+    fn build_cached(&mut self, idx: &mut CacheIndex, rec_env: &[(Ident, CacheIndex)]);
+}
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub struct CBNCache {}
+
+pub type CacheIndex = Thunk;
+
+impl Cache for CBNCache {
+    type UpdateIndex = ThunkUpdateFrame;
+
+    fn get(&self, idx: CacheIndex) -> Closure {
+        idx.get_owned()
+    }
+
+    fn get_update_index(
+        &mut self,
+        idx: &mut CacheIndex,
+    ) -> Result<Option<Self::UpdateIndex>, BlackholedError> {
+        if idx.state() != ThunkState::Evaluated {
+            if idx.should_update() {
+                idx.mk_update_frame().map(Some)
+            }
+            // If the thunk isn't to be updated, directly set the evaluated flag.
+            else {
+                idx.set_evaluated();
+                Ok(None)
+            }
+        } else {
+            Ok(None)
+        }
+    }
+
+    fn add(&mut self, clos: Closure, kind: IdentKind, bty: BindingType) -> CacheIndex {
+        match bty {
+            BindingType::Normal => Thunk::new(clos, kind),
+            BindingType::Revertible(deps) => Thunk::new_rev(clos, kind, deps),
+        }
+    }
+
+    fn patch<F: FnOnce(&mut Closure)>(&mut self, mut idx: CacheIndex, f: F) {
+        f(&mut idx.borrow_mut());
+    }
+
+    fn get_then<T, F: FnOnce(&Closure) -> T>(&self, idx: CacheIndex, f: F) -> T {
+        f(&idx.borrow())
+    }
+
+    fn update(&mut self, clos: Closure, uidx: Self::UpdateIndex) {
+        uidx.update(clos);
+    }
+
+    fn new() -> Self {
+        CBNCache {}
+    }
+
+    fn reset_index_state(&self, idx: &mut Self::UpdateIndex) {
+        idx.reset_state();
+    }
+
+    fn map_at_index<F: FnMut(&Closure) -> Closure>(
+        &mut self,
+        idx: &CacheIndex,
+        f: F,
+    ) -> CacheIndex {
+        idx.map(f)
+    }
+
+    fn build_cached(&mut self, idx: &mut CacheIndex, rec_env: &[(Ident, CacheIndex)]) {
+        idx.build_cached(rec_env)
+    }
+}
diff --git a/src/eval/fixpoint.rs b/src/eval/fixpoint.rs
index 86760eca..b53b4749 100644
--- a/src/eval/fixpoint.rs
+++ b/src/eval/fixpoint.rs
@@ -5,18 +5,19 @@ use super::*;
 /// the corresponding thunk from the environment in the general case, or create a closure on the
 /// fly if the field is a constant. The resulting environment is to be passed to the
 /// [`patch_field`] function.
-pub fn rec_env<'a, I: Iterator<Item = (&'a Ident, &'a RichTerm)>>(
+pub fn rec_env<'a, I: Iterator<Item = (&'a Ident, &'a RichTerm)>, C: Cache>(
+    cache: &mut C,
     bindings: I,
     env: &Environment,
-) -> Result<Vec<(Ident, Thunk)>, EvalError> {
+) -> Result<Vec<(Ident, CacheIndex)>, EvalError> {
     bindings
         .map(|(id, rt)| match rt.as_ref() {
             Term::Var(ref var_id) => {
-                let thunk = env
+                let idx = env
                     .get(var_id)
                     .cloned()
                     .ok_or(EvalError::UnboundIdentifier(*var_id, rt.pos))?;
-                Ok((*id, thunk))
+                Ok((*id, idx))
             }
             _ => {
                 // If we are in this branch, `rt` must be a constant after the share normal form
@@ -26,7 +27,7 @@ pub fn rec_env<'a, I: Iterator<Item = (&'a Ident, &'a RichTerm)>>(
                     body: rt.clone(),
                     env: Environment::new(),
                 };
-                Ok((*id, Thunk::new(closure, IdentKind::Let)))
+                Ok((*id, cache.add(closure, IdentKind::Let, BindingType::Normal)))
             }
         })
         .collect()
@@ -37,21 +38,23 @@ pub fn rec_env<'a, I: Iterator<Item = (&'a Ident, &'a RichTerm)>>(
 /// step correspond to function application (see documentation of [crate::eval::lazy::ThunkData]).
 ///
 /// For each field, retrieve the set set of dependencies from the corresponding thunk in the
-/// environment, and only add those dependencies to the environment. This avoid retaining
+/// environment, and only add those dependencies to the environment. This avoids retaining
 /// reference-counted pointers to unused data. If no dependencies are available, conservatively add
 /// all the recursive environment. See [`crate::transform::free_vars`].
-pub fn patch_field(
+pub fn patch_field<C: Cache>(
+    cache: &mut C,
     rt: &RichTerm,
-    rec_env: &[(Ident, Thunk)],
+    rec_env: &[(Ident, CacheIndex)],
     env: &Environment,
 ) -> Result<(), EvalError> {
     if let Term::Var(var_id) = &*rt.term {
-        let mut thunk = env
+        // TODO: Shouldn't be mutable, [`CBNCache`] abstraction is leaking.
+        let mut idx = env
             .get(var_id)
             .cloned()
             .ok_or(EvalError::UnboundIdentifier(*var_id, rt.pos))?;
 
-        thunk.build_cached(rec_env);
+        cache.build_cached(&mut idx, rec_env);
     }
 
     // Thanks to the share normal form transformation, the content is either a constant or a
diff --git a/src/eval/lazy.rs b/src/eval/lazy.rs
index bf614c4f..a65053a1 100644
--- a/src/eval/lazy.rs
+++ b/src/eval/lazy.rs
@@ -1,5 +1,5 @@
 //! Thunks and associated devices used to implement lazy evaluation.
-use super::{Closure, Environment, IdentKind};
+use super::{cache::CacheIndex, Closure, Environment, IdentKind};
 use crate::{
     identifier::Ident,
     term::{FieldDeps, RichTerm, Term},
@@ -32,6 +32,8 @@ pub struct ThunkData {
     state: ThunkState,
 }
 
+type CBNClosure = Closure;
+
 /// The part of [ThunkData] responsible for storing the closure itself. It can either be:
 /// - A standard thunk, that is destructively updated once and for all
 /// - A revertible thunk, that can be restored to its original expression. Used to implement
@@ -104,7 +106,7 @@ pub struct ThunkData {
 /// variables of `orig`.
 #[derive(Clone, Debug, PartialEq)]
 pub enum InnerThunkData {
-    Standard(Closure),
+    Standard(CBNClosure),
     Revertible {
         orig: Rc<Closure>,
         cached: Option<Closure>,
@@ -117,7 +119,7 @@ const REVTHUNK_NO_CACHED_VALUE_MSG: &str =
 
 impl ThunkData {
     /// Create new standard thunk data.
-    pub fn new(closure: Closure) -> Self {
+    pub fn new(closure: CBNClosure) -> Self {
         ThunkData {
             inner: InnerThunkData::Standard(closure),
             state: ThunkState::Suspended,
@@ -224,7 +226,7 @@ impl ThunkData {
     }
 
     /// Return a reference to the closure currently cached.
-    pub fn closure(&self) -> &Closure {
+    pub fn closure(&self) -> &CBNClosure {
         match self.inner {
             InnerThunkData::Standard(ref closure) => closure,
             // Nothing should peek into a revertible thunk before the cached value has been
@@ -243,7 +245,7 @@ impl ThunkData {
     }
 
     /// Return a mutable reference to the closure currently cached.
-    pub fn closure_mut(&mut self) -> &mut Closure {
+    pub fn closure_mut(&mut self) -> &mut CBNClosure {
         match self.inner {
             InnerThunkData::Standard(ref mut closure) => closure,
             InnerThunkData::Revertible {
@@ -255,7 +257,7 @@ impl ThunkData {
     }
 
     /// Consume the data and return the cached closure.
-    pub fn into_closure(self) -> Closure {
+    pub fn into_closure(self) -> CBNClosure {
         match self.inner {
             InnerThunkData::Standard(closure) => closure,
             // Nothing should access the cached value of a revertible thunk before the cached
@@ -274,7 +276,7 @@ impl ThunkData {
     }
 
     /// Update the cached closure.
-    pub fn update(&mut self, new: Closure) {
+    pub fn update(&mut self, new: CBNClosure) {
         match self.inner {
             InnerThunkData::Standard(ref mut closure) => *closure = new,
             InnerThunkData::Revertible { ref mut cached, .. } => *cached = Some(new),
@@ -312,7 +314,7 @@ impl ThunkData {
     /// the cached expression.
     pub fn map<F>(&self, mut f: F) -> Self
     where
-        F: FnMut(&Closure) -> Closure,
+        F: FnMut(&CBNClosure) -> CBNClosure,
     {
         match self.inner {
             InnerThunkData::Standard(ref c) => ThunkData {
@@ -367,7 +369,7 @@ pub struct BlackholedError;
 
 impl Thunk {
     /// Create a new standard thunk.
-    pub fn new(closure: Closure, ident_kind: IdentKind) -> Self {
+    pub fn new(closure: CBNClosure, ident_kind: IdentKind) -> Self {
         Thunk {
             data: Rc::new(RefCell::new(ThunkData::new(closure))),
             ident_kind,
@@ -411,17 +413,17 @@ impl Thunk {
     }
 
     /// Immutably borrow the inner closure. Panic if there is another active mutable borrow.
-    pub fn borrow(&self) -> Ref<'_, Closure> {
+    pub fn borrow(&self) -> Ref<'_, CBNClosure> {
         Ref::map(self.data.borrow(), |data| data.closure())
     }
 
     /// Mutably borrow the inner closure. Panic if there is any other active borrow.
-    pub fn borrow_mut(&mut self) -> RefMut<'_, Closure> {
+    pub fn borrow_mut(&mut self) -> RefMut<'_, CBNClosure> {
         RefMut::map(self.data.borrow_mut(), |data| data.closure_mut())
     }
 
     /// Get an owned clone of the inner closure.
-    pub fn get_owned(&self) -> Closure {
+    pub fn get_owned(&self) -> CBNClosure {
         self.data.borrow().closure().clone()
     }
 
@@ -431,7 +433,7 @@ impl Thunk {
 
     /// Consume the thunk and return an owned closure. Avoid cloning if this thunk is the only
     /// reference to the inner closure.
-    pub fn into_closure(self) -> Closure {
+    pub fn into_closure(self) -> CBNClosure {
         match Rc::try_unwrap(self.data) {
             Ok(inner) => inner.into_inner().into_closure(),
             Err(rc) => rc.borrow().closure().clone(),
@@ -448,7 +450,7 @@ impl Thunk {
         }
     }
 
-    pub fn build_cached(&mut self, rec_env: &[(Ident, Thunk)]) {
+    pub fn build_cached(&mut self, rec_env: &[(Ident, CacheIndex)]) {
         self.data.borrow_mut().init_cached(rec_env)
     }
 
@@ -541,7 +543,7 @@ impl Thunk {
     /// cached expression.
     pub fn map<F>(&self, f: F) -> Self
     where
-        F: FnMut(&Closure) -> Closure,
+        F: FnMut(&CBNClosure) -> CBNClosure,
     {
         Thunk {
             data: Rc::new(RefCell::new(self.data.borrow().map(f))),
@@ -583,7 +585,7 @@ impl ThunkUpdateFrame {
     ///
     /// - `true` if the thunk was successfully updated
     /// - `false` if the corresponding closure has been dropped since
-    pub fn update(self, closure: Closure) -> bool {
+    pub fn update(self, closure: CBNClosure) -> bool {
         if let Some(data) = Weak::upgrade(&self.data) {
             data.borrow_mut().update(closure);
             true
@@ -594,7 +596,7 @@ impl ThunkUpdateFrame {
 
     /// Reset the state of the thunk to Suspended
     /// Mainly used to reset the state of the vm between REPL runs
-    pub fn reset_state(self) {
+    pub fn reset_state(&mut self) {
         if let Some(data) = Weak::upgrade(&self.data) {
             data.borrow_mut().state = ThunkState::Suspended;
         }
diff --git a/src/eval/merge.rs b/src/eval/merge.rs
index be331cd1..58b7f94b 100644
--- a/src/eval/merge.rs
+++ b/src/eval/merge.rs
@@ -86,7 +86,9 @@ impl Default for MergeMode {
 ///
 /// In [`MergeMode::Contract`] mode, `t1` must be the value and `t2` must be the contract. It is
 /// important as `merge` is not commutative in this mode.
-pub fn merge(
+#[allow(clippy::too_many_arguments)] // TODO: Is it worth to pack the inputs in an ad-hoc struct?
+pub fn merge<C: Cache>(
+    cache: &mut C,
     t1: RichTerm,
     env1: Environment,
     t2: RichTerm,
@@ -271,6 +273,7 @@ pub fn merge(
                         && (priority1 >= priority2 || value2.is_none()) =>
                 {
                     let (v, e) = cross_apply_contracts(
+                        cache,
                         v1,
                         &env1,
                         types2.iter().chain(contracts2.iter()),
@@ -288,6 +291,7 @@ pub fn merge(
                         && (priority2 >= priority1 || value1.is_none()) =>
                 {
                     let (v, e) = cross_apply_contracts(
+                        cache,
                         v2,
                         &env2,
                         types1.iter().chain(contracts1.iter()),
@@ -304,7 +308,7 @@ pub fn merge(
                 (Some(t1), Some(t2)) if priority1 == priority2 => {
                     let mut env = Environment::new();
                     (
-                        Some(merge_closurize(&mut env, t1, val_env1, t2, val_env2)),
+                        Some(merge_closurize(cache, &mut env, t1, val_env1, t2, val_env2)),
                         priority1,
                         env,
                     )
@@ -320,7 +324,7 @@ pub fn merge(
             // Finally, we also need to closurize the contracts in the final envirnment.
             let mut contracts1: Vec<Contract> = contracts1
                 .into_iter()
-                .map(|ctr| ctr.closurize(&mut env, env1.clone()))
+                .map(|ctr| ctr.closurize(cache, &mut env, env1.clone()))
                 .collect();
             // Clippy is wrong to complain about the useless `collect` here:
             // It is necessary to release the mutable borrow on `env`
@@ -328,10 +332,10 @@ pub fn merge(
             #[allow(clippy::needless_collect)]
             let contracts2: Vec<Contract> = contracts2
                 .into_iter()
-                .map(|ctr| ctr.closurize(&mut env, env2.clone()))
+                .map(|ctr| ctr.closurize(cache, &mut env, env2.clone()))
                 .collect();
-            let types1 = types1.map(|ctr| ctr.closurize(&mut env, env1));
-            let types2 = types2.map(|ctr| ctr.closurize(&mut env, env2));
+            let types1 = types1.map(|ctr| ctr.closurize(cache, &mut env, env1));
+            let types2 = types2.map(|ctr| ctr.closurize(cache, &mut env, env2));
 
             // If both have type annotations, we arbitrarily choose the first one. At this point we
             // are evaluating the term, and types annotations and contracts make no difference
@@ -483,7 +487,8 @@ pub fn merge(
 ///
 /// - the term is given by `t1` in its environment `env1`
 /// - the contracts are given as an iterator `it2` together with their environment `env2`
-fn cross_apply_contracts<'a>(
+fn cross_apply_contracts<'a, C: Cache>(
+    cache: &mut C,
     t1: RichTerm,
     env1: &Environment,
     mut it2: impl Iterator<Item = &'a Contract>,
@@ -495,7 +500,10 @@ fn cross_apply_contracts<'a>(
     let pos = t1.pos.into_inherited();
     let result = it2
         .try_fold(t1, |acc, ctr| {
-            let ty_closure = ctr.types.clone().closurize(&mut env1_local, env2.clone());
+            let ty_closure = ctr
+                .types
+                .clone()
+                .closurize(cache, &mut env1_local, env2.clone());
             mk_term::assume(ty_closure, ctr.label.clone(), acc)
                 .map_err(|crate::types::UnboundTypeVariableError(id)| {
                     let pos = id.pos;
@@ -503,7 +511,7 @@ fn cross_apply_contracts<'a>(
                 })
                 .map(|rt| rt.with_pos(pos))
         })?
-        .closurize(&mut env, env1_local);
+        .closurize(cache, &mut env, env1_local);
 
     Ok((result, env))
 }
@@ -596,7 +604,8 @@ fn fields_merge_closurize<'a, I: DoubleEndedIterator<Item = &'a Ident> + Clone>(
 /// is the closurized merge of the two. A simplified version of [fields_merge_closurize], when we
 /// are not merging recursive record fields and thus don't have to deal with revertible thunks and
 /// saturation.
-fn merge_closurize(
+fn merge_closurize<C: Cache>(
+    cache: &mut C,
     env: &mut Environment,
     t1: RichTerm,
     env1: Environment,
@@ -606,10 +615,10 @@ fn merge_closurize(
     let mut local_env = Environment::new();
     let body = RichTerm::from(Term::Op2(
         BinaryOp::Merge(),
-        t1.closurize(&mut local_env, env1),
-        t2.closurize(&mut local_env, env2),
+        t1.closurize(cache, &mut local_env, env1),
+        t2.closurize(cache, &mut local_env, env2),
     ));
-    body.closurize(env, local_env)
+    body.closurize(cache, env, local_env)
 }
 
 /// Revert the thunk inside the provided field (if any), and closurize the result inside `env`.
diff --git a/src/eval/mod.rs b/src/eval/mod.rs
index 5b5ce842..8dfaecbd 100644
--- a/src/eval/mod.rs
+++ b/src/eval/mod.rs
@@ -90,9 +90,9 @@
 //! something to consider at some point.
 
 use crate::{
-    cache::ImportResolver,
+    cache::{Cache as ImportCache, Envs, ImportResolver},
     environment::Environment as GenericEnvironment,
-    error::EvalError,
+    error::{Error, EvalError},
     identifier::Ident,
     match_sharedterm,
     term::{
@@ -102,6 +102,7 @@ use crate::{
     transform::Closurizable,
 };
 
+pub mod cache;
 pub mod callstack;
 pub mod fixpoint;
 pub mod lazy;
@@ -110,10 +111,13 @@ pub mod operation;
 pub mod stack;
 
 use callstack::*;
+use codespan::FileId;
 use lazy::*;
 use operation::OperationCont;
 use stack::Stack;
 
+use self::cache::{Cache, CacheIndex};
+
 impl AsRef<Vec<StackElem>> for CallStack {
     fn as_ref(&self) -> &Vec<StackElem> {
         &self.0
@@ -133,24 +137,37 @@ impl Default for EvalMode {
 }
 
 // The current state of the Nickel virtual machine.
-pub struct VirtualMachine<R: ImportResolver> {
+pub struct VirtualMachine<R: ImportResolver, C: Cache> {
     // Behavior of evaluation with respect to metavalues.
     eval_mode: EvalMode,
     // The main stack, storing arguments, thunks and pending computations.
-    stack: Stack,
+    stack: Stack<C>,
     // The call stack, for error reporting.
     call_stack: CallStack,
     // The interface used to fetch imports.
     import_resolver: R,
+    // The evaluation cache.
+    pub cache: C,
 }
 
-impl<R: ImportResolver> VirtualMachine<R> {
+impl<R: ImportResolver, C: Cache> VirtualMachine<R, C> {
     pub fn new(import_resolver: R) -> Self {
         VirtualMachine {
             import_resolver,
             eval_mode: Default::default(),
             call_stack: Default::default(),
-            stack: Default::default(),
+            stack: Stack::new(),
+            cache: Cache::new(),
+        }
+    }
+
+    pub fn new_with_cache(import_resolver: R, cache: C) -> Self {
+        VirtualMachine {
+            import_resolver,
+            eval_mode: Default::default(),
+            call_stack: Default::default(),
+            stack: Stack::new(),
+            cache,
         }
     }
 
@@ -158,7 +175,8 @@ impl<R: ImportResolver> VirtualMachine<R> {
     pub fn reset(&mut self) {
         self.eval_mode = Default::default();
         self.call_stack.0.clear();
-        self.stack.reset();
+        self.stack.reset(&mut self.cache);
+        self.cache = Cache::new();
     }
 
     fn set_mode(&mut self, new_mode: EvalMode) {
@@ -191,7 +209,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
         initial_env: &Environment,
     ) -> Result<RichTerm, EvalError> {
         self.eval_deep_closure(t0, initial_env)
-            .map(|(term, env)| subst(term, initial_env, &env))
+            .map(|(term, env)| subst(&self.cache, term, initial_env, &env))
     }
 
     /// Fully evaluates a Nickel term like `eval_full`, but does not substitute all variables.
@@ -230,7 +248,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
             if let Some(t) = meta.value.take() {
                 self.reset();
                 let (evaluated, env) = self.eval_closure(Closure { body: t, env }, initial_env)?;
-                let substituted = subst(evaluated, initial_env, &env);
+                let substituted = subst(&self.cache, evaluated, initial_env, &env);
 
                 meta.value = Some(substituted);
             }
@@ -290,7 +308,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
                     // We do this because  we are on a `Sealed` term, and this is in WHNF, and if we don't,
                     // we will be unwrapping a `Sealed` term and assigning the "unsealed" value to the result
                     // of the `Seq` operation. See also: https://github.com/tweag/nickel/issues/123
-                    update_thunks(&mut self.stack, &closure);
+                    update_at_indices(&mut self.cache, &mut self.stack, &closure);
                     match stack_item {
                         Some(OperationCont::Op2Second(BinaryOp::Unseal(), _, _, _)) => {
                             self.continuate_operation(closure)?
@@ -312,32 +330,23 @@ impl<R: ImportResolver> VirtualMachine<R> {
                     }
                 }
                 Term::Var(x) => {
-                    let mut thunk = env
+                    let mut idx = env
                         .get(x)
                         .or_else(|| initial_env.get(x))
                         .cloned()
                         .ok_or(EvalError::UnboundIdentifier(*x, pos))?;
-                    std::mem::drop(env); // thunk may be a 1RC pointer
-
-                    if thunk.state() != ThunkState::Evaluated {
-                        if thunk.should_update() {
-                            match thunk.mk_update_frame() {
-                                Ok(thunk_upd) => self.stack.push_thunk(thunk_upd),
-                                Err(BlackholedError) => {
-                                    return Err(EvalError::InfiniteRecursion(
-                                        self.call_stack.clone(),
-                                        pos,
-                                    ))
-                                }
-                            }
-                        }
-                        // If the thunk isn't to be updated, directly set the evaluated flag.
-                        else {
-                            thunk.set_evaluated();
+                    std::mem::drop(env); // idx may be a 1RC pointer
+
+                    match self.cache.get_update_index(&mut idx) {
+                        Ok(Some(idx_upd)) => self.stack.push_update_index(idx_upd),
+                        Ok(None) => {}
+                        Err(BlackholedError) => {
+                            return Err(EvalError::InfiniteRecursion(self.call_stack.clone(), pos))
                         }
                     }
-                    self.call_stack.enter_var(thunk.ident_kind(), *x, pos);
-                    thunk.into_closure()
+
+                    self.call_stack.enter_var(idx.ident_kind(), *x, pos);
+                    self.cache.get(idx)
                 }
                 Term::App(t1, t2) => {
                     self.call_stack.enter_app(pos);
@@ -356,25 +365,22 @@ impl<R: ImportResolver> VirtualMachine<R> {
                     }
                 }
                 Term::Let(x, s, t, LetAttrs { binding_type, rec }) => {
-                    let closure = Closure {
+                    let closure: Closure = Closure {
                         body: s.clone(),
                         env: env.clone(),
                     };
 
-                    let mut thunk = match binding_type {
-                        BindingType::Normal => Thunk::new(closure, IdentKind::Let),
-                        BindingType::Revertible(deps) => {
-                            Thunk::new_rev(closure, IdentKind::Let, deps.clone())
-                        }
-                    };
+                    let idx = self
+                        .cache
+                        .add(closure, IdentKind::Let, binding_type.clone());
 
                     // Patch the environment with the (x <- closure) binding
                     if *rec {
-                        let thunk_ = thunk.clone();
-                        thunk.borrow_mut().env.insert(*x, thunk_);
+                        let idx_ = idx.clone();
+                        self.cache.patch(idx_.clone(), |cl| cl.env.insert(*x, idx_));
                     }
 
-                    env.insert(*x, thunk);
+                    env.insert(*x, idx);
                     Closure {
                         body: t.clone(),
                         env,
@@ -514,12 +520,11 @@ impl<R: ImportResolver> VirtualMachine<R> {
                     }
                 }
                 Term::RecRecord(record, dyn_fields, _) => {
-                    let rec_env = fixpoint::rec_env(record.fields.iter(), &env)?;
+                    let rec_env = fixpoint::rec_env(&mut self.cache, record.fields.iter(), &env)?;
 
-                    record
-                        .fields
-                        .iter()
-                        .try_for_each(|(_, rt)| fixpoint::patch_field(rt, &rec_env, &env))?;
+                    record.fields.iter().try_for_each(|(_, rt)| {
+                        fixpoint::patch_field(&mut self.cache, rt, &rec_env, &env)
+                    })?;
 
                     //TODO: We should probably avoid cloning the record, using `match_sharedterm`
                     //instead of `match` in the main eval loop, if possible
@@ -538,7 +543,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
                                 let id_t = id_t.clone();
                                 let pos = t.pos;
 
-                                fixpoint::patch_field(t, &rec_env, &env)?;
+                                fixpoint::patch_field(&mut self.cache, t, &rec_env, &env)?;
                                 Ok(RichTerm::new(
                                     Term::App(
                                         mk_term::op2(BinaryOp::DynExtend(), id_t, acc),
@@ -570,7 +575,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
                             },
                             env,
                         };
-                        update_thunks(&mut self.stack, &update_closure);
+                        update_at_indices(&mut self.cache, &mut self.stack, &update_closure);
 
                         let Closure {
                             body: RichTerm { term, .. },
@@ -617,7 +622,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
                     let closurized_array = terms
                         .clone()
                         .into_iter()
-                        .map(|t| t.closurize(&mut local_env, env.clone()))
+                        .map(|t| t.closurize(&mut self.cache, &mut local_env, env.clone()))
                         .collect();
 
                     let closurized_ctrs = attrs
@@ -625,7 +630,11 @@ impl<R: ImportResolver> VirtualMachine<R> {
                         .iter()
                         .map(|ctr| {
                             PendingContract::new(
-                                ctr.contract.clone().closurize(&mut local_env, env.clone()),
+                                ctr.contract.clone().closurize(
+                                    &mut self.cache,
+                                    &mut local_env,
+                                    env.clone(),
+                                ),
                                 ctr.label.clone(),
                             )
                         })
@@ -649,7 +658,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
                     return Err(EvalError::ParseError(parse_error.clone()));
                 }
                 // Continuation of operations and thunk update
-                _ if self.stack.is_top_thunk() || self.stack.is_top_cont() => {
+                _ if self.stack.is_top_idx() || self.stack.is_top_cont() => {
                     clos = Closure {
                         body: RichTerm {
                             term: shared_term,
@@ -657,8 +666,8 @@ impl<R: ImportResolver> VirtualMachine<R> {
                         },
                         env,
                     };
-                    if self.stack.is_top_thunk() {
-                        update_thunks(&mut self.stack, &clos);
+                    if self.stack.is_top_idx() {
+                        update_at_indices(&mut self.cache, &mut self.stack, &clos);
                         clos
                     } else {
                         self.continuate_operation(clos)?
@@ -666,9 +675,9 @@ impl<R: ImportResolver> VirtualMachine<R> {
                 }
                 // Function call
                 Term::Fun(x, t) => {
-                    if let Some((thunk, pos_app)) = self.stack.pop_arg_as_thunk() {
+                    if let Some((idx, pos_app)) = self.stack.pop_arg_as_idx(&mut self.cache) {
                         self.call_stack.enter_fun(pos_app);
-                        env.insert(*x, thunk);
+                        env.insert(*x, idx);
                         Closure {
                             body: t.clone(),
                             env,
@@ -679,7 +688,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
                 }
                 // Otherwise, this is either an ill-formed application, or we are done
                 t => {
-                    if let Some((arg, pos_app)) = self.stack.pop_arg() {
+                    if let Some((arg, pos_app)) = self.stack.pop_arg(&self.cache) {
                         return Err(EvalError::NotAFunc(
                             RichTerm {
                                 term: shared_term.clone(),
@@ -697,6 +706,21 @@ impl<R: ImportResolver> VirtualMachine<R> {
     }
 }
 
+impl<C: Cache> VirtualMachine<ImportCache, C> {
+    pub fn prepare_eval(&mut self, main_id: FileId) -> Result<(RichTerm, Environment), Error> {
+        let Envs {
+            eval_env,
+            type_ctxt,
+        }: Envs = self.import_resolver.prepare_stdlib(&mut self.cache)?;
+        self.import_resolver.prepare(main_id, &type_ctxt)?;
+        Ok((self.import_resolver().get(main_id).unwrap(), eval_env))
+    }
+
+    pub fn prepare_stdlib(&mut self) -> Result<Envs, Error> {
+        self.import_resolver.prepare_stdlib(&mut self.cache)
+    }
+}
+
 /// Kind of an identifier.
 #[derive(Debug, PartialEq, Eq, Clone, Copy)]
 pub enum IdentKind {
@@ -706,22 +730,30 @@ pub enum IdentKind {
 }
 
 /// A closure, a term together with an environment.
-#[derive(Clone, Debug, PartialEq)]
+#[derive(Debug, PartialEq)]
 pub struct Closure {
     pub body: RichTerm,
     pub env: Environment,
 }
 
-impl Closure {
-    pub fn atomic_closure(body: RichTerm) -> Closure {
+impl Clone for Closure {
+    fn clone(&self) -> Self {
         Closure {
-            body,
-            env: Environment::new(),
+            body: self.body.clone(),
+            env: self.env.clone(),
         }
     }
 }
 
-pub type Environment = GenericEnvironment<Ident, Thunk>;
+impl Closure {
+    pub fn atomic_closure(body: RichTerm) -> Closure {
+        let env: Environment = Environment::new();
+        Closure { body, env }
+    }
+}
+
+#[allow(type_alias_bounds)] // TODO: Look into this warning.
+pub type Environment = GenericEnvironment<Ident, CacheIndex>;
 
 /// Raised when trying to build an environment from a term which is not a record.
 #[derive(Clone, Debug)]
@@ -730,13 +762,17 @@ pub enum EnvBuildError {
 }
 
 /// Add the bindings of a record to an environment. Ignore the fields defined by interpolation.
-pub fn env_add_term(env: &mut Environment, rt: RichTerm) -> Result<(), EnvBuildError> {
+pub fn env_add_term<C: Cache>(
+    cache: &mut C,
+    env: &mut Environment,
+    rt: RichTerm,
+) -> Result<(), EnvBuildError> {
     match_sharedterm! {rt.term, with {
             Term::Record(record) | Term::RecRecord(record, ..) => {
                 let ext = record.fields.into_iter().map(|(id, t)| {
                     (
                         id,
-                        Thunk::new(Closure::atomic_closure(t), IdentKind::Record),
+                        cache.add(Closure::atomic_closure(t), IdentKind::Record, BindingType::Normal),
                     )
                 });
 
@@ -748,32 +784,43 @@ pub fn env_add_term(env: &mut Environment, rt: RichTerm) -> Result<(), EnvBuildE
 }
 
 /// Bind a closure in an environment.
-pub fn env_add(env: &mut Environment, id: Ident, rt: RichTerm, local_env: Environment) {
+pub fn env_add<C: Cache>(
+    cache: &mut C,
+    env: &mut Environment,
+    id: Ident,
+    rt: RichTerm,
+    local_env: Environment,
+) {
     let closure = Closure {
         body: rt,
         env: local_env,
     };
-    env.insert(id, Thunk::new(closure, IdentKind::Let));
+    env.insert(id, cache.add(closure, IdentKind::Let, BindingType::Normal));
 }
 
 /// Pop and update all the thunks on the top of the stack with the given closure.
-fn update_thunks(stack: &mut Stack, closure: &Closure) {
-    while let Some(thunk) = stack.pop_thunk() {
-        thunk.update(closure.clone());
+fn update_at_indices<C: Cache>(cache: &mut C, stack: &mut Stack<C>, closure: &Closure) {
+    while let Some(idx) = stack.pop_update_index() {
+        cache.update(closure.clone(), idx);
     }
 }
 
 /// Recursively substitute each variable occurrence of a term for its value in the environment.
-pub fn subst(rt: RichTerm, initial_env: &Environment, env: &Environment) -> RichTerm {
+pub fn subst<C: Cache>(
+    cache: &C,
+    rt: RichTerm,
+    initial_env: &Environment,
+    env: &Environment,
+) -> RichTerm {
     let RichTerm { term, pos } = rt;
 
     match term.into_owned() {
         Term::Var(id) => env
             .get(&id)
             .or_else(|| initial_env.get(&id))
-            .map(|thunk| {
-                let closure = thunk.get_owned();
-                subst(closure.body, initial_env, &closure.env)
+            .map(|idx| {
+                let closure = cache.get(idx.clone());
+                subst(cache, closure.body, initial_env, &closure.env)
             })
             .unwrap_or_else(|| RichTerm::new(Term::Var(id), pos)),
         v @ Term::Null
@@ -790,72 +837,72 @@ pub fn subst(rt: RichTerm, initial_env: &Environment, env: &Environment) -> Rich
         | v @ Term::Import(_)
         | v @ Term::ResolvedImport(_) => RichTerm::new(v, pos),
         Term::Let(id, t1, t2, attrs) => {
-            let t1 = subst(t1, initial_env, env);
-            let t2 = subst(t2, initial_env, env);
+            let t1 = subst(cache, t1, initial_env, env);
+            let t2 = subst(cache, t2, initial_env, env);
 
             RichTerm::new(Term::Let(id, t1, t2, attrs), pos)
         }
         p @ Term::LetPattern(..) => panic!("Pattern {:?} has not been transformed before evaluation", p),
         p @ Term::FunPattern(..) => panic!("Pattern {:?} has not been transformed before evaluation", p),
         Term::App(t1, t2) => {
-            let t1 = subst(t1, initial_env, env);
-            let t2 = subst(t2, initial_env, env);
+            let t1 = subst(cache, t1, initial_env, env);
+            let t2 = subst(cache, t2, initial_env, env);
 
             RichTerm::new(Term::App(t1, t2), pos)
         }
         Term::Switch(t, cases, default) => {
             let default =
-                default.map(|d| subst(d, initial_env, env));
+                default.map(|d| subst(cache, d, initial_env, env));
             let cases = cases
                 .into_iter()
                 .map(|(id, t)| {
                     (
                         id,
-                        subst(t, initial_env, env),
+                        subst(cache, t, initial_env, env),
                     )
                 })
                 .collect();
-            let t = subst(t, initial_env, env);
+            let t = subst(cache, t, initial_env, env);
 
             RichTerm::new(Term::Switch(t, cases, default), pos)
         }
         Term::Op1(op, t) => {
-            let t = subst(t, initial_env, env);
+            let t = subst(cache, t, initial_env, env);
 
             RichTerm::new(Term::Op1(op, t), pos)
         }
         Term::Op2(op, t1, t2) => {
-            let t1 = subst(t1, initial_env, env);
-            let t2 = subst(t2, initial_env, env);
+            let t1 = subst(cache, t1, initial_env, env);
+            let t2 = subst(cache, t2, initial_env, env);
 
             RichTerm::new(Term::Op2(op, t1, t2), pos)
         }
         Term::OpN(op, ts) => {
             let ts = ts
                 .into_iter()
-                .map(|t| subst(t, initial_env, env))
+                .map(|t| subst(cache, t, initial_env, env))
                 .collect();
 
             RichTerm::new(Term::OpN(op, ts), pos)
         }
         Term::Sealed(i, t, lbl) => {
-            let t = subst(t, initial_env, env);
+            let t = subst(cache, t, initial_env, env);
             RichTerm::new(Term::Sealed(i, t, lbl), pos)
         }
         Term::Record(record) => {
-            let record = record.map_fields(|_, t| subst(t, initial_env, env));
+            let record = record.map_fields(|_, t| subst(cache, t, initial_env, env));
 
             RichTerm::new(Term::Record(record), pos)
         }
         Term::RecRecord(record, dyn_fields, deps) => {
-            let record = record.map_fields(|_, t| subst(t, initial_env, env));
+            let record = record.map_fields(|_, t| subst(cache, t, initial_env, env));
 
             let dyn_fields = dyn_fields
                 .into_iter()
                 .map(|(id_t, t)| {
                     (
-                        subst(id_t, initial_env, env),
-                        subst(t, initial_env, env),
+                        subst(cache, id_t, initial_env, env),
+                        subst(cache, t, initial_env, env),
                     )
                 })
                 .collect();
@@ -865,7 +912,7 @@ pub fn subst(rt: RichTerm, initial_env: &Environment, env: &Environment) -> Rich
         Term::Array(ts, attrs) => {
             let ts = ts
                 .into_iter()
-                .map(|t| subst(t, initial_env, env))
+                .map(|t| subst(cache, t, initial_env, env))
                 .collect();
 
             RichTerm::new(Term::Array(ts, attrs), pos)
@@ -876,7 +923,7 @@ pub fn subst(rt: RichTerm, initial_env: &Environment, env: &Environment) -> Rich
                 .map(|chunk| match chunk {
                     chunk @ StrChunk::Literal(_) => chunk,
                     StrChunk::Expr(t, indent) => StrChunk::Expr(
-                        subst(t, initial_env, env),
+                        subst(cache, t, initial_env, env),
                         indent,
                     ),
                 })
@@ -921,7 +968,7 @@ pub fn subst(rt: RichTerm, initial_env: &Environment, env: &Environment) -> Rich
             //     Contract { types, ..ctr }
             // });
 
-            let value = meta.value.map(|t| subst(t, initial_env, env));
+            let value = meta.value.map(|t| subst(cache, t, initial_env, env));
 
             let meta = MetaValue {
                 doc: meta.doc,
@@ -947,14 +994,20 @@ pub fn subst(rt: RichTerm, initial_env: &Environment, env: &Environment) -> Rich
 /// approximation and hence is necessarily incomplete. In practice, this function is able to
 /// traverse merge expressions and follow variables links, but within a limit (in the number of
 /// variables followed).
-pub fn is_empty_optional(rt: &RichTerm, env: &Environment) -> bool {
-    fn is_empty_optional_aux(rt: &RichTerm, env: &Environment, is_opt: bool, gas: &mut u8) -> bool {
+pub fn is_empty_optional<C: Cache>(cache: &C, rt: &RichTerm, env: &Environment) -> bool {
+    fn is_empty_optional_aux<C: Cache>(
+        cache: &C,
+        rt: &RichTerm,
+        env: &Environment,
+        is_opt: bool,
+        gas: &mut u8,
+    ) -> bool {
         match rt.as_ref() {
             Term::MetaValue(meta) => {
                 let is_opt = is_opt || meta.opt;
 
                 if let Some(ref next) = meta.value {
-                    is_empty_optional_aux(next, env, is_opt, gas)
+                    is_empty_optional_aux(cache, next, env, is_opt, gas)
                 } else {
                     is_opt
                 }
@@ -968,13 +1021,15 @@ pub fn is_empty_optional(rt: &RichTerm, env: &Environment) -> bool {
                 // - both branch are empty optionals
                 // - a wrapping metavalue is optional (is_opt is true at this point) and both
                 // branch are empty.
-                is_empty_optional_aux(t1, env, is_opt, gas)
-                    && is_empty_optional_aux(t2, env, is_opt, gas)
+                is_empty_optional_aux(cache, t1, env, is_opt, gas)
+                    && is_empty_optional_aux(cache, t2, env, is_opt, gas)
             }
             Term::Var(id) if *gas > 0 => {
-                if let Some(closure) = env.get(id).map(Thunk::borrow) {
-                    *gas -= 1;
-                    is_empty_optional_aux(&closure.body, &closure.env, is_opt, gas)
+                if let Some(index) = env.get(id) {
+                    cache.get_then(index.clone(), |clos| {
+                        *gas -= 1;
+                        is_empty_optional_aux(cache, &clos.body, &clos.env, is_opt, gas)
+                    })
                 } else {
                     false
                 }
@@ -986,7 +1041,7 @@ pub fn is_empty_optional(rt: &RichTerm, env: &Environment) -> bool {
     // The total amount of gas is rather abritrary, but in any case, it ought to stay low: remember
     // that is_empty_optional may be called on each field of a record when evaluatinog some record
     // operations.
-    is_empty_optional_aux(rt, env, false, &mut 8)
+    is_empty_optional_aux(cache, rt, env, false, &mut 8)
 }
 
 #[cfg(test)]
diff --git a/src/eval/operation.rs b/src/eval/operation.rs
index 01f9cb20..4f84ae1f 100644
--- a/src/eval/operation.rs
+++ b/src/eval/operation.rs
@@ -20,6 +20,7 @@ use crate::{
 use crate::{
     error::EvalError,
     eval,
+    eval::Cache,
     identifier::Ident,
     label::ty_path,
     match_sharedterm, mk_app, mk_fun, mk_opn, mk_record,
@@ -96,7 +97,7 @@ impl std::fmt::Debug for OperationCont {
     }
 }
 
-impl<R: ImportResolver> VirtualMachine<R> {
+impl<R: ImportResolver, C: Cache> VirtualMachine<R, C> {
     /// Process to the next step of the evaluation of an operation.
     ///
     /// Depending on the content of the stack, it either starts the evaluation of the first argument,
@@ -170,8 +171,14 @@ impl<R: ImportResolver> VirtualMachine<R> {
             UnaryOp::Ite() => {
                 if let Term::Bool(b) = *t {
                     if self.stack.count_args() >= 2 {
-                        let (fst, ..) = self.stack.pop_arg().expect("Condition already checked.");
-                        let (snd, ..) = self.stack.pop_arg().expect("Condition already checked.");
+                        let (fst, ..) = self
+                            .stack
+                            .pop_arg(&self.cache)
+                            .expect("Condition already checked.");
+                        let (snd, ..) = self
+                            .stack
+                            .pop_arg(&self.cache)
+                            .expect("Condition already checked.");
 
                         Ok(if b { fst } else { snd })
                     } else {
@@ -206,7 +213,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
             UnaryOp::BoolAnd() =>
             // The syntax should not allow partially applied boolean operators.
             {
-                if let Some((next, ..)) = self.stack.pop_arg() {
+                if let Some((next, ..)) = self.stack.pop_arg(&self.cache) {
                     match &*t {
                         Term::Bool(true) => Ok(next),
                         // FIXME: this does not check that the second argument is actually a boolean.
@@ -230,7 +237,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
                 }
             }
             UnaryOp::BoolOr() => {
-                if let Some((next, ..)) = self.stack.pop_arg() {
+                if let Some((next, ..)) = self.stack.pop_arg(&self.cache) {
                     match &*t {
                         Term::Bool(true) => Ok(Closure::atomic_closure(RichTerm {
                             term: t,
@@ -298,11 +305,14 @@ impl<R: ImportResolver> VirtualMachine<R> {
                 }
             }
             UnaryOp::Switch(has_default) => {
-                let (cases_closure, ..) = self.stack.pop_arg().expect("missing arg for switch");
+                let (cases_closure, ..) = self
+                    .stack
+                    .pop_arg(&self.cache)
+                    .expect("missing arg for switch");
                 let default = if has_default {
                     Some(
                         self.stack
-                            .pop_arg()
+                            .pop_arg(&self.cache)
                             .map(|(clos, ..)| clos)
                             .expect("missing default case for switch"),
                     )
@@ -472,7 +482,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
                             .into_iter()
                             // Ignore optional fields without definitions.
                             .filter_map(|(id, t)| {
-                                (!is_empty_optional(&t, &env)).then(|| id.to_string())
+                                (!is_empty_optional(&self.cache, &t, &env)).then(|| id.to_string())
                             })
                             .collect();
                         fields.sort();
@@ -503,7 +513,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
                             .into_iter()
                             // Ignore optional fields without definitions.
                             .filter_map(|(_, t)| {
-                                (!is_empty_optional(&t, &env)).then_some(t)
+                                (!is_empty_optional(&self.cache, &t, &env)).then_some(t)
                             })
                             .collect();
                         Ok(Closure {
@@ -525,12 +535,12 @@ impl<R: ImportResolver> VirtualMachine<R> {
             UnaryOp::ArrayMap() => {
                 let (f, ..) = self
                     .stack
-                    .pop_arg()
+                    .pop_arg(&self.cache)
                     .ok_or_else(|| EvalError::NotEnoughArgs(2, String::from("map"), pos_op))?;
                 match_sharedterm! {t, with {
                         Term::Array(ts, attrs) => {
                             let mut shared_env = Environment::new();
-                            let f_as_var = f.body.closurize(&mut env, f.env);
+                            let f_as_var = f.body.closurize(&mut self.cache, &mut env, f.env);
 
                             // Array elements are closurized to preserve lazyness of data structures. It
                             // maintains the invariant that any data structure only contain thunks (that is,
@@ -545,7 +555,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
                                     );
 
                                     RichTerm::new(Term::App(f_as_var.clone(), t_with_ctrs), pos_op_inh)
-                                        .closurize(&mut shared_env, env.clone())
+                                        .closurize(&mut self.cache, &mut shared_env, env.clone())
                                 })
                                 .collect();
 
@@ -567,7 +577,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
             UnaryOp::ArrayGen() => {
                 let (f, _) = self
                     .stack
-                    .pop_arg()
+                    .pop_arg(&self.cache)
                     .ok_or_else(|| EvalError::NotEnoughArgs(2, String::from("generate"), pos_op))?;
 
                 if let Term::Num(n) = *t {
@@ -582,15 +592,18 @@ impl<R: ImportResolver> VirtualMachine<R> {
                         ))
                     } else {
                         let mut shared_env = Environment::new();
-                        let f_as_var = f.body.closurize(&mut env, f.env);
+                        let f_as_var = f.body.closurize(&mut self.cache, &mut env, f.env);
 
                         // Array elements are closurized to preserve lazyness of data structures. It
                         // maintains the invariant that any data structure only contain thunks (that is,
                         // currently, variables).
                         let ts = (0..n_int)
                             .map(|n| {
-                                mk_app!(f_as_var.clone(), Term::Num(n as f64))
-                                    .closurize(&mut shared_env, env.clone())
+                                mk_app!(f_as_var.clone(), Term::Num(n as f64)).closurize(
+                                    &mut self.cache,
+                                    &mut shared_env,
+                                    env.clone(),
+                                )
                             })
                             .collect();
 
@@ -612,7 +625,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
                 }
             }
             UnaryOp::RecordMap() => {
-                let (f, ..) = self.stack.pop_arg().ok_or_else(|| {
+                let (f, ..) = self.stack.pop_arg(&self.cache).ok_or_else(|| {
                     EvalError::NotEnoughArgs(2, String::from("recordMap"), pos_op)
                 })?;
 
@@ -633,14 +646,13 @@ impl<R: ImportResolver> VirtualMachine<R> {
                             }
 
                             let mut shared_env = Environment::new();
-                            let f_as_var = f.body.closurize(&mut env, f.env);
+                            let f_as_var = f.body.closurize(&mut self.cache, &mut env, f.env);
 
                             // As for `ArrayMap` (see above), we closurize the content of fields
-                            let record = record.map_fields_without_optionals(&env, |id, t| {
+                            let record = record.map_fields_without_optionals(&mut self.cache, &mut shared_env, &env, |id, t| {
                                 let pos = t.pos.into_inherited();
 
                                 mk_app!(f_as_var.clone(), mk_term::string(id.label()), t)
-                                    .closurize(&mut shared_env, env.clone())
                                     .with_pos(pos)
                             });
 
@@ -661,7 +673,10 @@ impl<R: ImportResolver> VirtualMachine<R> {
             }
             UnaryOp::Seq() => {
                 if self.stack.count_args() >= 1 {
-                    let (next, ..) = self.stack.pop_arg().expect("Condition already checked.");
+                    let (next, ..) = self
+                        .stack
+                        .pop_arg(&self.cache)
+                        .expect("Condition already checked.");
                     Ok(next)
                 } else {
                     Err(EvalError::NotEnoughArgs(2, String::from("seq"), pos_op))
@@ -700,7 +715,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
                             .fields
                             .into_iter()
                             // We ignore empty optional fields
-                            .filter(|(_, t)| !is_empty_optional(t, &env))
+                            .filter(|(_, t)| !is_empty_optional(&self.cache, t, &env))
                             .map(|(id, t)| {
                                 (
                                     Some(callstack::StackElem::Field {
@@ -719,18 +734,19 @@ impl<R: ImportResolver> VirtualMachine<R> {
                     }
                     Term::Array(ts, attrs) if !ts.is_empty() => {
                         let mut shared_env = Environment::new();
-                        let terms = seq_terms(
-                            ts.into_iter().map(|t| {
-                                let t_with_ctr = apply_contracts(
-                                    t,
-                                    attrs.pending_contracts.iter().cloned(),
-                                    pos.into_inherited(),
-                                )
-                                .closurize(&mut shared_env, env.clone());
-                                (None, t_with_ctr)
-                            }),
-                            pos_op,
-                        );
+                        let terms =
+                            seq_terms(
+                                ts.into_iter().map(|t| {
+                                    let t_with_ctr = apply_contracts(
+                                        t,
+                                        attrs.pending_contracts.iter().cloned(),
+                                        pos.into_inherited(),
+                                    )
+                                    .closurize(&mut self.cache, &mut shared_env, env.clone());
+                                    (None, t_with_ctr)
+                                }),
+                                pos_op,
+                            );
 
                         Ok(Closure {
                             body: terms,
@@ -738,7 +754,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
                         })
                     }
                     _ => {
-                        if let Some((next, ..)) = self.stack.pop_arg() {
+                        if let Some((next, ..)) = self.stack.pop_arg(&self.cache) {
                             Ok(next)
                         } else {
                             Err(EvalError::NotEnoughArgs(2, String::from("deepSeq"), pos_op))
@@ -1162,7 +1178,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
                         Term::Record(record) if !record.fields.is_empty() => {
                             let mut shared_env = Environment::new();
 
-                            let record = record.map_fields_without_optionals(&env, |id, t| {
+                            let record = record.map_fields_without_optionals(&mut self.cache, &mut shared_env, &env, |id, t| {
                                 let stack_elem = Some(callstack::StackElem::Field {
                                     id,
                                     pos_record: pos,
@@ -1171,7 +1187,6 @@ impl<R: ImportResolver> VirtualMachine<R> {
                                 });
 
                                 mk_term::op1(UnaryOp::Force(stack_elem), t)
-                                    .closurize(&mut shared_env, env.clone())
                             });
 
                             let terms = record.fields.clone().into_values();
@@ -1195,7 +1210,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
                                             pos.into_inherited(),
                                         ),
                                     )
-                                    .closurize(&mut shared_env, env.clone())
+                                    .closurize(&mut self.cache, &mut shared_env, env.clone())
                                 })
                                 // It's important to collect here, otherwise the two usages below
                                 // will each do their own .closurize(...) calls and end up with
@@ -1216,8 +1231,12 @@ impl<R: ImportResolver> VirtualMachine<R> {
                     })
                 }
             }
-            UnaryOp::RecDefault() => Ok(RecPriority::Bottom.propagate_in_term(t, env, pos)),
-            UnaryOp::RecForce() => Ok(RecPriority::Top.propagate_in_term(t, env, pos)),
+            UnaryOp::RecDefault() => {
+                Ok(RecPriority::Bottom.propagate_in_term(&mut self.cache, t, env, pos))
+            }
+            UnaryOp::RecForce() => {
+                Ok(RecPriority::Top.propagate_in_term(&mut self.cache, t, env, pos))
+            }
             UnaryOp::RecordEmptyWithTail() => match_sharedterm! { t,
                 with {
                     Term::Record(r) => {
@@ -1519,12 +1538,12 @@ impl<R: ImportResolver> VirtualMachine<R> {
                 if let Term::Lbl(l) = &*t2 {
                     // Track the contract argument for better error reporting, and push back the label
                     // on the stack, so that it becomes the first argument of the contract.
-                    let thunk = self.stack.track_arg().ok_or_else(|| {
+                    let idx = self.stack.track_arg(&mut self.cache).ok_or_else(|| {
                         EvalError::NotEnoughArgs(3, String::from("assume"), pos_op)
                     })?;
                     let mut l = l.clone();
-                    l.arg_pos = thunk.borrow().body.pos;
-                    l.arg_thunk = Some(thunk);
+                    l.arg_pos = self.cache.get_then(idx.clone(), |c| c.body.pos);
+                    l.arg_idx = Some(idx);
 
                     self.stack.push_arg(
                         Closure::atomic_closure(RichTerm::new(Term::Lbl(l), pos2.into_inherited())),
@@ -1545,7 +1564,11 @@ impl<R: ImportResolver> VirtualMachine<R> {
                                 term: t1,
                                 pos: pos1,
                             }
-                            .closurize(&mut new_env, env1);
+                            .closurize(
+                                &mut self.cache,
+                                &mut new_env,
+                                env1,
+                            );
 
                             // Convert the record to the function `fun l x => MergeContract l x t1
                             // contract`.
@@ -1666,7 +1689,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
                     env: env2,
                 };
 
-                match eq(&mut env, c1, c2) {
+                match eq(&mut self.cache, &mut env, c1, c2) {
                     EqResult::Bool(b) => match (b, self.stack.pop_eq()) {
                         (false, _) => {
                             self.stack.clear_eqs();
@@ -1680,8 +1703,8 @@ impl<R: ImportResolver> VirtualMachine<R> {
                             pos_op_inh,
                         ))),
                         (true, Some((c1, c2))) => {
-                            let t1 = c1.body.closurize(&mut env, c1.env);
-                            let t2 = c2.body.closurize(&mut env, c2.env);
+                            let t1 = c1.body.closurize(&mut self.cache, &mut env, c1.env);
+                            let t2 = c2.body.closurize(&mut self.cache, &mut env, c2.env);
 
                             Ok(Closure {
                                 body: RichTerm::new(Term::Op2(BinaryOp::Eq(), t1, t2), pos_op),
@@ -1901,16 +1924,16 @@ impl<R: ImportResolver> VirtualMachine<R> {
             BinaryOp::DynExtend() => {
                 let (clos, _) = self
                     .stack
-                    .pop_arg()
+                    .pop_arg(&self.cache)
                     .ok_or_else(|| EvalError::NotEnoughArgs(3, String::from("$[ .. ]"), pos_op))?;
 
                 if let Term::Str(id) = &*t1 {
                     match_sharedterm! {t2, with {
                             Term::Record(record) => {
                                 let mut fields = record.fields;
-                                let as_var = clos.body.closurize(&mut env2, clos.env);
+                                let as_var = clos.body.closurize(&mut self.cache, &mut env2, clos.env);
                                 match fields.insert(Ident::from(id), as_var) {
-                                    Some(t) if !is_empty_optional(&t, &env2) => Err(EvalError::Other(format!("$[ .. ]: tried to extend record with the field {}, but it already exists", id), pos_op)),
+                                    Some(t) if !is_empty_optional(&self.cache, &t, &env2) => Err(EvalError::Other(format!("$[ .. ]: tried to extend record with the field {}, but it already exists", id), pos_op)),
                                     _ => Ok(Closure {
                                         body: Term::Record(RecordData { fields, ..record }).into(),
                                         env: env2,
@@ -1947,7 +1970,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
                                 let mut fields = record.fields;
                                 let fetched = fields.remove(&Ident::from(&id));
                                 if fetched.is_none()
-                                   || matches!(fetched, Some(t) if is_empty_optional(&t, &env2)) {
+                                   || matches!(fetched, Some(t) if is_empty_optional(&self.cache, &t, &env2)) {
                                     Err(EvalError::FieldMissing(
                                         id,
                                         String::from("(-$)"),
@@ -1995,7 +2018,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
                     Term::Str(id) => {
                         if let Term::Record(record) = &*t2 {
                             Ok(Closure::atomic_closure(RichTerm::new(
-                                Term::Bool(matches!(record.fields.get(&Ident::from(id)), Some(t5) if !is_empty_optional(t5, &env2))),
+                                Term::Bool(matches!(record.fields.get(&Ident::from(id)), Some(t5) if !is_empty_optional(&self.cache, t5, &env2))),
                                 pos_op_inh,
                             )))
                         } else {
@@ -2067,12 +2090,12 @@ impl<R: ImportResolver> VirtualMachine<R> {
 
                                 ts.extend(ts1.into_iter().map(|t|
                                     apply_contracts(t, ctrs_left.iter().cloned(), pos1)
-                                    .closurize(&mut env, env1.clone())
+                                    .closurize(&mut self.cache, &mut env, env1.clone())
                                 ));
 
                                 ts.extend(ts2.into_iter().map(|t|
                                     apply_contracts(t, ctrs_right.clone(), pos2)
-                                    .closurize(&mut env, env2.clone())
+                                    .closurize(&mut self.cache, &mut env, env2.clone())
                                 ));
 
                                 let attrs = ArrayAttrs {
@@ -2149,6 +2172,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
                 )),
             },
             BinaryOp::Merge() => merge(
+                &mut self.cache,
                 RichTerm {
                     term: t1,
                     pos: pos1,
@@ -2239,6 +2263,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
                     // Serialization needs all variables term to be fully substituted
                     let initial_env = Environment::new();
                     let rt2 = subst(
+                        &self.cache,
                         RichTerm {
                             term: t2,
                             pos: pos2,
@@ -2375,7 +2400,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
                 )),
             },
             BinaryOp::ArrayLazyAssume() => {
-                let (ctr, _) = self.stack.pop_arg().ok_or_else(|| {
+                let (ctr, _) = self.stack.pop_arg(&self.cache).ok_or_else(|| {
                     EvalError::NotEnoughArgs(3, String::from("arrayLazyAssume"), pos_op)
                 })?;
 
@@ -2402,7 +2427,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
                     with {
                         Term::Array(ts, attrs) => {
                             // Preserve the environment of the contract in the resulting array.
-                            let rt3 = rt3.closurize(&mut env2, env3);
+                            let rt3 = rt3.closurize(&mut self.cache, &mut env2, env3);
 
                             let array_with_ctr = Closure {
                                 body: RichTerm::new(
@@ -2591,6 +2616,7 @@ impl<R: ImportResolver> VirtualMachine<R> {
                 match_sharedterm! {t1, with {
                         Term::Lbl(lbl) => {
                             merge(
+                                &mut self.cache,
                                 RichTerm {
                                     term: t2,
                                     pos: pos2,
@@ -2669,8 +2695,11 @@ impl<R: ImportResolver> VirtualMachine<R> {
                         let mut r = r.clone();
                         let mut env = env3;
 
-                        let tail_as_var =
-                            RichTerm::from(Term::Record(tail.clone())).closurize(&mut env, env4);
+                        let tail_as_var = RichTerm::from(Term::Record(tail.clone())).closurize(
+                            &mut self.cache,
+                            &mut env,
+                            env4,
+                        );
                         r.sealed_tail =
                             Some(record::SealedTail::new(*s, label.clone(), tail_as_var));
 
@@ -2815,62 +2844,74 @@ impl RecPriority {
     }
 
     /// Propagate the priority down the fields of a record.
-    fn propagate_in_record(&self, record: RecordData, env: &Environment, pos: TermPos) -> Closure {
+    fn propagate_in_record<C: Cache>(
+        &self,
+        cache: &mut C,
+        mut record: RecordData,
+        env: &Environment,
+        pos: TermPos,
+    ) -> Closure {
         let mut new_env = Environment::new();
 
-        let record = record.map_fields_without_optionals(env, |_, rt| {
-            // There is a subtlety with respect to overriding here. Take:
-            //
-            // ```nickel
-            // ({foo = bar + 1, bar = 1} | rec default) & {bar = 2}
-            // ```
-            //
-            // In the example above, if we just map `$rec_default` on the value of `foo` and
-            // closurize it into a new, normal thunk (non revertible), we lose the ability to
-            // override `foo` and we end up with the unexpected result `{foo = 2, bar = 2}`.
-            //
-            // What we want is that:
-            //
-            // ```nickel
-            // {foo = bar + 1, bar = 1} | rec default
-            // ```
-            //
-            // is equivalent to writing:
-            //
-            // ```nickel
-            // {foo | default = bar + 1, bar | default = 1}
-            // ```
-            //
-            // For revertible thunks, we don't want to only map the push operator on the
-            // current cached value, but also on the original expression.
-            //
-            // To do so, we create a new independent copy of the original thunk by mapping the
-            // function over both expressions (in the sense of both the original expression and
-            // the cached expression). This logic is encapsulated by `Thunk::map`.
-            let pos = rt.pos;
-
-            let thunk = match rt.as_ref() {
-                Term::Var(id) => {
-                    env.get(id)
-                        .unwrap()
-                        .map(|Closure { ref body, ref env }| Closure {
-                            body: self.apply_rec_prio_op(body.clone()),
-                            env: env.clone(),
-                        })
-                }
-                _ => eval::lazy::Thunk::new(
-                    Closure {
-                        body: self.apply_rec_prio_op(rt),
-                        env: env.clone(),
-                    },
-                    eval::IdentKind::Record,
-                ),
-            };
+        record.fields = record
+            .fields
+            .into_iter()
+            .filter_map(|(id, rt)| {
+                // There is a subtlety with respect to overriding here. Take:
+                //
+                // ```nickel
+                // ({foo = bar + 1, bar = 1} | rec default) & {bar = 2}
+                // ```
+                //
+                // In the example above, if we just map `$rec_default` on the value of `foo` and
+                // closurize it into a new, normal thunk (non revertible), we lose the ability to
+                // override `foo` and we end up with the unexpected result `{foo = 2, bar = 2}`.
+                //
+                // What we want is that:
+                //
+                // ```nickel
+                // {foo = bar + 1, bar = 1} | rec default
+                // ```
+                //
+                // is equivalent to writing:
+                //
+                // ```nickel
+                // {foo | default = bar + 1, bar | default = 1}
+                // ```
+                //
+                // For revertible thunks, we don't want to only map the push operator on the
+                // current cached value, but also on the original expression.
+                //
+                // To do so, we create a new independent copy of the original thunk by mapping the
+                // function over both expressions (in the sense of both the original expression and
+                // the cached expression). This logic is encapsulated by `Thunk::map`.
+                (!is_empty_optional(cache, &rt, env)).then(|| {
+                    let pos = rt.pos;
+
+                    let idx = match rt.as_ref() {
+                        Term::Var(id) => {
+                            let idx = env.get(id).unwrap();
+                            cache.map_at_index(idx, |Closure { ref body, ref env }| Closure {
+                                body: self.apply_rec_prio_op(body.clone()),
+                                env: env.clone(),
+                            })
+                        }
+                        _ => cache.add(
+                            Closure {
+                                body: self.apply_rec_prio_op(rt),
+                                env: env.clone(),
+                            },
+                            eval::IdentKind::Record,
+                            crate::term::BindingType::Normal,
+                        ),
+                    };
 
-            let fresh_id = Ident::fresh();
-            new_env.insert(fresh_id, thunk);
-            RichTerm::new(Term::Var(fresh_id), pos)
-        });
+                    let fresh_id = Ident::fresh();
+                    new_env.insert(fresh_id, idx);
+                    (id, RichTerm::new(Term::Var(fresh_id), pos))
+                })
+            })
+            .collect();
 
         Closure {
             body: RichTerm::new(Term::Record(record), pos),
@@ -2884,7 +2925,13 @@ impl RecPriority {
     ///
     /// - `st` must represent an evaluated term (a weak head normal form), that is `st.is_whnf()`
     ///   must be true. Otherwise, this function panics
-    fn propagate_in_term(&self, st: SharedTerm, env: Environment, pos: TermPos) -> Closure {
+    fn propagate_in_term<C: Cache>(
+        &self,
+        cache: &mut C,
+        st: SharedTerm,
+        env: Environment,
+        pos: TermPos,
+    ) -> Closure {
         let update_priority = |meta: &mut MetaValue| {
             if let MergePriority::Neutral = meta.priority {
                 meta.priority = (*self).into();
@@ -2894,7 +2941,7 @@ impl RecPriority {
         let t = st.into_owned();
 
         if let Term::Record(record) = t {
-            self.propagate_in_record(record, &env, pos)
+            self.propagate_in_record(cache, record, &env, pos)
         } else {
             // Extract the metavalue, or if `st` isn't a metavalue, wrap it in a new one to set the merge
             // priority.
@@ -2906,7 +2953,7 @@ impl RecPriority {
                     let rt = RichTerm::new(t, pos);
 
                     if crate::transform::share_normal_form::should_share(rt.as_ref()) {
-                        meta.value = Some(rt.closurize(&mut new_env, env));
+                        meta.value = Some(rt.closurize(cache, &mut new_env, env));
                     } else {
                         meta.value = Some(rt);
                     }
@@ -2919,7 +2966,7 @@ impl RecPriority {
                 // The term is expected to be forced before calling to rec_priority, which means that
                 // inner is either a simple value, or a thunk containing a weak head normal form.
                 let (inner, env_inner) = if let Term::Var(id) = inner.as_ref() {
-                    let closure = env.get(id).unwrap().get_owned();
+                    let closure = cache.get(env.get(id).unwrap().clone());
                     (closure.body, closure.env)
                 } else {
                     (inner, env.clone())
@@ -2932,13 +2979,13 @@ impl RecPriority {
                         let Closure {
                             body,
                             env: record_env,
-                        } = self.propagate_in_record(record, &env_inner, pos_inner);
-                        meta.value = Some(body.closurize(&mut env, record_env));
+                        } = self.propagate_in_record(cache, record, &env_inner, pos_inner);
+                        meta.value = Some(body.closurize(cache, &mut env, record_env));
                     }
                     t if t.is_whnf() => {
                         update_priority(&mut meta);
                         meta.value =
-                            Some(RichTerm::new(t, pos_inner).closurize(&mut env, env_inner));
+                            Some(RichTerm::new(t, pos_inner).closurize(cache, &mut env, env_inner));
                     }
                     _ => panic!("rec_priority: expected an evaluated form"),
                 }
@@ -2965,7 +3012,7 @@ impl RecPriority {
 ///
 /// Return either a boolean when the equality can be computed directly, or a new non-empty list of
 /// equalities to be checked if operands are composite values.
-fn eq(env: &mut Environment, c1: Closure, c2: Closure) -> EqResult {
+fn eq<C: Cache>(cache: &mut C, env: &mut Environment, c1: Closure, c2: Closure) -> EqResult {
     let Closure {
         body: RichTerm { term: t1, .. },
         env: env1,
@@ -2977,7 +3024,8 @@ fn eq(env: &mut Environment, c1: Closure, c2: Closure) -> EqResult {
 
     // Take a list of subequalities, and either return `EqResult::Bool(true)` if it is empty, or
     // generate an approriate `EqResult::Eqs` variant with closurized terms in it.
-    fn gen_eqs<I>(
+    fn gen_eqs<I, C: Cache>(
+        cache: &mut C,
         mut it: I,
         env: &mut Environment,
         env1: Environment,
@@ -3002,7 +3050,11 @@ fn eq(env: &mut Environment, c1: Closure, c2: Closure) -> EqResult {
                 })
                 .collect();
 
-            EqResult::Eqs(t1.closurize(env, env1), t2.closurize(env, env2), eqs)
+            EqResult::Eqs(
+                t1.closurize(cache, env, env1),
+                t2.closurize(cache, env, env2),
+                eqs,
+            )
         } else {
             EqResult::Bool(true)
         }
@@ -3024,15 +3076,15 @@ fn eq(env: &mut Environment, c1: Closure, c2: Closure) -> EqResult {
             } = merge::hashmap::split(r1.fields, r2.fields);
 
             // As for other record operations, we ignore optional fields without a definition.
-            if !left.values().all(|rt| is_empty_optional(rt, &env1))
-                || !right.values().all(|rt| is_empty_optional(rt, &env2))
+            if !left.values().all(|rt| is_empty_optional(cache, rt, &env1))
+                || !right.values().all(|rt| is_empty_optional(cache, rt, &env2))
             {
                 EqResult::Bool(false)
             } else if center.is_empty() {
                 EqResult::Bool(true)
             } else {
                 let eqs = center.into_iter().map(|(_, (t1, t2))| (t1, t2));
-                gen_eqs(eqs, env, env1, env2)
+                gen_eqs(cache, eqs, env, env1, env2)
             }
         }
         (Term::Array(l1, a1), Term::Array(l2, a2)) if l1.len() == l2.len() => {
@@ -3048,13 +3100,21 @@ fn eq(env: &mut Environment, c1: Closure, c2: Closure) -> EqResult {
                 .into_iter()
                 .map(|t| {
                     let pos = t.pos.into_inherited();
-                    apply_contracts(t, a1.pending_contracts.iter().cloned(), pos)
-                        .closurize(&mut shared_env1, env1.clone())
+                    apply_contracts(t, a1.pending_contracts.iter().cloned(), pos).closurize(
+                        cache,
+                        &mut shared_env1,
+                        env1.clone(),
+                    )
                 })
+                .collect::<Vec<_>>()
+                .into_iter()
                 .zip(l2.into_iter().map(|t| {
                     let pos = t.pos.into_inherited();
-                    apply_contracts(t, a2.pending_contracts.iter().cloned(), pos)
-                        .closurize(&mut shared_env2, env2.clone())
+                    apply_contracts(t, a2.pending_contracts.iter().cloned(), pos).closurize(
+                        cache,
+                        &mut shared_env2,
+                        env2.clone(),
+                    )
                 }))
                 .collect::<Vec<_>>();
 
@@ -3078,8 +3138,8 @@ fn eq(env: &mut Environment, c1: Closure, c2: Closure) -> EqResult {
                         .collect::<Vec<_>>();
 
                     EqResult::Eqs(
-                        t1.closurize(env, shared_env1),
-                        t2.closurize(env, shared_env2),
+                        t1.closurize(cache, env, shared_env1),
+                        t2.closurize(cache, env, shared_env2),
                         eqs,
                     )
                 }
@@ -3090,7 +3150,13 @@ fn eq(env: &mut Environment, c1: Closure, c2: Closure) -> EqResult {
 }
 
 trait RecordDataExt {
-    fn map_fields_without_optionals<F>(self, env: &Environment, f: F) -> Self
+    fn map_fields_without_optionals<F, C: Cache>(
+        self,
+        cache: &mut C,
+        shared_env: &mut Environment,
+        env: &Environment,
+        f: F,
+    ) -> Self
     where
         F: FnMut(Ident, RichTerm) -> RichTerm;
 }
@@ -3098,19 +3164,28 @@ trait RecordDataExt {
 impl RecordDataExt for RecordData {
     /// Returns the record resulting from applying the provided function
     /// to each field, and removing any field which is an empty optional
-    /// in the provided environment.
+    /// in the provided environment. The resulting values are then closurized
+    /// into the shared environment.
     ///
     /// Note that `f` is taken as `mut` in order to allow it to mutate
     /// external state while iterating.
-    fn map_fields_without_optionals<F>(self, env: &Environment, mut f: F) -> Self
+    fn map_fields_without_optionals<F, C: Cache>(
+        self,
+        cache: &mut C,
+        shared_env: &mut Environment,
+        env: &Environment,
+        mut f: F,
+    ) -> Self
     where
         F: FnMut(Ident, RichTerm) -> RichTerm,
     {
         let fields = self
             .fields
             .into_iter()
-            .filter(|(_, t)| !is_empty_optional(t, env))
-            .map(|(id, t)| (id, f(id, t)))
+            .filter_map(|(id, t)| {
+                (!is_empty_optional(cache, &t, env))
+                    .then(|| (id, f(id, t).closurize(cache, shared_env, env.clone())))
+            })
             .collect();
         Self { fields, ..self }
     }
@@ -3120,12 +3195,15 @@ impl RecordDataExt for RecordData {
 mod tests {
     use super::*;
     use crate::cache::resolvers::DummyResolver;
+    use crate::eval::cache::CBNCache;
     use crate::eval::Environment;
 
+    type EC = CBNCache;
+
     #[test]
     fn ite_operation() {
-        let cont = OperationCont::Op1(UnaryOp::Ite(), TermPos::None);
-        let mut vm = VirtualMachine::new(DummyResolver {});
+        let cont: OperationCont = OperationCont::Op1(UnaryOp::Ite(), TermPos::None);
+        let mut vm: VirtualMachine<DummyResolver, EC> = VirtualMachine::new(DummyResolver {});
 
         vm.stack.push_arg(
             Closure::atomic_closure(Term::Num(5.0).into()),
@@ -3204,7 +3282,7 @@ mod tests {
 
     #[test]
     fn plus_second_term_operation() {
-        let cont = OperationCont::Op2Second(
+        let cont: OperationCont = OperationCont::Op2Second(
             BinaryOp::Plus(),
             Closure {
                 body: Term::Num(7.0).into(),
@@ -3214,7 +3292,7 @@ mod tests {
             TermPos::None,
         );
 
-        let mut vm = VirtualMachine::new(DummyResolver {});
+        let mut vm: VirtualMachine<DummyResolver, EC> = VirtualMachine::new(DummyResolver {});
         let mut clos = Closure {
             body: Term::Num(6.0).into(),
             env: Environment::new(),
diff --git a/src/eval/stack.rs b/src/eval/stack.rs
index 498653ab..c3a11596 100644
--- a/src/eval/stack.rs
+++ b/src/eval/stack.rs
@@ -1,14 +1,15 @@
 //! Define the main evaluation stack of the Nickel abstract machine and related operations.
 //!
 //! See [eval](../eval/index.html).
+use super::cache::{Cache, CacheIndex};
 use super::operation::OperationCont;
 use crate::eval::EvalMode;
-use crate::eval::{Closure, Environment, IdentKind, Thunk, ThunkUpdateFrame};
+use crate::eval::{Closure, Environment, IdentKind};
 use crate::position::TermPos;
-use crate::term::{RichTerm, StrChunk};
+use crate::term::{BindingType, RichTerm, StrChunk};
 
 /// An element of the stack.
-pub enum Marker {
+pub enum Marker<C: Cache> {
     /// An equality to test.
     ///
     /// When evaluating one equality `t1 == t2`, the abstract machine may generate several new
@@ -23,9 +24,9 @@ pub enum Marker {
     /// it can be shared with other part of the program.
     ///
     /// In particular, contract arguments are tracked, in order to report the actual, evaluated offending term in case of blame.
-    TrackedArg(Thunk, TermPos),
-    /// A thunk, which is pointer to a mutable memory cell to be updated.
-    Thunk(ThunkUpdateFrame),
+    TrackedArg(CacheIndex, TermPos),
+    /// An update index, which is a pointer to a mutable memory cell to be updated.
+    UpdateIndex(C::UpdateIndex),
     /// The continuation of a primitive operation.
     Cont(
         OperationCont,
@@ -49,13 +50,13 @@ pub enum Marker {
     Strictness(EvalMode),
 }
 
-impl std::fmt::Debug for Marker {
+impl<C: Cache> std::fmt::Debug for Marker<C> {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         match self {
             Marker::Eq(_, _) => write!(f, "Eq"),
             Marker::Arg(_, _) => write!(f, "Arg"),
             Marker::TrackedArg(_, _) => write!(f, "TrackedArg"),
-            Marker::Thunk(_) => write!(f, "Thunk"),
+            Marker::UpdateIndex(_) => write!(f, "UpdateIndex"),
             Marker::Cont(op, sz, _) => write!(f, "Cont {:?} (callstack size {})", op, sz),
             Marker::StrChunk(_) => write!(f, "StrChunk"),
             Marker::StrAcc(_, _, _) => write!(f, "StrAcc"),
@@ -64,13 +65,13 @@ impl std::fmt::Debug for Marker {
     }
 }
 
-impl Marker {
+impl<C: Cache> Marker<C> {
     pub fn is_arg(&self) -> bool {
         matches!(*self, Marker::Arg(..) | Marker::TrackedArg(..))
     }
 
-    pub fn is_thunk(&self) -> bool {
-        matches!(*self, Marker::Thunk(..))
+    pub fn is_idx(&self) -> bool {
+        matches!(*self, Marker::UpdateIndex(..))
     }
 
     pub fn is_cont(&self) -> bool {
@@ -96,26 +97,26 @@ impl Marker {
 
 /// The evaluation stack.
 #[derive(Default)]
-pub struct Stack(Vec<Marker>);
+pub struct Stack<C: Cache>(Vec<Marker<C>>);
 
-impl IntoIterator for Stack {
-    type Item = Marker;
-    type IntoIter = ::std::vec::IntoIter<Marker>;
+impl<C: Cache> IntoIterator for Stack<C> {
+    type Item = Marker<C>;
+    type IntoIter = ::std::vec::IntoIter<Marker<C>>;
 
     fn into_iter(self) -> Self::IntoIter {
         self.0.into_iter()
     }
 }
 
-impl Stack {
-    pub fn new() -> Stack {
+impl<C: Cache> Stack<C> {
+    pub fn new() -> Stack<C> {
         Stack(Vec::new())
     }
 
     /// Count the number of consecutive elements satisfying `pred` from the top of the stack.
     fn count<P>(&self, pred: P) -> usize
     where
-        P: Fn(&Marker) -> bool,
+        P: Fn(&Marker<C>) -> bool,
     {
         let mut count = 0;
         for marker in self.0.iter().rev() {
@@ -129,10 +130,10 @@ impl Stack {
     }
 
     /// Pops all items in the stack and resets the state of the thunks it encounters.
-    pub fn reset(&mut self) {
+    pub fn reset(&mut self, cache: &mut C) {
         while let Some(marker) = self.0.pop() {
-            if let Marker::Thunk(thunk) = marker {
-                thunk.reset_state();
+            if let Marker::UpdateIndex(mut uidx) = marker {
+                cache.reset_index_state(&mut uidx);
             }
         }
     }
@@ -146,12 +147,12 @@ impl Stack {
         self.0.push(Marker::Arg(arg, pos))
     }
 
-    pub fn push_tracked_arg(&mut self, arg_thunk: Thunk, pos: TermPos) {
-        self.0.push(Marker::TrackedArg(arg_thunk, pos))
+    pub fn push_tracked_arg(&mut self, idx: CacheIndex, pos: TermPos) {
+        self.0.push(Marker::TrackedArg(idx, pos))
     }
 
-    pub fn push_thunk(&mut self, thunk: ThunkUpdateFrame) {
-        self.0.push(Marker::Thunk(thunk))
+    pub fn push_update_index(&mut self, uidx: C::UpdateIndex) {
+        self.0.push(Marker::UpdateIndex(uidx))
     }
 
     pub fn push_op_cont(&mut self, cont: OperationCont, len: usize, pos: TermPos) {
@@ -187,10 +188,10 @@ impl Stack {
     /// was not an argument and the stack is left unchanged.
     ///
     /// If the argument is tracked, it is automatically converted into an owned closure.
-    pub fn pop_arg(&mut self) -> Option<(Closure, TermPos)> {
+    pub fn pop_arg(&mut self, cache: &C) -> Option<(Closure, TermPos)> {
         match self.0.pop() {
             Some(Marker::Arg(arg, pos)) => Some((arg, pos)),
-            Some(Marker::TrackedArg(arg_thunk, pos)) => Some((arg_thunk.into_closure(), pos)),
+            Some(Marker::TrackedArg(arg_idx, pos)) => Some((cache.get(arg_idx), pos)),
             Some(m) => {
                 self.0.push(m);
                 None
@@ -199,14 +200,16 @@ impl Stack {
         }
     }
 
-    /// Try to pop an argument from the top of the stack and return it as a thunk. If `None` is
+    /// Try to pop an argument from the top of the stack and return it as an index. If `None` is
     /// returned, the top element was not an argument and the stack is left unchanged.
     ///
     /// If the argument is not tracked, it is directly returned.
-    pub fn pop_arg_as_thunk(&mut self) -> Option<(Thunk, TermPos)> {
+    pub fn pop_arg_as_idx(&mut self, cache: &mut C) -> Option<(CacheIndex, TermPos)> {
         match self.0.pop() {
-            Some(Marker::Arg(arg, pos)) => Some((Thunk::new(arg, IdentKind::Lambda), pos)),
-            Some(Marker::TrackedArg(arg_thunk, pos)) => Some((arg_thunk, pos)),
+            Some(Marker::Arg(arg, pos)) => {
+                Some((cache.add(arg, IdentKind::Lambda, BindingType::Normal), pos))
+            }
+            Some(Marker::TrackedArg(arg_idx, pos)) => Some((arg_idx, pos)),
             Some(m) => {
                 self.0.push(m);
                 None
@@ -215,11 +218,11 @@ impl Stack {
         }
     }
 
-    /// Try to pop a thunk from the top of the stack. If `None` is returned, the top element was
-    /// not a thunk and the stack is left unchanged.
-    pub fn pop_thunk(&mut self) -> Option<ThunkUpdateFrame> {
+    /// Try to pop an index from the top of the stack. If `None` is returned, the top element was
+    /// not an index and the stack is left unchanged.
+    pub fn pop_update_index(&mut self) -> Option<C::UpdateIndex> {
         match self.0.pop() {
-            Some(Marker::Thunk(thunk)) => Some(thunk),
+            Some(Marker::UpdateIndex(uidx)) => Some(uidx),
             Some(m) => {
                 self.0.push(m);
                 None
@@ -246,7 +249,7 @@ impl Stack {
             .0
             .iter()
             .rev()
-            .skip_while(|&marker| matches!(marker, Marker::Thunk(..)));
+            .skip_while(|&marker| matches!(marker, Marker::UpdateIndex(..)));
 
         match it.next() {
             Some(Marker::Cont(cont, _, _)) => Some(cont.clone()),
@@ -305,8 +308,8 @@ impl Stack {
     }
 
     /// Check if the top element is a thunk.
-    pub fn is_top_thunk(&self) -> bool {
-        self.0.last().map(Marker::is_thunk).unwrap_or(false)
+    pub fn is_top_idx(&self) -> bool {
+        self.0.last().map(Marker::is_idx).unwrap_or(false)
     }
 
     /// Check if the top element is an operation continuation.
@@ -322,21 +325,21 @@ impl Stack {
 
     /// Turning the top element of the stack into a tracked arg if it was not already. Returns the
     /// corresponding thunk, or `None` if the top element wasn't an argument.
-    pub fn track_arg(&mut self) -> Option<Thunk> {
+    pub fn track_arg(&mut self, cache: &mut C) -> Option<CacheIndex> {
         match self.0.last_mut() {
-            Some(Marker::TrackedArg(thunk, _)) => Some(thunk.clone()),
+            Some(Marker::TrackedArg(idx, _)) => Some(idx.clone()),
             Some(Marker::Arg(..)) => {
-                let (closure, pos) = self.pop_arg().unwrap();
-                let thunk = Thunk::new(closure, IdentKind::Lambda);
-                self.push_tracked_arg(thunk.clone(), pos);
-                Some(thunk)
+                let (closure, pos) = self.pop_arg(cache).unwrap();
+                let idx = cache.add(closure, IdentKind::Lambda, BindingType::Normal);
+                self.push_tracked_arg(idx.clone(), pos);
+                Some(idx)
             }
             _ => None,
         }
     }
 }
 
-impl std::fmt::Debug for Stack {
+impl<C: Cache> std::fmt::Debug for Stack<C> {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         writeln!(f, "--- STACK ---")?;
         for marker in self.0.iter().rev() {
@@ -349,14 +352,16 @@ impl std::fmt::Debug for Stack {
 #[cfg(test)]
 mod tests {
     use super::*;
-    use crate::eval::{IdentKind, Thunk};
+    use crate::eval::{cache::CBNCache, IdentKind, Thunk};
     use crate::term::{Term, UnaryOp};
     use assert_matches::assert_matches;
 
-    impl Stack {
+    type EC = CBNCache;
+
+    impl Stack<EC> {
         /// Count the number of thunks at the top of the stack.
         pub fn count_thunks(&self) -> usize {
-            Stack::count(self, Marker::is_thunk)
+            Stack::count(self, Marker::is_idx)
         }
 
         /// Count the number of operation continuation at the top of the stack.
@@ -373,23 +378,23 @@ mod tests {
         OperationCont::Op1(UnaryOp::Typeof(), TermPos::None)
     }
 
-    fn some_arg_marker() -> Marker {
+    fn some_arg_marker() -> Marker<EC> {
         Marker::Arg(some_closure(), TermPos::None)
     }
 
-    fn some_thunk_marker() -> Marker {
+    fn some_thunk_marker() -> Marker<EC> {
         let mut thunk = Thunk::new(some_closure(), IdentKind::Let);
-        Marker::Thunk(thunk.mk_update_frame().unwrap())
+        Marker::UpdateIndex(thunk.mk_update_frame().unwrap())
     }
 
-    fn some_cont_marker() -> Marker {
+    fn some_cont_marker() -> Marker<EC> {
         Marker::Cont(some_cont(), 42, TermPos::None)
     }
 
     #[test]
     fn marker_differentiates() {
         assert!(some_arg_marker().is_arg());
-        assert!(some_thunk_marker().is_thunk());
+        assert!(some_thunk_marker().is_idx());
         assert!(some_cont_marker().is_cont());
     }
 
@@ -401,7 +406,10 @@ mod tests {
         s.push_arg(some_closure(), TermPos::None);
         s.push_arg(some_closure(), TermPos::None);
         assert_eq!(2, s.count_args());
-        assert_eq!(some_closure(), s.pop_arg().expect("Already checked").0);
+        assert_eq!(
+            some_closure(),
+            s.pop_arg(&CBNCache {}).expect("Already checked").0
+        );
         assert_eq!(1, s.count_args());
     }
 
@@ -411,12 +419,13 @@ mod tests {
         assert_eq!(0, s.count_thunks());
 
         let mut thunk = Thunk::new(some_closure(), IdentKind::Let);
-        s.push_thunk(thunk.mk_update_frame().unwrap());
+        s.push_update_index(thunk.mk_update_frame().unwrap());
+        // TODO: This is not generic
         thunk = Thunk::new(some_closure(), IdentKind::Let);
-        s.push_thunk(thunk.mk_update_frame().unwrap());
+        s.push_update_index(thunk.mk_update_frame().unwrap());
 
         assert_eq!(2, s.count_thunks());
-        s.pop_thunk().expect("Already checked");
+        s.pop_update_index().expect("Already checked");
         assert_eq!(1, s.count_thunks());
     }
 
@@ -448,6 +457,7 @@ mod tests {
     #[test]
     fn pushing_and_poping_strictness_markers() {
         let mut s = Stack::new();
+        let cache = CBNCache {};
         assert_eq!(0, s.count_args());
 
         s.push_strictness(EvalMode::UnwrapMeta);
@@ -460,9 +470,9 @@ mod tests {
 
         assert_eq!(s.pop_strictness_marker(), Some(EvalMode::StopAtMeta));
         assert_eq!(2, s.count_args());
-        assert_matches!(s.pop_arg(), Some(..));
-        assert_matches!(s.pop_arg(), Some(..));
-        assert_eq!(s.pop_arg(), None);
+        assert_matches!(s.pop_arg(&cache), Some(..));
+        assert_matches!(s.pop_arg(&cache), Some(..));
+        assert_eq!(s.pop_arg(&cache), None);
         assert_eq!(0, s.count_args());
         assert_eq!(s.pop_strictness_marker(), Some(EvalMode::UnwrapMeta));
         assert_eq!(0, s.count_args());
diff --git a/src/label.rs b/src/label.rs
index 85f9dd19..7e6b9d1b 100644
--- a/src/label.rs
+++ b/src/label.rs
@@ -4,7 +4,7 @@
 //! information about the context of a contract failure.
 use std::rc::Rc;
 
-use crate::eval::lazy::Thunk;
+use crate::eval::cache::CacheIndex;
 use crate::position::{RawSpan, TermPos};
 use crate::types::{TypeF, Types};
 use codespan::Files;
@@ -246,8 +246,8 @@ pub struct Label {
     pub tag: String,
     /// The position of the original contract.
     pub span: RawSpan,
-    /// The thunk corresponding to the value being checked. Set at run-time by the interpreter.
-    pub arg_thunk: Option<Thunk>,
+    /// The index corresponding to the value being checked. Set at run-time by the interpreter.
+    pub arg_idx: Option<CacheIndex>,
     /// The original position of the value being checked. Set at run-time by the interpreter.
     pub arg_pos: TermPos,
     /// The polarity, used for higher-order contracts, that specifies if the current contract is
@@ -268,7 +268,7 @@ impl Label {
                 start: 0.into(),
                 end: 1.into(),
             },
-            arg_thunk: None,
+            arg_idx: None,
             arg_pos: TermPos::None,
             polarity: true,
             path: Vec::new(),
@@ -286,7 +286,7 @@ impl Default for Label {
                 start: 0.into(),
                 end: 1.into(),
             },
-            arg_thunk: None,
+            arg_idx: None,
             arg_pos: TermPos::None,
             polarity: true,
             path: Vec::new(),
diff --git a/src/parser/utils.rs b/src/parser/utils.rs
index eaa6a747..618acda5 100644
--- a/src/parser/utils.rs
+++ b/src/parser/utils.rs
@@ -419,7 +419,7 @@ pub fn mk_label(types: Types, src_id: FileId, l: usize, r: usize) -> Label {
         types: Rc::new(types),
         tag: String::new(),
         span: mk_span(src_id, l, r),
-        arg_thunk: None,
+        arg_idx: None,
         arg_pos: TermPos::None,
         polarity: true,
         path: Vec::new(),
diff --git a/src/program.rs b/src/program.rs
index f1151184..0474faa4 100644
--- a/src/program.rs
+++ b/src/program.rs
@@ -22,6 +22,7 @@
 //! Each such value is added to the initial environment before the evaluation of the program.
 use crate::cache::*;
 use crate::error::{Error, ToDiagnostic};
+use crate::eval::cache::Cache as EvalCache;
 use crate::eval::VirtualMachine;
 use crate::identifier::Ident;
 use crate::parser::lexer::Lexer;
@@ -37,29 +38,29 @@ use std::result::Result;
 ///
 /// Manage a file database, which stores the original source code of the program and eventually the
 /// code of imported expressions, and a dictionary which stores corresponding parsed terms.
-pub struct Program {
+pub struct Program<EC: EvalCache> {
     /// The id of the program source in the file database.
     main_id: FileId,
     /// The state of the Nickel virtual machine.
-    vm: VirtualMachine<Cache>,
+    vm: VirtualMachine<Cache, EC>,
 }
 
-impl Program {
+impl<EC: EvalCache> Program<EC> {
     /// Create a program by reading it from the standard input.
-    pub fn new_from_stdin() -> std::io::Result<Program> {
+    pub fn new_from_stdin() -> std::io::Result<Self> {
         Program::new_from_source(io::stdin(), "<stdin>")
     }
 
-    pub fn new_from_file(path: impl Into<OsString>) -> std::io::Result<Program> {
+    pub fn new_from_file(path: impl Into<OsString>) -> std::io::Result<Self> {
         let mut cache = Cache::new(ErrorTolerance::Strict);
         let main_id = cache.add_file(path)?;
         let vm = VirtualMachine::new(cache);
 
-        Ok(Program { main_id, vm })
+        Ok(Self { main_id, vm })
     }
 
     /// Create a program by reading it from a generic source.
-    pub fn new_from_source<T, S>(source: T, source_name: S) -> std::io::Result<Program>
+    pub fn new_from_source<T, S>(source: T, source_name: S) -> std::io::Result<Self>
     where
         T: Read,
         S: Into<OsString> + Clone,
@@ -68,23 +69,13 @@ impl Program {
         let main_id = cache.add_source(source_name, source)?;
         let vm = VirtualMachine::new(cache);
 
-        Ok(Program { main_id, vm })
+        Ok(Self { main_id, vm })
     }
 
     /// Retrieve the parsed term and typecheck it, and generate a fresh initial environment. Return
     /// both.
     fn prepare_eval(&mut self) -> Result<(RichTerm, eval::Environment), Error> {
-        let Envs {
-            eval_env,
-            type_ctxt,
-        } = self.vm.import_resolver_mut().prepare_stdlib()?;
-        self.vm
-            .import_resolver_mut()
-            .prepare(self.main_id, &type_ctxt)?;
-        Ok((
-            self.vm.import_resolver().get(self.main_id).unwrap(),
-            eval_env,
-        ))
+        self.vm.prepare_eval(self.main_id)
     }
 
     /// Parse if necessary, typecheck and then evaluate the program.
@@ -110,7 +101,7 @@ impl Program {
 
     /// Wrapper for [`query`].
     pub fn query(&mut self, path: Option<String>) -> Result<Term, Error> {
-        let initial_env = self.vm.import_resolver_mut().prepare_stdlib()?;
+        let initial_env = self.vm.prepare_stdlib()?;
         query(&mut self.vm, self.main_id, &initial_env, path)
     }
 
@@ -191,8 +182,8 @@ impl Program {
 //would additionally report `type: Num` for example.
 //TODO: not sure where this should go. It seems to embed too much logic to be in `Cache`, but is
 //common to both `Program` and `Repl`. Leaving it here as a stand-alone function for now
-pub fn query(
-    vm: &mut VirtualMachine<Cache>,
+pub fn query<EC: EvalCache>(
+    vm: &mut VirtualMachine<Cache, EC>,
     file_id: FileId,
     initial_env: &Envs,
     path: Option<String>,
@@ -210,13 +201,15 @@ pub fn query(
 
         // Substituting `y` for `t`
         let mut env = eval::Environment::new();
+        let rt = vm.import_resolver().get_owned(file_id).unwrap();
         eval::env_add(
+            &mut vm.cache,
             &mut env,
             Ident::from("x"),
-            vm.import_resolver().get_owned(file_id).unwrap(),
+            rt,
             eval::Environment::new(),
         );
-        eval::subst(new_term, &eval::Environment::new(), &env)
+        eval::subst(&vm.cache, new_term, &eval::Environment::new(), &env)
     } else {
         vm.import_resolver().get_owned(file_id).unwrap()
     };
@@ -372,15 +365,18 @@ mod doc {
 mod tests {
     use super::*;
     use crate::error::EvalError;
+    use crate::eval::cache::CBNCache;
     use crate::position::TermPos;
     use crate::term::ArrayAttrs;
     use assert_matches::assert_matches;
     use std::io::Cursor;
 
+    type EC = CBNCache;
+
     fn eval_full(s: &str) -> Result<RichTerm, Error> {
         let src = Cursor::new(s);
 
-        let mut p = Program::new_from_source(src, "<test>").map_err(|io_err| {
+        let mut p: Program<EC> = Program::new_from_source(src, "<test>").map_err(|io_err| {
             Error::EvalError(EvalError::Other(
                 format!("IO error: {}", io_err),
                 TermPos::None,
@@ -392,7 +388,7 @@ mod tests {
     fn typecheck(s: &str) -> Result<(), Error> {
         let src = Cursor::new(s);
 
-        let mut p = Program::new_from_source(src, "<test>").map_err(|io_err| {
+        let mut p: Program<EC> = Program::new_from_source(src, "<test>").map_err(|io_err| {
             Error::EvalError(EvalError::Other(
                 format!("IO error: {}", io_err),
                 TermPos::None,
diff --git a/src/repl/mod.rs b/src/repl/mod.rs
index 325c690b..e56a50c7 100644
--- a/src/repl/mod.rs
+++ b/src/repl/mod.rs
@@ -8,6 +8,7 @@
 //! formatting), etc.
 use crate::cache::{Cache, Envs, ErrorTolerance};
 use crate::error::{Error, EvalError, IOError, ParseError, ParseErrors, ReplError};
+use crate::eval::cache::Cache as EvalCache;
 use crate::eval::VirtualMachine;
 use crate::identifier::Ident;
 use crate::parser::{grammar, lexer, ExtendedTerm};
@@ -67,7 +68,7 @@ pub trait Repl {
 }
 
 /// Standard implementation of the REPL backend.
-pub struct ReplImpl {
+pub struct ReplImpl<EC: EvalCache> {
     /// The parser, supporting toplevel let declaration.
     parser: grammar::ExtendedTermParser,
     /// The current environment (for evaluation and typing). Contain the initial environment with
@@ -77,10 +78,10 @@ pub struct ReplImpl {
     /// typecheck imports in a fresh environment.
     initial_type_ctxt: typecheck::Context,
     /// The state of the Nickel virtual machine, holding a cache of loaded files and parsed terms.
-    vm: VirtualMachine<Cache>,
+    vm: VirtualMachine<Cache, EC>,
 }
 
-impl ReplImpl {
+impl<EC: EvalCache> ReplImpl<EC> {
     /// Create a new empty REPL.
     pub fn new() -> Self {
         ReplImpl {
@@ -94,7 +95,7 @@ impl ReplImpl {
     /// Load and process the stdlib, and use it to populate the eval environment as well as the
     /// typing environment.
     pub fn load_stdlib(&mut self) -> Result<(), Error> {
-        self.env = self.vm.import_resolver_mut().prepare_stdlib()?;
+        self.env = self.vm.prepare_stdlib()?;
         self.initial_type_ctxt = self.env.type_ctxt.clone();
         Ok(())
     }
@@ -126,8 +127,8 @@ impl ReplImpl {
         // `id` must be set to `None` for normal lets and to `Some(id_)` for top-level lets. In the
         // latter case, we need to update the current type environment before doing program
         // transformations in the case of a top-level let.
-        fn prepare(
-            repl_impl: &mut ReplImpl,
+        fn prepare<EC: EvalCache>(
+            repl_impl: &mut ReplImpl<EC>,
             id: Option<Ident>,
             t: RichTerm,
         ) -> Result<RichTerm, Error> {
@@ -194,14 +195,14 @@ impl ReplImpl {
             ExtendedTerm::ToplevelLet(id, t) => {
                 let t = prepare(self, Some(id), t)?;
                 let local_env = self.env.eval_env.clone();
-                eval::env_add(&mut self.env.eval_env, id, t, local_env);
+                eval::env_add(&mut self.vm.cache, &mut self.env.eval_env, id, t, local_env);
                 Ok(EvalResult::Bound(id))
             }
         }
     }
 }
 
-impl Repl for ReplImpl {
+impl<EC: EvalCache> Repl for ReplImpl<EC> {
     fn eval(&mut self, exp: &str) -> Result<EvalResult, Error> {
         self.eval_(exp, false)
     }
@@ -249,7 +250,7 @@ impl Repl for ReplImpl {
             self.vm.import_resolver(),
         )
         .unwrap();
-        eval::env_add_term(&mut self.env.eval_env, term.clone()).unwrap();
+        eval::env_add_term(&mut self.vm.cache, &mut self.env.eval_env, term.clone()).unwrap();
 
         Ok(term)
     }
diff --git a/src/repl/rustyline_frontend.rs b/src/repl/rustyline_frontend.rs
index 0898ccd8..1a9d86fc 100644
--- a/src/repl/rustyline_frontend.rs
+++ b/src/repl/rustyline_frontend.rs
@@ -21,7 +21,7 @@ pub fn config() -> Config {
 
 /// Main loop of the REPL.
 pub fn repl(histfile: PathBuf) -> Result<(), InitError> {
-    let mut repl = ReplImpl::new();
+    let mut repl = ReplImpl::<crate::eval::cache::CBNCache>::new();
 
     match repl.load_stdlib() {
         Ok(()) => (),
diff --git a/src/repl/simple_frontend.rs b/src/repl/simple_frontend.rs
index bf3781cf..1ea8f2ed 100644
--- a/src/repl/simple_frontend.rs
+++ b/src/repl/simple_frontend.rs
@@ -29,7 +29,7 @@ impl From<Error> for InputError {
 }
 
 /// Return a new instance of an REPL with the standard library loaded.
-pub fn init() -> Result<ReplImpl, Error> {
+pub fn init<EC: EvalCache>() -> Result<ReplImpl<EC>, Error> {
     let mut repl = ReplImpl::new();
     repl.load_stdlib()?;
     Ok(repl)
diff --git a/src/repl/wasm_frontend.rs b/src/repl/wasm_frontend.rs
index 05e41999..c83c97b6 100644
--- a/src/repl/wasm_frontend.rs
+++ b/src/repl/wasm_frontend.rs
@@ -3,6 +3,7 @@ use super::simple_frontend::{input, serialize, InputError, InputResult};
 use super::{Repl, ReplImpl};
 use crate::cache::Cache;
 use crate::error::ToDiagnostic;
+use crate::eval::cache::CBNCache;
 use crate::serialize::ExportFormat;
 use codespan::{FileId, Files};
 use codespan_reporting::{
@@ -243,7 +244,7 @@ impl From<InputResult> for WasmInputResult {
 
 /// WASM-compatible wrapper around `ReplImpl`.
 #[wasm_bindgen]
-pub struct ReplState(ReplImpl);
+pub struct ReplState(ReplImpl<CBNCache>);
 
 /// WASM-compatible wrapper around `serialize::ExportFormat`.
 #[wasm_bindgen]
diff --git a/src/serialize.rs b/src/serialize.rs
index f8fd2b66..a2c2f138 100644
--- a/src/serialize.rs
+++ b/src/serialize.rs
@@ -1,7 +1,11 @@
 //! Serialization of an evaluated program to various data format.
 use crate::{
     error::SerializationError,
-    eval::{self, is_empty_optional},
+    eval::{
+        self,
+        cache::{CBNCache, Cache},
+        is_empty_optional,
+    },
     term::{array::Array, record::RecordData, ArrayAttrs, MetaValue, RichTerm, Term},
 };
 
@@ -105,7 +109,7 @@ where
         .iter()
         // Filtering out optional fields without a definition. All variable should have been
         // substituted at this point, so we pass an empty environment.
-        .filter(|(_, t)| !is_empty_optional(t, &eval::Environment::new()))
+        .filter(|(_, t)| !is_empty_optional(&CBNCache {}, t, &eval::Environment::new()))
         .collect();
     entries.sort_by_key(|(k, _)| *k);
 
@@ -174,6 +178,7 @@ impl<'de> Deserialize<'de> for RichTerm {
 
 /// Check that a term is serializable. Serializable terms are booleans, numbers, strings, enum,
 /// arrays of serializable terms or records of serializable terms.
+/// TODO: We should have a NoCache impl of Cache or adapt the signature of [is_empty_optional()]
 pub fn validate(format: ExportFormat, t: &RichTerm) -> Result<(), SerializationError> {
     use crate::term;
     use Term::*;
@@ -206,7 +211,8 @@ pub fn validate(format: ExportFormat, t: &RichTerm) -> Result<(), SerializationE
                 value: Some(ref t), ..
             }) => validate(format, t),
             // Optional field without definition are accepted and ignored during serialization.
-            _ if is_empty_optional(t, &eval::Environment::new()) => Ok(()),
+            // TODO: This shouldn't spin a new cache
+            _ if is_empty_optional(&CBNCache::new(), t, &eval::Environment::new()) => Ok(()),
             _ => Err(SerializationError::NonSerializable(t.clone())),
         }
     }
@@ -267,14 +273,16 @@ mod tests {
     use super::*;
     use crate::cache::resolvers::DummyResolver;
     use crate::error::{Error, EvalError};
-    use crate::eval::{Environment, VirtualMachine};
+    use crate::eval::{cache::CBNCache, Environment, VirtualMachine};
     use crate::position::TermPos;
     use crate::program::Program;
     use crate::term::{make as mk_term, BinaryOp};
     use serde_json::json;
     use std::io::Cursor;
 
-    fn mk_program(s: &str) -> Result<Program, Error> {
+    type EC = CBNCache;
+
+    fn mk_program(s: &str) -> Result<Program<EC>, Error> {
         let src = Cursor::new(s);
 
         Program::new_from_source(src, "<test>").map_err(|io_err| {
@@ -330,7 +338,7 @@ mod tests {
                     .unwrap();
 
             assert_eq!(
-                VirtualMachine::new(DummyResolver {})
+                VirtualMachine::<_, EC>::new(DummyResolver {})
                     .eval(
                         mk_term::op2(BinaryOp::Eq(), from_json, evaluated.clone()),
                         &Environment::new(),
@@ -339,7 +347,7 @@ mod tests {
                 Ok(Term::Bool(true))
             );
             assert_eq!(
-                VirtualMachine::new(DummyResolver {})
+                VirtualMachine::<_, EC>::new(DummyResolver {})
                     .eval(
                         mk_term::op2(BinaryOp::Eq(), from_yaml, evaluated.clone()),
                         &Environment::new(),
@@ -348,7 +356,7 @@ mod tests {
                 Ok(Term::Bool(true))
             );
             assert_eq!(
-                VirtualMachine::new(DummyResolver {})
+                VirtualMachine::<_, EC>::new(DummyResolver {})
                     .eval(
                         mk_term::op2(BinaryOp::Eq(), from_toml, evaluated),
                         &Environment::new(),
diff --git a/src/transform/mod.rs b/src/transform/mod.rs
index 3bd0c987..4e7152c8 100644
--- a/src/transform/mod.rs
+++ b/src/transform/mod.rs
@@ -1,9 +1,9 @@
 //! Various post transformations of nickel code.
 use crate::{
     cache::ImportResolver,
-    eval::{lazy::Thunk, Closure, Environment, IdentKind},
+    eval::{cache::Cache, Closure, Environment, IdentKind},
     identifier::Ident,
-    term::{Contract, RichTerm, Term, TraverseOrder},
+    term::{BindingType, Contract, RichTerm, Term, TraverseOrder},
     typecheck::Wildcards,
     types::{TypeF, Types, UnboundTypeVariableError},
 };
@@ -70,7 +70,12 @@ pub fn transform_no_free_vars(
 pub trait Closurizable {
     /// Pack a closurizable together with its environment `with_env` as a closure in the main
     /// environment `env`.
-    fn closurize(self, env: &mut Environment, with_env: Environment) -> Self;
+    fn closurize<C: Cache>(
+        self,
+        cache: &mut C,
+        env: &mut Environment,
+        with_env: Environment,
+    ) -> Self;
 }
 
 impl Closurizable for RichTerm {
@@ -78,7 +83,12 @@ impl Closurizable for RichTerm {
     ///
     /// Generate a fresh variable, bind it to the corresponding closure `(t,with_env)` in `env`,
     /// and return this variable as a fresh term.
-    fn closurize(self, env: &mut Environment, with_env: Environment) -> RichTerm {
+    fn closurize<C: Cache>(
+        self,
+        cache: &mut C,
+        env: &mut Environment,
+        with_env: Environment,
+    ) -> RichTerm {
         // If the term is already a variable, we don't have to create a useless intermediate
         // closure. We just transfer the original thunk to the new environment. This is not only an
         // optimization: this is relied upon by recursive record merging when computing the
@@ -125,7 +135,7 @@ impl Closurizable for RichTerm {
         let var = Ident::fresh();
         let pos = self.pos;
 
-        let thunk = match self.as_ref() {
+        let idx = match self.as_ref() {
             Term::Var(id) if id.is_generated() => with_env.get(id).cloned().unwrap_or_else(|| {
                 panic!(
                 "Internal error(closurize) : generated identifier {} not found in the environment",
@@ -133,15 +143,15 @@ impl Closurizable for RichTerm {
             )
             }),
             _ => {
-                let closure = Closure {
+                let closure: Closure = Closure {
                     body: self,
                     env: with_env,
                 };
-                Thunk::new(closure, IdentKind::Record)
+                cache.add(closure, IdentKind::Record, BindingType::Normal)
             }
         };
 
-        env.insert(var, thunk);
+        env.insert(var, idx);
         RichTerm::new(Term::Var(var), pos.into_inherited())
     }
 }
@@ -151,17 +161,27 @@ impl Closurizable for Types {
     ///
     /// Extract the underlying contract, closurize it and wrap it back as a flat type (an opaque
     /// type defined by a custom contract).
-    fn closurize(self, env: &mut Environment, with_env: Environment) -> Types {
+    fn closurize<C: Cache>(
+        self,
+        cache: &mut C,
+        env: &mut Environment,
+        with_env: Environment,
+    ) -> Types {
         Types(TypeF::Flat(
-            self.contract().unwrap().closurize(env, with_env),
+            self.contract().unwrap().closurize(cache, env, with_env),
         ))
     }
 }
 
 impl Closurizable for Contract {
-    fn closurize(self, env: &mut Environment, with_env: Environment) -> Contract {
+    fn closurize<C: Cache>(
+        self,
+        cache: &mut C,
+        env: &mut Environment,
+        with_env: Environment,
+    ) -> Contract {
         Contract {
-            types: self.types.closurize(env, with_env),
+            types: self.types.closurize(cache, env, with_env),
             label: self.label,
         }
     }
diff --git a/src/typecheck/eq.rs b/src/typecheck/eq.rs
index 1e8fb0b8..67a6baf9 100644
--- a/src/typecheck/eq.rs
+++ b/src/typecheck/eq.rs
@@ -43,7 +43,10 @@
 //! times. For anything more complex, we return false.
 
 use super::*;
-use crate::{eval, term::UnaryOp};
+use crate::{
+    eval::{self, cache::Cache},
+    term::UnaryOp,
+};
 
 /// The maximal number of variable links we want to unfold before abandoning the check. It should
 /// stay low, but has been fixed arbitrarily: feel fee to increase reasonably if it turns out
@@ -95,7 +98,8 @@ impl std::iter::FromIterator<(Ident, (RichTerm, SimpleTermEnvironment))> for Sim
     }
 }
 
-impl TermEnvironment for eval::Environment {
+/*
+impl<C: Cache> TermEnvironment for eval::Environment {
     fn get_then<F, T>(&self, id: &Ident, f: F) -> T
     where
         F: FnOnce(Option<(&RichTerm, &eval::Environment)>) -> T,
@@ -106,20 +110,21 @@ impl TermEnvironment for eval::Environment {
         }
     }
 }
+*/
 
-impl From<eval::Environment> for SimpleTermEnvironment {
-    fn from(eval_env: eval::Environment) -> Self {
+pub trait FromEnv<C: Cache> {
+    fn from_env(eval_env: eval::Environment, cache: &C) -> Self;
+}
+
+impl<C: Cache> FromEnv<C> for SimpleTermEnvironment {
+    fn from_env(eval_env: eval::Environment, cache: &C) -> Self {
         let generic_env: GenericEnvironment<_, _> = eval_env
             .iter_elems()
-            .map(|(id, thunk)| {
-                let borrowed = thunk.borrow();
-                (
-                    *id,
-                    (
-                        borrowed.body.clone(),
-                        SimpleTermEnvironment::from(borrowed.env.clone()),
-                    ),
-                )
+            .map(|(id, idx)| {
+                let borrowed = cache.get_then(idx.clone(), |c| {
+                    (c.body.clone(), Self::from_env(c.env.clone(), cache))
+                });
+                (*id, borrowed)
             })
             .collect();
         SimpleTermEnvironment(generic_env)
diff --git a/utilities/src/lib.rs b/utilities/src/lib.rs
index 05e90e44..1e7bdf69 100644
--- a/utilities/src/lib.rs
+++ b/utilities/src/lib.rs
@@ -4,7 +4,10 @@ use criterion::Criterion;
 use nickel_lang::{
     cache::{Cache, Envs, ErrorTolerance},
     error::{Error, ParseError},
-    eval::VirtualMachine,
+    eval::{
+        cache::{CBNCache, Cache as EvalCache},
+        VirtualMachine,
+    },
     parser::{grammar, lexer},
     program::Program,
     term::{RichTerm, Term},
@@ -13,13 +16,16 @@ use nickel_lang::{
 
 use std::{io::Cursor, path::PathBuf};
 
+pub type EC = CBNCache;
+pub type TestProgram = Program<EC>;
+
 pub fn eval(s: impl std::string::ToString) -> Result<Term, Error> {
-    let mut p = Program::new_from_source(Cursor::new(s.to_string()), "test").unwrap();
+    let mut p = Program::<EC>::new_from_source(Cursor::new(s.to_string()), "test").unwrap();
     p.eval().map(Term::from)
 }
 
 pub fn eval_file(f: &str) -> Result<Term, Error> {
-    let mut p = program_from_test_fixture(f);
+    let mut p: Program<EC> = program_from_test_fixture(f);
     p.eval().map(Term::from)
 }
 
@@ -32,11 +38,11 @@ pub fn parse(s: &str) -> Result<RichTerm, ParseError> {
 }
 
 pub fn typecheck_fixture(f: &str) -> Result<(), Error> {
-    let mut p = program_from_test_fixture(f);
+    let mut p: Program<EC> = program_from_test_fixture(f);
     p.typecheck()
 }
 
-fn program_from_test_fixture(f: &str) -> Program {
+fn program_from_test_fixture(f: &str) -> Program<EC> {
     let path = format!("{}/../tests/integration/{}", env!("CARGO_MANIFEST_DIR"), f);
     Program::new_from_file(&path)
         .unwrap_or_else(|e| panic!("Could not create program from `{}`\n {}", path, e))
@@ -127,10 +133,11 @@ impl<'b> Bench<'b> {
 
 pub fn bench_terms<'r>(rts: Vec<Bench<'r>>) -> Box<dyn Fn(&mut Criterion) + 'r> {
     let mut cache = Cache::new(ErrorTolerance::Strict);
+    let mut eval_cache = EC::new();
     let Envs {
         eval_env,
         type_ctxt,
-    } = cache.prepare_stdlib().unwrap();
+    } = cache.prepare_stdlib(&mut eval_cache).unwrap();
     Box::new(move |c: &mut Criterion| {
         rts.iter().for_each(|bench| {
             let t = bench.term();
@@ -148,7 +155,9 @@ pub fn bench_terms<'r>(rts: Vec<Bench<'r>>) -> Box<dyn Fn(&mut Criterion) + 'r>
                             c_local.typecheck(id, &type_ctxt).unwrap();
                         } else {
                             c_local.prepare(id, &type_ctxt).unwrap();
-                            VirtualMachine::new(c_local).eval(t, &eval_env).unwrap();
+                            VirtualMachine::new_with_cache(c_local, eval_cache.clone())
+                                .eval(t, &eval_env)
+                                .unwrap();
                         }
                     },
                     criterion::BatchSize::LargeInput,
@@ -191,14 +200,15 @@ macro_rules! ncl_bench_group {
         pub fn $group_name() {
             use nickel_lang::{
                 cache::{Envs, Cache, ErrorTolerance, ImportResolver},
-                eval::VirtualMachine,
+                eval::{VirtualMachine, cache::Cache as EvalCache},
                 transform::import_resolution::resolve_imports,
             };
 
             let mut c: criterion::Criterion<_> = $config
                 .configure_from_args();
             let mut cache = Cache::new(ErrorTolerance::Strict);
-            let Envs {eval_env, type_ctxt} = cache.prepare_stdlib().unwrap();
+            let mut eval_cache = nickel_lang_utilities::EC::new();
+            let Envs {eval_env, type_ctxt} = cache.prepare_stdlib(&mut eval_cache).unwrap();
             $(
                 let bench = $crate::ncl_bench!$b;
                 let t = bench.term();
@@ -220,7 +230,7 @@ macro_rules! ncl_bench_group {
                                 c_local.typecheck(id, &type_ctxt).unwrap();
                             } else {
                                 c_local.prepare(id, &type_ctxt).unwrap();
-                                VirtualMachine::new(c_local).eval(t, &eval_env).unwrap();
+                                VirtualMachine::new_with_cache(c_local, eval_cache.clone()).eval(t, &eval_env).unwrap();
                             }
                         },
                         criterion::BatchSize::LargeInput,


Test patch:
diff --git a/src/eval/tests.rs b/src/eval/tests.rs
index d0f0f261..8d09efd2 100644
--- a/src/eval/tests.rs
+++ b/src/eval/tests.rs
@@ -1,6 +1,7 @@
 use super::*;
 use crate::cache::resolvers::{DummyResolver, SimpleResolver};
 use crate::error::ImportError;
+use crate::eval::cache::CBNCache;
 use crate::label::Label;
 use crate::parser::{grammar, lexer};
 use crate::term::make as mk_term;
@@ -9,9 +10,11 @@ use crate::transform::import_resolution::resolve_imports;
 use crate::{mk_app, mk_fun};
 use codespan::Files;
 
+type EC = CBNCache;
+
 /// Evaluate a term without import support.
 fn eval_no_import(t: RichTerm) -> Result<Term, EvalError> {
-    VirtualMachine::new(DummyResolver {})
+    VirtualMachine::<_, EC>::new(DummyResolver {})
         .eval(t, &Environment::new())
         .map(Term::from)
 }
@@ -171,7 +174,7 @@ fn imports() {
         var: &str,
         import: &str,
         body: RichTerm,
-        vm: &mut VirtualMachine<R>,
+        vm: &mut VirtualMachine<R, EC>,
     ) -> Result<RichTerm, ImportError>
     where
         R: ImportResolver,
@@ -284,17 +287,19 @@ fn interpolation_nested() {
 #[test]
 fn initial_env() {
     let mut initial_env = Environment::new();
+    let mut eval_cache = EC::new();
     initial_env.insert(
         Ident::from("g"),
-        Thunk::new(
+        eval_cache.add(
             Closure::atomic_closure(Term::Num(1.0).into()),
             IdentKind::Let,
+            BindingType::Normal,
         ),
     );
 
     let t = mk_term::let_in("x", Term::Num(2.0), mk_term::var("x"));
     assert_eq!(
-        VirtualMachine::new(DummyResolver {})
+        VirtualMachine::new_with_cache(DummyResolver {}, eval_cache.clone())
             .eval(t, &initial_env)
             .map(Term::from),
         Ok(Term::Num(2.0))
@@ -302,7 +307,7 @@ fn initial_env() {
 
     let t = mk_term::let_in("x", Term::Num(2.0), mk_term::var("g"));
     assert_eq!(
-        VirtualMachine::new(DummyResolver {})
+        VirtualMachine::new_with_cache(DummyResolver {}, eval_cache.clone())
             .eval(t, &initial_env)
             .map(Term::from),
         Ok(Term::Num(1.0))
@@ -311,20 +316,24 @@ fn initial_env() {
     // Shadowing of the initial environment
     let t = mk_term::let_in("g", Term::Num(2.0), mk_term::var("g"));
     assert_eq!(
-        VirtualMachine::new(DummyResolver {})
+        VirtualMachine::new_with_cache(DummyResolver {}, eval_cache.clone())
             .eval(t, &initial_env)
             .map(Term::from),
         Ok(Term::Num(2.0))
     );
 }
 
-fn mk_env(bindings: Vec<(&str, RichTerm)>) -> Environment {
+fn mk_env(bindings: Vec<(&str, RichTerm)>, eval_cache: &mut EC) -> Environment {
     bindings
         .into_iter()
         .map(|(id, t)| {
             (
                 id.into(),
-                Thunk::new(Closure::atomic_closure(t), IdentKind::Let),
+                eval_cache.add(
+                    Closure::atomic_closure(t),
+                    IdentKind::Let,
+                    BindingType::Normal,
+                ),
             )
         })
         .collect()
@@ -332,26 +341,33 @@ fn mk_env(bindings: Vec<(&str, RichTerm)>) -> Environment {
 
 #[test]
 fn substitution() {
-    let initial_env = mk_env(vec![
-        ("glob1", Term::Num(1.0).into()),
-        ("glob2", parse("\"Glob2\"").unwrap()),
-        ("glob3", Term::Bool(false).into()),
-    ]);
-    let env = mk_env(vec![
-        ("loc1", Term::Bool(true).into()),
-        ("loc2", parse("if glob3 then glob1 else glob2").unwrap()),
-    ]);
+    let mut eval_cache = EC::new();
+    let initial_env = mk_env(
+        vec![
+            ("glob1", Term::Num(1.0).into()),
+            ("glob2", parse("\"Glob2\"").unwrap()),
+            ("glob3", Term::Bool(false).into()),
+        ],
+        &mut eval_cache,
+    );
+    let env = mk_env(
+        vec![
+            ("loc1", Term::Bool(true).into()),
+            ("loc2", parse("if glob3 then glob1 else glob2").unwrap()),
+        ],
+        &mut eval_cache,
+    );
 
     let t = parse("let x = 1 in if loc1 then 1 + loc2 else glob3").unwrap();
     assert_eq!(
-        subst(t, &initial_env, &env),
+        subst(&eval_cache, t, &initial_env, &env),
         parse("let x = 1 in if true then 1 + (if false then 1 else \"Glob2\") else false").unwrap()
     );
 
     let t = parse("switch {`x => [1, glob1], `y => loc2, `z => {id = true, other = glob3}} loc1")
         .unwrap();
     assert_eq!(
-        subst(t, &initial_env, &env),
+        subst(&eval_cache, t, &initial_env, &env),
         parse("switch {`x => [1, 1], `y => (if false then 1 else \"Glob2\"), `z => {id = true, other = false}} true").unwrap()
     );
 }
diff --git a/tests/integration/examples.rs b/tests/integration/examples.rs
index b6a0f4f2..8bc974bc 100644
--- a/tests/integration/examples.rs
+++ b/tests/integration/examples.rs
@@ -1,13 +1,13 @@
 use assert_matches::assert_matches;
 use nickel_lang::error::{Error, EvalError};
-use nickel_lang::program::Program;
 use nickel_lang::term::RichTerm;
+use nickel_lang_utilities::TestProgram;
 use std::path::PathBuf;
 
 fn eval_file(file: &str) -> Result<RichTerm, Error> {
     let mut path = PathBuf::from(env!("CARGO_MANIFEST_DIR"));
     path.push(format!("examples/{}", file));
-    let mut p = Program::new_from_file(path).expect("could not load file as a program");
+    let mut p = TestProgram::new_from_file(path).expect("could not load file as a program");
     p.eval_deep()
 }
 
diff --git a/tests/integration/imports.rs b/tests/integration/imports.rs
index a489ff68..3ede4d1a 100644
--- a/tests/integration/imports.rs
+++ b/tests/integration/imports.rs
@@ -1,7 +1,7 @@
 use assert_matches::assert_matches;
 use nickel_lang::error::{Error, EvalError, ImportError, TypecheckError};
-use nickel_lang::program::Program;
 use nickel_lang::term::Term;
+use nickel_lang_utilities::TestProgram;
 use std::io::BufReader;
 use std::path::PathBuf;
 
@@ -16,7 +16,7 @@ fn mk_import(file: &str) -> String {
 
 #[test]
 fn nested() {
-    let mut prog = Program::new_from_source(
+    let mut prog = TestProgram::new_from_source(
         BufReader::new(mk_import("nested.ncl").as_bytes()),
         "should_be = 3",
     )
@@ -26,7 +26,7 @@ fn nested() {
 
 #[test]
 fn root_path() {
-    let mut prog = Program::new_from_source(
+    let mut prog = TestProgram::new_from_source(
         BufReader::new(mk_import("root_path.ncl").as_bytes()),
         "should_be = 44",
     )
@@ -36,7 +36,7 @@ fn root_path() {
 
 #[test]
 fn multi_imports() {
-    let mut prog = Program::new_from_source(
+    let mut prog = TestProgram::new_from_source(
         BufReader::new(mk_import("multi_imports.ncl").as_bytes()),
         "should_be = 5",
     )
@@ -46,7 +46,7 @@ fn multi_imports() {
 
 #[test]
 fn contract_fail() {
-    let mut prog = Program::new_from_source(
+    let mut prog = TestProgram::new_from_source(
         BufReader::new(mk_import("contract-fail.ncl").as_bytes()),
         "should_fail",
     )
@@ -59,7 +59,7 @@ fn contract_fail() {
 
 #[test]
 fn typecheck_fail() {
-    let mut prog = Program::new_from_source(
+    let mut prog = TestProgram::new_from_source(
         BufReader::new(mk_import("typecheck-fail.ncl").as_bytes()),
         "should_fail",
     )
@@ -72,7 +72,7 @@ fn typecheck_fail() {
 
 #[test]
 fn static_typing_fail() {
-    let mut prog = Program::new_from_source(
+    let mut prog = TestProgram::new_from_source(
         BufReader::new(format!("(let x = {} in x) : Str", mk_import("two.ncl")).as_bytes()),
         "should_fail",
     )
@@ -86,7 +86,7 @@ fn static_typing_fail() {
 #[test]
 fn serialize() {
     use nickel_lang::term::Term;
-    let mut prog = Program::new_from_source(
+    let mut prog = TestProgram::new_from_source(
         BufReader::new(
             format!(
                 "(builtin.serialize `Json ({})) == (builtin.serialize `Json ({{foo = \"ab\"}}))",
@@ -102,7 +102,7 @@ fn serialize() {
 
 #[test]
 fn circular_imports_fail() {
-    let mut prog = Program::new_from_source(
+    let mut prog = TestProgram::new_from_source(
         BufReader::new(mk_import("cycle.ncl").as_bytes()),
         "should_fail",
     )
@@ -115,7 +115,7 @@ fn circular_imports_fail() {
 
 #[test]
 fn import_unexpected_token_fail() {
-    let mut prog = Program::new_from_source(
+    let mut prog = TestProgram::new_from_source(
         BufReader::new(mk_import("unexpected_token.ncl").as_bytes()),
         "should_fail",
     )
@@ -128,7 +128,7 @@ fn import_unexpected_token_fail() {
 
 #[test]
 fn import_unexpected_token_in_record_fail() {
-    let mut prog = Program::new_from_source(
+    let mut prog = TestProgram::new_from_source(
         BufReader::new(
             format!(
                 "let x = {} in \"Hello, \" ++ x.name",
@@ -147,7 +147,7 @@ fn import_unexpected_token_in_record_fail() {
 
 #[test]
 fn import_unexpected_token_buried_fail() {
-    let mut prog = Program::new_from_source(
+    let mut prog = TestProgram::new_from_source(
         BufReader::new(
             format!(
                 "let _ign = {} in 1",
diff --git a/tests/integration/merge_fail.rs b/tests/integration/merge_fail.rs
index 449fe2ef..063e02d2 100644
--- a/tests/integration/merge_fail.rs
+++ b/tests/integration/merge_fail.rs
@@ -1,14 +1,14 @@
 use assert_matches::assert_matches;
 use nickel_lang::error::{Error, EvalError};
 use nickel_lang::position::TermPos;
-use nickel_lang::program::Program;
 use nickel_lang::term::RichTerm;
+use nickel_lang_utilities::TestProgram;
 use std::io::Cursor;
 
 fn eval_full(s: &str) -> Result<RichTerm, Error> {
     let src = Cursor::new(s);
 
-    let mut p = Program::new_from_source(src, "<test>").map_err(|io_err| {
+    let mut p = TestProgram::new_from_source(src, "<test>").map_err(|io_err| {
         Error::EvalError(EvalError::Other(
             format!("IO error: {}", io_err),
             TermPos::None,
diff --git a/tests/integration/pass.rs b/tests/integration/pass.rs
index 66bc59a8..9070d37a 100644
--- a/tests/integration/pass.rs
+++ b/tests/integration/pass.rs
@@ -1,5 +1,5 @@
-use nickel_lang::program::Program;
 use nickel_lang::term::Term;
+use nickel_lang_utilities::TestProgram;
 use std::ffi::OsString;
 use std::path::PathBuf;
 use std::thread;
@@ -10,7 +10,7 @@ const STACK_SIZE: usize = 4 * 1024 * 1024;
 
 fn run(path: impl Into<OsString>) {
     let path = path.into();
-    let mut p = Program::new_from_file(path.clone()).expect("could not load file as a program");
+    let mut p = TestProgram::new_from_file(path.clone()).expect("could not load file as a program");
     assert_eq!(
         p.eval().map(Term::from),
         Ok(Term::Bool(true)),
diff --git a/tests/integration/query.rs b/tests/integration/query.rs
index 6ed63652..7af9bf40 100644
--- a/tests/integration/query.rs
+++ b/tests/integration/query.rs
@@ -1,9 +1,9 @@
-use nickel_lang::program::Program;
 use nickel_lang::term::{MetaValue, SharedTerm, Term};
+use nickel_lang_utilities::TestProgram;
 
 #[test]
 pub fn test_query_metadata_basic() {
-    let mut program = Program::new_from_source(
+    let mut program = TestProgram::new_from_source(
         "{val | doc \"Test basic\" = (1 + 1)}".as_bytes(),
         "regr_tests",
     )
@@ -22,11 +22,11 @@ pub fn test_query_metadata_basic() {
 pub fn test_query_with_wildcard() {
     /// Checks whether `lhs` and `rhs` both evaluate to terms with the same static type
     fn assert_types_eq(lhs: &str, rhs: &str) {
-        let term1 = Program::new_from_source(lhs.as_bytes(), "regr_tests")
+        let term1 = TestProgram::new_from_source(lhs.as_bytes(), "regr_tests")
             .unwrap()
             .query(None)
             .unwrap();
-        let term2 = Program::new_from_source(rhs.as_bytes(), "regr_tests")
+        let term2 = TestProgram::new_from_source(rhs.as_bytes(), "regr_tests")
             .unwrap()
             .query(None)
             .unwrap();
@@ -52,7 +52,7 @@ pub fn test_query_with_wildcard() {
     }
 
     // Without wildcard, the result has no type annotation
-    let mut program = Program::new_from_source("10".as_bytes(), "regr_tests").unwrap();
+    let mut program = TestProgram::new_from_source("10".as_bytes(), "regr_tests").unwrap();
     let result = program.query(None).unwrap();
     assert!(!matches!(result, Term::MetaValue(_)));