git.iko.soy/streamly
on 4e04eff help sign in
streamly/src/Streamly/Streams/StreamDK/Type.hs
108 lines 5.1 kB history raw
1{-# LANGUAGE CPP #-}
2{-# LANGUAGE ExistentialQuantification #-}
3{-# LANGUAGE FlexibleContexts #-}
5-- |
6-- Module : Streamly.StreamDK.Type
7-- Copyright : (c) 2019 Composewell Technologies
8-- License : BSD3
9-- Maintainer : streamly@composewell.com
10-- Stability : experimental
11-- Portability : GHC
12--
13-- A CPS style stream using a constructor based representation instead of a
14-- function based representation.
15--
16-- Streamly internally uses two fundamental stream representations, (1) streams
17-- with an open or arbitrary control flow (we call it StreamK), (2) streams
18-- with a structured or closed loop control flow (we call it StreamD). The
19-- higher level stream types can use any of these representations under the
20-- hood and can interconvert between the two.
21--
22-- StreamD:
23--
24-- StreamD is a non-recursive data type in which the state of the stream and
25-- the step function are separate. When the step function is called, a stream
26-- element and the new stream state is yielded. The generated element and the
27-- state are passed to the next consumer in the loop. The state is threaded
28-- around in the loop until control returns back to the original step function
29-- to run the next step. This creates a structured closed loop representation
30-- (like "for" loops in C) with state of each step being hidden/abstracted or
31-- existential within that step. This creates a loop representation identical
32-- to the "for" or "while" loop constructs in imperative languages, the states
33-- of the steps combined together constitute the state of the loop iteration.
34--
35-- Internally most combinators use a closed loop representation because it
36-- provides very high efficiency due to stream fusion. The performance of this
37-- representation is competitive to the C language implementations.
38--
39-- Pros and Cons of StreamD:
40--
41-- 1) stream-fusion: This representation can be optimized very efficiently by
42-- the compiler because the state is explicitly separated from step functions,
43-- represented using pure data constructors and visible to the compiler, the
44-- stream steps can be fused using case-of-case transformations and the state
45-- can be specialized using spec-constructor optimization, yielding a C like
46-- tight loop/state machine with no constructors, the state is used unboxed and
47-- therefore no unnecessary allocation.
48--
49-- 2) Because of a closed representation consing too many elements in this type
50-- of stream does not scale, it will have quadratic performance slowdown. Each
51-- cons creates a layer that needs to return the control back to the caller.
52-- Another implementation of cons is possible but that will have to box/unbox
53-- the state and will not fuse. So effectively cons breaks fusion.
54--
55-- 3) unconsing an item from the stream breaks fusion, we have to "pause" the
56-- loop, rebox and save the state.
57--
58-- 3) Exception handling is easy to implement in this model because control
59-- flow is structured in the loop and cannot be arbitrary. Therefore,
60-- implementing "bracket" is natural.
61--
62-- 4) Round-robin scheduling for co-operative multitasking is easy to implement.
63--
64-- 5) It fuses well with the direct style Fold implementation.
65--
66-- StreamK/StreamDK:
67--
68-- StreamDK i.e. the stream defined in this module, like StreamK, is a
69-- recursive data type which has no explicit state defined using constructors,
70-- each step yields an element and a computation representing the rest of the
71-- stream. Stream state is part of the function representing the rest of the
72-- stream. This creates an open computation representation, or essentially a
73-- continuation passing style computation. After the stream step is executed,
74-- the caller is free to consume the produced element and then send the control
75-- wherever it wants, there is no restriction on the control to return back
76-- somewhere, the control is free to go anywhere. The caller may decide not to
77-- consume the rest of the stream. This representation is more like a "goto"
78-- based implementation in imperative languages.
79--
80-- Pros and Cons of StreamK:
81--
82-- 1) The way StreamD can be optimized using stream-fusion, this type can be
83-- optimized using foldr/build fusion. However, foldr/build has not yet been
84-- fully implemented for StreamK/StreamDK.
85--
86-- 2) Using cons is natural in this representation, unlike in StreamD it does
87-- not have a quadratic slowdown. Currently, we in fact wrap StreamD in StreamK
88-- to support a better cons operation.
89--
90-- 3) Similarly, uncons is natural in this representation.
91--
92-- 4) Exception handling is not easy to implement because of the "goto" nature
93-- of CPS.
94--
95-- 5) Composable folds are not implemented/proven, however, intuition says that
96-- a push style CPS representation should be able to be used along with StreamK
97-- to efficiently implement composable folds.
99module Streamly.Streams.StreamDK.Type
100 ( Step(..)
101 , Stream (..)
102 )
103where
105-- XXX Use Cons and Nil instead of Yield and Stop?
106data Step m a = Yield a (Stream m a) | Stop
108data Stream m a = Stream (m (Step m a))