Hamming numbers, lazy evaluation, and eager disposal

Nicholas Pippenger has recently given a problem that, under two simple restrictions, can be solved in linear time by an impure Lisp program, but requires Ω(n log n) steps to be solved by any eager pure Lisp program. By showing how to solve the problem ...

What is a non-strict functional language? Is a non-strict language necessarily lazy? What additional expressiveness brings non-strictness, with or without laziness? This paper tries to shed some light on these questions. First, in order to characterize ...

Given a string x and a language L, the Hamming distance of x to L is the minimum Hamming distance of x to any string in L. The edit distance of a string to a language is analogously defined.First, we prove that there is a language in AC⁰ such that both ...