1 ;;; stream.el --- Implementation of streams -*- lexical-binding: t -*-
3 ;; Copyright (C) 2015 Free Software Foundation, Inc.
5 ;; Author: Nicolas Petton <nicolas@petton.fr>
6 ;; Keywords: stream, laziness, sequences
8 ;; Package-Requires: ((emacs "25.1"))
11 ;; Maintainer: nicolas@petton.fr
13 ;; This program is free software; you can redistribute it and/or modify
14 ;; it under the terms of the GNU General Public License as published by
15 ;; the Free Software Foundation, either version 3 of the License, or
16 ;; (at your option) any later version.
18 ;; This program is distributed in the hope that it will be useful,
19 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
20 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 ;; GNU General Public License for more details.
23 ;; You should have received a copy of the GNU General Public License
24 ;; along with this program. If not, see <http://www.gnu.org/licenses/>.
28 ;; This library provides an implementation of streams. Streams are
29 ;; implemented as delayed evaluation of cons cells.
31 ;; Functions defined in `seq.el' can also take a stream as input.
33 ;; streams could be created from any sequential input data:
34 ;; - sequences, making operation on them lazy
35 ;; - a set of 2 forms (first and rest), making it easy to represent infinite sequences
36 ;; - buffers (by character)
37 ;; - buffers (by line)
38 ;; - buffers (by page)
40 ;; - orgmode table cells
43 ;; All functions are prefixed with "stream-".
44 ;; All functions are tested in test/automated/stream-tests.el
46 ;; Here is an example implementation of the Fibonacci numbers
47 ;; implemented as in infinite stream:
50 ;; (stream-cons a (fib b (+ a b))))
55 (eval-when-compile (require 'cl-lib))
59 (defconst stream--identifier '--stream--
60 "Symbol internally used to identify streams."))
62 (defmacro stream--delay (&rest body)
63 "Delay the evaluation of BODY."
65 (let ((forced (make-symbol "forced"))
66 (val (make-symbol "val")))
70 (setf ,val (progn ,@body))
74 (defun stream--force (delayed)
75 "Force the evaluation of DELAYED."
78 (defmacro stream-make (&rest body)
79 "Return a stream built from BODY.
80 BODY must return nil or a cons cell, which cdr is itself a
83 `(list ',stream--identifier (stream--delay ,@body)))
85 (defmacro stream-cons (first rest)
86 "Return a stream built from the cons of FIRST and REST.
87 FIRST and REST are forms and REST must return a stream."
89 `(stream-make (cons ,first ,rest)))
92 ;;; Convenient functions for creating streams
94 (cl-defgeneric stream (src)
95 "Return a new stream from SRC.")
97 (cl-defmethod stream ((seq sequence))
98 "Return a stream built from the sequence SEQ.
99 SEQ can be a list, vector or string."
100 (if (seq-empty-p seq)
104 (stream (seq-subseq seq 1)))))
106 (cl-defmethod stream ((list list))
107 "Return a stream built from the list LIST."
112 (stream (cdr list)))))
114 (cl-defmethod stream ((buffer buffer) &optional pos)
115 "Return a stream of the characters of the buffer BUFFER.
116 BUFFER-OR-NAME may be a buffer or a string (buffer name).
117 The sequence starts at POS if non-nil, 1 otherwise."
118 (with-current-buffer buffer
119 (unless pos (setq pos (point-min)))
120 (if (>= pos (point-max))
123 (with-current-buffer buffer
128 (char-after (point)))))
129 (stream buffer (1+ pos)))))
131 (defun stream-range (&optional start end step)
132 "Return a stream of the integers from START to END, stepping by STEP.
133 If START is nil, it defaults to 0. If STEP is nil, it defaults to
134 1. START is inclusive and END is exclusive. If END is nil, the
136 (unless start (setq start 0))
137 (unless step (setq step 1))
138 (if (equal start end)
142 (stream-range (+ start step) end step))))
145 (defun stream-p (stream)
146 "Return non-nil if STREAM is a stream, nil otherwise."
148 (eq (car stream) stream--identifier)))
150 (defun stream-empty ()
151 "Return an empty stream."
152 (list stream--identifier (stream--delay nil)))
154 (defun stream-empty-p (stream)
155 "Return non-nil is STREAM is empty, nil otherwise."
156 (null (stream--force (cadr stream))))
158 (defun stream-first (stream)
159 "Return the first element of STREAM."
160 (car (stream--force (cadr stream))))
162 (defun stream-rest (stream)
163 "Return a stream of all but the first element of STREAM."
164 (cdr (stream--force (cadr stream))))
167 ;;; cl-generic support for streams
169 (defvar stream--generalizer
170 (cl-generic-make-generalizer
173 `(when (stream-p ,name)
176 (when (eq tag 'stream)
179 (cl-defmethod cl-generic-generalizers ((_specializer (eql stream)))
180 "Support for `stream' specializers."
181 (list stream--generalizer))
184 ;;; Implementation of seq.el generic functions
186 (cl-defgeneric seq-p ((_stream stream))
189 (cl-defgeneric seq-elt ((stream stream) n)
190 "Return the element of STREAM at index N."
192 (setq stream (stream-rest stream))
194 (stream-first stream))
196 (cl-defgeneric seq-length ((stream stream))
197 "Return the length of STREAM.
198 This function will eagerly consume the entire stream."
200 (while (not (stream-empty-p stream))
202 (setq stream (stream-rest stream)))
205 (cl-defgeneric seq-subseq ((stream stream) start end)
206 (seq-take (seq-drop stream start) (- end start)))
208 (cl-defgeneric seq-into-sequence ((stream stream))
209 "Convert STREAM into a sequence"
211 (seq-doseq (elt stream)
215 (cl-defgeneric seq-into ((stream stream) type)
216 "Convert STREAM into a sequence of type TYPE."
217 (seq-into (seq-into-sequence stream) type))
219 (cl-defgeneric seq-into ((stream stream) (_type (eql stream)))
222 (cl-defgeneric seq-into ((seq sequence) (_type (eql stream)))
225 (cl-defgeneric seq-take ((stream stream) n)
226 "Return a stream of the first N elements of STREAM."
230 (stream-first stream)
231 (seq-take (stream-rest stream) (1- n)))))
233 (cl-defgeneric seq-drop ((stream stream) n)
234 "Return a stream of STREAM without its first N elements."
236 (while (not (or (stream-empty-p stream) (zerop n)))
238 (setq stream (stream-rest stream)))
239 (unless (stream-empty-p stream)
240 (cons (stream-first stream)
241 (stream-rest stream)))))
243 (cl-defgeneric seq-take-while (pred (stream stream))
244 "Return a stream of the successive elements for which (PRED elt) is non-nil in STREAM."
246 (when (funcall pred (stream-first stream))
247 (cons (stream-first stream)
248 (seq-take-while pred (stream-rest stream))))))
250 (cl-defgeneric seq-drop-while (pred (stream stream))
251 "Return a stream from the first element for which (PRED elt) is nil in STREAM."
253 (while (not (or (stream-empty-p stream)
254 (funcall pred (stream-first stream))))
255 (setq stream (stream-rest stream)))
256 (unless (stream-empty-p stream)
257 (cons (stream-first stream)
258 (stream-rest stream)))))
260 (cl-defgeneric seq-map (function (stream stream))
262 The elements of the produced sequence consist of the application
263 of FUNCTION to each element of STREAM."
264 (if (stream-empty-p stream)
267 (funcall function (stream-first stream))
268 (seq-map function (stream-rest stream)))))
270 (cl-defgeneric seq-do (function (stream stream))
271 "Evaluate FUNCTION for each element of STREAM eagerly, and return nil.
273 `seq-do' should never be used on infinite streams."
274 (while (not (stream-empty-p stream))
275 (funcall function (stream-first stream))
276 (setq stream (stream-rest stream))))
278 (cl-defgeneric seq-filter (pred (stream stream))
279 "Return a stream of the elements for which (PRED element) is non-nil in STREAM."
280 (if (stream-empty-p stream)
283 (while (not (or (stream-empty-p stream)
284 (funcall pred (stream-first stream))))
285 (setq stream (stream-rest stream)))
286 (if (stream-empty-p stream)
288 (cons (stream-first stream)
289 (seq-filter pred (stream-rest stream)))))))
291 (cl-defgeneric seq-copy ((stream stream))
292 "Return a shallow copy of STREAM."
293 (stream-cons (stream-first stream)
294 (stream-rest stream)))
297 ;;; stream.el ends here