caa a22 4500 467989648 CHVBK 20180323112541.0 cr unu---uuuuu 170328e19901101xx s 000 0 eng 10.1007/BF02983374 doi (NATIONALLICENCE)springer-10.1007/BF02983374 Khoshnevisan Hessam Department of Computing, Imperial College of Science and Technology and Medicine, SW 7 2BZ, London, UK aut Efficient memo-table management strategies [Elektronische Daten] [Hessam Khoshnevisan] Summary: A large, automatically detectable class of non-linear functions is defined and their evaluation graphs are characterised. These results are then used to develop space-efficient implementation ofmemo-functions. We generate a variant of memo-functions which can be used to linearise the time cost of calls of a non-linear function to itself whilst executing in bounded space. These memo-functions dynamically garbage collect (or reuse) memo-table entries when it is known that such entries will not be useful again. For each non-linear function a function called the "table-manager” function is synthesised by a static analysis of the definition of the non-linear function. The table-managers delete (or reuse) entries that are guaranteed to be obsolete as a result of any insertion into the memo-tables. In this way they ensure that the size of the tables is minimised. Furthermore, the sizes of the tables for these memo-functions are guaranteed not to exceed a compile-time constant found by the same static analysis which synthesises the table-managers. The applicability of the method also includes many problems which have been previously solved by applyingdynamic programming techniques. An implementation of these memo-functions for the functional language HOPE is also outlined. Springer-Verlag, 1990 Acta Informatica Springer-Verlag 28/1(1990-11-01), 43-81 0001-5903 28:1<43 1990 28 236 https://doi.org/10.1007/BF02983374 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02983374 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Khoshnevisan Hessam Department of Computing, Imperial College of Science and Technology and Medicine, SW 7 2BZ, London, UK aut NATIONALLICENCE 773 0- Acta Informatica Springer-Verlag 28/1(1990-11-01), 43-81 0001-5903 28:1<43 1990 28 236 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer