Bayle Shanks's website: proj-oot-ootLazyNotes1

consider a strictness analyzer which is conservative in that it marks functions as 'maybe strict in argument 1' when its not sure, and values as 'maybe infinite' when not sure. these can be overriden by declarations

also maybe it notices when it is recursing into a function and if so, strictifies that.

sort of like that haskell library that provides lists that evaluate the whole list when you evaluate any element of it.

but not quite. b/c we still want to allow infinite lists. more like codata: if you find yourself recursing WITHOUT producing any output, THEN strictify.

note that 'recursing' has to include MUTUAL recursion, so that the programmer can choose to divide a big recursive function into multiple functions that call each other

so, in the example with foldl in http://www.haskell.org/haskellwiki/Stack_overflow , we would notice that we are building up a thunk by recursing between + and foldl, without producing any output (this is not codata-like guarded recursion). so we strictify the thunk.

the example with foldr is tougher. looking at the expansion which is explicitly shown in http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27, we see that we actually can't reduce this without knowing that + is associative. So this really falls into the 'almost tail recursive' detection scenario.

however, the strictness analysis should be able to be given "sum1 = foldr (+) 0", and the knowledge that + is associative, and from this derive that sum1 will hang if applied to codata.

so it seems that data and codata might be just the language we need to talk about the sort of strictness analysis that i want.

btw the terms 'data' and 'codata' are confusing because 'data' already has another definition. when i write about 'data', you don't know if mean the usual definition of the term, which includes all codata, or the data/codata definition, which excludes some codata. so i'd like to call it finite data vs. infinite data instead of data vs. codata.

so, note that finite data is a value for which, if a substructurally recursive function is strictly (or lazily) applied to it, that function will terminate. infinite data is a value for which, if a guarded recursive function is lazily applied to it, that function will terminate and produce at least one next element.

the traditional use seems to be to restrict the language in order to prove termination. but in this case we want the compiler to hypothetically consider strictification and decide if there's any chance that strictification would convert a terminating program into a non-terminating one.

if the program was already non-terminating, then we don't care (it's the programmer's fault). so if a programmer calls a non-substructurally recursive function on finite data, that's fine, and if they lazily call a non-guarded recursive function on infinite data, that's fine.

what we are considering is strictification. if you strictify something which is applied to finite data, it'll still terminate, it might just be less efficient. but if you strictify something which is applied to infinite data which is not necessarily finite data, you may turn something terminating into something nonterminating. so that's what we want to watch out for.

so, we want to identify things which may not be finite data and which may be infinite data, and avoid strictifying them.

the conservative approach is to assume that anything might be infinite data, and so not strictify unless the programmer declares something as finite data, or unless we infer that. This is similar to my idea that laziness is the default but that optionally 'eagerness' could be attached to values.

however, we could be more aggressive. as noted above, if you have a function that is not terminating on finite data, and furthermore not even a single lazy step is terminating on infinite data, then we don't care because the programmer made a mistake. if we have an arbitrary function being applied to arbitrary finite data, the compiler can reason:

maybe it's finite data, and the function is structurally recursive. if i knew that, i could strictify.
maybe it's finite data, and the function is guarded recursive. if i knew that, i could strictify.
maybe it's finite data, and the function is neither structurally recursive nor guarded recursive. if i knew that, i could strictify.
maybe it's infinite data, and the function is guarded recursive. in this case, i must not strictify.
maybe it's infinite data, and the function is not guarded recursive but still lazily terminates on infinite data. in this case, i must not strictify.
maybe it's infinite data, and the function is not guarded recursive but does not lazily terminate on infinite data. in this case, i can strictify.

so the only cases in which strictification is forbidden is when (a) the argument is infinite data, and (b) the function operating on it lazily terminates on infinite data.

the conservative thing to do is to assume that any finite data that we don't understand must be infinite data, and any function that we don't understand must lazily terminate on infinite data.

but we could get more aggressive by prohibiting either undeclared infinite data (e.g. forcing possibly lazy values to be explicitly declared as 'lazy', except when this is inferred), or undeclared functions that terminate on infinite data (e.g. forcing functions that can safely operate on lazy data structures to be declared as such, except when this is inferred). if we did either of these, then the compiler need only check if it can infer either that the inputs are infinite data or that the function is safe on infinite data, and if neither are true, then it can strictify.

(and by strictify, we might mean strictify inputs, or we might mean only strictify if the function finds that it is (possibly mutually) recursively calling itself before producing any output)

note that if a function finds that it is (possibly mutually) recursively calling itself before producing any output, then it must not be guarded recursive.

so how about this. if a function finds that it is (possibly mutually) recursively calling itself before producing any output, then unless it is specially declared as safe for infinite data, we strictify.

the only time this causes a problem is if we have some weird function which recurses on itself more than once before producing output. this is the case in which the programmer is required to declare.

this could be annoying because if the programmer forgets to declare this for such a function, and that function is run on finite data, it will be strictified and everything will seem fine, but then a bug will only crop up when it is run on infinite data. Worse, if that function is in library code, now the library can't be used with infinite data.

so maybe we should require the programmer to declare for EVERY function either 'safe for infinite data' or 'unsafe for infinite data', except when we can infer this at compile time. this would mean automatically identifying guarded recursion, and forcing a declaration in all other cases.

another approach would be to provide both a facility to declare infinite data, and a facility to declare functions safe for infinite data (and therefore unsafe for strictification on infinite data). Now if the library writing forgets to declare their function safe for infinite data, the user can prevent autostrictification by passing in something declared as infinite data.

so, the proposal is as follows:

1) provide a facility to declare that certain inputs to certain functions are cool with infinite data, even though the function may not be guarded recursive 2) provide a facility to declare that certain outputs from certain functions will only yield infinite data if the function is given infinite data input 3) provide a facility to declare that certain outputs from certain functions will always yield finite data, even when the function's inputs are infinite data (e.g. the Haskell function 'take'). This implies (2). 4) provide a facility to declare that certain values are eager data, or that they are lazy data

and then during compile time: 1) infer substructural recursion. Mark such functions as 'only yields infinite data if given infinite data'. (this covers 'sum') 2) infer functions will only recur on some of their arguments, and mark them as 'always yields finite data' and 'only yields infinite data if given infinite data' in the other arguments (this covers 'take') 4) transitively dataflow trace eager data through functions that 'only yields infinite data if given infinite data', to mark their outputs as eager when only eager data is provided 4) transitively dataflow trace lazy data through functions that are not 'always yields finite data', to mark their outputs as lazy when lazy data is provided 5) if any value is marked both 'eager' and 'lazy' then raise a compile-time error

and then during runtime:

1) upon exiting a function or calling into a function, for those outputs or parameter values that are marked eager, strictify 2) upon exiting a function, check to see if we are stuck in a mutual recursion loop that has not produced any lazy output in an entire pass. If so, then unless either (a) the data is marked 'lazy', or (b) the data is passing into function inputs marked 'cool with infinite data', strictify.

i think this would allow the runtime to convert foldl to foldl' automatically, while still permitting codata-safe but non-guarded recursive functions (like interpreters), and still allowing a client to make such a libary function work if the original author forgot to declare it as such (by passing in 'lazy' values), and still allow stream fusion (because the auto-strictification only occurs when the runtime detects a loop that is not producing lazy output).

now, we don't really need declarations (2) and (3), because if we miss some of these, we only under-propagate the eager attribute and over-propagate the lazy attribute. This just reduces the power of the user to use eager data to overcome laziness (because we're being overly 'safe' about not letting the user force strictness through things that we worry may be like 'iterate') , and increases the clumsiness of the 'lazy' attribute (because it will not be removed through some things that are undetectably like 'take').

also, the 'cool with infinite data' is really about the path between certain inputs and certain arguments to recursive calls, but we might want to move just to the function as a whole, b/c that might seem simpler.

also, i guess 'cool with infinite data' applies to foldl inside 'sum1 = foldr (+) 0', but not always to foldr, so we need to be able to add that modifier on a per-call basis.

so the streamlined proposal is:

1) you can declare functions as 'lazyrec', meaning that you don't want autostrictification within them 2) when calling functions, you can call them thru the functor 'lazyrec', which is like declaring them 'lazyrec' just for that call 3) you can declare values as 'lazy', meaning that you don't want autostrictification applied to them or their heirs 4) you can declare values as 'eager', meaning that you want strictification applied to them and their heirs

during compile time:

1) infer substructural recursion. Mark such functions as 'only yields infinite data if given infinite data'. (this covers 'sum') 2) infer functions will only recur on some of their arguments, and mark them as 'always yields finite data' and 'only yields infinite data if given infinite data' in the other arguments (this covers 'take') 4) transitively dataflow trace eager data through functions that 'only yields infinite data if given infinite data', to mark their outputs as eager when only eager data is provided 4) transitively dataflow trace lazy data through functions that are not 'always yields finite data', to mark their outputs as lazy when lazy data is provided 5) if any value is marked both 'eager' and 'lazy' then raise a compile-time error

and then during runtime:

1) upon exiting a function or calling into a function, for those outputs or parameter values that are marked eager, strictify 2) upon exiting a function, check to see if we are stuck in a mutual recursion loop that has not produced any lazy output in an entire pass. If so, then unless either (a) the data is marked 'lazy', or (b) the function at the top of the loop is marked 'lazyrec', strictify.

---

http://www.cs.cmu.edu/~me/150/resources/lectures/23/LazyEvaluation.pdf

---

If you haven't read it,

If you haven't read it, check out Why Functional Programming Matters. By Ehud Lamm at Wed, 2007-05-30 18:05

Why Functional Programming Matters

Why Functional Programming Matters by John Hughes (1984)

Let me reemphasize this. This is one the best motivating papers for lazy evaluation and higher order functions even 23 years after it's creation. The most significant feature missing from it's treatment of laziness is circular programming, a.k.a. tying the knot. By Derek Elkins at Wed, 2007-05-30 22:15

http://www.haskell.org/haskellwiki/Tying_the_Knot

i think this is probably not a good idea, but just putting it out there: should we be lazy only across fn boundaries?

mb have laziness only for referentially transparent things, and have strictness for non-referentially transparent things, including not only I/O to the outside world, but also accesses to aliased reference variables.

(purely stochastic functions are technically non-referentially transparent but we'll treat them as if they were; what we are really concerned about is spooky action at a distance, e.g. aliasing)

if you do this, though, then what about accesses to aliased reference variables which are 'within one of the current monads'? this should logically be done lazily, because accesses to something 'within one of the current monads' should not 'count' as aliased reference right? but in that case since there we may have (commutative) multiple monads, this doesn't jive with the 'one receiver' for non-referentially transparent things (although maybe it does, since each such thing's 'receiver' just means either that the thing itself is accessed only via a API/set of methods, or that accesses to it are syntactic sugar for calls to methods of its monad?).

if we do something like that, must make sure that stuff like backtracking monads ( http://www.randomhacks.net/2007/03/12/monads-in-15-minutes/ ) still exist/work

an alternative to stict and lazy would be 'strict unless', where everything is strict except when the value is marked as infinite, or when the evaluation of the value would produce (nonundoable?) side effects. this would necessitate that all potentially infinite valuees would be marked (or, perhaps better, that all definitely finite values be marked; this would give the same semantics as laziness). this would bllock lazy stream fusion, tho, i think

---

laziness in clojure vs haskell:

http://debasishg.blogspot.com/2010/05/laziness-in-clojure-some-thoughts.html

" Clojure is not as lazy as Haskell. And hence the benefits are also not as pervasive. Haskell being lazy by default, the compiler can afford to make aggressive optimizations like reordering of operations and transformations that Clojure can't. With Haskell's purity that guarantees absence of side-effects, deforestation optimizations like stream fusion generates tight loops and minimizes heap allocations. But I hear that Clojure 1.2 will have some more compiler level optimizations centered around laziness of its sequences. "

" Being interoperable with Java is one of the benefits of Clojure. However you need to be aware of the pitfalls of using Java's data structures with the lazy paradigm of Clojure. Consider the following example where I put all accounts in a java.util.concurrent.LinkedBlockingQueue?.

(import '(java.util.concurrent LinkedBlockingQueue?)) (def myq (new LinkedBlockingQueue?)) (doto myq (.put acc-1) (.put acc-2) (.put acc-3))

Now consider the following snippet that does some stuff on the queue ..

(let [savings-accounts (filter #(= (:type %) ::savings) myq)] (.clear myq) (.addAll myq savings-accounts))

Should work .. right ? Doesn't ! filter is lazy and hence savings-accounts is empty within the let-block. Then we clear myq and when we do an addAll, it fails since savings-accounts is still empty. The solution is to use a doall, that blows away the laziness and realizes the filtered sequence ..

(let [savings-accounts (doall (filter #(= (:type %) ::savings) myq))] (.clear myq) (.addAll myq savings-accounts))

Of course laziness in Clojure sequences is something that adds power to your abstractions. However you need to be careful on two grounds :

    Clojure as a language is not lazy by default in totality (unlike Haskell) and hence laziness may get mixed up with strict evaluation leading to surprising and unoptimized consequences.
    Clojure interoperates with Java, which has mutable data structures and strict evaluation. Like the situation I described above with LinkedBlockingQueue, sometimes it's always safe to bite the bullet and do things the Java way.

---

" Update: It seems worthwhile to point out that memoization to create a persistent from an ephemeral data structure is a premier example of a benign effect, the use of state to evince functional behavior. But benign effects are not programmable in Haskell, because of the segregation of effects into the IO monad. "

---

http://existentialtype.wordpress.com/2011/04/24/the-real-point-of-laziness/

---

maybe have strictness-by-default within modules, but lazy-by-default between modules (e.g. upon values deriving from module inputs). So e.g. if you have

any p = or . map p

if the function 'any' is exposed to other modules, then this'll work as desired (both 'map' and 'or' will be lazy because their input is from another module, and '.' will be lazy because its operating on an input to this function, and this function is exposed to other modules)

if it was instead a module-internal function, then you'd have to make the '.' explicitly lazy:

any p = or lazy. map p

hmm... alternately, maybe lazy-by-default for point-free functions?

any p = or . map p

would be lazy, but

any p x = or . map p x

would not?

---

guess: memory consumption of laziness really only a prob when u have a recursive stack of thunks, by which i mean a thujnk of a thunk if thunck etc where the same subroutine generated many of those thunks. so idea: tag each thunk with a graph of all subroutines that generated any thunks within it ( i say graph so you can discriminate vertical stacking from mere hroizontal reoccurence), and if the subroutine on top (in root/head position) is part of a vertical stack in which the same subroutine occured n times, strictify. not quite; we want to only strictify if the (effective?) control flow graph involved this guy calling itself; not just if the computation has a lot of values 'wrapped' by this guy e.g. map f; map is never gonna recursively call itself, so even if there are 3 other maps vertically inside f, map is not the problem amd fold can have a memory leak without thunking over itslef, right? so what we want is to annotation the point of control is the program source from which each thunk was generated, rather than of the contents of the thunk

strict and lazy annotations, otherwise the compiler and/or runtime decides need bytecode for 'runtime decides' constraints on compiler: respect annotations, and if unannoated, nothing which takes a designated_lazy value is strict, and if unannotated and provably cannot take a designated lazy value, then must be strict if control flow generating the recursion is not fixed ?

note: compiler/runtime can trivially satisfy these by ??? no it can't

should have a 'must be lazy' annotation and a 'must be strict' annotation. Also, values may be annotated as 'lazy' (wait, is this any different from annotating expressions? i think no, because thunks contain expressions; if the head of the thunk has a 'lazy' annotation that's the same, right?). if neither are present, the laziness/strictness is undefined (the compiler/interpreter/runtime can choose), subject to the following guarantees:

if the control flow generating this thunk is recursing a non-constant number of times, then must be strict

bytecodes:

lazy
strict
runtime decides, but must enforce language guarantees (note: can be easily implemented by just checking if the head of the thunk is marked 'lazy', and otherwise, always choosing strict)
runtime decides, and compiler promises that strictness is not required by language guarantees (e.g. runtime could just treat this as 'always lazy')
runtime decides, and compiler promises that laziness is not required by language guarantees (e.g. runtime could just treat this as 'always strict')

should also have a 'lazy unless proven unnecessary' annotation, meaning, lazy unless the compiler can prove that no infinite data structure is generated

maybe in fact just have four annotations:

lazy
strict
lazy-unless-provably-nonrecursive-thunk-contents
strict-unless-provably-constant-control-flow-generating-thunk

and the default is the same as strict-unless-provably-constant-control-flow-generating-thunk ? but now there's a language requirement for the programmer to tag their fibonacchi generators as 'lazy'..

ok this is getting complicated, let's go back and look at what we know about the design space:

---

the design space:

after the compiler executes, we can tell the runtime either:
- be lazy,
- be strict,
- you decide, and it is safe to decide 'strict', and here is what i know
- you decide, and it is safe to decide 'lazy', and here is what i know
- you decide, and it is safe to decide either 'strict' or 'lazy', and here is what i know
- you decide, and i'm not promising that either one is safe, and here is what i know

if we never say 'you decide', then dynamic analysis is not allowed.

if the compiler never says to the runtime 'you decide, and i'm not promising that either one is safe', then you could do without a runtime by defaulting to either lazy or strict depending on which one the compiler guarantees is safe.

by contrast, if the compiler can't make either guarantee, and sometimes says that last thing, then whatever guarantees the language wants to provide must be guaranteed by the runtime. If these involve maintaining metadata about stuff, then the runtime will have to maintain that.

in any one case, the choice between 'strict' or 'lazy' might: (1) have exactly one 'crashing' choice, in that one choice requires infinite time or infinite memory and the other choice requires neither infinite time nor infinite memory, (2) have no crashing choice, and has at least one 'right' choice, in that one choice takes finite time and finite memory and no more time and no more memory than the other choice would, (3) be a tradeoff, meaning that one choice takes more time and the other takes more memory, but in both cases the amount of time or memory required is finite (4) have no possible solution, in that both choices take either an infinite amount of time or an infinite amount of memory.

Assuming the programmer didn't choose strict or lazy explicitly, the language must choose (at compile time or at runtime).

now some hypotheses:

In case (1) we really want the compiler to make the right choice. It would be nice if in case (2) the compiler would right choice. It would be nice if the compiler provided us with a type system that allowed us to at least sometimes prove that case (4) is not the case. We don't care much what the compiler does in case (3).
the danger of saying 'strict' too often is that we might try to strictify a thunk that generates an infinite data structure (a case (1) problem)
the danger of saying 'lazy' too often is that we might generate a thunk whose 'vertical size' (count of longest chain of thunk-within-thunk) in memory is non-constant, when by strictifying we could have made its vertical size constant (a case (2) problem)
both of the previous two might be considered "dangerous", the former because it requires infinite time, the latter because it requires finite yet infeasibly much memory; in both cases the program 'crashes' on reasonably small inputs, either by hanging or by an out-of-memory error.
we'd like the language to guarantee avoidance of these dangerous outcomes where it is feasible to do so
we don't care about guaranteeing that we can avoid non-dangerous yet inefficient outcomes (the programmer can optimize that via annotations later)
we'd like to never say to the runtime 'you decide, and i'm not promising that either one is safe', unless what the runtime has to do to meet the language guarantees is sufficiently simple and sufficiently non-intrusive

---

so now back to ideas:

we can avoid voluntarily strictifying an infinite data structure if we keep track of the point in source code corresponding to each head of the thunk, and stop if we iterate through heads from the same bit of source code more than n times
- but, this would also stop us if we hit eg multiple 'map's in the thunk, even if those maps weren't recursively related to each other, e.g. "g x y = map (\z -> or . map f x) y"

note that in that example, we see the maps stacked lexically in the source code

so in that example we could avoid unnecessary laziness by, at compile-time, set n to be greater than the amount of lexically stacked calls to the same function. But in general, we might pull out a subexpression into a separate function, even one in a separate module.

however, you could just count the total number of occurences of each function in the source.

but, you could do e.g. "f (\z -> g(h))"; now if f = g = h then you have a depth-3 stack of some function, even if that function's name only appears once.

still, you could just count the greatest observed lexical depth in the source.

but, you could have f(x) = x + 1; g(x) = f(f(x)); h(x) = g(g(x)). h(x) = g(g(x)) = g(f(f(x))) = f(f(f(f(x)))).

so, it's the sum of all lexical depths observed over the whole program.

note that an interpreter might 'benignly' exceed that (e.g. their runtime recursion through the same piece of source code in a thunk might exceed the sum of all lexical depths observed over the whole program); but, that makes sense, that's just the sort of thing we're trying to catch, because we can't make guarantees about an interpreter's benignness; so a programmer writing such an interpreter who wants voluntary strictification must add strictness annotations.

we can avoid voluntarily creating a non-constant lazy data structure if, for each thunk, we keep track of the point in source code which is adding each new thunk on top of the existing thunk, and strictify if we find that a thunk has had more than n heads added by the same point in source code

so you get the idea:

for each thunk head, keep track of:
- (a) the location of the expression in the source code from which it was generated
- (b) the location of the expression in the source code which ordered it to be generated (e.g. the location of control flow at the time it was generated)
as you lazily build thunks, maintain a count of the highest vertical column of each (b) src code location within (e.g. if an expression is "f(g,h)", and f,g,h are themselves thunks, then for each location in any of g,h, take the greatest count of that location over all of g,h, and make that the count of (g,h); now add to it the count of that location in f, and also to the tracking table, add f's count of any locations not found in either g or h; i think). Any thunk head annotated 'lazy' by the programmer has all counts set to 0. This table of counts travels with the thunk. If any count exceeds n, then (voluntarily?) strictify.
- is it safe to just compare the total thunk depth to the thunk length, regardless of source code location, so you only have to maintain one count?
as you voluntarily strictify thunks, maintain a count of each (a) src code location of the heads that you have removed. Don't add to the count when the head is annotated strict by the programmer. If it exceeds n, then abort the voluntarily strictification
for each module, n is the sum of the variable lexical nestings plus the greatest constant lexical nesting found in that module
for the whole program, n is the sum of the modules

let's think about both simplifying proposals:

just count the total thunk lengths, rather than specific locations in the program
if strictification is triggered by the laziness count, it is voluntary, so the voluntary strictness count might abort it

i dunno if those are kosher, but if they are, that leads to relatively simple guarantees and implementation:

guarantee:

for any particular program, there is a finite bound on the depth of any explicitly represented nested chain of thunks (which are all consecutively not marked 'lazy')
for any particular program, there is a finite bound on the number of thunks that will be expanded in any one evaluation step, not counting thunks marked 'strict' or thunks below a thunk marked 'recursive strictify'

note: to handle the foldl case as well as the foldr case, we do this will closures as well a thunks (if they are different), see http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27

so, imagine the foldr and foldl case in http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27 . We still seem to be stymied; without knowing that + is associative, even when the runtime notices that our chain is too long, it can't do anything about it. In the foldr case, we have something of the form

1 + (2 + (3 + (4 + (foldr (+) 0 [5..1000000]))))

the point is, you can't just 'reduce' thunks on demand without associativity.

but in the foldl case, we have something of the form

> foldl f z [] = z > foldl f z (x:xs) = let z' = z `f` x > in foldl f z' xs

let z1 = 0 + 1 z2 = z1 + 2 z3 = z2 + 3 z4 = z3 + 4 ... in (((z999996 + 999997) + 999998) + 999999) + 1000000

By comparision, foldl' goes:

> foldl' f z [] = z > foldl' f z (x:xs) = let z' = z `f` x > in seq z' $ foldl' f z' xs

> sum3 = foldl' (+) 0

> try3 = sum3 veryBigList

foldl' (+) 0 [1..1000000] --> foldl' (+) 1 [2..1000000] --> foldl' (+) 3 [3..1000000] --> foldl' (+) 6 [4..1000000] --> foldl' (+) 10 [5..1000000] -->

so, here we should be able to figure out that we can reduce z1 when the chain gets too long

however, does this has problems with the same cases that foldl' does?

" if the combining function is lazy in its first argument, foldl may happily return a result where foldl' hits an exception:

> (?) :: Int -> Int -> Int > _ ? 0 = 0 > x ? y = x*y > > list :: [Int] > list = [2,3,undefined,5,0] > > okey = foldl (?) 1 list > > boom = foldl' (?) 1 list

Let's see what happens:

okey --> foldl (?) 1 [2,3,undefined,5,0] --> foldl (?) (1 ? 2) [3,undefined,5,0] --> foldl (?) ((1 ? 2) ? 3) [undefined,5,0] --> foldl (?) (((1 ? 2) ? 3) ? undefined) [5,0] --> foldl (?) ((((1 ? 2) ? 3) ? undefined) ? 5) [0] --> foldl (?) (((((1 ? 2) ? 3) ? undefined) ? 5) ? 0) [] --> ((((1 ? 2) ? 3) ? undefined) ? 5) ? 0 --> 0

boom --> foldl' (?) 1 [2,3,undefined,5,0] --> 1 ? 2 --> 2 foldl' (?) 2 [3,undefined,5,0] --> 2 ? 3 --> 6 foldl' (?) 6 [undefined,5,0] --> 6 ? undefined --> * Exception: Prelude.undefined "

if you treat 'undefined' as an immediate error, yes. However, if you treat 'undefined' as a (runtime detectable) shorthand for an infinite recursion, then this would merely cause the voluntary strictification to abort when 'undefined' is reached.

So in conclusion, (assuming associativity is markable and is used by the voluntary strictification) this approach still has trouble with foldr with non-associative operators, but otherwise seems good. One could imagine that a sufficiently smart compiler could statically identify foldr-like situations used with operators that haven't been declared associative, and throw a warning.

---

although thunks are made of expressions, and the laziness/strictness annotations therefore correspond to places in the source code, there may be times (such as in an interpreter) when the programmer wants to dynamically say whether a given thunk should be treated strictly or not. So perhaps we should allow dynamic modification of 'treat the head of this thunk lazily or strictly'.

note that the language should also have a 'recursive strictify' bit, e.g. if you encounter that in a thunk, not only do you evaluate the head one more time, but you continue recursively evaluating the result until you can't anymore.

---

toread taming laziness http://iris.lib.neu.edu/cgi/viewcontent.cgi?article=1037&context=comp_sci_diss

On the relationship between laziness and strictness stephen chang

summary: Looks like a good paper (its a dissertation, actually) for its literature refs, but ultimately it is concerned with efficiency and presents a static analysis, whereas i'm mainly concerned with the minimal/simplest things that could be done to ensure (or at least make likely) that the program does not unexpectedly hang by trying to strictify an infinite data structure, but also does not unexpectedly run out of memory by lazily creating a long chain of thunks that could have been evaluated. Also, this dissertation is trying to make initially strict programs more efficient by automatically adding laziness, which i guess means it isn't considering programs which have infinite data structures to start with ("This dissertation tackles the laziness problem from the relatively-unexplored, strict-evaluation-first end of the spectrum. We are not aware of any work that looks to automatically insert laziness into strict programs".)

more comments: Is the thing i proposed above similar to 'stingy evaluation' (section 2.2.1, Subtracting Laziness, copied below)? Or maybe its more like "Eager Haskell: resource-bounded execution yields efficient iteration", whose abstract reads 'The advantages of the Haskell programming language are rooted in its clean equational semantics. Those advantages evaporate as soon as programmers try to write simple iterative computations and discover that their code must be annotated with calls to seq in order to overcome space leaks introduced by lazy evaluation. The Eager Haskell compiler executes Haskell programs eagerly by default, i.e. , bindings and function arguments are evaluated before bodies. When resource bounds are exceeded, computation falls back and is restarted lazily. By using a hybrid of eager and lazy evaluation, we preserve the semantics of Haskell and yet permit efficient iteration.'. Also, 'lenient evaluation' looks pretty cool, especially in the context of Oot's 'massive parallel' use-case/assumptions.

2 . 2 . 1 Subtracting Laziness The most well-known technique to remove laziness from lazy programs is strictness analysis [ 10 , 16 , 37 , 39 , 42 , 57 , 79 , 84 ], which statically removes lazi- ness by estimating which thunks would be forced during evaluation without introducing non-termination. Others have introduced additional static techniques that build on strict- ness analysis to remove even more laziness. Faxén [ 23 ] uses a whole-program analysis that utilizes labeled types and type inference [ 22 ] to identify “cheap eagerness.” The analysis maps labeled expressions to “costs” and expressions with low enough cost are evaluated strictly. Boquist [ 9 ] uses an analysis to identify promises that can be removed in case expressions. Researchers have also explored the idea of combining strict and lazy eval- uation in a dynamic setting. In “stingy” evaluation [ 77 ] expressions are eval- uated strictly, but only for a short period of time, thus yielding only a small occasional improvement. Maessen [ 51 ] and Ennals and Peyton Jones [ 20 ] ad- ditionally introduced similar strict-by-default mechanisms. In both their sys- tems, programs are evaluated eagerly but various runtime heuristics deter- mine when to suspend the computation to preserve lazy semantics. Id [ 60 ] and pH [ 1 ], are two languages that try to exploit parallelism in pro- grams using a technique called lenient evaluation, which is a blend of lazy and strict evaluation. To leniently evaluate a function call, the arguments and function body are eagerly evaluated at the same time. When a computation needs the value from another computation, it blocks if the other value is not ready. If some computation, a function argument for example, is not used, then the program never waits for its completion, so it does not affect evalua- tion of the final answer, even if that computation never terminates. Therefore, though function calls are evaluated eagerly, lenient evaluation ultimately im- plements a non-strict semantics. The previous techniques experienced varying degrees of success. Faxén’s cheap eagerness seems to gain the most improvement with regard to fixing space leaks during tail-recursive iterations. The dynamic strategies [ 20 , 51 ] successfully meet their goal of efficient iteration while still handling infinite data structures (i.e., non-termination) with a reasonable amount of overhead. But these strategies sometimes remove too much laziness, for example where laziness is beneficial in finite programs [ 62 ]. Strictness analysis is the sole technique that sees practical use today, though it too struggles to handle tail- recursive iteration and leaves too much laziness in the program. 2 . 2 balancing lazy and strict 17 Overall, it seems that the prior strategies have not quite found an ideal balance of lazy and strict, as real-world lazy programmers still resort to man- ually annotating their programs with strictness annotations such as seq [ 63 ] and bang ( ! )

cites:

skimmed. a clear, easy to read paper. strictness analysis seems to be a compile-time analysis that figures out which functions are strict in which arguments by starting out knowing how a basis set of functions are strict and then computing how functions built from them are strict. There are some wrinkles when it comes to recursion, etc, and this paper describes algorithms for dealing with these cases too.

[ 16 ] Chris Clack and Simon L. Peyton Jones. Strictness analysis—a practi- cal approach. In FPCA ’ 85

: Proceedings of the 2 nd ACM Conference on Functional Programming Languages and Computer Architecture , pages 35 – 49 , 1985

looked at the abstract and at talk slides (see below), looks like this is about doing speculative execution to improve efficiency and then doing VM hotspot-like runtime tuning to stop speculatively executing expressions that in the past didn't help much, so not what i'm looking for:

[ 20 ] Robert Ennals and Simon Peyton Jones. Optimistic evaluation: an adap- tive evaluation strategy for non-strict programs. In ICFP ’ 03

: Proceedings of the 8 th ACM SIGPLAN International Conference on Functional Program- ming , pages 287 – 298 , 2003 .

looked the the first page of this paper, looks like it is about using global static flow analysis to increase efficiency, not what i'm looking for:

[ 23 ] Karl-Filip Faxén. Cheap eagerness: speculative evaluation in a lazy func- tional language. In ICFP ’ 00

: Proceedings of the 5 th ACM SIGPLAN Inter- national Conference on Functional Programming , pages 150 – 161 , 2000 .

toread, may be good: [ 51 ] Jan-Willem Maessen. Eager Haskell: resource-bounded execution yields efficient iteration. In Proceedings of the ACM SIGPLAN Workshop on Haskell , pages 38 – 50 , 200

the "cheap eagerness" paper cites Mycroft "the theory and practice of transforming call-by-need into call-by-value" and says it requires global compiler analysis, so it's probably not what i'm looking for, although this is a different paper. [ 57 ] A Mycroft. Abstract interpretation and optimising transformations for applica- tive programs . PhD? thesis, University of Edinburgh, 1981 .

great read, but not relevant to my current question (talks about times where laziness is and isn't useful in R):

[ 55 ] Floréal Morandat, Brandon Hill, Leo Osvald, and Jan Vitek. Evaluating the design of the R language. In ECOOP ’ 12

: Proceedings of the 26 th Euro- pean Conference on Object-Oriented Programming , pages 104 – 131 , 2012 .

skimmed, doesn't seem to have much for me, the later paper "Lenient evaluation is neither strict nor lazy" is more up my alley:

[ 69 ] Klaus E. Schauser and Seth C. Goldstein. How much non-strictness do lenient programs require? In FPCA ’ 95

: Proceedings of the 7 th ACM Conference on Functional Programming Languages and Computer Architecture , pages 216 – 225 , 1995 .

weird edge case? in any case talking about adding lazy to strict, so probably not what i want:

[ 80 ] Philip Wadler, Walid Taha, and David MacQueen?. How to add laziness to a strict language, without even being odd. In Proceedings of the Workshop on Standard ML , 1998 .

---

Ennals' Optimistic Evaluation: http://www2.berkeley.intel-research.net/~rennals/pubs/talk_opt.pdf

" Strictness Analysis

Expressions that are certain to be used. Cheapness Analysis
Expressions that are certain to be cheap

BUT: Such analyses must be conservative. Almost always cheap or Almost always used are missed

...

Speculative Evaluation Evaluate expressions eagerly, in the hope that they are cheap Eager Haskell : J-W Maessen Evaluate every expression eagerly, in the hope that it is cheap. Impose a timeout on how long we can speculate for. Abort all speculation when this timeout is reached. Good average performance But very bad performance in some cases. (100x slowdown) If speculation moderately expensive, but unneeded. Not sufficient to just use a small timeout Consider a thunk that has moderate cost, but is always used. Optimistic Evaluation (ICFP2003) Robert Ennals and Simon Peyton-Jones 5 / 21 Optimistic Evaluation Use runtime profiling to determine what to speculate Switchable Let Expressions: Decide at runtime whether to speculate their right hand side Runtime Profiling: (guarantees efficiency) Like strictness and cheapness analysis, but at runtime. Find out whether speculating a let is saving or wasting work. Abortion: (guarantees correctness) Recovers from ill-judged speculative evaluation Chunky Evaluation: Allows large lazy structures to be evaluated in chunks.

http://ennals.org/rob/archive/intel/pubs/icfp2003.pdf

" ABSTRACT Lazy programs are b eautiful, but they are slo w b ecause they build man y th unks. Simple measuremen ts sho w that most of these th unks are unnecessary: they are in fact alw a ys ev aluated, or are alw a ys c heap. In this pap er w e describ e Optimistic Ev aluation

an ev aluation strategy that ex- ploits this observ ation. Optimistic Ev aluation complemen ts compile-time analyses with run-time exp erimen ts: it ev alu- ates a th unk sp eculativ ely , but has an ab ortion mec hanism to bac k out if it mak es a bad c hoice. A run-time adaption mec hanism records expressions found to b e unsuitable for sp eculativ e ev aluation, and arranges for them to b e ev alu- ated more lazily in the future. W e ha v e implemen ted optimistic ev aluation in the Glas- go w Hask ell Compiler. The results are encouraging: man y programs sp eed up signi can tly (5-25%), some impro v e dra- matically , and none go more than 15% slo w er "

" Stingy Evaluation [39] is an evaluation strategy designed to reduce space leaks such as the one described in Section 6.2. When evaluating a let expression, or during garbage collection, the evaluator does a little bit of work on the ex- pression, with the hope of evaluating it, and avoiding havingto build a thunk. As with Eager Haskell, all expressions are eagerly evaluated, however the amount of evaluation done before abortion is significantly smaller, with only very simple evaluations allowed. Often this small amount of work will not be useful, causing some programs to run slower. Stingy evaluation was implemented in the LML [1] compiler. "

http://www.haskell.org/haskellwiki/Lazy_vs._non-strict

" 3 Further references

Laziness is simply a common implementation technique for non-strict languages, but it is not the only possible technique. One major drawback with lazy implementations is that they are not generally amenable to parallelisation. This paper states that experiments indicate that little parallelism can be extracted from lazy programs:

"The Impact of Laziness on Parallelism and the Limits of Strictness Analysis" (G. Tremblay G. R. Gao) http://citeseer.ist.psu.edu/tremblay95impact.html

Lenient, or optimistic, evaluation is an implementation approach that lies somewhere between lazy and strict, and combines eager evaluation with non-strict semantics. This seems to be considered more promising for parallelisation.

This paper implies (section 2.2.1) that lenient evaluation can handle circular data structures and recursive definitions, but cannot express infinite structures without explicit use of delays:

"How Much Non-strictness do Lenient Programs Require?" (Klaus E. Schauser, Seth C. Goldstein) http://citeseer.ist.psu.edu/schauser95how.html

Some experiments with non-lazy Haskell compilers have been attempted: Research_papers/Runtime_systems#Optimistic_Evaluation "

Lenient evaluation is neither strict nor lazy citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.137.9885 by G Tremblay - ‎2000 - ‎Cited by 2 - ‎Related articles

" As it will be seen in more detail in Section 4, one of the feature that really distinguishes le- niency from laziness is the ability of the latter to deal with potentially in3nite computation without generating an unbounded amount of unneeded computation. Here is a simple example: f x=x:f (x + 1) head (tail (f 0)) Function f generates an in3nite list of numbers starting from x —the operator “ : ” is the list construc- tor; here, it combines an integer and a list to produce a new list having the indicated integer as 3rst element. The result expression then retrieves the second element of this in3nite list of numbers; since the list starts at 0 , the expression thus evaluates to 1 . In a lazy language, the correct result would be produced and no unneeded computation would be performed, since evaluation of all but the 3rst right-hand side of “ : ” would be delayed—in other words, only the 3rst recursive call to f would not be delayed. On the other hand, a lenient language might well produce the correct result, as long as the strategy used by the implementation to select the work to be done is fair, so that a computation that becomes ready eventually gets performed. However, since leniency does not require delaying the evaluation of the right-hand side of “ : ”, a real (instead of only potentially) in3nite list would be generated and, thus, execution would not terminate or would terminate because of lack of memory. "

ok it seems to me this is not necessarily a problem; just keep track of how much time/memory you are spending on speculative execution and results, and manage that.

" Cheap Eagerness: Speculative Evaluation in a Lazy Functional Language Karl-Filip Fax ́en Dept. of Teleinformatics, KTH, Stockholm kff@it.kth.se

Cheap eagerness is an optimization where cheap and safe expressions are evaluated before it is known that their values are needed. Many compilers for lazy functional languages implement this optimization, but they are limited by a lack of information about the global flow of control and about which variables are already evaluated. Without this information, even a variable reference is a potentially unsafe expression! In this paper we show that significant speedups are achievable by cheap eagerness. Our cheapness analysis uses the results of a program-wide data and control flow analysis to find out which variables may be unevaluated and which variables may be bound to functions which are dangerous to call. 1. "

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.13.333&rep=rep1&type=pdf

the first page of the paper has some informative stuff, but annoyingly i can't copy and paste from it.

variable refs seem to be 'potentially unsafe' because they can throw exceptions (?). imo that's pretty simple, if a non-benign side-effect is about to occur in speculatively executed code, suspend.

The other dissertation says "Faxén [23] uses a whole-program analysis that utilizes labeled types and type inference [22] to identify “cheap eagerness.” The analysis maps labeled expressions to “costs” and expressions with low enough cost are evaluated strictly"

The cheap eagerness paper confirms that this technique uses a global flow-control analysis provided by the compiler. So this is not what i'm looking for. It cites Mycroft as earlier work, and says it also used global analysis. So i don't need to read that one, either.

todo: add these papers to plbook

todo: add the concept of 'benign side-effect' to plbook

---

" R does not prevent the declaration of ambiguous multi-methods. At each method call, R will attempt to find the best match between the classes of the parameters and the signatures of method bodies. Thus add(r, l) would be treated as the addition of two “Point” objects. The resolution algorithm differs from Clos’s and if more than one method is applicable, R will pick one and emit a warning. One unfortunate side effect of combining generic functions and lazy evaluation is that method dispatch forces promises to assess the class of each argument. Thus when S4 objects are used, evaluation of arguments becomes strict " -- http://r.cs.purdue.edu/pub/ecoop12.pdf

---

Observations. One of our discoveries while working out the semantics was how eager evaluation of promises turns out to be. The semantics captures this with C [] ; the only cases where promises are not evaluated is in the arguments of a function call and when promises occur in a nested function body, all other references to promises are evaluated. In particular, it was surprising and unnecessary to force assignments as this hampers building infinite structures. Many basic functions that are lazy in Haskell, for example, are strict in R, including data type constructors. As for sharing, the semantics cleary demonstrates that R prevents sharing by performing copies at assignments. The R implementation uses copy-on-write to reduce the number of copies. With super- assignment, environments can be used as shared mutable data structures. The way assignment into vectors preserves the pass-by-value semantics is rather unusual and, from personal experience, it is unclear if programmers understand the feature. Extending the semantics to supporting reflection and objects should be possible. Objects are encoded by vectors with attributes that hold their class, as a vector of strings, fields. Methods are functions that abide by a particular naming convention. Dispatch is done by reflecting over defined functions. It is noteworthy that objects are mutable within a function (since fields are attributes), but are copied when passed as an argument.

---

With the exception of [ 13 ], which mistakenly characterized R as strict and imperative, ours is the first attempt to introduce R to a mainstream computer science audience.

Speculative Evaluation in the Glasgow Haskell Compiler

Robert Ennals and Simon Peyton-Jones wrote a paper about a fork of GHC 5.04 that used speculative evaluation.

In essence you got the strengths of Eager Haskell without a huge change in behaviour. The approach was to execute rather than thunk, up to a configurable thunk depth but never across IO or other places where optimistic evaluation would change semantics. Speculative evaluation also allowed for a procedural-style debugger that worked as you would expect.

Sadly, the internal changes to GHC were drastic, so the changes weren't folded into GHC proper. Speculative evaluation is the best approach I've seen that keeps the beauty and elegance of non-strict evalution while increasing speed and predictability.

--Shae Erisson - ScannedInAvian?.com By shapr at Wed, 2005-01-19 15:18

---

" Bryn Keller - Eager Haskell blueArrow 6/4/2002; 4:00:11 PM (reads: 2356, responses: 2) Eager Haskell Jan-Willem Maessen's dissertation, Hybrid Eager and Lazy Evaluation for Efficient Compilation of Haskellthesis has recently been released, and the author says an implementation is on the way:

I'm presently working hard on making a production-quality version of the Eager Haskell compiler. If you have any questions about Eager Haskell, or would like to see a pre-release version of the compiler along with the programs I used as benchmarks, drop me a line. A full release of the unified pH / EH compiler is slated for mid-August.

Here's the first paragraph of the abstract:

The advantage of a non-strict, purely functional language such as Haskell lies in its clean equational semantics. However, lazy implementations of Haskell fall short: they cannot express tail recursion gracefully without annotation. We describe resource-bounded hybrid evaluation, a mixture of strict and lazy evaluation, and its realization in Eager Haskell. From the programmer's perspective, Eager Haskell is simply another implementation of Haskell with the same clean equational semantics. Iteration can be expressed using tail recursion, without the need to resort to program annotations. Under hybrid evaluation, computations are ordinarily executed in program order just as in a strict functional language. When particular stack, heap, or time bounds are exceeded, suspensions are generated for all outstanding computations. These suspensions are re-started in a demand-driven fashion from the root.

" -- http://lambda-the-ultimate.org/classic/message3516.html

" More Haste, Less Speed The Complexity of Lazy Evaluation Richard Bird, Geraint Jones and Oege de Moor

We have shown, we believe for the first time, that lazy evaluation of functional programming languages is strictly more powerful than eager evaluation, as measured by the asymptotic complexity of evaluating certain programs.

One of the attractions of functional programming languages - ones that do not use assignments - is that programs consist in essence of mathematical equations, and can be reasoned about by everyday mathematical techniques such as the substitution of an expression for any other which is equal to it.

However, the most straightforward way of implementing a set of equations as a program - eager evaluation as it is called - evaluates the arguments of functions first, and only then applies those functions. It turns out to be relatively straightforward to estimate the execution time of functional programs under an eager evaluation strategy, but it is hard to reason about the value produced: applying a constant function to a non-terminating expression leads to a non-terminating program, rather than returning the constant. This interferes with equational reasoning: you cannot always substitute for each other the value of the constant and an application of a constant function.

Soundness of equational reasoning comes from normal order evaluation, in which functions are applied to unevaluated arguments, although if many copies are made of an unevaluated argument it might have to be evaluated many times, at great cost in execution time. Languages such as Haskell use lazy evaluation, which applies functions to arguments whose evaluation is postponed until the first (but only the first) time their values are needed. This ensures that equational reasoning about the values of programs is sound, at the expense of making it extremely hard to reason about when expressions are evaluated, and to estimate how much work is involved in doing so. We are interested in exploiting the elegance and power of lazy evaluation, but also in developing techniques to measure the cost of doing so.

Nicholas Pippenger showed that under certain simple restrictions, problems that can be solved in linear time in a language with assignments must take longer (by a logarithmic factor) in an eagerly evaluated purely functional language. Our paper (Journal of Functional Programming, 7(5):541-547, September 1997) shows that a lazy functional program solves Pippenger's problem in linear time. This demonstrates that lazy evaluation is strictly more efficient - in asymptotic terms - than eager evaluation, and that there is no general complexity-preserving translation of lazy programs into an eager functional language. " -- http://www.cs.ox.ac.uk/people/geraint.jones/morehaste.html ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Geraint.Jones/FP-1-96.ps.Z

" Optimistic evaluation decides at run-time what should be evaluated eagerly, and provides an abortion mechanism that backs out of eager computations that go on for too long....

Eager Haskell [20, 19] was developed simultaneously, but independently, from our work. Its basic premise is identical: use eager evaluation by default, together with an abortion mechanism to back out when eagerness turns out to be overoptimistic. "

" Speculative evaluation did have one nifty benefit, it allowed a 'standard' debugger that gave readable stack traces. "

" On the other hand, I swapped some emails with Robert Ennals, one of the authors of the Optimistic Evaluation paper. He said,

    My general feeling now, after studying lazy evaluation for a few years, is
    that, while it can be very useful sometimes, it usually isn't what you want,
    and thus that lazy languages are a bad idea."

---

HsDebug?: debugging lazy programs by not being lazy

HsDebug?: Deb ug ging Lazy Pr ograms b y Not Being Lazy Rober t Ennals Computer Labor ator y , Univ ersity of Cambr idge Rober t.Ennals@cl.cam.ac.uk Simon P e yton Jones Microsoft Research Ltd, Cambr idge simonpj@microsoft.com 1 Moti v ation Deb ugging has long been recognised as one of the weaknesses of lazy functional languages. Con v entional (strict, imperati v e) languages almost in v ariably use the ìstop, e xamine, continueî paradigm (Section 2), b ut this approach just does not w ork well for with lazy e v aluation. This dif culty has led to f ascinating research in no v el deb ugging techniques (Section 7). W e ar gue that con v entional deb ugging techniques ha v e perhaps been dismissed too quickly . W e present tw o alterations to the e v aluation model of lazy functional languages that allo w con v en- tional deb ugging techniques to be successfully applied. T ransient tail frames allo w tail-calls to be visible to the deb ugger without af- fecting space comple xity (Section 4). Optimistic Ev aluation causes e v aluation to only use laziness when absolutely necessary , thus pre- serving the termination beha viour of Lazy Ev aluation, while reduc- ing its confusing ef fect on program state (Section 5). W e ha v e implemented these ideas in HsDeb? ug, an e xtension to the GHC tool set (Section 6). Our deb ugger is, by design, ìcheap and cheerfulî. Its results are not as predictable, nor as user -friendly , as those of (say) Hat ó b ut the y come cheap. HsDeb? ug can deb ug an entirely un-instrumented program, and it can do a lot better if the compiler deposits modest deb ug information (much lik e a con v en- tional deb ugger). Furthermore, an arbitrary subset of the program can be compiled with deb ug information ñ in particular , the libraries need not be. Furthermore, program transformation and optimisation are unaf fected.

--- " 5) Languages will start showing up looking to be the successor to Haskell. These languages will have Hindley-Milner type systems, be purely functional, and use monads, but will not be lazily evaluated. The goal of these languages will be to solve the problems Haskell has with space leaks and judging space/time costs of complicated algorithms in "production" code. Note that none of these languages will actually manage to dislodge Haskell from being king of theoretical hill (at least in 2008, and maybe not ever), I'm just saying they'll start showing up. ...

Eager Haskell

    I don't think there is such a strong demand for a successor to Haskell. I think we'll instead see the recent trend of pragmatism to continue for a while longer.

Agreed. Haskell's direction is and will continue to be driven by the research community. Pure and eager aren't that interesting a research combination, even if there is some pragmatic value in it. And the industrial community that values the pragmatism of eagerness doesn't yet know how to evaluate the pragmatism of purely functional code.

Some future Haskell-like purely functional eager language is certainly possible, but not in 2008 - not with any significant up-take in either the industrial or research settings. I can safely predict, 10 or 20 years from now when language X is hot, some Paul Graham like pundit will be saying "I don't understand why X is getting so much attention now - Haskell did all that decades ago and did it better." :-) By James Iry at Mon, 2008-01-14 20:06

---

http://lambda-the-ultimate.org/node/1248

Haskell is not not ML

Haskell is not not ML. Ben Rudiak-Gould, Alan Mycroft, and Simon Peyton Jones. European Symposium on Programming 2006 (ESOP'06).

    We present a typed calculus IL ("intermediate language") which supports the embedding of ML-like (strict, eager) and Haskell-like (non-strict, lazy) languages, without favoring either. IL's type system includes negation (continuations), but not implication (function arrow). Within IL we find that lifted sums and products can be represented as the double negation of their unlifted counterparts. We exhibit a compilation function from IL to AM --- an abstract von Neumann machine --- which maps values of ordinary and doubly negated types to heap structures resembling those found in practical implementations of languages in the ML and Haskell families. Finally, we show that a small variation in the design of AM allows us to treat any ML value as a Haskell value at runtime without cost, and project a Haskell value onto an ML type with only the cost of a Haskell deepSeq. This suggests that IL and AM may be useful as a compilation and execution model for a new language which combines the best features of strict and non-strict functional programming.

The authors start from the claim that most of the differences between SML and Haskell are independent of evaluation order. Is it possible, they wonder, to design a hybrid language which in some way abstracts over possible evaluation orders?

This papers leaves the language design for future work, and concentrates on the implementation costs. The results seem positive, so one hopes this project will mature and end the civil war between lazy and eager functional programming...

More information on this project is likely to appear here. By Ehud Lamm at 2006-01-23 18:02

Functional

Implementation

other blogs

8694 reads

Hard

This paper isn't easy. Feel free to use LtU? for help. By Ehud Lamm at Mon, 2006-01-23 18:26

reminds me of call-by-push-value

The IL described in section 2, and the translation from strict and non-strict languages into the IL are strongly reminiscent of Paul Blaine Levy's call-by-push-value. Both the IL and the CBPV calculus classify expressions so as to disallow certain expressions where you might expect them. For example, the components of a tuple must be non-0 type in IL, while in CBPV they must be values. Unfortunately, at the end of a long day I'm not up to the task of sorting out the similarities and differences.

Last year, motivated by Wadler's dual calculus to bring together strict and non-strict evaluation, I developed my toy language Ambidexter. The current interpreter is worth a look. Rather than "abstract over possible evaluation orders" it puts the two on an equal footing and permits conversions back and forth. By Scott Turner at Tue, 2006-01-24 02:13

---

What type of laziness?

There are two sorts of laziness out there. The first is optional laziness, such as is found in Ocaml. In this case, most of the program is evaluated eagerly, but some computations can be marked as lazy (in Ocaml, the 'lazy' keyword introduces a lazy evaluation, that can be forced with a call to Lazy.force).

This level of laziness is usefull in developing purely purely functional data structures. I did a short introduction here on the usefullness of lazy lists, even in an eager language like Ocaml.

The other "style" of laziness is pervasive laziness, like Haskell. This does bring some advantages- for example, laziness has kept Haskell pure, and made it easier for Haskell to parallelize (unlike, for example, Ocaml). Also, it opens up possibilities for high level optimizations which are either incredibly difficult to do or generally not worth it in a language like Ocaml. For example, it is always true in Haskell that map f (map g lst) is the exact same as map (f . g) lst . This is true for all functions f and g, and all lists, in Haskell- it is not true for all functions and all lists in Ocaml (hint: what happens if f or g has side effects?). And thus Haskell doesn't have to perform tricky and complicated tests to see if the transformation is safe. In addition to eliminating the intermediate data structure, this transformation has also opened up new optimization possibilities (the function (f . g) can be specialized and inlined in many cases).

There are downsides to pure laziness as well. For example, based on results from the Great Computer Language Shootout (where Haskell is performance competitive with Java and C#), laziness costs about as much as executing in a virtual machine. Plus, you have the problem of space leaks. By bhurt-aw at Wed, 2007-05-30 13:02

---

Thank-you so much for writing that blog post discussing the usefulness of lazy lists. I think that I actually understand now. Of course, I had heard the phrase "separating generation from selection" before, but that didn't really mean anything to me. If anyone reading this is even slightly fuzzy on why lazy lists are so great, read that post!

PS: First post. I've lurked here for a while, but this is the first thing that's made me feel the overwhelming need to write a comment. Thanks again, bhurt-aw! By nobodysbusiness at Fri, 2007-06-01 16:35

---

toread: http://lambda-the-ultimate.org/node/2273

---

toread: http://stackoverflow.com/questions/10784124/non-lazy-branch-of-ghc

---

" So there are two kinds of laziness to distinguish in Haskell. There's lazy I/O, which is an abomination and is solved by iteratee libraries (Shameless plug: including my pipes library). Then there's laziness in pure computations... "

---

the best description i've seen yet of Eager Haskell. Also related it to pH:

http://csg.csail.mit.edu/pubs/haskell.html

---

http://www.haskell.org/pipermail/haskell/2002-May/009801.html

My dissertation, "Hybrid Eager and Lazy Evaluation for Efficient Compilation of Haskell", is now available on the web: http://www.csg.lcs.mit.edu/~earwig/thesis.html

---

according to my new idea, the language runtime should have dual 'counts': count strictification iterations (reducing) and stop if there are too many (so you don't autostrictify an infinite data structure), and count upwards-going levels of towers of lazy thunks (a thunk that references a thunk that references a thunk, etc) to make sure you don't build too high

this inspires one to make the strictness annotations dual, too: you can annotate data to be lazy, but not strict; and you can annotate expressions to be strict, but not lazy.

the reason is that you want expressions like: any = or map to work efficiently (eg to short-circuit after a True is found); you don't want someone to pass in inputs that are marked 'strictify anything computed with these' that force the map to execute over everything before the 'or' is reached

similarly, you want ("stream fusion"?) to work; you want to be able to write:

f = \coll -> map inc (map timesTwo coll)

and to have it be implemented by ONE loop over the collection, not two. Again, if 'coll' can be mapped 'strictify anything using this', that'll break that

in addition, you might sometimes want to recursively strictify PART of an expression without strictifying all the way down. E.g.

def f(x): f2 = something(x) f3 = something_else(f2) r = something3(f3) return r

you might want to say "strictify all of the transformations applied to x, that is, all of the transformations IN BETWEEN x and r, but don't strictify x itself, because x might be an infinite data structure. You could just use 'seq' all over the place but that's tedious. In analogy with delimited continuation, we might call this "delimited strictification"

---

i feel like the key will actually just be to offer 'local' or 'regional' deepseq ('local' or regionally 'strict' functions), that is, functions deepseq their inputs, except that have a concept of 'current deepseq scope', and thunks that originate from code outside of the current deepseq scope terminate the recursive evaluation.

In other words, there is a current 'region', like a database transaction (but i guess this should be static, not dynamic), and values generated from code outside the current region are treated like primitives, like there is a Oot graph boundary there, and local deepseq doesn't deepseq past that boundary.

For example, if you represent all possible chess moves as a lazy tree, then you don't have to worry about other functions trying to strictify that whole tree, because other functions will recognize those thunks as coming from a different module or region, and not try to strictify them, even when the other functions are 'strict'.

So, within one region, things are 'strict' by default (locally strict), but not necessarily between regions.

And then we need some easy syntax to override the default of local strictness to get full laziness (or, rather, non-strictness, because we are probably lenient instead of lazy). Eg:

  any = or^lazy map^lazy

---

note: if evaluation of thunks are non-deterministic or have side-effects, then when the thunks are evaluated has consequences for the output of the program. But assuming that thunks are pure:

if you don't have pervasive lazy evaluation (e.g. language and libraries encourage lazy-evaluation-by-default), but instead you only have a 'lazy list' data constructor, then you might have the following two problems:

people using libraries might find that their library inadvertantly strictifies data that they pass in. This is especially troublesome in two cases:
- if you are using lazy lists for infinite data structures, such as a lazy list of the natural numbers -- in this case strictification causes the library call to hang
- if you are filtering lists by stacking wrapped filter functions around a thunk, e.g. "theList.filter(\f x: x > 3).filter(\f x: isOdd(x))". In this case, if you strictify after adding each filter instead of at the end, and so you end up traversing the list once per filter instead of only once (why can you do it only once if they are lazy? Because the compiler can use a stream fusion optimization (is that the right term for it?) which just iterates through the list once and applies all of the relevant filters at each iteration step) (i think this is the same number of steps, but can involve less memory allocation than the naive approach, i think; also, you can inline the sequence of checks for filters instead of having a loop-within-a-loop).

---

" Unfortunately, no language I know of has a good concept of "strictness polymorphism" so in Haskell you end up with duplicate implementations of Strict and Lazy data structures. This ends up being not so much duplicated code, but a whole hell of a lot of duplicated API. "

---