ATS Streams Notes

(* 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