From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Michael Heerdegen Newsgroups: gmane.emacs.devel Subject: Generators (iterators) for Gnu Emacs Date: Fri, 05 Dec 2014 00:43:14 +0100 Message-ID: <877fy77zhp.fsf@web.de> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" X-Trace: ger.gmane.org 1417736631 12460 80.91.229.3 (4 Dec 2014 23:43:51 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 4 Dec 2014 23:43:51 +0000 (UTC) Cc: Daniel Colascione To: Emacs Development Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Dec 05 00:43:44 2014 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1Xwg3j-0005Bu-LB for ged-emacs-devel@m.gmane.org; Fri, 05 Dec 2014 00:43:43 +0100 Original-Received: from localhost ([::1]:48158 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Xwg3j-0005Iv-4C for ged-emacs-devel@m.gmane.org; Thu, 04 Dec 2014 18:43:43 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:48126) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Xwg3Y-0005Io-Ss for emacs-devel@gnu.org; Thu, 04 Dec 2014 18:43:40 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Xwg3R-0000hG-CY for emacs-devel@gnu.org; Thu, 04 Dec 2014 18:43:32 -0500 Original-Received: from mout.web.de ([212.227.15.14]:64137) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Xwg3R-0000fq-0u for emacs-devel@gnu.org; Thu, 04 Dec 2014 18:43:25 -0500 Original-Received: from drachen.dragon ([90.187.67.236]) by smtp.web.de (mrweb001) with ESMTPSA (Nemesis) id 0MSs2H-1YOLpF3nyn-00Rqd2; Fri, 05 Dec 2014 00:43:21 +0100 User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.0.50 (gnu/linux) X-Provags-ID: V03:K0:pDwACyWT0MSQSVV8YyOo69677B9srkTcO0p1MIA59NnvjHj97Vi 9f0F1d36N6bduH02w14ko2r0IxHzEEE+L/icXAHKMW8680G961GcN5L0zn03Rx560X62UKz 4d0XTi1VR3NZEq+GQ2msYqHZtsStNsfNql9DfbGWw161AGH/+Dbz9UwIH8gkCIOcX193jPx nl94h200W71/68iqUJ0kQ== X-UI-Out-Filterresults: notjunk:1; X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x [generic] X-Received-From: 212.227.15.14 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:178861 Archived-At: --=-=-= Content-Type: text/plain Hello, I want to contribute a package about generators to Gnu Emacs. It is quite simple, but turned out to be surprisingly useful to have in several situations. It is efficient and avoids recursion - iterating across a generator's elements results in a simple `while' loop being executed. Daniel Colascione suggested to me to rename the thing to "iterators.el", since this package doesn't use continuation passing style to implement "yield". I guess that's reasonable. Thanks, Michael. --=-=-= Content-Type: application/emacs-lisp Content-Disposition: attachment; filename=generator.el Content-Transfer-Encoding: quoted-printable ;;; generator.el --- Generators for Emacs Lisp -*- lexical-binding: t -*- ;; Copyright (C) 2014 Michael Heerdegen ;; Author: Michael Heerdegen ;; Maintainer: Michael Heerdegen ;; Keywords: extensions ;; This file is not part of GNU Emacs. ;; GNU Emacs is free software: you can redistribute it and/or modify ;; it under the terms of the GNU General Public License as published by ;; the Free Software Foundation, either version 3 of the License, or ;; (at your option) any later version. ;; GNU Emacs is distributed in the hope that it will be useful, ;; but WITHOUT ANY WARRANTY; without even the implied warranty of ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ;; GNU General Public License for more details. ;; You should have received a copy of the GNU General Public License ;; along with GNU Emacs. If not, see . ;;; Commentary: ;; Generators are things that generate and return elements on demand. ;; ;; When a generator returns the symbol `gen-done', this denotes the ;; generator has finished. All functions examining elements of ;; generators will handle this value specially and only request and ;; process elements until the generator returns `gen-done' the first ;; time. The elements returned before `gen-done' are considered the ;; generator's sequence of produced elements. ;; ;; This packages defines the following kinds of functions: ;; ;; - Basic functions: `gen-make' (create a generator), `gen-next' ;; (request an element), and some functions creating certain simple ;; kinds of generators like number ranges ;; ;; - Transducers (operations on generators). These functions take ;; generators as input and construct a new generator. All of them ;; are delayed operations, meaning that no elements from any input ;; generator are requested. Instead, a new generator encapsulating ;; an appropriate generation rule is created. ;; ;; - Functions processing elements of generators: looping, conversion ;; to lists, reduction, maximum, etc. ;; ;; - Caching - see `gen-cache' and `gen-from-cache' ;; ;; ;; Programming examples (all make use of lexical-binding): ;; ;; A function returning a generator of the powers of 2 (starting with ;; 2): ;; ;; (defun make-generator-of-powers-of-two () ;; (let ((i 1)) ;; (gen-make (setq i (* 2 i))))) ;; ;; Let's create a generator ... ;; ;; (setq g (make-generator-of-powers-of-two)) ;; ;; ... and request some elements: ;; ;; (gen-next g) ;; =3D=3D> 2 ;; (gen-next g) ;; =3D=3D> 4 ;; (gen-next g) ;; =3D=3D> 8 ;; ;; Let's create a second generator of the powers of 2: ;; ;; (setq h (make-generator-of-powers-of-two)) ;; ;; g and h both have an individual state: ;; ;; (gen-next h) ;; =3D=3D> 2 ;; (gen-next g) ;; =3D=3D> 16 ;; (gen-next h) ;; =3D=3D> 4 ;;=20 ;; Here is another way to create a generator of the powers of 2: ;; ;; (gen-map (lambda (n) (expt 2 n)) ;; (gen-number-range 1)) ;; ;; and a third one: ;; ;; (gen-scan #'* 2 (gen-cycle-elts 2)) ;; ;; The following expression tests integers starting from 1 and returns ;; the first one whose square is >=3D 726: ;; ;; (gen-last ;; (gen-take-until ;; (lambda (x) (>=3D (* x x) 726)) ;; (gen-number-range 1))) ;; ;; This example uses a generator to read strings from the user until ;; the empty string is entered. Finally all strings are printed in a ;; message: ;; ;; (let ((string-reader ;; (let ((i 0)) ;; (gen-take-while ;; (lambda (s) (not (string=3D s ""))) ;; (gen-make ;; (read-string (format "String %d (empty string means done): " ;; (cl-incf i)))))))) ;; (message "You entered: %s." (gen-mapconcat 'identity string-reader "= , "))) ;; ;; Note that the strings are read in when the generator's elements are ;; requested (in the `message' call), not when the generator is ;; defined. ;; ;; Let's define a function that returns a generator of the prime ;; numbers using the sieve of Eratosthenes: ;; ;; (defun cross-through-multiples-of (n) ;; "Repeat indefinitely: Return `t' N-1 times, then return `nil' once." ;; (let ((i (1- n))) ;; (gen-make ;; (if (zerop i) (progn (setq i (1- n)) nil) ;; (prog1 t (cl-decf i)))))) ;;=20=20=20=20 ;; (defun make-prime-gen () ;; "Return a generator of the prime numbers." ;; (let ((n 2) (sieve '())) ;; (gen-delq nil ;; (gen-make ;; (if (cl-every #'identity (mapcar #'gen-next sieve)) ;; (prog2 (push (cross-through-multiples-of n) sieve) ;; n ;; (cl-incf n)) ;; (cl-incf n) ;; nil))))) ;; ;; ;; We don't want to recalculate the prime numbers every time we need ;; them, so we use a cache: ;; ;; (setq prime-cache (gen-cache (make-prime-gen))) ;; ;; Let's print all primes < 10000 that are congruent to 3 modulo 4: ;; ;; (gen-do (p (thread-last (gen-from-cache prime-cache) ;; (gen-take-while (lambda (p) (< p 10000))) ;; (gen-filter (lambda (p) (=3D 3 (mod p 4)))))) ;; (message "%S" p)) ;; ;; If you evaluate this a second time, it is much faster, since every ;; prime number is calculated only once. ;; ;; ;;; Todo ;; ;; Enable `cl-loop' to iterate across generators ;;; Code: (require 'cl-lib) ;; Basic stuff (defmacro gen-make (&rest body) "Return a generator that evaluates BODY to generate elements. For each call of `gen-next' with the the returned generator, BODY will be evaluated to produce an element." (let ((this-element (make-symbol "this-element"))) `(let (,this-element) (lambda () (if (eq ,this-element 'gen-done) 'gen-done (setq ,this-element (progn ,@body))))))) (defun gen-next (generator) "Request and return an element from GENERATOR. This is done by calling GENERATOR as a function of zero arguments. When the result is the symbol `gen-done', this denotes that the generator has finished." (funcall generator)) ;; Special simple generators (defun gen-from-elts (&rest elements) "Return a generator generating the ELEMENTS." (gen-make (if (not (null elements)) (pop elements) 'gen-done))) (defun gen-cycle-elts (&rest elements) "Return a generator cycling through the ELEMENTS. Unlike `gen-from-elts', after the last of the ELEMENTS has been generated, the resulting generator will generate all ELEMENTS again ad finitum." (if (null elements) (gen-from-elts) (setcdr (last elements) elements) (gen-make (pop elements)))) (defun gen-iterate (function value) "Return a generator of repeated applications of FUNCTION to VALUE. The sequence of returned elements is starting with VALUE. Any successive element will be found by calling FUNCTION on the preceding element." (gen-append (gen-from-elts value) (gen-make (setq value (funcall function value))))) (defun gen-number-range (&optional start end inc) "Return a generator of a number sequence. START denotes the first number and defaults to 1. The second optional argument END specifies the upper limit. If nil, the returned generator is infinite. INC is the increment used between numbers and defaults to 1." (let* ((inc (or inc +1)) (start (or start 0)) (i start)) (if end (let ((comp (if (> inc 0) #'<=3D #'>=3D))) (gen-make (if (funcall comp i end) (prog1 i (cl-incf i inc)) 'gen= -done))) (gen-make (prog1 i (cl-incf i)))))) (defmacro gen-delay-expr (expression) "Delay EXPRESSION. Return a generator that evaluates EXPRESSION once (only), upon its first element request, and returns the evaluation result as that first element. It returns the same value thereafter, each time an element is requested." (let ((res (make-symbol "res")) (done (make-symbol "done"))) `(let (,res (,done nil)) (gen-make (if ,done ,res (prog1 ; expression can exit nonlocally, so set ,done at the end! (setq ,res ,expression) (setq ,done t))))))) ;; (defalias 'delay #'gen-delay-expr) ;; (defalias 'force #'gen-next) ;; Operations on generators, transducers (defun gen-filter (predicate generator) "Return a generator filtering GENERATOR with PREDICATE. This new generator will return elements in the same order as GENERATOR, but only those that fulfill PREDICATE, a function that accepts only one required argument." (let ((done nil) el) (gen-make (if done 'gen-done (setq el (gen-next generator)) (while (and (not (eq el 'gen-done)) (not (funcall predicate el))) (setq el (gen-next generator))) (if (eq el 'gen-done) (setq done 'gen-done) el))))) (defun gen-delq (elt generator) "Return a generator of the elements of GENERATOR not `eq' to ELT." (gen-filter (lambda (el) (not (eq el elt))) generator)) (defun gen-append (&rest generators) "Concatenate the GENERATORS. Return a new generator that returns the elements generated by each generator in GENERATORS, in order. The GENERATORS are each invoked to completion, in order, each taking the relay of its predecessor." (if (null generators) (gen-from-elts) (let ((current (pop generators)) el (done nil) (skip (make-symbol "skip= "))) (gen-delq skip (gen-make=20 (if done 'gen-done (setq el (gen-next current)) (if (eq el 'gen-done) (if (null generators) (progn (setq done t) 'gen-done) (setq current (pop generators)) skip) el))))))) (defun gen-map (function &rest generators) "Return a generator mapping FUNCTION across GENERATORS. If there are several GENERATORS, FUNCTION is called with that many arguments. The resulting generator will produce elements as long as the shortest generator does." (if (null generators) (gen-from-elts) (let ((done nil)) (gen-make (if done 'gen-done (let ((elts (mapcar #'gen-next generators))) (if (memq 'gen-done elts) (progn (setq done t) 'gen-done) (apply function elts)))))))) (defun gen-take-while (predicate generator) "Return a generator representing a \"do-while\" loop. This generator will invoke GENERATOR to produce elements as long they fulfill PREDICATE and stop then." (gen-map (lambda (el) (if (funcall predicate el) el 'gen-done)) generator)) (defun gen-take-until (predicate generator) "Return a generator representing an \"until-do\" loop. This generator will invoke GENERATOR to produce elements until one fulfills PREDICATE. It will stop after returning this element." (gen-map (let ((done nil)) (lambda (el) (if done 'gen-done (setq done (funcall predicate el)) el))) generator)) (defun gen-take (n generator) "Return a generator of the first N elements of GENERATOR. This generator generates at most the first N elements generated by GENERATOR, in order." (gen-take-while (lambda (el) (and (>=3D (cl-decf n) 0) (not (eq el 'gen-d= one)))) generator)) (defun gen-scan (function init generator) "Return a generator of successive reduced values. If the elements generated by generator g are g_1, g_2, ..., the elements h_1, h_2, ... of the generator returned by \(gen-scan f init g) are defined recursively by h_1 =3D init h_2 =3D (funcall f init g_1) h_(n+1) =3D (funcall f h_n g_n) as long as g_n exists. Example: (gen-scan #'* 1 (gen-number-range 1)) returns a generator of the factorials of the natural numbers." (let ((res init)) (gen-append (gen-from-elts res) (gen-map (lambda (el) (setq res (funcall function res el))) generator)= ))) ;; Iteration (cl-defmacro gen-do ((var generator) &rest body) "Loop over the elements of a generator. Evaluate BODY with VAR bound in turn to each element generated by GENERATOR." (declare (indent 1)) (let ((gen (make-symbol "g"))) `(let (,var (,gen ,generator)) (while (not (eq (setq ,var (gen-next ,gen)) 'gen-done)) ,@body)))) (defun gen-flush (generator) "Request all elements from GENERATOR, for side effects only." (while (not (eq (gen-next generator) 'gen-done)))) ;; Processing elements (defun gen-reduce (function init generator) "Reduce two-argument FUNCTION across GENERATOR starting with INIT. This is the same value as the expression (gen-last (gen-scan function init generator)) would return." (let ((res init)) (gen-flush (gen-map (lambda (el) (setq res (funcall function res el))) = generator)) res)) (defun gen-to-list (generator) "Convert GENERATOR into a list. Run GENERATOR until it runs out of elements and return a list of the generated elements." (nreverse (gen-reduce (lambda (x y) (cons y x)) () generator))) (defun gen-last (generator) "Request all elements from GENERATOR and return the last one. If generator produces zero elements, return gen-done." (gen-reduce (lambda (_ el) el) 'gen-done generator)) (defun gen-count (generator) "Request all elements from GENERATOR and return their count." (gen-reduce (lambda (s _el) (1+ s)) 0 generator)) (defun gen-some (predicate generator) "Return true if PREDICATE is true for any element of GENERATOR." (catch 'success (gen-flush (gen-map (lambda (elt) (when (funcall predicate elt) (throw 'success t))) generator)) nil)) (defun gen-every (predicate generator) "Return true if PREDICATE is true for every element of GENERATOR." (not (gen-some (lambda (arg) (not (funcall predicate arg))) generator))) (defun gen-max (generator &optional function) "Return an element of GENERATOR that maximizes FUNCTION. Request all elements from GENERATOR and pass them to FUNCTION, a one-argument function that must return a number. Return an element for which FUNCTION was maximal. Raise an error if GENERATOR produced no elements. FUNCTION defaults to `identity'. Example: if GENERATOR is a generator of lists, this would return a longest generated list: (gen-max g #'length)." (let ((first (gen-next generator))) (if (eq first 'gen-done) (error "Empty generator") (gen-reduce (if function (lambda (x y) (if (< (funcall function x) (funcall function y)) = y x)) #'<) first generator)))) (defun gen-min (generator &optional function) "Return an element of GENERATOR that minimizes FUNCTION. Request all elements from GENERATOR and pass them to FUNCTION, a one-argument function that must return a number. Return an element for which FUNCTION was minimal. Raise an error if GENERATOR produced no elements. FUNCTION defaults to `identity'." (cl-callf or function #'identity) (gen-max generator (and function (lambda (x) (- (funcall function x)))))) (defun gen-mapconcat (function generator separator) "Apply FUNCTION to each element of GENERATOR, and concat the results as s= trings. In between of each pair of results, stick in SEPARATOR. This is like `mapconcat', but for generators." (let ((first (gen-next generator))) (if (eq first 'gen-done) (error "Empty generator") (gen-reduce (lambda (x y) (concat x separator y)) (funcall function first) (gen-map function generator))))) ;; Caching (defun gen-cache (generator) "Return a cache object corresponding to generator GENERATOR. Turn GENERATOR into a cache. That cache can be used to clone \"client\" generators by using `gen-from-cache'. Requesting elements from any client generator works by first looking up elements in the cache as far as they already have been generated. Each client generator will produce the same sequence of elements, first returning all the cached elements as far as they already have been generated, and requesting further elements from GENERATOR when necessary to produce more elements. Newly created elements will silently be appended to the cache. Example: (let ((i 0)) (setq my-cache (gen-cache (gen-make (incf i) (message \"Calculating (sin(%S)+cos(%S))^3\" = i i) (expt (+ (sin i) (cos i)) 3))))) (setq g (gen-from-cache my-cache)) (gen-next g) \"Calculating (sin(1)+cos(1))^3\" =3D=3D> 2.638216188344211 (gen-next g) \"Calculating (sin(2)+cos(2))^3\" =3D=3D> 0.11993299299316301 (setq h (gen-from-cache my-cache)) (gen-next h) =3D=3D> 2.638216188344211 (gen-next h) =3D=3D> 0.11993299299316301 (gen-next h) \"Calculating (sin(3)+cos(3))^3\" =3D=3D> -0.6116843592476504" ;; This is just a transformation into a delayed list (cons (gen-delay-expr (gen-next generator)) (gen-delay-expr (gen-cache generator)))) (defun gen-from-cache (cache) "Clone a generator from CACHE. See `gen-cache' for more information." (gen-make (prog1 (gen-next (car cache)) (setq cache (gen-next (cdr cache)))))) (provide 'generator) ;;; generator.el ends here --=-=-=--