%--------------------------------------------------% % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0 %--------------------------------------------------% % Copyright (C) 1999, 2006, 2009-2010 The University of Melbourne. % This file may only be copied under the terms of the GNU Library General % Public License - see the file COPYING.LIB in the Mercury distribution. %--------------------------------------------------% % % lazy.m - provides support for optional explicit lazy evaluation. % % Author: fjh, pbone. % Stability: medium. % % 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 contains subterms of type lazy(T), % as is the case when T is a recursive type like the lazy_list(T) type % defined in lazy_list.m, 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). % %--------------------------------------------------% %--------------------------------------------------%