Thunk

java.lang.Object
- frege.run8.Thunk<R>

All Implemented Interfaces:

Lazy<R>, java.util.concurrent.Callable<R>
```
public class Thunk<R>
extends java.lang.Object
implements Lazy<R>
```
A lazy value that can be shared and is updated with the evaluated value.

Lazy values differ from proper values insofar as they need to know how to exactly evaluate themselves. This is the job of the call().

The functionality of call() is fixed through final and cannot be changed. It is in some sense the heart of the runtime, as it provides support for tail calls and lazy evaluation.

call() repeatedly invokes Lazy.call() until the returned value is in weak head normal form, which is signalled by not being an instance of Lazy. In addition, the result is shared through caching it in a private instance variable. Hence, instances of Thunk are not immutable and this in turn requires synchronization.

The caching of the evaluated value would not be strictly necessary, as repeated evaluation must always yield the same result. Experience shows, however, that re-evaluations are quite common, hence not caching the result would most likely cause even the simplest program to perform unacceptably bad.

Introduction of laziness in frege compiled code

Thunk values are introduced at only 2 occasions:
1. Thunk arguments of data constructors or functions. Take the following example:
```
 -- the list of Fibonacci numbers
 fibs = 0:1:zipWith (+) fibs (tail fibs)
 
```
  The second argument of (:) must be lazy because its type is recursive. Types of constructor arguments are said to be recursive, if they mention a type that depends on the type of the constructed value. A type depends on itself and on types that mention it in at least one constructor argument.
  
  Hence, the application of zipWith argument may appear in code like this:
```
 new Thunk(() -> zipWith(plusFunc, fibs, tail(fibs));
 
```
2. Non-recursive tail calls.
  
  If the return value of a function is expressed as a function call, we call this a tail call. If a function tail-calls itself, this is tail recursion. Here are examples:
```
 
 even 0 = true
 even n = odd  (n-1)
 odd  0 = false
 odd  n = even (n-1)
 factorial n | n >= 0 = helper 1 n where
    helper r 0 = r
    helper r n = helper (r*n) (n-1)
 
 
```
  Function "helper" is tail recursive and will be compiled to a while loop. Functions "factorial", "even" and "odd", however, employ tail calls. In "factorial", this is not a problem, it just sets up parameters for the very efficient "helper" function, thus we can expect a maximum stack depth of 2 no matter what the value of "n" is.
  
  Things are different with "even" and "odd" that would need stack space proportional to the value of their argument if implemented naively. But frege functions may simply return their tail call in the form of a Thunk object instead of actually evaluating it themselves. This way, a long series of tail calls can be converted to a while loop, see call().
  
  Unfortunately, this does not work in every case. Take the even/odd exmple in a slightly changed form:
```
 even 0 = true
 even 1 = false
 even n = odd  (n-1)
 odd  n = !(even n)
 
```
  This will very soon run out of stack space with greater n. To see why, imagine even 5 had to be evaluated.
```
 even 5 = odd 4               by 3rd rule of even
 odd 4 = !(even 4)            by definition of odd
 !(even 4) = !(odd 3)         by 3rd rule of even
 !(odd 3)  = !(!(even 3))
 !(!(even 3)) = !(!(odd 2))
 !(!(odd 2))  = !(!(!(even 2)))
 !(!(!(even 2))) = !(!(!(odd 1)))
 !(!(!(odd 1))) = !(!(!(!(even 0))))
 !(!(!(!(even 0)))) = !(!(!(!true)))
 
```
  Because ! must first know the value to negate it must evaluate its argument before it returns. Hence, evaluation of (odd n) results in n nested negations, i.e. in a stack depth of n.
  
  This effect happens always when the recursion is done indirectly in an argument of a strict function. Another well-known case is the naive implementation of a function that tells a lists's length:
```
 naiveLength [] = 0
 naiveLength (_:as) = 1 + naiveLength as
 
```
  Here, the recursion takes place in the 2nd argument of the addition. To add 1 to something, one must first know to what, hence the whole list must be consulted before even the first addition can take place.
  
  Compare the better implementation:
```
 length xs = helper xs 0
    where
       helper []     !count = count
       helper (_:as) !count = helper as (count+1)
 
```
  Here, only tail call recursion takes place and because counter is strict, the increment will be evaluated in each loop.

Field Summary

