general lazy list facility for Emacs Lisp?

general lazy list facility for Emacs Lisp?

[Ted Zlatanov]

Is there a package for general lazy list management in Emacs Lisp?  I
couldn't find one.

Thanks
Ted

Re: general lazy list facility for Emacs Lisp?

[Tassilo Horn]

Ted Zlatanov <tzz@lifelogs.com> writes:

> Is there a package for general lazy list management in Emacs Lisp?

What's a lazy list?  Something like a LazySeq in Clojure, that is, a
possibly infinite sequence of things that are only calculated when
actually consumed ("realized")?

If that's what you mean, I think the answer is no.

Bye,
Tassilo

Re: general lazy list facility for Emacs Lisp?

[Ted Zlatanov]

On Wed, 23 Mar 2011 17:45:35 +0100 Tassilo Horn <tassilo@member.fsf.org> wrote: 

TH> Ted Zlatanov <tzz@lifelogs.com> writes:
>> Is there a package for general lazy list management in Emacs Lisp?

TH> What's a lazy list?  Something like a LazySeq in Clojure, that is, a
TH> possibly infinite sequence of things that are only calculated when
TH> actually consumed ("realized")?

TH> If that's what you mean, I think the answer is no.

Yes, that's what I mean.  In Haskell such lists are simply part of the
core language; Perl 5 can hack them together with list accessors; Perl 6
has them in the core too...  I think "lazy list" is a popular term for
the general facility?  I'm surprised no one has needed them, whatever
the name :)

Slightly related: is there a general memoization package or standard
approach to memoizing functions?

Ted

RE: general lazy list facility for Emacs Lisp?

[Drew Adams]

> > Is there a package for general lazy list management in Emacs Lisp?
> 
> What's a lazy list?  Something like a LazySeq in Clojure, that is, a
> possibly infinite sequence of things that are only calculated when
> actually consumed ("realized")?
> 
> If that's what you mean, I think the answer is no.

My guess is yes, that's what he meant.

Lazy lists in Lisp date from this paper, at least:
"Daniel P. Friedman and David S. Wise. "Cons should not evaluate its arguments,"
in S. Michaelson and R. Milner (eds.) Automata, Languages and Programming,
Edinburgh University Press (Edinburgh, 1976), 257--284."

This is probably pretty much the same paper:
"Friedman, Daniel P. (1976). Cons should not evaluate its arguments. ICALP."

Re: general lazy list facility for Emacs Lisp?

[Thierry Volpiatto]

Hi Ted,

Ted Zlatanov <tzz@lifelogs.com> writes:

> On Wed, 23 Mar 2011 17:45:35 +0100 Tassilo Horn <tassilo@member.fsf.org> wrote: 
>
> TH> Ted Zlatanov <tzz@lifelogs.com> writes:
>>> Is there a package for general lazy list management in Emacs Lisp?
>
> TH> What's a lazy list?  Something like a LazySeq in Clojure, that is, a
> TH> possibly infinite sequence of things that are only calculated when
> TH> actually consumed ("realized")?
>
> TH> If that's what you mean, I think the answer is no.
>
> Yes, that's what I mean.  In Haskell such lists are simply part of the
> core language; Perl 5 can hack them together with list accessors; Perl 6
> has them in the core too...  I think "lazy list" is a popular term for
> the general facility?  I'm surprised no one has needed them, whatever
> the name :)
Not sure to understand what you want, but maybe have a look at some
ioccur.el functions:

--8<---------------cut here---------------start------------->8---
ELISP> (setq A '(a b c d))
(a b c d)

ELISP> (setq it (ioccur-iter-circular A))

[...]

ELISP> (ioccur-iter-next it)
a
ELISP> (ioccur-iter-next it)
b
ELISP> (ioccur-iter-next it)
c
ELISP> (ioccur-iter-next it)
d
ELISP> (ioccur-iter-next it)
a
ELISP> (ioccur-iter-next it)
b
ELISP> (ioccur-iter-next it)
c
ELISP> (ioccur-iter-next it)
d
ELISP> (ioccur-iter-next it)
a
--8<---------------cut here---------------end--------------->8---
etc...etc...


> Slightly related: is there a general memoization package or standard
> approach to memoizing functions?
>
> Ted
>
>
>

-- 
A+ Thierry
Get my Gnupg key:
gpg --keyserver pgp.mit.edu --recv-keys 59F29997 

Re: general lazy list facility for Emacs Lisp?

[Ted Zlatanov]

On Wed, 23 Mar 2011 18:46:16 +0100 Thierry Volpiatto <thierry.volpiatto@gmail.com> wrote: 

TV> Not sure to understand what you want, but maybe have a look at some
TV> ioccur.el functions:
ELISP> (setq A '(a b c d))
TV> (a b c d)

ELISP> (setq it (ioccur-iter-circular A))

That's useful but I was thinking more of infinite lists,
e.g. http://landoflisp.com/lazy.lisp (that's a CL implementation but the
ELisp equivalent shouldn't be too bad).

Ted

Re: general lazy list facility for Emacs Lisp?

[Thierry Volpiatto]

Ted Zlatanov <tzz@lifelogs.com> writes:

> On Wed, 23 Mar 2011 18:46:16 +0100 Thierry Volpiatto <thierry.volpiatto@gmail.com> wrote: 
>
> TV> Not sure to understand what you want, but maybe have a look at some
> TV> ioccur.el functions:
> ELISP> (setq A '(a b c d))
> TV> (a b c d)
>
> ELISP> (setq it (ioccur-iter-circular A))
>
> That's useful but I was thinking more of infinite lists,
In this case ioccur-iter-circular produce infinite list.

> e.g. http://landoflisp.com/lazy.lisp (that's a CL implementation but the
> ELisp equivalent shouldn't be too bad).
Didn't look carefuly, but it seem to be the same mechanism, with
closures.

-- 
A+ Thierry
Get my Gnupg key:
gpg --keyserver pgp.mit.edu --recv-keys 59F29997 

Re: general lazy list facility for Emacs Lisp?

[Tassilo Horn]

Ted Zlatanov <tzz@lifelogs.com> writes:

Hi Ted,

> Yes, that's what I mean.  In Haskell such lists are simply part of the
> core language; Perl 5 can hack them together with list accessors; Perl
> 6 has them in the core too...  I think "lazy list" is a popular term
> for the general facility?  I'm surprised no one has needed them,
> whatever the name :)

Lately, I do some Clojure coding for fun, and I really enjoy lazy seqs
there.  However, I don't see a real use case in emacs.  So, pants off,
what are you planning to do?

> Slightly related: is there a general memoization package or standard
> approach to memoizing functions?

I think for "real" memoization, you need clojures.  However, I think you
can simulate memoization with a macro like that (tested only very
briefly).

--8<---------------cut here---------------start------------->8---
(defmacro memoize (name fun)
  (let ((map-name (gensym "memo-map"))
	(args-name (gensym))
	(val-name (gensym)))
    `(progn
       (defvar ,map-name (make-hash-table :test 'equal))
       (defun ,name (&rest ,args-name)
	 (let ((,val-name (gethash ,args-name ,map-name)))
	   (if ,val-name
	       ,val-name
	     (puthash ,args-name (apply (quote ,fun) ,args-name)
		      ,map-name)))))))

;; Create a memoized version of +
(memoize memo-+ +)
;; Call it
(memo-+ 1 1)
;; ==> 2
(memo-+)
;; ==> 2, not computed by looked up in the hash table
--8<---------------cut here---------------end--------------->8---

Bye,
Tassilo

Re: general lazy list facility for Emacs Lisp?

[Tassilo Horn]

Tassilo Horn <tassilo@member.fsf.org> writes:

> I think for "real" memoization, you need clojures.  However, I think
> you can simulate memoization with a macro like that (tested only very
> briefly).
>
> (defmacro memoize (name fun)
>   (let ((map-name (gensym "memo-map"))
> 	(args-name (gensym))
> 	(val-name (gensym)))
>     `(progn
>        (defvar ,map-name (make-hash-table :test 'equal))
>        (defun ,name (&rest ,args-name)
> 	 (let ((,val-name (gethash ,args-name ,map-name)))
> 	   (if ,val-name
> 	       ,val-name
> 	     (puthash ,args-name (apply (quote ,fun) ,args-name)
> 		      ,map-name)))))))

Just a short remark on what I've had in mind with "real" memoization: If
elisp had closures (not clojures ;-)), then one could write memoize as
function, just like the variant in the clojure source code below:

--8<---------------cut here---------------start------------->8---
(defn memoize
  [f]
  (let [mem (atom {})]
    (fn [& args]
      (if-let [e (find @mem args)]
        (val e)
        (let [ret (apply f args)]
          (swap! mem assoc args ret)
          ret)))))
--8<---------------cut here---------------end--------------->8---

Bye,
Tassilo

Re: general lazy list facility for Emacs Lisp?

[Ted Zlatanov]

On Wed, 23 Mar 2011 20:10:27 +0100 Tassilo Horn <tassilo@member.fsf.org> wrote: 

TH> Just a short remark on what I've had in mind with "real" memoization: If
TH> elisp had closures (not clojures ;-)), then one could write memoize as
TH> function

I think `lexical-let' (according to the docstring at least) creates true
CL-style closures in ELisp.

Ted

Re: general lazy list facility for Emacs Lisp?

[Stefan Monnier]

> Just a short remark on what I've had in mind with "real" memoization: If
> elisp had closures (not clojures ;-)), then one could write memoize as
> function, just like the variant in the clojure source code below:

On a related note:
Emacs has had closures for "ever", tho it only closes over variables
that are bound by `lexical-let' (provided by CL).  Emacs-24 will have
a more integrated and efficient support for closures, by setting the
`lexical-binding' variable which makes `let' bind lexically in the same
way as in Common-Lisp.  You can try it out right now in the
`lexbind-new' branch which is pretty much ready for inclusion (mostly
lacks testing, and has currently 1 open bug apparently around eieio;
additional testers are welcome).


        Stefan

Re: general lazy list facility for Emacs Lisp?

[Jason Earl]

On Wed, Mar 23 2011, Stefan Monnier wrote:

>> Just a short remark on what I've had in mind with "real" memoization: If
>> elisp had closures (not clojures ;-)), then one could write memoize as
>> function, just like the variant in the clojure source code below:
>
> On a related note:
> Emacs has had closures for "ever", tho it only closes over variables
> that are bound by `lexical-let' (provided by CL).  Emacs-24 will have
> a more integrated and efficient support for closures, by setting the
> `lexical-binding' variable which makes `let' bind lexically in the same
> way as in Common-Lisp.  You can try it out right now in the
> `lexbind-new' branch which is pretty much ready for inclusion (mostly
> lacks testing, and has currently 1 open bug apparently around eieio;
> additional testers are welcome).
>
>
>         Stefan

Do you have a url for the branch?

Jason

Re: general lazy list facility for Emacs Lisp?

[Tassilo Horn]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

Hi Stefan,

> Emacs has had closures for "ever", tho it only closes over variables
> that are bound by `lexical-let' (provided by CL).  Emacs-24 will have
> a more integrated and efficient support for closures, by setting the
> `lexical-binding' variable which makes `let' bind lexically in the
> same way as in Common-Lisp.  You can try it out right now in the
> `lexbind-new' branch which is pretty much ready for inclusion (mostly
> lacks testing, and has currently 1 open bug apparently around eieio;
> additional testers are welcome).

I've started compiling and will report issues if I find one in my daily
use.  I guess, that there are many packages that won't work with
lexical-binding set to t, right?

I mean, at least I've seen code that uses let in order to save some
parameters, like

  (let ((foo "bar"))
    (function-that-does-something-with-foo))

without defvar-ing foo.  I might be wrong, but I think I remember
org-mode did so in some places...

Bye,
Tassilo

Re: general lazy list facility for Emacs Lisp?

[Tassilo Horn]

Jason Earl <jearl@notengoamigos.org> writes:

> Do you have a url for the branch?

bzr://bzr.savannah.gnu.org/emacs/lexbind-new/

Bye,
Tassilo

Re: general lazy list facility for Emacs Lisp?

[Ted Zlatanov]

On Wed, 23 Mar 2011 20:03:06 +0100 Tassilo Horn <tassilo@member.fsf.org> wrote: 

TH> Lately, I do some Clojure coding for fun, and I really enjoy lazy seqs
TH> there.  However, I don't see a real use case in emacs.  So, pants off,
TH> what are you planning to do?

If I mention Haskell and Perl 6 in a sentence you can assume it's mostly
theoretical utility ;)

Seriously though, I want to use them for some private ELisp work looking
at large data sets.  They fit the data model well.

Ted

Re: general lazy list facility for Emacs Lisp?

[Ted Zlatanov]

On Wed, 23 Mar 2011 19:27:54 +0100 Thierry Volpiatto <thierry.volpiatto@gmail.com> wrote: 

TV> Ted Zlatanov <tzz@lifelogs.com> writes:
>> On Wed, 23 Mar 2011 18:46:16 +0100 Thierry Volpiatto <thierry.volpiatto@gmail.com> wrote: 
>> 
TV> Not sure to understand what you want, but maybe have a look at some
TV> ioccur.el functions:
ELISP> (setq A '(a b c d))
TV> (a b c d)
>> 
ELISP> (setq it (ioccur-iter-circular A))
>> 
>> That's useful but I was thinking more of infinite lists,
TV> In this case ioccur-iter-circular produce infinite list.

Hmm, it's not really what I had in mind, although it's certainly
useful...  The ioccur.el code returns an iterator across an existing
collection.  I need the next element dynamically generated, not
retrieved from a pre-existing collection.  The idea is to avoid the
memory and CPU usage until you know you need the data.  

I think Tassilo's macro or something similar with closures is closer to
my need and the general meaning of "lazy lists."

Ted

Re: general lazy list facility for Emacs Lisp?

[Tassilo Horn]

Tassilo Horn <tassilo@member.fsf.org> writes:

>> You can try it out right now in the `lexbind-new' branch which is
>> pretty much ready for inclusion (mostly lacks testing, and has
>> currently 1 open bug apparently around eieio; additional testers are
>> welcome).
>
> I've started compiling

Compiled it.

--8<---------------cut here---------------start------------->8---
(setq lexical-binding t)

(let ((x 1))
  (defun lex-test (y)
    (+ x y)))

(lex-test 1)
;; ==> 2
--8<---------------cut here---------------end--------------->8---

Wow! :-)

> and will report issues if I find one in my daily use.

Found one!  C-h k lexical-binding RET errors.  I've reported it, but the
confirmation mail has not yet arrived.

> I guess, that there are many packages that won't work with
> lexical-binding set to t, right?

Seems to be a false assumption.  At least org and Gnus are running fine.

Bye,
Tassilo

Re: general lazy list facility for Emacs Lisp?

[Ted Zlatanov]

On Wed, 23 Mar 2011 15:33:44 -0500 Ted Zlatanov <tzz@lifelogs.com> wrote: 

TZ> I think Tassilo's macro or something similar with closures is closer to
TZ> my need and the general meaning of "lazy lists."

s/Tassilo's macro/the landoflisp.com implementation/

Sorry for the confusion.

Ted

Re: general lazy list facility for Emacs Lisp?

[Stefan Monnier]

> (let ((x 1))
>   (defun lex-test (y)
>     (+ x y)))

Note that the byte-compiler won't like the above.  You'll want either

  (let ((x 1))
    (defalias 'lex-test (lambda (y) (+ x y))))

or

  (defalias 'lex-test (let ((x 1)) (lambda (y) (+ x y))))

or something like that.
  
>> and will report issues if I find one in my daily use.
> Found one!  C-h k lexical-binding RET errors.

Hmm... works here.

> I've reported it, but the confirmation mail has not yet arrived.

I'll wait for the precise report, then.

>> I guess, that there are many packages that won't work with
>> lexical-binding set to t, right?

Indeed.  Tho check the Elisp manual for hints about how to convert
(it's usually pretty easy).

> Seems to be a false assumption.  At least org and Gnus are running fine.

I think you're misunderstanding your test, because I doubt either of
Gnus or Org would work with lexical-binding without any
additional modification.
lexical-binding is a variable that applies to a file/buffer.  E.g. it
affects the compiler but not the compiled code.


        Stefan

Re: general lazy list facility for Emacs Lisp?

[Eric Schulte]

[-- Attachment #1: Type: text/plain, Size: 612 bytes --]

Ted Zlatanov <tzz@lifelogs.com> writes:

> On Wed, 23 Mar 2011 20:10:27 +0100 Tassilo Horn <tassilo@member.fsf.org> wrote: 
>
> TH> Just a short remark on what I've had in mind with "real" memoization: If
> TH> elisp had closures (not clojures ;-)), then one could write memoize as
> TH> function
>
> I think `lexical-let' (according to the docstring at least) creates true
> CL-style closures in ELisp.
>

Just for completeness, a lazy.el file is attached implementing lazy
sequences in Emacs Lisp.  This is basically an exact copy of lazy.lisp
with `lexical-let' used where closures are needed.

Best -- Eric


[-- Attachment #2: lazy.el --]
[-- Type: application/emacs-lisp, Size: 1974 bytes --]

Re: general lazy list facility for Emacs Lisp?

[Tassilo Horn]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

Hi Stefan,

> Note that the byte-compiler won't like the above.  You'll want either
>
>   (let ((x 1))
>     (defalias 'lex-test (lambda (y) (+ x y))))
>
> or
>
>   (defalias 'lex-test (let ((x 1)) (lambda (y) (+ x y))))
>
> or something like that.

Yes, I know, just wanted to check if it works at all.

>>> and will report issues if I find one in my daily use.
>> Found one!  C-h k lexical-binding RET errors.
>
> Hmm... works here.

Strange.

>> I've reported it, but the confirmation mail has not yet arrived.
>
> I'll wait for the precise report, then.

Oh, I'll have to add that this happens for any describe command, no
matter what I describe.  First I get that error, but after quitting the
debugger, I get the *Help* buffer anyway...

>>> I guess, that there are many packages that won't work with
>>> lexical-binding set to t, right?
>
> Indeed.  Tho check the Elisp manual for hints about how to convert
> (it's usually pretty easy).

Great, I'll see if I can help with some patches for transitioning the
packages I'm using most.

>> Seems to be a false assumption.  At least org and Gnus are running
>> fine.
>
> I think you're misunderstanding your test, because I doubt either of
> Gnus or Org would work with lexical-binding without any additional
> modification.  lexical-binding is a variable that applies to a
> file/buffer.  E.g. it affects the compiler but not the compiled code.

Ah, ok.  In the mean time, I've found out that Gnus does not build
(byte-compile) at all with a lexical-binding set to t.

Bye,
Tassilo

Re: general lazy list facility for Emacs Lisp?

[Ted Zlatanov]

On Wed, 23 Mar 2011 23:27:48 -0600 "Eric Schulte" <schulte.eric@gmail.com> wrote: 

ES> Just for completeness, a lazy.el file is attached implementing lazy
ES> sequences in Emacs Lisp.  This is basically an exact copy of lazy.lisp
ES> with `lexical-let' used where closures are needed.

Thanks, Eric.  I'm not sure of the http://landoflisp.com/lazy.lisp
license.  There's also http://www.common-lisp.org/project/clazy (very
similar to lazy.lisp), http://cl-heresy.sourceforge.net/Heresy.htm,
http://common-lisp.net/project/funds, and
http://www.common-lisp.org/project/fset all of which have different and
viable implementations (the common name seems to be "purely functional
data structures").  They all refer to SICP as a reference since it has a
similar implementation of the basic idea.  Of all of them, lazy.lisp
seems most basic; funds and fset seem very data-oriented.

Heresy seems like the most comprehensive and powerful package (see
http://cl-heresy.sourceforge.net/Heresy.htm for examples, details, and
functions provided).  I'd love to use it but I don't know CL well so it
will take me some time to port it.  Still, it has a BSD license and
should be OK as an ELPA package.  Does that sound reasonable?  Eric, are
you interested in helping me port it?

Thanks
Ted

Re: general lazy list facility for Emacs Lisp?

[Eric Schulte]

Ted Zlatanov <tzz@lifelogs.com> writes:

> On Wed, 23 Mar 2011 23:27:48 -0600 "Eric Schulte" <schulte.eric@gmail.com> wrote: 
>
> ES> Just for completeness, a lazy.el file is attached implementing lazy
> ES> sequences in Emacs Lisp.  This is basically an exact copy of lazy.lisp
> ES> with `lexical-let' used where closures are needed.
>
> Thanks, Eric.  I'm not sure of the http://landoflisp.com/lazy.lisp
> license.  There's also http://www.common-lisp.org/project/clazy (very
> similar to lazy.lisp), http://cl-heresy.sourceforge.net/Heresy.htm,
> http://common-lisp.net/project/funds, and
> http://www.common-lisp.org/project/fset all of which have different and
> viable implementations (the common name seems to be "purely functional
> data structures").  They all refer to SICP as a reference since it has a
> similar implementation of the basic idea.  Of all of them, lazy.lisp
> seems most basic; funds and fset seem very data-oriented.
>
> Heresy seems like the most comprehensive and powerful package (see
> http://cl-heresy.sourceforge.net/Heresy.htm for examples, details, and
> functions provided).  I'd love to use it but I don't know CL well so it
> will take me some time to port it.  Still, it has a BSD license and
> should be OK as an ELPA package.  Does that sound reasonable?  Eric, are
> you interested in helping me port it?
>

Sure, I can't guarantee any significant time commitment, but this would
serve as a good CL learning experience for me, so count me as /on board/
to help to port cl-heresy to elisp.

As a first step, I've copied the latest release of cl-heresy into a git
repository on repo.or.cz [1].  Anyone can anonymously push to the mob
branch of this repo (see [2]), and anyone who's interested in helping
can send me their repo.or.cz username and I'll grant push permission for
the master branch.

Best -- Eric

Footnotes: 
[1]  http://repo.or.cz/w/el-heresy.git

[2]  http://repo.or.cz/h/mob.html