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 whose 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 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-regexp (buffer regexp)
 117   (stream-make
 118    (let (match)
 119      (with-current-buffer buffer
 120        (setq match (re-search-forward regexp nil t)))
 121      (when match
 122        (cons (match-data) (stream-regexp buffer regexp))
 123        nil))))
 124
 125 (defun stream-range (&optional start end step)
 126   "Return a stream of the integers from START to END, stepping by STEP.
 127 If START is nil, it defaults to 0. If STEP is nil, it defaults to
 128 1.  START is inclusive and END is exclusive.  If END is nil, the
 129 range is infinite."
 130   (unless start (setq start 0))
 131   (unless step (setq step 1))
 132   (if (equal start end)
 133       (stream-empty)
 134     (stream-cons
 135      start
 136      (stream-range (+ start step) end step))))
 137 \f
 138
 139 (defun streamp (stream)
 140   "Return non-nil if STREAM is a stream, nil otherwise."
 141   (and (consp stream)
 142        (eq (car stream) stream--identifier)))
 143
 144 (defun stream-empty ()
 145   "Return an empty stream."
 146   (list stream--identifier (thunk-delay nil)))
 147
 148 (defun stream-empty-p (stream)
 149   "Return non-nil is STREAM is empty, nil otherwise."
 150   (null (thunk-force (cadr stream))))
 151
 152 (defun stream-first (stream)
 153   "Return the first element of STREAM."
 154   (car (thunk-force (cadr stream))))
 155
 156 (defun stream-rest (stream)
 157   "Return a stream of all but the first element of STREAM."
 158   (or (cdr (thunk-force (cadr stream)))
 159       (stream-empty)))
 160 \f
 161
 162 ;;; cl-generic support for streams
 163
 164 (cl-generic-define-generalizer stream--generalizer
 165   11
 166   (lambda (name)
 167     `(when (streamp ,name)
 168        'stream))
 169   (lambda (tag)
 170     (when (eq tag 'stream)
 171       '(stream))))
 172
 173 (cl-defmethod cl-generic-generalizers ((_specializer (eql stream)))
 174   "Support for `stream' specializers."
 175   (list stream--generalizer))
 176 \f
 177
 178 ;;; Implementation of seq.el generic functions
 179
 180 (cl-defmethod seq-p ((_stream stream))
 181   t)
 182
 183 (cl-defmethod seq-elt ((stream stream) n)
 184   "Return the element of STREAM at index N."
 185   (while (> n 0)
 186     (setq stream (stream-rest stream))
 187     (setq n (1- n)))
 188   (stream-first stream))
 189
 190 (cl-defmethod seq-length ((stream stream))
 191   "Return the length of STREAM.
 192 This function will eagerly consume the entire stream."
 193   (let ((len 0))
 194     (while (not (stream-empty-p stream))
 195       (setq len (1+ len))
 196       (setq stream (stream-rest stream)))
 197     len))
 198
 199 (cl-defmethod seq-subseq ((stream stream) start end)
 200   (seq-take (seq-drop stream start) (- end start)))
 201
 202 (cl-defmethod seq-into-sequence ((stream stream))
 203   "Convert STREAM into a sequence."
 204   (let ((list))
 205     (seq-doseq (elt stream)
 206       (push elt list))
 207     (nreverse list)))
 208
 209 (cl-defmethod seq-into ((stream stream) type)
 210   "Convert STREAM into a sequence of type TYPE."
 211   (seq-into (seq-into-sequence stream) type))
 212
 213 (cl-defmethod seq-into ((stream stream) (_type (eql stream)))
 214   stream)
 215
 216 (cl-defmethod seq-into ((seq sequence) (_type (eql stream)))
 217   (stream seq))
 218
 219 (cl-defmethod seq-take ((stream stream) n)
 220   "Return a stream of the first N elements of STREAM."
 221   (if (or (zerop n)
 222           (stream-empty-p stream))
 223       (stream-empty)
 224     (stream-cons
 225      (stream-first stream)
 226      (seq-take (stream-rest stream) (1- n)))))
 227
 228 (cl-defmethod seq-drop ((stream stream) n)
 229   "Return a stream of STREAM without its first N elements."
 230   (stream-make
 231    (while (not (or (stream-empty-p stream) (zerop n)))
 232      (setq n (1- n))
 233      (setq stream (stream-rest stream)))
 234    (unless (stream-empty-p stream)
 235      (cons (stream-first stream)
 236            (stream-rest stream)))))
 237
 238 (cl-defmethod seq-take-while (pred (stream stream))
 239   "Return a stream of the successive elements for which (PRED elt) is non-nil in STREAM."
 240   (stream-make
 241    (when (funcall pred (stream-first stream))
 242      (cons (stream-first stream)
 243            (seq-take-while pred (stream-rest stream))))))
 244
 245 (cl-defmethod seq-drop-while (pred (stream stream))
 246   "Return a stream from the first element for which (PRED elt) is nil in STREAM."
 247   (stream-make
 248    (while (not (or (stream-empty-p stream)
 249                    (funcall pred (stream-first stream))))
 250      (setq stream (stream-rest stream)))
 251    (unless (stream-empty-p stream)
 252      (cons (stream-first stream)
 253            (stream-rest stream)))))
 254
 255 (cl-defmethod seq-map (function (stream stream))
 256     "Return a stream representing the mapping of FUNCTION over STREAM.
 257 The elements of the produced stream are the results of the
 258 applications of FUNCTION on each element of STREAM in succession."
 259   (stream-make
 260    ;; Avoid using `stream-empty-p', as it will consume the first element of the
 261    ;; stream before iterating over the stream.
 262    (let ((first (stream-first stream)))
 263      (when first
 264        (cons (funcall function first)
 265              (seq-map function (stream-rest stream)))))))
 266
 267 (cl-defmethod seq-do (function (stream stream))
 268   "Evaluate FUNCTION for each element of STREAM eagerly, and return nil.
 269
 270 `seq-do' should never be used on infinite streams without some
 271 kind of nonlocal exit."
 272   (while (not (stream-empty-p stream))
 273     (funcall function (stream-first stream))
 274     (setq stream (stream-rest stream))))
 275
 276 (cl-defmethod seq-filter (pred (stream stream))
 277   "Return a stream of the elements for which (PRED element) is non-nil in STREAM."
 278   (if (stream-empty-p stream)
 279       stream
 280     (stream-make
 281      (while (not (or (stream-empty-p stream)
 282                      (funcall pred (stream-first stream))))
 283        (setq stream (stream-rest stream)))
 284      (if (stream-empty-p stream)
 285          nil
 286        (cons (stream-first stream)
 287              (seq-filter pred (stream-rest stream)))))))
 288
 289 (cl-defmethod seq-copy ((stream stream))
 290   "Return a shallow copy of STREAM."
 291   (stream-cons (stream-first stream)
 292                (stream-rest stream)))
 293
 294 (provide 'stream)
 295 ;;; stream.el ends here