Fields
Modifier and Type	Field and Description
`private Lazy<R>`	`eval`
`private java.lang.Object`	`item`
`static Lazy<java.lang.String>`	`lazyemptyString`
`static Lazy<java.lang.Boolean>`	`lazyFalse`
`static Lazy<java.lang.Integer>`	`lazyOne`
`static Lazy<java.lang.Boolean>`	`lazyTrue` Some often used lazy values.
`static Lazy<java.lang.Integer>`	`lazyTwo`
`static Lazy<java.lang.Short>`	`lazyUnit`
`static Lazy<Phantom.RealWorld>`	`lazyWorld`
`static Lazy<java.lang.Integer>`	`lazyZero`

Constructor Summary

Constructors
Modifier Constructor and Description

private Thunk()

private Thunk(Lazy<R> it)
Create a thunk from a Lazy value.

Constructors
Modifier	Constructor and Description
`private`	`Thunk()`
`private`	`Thunk(Lazy<R> it)` Create a thunk from a `Lazy` value.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`Thunk<R>`	`asThunk()` Tell if this is really a `Thunk`
`R`	`call()` evaluate the `Lazy`, and update this Thunk, unless it is already evaluated.
`(package private) boolean`	`isEvaluated()` tell if this Thunk is already evaluated.
`boolean`	`isShared()` Tell if this is shared.
`static Lazy<java.lang.Boolean>`	`lazy(boolean val)` Make sure we have a `Lazy` value.
`static Lazy<java.lang.Byte>`	`lazy(byte val)`
`static Lazy<java.lang.Character>`	`lazy(char val)`
`static Lazy<java.lang.Double>`	`lazy(double val)`
`static Lazy<java.lang.Float>`	`lazy(float val)`
`static Lazy<java.lang.Integer>`	`lazy(int val)`
`static <X> Lazy<X>`	`lazy(Lazy<X> val)`
`static Lazy<java.lang.Long>`	`lazy(long val)`
`static Lazy<java.lang.Short>`	`lazy(short val)`
`static <X> Lazy<X>`	`lazy(X val)`
`static <R> Lazy<R>`	`nested(Lazy<Lazy<R>> v)` The following creates a Thunk«B» and hence a Lazy«B» from something that is known to be Lazy«Lazy«B»».
`static <X> X`	`once(X obj, X nul)` Utility function to get some value and clearing it at the same time.
`static <R> Lazy<R>`	`shared(Lazy<R> v)` Static form of the constructor

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - item
```
private volatile java.lang.Object item
```
  - eval
```
private Lazy<R> eval
```
  - lazyTrue
```
public static final Lazy<java.lang.Boolean> lazyTrue
```
    Some often used lazy values.
  - lazyFalse
```
public static final Lazy<java.lang.Boolean> lazyFalse
```
  - lazyemptyString
```
public static final Lazy<java.lang.String> lazyemptyString
```
  - lazyZero
```
public static final Lazy<java.lang.Integer> lazyZero
```
  - lazyOne
```
public static final Lazy<java.lang.Integer> lazyOne
```
  - lazyTwo
```
public static final Lazy<java.lang.Integer> lazyTwo
```
  - lazyWorld
```
public static final Lazy<Phantom.RealWorld> lazyWorld
```
  - lazyUnit
```
public static final Lazy<java.lang.Short> lazyUnit
```
- Constructor Detail
  - Thunk
```
private Thunk(Lazy<R> it)
```
    Create a thunk from a Lazy value.
    
    On evaluation via call(), this Thunk will be updated with the result of evaluating the value.
    
    Parameters:
    
    it - a lazy value. This must never be null!
  - Thunk
```
private Thunk()
```
- Method Detail
  - asThunk
```
public Thunk<R> asThunk()
```
    Description copied from interface: Lazy
    
    Tell if this is really a Thunk
    
    Specified by:
    
    asThunk in interface Lazy<R>
    
    Returns:
  - call
```
public final R call()
```
    evaluate the Lazy, and update this Thunk, unless it is already evaluated.
    
    Specified by:
    
    call in interface Lazy<R>
    
    Specified by:
    
    call in interface java.util.concurrent.Callable<R>
    
    Returns:
    
    the evaluated value
    
    See Also:
    
    Callable.call()
  - isShared
```
public boolean isShared()
```
    Description copied from interface: Lazy
    
    Tell if this is shared.
    
    Data and functions whose Lazy.call() method returns this as well as simple boxes that just hold a value ready to be supplied and Thunks are considered shared.
    But a bare lambda expression is assumed to be in need of sharing. For example:
    () -> 42
    
    Specified by:
    
    isShared in interface Lazy<R>
    
    Returns:
    
    false, if sharing this would make any sense, otherwise true
  - isEvaluated
