wiki:FirstPrinciples/Streams

Streams

A Stream is just an ADT. Usually, it is implemented as a lazy List (which is also called an infinite List).

Technically it is a Pair of a head-element and and a Closure, which produces the next element (when called implicitly by the tail function). Creation of an infinite (or lazy) List returns such a value (a Pair).

Here is a simple Stream ADT.

(define-syntax stream-cons
  (syntax-rules ()
    ((_ x xs)
     (cons x (delay xs)))))
(define stream-car car)
(define (stream-cdr xs)
  (force (cdr xs)))
(define (stream? s) (and (pair? p) (procedure? (cdr s)))

this is the whole definition of an ADT. It forms a closure - a tail of a infinite List is itself an infinite List. There is ever '() at the end of an infinite list (and there is no end!).

Usually, elements of an infinite list are being taken (consumed) by a function analogous to take for Lists.

(define (stream-take n xs)
  (if (<= n 0)
      '()
      (cons (car xs) (stream-take (- n 1) (stream-cdr xs)))))

The elements, therefore, are produced on-demand, driven by a consumer. This means that infinite lists are reactive.

(define (stream-map f xs)
  (stream-cons (f (car xs)) (stream-map f (stream-cdr xs))))
(define (stream-filter f xs)
  (if (f (car xs))
      (stream-cons (car xs) (stream-filter f (stream-cdr xs)))
      (stream-filter f (stream-cdr xs))))
(define (repeat x)
  (stream-cons x (repeat x)))
(define (iterate f x)
  (stream-cons x (iterate f (f x))))
(define (replicate n x)
  (stream-take n (repeat x)))
(check-expect
 (stream-take 5 (stream-filter odd?
                               (stream-map (lambda (x) (* x x)) (iterate (lambda (x) (+ x 1)) 1))))
 '(1 9 25 49 81))

Typing

There is the abstract notion of nothing (no thing, absence, empty slot) which is math is denoted with the special symbol 0. You could get nothing by (- 1 1) for example.

This notion of nothing, of empty catch, of zero quantity is natural (for human minds) and is good enough to indicate an absence of a value. In a well-crafted languages like Go there is a well-defined zero-value for each concrete type. In other great languages there is notion of nil which is basically a symbolic 0 for the realm data structures.

This is important - a zero value is enough. All these Maybe monads, Option types and other fancies are just unnecessary clutter.

Files

Files is a finite sequence of bytes. Sequence implies ordering, bytes implies uniformity of the data (which later could be interpreted in a particular way) and finite implies that there is a potential EOF condition while reading from a file. This EOF is a zero-value of a stream of data from a file.

The analogy is quite simple, you are opening your wallet, put your fingers in it and there is nothing left. What you get for wallet in this case? An empty hand, zero notes, End-Of-Money condition, or EOM. Again, it is natural for a conditioned as an observer human mind.

For the read operation it is natural to return a zero value when there is nothing more to read. For a buffered read (using a water bucket) one eventually would get a partially filled buffer (a half-empty bucket).

Again, no reason for inventing of a wheel. Always explicitly check for the zero value condition or always measure of how much you have got in a buffer.

Streams

Streams, like the ones of Nature, are supposed to be infinite. This implies that there will never be the EOF condition. In reality most of streams eventually dry out. There is no such thing as an infinite stream (there is no infinity outside human minds in the first place). Such condition will be signalled via some fatal exception.

So, for sane people a stream is a file without an explicit EOF. There is no need for special streaming Java bloatware as long as you understand the principles and have proper rules and definitions.

A Stream is an ADT. No more, no less. delay is a special form which passes an expression unevaluated.

(define-syntax seq
  (syntax-rules ()
    ((_ a b) (cons a (delay b)))))

For a statically typed language it is a type-class.

datatype 'a seq = Nil
                | Cons of 'a * (unit -> 'a seq)

Note: expr will be evaluated (according to the general evaluation rule).

fun cons (x, expr) = Cons(x, fn () => expr)

Scala has special syntax for to avoid evaluation of a parameter expression (=>)

here, however, the expression from (k+1) has not been evaluated yet.

fun from k = Cons(k, fn() => from (k+1));

Blocking

Blocking is a natural thing too. If you are filling a bucket with water you have to wait until it is full.

On the other hand, if you have send a SMS to your friend, it is quite stupid to freeze stating at the phone until confirmation of delivery is received. So, we usually send asynchronously.

It is okay to block on the send and receive operations, and being interrupted with incoming calls or confirmations. The principle is Synchronous (blocking) operations, within asynchronous (send and pray) communication. TCP got it right.

Bidirectional streams

Sometimes we want to send and receive from the same stream. First of all, this is probably a bad idea. Logically, it is much better to have two separate channels (like in a phone - a mike and a speaker) in one data structure.

Last modified 16 months ago Last modified on Nov 2, 2018, 3:13:42 PM
Note: See TracWiki for help on using the wiki.