# Library Ltac2.Lazy

Require Import Ltac2.Init.

Require Ltac2.Ref.

Require Ltac2.Control.

Ltac2 Type 'a lazy_data := [ Value ('a) | Thunk (unit -> 'a) ].

Type of a lazy cell, similar to OCaml's 'a Lazy.t type. The functions of
this module do not have any specific backtracking support, so any function
passed to primitives of this module is handled as if it had one success at
most (potential other successes are ignored).

Ltac2 Type 'a t := 'a lazy_data Ref.ref.

from_val v creates a new lazy cell storing (already-computed) value v.
Forcing (i.e., using the force function on) the produced cell gives back
value v, and never gives an exception.

Ltac2 from_val (v : 'a) : 'a t :=

Ref.ref (Value v).

Ref.ref (Value v).

from_fun f creates a new lazy cell from the given thunk f. There is no
specific support for backtracking in the Lazy module, so if f has more
than one success, only the first one will be considered.

Ltac2 from_fun (f : unit -> 'a) : 'a t :=

Ref.ref (Thunk f).

Ref.ref (Thunk f).

is_val r indicates whether the given lazy cell r holds a forced value.
In particular, is_val r always returns true if r was created via the
from_val function. If r was created using from_fun, then true will
only be returned if the value of r was previously forced (e.g., with the
force function), and if no exception was produced by said forcing.

Ltac2 is_val (r : 'a t) : bool :=

match Ref.get r with

| Value _ => true

| Thunk _ => false

end.

match Ref.get r with

| Value _ => true

| Thunk _ => false

end.

Exception raised in case of a "cyclic" lazy cell.

Ltac2 Type exn ::= [ Undefined ].

force r gives the value represented by the lazy cell r, which requires
forcing a thunk and updating r to the produced value if r does not yet
have a value. Note that if forcing produces an exception, subsequent calls
to force will immediately yield the same exception (without re-computing
the whole thunk). Additionally, the Undefined exception is produced (and
set to be produced by r on subsequent calls to force) if r relies on
its own value for its definition (i.e., if r is "cyclic").

Ltac2 force (r : 'a t) : 'a :=

match Ref.get r with

| Value v => v

| Thunk f =>

Ref.set r (Thunk (fun () => Control.throw Undefined));

match Control.case f with

| Val (v, _) =>

Ref.set r (Value v);

v

| Err e =>

Ref.set r (Thunk (fun () => Control.zero e));

Control.zero e

end

end.

match Ref.get r with

| Value v => v

| Thunk f =>

Ref.set r (Thunk (fun () => Control.throw Undefined));

match Control.case f with

| Val (v, _) =>

Ref.set r (Value v);

v

| Err e =>

Ref.set r (Thunk (fun () => Control.zero e));

Control.zero e

end

end.

map f r is equivalent to from_fun (fun () => f (force r)).

Ltac2 map (f : 'a -> 'b) (r : 'a t) : 'b t :=

from_fun (fun () => f (force r)).

from_fun (fun () => f (force r)).

map_val f r is similar to map f r, but the function f is immediately
applied if r contains a forced value. If the immediate application gives
an exception, then any subsequent forcing of produced lazy cell will raise
the same exception.

Ltac2 map_val (f : 'a -> 'b) (r : 'a t) : 'b t :=

match Ref.get r with

| Value v =>

match Control.case (fun () => f v) with

| Val (v, _) => from_val v

| Err e => from_fun (fun () => Control.zero e)

end

| Thunk t => from_fun (fun () => f (t ()))

end.

Module Export Notations.

Ltac2 Notation "lazy!" f(thunk(self)) := from_fun f.

End Notations.

match Ref.get r with

| Value v =>

match Control.case (fun () => f v) with

| Val (v, _) => from_val v

| Err e => from_fun (fun () => Control.zero e)

end

| Thunk t => from_fun (fun () => f (t ()))

end.

Module Export Notations.

Ltac2 Notation "lazy!" f(thunk(self)) := from_fun f.

End Notations.