```
boolean isEvaluated()
```
    tell if this Thunk is already evaluated.
    
    Returns:
    
    true, if it is already evaluated, false otherwise
  - lazy
```
public static final Lazy<java.lang.Boolean> lazy(boolean val)
```
    Make sure we have a Lazy value.
    This is, in a sense, the exact opposite of call(). Whereas the latter evaluates a Thunk, unless already evaluated, this method constructs a Lazy value unless it is statically known to be a Lazy.
    
    Because all algebraic types implement Lazy, this should create an extra wrapper for native values only.
    
    Parameters:
    
    val - some value
    
    Returns:
    
    If the argument is already Lazy, it is returned properly casted. Otherwise it is wrapped in a Box and returned.
  - lazy
```
public static final Lazy<java.lang.Byte> lazy(byte val)
```
  - lazy
```
public static final Lazy<java.lang.Short> lazy(short val)
```
  - lazy
```
public static final Lazy<java.lang.Character> lazy(char val)
```
  - lazy
```
public static final Lazy<java.lang.Integer> lazy(int val)
```
  - lazy
```
public static final Lazy<java.lang.Long> lazy(long val)
```
  - lazy
```
public static final Lazy<java.lang.Double> lazy(double val)
```
  - lazy
```
public static final Lazy<java.lang.Float> lazy(float val)
```
  - lazy
```
public static final <X> Lazy<X> lazy(Lazy<X> val)
```
  - lazy
```
public static final <X> Lazy<X> lazy(X val)
```
  - shared
```
public static final <R> Lazy<R> shared(Lazy<R> v)
```
    Static form of the constructor
    
    For Lazy values that are already shared, this is the identity.
    
    Other Lazy instances are wrapped in a Thunk, this makes them shared.
    
    Returns:
    
    a shared version of the Lazy value.
  - nested
```
public static final <R> Lazy<R> nested(Lazy<Lazy<R>> v)
```
    The following creates a Thunk«B» and hence a Lazy«B» from something that is known to be Lazy«Lazy«B»».
    
    Now, the cast is justified for the reason that a Thunk«B» arranges for evaluation in such a way that a B will actually be returned. Hence, while Thunk«B» and Thunk«Lazy«B»» are indeed different types, it is the case that call() must never return a Lazy«B» that is not also a B (like with algebraic values).
    
    We need this when two or more functions are mutually recursive, like in the following scenario:
```
        even 0 = true
  even 1 = false
  even n = odd (n-1)
  odd n = even (n-1)
 
```
    In such cases, direct method calls would cause a StackOverflow on larger numbers. Hence, it is mandatory, that the result must be Lazy for all functions. Now consider the case where odd() is about to call even(): it must return the same value as even(n-1) without actually calling even(). Hence it should return something like:
```
return (Lazy«Boolean») (() -> even(n-1));
```
    but since the right hand side is already Lazy«Boolean» this doesn't type check. Likewise
```
return (Lazy«Lazy«Boolean»») (() -> even(n-1));
```
    is incommensurable with the return type, which is just Lazy«Boolean». Hence the solution is to embed the lambda in a Thunk:
```
return Thunk.«B»nested( (Lazy«Lazy«Boolean»») (() -> even(n-1)) );
```
    thereby lowering the compile type laziness of the result by one level.
    
    Furthermore, odd() can now be seen as a tail-call safe function, since it doesn't actually do a tail call, but just constructs the thunk. This, in turn, makes it now possible for even to call odd(n-1) method directly, yet without evaluating the result. For, this will just give the nested thunk after a limited number of method calls (1, in this case), which is a lazy boolean and can be returned right away.
    
    An alternative to this method would be to have 3 categories of functions: strict ones, lazy ones and double lazy ones. But this would dramatically complicate the code generator.
  - once
```
public static final <X> X once(X obj,
                               X nul)
```
    Utility function to get some value and clearing it at the same time.
    
    Use like
    Thunk.once(v, v = null)
    
    Parameters:
    
    obj - the desired value, usually given as a nonfinal variable
    
    nul - this argument is ignored, usually used to assign null to the variable
    
    Returns:
    
    the first argument

Class Thunk<R>

Introduction of laziness in frege compiled code

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

item

eval

lazyTrue

lazyFalse

lazyemptyString

lazyZero

lazyOne

lazyTwo

lazyWorld

lazyUnit

Constructor Detail

Thunk

Thunk

Method Detail

asThunk

call

isShared

isEvaluated

lazy

lazy

lazy

lazy

lazy

lazy

lazy

lazy

lazy

lazy

shared

nested

once