ATS streams intro

(* credits goes to M. Lemay *)

#include "share/atspre_staload.hats"
#include "share/HATS/atspre_staload_libats_ML.hats"

// we always need this to make c happy
implement main0 () = ()

// lazyness means we only compute values when we need them 
// and save them so they don't need to be recomputed

// functions that don't take parameters 
// let you schedule computations for later
typedef BadLazy (A) = cfun (A)

// for instance:
fun slowComp ():<cloref1> int =
  let val () = println!("long time in a closure ...")
  in 1+1 end

// we can evaluate the lazy value with ()
val i  = slowComp ()
val () = println! i

// we can pass around BadLazy values
fun decide (bl: BadLazy (int)):int =
  if   true     // complicated logic
  then bl() + 1 // only compute the value when needed
  else 4

val () = println! (decide (slowComp))
val () = println! ()

// however the result is not saved and must be recomputed

// this is solved with the $delay keyword and lazy type
val slowComp2: lazy(int) =
  $delay(
    let val () = println!("long time in a $delay ...")
    in 1+2 end
  )

val i  = !slowComp2
val () = println! i

val i  = !slowComp2 // the value is not recomputed
val () = println! i

fun decide (bl: lazy(int)): int =
  if   true    // complicated logic
  then !bl + 1 // only compute the value when needed, 
               // or use the one that was already computed
  else 4

val i  = decide (slowComp2)  // the value is not recomputed
val () = println! i
val () = println! ()

// remember that types can interact
val x1: lazy (lazy (int)) =
  $delay( $delay(
    let val () = println!("Hello from inside $delay $delay ...")
    in 999 end
  ))

// We need the exact amount of ! to get the value.  
// Too many or too few will result in a type error.
val () = println! (!(!x1))
val () = println! ()

// we can use lazyness to build a lazy list (normally called a stream)

// one way to do this is
datatype mystream (A:t@ype) =
  | mystream_nil  of ()
  | mystream_cons of (A, lazy (mystream (A)))

// but this stream requires the first value to be computed, 
// so we can make a lazier stream as they are defined in ATS

datatype mystream_con (A:t@ype) =
  | mystream_nil  of ()
  | mystream_cons of (A, mystream (A))
where mystream (A:t@ype) = lazy (mystream_con (A)) // just a mutual typedef

// now we don't even know if a stream is empty until we unpack it

// we can build streams using the constructors 
// (but we need to delay the right things)
val ls:mystream (int) = $delay (mystream_cons (1, $delay (mystream_nil ())))

// we can pattern match as long as we unpack the correct values
val a =
  case+ !ls of //NOTE: we must force computation using ! before pattern matching
    | mystream_nil  ()     => 100
    | mystream_cons (x, _) => x

val () = println! ("Pattern matching the first element ...")
val () = println! (a:int) // 1
val () = println! ()

// we can create a large list
fun longg (i: int): mystream (int) =
    $delay(
      if   i=0
      then mystream_nil()
      else let val () = println!("a long time in longg ...") 
           in mystream_cons (i, longg (i-1)) end
    )

// equivelently:
fun longgg (i: int): mystream (int) =
  if i=0
  then $delay (mystream_nil())
  else let val () = println!("a long time in g longgg ...") 
       in $delay (mystream_cons (i, longgg (i-1))) end

//we can print just the first several values we are intrested in
fun myprint (ls: mystream (int), i: int): void =
  if i <= 0
  then println! ("...")
  else case+ !ls of
       | mystream_nil()         => ()
       | mystream_cons(x, rest) =>
           let val () = println!(x)
           in myprint(rest,i-1) end

val () = myprint(longg (10000), 10) // only 10 "hard computations" are done
val () = println!()


// perhaps the most intresting thing about streams is that they can modle infinite data

// and infinite stream of 42s
val fortytwo =
  let
    fun fortytwos (): mystream (int) =
        $delay(mystream_cons(42, fortytwos()))
  in
    fortytwos()
  end

val () = myprint (fortytwo,10)
val () = println!()

// and infinite stream of fibs
val fibs =
  let
    fun help(i:int,j:int):mystream(int) =
        $delay(mystream_cons(i, help(j, i+j)))
  in
    help(0,1)
  end

val () = myprint (fibs,20)
val () = println!()

// and infinite stream of positive numbers
val pos =
  let
    fun help(i:int):mystream(int) =
        $delay(
              mystream_cons(i, help(i+1) ) //note that the recursion help(i+1) is ok becuase of lazyness!
        )
  in
    help(1)
  end

val () = myprint (pos,100)
val () = println!()

// we can implement several combinators on streams

fun {A,B:t@ype} mystreammap(s:mystream(A), f:cfun(A,B)): mystream(B) =
  $delay(
    case+ !s of
      | mystream_nil()         =>  mystream_nil()
      | mystream_cons(x, rest) =>  mystream_cons(f(x), mystreammap(rest, f))
  )

fun {A:t@ype} mystreamfilter(s:mystream(A), f:cfun(A,bool)): mystream(A) =
  $delay(
    case+ !s of
      | mystream_nil()         =>  mystream_nil()
      | mystream_cons(x, rest) =>
        if f(x)
        then mystream_cons(x, mystreamfilter(rest,f) )
        else !(mystreamfilter(rest,f))
  )

//we do have to be careful when using infinite data, this is ok:
val () = myprint(mystreamfilter(pos, (lam(x) =>  x < 10) ), 5 )

//but this will crash
//  val () = myprint(mystreamfilter(pos, (lam(x) =>  x < 10) ), 15 )
//becuase there is no way for the program to know that there is another x less then 10 without doing infinite work

val () = println!()

// an infinite stream of all the numbers greater then or equal to 2
val from2 =
  let
    fun help(i:int):mystream(int) =
        $delay(
              mystream_cons(i, help(i+1) )
        )
  in
    help(2)
  end

// an infinite stream of all the primes
val primes =
  let
    fun sieve (s: mystream (int)): mystream (int) =
      $delay(
        case+ !s of
          | mystream_nil () => mystream_nil () // this never actual happens becuase the stream is infinite
          | mystream_cons (prime, rest) => 
                mystream_cons (prime, 
                               sieve (mystreamfilter (rest, lam (x) => x % prime <> 0)))
        )
  in
      sieve (from2)
  end

val () = myprint (primes, 100 )
val () = println!()

//we can write combinators over streams
fun {A:t@ype} mystreamappend(l:mystream(A), r:mystream(A)): mystream(A) =
  $delay(
    case+ !l of
      | mystream_nil()         => !r
      | mystream_cons(x, rest) => mystream_cons(x, mystreamappend(rest,r) )
  )

fun {A,B:t@ype} mystreamzip(l:mystream(A), r:mystream(B)): mystream($tup(A,B)) =
  $delay(
    case+ (!l , !r) of
      | (mystream_nil()         , _                      ) => mystream_nil()
      | ( _                     , mystream_nil()         ) => mystream_nil()
      | (mystream_cons(lx,lrest), mystream_cons(rx,rrest)) => mystream_cons($tup(lx,rx), mystreamzip(lrest, rrest) )
  )

// once we have good library of combinators we can do lots of intresting things with infinite data