code.delx.au - gnu-emacs-elpa/blob - packages/stream/stream.el

   1 ;;; stream.el --- Implementation of streams  -*- lexical-binding: t -*-
   2
   3 ;; Copyright (C) 2015 Free Software Foundation, Inc.
   4
   5 ;; Author: Nicolas Petton <nicolas@petton.fr>
   6 ;; Keywords: stream, laziness, sequences
   7 ;; Version: 2.0.2
   8 ;; Package-Requires: ((emacs "25"))
   9 ;; Package: stream
  10
  11 ;; Maintainer: nicolas@petton.fr
  12
  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.
  17
  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.
  22
  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/>.
  25
  26 ;;; Commentary:
  27
  28 ;; This library provides an implementation of streams. Streams are
  29 ;; implemented as delayed evaluation of cons cells.
  30 ;;
  31 ;; Functions defined in `seq.el' can also take a stream as input.
  32 ;;
  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)
  39 ;; - IO streams
  40 ;; - orgmode table cells
  41 ;; - ...
  42 ;;
  43 ;; All functions are prefixed with "stream-".
  44 ;; All functions are tested in test/automated/stream-tests.el
  45 ;;
  46 ;; Here is an example implementation of the Fibonacci numbers
  47 ;; implemented as in infinite stream:
  48 ;;
  49 ;; (defun fib (a b)
  50 ;;  (stream-cons a (fib b (+ a b))))
  51 ;; (fib 0 1)
  52
  53 ;;; Code:
  54
  55 (eval-when-compile (require 'cl-lib))
  56 (require 'seq)
  57 (require 'thunk)
  58
  59 (eval-and-compile
  60   (defconst stream--identifier '--stream--
  61     "Symbol internally used to identify streams."))
  62
  63 (defmacro stream-make (&rest body)
  64   "Return a stream built from BODY.
  65 BODY must return nil or a cons cell, which cdr is itself a
  66 stream."
  67   (declare (debug t))
  68   `(list ',stream--identifier (thunk-delay ,@body)))
  69
  70 (defmacro stream-cons (first rest)
  71   "Return a stream built from the cons of FIRST and REST.
  72 FIRST and REST are forms and REST must return a stream."
  73   (declare (debug t))
  74   `(stream-make (cons ,first ,rest)))
  75 \f
  76
  77 ;;; Convenient functions for creating streams
  78
  79 (cl-defgeneric stream (src)
  80   "Return a new stream from SRC.")
  81
  82 (cl-defmethod stream ((seq sequence))
  83   "Return a stream built from the sequence SEQ.
  84 SEQ can be a list, vector or string."
  85   (if (seq-empty-p seq)
  86       (stream-empty)
  87     (stream-cons
  88      (seq-elt seq 0)
  89      (stream (seq-subseq seq 1)))))
  90
  91 (cl-defmethod stream ((list list))
  92   "Return a stream built from the list LIST."
  93   (if (null list)
  94       (stream-empty)
  95     (stream-cons
  96      (car list)
  97      (stream (cdr list)))))
  98
  99 (cl-defmethod stream ((buffer buffer) &optional pos)
 100   "Return a stream of the characters of the buffer BUFFER.
 101 BUFFER-OR-NAME may be a buffer or a string (buffer name).
 102 The sequence starts at POS if non-nil, 1 otherwise."
 103   (with-current-buffer buffer
 104     (unless pos (setq pos (point-min)))
 105     (if (>= pos (point-max))
 106         (stream-empty))
 107     (stream-cons
 108      (with-current-buffer buffer
 109        (save-excursion
 110          (save-restriction
 111            (widen)
 112            (goto-char pos)
 113            (char-after (point)))))
 114      (stream buffer (1+ pos)))))
 115
 116 (defun stream-range (&optional start end step)
 117   "Return a stream of the integers from START to END, stepping by STEP.
 118 If START is nil, it defaults to 0. If STEP is nil, it defaults to
 119 1.  START is inclusive and END is exclusive.  If END is nil, the
 120 range is infinite."
 121   (unless start (setq start 0))
 122   (unless step (setq step 1))
 123   (if (equal start end)
 124       (stream-empty)
 125     (stream-cons
 126      start
 127      (stream-range (+ start step) end step))))
 128 \f
 129
 130 (defun streamp (stream)
 131   "Return non-nil if STREAM is a stream, nil otherwise."
 132   (and (consp stream)
 133        (eq (car stream) stream--identifier)))
 134
 135 (defun stream-empty ()
 136   "Return an empty stream."
 137   (list stream--identifier (thunk-delay nil)))
 138
 139 (defun stream-empty-p (stream)
 140   "Return non-nil is STREAM is empty, nil otherwise."
 141   (null (thunk-force (cadr stream))))
 142
 143 (defun stream-first (stream)
 144   "Return the first element of STREAM."
 145   (car (thunk-force (cadr stream))))
 146
 147 (defun stream-rest (stream)
 148   "Return a stream of all but the first element of STREAM."
 149   (or (cdr (thunk-force (cadr stream)))
 150       (stream-empty)))
 151 \f
 152
 153 ;;; cl-generic support for streams
 154
 155 (cl-generic-define-generalizer stream--generalizer
 156   11
 157   (lambda (name)
 158     `(when (streamp ,name)
 159        'stream))
 160   (lambda (tag)
 161     (when (eq tag 'stream)
 162       '(stream))))
 163
 164 (cl-defmethod cl-generic-generalizers ((_specializer (eql stream)))
 165   "Support for `stream' specializers."
 166   (list stream--generalizer))
 167 \f
 168
 169 ;;; Implementation of seq.el generic functions
 170
 171 (cl-defmethod seq-p ((_stream stream))
 172   t)
 173
 174 (cl-defmethod seq-elt ((stream stream) n)
 175   "Return the element of STREAM at index N."
 176   (while (> n 0)
 177     (setq stream (stream-rest stream))
 178     (setq n (1- n)))
 179   (stream-first stream))
 180
 181 (cl-defmethod seq-length ((stream stream))
 182   "Return the length of STREAM.
 183 This function will eagerly consume the entire stream."
 184   (let ((len 0))
 185     (while (not (stream-empty-p stream))
 186       (setq len (1+ len))
 187       (setq stream (stream-rest stream)))
 188     len))
 189
 190 (cl-defmethod seq-subseq ((stream stream) start end)
 191   (seq-take (seq-drop stream start) (- end start)))
 192
 193 (cl-defmethod seq-into-sequence ((stream stream))
 194   "Convert STREAM into a sequence"
 195   (let ((list))
 196     (seq-doseq (elt stream)
 197       (push elt list))
 198     (nreverse list)))
 199
 200 (cl-defmethod seq-into ((stream stream) type)
 201   "Convert STREAM into a sequence of type TYPE."
 202   (seq-into (seq-into-sequence stream) type))
 203
 204 (cl-defmethod seq-into ((stream stream) (_type (eql stream)))
 205   stream)
 206
 207 (cl-defmethod seq-into ((seq sequence) (_type (eql stream)))
 208   (stream seq))
 209
 210 (cl-defmethod seq-take ((stream stream) n)
 211   "Return a stream of the first N elements of STREAM."
 212   (if (or (zerop n)
 213           (stream-empty-p stream))
 214       (stream-empty)
 215     (stream-cons
 216      (stream-first stream)
 217      (seq-take (stream-rest stream) (1- n)))))
 218
 219 (cl-defmethod seq-drop ((stream stream) n)
 220   "Return a stream of STREAM without its first N elements."
 221   (stream-make
 222    (while (not (or (stream-empty-p stream) (zerop n)))
 223      (setq n (1- n))
 224      (setq stream (stream-rest stream)))
 225    (unless (stream-empty-p stream)
 226      (cons (stream-first stream)
 227            (stream-rest stream)))))
 228
 229 (cl-defmethod seq-take-while (pred (stream stream))
 230   "Return a stream of the successive elements for which (PRED elt) is non-nil in STREAM."
 231   (stream-make
 232    (when (funcall pred (stream-first stream))
 233      (cons (stream-first stream)
 234            (seq-take-while pred (stream-rest stream))))))
 235
 236 (cl-defmethod seq-drop-while (pred (stream stream))
 237   "Return a stream from the first element for which (PRED elt) is nil in STREAM."
 238   (stream-make
 239    (while (not (or (stream-empty-p stream)
 240                    (funcall pred (stream-first stream))))
 241      (setq stream (stream-rest stream)))
 242    (unless (stream-empty-p stream)
 243      (cons (stream-first stream)
 244            (stream-rest stream)))))
 245
 246 (cl-defmethod seq-map (function (stream stream))
 247   "Return a stream.
 248 The elements of the produced sequence consist of the application
 249 of FUNCTION to each element of STREAM."
 250   (if (stream-empty-p stream)
 251       stream
 252     (stream-cons
 253       (funcall function (stream-first stream))
 254      (seq-map function (stream-rest stream)))))
 255
 256 (cl-defmethod seq-do (function (stream stream))
 257   "Evaluate FUNCTION for each element of STREAM eagerly, and return nil.
 258
 259 `seq-do' should never be used on infinite streams."
 260   (while (not (stream-empty-p stream))
 261     (funcall function (stream-first stream))
 262     (setq stream (stream-rest stream))))
 263
 264 (cl-defmethod seq-filter (pred (stream stream))
 265   "Return a stream of the elements for which (PRED element) is non-nil in STREAM."
 266   (if (stream-empty-p stream)
 267       stream
 268     (stream-make
 269      (while (not (or (stream-empty-p stream)
 270                      (funcall pred (stream-first stream))))
 271        (setq stream (stream-rest stream)))
 272      (if (stream-empty-p stream)
 273          nil
 274        (cons (stream-first stream)
 275              (seq-filter pred (stream-rest stream)))))))
 276
 277 (cl-defmethod seq-copy ((stream stream))
 278   "Return a shallow copy of STREAM."
 279   (stream-cons (stream-first stream)
 280                (stream-rest stream)))
 281
 282 (provide 'stream)
 283 ;;; stream.el ends here