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