Time complexity of lazy programs. profiling functional languages 
Author Message
 Time complexity of lazy programs. profiling functional languages

Theo Norvell writes:
>> What research has been done on analysing the time required for
>> programs written in lazy languages to execute?  I'm interested
>> in both exact counts (e.g. the number of application of primitives)
>> or the big-oh (or big-theta) complexity.

>> Any pointers or ideas will be greatfully received.

We've done work on this at UCL.  Have a look at

%A S. Clayman
%A D. Parrott
%A C. Clack
%T A Profiling Technique for Lazy, Higher-order Functional Programs
%R RN/92/24
%D November 1991
%X abstract
This paper presents a technique for accurately profiling the time and
space used by lazy, higher-order functional programs.  Using this
technique we have constructed a profiler that can be used to monitor
programs as they run and to build detailed trace information for
post-mortem debugging.  Time profiling results are similar in nature
to, but more accurate than, the \s-1UNIX\s+1 imperative language
.B gprof
The profiling technique is designed primarily for use by programmers
rather than functional language implementors and
the results directly reflect the lexical scoping of the source
program, thus overcoming problems caused by compile-time program
transformation, lazy evaluation, and higher order functions.

Fri, 18 Nov 1994 21:47:37 GMT  
 Time complexity of lazy programs. profiling functional languages
Other references include

A compositional approach to time analysis of first order lazy
functional programs

B Bjerner, S. Holmstrom


Functional Programming Languages and Computer Architecture 1989
ACM Press
ISBN 0-201-51389-7

Simon Thompson
University of Kent

Sat, 19 Nov 1994 16:37:13 GMT  
 Time complexity of lazy programs. profiling functional languages
Another reference is:

P. Wadler, Strictness analysis aids time analysis, 15'th ACM Symposium
on Principles of Programming Languages, San Diego, January 1988.

Cheers,  -- P

Sun, 20 Nov 1994 16:44:18 GMT  
 [ 3 post ] 

 Relevant Pages 

1. Profiling Lazy Functional Languages

2. Time complexity of lazy programs.

3. Questions about time complexity of functional programming

4. Functional Programming Languages with Lazy Evaluation

5. Speed of FP languages, prospects (was Re: Benchmarking Lazy Functional Languages)

6. Profiling Lazy Languages

7. Complexity (Was: Why use a functional language?)

8. Complexity (Was: Why use a functional language?)

9. A functional/imperative lazy curious guy with too much time on his hands

10. multiplatform GUI design with parallelized lazy functional language

11. Lazy and Strict Functional languages

12. Computational Complexity of Functional Program


Powered by phpBB® Forum Software