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.1
   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 (defvar stream--generalizer
 156   (cl-generic-make-generalizer
 157    11
 158    (lambda (name)
 159      `(when (streamp ,name)
 160         'stream))
 161    (lambda (tag)
 162      (when (eq tag 'stream)
 163        '(stream)))))
 164
 165 (cl-defmethod cl-generic-generalizers ((_specializer (eql stream)))
 166   "Support for `stream' specializers."
 167   (list stream--generalizer))
 168 \f
 169
 170 ;;; Implementation of seq.el generic functions
 171
 172 (cl-defmethod seq-p ((_stream stream))
 173   t)
 174
 175 (cl-defmethod seq-elt ((stream stream) n)
 176   "Return the element of STREAM at index N."
 177   (while (> n 0)
 178     (setq stream (stream-rest stream))
 179     (setq n (1- n)))
 180   (stream-first stream))
 181
 182 (cl-defmethod seq-length ((stream stream))
 183   "Return the length of STREAM.
 184 This function will eagerly consume the entire stream."
 185   (let ((len 0))
 186     (while (not (stream-empty-p stream))
 187       (setq len (1+ len))
 188       (setq stream (stream-rest stream)))
 189     len))
 190
 191 (cl-defmethod seq-subseq ((stream stream) start end)
 192   (seq-take (seq-drop stream start) (- end start)))
 193
 194 (cl-defmethod seq-into-sequence ((stream stream))
 195   "Convert STREAM into a sequence"
 196   (let ((list))
 197     (seq-doseq (elt stream)
 198       (push elt list))
 199     (nreverse list)))
 200
 201 (cl-defmethod seq-into ((stream stream) type)
 202   "Convert STREAM into a sequence of type TYPE."
 203   (seq-into (seq-into-sequence stream) type))
 204
 205 (cl-defmethod seq-into ((stream stream) (_type (eql stream)))
 206   stream)
 207
 208 (cl-defmethod seq-into ((seq sequence) (_type (eql stream)))
 209   (stream seq))
 210
 211 (cl-defmethod seq-take ((stream stream) n)
 212   "Return a stream of the first N elements of STREAM."
 213   (if (or (zerop n)
 214           (stream-empty-p stream))
 215       (stream-empty)
 216     (stream-cons
 217      (stream-first stream)
 218      (seq-take (stream-rest stream) (1- n)))))
 219
 220 (cl-defmethod seq-drop ((stream stream) n)
 221   "Return a stream of STREAM without its first N elements."
 222   (stream-make
 223    (while (not (or (stream-empty-p stream) (zerop n)))
 224      (setq n (1- n))
 225      (setq stream (stream-rest stream)))
 226    (unless (stream-empty-p stream)
 227      (cons (stream-first stream)
 228            (stream-rest stream)))))
 229
 230 (cl-defmethod seq-take-while (pred (stream stream))
 231   "Return a stream of the successive elements for which (PRED elt) is non-nil in STREAM."
 232   (stream-make
 233    (when (funcall pred (stream-first stream))
 234      (cons (stream-first stream)
 235            (seq-take-while pred (stream-rest stream))))))
 236
 237 (cl-defmethod seq-drop-while (pred (stream stream))
 238   "Return a stream from the first element for which (PRED elt) is nil in STREAM."
 239   (stream-make
 240    (while (not (or (stream-empty-p stream)
 241                    (funcall pred (stream-first stream))))
 242      (setq stream (stream-rest stream)))
 243    (unless (stream-empty-p stream)
 244      (cons (stream-first stream)
 245            (stream-rest stream)))))
 246
 247 (cl-defmethod seq-map (function (stream stream))
 248   "Return a stream.
 249 The elements of the produced sequence consist of the application
 250 of FUNCTION to each element of STREAM."
 251   (if (stream-empty-p stream)
 252       stream
 253     (stream-cons
 254       (funcall function (stream-first stream))
 255      (seq-map function (stream-rest stream)))))
 256
 257 (cl-defmethod seq-do (function (stream stream))
 258   "Evaluate FUNCTION for each element of STREAM eagerly, and return nil.
 259
 260 `seq-do' should never be used on infinite streams."
 261   (while (not (stream-empty-p stream))
 262     (funcall function (stream-first stream))
 263     (setq stream (stream-rest stream))))
 264
 265 (cl-defmethod seq-filter (pred (stream stream))
 266   "Return a stream of the elements for which (PRED element) is non-nil in STREAM."
 267   (if (stream-empty-p stream)
 268       stream
 269     (stream-make
 270      (while (not (or (stream-empty-p stream)
 271                      (funcall pred (stream-first stream))))
 272        (setq stream (stream-rest stream)))
 273      (if (stream-empty-p stream)
 274          nil
 275        (cons (stream-first stream)
 276              (seq-filter pred (stream-rest stream)))))))
 277
 278 (cl-defmethod seq-copy ((stream stream))
 279   "Return a shallow copy of STREAM."
 280   (stream-cons (stream-first stream)
 281                (stream-rest stream)))
 282
 283 (provide 'stream)
 284 ;;; stream.el ends here