%--------------------------------------------------% % vim: ft=mercury ts=4 sw=4 et %--------------------------------------------------% % Copyright (C) 1999, 2006, 2009-2010 The University of Melbourne. % Copyright (C) 2013-2016, 2018-2019, 2022 The Mercury team. % This file is distributed under the terms specified in COPYING.LIB. %--------------------------------------------------% % % File: lazy.m. % Main authors: fjh, pbone. % Stability: medium. % % Provides support for optional explicit lazy evaluation. % % This module provides the data type lazy(T) and the functions `val', % `delay', and `force', which can be used to emulate lazy evaluation. % % A field within a data structure can be made lazy by wrapping it within % a lazy type. Or a lazy data structure can be implemented, for example: % % :- type lazy_list(T) % ---> lazy_list( % lazy(list_cell(T)) % ). % % :- type list_cell(T) % ---> cons(T, lazy_list(T)) % ; nil. % % Note that this makes every list cell lazy, whereas: % % lazy(list(T)) % % uses only one thunk for the entire list. And: % % list(lazy(T)) % % uses one thunk for every element, but the list's structure is not lazy. % %--------------------------------------------------% :- module lazy. :- interface. % A lazy(T) is a value of type T which will only be evaluated on demand. % :- type lazy(T). % Convert a value from type T to lazy(T). % :- func val(T) = lazy(T). % Construct a lazily-evaluated lazy(T) from a closure. % :- func delay((func) = T) = lazy(T). % Force the evaluation of a lazy(T), and return the result as type T. % Note that if the type T may itself contain subterms of type lazy(T), % as is the case when T is a recursive type, those subterms will not be % evaluated -- force/1 only forces evaluation of the lazy/1 term at % the top level. % % A second call to force will not re-evaluate the lazy expression, it % will simply return T. % :- func force(lazy(T)) = T. % Get the value of a lazy expression if it has already been made available % with force/1. This is useful as it can provide information without % incurring (much) cost. % :- impure pred read_if_val(lazy(T)::in, T::out) is semidet. % Test lazy values for equality. % :- pred equal_values(lazy(T)::in, lazy(T)::in) is semidet. :- pred compare_values(comparison_result::uo, lazy(T)::in, lazy(T)::in) is det. %--------------------------------------------------% % % The declarative semantics of the above constructs are given by the % following equations: % % val(X) = delay((func) = X). % % force(delay(F)) = apply(F). % % The operational semantics satisfy the following: % % - val/1 and delay/1 both take O(1) time and use O(1) additional space. % In particular, delay/1 does not evaluate its argument using apply/1. % % - When force/1 is first called for a given term, it uses apply/1 to % evaluate the term, and then saves the result computed by destructively % modifying its argument; subsequent calls to force/1 on the same term % will return the same result. So the time to evaluate force(X), where % `X = delay(F)', is O(the time to evaluate `apply(F)') for the first call, % and O(1) time for subsequent calls. % % - Equality on values of type lazy(T) is implemented by calling force/1 % on both arguments and comparing the results. So if X and Y have type % lazy(T), and both X and Y are ground, then the time to evaluate % `X = Y' is O(the time to evaluate `X1 = force(X)' + the time to evaluate % `Y1 = force(Y)' + the time to unify X1 and Y1). % %--------------------------------------------------% %--------------------------------------------------%